顺序表

静态顺序表

test.c

//顺序表是物理地址连续的存储单元，一次存储数据元素的线性结构，在数组上实现数据增删查改
//顺序表一般可以分为
//1.静态的顺序表：使用定长数组存储
//2.动态的顺序表，使用动态开辟的数组进行存储

//1.连续的物理空间存储——数组
//2.数据必须是从头开始，依次存储，一个一个存

//静态的顺序表，给少了不够用，够多了浪费，不能灵活利用
#include"seqlist.h"

void testseqlist()
{
	SL s;
	seqlistinit(&s);//要把实参的地址传给形参
	seqlistpushback(&s, 1);
	seqlistpushback(&s, 2);
	seqlistpushback(&s, 3);
	seqlistpushback(&s, 4);
	seqlistpushback(&s, 5);
	seqlistpushback(&s, 6);
	seqlistpushback(&s, 7);
	seqlistpushback(&s, 8);
	seqlistpushback(&s, 9);
	seqlistpushback(&s, 10);
	seqlistpushback(&s, 11);

}
int main()
{
	testseqlist();
	return 0;
}

seqlist.c

#include"seqlist.h"
void seqlistinit(SL* ps)
{
	memset(ps->a, 0, sizeof(seqdata)*n);//对数组初始化为0
	ps->sz = 0;
}

void seqlistpushback(SL*ps, seqdata x)
{
	if (ps->sz >= n)
	{
		printf("seqlist is full\n");
		return;
	}
	ps->a[ps->sz] = x;//尾插在sz下一个位置的下标
	ps->sz++;
	//sz可能会超过数组的最大范围，会越界
}

seqlist.h

#pragma once
#include<stdio.h>
#include<string.h>
#define n 10
typedef int seqdata;

typedef struct seqlist
{
	seqdata a[n];
	int sz;
}SL;

void testseqlist();


//初始化一个数组
void seqlistinit(SL* ps);

//尾插
void seqlistpushback(SL*ps, seqdata x);

动态版顺序表

 

seqlist.h

#define _CRT_SECURE_NO_WARNINGS 1;

#pragma once
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<assert.h>
#define n 10
typedef int seqdata;

typedef struct seqlist
{
	seqdata *a;//指向动态开辟的数组
	int sz;//有效数据的个数
	int capacity;//记录容量
}SL;

void testseqlist();


//初始化一个数组
void seqlistinit(SL* ps);

//尾插
void seqlistpushback(SL*ps, seqdata x);

//打印
void seqlistprint(SL*ps);

//头插
void seqlistpushfront(SL *ps, seqdata x);
//检查容量是否充足
void seqlistcheckcapacity(SL*ps);

//尾删
void seqlistpopback(SL*ps);

//头删
void seqlistpopfront(SL*ps);

//中间插入
void seqlistinsert(SL*ps, int pos, seqdata x);

//中间删除
void seqlisterase(SL*ps, int pos);

//销毁
void seqlistdestroy(SL*ps);

//查
void seqlistfind(SL *ps, seqdata x);

//修改
void seqlistmodify(SL *ps,int pos, seqdata x);

seqlist.c

#include"seqlist.h"
void seqlistinit(SL* ps)//对顺序表进行初始化
{
	ps->a = NULL;
	ps->sz = 0;
	ps->capacity = 0;
}


//尾插
void seqlistpushback(SL*ps, seqdata x)
{
	seqlistcheckcapacity(ps);
	ps->a[ps->sz] = x;//尾插在sz下一个位置的下标
	ps->sz++;
	//sz可能会超过数组的最大范围，会越界
}


