顺序表基础

在C语言中，顺序表是一种线性表的实现方式，通常使用数组作为底层存储结构。顺序表具有高效的随机访问特性，也可对元素进行插入和删除操作。主要用到动态内存管理（malloc,realloc,calloc,free），数组，结构体，指针,一般推荐使用动态顺序表。

//静态顺序表
struct Seplist
{
  int arr[100];//定长数组
  int size;//顺序表当前有效元素个数
}
//动态顺序表
struct Seplist
{
  int *arr;
  int  size;//有效的数据个数
  int capacity;//空间大小
  }

动态顺序表优势在于可根据具体情况增容，使用时要注意释放内存和指针置空。

typedef int SLDataType;//为方便后续对顺序表元素类型创建的改变，例如，要建立char型，直接将代码中int变为char即可
typedef struct Seplist
{
  int *arr;
  int  size;//有效的数据个数
  int capacity;//空间大小
  }SL;
//typedef struct Seplist SL;//给顺序表结构体起名，方便后面书写

 顺序表初始化

void SLIint(SL* ps)
{
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

顺序表销毁

void SLDestroy(SL* ps)
{
	if (ps->arr)
	{
		free(ps->arr);
	}
	ps->arr = NULL;
	ps->size = ps->capacity = 0;
}

尾部插入

void SLPushBack(SL* ps, SLDataType x)//尾部插入，x表示插入的数
//这里得注意数组的越界访问，得扩大内存
{
	assert(ps);//等价于assert(ps!=NULL)
	if (ps->size == ps->capacity)//申请空间，增容一般为二倍，三倍更合理，频繁增容影响效率
	{
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//三目运算符，判断capacity大小，如果为0，则capacity赋值为4，并开辟空间，不为0则变为2倍，也可在顺序表建立时直接赋值并开辟相应空间
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));
		if (NULL == tmp)//判断开辟是否成功
		{
			perror("realloc fail");
			exit(1);  //直接退出，不再执行    
		}
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
	ps->arr[ps->size] = x;
	ps->size++;
	//ps->arr[ps->size++];(也可以这样写，但可读性低)
}

头部插入

void SLCheckcapacity(SL* ps)//插入数据前看内存够不够
{
	if (ps->size == ps->capacity)//申请空间，增容一般为二倍，三倍更合理，频繁增容影响效率
	{
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//三目运算符，判断capacity大小，如果为0，则capacity赋值为4，并开辟空间，不为0则变为2倍，也可在顺序表建立时直接赋值并开辟相应空间
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));
			if (NULL == tmp)//判断开辟是否成功
			{
				perror("realloc fail");
				exit(1);  //直接退出，不再执行    
			}
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
}
void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	SLCheckcapacity(ps);
	for (int i = ps->size; i > 0; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}
	ps->arr[0] = x;
	ps->size++;
}

尾部删除

void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size);//顺序表不为空
		ps->size--;
}

 头部删除

void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size);
	for (int i = 0; i < ps->size - 1; i++)
	{
		ps->arr[i] = ps->arr[i + 1];
	}
	ps->size--;
}

 打印

void SLprint(SL s)
{
	for (int i = 0; i < s.size; i++)
	{
		printf("%d ", s.arr[i]);
	}
	printf("\n");
}

建议将上述所有函数名写入"Seplist.h"的自建头文件中

将对应函数写入"Seplist.c"的文件中，再创建别的文件建立main函数去验证每个顺序表函数的正确性

#include "Seplist.h"

void SLTest01()
{
	SL  sl;
	SLIint(&sl);//注意这里的传址调用，直接传值不行，思考函数栈帧的创建和销毁过程很容易解决，下面一样
	//测试尾插
	SLPushBack(&sl, 1);
	SLPushBack(&sl, 2);
	SLPushBack(&sl, 3);
	SLPushBack(&sl, 4);
	SLprint(sl);//因为SLprint函数不需要改变顺序表内容并成功返回，只需要传给结构体变量，按照结构体打印即可
	//测试头插
	SLPushFront(&sl, 5);
	SLPushFront(&sl, 6);
	SLprint(sl);
//测试尾部删除
	SLPopBack(&sl);
	SLprint(sl);
	//测试头部删除
	SLPopFront(&sl);
	SLprint(sl);

	SLDestroy(&sl);
}


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

运行代码如下