顺序表

---

title: 顺序表
Author: isyang_
date: 2023/3/24 23:59:05

顺序表（数据从第一个位置开始放，且连续存储）

一. 接口实现

头文件（.h）写定义 源文件（.c） 写具体实现

二. 顺序表的结构

typedef int SLDataType; //这里使用别名是为了方便修改数据表储存数据的类型

typedef struct SeqList
{
	SLDataType *a;//指向动态开辟的数组
	int size;     //目前有效存储数据个数
	int capacity; //开辟空间总容量
}SL;

三.顺序表各种接口函数实现（初始化 增容 销毁 打印 增 删 改 查 ）

1.顺序表的初始化

void SeqListInit (SL *ps){
	ps->a = NULL;//开辟内存之前给指针赋值为空，可以避免野指针出现（野指针是指指向未知地址或未分配内存空间的指针，如果程序试图访问该地址，就会导致程序崩溃或出现不可预知的后果）//
  ps->a = (SLDataType)malloc(sizeof(SLDataType)* 4);//初始开辟四个空间，不够再扩容;
	if(ps->a == NULL)  //开辟失败
	{ 
	  printf("申请内存失败");
	  exit(-1);
	}
	ps->size = 0;
	ps->capacity = 4;
};

2.顺序表的增容（检查容量，不够则增容）

void SLCheckCapacity (SL *ps){
	if (ps->size >= ps->capacity)
	{
		ps->capacity *= 2;
		ps->a = (SLDataType)realloc(ps->a, sizeof(SLDataType)*ps->capacity);
		if (ps->a == NULL)
		{
			printf("增容失败\n");
			exit(-1);
		}
	}
};

3.顺序表的销毁

void SeqListDestory(SL *ps){
	assert(ps != NULL)                    //判断是否为空
	free(ps->a);                          //先释放指针a指向的空间
	ps->a = NULL;                         //再将指针a赋空
	ps->capacity = 0;
	ps->size = 0;                         //最后将容量和数据个数赋0
};

4.顺序表的打印

void SeqListPrint (SL *ps){
	int i = 0;
	for (; i < ps->size; i++)             //size控制打印次数
	{
		printf("%d ", ps->a[i]);          //根据具体类型改输出格式
	}
	printf("\n");
};

5.顺序表的头插

void SeqListPushFront (SL *ps,SLDataType x){
	SLCheckCapacity(ps);                 //检查容量，不足则增容
	int end = ps->size;                  //控制挪动数据
	for(; end > 0; end--){
		ps->a[end] = ps->a[end-1];
	}
	ps->a[0] = x;
	ps->size++;                          //插入后size记得加1
};

6.顺序表的尾插

void SeqListPushBack (SL *ps,SLDataType x){
	SLCheckCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;
};

7.顺序表的任意位置（pos位置）插入

void SeqListInsert (SL *ps, int pos, SLDataType x){
	assert(pos >= 0 && pos <= ps->size); //判断pos的合法性
	SLCheckCapacity(ps);                 //检查容量，不足则增容
	int end = ps->size - 1;
	while(end >= pos)
	{ 
		ps->a[end+1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
};

8.顺序表的头删

void SeqListPopFront (SL *ps){
	assert(ps->size > 0);               //保证有数据可删
	int begin = 1;
	while (begin < ps->size)            //begin小于size时挪动数据
	{
		ps->a[begin - 1] = ps->a[begin];
		begin++;
	}
	ps->size--;
};

9.顺序表的尾删

void SeqListPopBack (SL *ps){
	assert(ps->size > 0);               //保证有数据可删
	ps->size--;
};

10.顺序表的任意位置（pos位置）删除

void SeqListErase (SL *ps, int pos){
	assert(pos >= 0 && pos < ps->size);//保证pos的合法性
	int begin = pos + 1;
	while(begin < ps->size)
	{
	 ps->a[begin-1] = ps->a[begin];
	 begin++;
	}
	 ps->size--;
};

11.顺序表的元素查找

int SeqListFind(SL *ps, SLDataType x){
  for (int i = 0; i < ps->size; i++){ //遍历顺序表
		if (ps->a[i] == x){           //找到数据返回下标
		    return i;
		}
	}
	return -1;                       //找不到返回-1
};

12.顺序表修改任意位置（pos位置）的数据

void SeqListAlter(SL *ps, int pos, SLDataType x){
    assert(pos >=0 && pos < ps->size);
    ps->a[pos] = x;
};

四.顺序表知识小结

(1)写代码时的注意点

1. 插入数据之前需要确保是否容量足够，插入完size+1
   
2. 删除数据之前需要确保是否有数据可删，删除完size-1
   
3. 在任意位置插入或者删除时要判断该位置是否合理
   
4. 空间开辟先给指针赋空，再用分配内存函数开辟空间
   
5. 为了方便检查报错，用到哪个指针，就用assert函数去判断该指针是否为空

(2)顺序表的优点和缺点

1. 顺序表的优点：
   顺序表可以通过索引（下标）快速地存、取表中元素。
2. 顺序表的缺点:
   ① 顺序表的插入和删除操作，会使得表中的大量元素进行移动，效率较低。
   ② 顺序表在面对扩容问题的时候，比较繁琐。当顺序表放满的时候，我们需要进行扩容。而扩容的大小需要面对不同的情况，若扩容的容量较大，那么会使得空间利用率较低；若扩容的容量较小，在后续的代码执行过程中，又需要不断地扩容操作，这使得代码变得更加繁琐。