//打印
void seqlistprint(SL*ps)
{
	for (int i = 0; i < ps->sz; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

//头插
void seqlistpushfront(SL *ps, seqdata x)//同样面临一个增容的问题，但每次都写增容的代码很麻烦，所以我们可以写一个
{
	seqlistcheckcapacity(ps);
	int end = ps->sz - 1;
	//循环while的写法
	//1.初始条件
	//2.结束条件
	//3.迭代过程
	//头插就是每一位都往后挪,第一个位置空了出来
	
	while (end >= 0)//我们想的结束的条件，而循环写的是继续的条件
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[0] = x;//把第一个元素插入
	ps->sz++;

}

//搞出一个函数原来检查容量是否充足，如果不足就要增容
void seqlistcheckcapacity(SL*ps)
{
	if (ps->sz == ps->capacity)//有效数据对于最大容量，那么我们就要进行扩容
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//一开始sz为0，capacity也为0，所以当等于时有两种情况，
		//1.为开辟空间
		//2.sz到达了capabilities的容量
		//如果一开始的capaci的初值为0，就把capacity改为4，否则就把他扩容两倍
		//我们一般扩2倍，扩一倍浪费时间，扩3倍浪费空间
		seqdata *tmp = (seqdata*)realloc(ps->a, newcapacity * 2 * sizeof(seqdata));
		if (tmp == NULL)
		{
			printf("realloc failur");
			return;
		}
		else
		{
			ps->a = tmp;
			ps->capacity = newcapacity;
		}
	}
}
//尾删
void seqlistpopback(SL*ps)
{
	//假如说sz为0就不用删除了
	//但是如果想用粗暴的方法
	//断言，如果大于0就继续删除，等于0的化就会报错
	assert(ps->sz>0);
	//由sz来标识有多少个有效数据
	//直接把sz--，把有效数据减少就行了
	//如果我们把最后一个数据置为0，再sz--，不合适，因为可能最后一个元素本来就是一个0，或者他并不是int类型，是一个double类型的变量

	ps->sz--;
}
//头删
void seqlistpopfront(SL*ps)
{
	//同时也要预防头没有数据了
	assert(ps->sz > 0);
		int start = 1;
		//前一个都用后一个来覆盖
		while (start < ps->sz)
	{
			ps->a[start - 1] = ps->a[start];//start下标最多到sz-1的位置
			start++;
	}
		//头部数据删除完之后
		//同样sz也要减
		ps->sz--;
}

void seqlistinsert(SL*ps, int pos, seqdata x)
{
	//pos只能再sz有效数据里面进行选择
	assert(pos < ps->sz);
	seqlistcheckcapacity(ps);
	int end = ps->sz - 1;
	while (end>=pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	//直到end挪到小于pos就终止了
	ps->a[pos] = x;//pos是数组的下标
	ps->sz++;
}

void seqlisterase(SL*ps, int pos)
{
	//一次把后面的数据往前挪
	//把pos的位置给覆盖掉
	assert(pos < ps->sz);
	int start = pos + 1;
	while (start < ps->sz)
	{
		ps->a[start-1] = ps->a[start];
		start++;
	}
	ps->sz--;
}


void seqlistdestroy(SL*ps)//malloc出来的空间不销毁就会内存泄露
{
	free(ps->a);
	ps->a = NULL;
	ps->sz = ps->capacity = 0;
}

void seqlistfind(SL *ps, seqdata x)//如果有序的化就可以使用二分查找
{
	//假如是有序的化，就可以用二分查找，但他并不是有序的
	//那么我们就用暴力解法
	int i = 0;
	for (i = 0; i < ps->sz; i++)
	{
		if (ps->a[i] == x)
		{
			return i;//返回x的下标
		}
	}
	return -1;//如果找到的化就返回下标，每找到就返回-1，因为数组里面的下标不可能是-1
}

void seqlistmodify(SL *ps, int pos, seqdata x)
{
	assert(pos < ps->sz);
	ps->a[pos] = x;
}

 test.c

//顺序表是物理地址连续的存储单元，一次存储数据元素的线性结构，在数组上实现数据增删查改
//顺序表一般可以分为
//1.静态的顺序表：使用定长数组存储
//2.动态的顺序表，使用动态开辟的数组进行存储

//1.连续的物理空间存储——数组
//2.数据必须是从头开始，依次存储，一个一个存

//静态的顺序表，给少了不够用，够多了浪费，不能灵活利用
#include"seqlist.h"

void testseqlist()
{
	SL s;
	seqlistinit(&s);//要把实参的地址传给形参
	seqlistpushback(&s, 1);
	seqlistpushback(&s, 2);
	seqlistpushback(&s, 3);
	seqlistpushback(&s, 4);
	seqlistpushback(&s, 5);
	seqlistpushback(&s, 6);
	seqlistpushback(&s, 7);   
	seqlistpushback(&s, 8);
	seqlistpushback(&s, 9);
	seqlistpushback(&s, 10);
	seqlistpushback(&s, 11);
	seqlistpushfront(&s, 0);
	seqlistpushfront(&s, -1);
	seqlistpopfront(&s);
	seqlistpopback(&s);
	seqlistinsert(&s, 0, 20);//0数组的下标
	seqlisterase(&s, 0);
	seqlistprint(&s);
	seqlistdestroy(&s);

}
int main()
{
	testseqlist();
	return 0;
}

随后我会上传一些顺序表的oj