目录

线性表

顺序表

动态顺序表类型

初始化

 销毁

打印

检查空间是否充足（扩容）

尾部插入

头部插入

尾部删除

头部删除

指定位置插入

指定位置删除

查找数据

---

线性表

        线性表是n个相同特性的数据元素组成的有限序列，其是一种广泛运用的数据结构，常见的线性表有顺序表、栈、链表、队列等。

        其在逻辑上是线性的，物理结构（存储结构）上不一定是线性的。

---

顺序表

        顺序表就是线性表的一种，它在逻辑结构与物理结构上都是连续的，一般情况下它的底层就是数组，在数组基础上多了增删查改操作。

顺序表有静态顺序表和动态顺序表，我们常常采用动态顺序表，因为它的扩容方便、空间浪费更少。

---

动态顺序表类型

<code>typedef int SeqDataType;//将动态顺表的存储数据的类型重命名，方便后期统一修改

//动态顺序表

typedef struct SeqList {//命名：Sequence List顺序表

SeqDataType* arr;

int capacity;//动态顺序表的容量

int size;//动态顺序表的有效个数

}SL;

---

初始化

//初始化

void SLInit(SL* s) {

s->;arr = NULL;

s->capacity = s->size = 0;

}

---

 销毁

//销毁

void SLDestory(SL* s) {

if (!s->arr) {//等同于s->arr==NULL，判断要释放的空间是否是NULL，防止释放NULL

perror("Destory Fail");//打印错误

exit(1);

}

free(s->arr);//释放动态开辟的内存

s->arr = NULL;

s->capacity = s->size = 0;

}

---

打印

打印操作方便我们检查错误。

//打印

void SLPrint(SL* s) {

assert(s);

for (int i = 0; i < s->size; i++) {

printf("%d ", s->arr[i]);

}

printf("\n");

}

---

检查空间是否充足（扩容）

插入操作会扩大空间大小，那么在进行插入操作前，我们应该检查空间是否充足（扩容）

//检查空间是否充足（扩容）

void SLCheckCapacity(SL* s) {

if (s->capacity == s->size) {

//判断有效元素个数是否和空间大小相同，相同：空间用满了，要扩容

int newcapacity = s->capacity == 0 ? 4 : s->capacity * 2;

//空间是否为0,是：赋个初值4（防止按倍数扩容出错）

//不是：按两倍扩容，赋给临时变量，防止扩容失败对原capacity改变

SeqDataType* p = (SeqDataType*)realloc(s->arr, sizeof(SeqDataType) *newcapacity);

//这里是为s->arr扩容，不是为结构体（动态顺序表）

if (!p) {

perror("realloc fail");

exit(1);

}

s->arr = p;

s->capacity = newcapacity;

}

}

---

尾部插入

//尾插

void SLPushBack(SL* s, SeqDataType x) {

assert(s);

SLCheckCapacity(s);//检查空间是否充足

s->arr[s->size++] = x;//尾部插入数据，并使有效元素加1

}

---

头部插入

//头插

void SLPushFront(SL* s, SeqDataType x) {

assert(s);//

SLCheckCapacity(s);

for (int i = s->size ; i > 0; i--) {

s->arr[i] = s->arr[i-1];

}//将数据整体后移一位，腾出第一位给头插，且循环条件初始化i等于s->size

s->arr[0] = x;

s->size++;//别忘了将有效数据个数加一

}

---

尾部删除

//尾删

void SLPopBack(SL* s) {

assert(s->arr);//不能对空数组进行删除

assert(s->size);//不能对有效元素0个的数组进行删除

s->size--;//直接使有效元素个数减1即可

}

---

头部删除

//头删

void SLPopFront(SL* s) {

assert(s->arr);

assert(s->size);

for (int i = 0; i < s->size - 1; i++) {

s->arr[i] = s->arr[i + 1];

}//注意循环条件s->size-1，取到最后一个元素前一个位置

s->size--;

}

---

指定位置插入

//指定位置之前插入数据

void SLInsert(SL* s, int pos, SeqDataType x) {

assert(s);

assert(pos >= 0 && pos <= s->size);//pos=0时头插，pos=s->size时尾插，

SLCheckCapacity(s);

for (int i = s->size; i >pos; i++) {//从pos位置开始腾出位置给要插入的数据

s->arr[i] = s->arr[i - 1];

}

s->size++;

s->arr[pos] = x;

}

---

指定位置删除

//指定位置删除

void SLErase(SL* s, int pos) {

assert(s->arr);

assert(pos >= 0 && pos < s->size);//保证pos是可删除的

for (int i = pos; i < s->size - 1; i++) {//使pos以后的数据向前移一位

s->arr[i] = s->arr[i + 1];

}

s->size--;

}

---

查找数据

//查找数据

void SLFind(SL* s, SeqDataType x) {

assert(s->arr);

assert(s->size > 0);

for (int i = 0; i < s->size; i++) {//遍历顺序表，找到值返回下标，找不到，返回-1

if (s->arr[i] == x) {

return i;

}

}

return -1;

}

---

最后我们来测试一下我们写的代码