C语言数据结构顺序表 C语言编程简单却重要的数据结构顺序表全面讲解

#define N 10//这里定义宏是为了方便将来如果需要更改空间的大小而代码中用到的10过于多要更改多次宏定义直接改N大小即可
typedef int SQDataType;//这里顺序表10个空间都是int型如果将来要改变类型可以在这里把int改为所需类型
struct SeqList//单个数据直接定义变量多个数据定义结构体
{
	SQDataType a[N];//顺序表有10个空间可进行存储
	int size;//顺序表存了几个数据（有10个空间不一定就存10个数据）
};

#include<stdio.h>
#include<string.h>//memset函数头文件
//增删查改等接口函数
void SeqListInit(struct SeqList *ps)
{
	memset(ps->a, 0, sizeof(SQDataType)*N);//memset是一个初始化函数
	//sl.a表示按字节初始化
	//0表示初始化为0
	//sizeof(SQDataType)表示数组内每个元素大小(之前定义了SQDataType=int)N表示数组内共有N个元素两者相乘是数组大小
	ps->size = 0;
}
void TestSeqList1()
{
	struct SeqList sl;//sl是实参上面的ps是形参,为了实参和形参可以相互影响这里用的是传址调用
	SeqListInit(&sl);
}
int main()
{
	TestSeqList1();
	return 0;
}
//ps:如果这里你觉得写struct SeqList sl烦你可以这样改进代码（这里和2.1代码对应）
//typedef struct SeqList//单个数据直接定义变量多个数据定义结构体
//{
//	SQDataType a[N];//顺序表有10个空间可进行存储
//	int size;//顺序表存了几个数据（有10个空间不一定就存10个数据）
//}SL;
//这样结构体类型就可以直接写成SL

void SeqListPushBack(struct SeqList *ps, SQDataType x)//尾插
{
	if (ps->size >= N)
	{
		printf("SeqList is full");//防止你尾插太多已经大于了顺序表最大容量
		return;
	}
	ps->a[ps->size] = x;
	ps->size++;//存储的数据多了一个size加1个
}

typedef int SQDataType;
struct SeqList
{
	SQDataType*a;
	int size;//有效数据个数
	int capacity;//容量
};
//由于没有数组a了所以顺序表初始化也要改一下
void SeqListInit(struct SeqList *ps)
{
	ps->a = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

void SeqListPushBack(struct SeqList *ps, SQDataType x)
{	
	if (ps->size == ps->capacity)//原先空间满了无法进行尾插了需要进行扩容（扩容一般扩2倍）
	{
		int newcapacity = ps->capacity==0?4:ps->capacity*2;//这个4是可以换其他数的
		//这里是防止原来的容量是0扩容后的倍数仍然是0
		SQDataType*tmp = (SQDataType*)realloc(ps->a, newcapacity* sizeof(SQDataType));
		if (tmp == NULL)//防止扩容失败也就是没有剩余空间供它使用了
		{
			printf("realloc is fail\n");
			exit(-1);//退出运行
		}
		else
		{
			ps->a = tmp;
			ps->capacity = newcapacity;
		}
	}
	ps->a[ps->size] = x;
	ps->size++;//存储的数据多了一个size加1个
}

void SeqListPushFront(struct SeqList *ps, SQDataType x)
{
//原先空间满了需要进行扩容
	if (ps->size == ps->capacity)
	{
		int newcapacity = ps->capacity==0?4:ps->capacity*2;
		//这里是防止原来的容量是0扩容后的倍数仍然是0
		SQDataType*tmp = (SQDataType*)realloc(ps->a, newcapacity* sizeof(SQDataType));
		if (tmp == NULL)//防止扩容失败也就是没有剩余空间供它使用了
		{
			printf("realloc is fail\n");
			exit(-1);
		}
		else
		{
			ps->a = tmp;
			ps->capacity = newcapacity;
		}
	}
	int end = ps->size - 1;//确定最后一个内容下标
	while (end >= 0)
	{
		ps->a[end + 1] = ps->a[end];//以此把原先的内容往后挪一位
		--end;
	}
	ps->a[0] = x;//把需要插入的内容放在最开始的空间
	ps->size++;
}

void SeqListPopBack(struct SeqList *ps)
{
	assert(ps->size > 0);
	//要进行删除首先要有东西可删
	//这里会进行断言如果没有东西删会报错
	ps->size--;
}

void SeqListPopFront(struct SeqList *ps)
{
	assert(ps->size > 0);
	int start = 1;
	while (start < ps->size)
	{
		ps->a[start - 1] = ps->a[start];
		++start;
	}
	ps->size--;
}

void SeqListInsert(struct SeqList *ps, int pos, SQDataType x)
//pos表示插入位置的下标
{
	assert(pos < ps->size);//防止在尾部插入构成非法访问
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}

void SeqListErase(struct SeqList *ps, int pos)
{
	assert(pos < ps->size);
	int start =pos + 1;
	while (start < ps->size)
	{
		ps->a[start - 1] = ps->a[start];
		start++;
	}
	ps->size--;
}