1.什么是顺序表

1.顺序表：可动态增长的数组，要求数据是连续存储的

2.顺序表的定义：

静态顺序表：使用定长数组存储元素（缺点：小了不够用，大了还浪费）

动态顺序表：可根据我们的需要分配空间大小

2.顺序表的接口实现

 3.SeqList.h 头文件：

#pragma once#include <string.h>
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>typedef int SLDatatype;
typedef struct SeqList
{SLDatatype* a;//指向动态开辟的数组int size;  //储存有效数据的个数int capacity;//容量
}SL;void SLInit(SL* psl);//初始化顺序表
void SLDertroy(SL* psl);//销毁顺序表
void SLPrint(SL* psl);//打印顺序表void SLPushBack(SL* psl, SLDatatype x);//尾插
void SLPushFront(SL* psl, SLDatatype x);//头插
void SLPopBack(SL* psl);//尾删
void SLPopFront(SL* psl);//头删void SLInsert(SL* psl, int pos, SLDatatype x);//指定下标插入
void SLErase(SL* psl, int pos);//指定下标删除// 找到返回下标，没有找到返回-1
int SLFind(SL* psl, SLDatatype x);//查找指定值
void SLModify(SL* psl, int pos, SLDatatype x);//修改指定下标数据

SeqList.c 各个接口函数的使用：

1.初始化顺序表

加上断言，防止传进来的指针为空

capacity是使它空间容量变为4

size是有效数据个数置为0

void SLInit(SL* psl)
{assert(psl);psl->a = (SLDatatype*)malloc(sizeof(SLDatatype) * 4);if (psl->a == NULL){perror("malloc fail");return;}psl->size = 0;psl->capacity = 4;
}

2.销毁数组

防止内存泄漏一定要释放内存

void SLDestroy(SL* psl)
{assert(psl);free(psl->a);psl->a = NULL;psl->size = 0;psl->capacity = 0;
}

3.打印数组

这里就没有什么说的

void SLPrint(SL* psl)
{assert(psl);for (int i = 0; i < psl->size; i++){printf("%d ", psl -> a[i]);}printf("\\n");
}

4.检查顺序表容量是否满了，好进行增容

这里我们要注意，我们在扩容时不用去一个一个扩容，太费劲了，我们可以直接可以扩容2倍，这样既不会太大而产生浪费，也不会太小而不够

void SLCheckCapacity(SL* psl)
{assert(psl);if (psl->size == psl->capacity){SLDatatype* tmp = (SLDatatype*)realloc(psl->a, sizeof(SLDatatype) * psl->capacity * 2);if (tmp == NULL){perror("realloc fail");return;}psl->a = tmp;psl->capacity *= 2;}
}

5.尾插

void SLPushBack(SL* psl, SLDatatype x)
{assert(psl);SLCheckCapacity(psl)psl->a[psl->size] = x;psl->size++;//psl->a[psl->size++] = x;（上面写法和下面写法都可以）
}

6.头插

这里我们要注意一下，end = psl -> size - 1,这里我们要说明一下，画图解决问题，我们现在size的位置是最后一个数据的下一位，所以我们要减1

void SLPushFront(SL* psl, SLDatatype x)
{assert(psl);SLCheckCapacity(psl);//检查容量是否充足// 挪动数据int end = psl->size - 1;while (end >= 0){psl->a[end + 1] = psl->a[end];//让每个数据都向前移动一位--end;}psl->a[0] = x;//将数据插入头部psl->size++;//记录有效数据}

7.尾删

这里我们会发现有两种检查方法：我个人最喜欢的是暴力检查方法（这里不用过多的说明）

温柔检查方法：不知道 SLDataType 是什么类型的数据，不能冒然的将顺序表最后一个数据赋值为 0，我们只需将有效数据个数 size 减 1 即可达到尾删的目的

void SLPopBack(SL* psl)
{assert(psl);//暴力检查assert(psl->size > 0);// 温柔的检查//if (psl->size == 0)//	return;//psl->a[psl->size - 1] = 0;//psl->size--;}

8.头删

这里面有两个方法都一样，只是数组的下角标不同，整体思想就是让后面的数据往前移动一位，size别忘了减1

void SLPopFront(SL* psl)
{assert(psl);// 暴力检查assert(psl->size > 0);int start = 0;while (start < psl->size-1){psl->a[start] = psl->a[start + 1];start++;}//int start = 1;//while (start < psl->size)//{//	psl->a[start-1] = psl->a[start];//	start++;//}psl->size--;}

9.指定下标插入

这里前面就不用过多说明了，我们在执行循环语句的时候，要想数据插入到数组中，我们需要把要插入数据后面的数据依次向后面移动，给你要插入数据的位置留出来（我们在写完这个代码的时候可以更改前面的头插，和尾插）

void SLInsert(SL* psl, int pos, SLDatatype x)
{assert(psl);//assert(0 <= pos <= psl->size);assert(0 <= pos && pos <= psl->size);SLCheckCapacity(psl);int end = psl->size - 1;while (end >= pos){psl->a[end + 1] = psl->a[end];--end;}psl->a[pos] = x;psl->size++;
}

10.指定下标删除

思想和上面——下标插入，的思想一样，无非就是把数据往前移动一位呗（这里也可以更改前面头删和尾删）

void SLErase(SL* psl, int pos)
{assert(psl);assert(0 <= pos && pos < psl->size);//assert(psl->size > 0);int start = pos + 1;while (start < psl->size){psl->a[start - 1] = psl->a[start];++start;}psl->size--;
}

11.查找指定值

int SLFind(SL* psl, SLDatatype x)
{assert(psl);for (int i = 0; i < psl->size; i++){if (psl->a[i] == x){return i;}}return -1;
}

12.修改指定下标数据

void SLModify(SL* psl, int pos, SLDatatype x)
{assert(psl);assert(0 <= pos && pos < psl->size);psl->a[pos] = x;
}

这里我们要补充一点：越界不一定报错，系统对越界的检查是一种抽查，

• 越界读一般是检查不出来的

• 越界写如果是修改到标志位才会检查出来

（系统在数组末尾后设的有标志位，越界写时，恰好修改到标志位了，就会被检查出来）

以上就是我们今天的文章分享，感谢您的关注和点赞！！！