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

目录

• 前言
• 一、线性表定义
• 二、顺序表实现

• 1概念及结构
• 2静态顺序表

• 2.1实现顺序表接口，第一步要对顺序表进行初始化
• 2.2对顺序表的增删查改的接口函数（以尾插为例）

• 3.1动态顺序表初始化
• 3.2动态顺序表-尾插
• 3.3动态顺序表-头插
• 3.4动态顺序表-尾删
• 3.5动态顺序表-头删
• 3.6动态顺序表-任意位置插入数据
• 3.7动态顺序表-任意位置删除数据

#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--;
}