【数据结构】顺序表

前言

• 顺序表作为数据结构中的小小弟，还是很好应付的。说到数据结构，顺序表是我们的向导，它让你明白数据结构到底是干啥的，为啥数据结构这么的重要。

• 实际上，通讯录的底层就是一个顺序表，里面的增添联系人，删除联系人等一系列操作，都是基于顺序表实现的，这也侧面拖出了数据结构的作用。所以，学好数据结构是必须的。

• 要是能够自主实现通讯录，我肯定，顺序表学起来会非常的轻松。

---

初始化顺序表

• 实现顺序表需要三个文件：一个是.h为后缀的头文件SeqList.h：用来放相关头文件，宏定义，结构体声明，以及函数声明。一个是.c为后缀的C文件SeqList.c：用来实现函数接口。还有一个是.c为后缀的C文件test.c：用来测试代码。我们只要在SeqList.c文件和test.c文件最上面包含一下 SeqList.h文件，整个程序链接就OK了。

下面是所需头文件，宏定义，以及顺序表的定义的代码：

// 防止SeqList.h被重复包含
#pragma once// 所需头文件：
// 输入输出所需头文件
#include <stdio.h>
// realloc，free所需头文件
#include <stdlib.h>
// 判空所需头文件
#include <stdbool.h>
// assert断言所需头文件
#include <assert.h>// 初始化容量，每次增容也是增加这个数量
#define INIT_CAPACITY 8
// 这个为顺序表的数据类型
typedef int SLDateType;// 顺序表
typedef struct SeqList
{// a指向一个在堆上的空间（就是顺序表）SLDateType* a;// 顺序表数据个数int size;// 顺序表容量int capacity;
}SL;  // typedef将struct SeqList重新命名为SL

• 定义好主体后，首先是对顺序表初始化。可以看到，上面的结构体也就是顺序表里面的成员都是未初始化的，所以第一步就是将他们初始化，这里引出一个初始化函数接口，下面是相关功能代码实现：

// 初始化顺序表
void SLInit(SL* ps)
{// 这里断言是防止ps为一个空指针（传个NULL直接暴打）assert(ps);ps->a = NULL;ps->size = 0;ps->capacity = 0;
}

---

打印顺序表

• 该接口放在前面实现是为了后面能够更好的测试：通过对顺序表的数据的一个直观的展现，我们可以及时发现某些接口的bug。

• 顺序表的结构体中定义了一个size，这里size的作用就体现出来了（当然，size的作用很大，不止是这里），我们可以通过size来对顺序表中的数据顺序打印：

// 打印顺序表
void SLPrint(SL* ps)
{assert(ps);for (int i = 0; i < ps->size; i++) printf("%d ", ps->a[i]);printf("\n");
}

---

检查容量

• 当我们在顺序表中插入数据时，一定要检查容量够不够用，如果不够的话，再插入数据，就会出现非法访问空间的问题，此时程序会报错，因此这里要扩容。

• 由于size是统计数据个数的，所以，只要size等于capacity，就说明当前的容量已经满了，需要扩容。由于初始化顺序表时没有分配空间，所以当我们第一次插入数据的时候就要扩容，每次扩容增加的容量大小为INIT_CAPACITY(8)，而每增容一次，capacity就要更新一次。

下面是相关功能代码实现：

// 检查容量
void SLCheckCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity){int newcapacity = ps->capacity == 0 ? INIT_CAPACITY : ps->capacity + INIT_CAPACITY;// 开始没有空间，其功能相当于mallocSLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * newcapacity);assert(tmp);ps->a = tmp;ps->capacity = newcapacity;}
}

这一步实现后，每次插入数据就要引用该函数检查一下容量。

---

判空

• 判空很容易理解，这里如果通讯录为空，返回真，不为空，返回假。

下面是相关功能代码实现：

// 判空
bool SLEmpty(SL* ps)
{assert(ps);return ps->size == 0;
}

---

顺序表数据个数

• 该功能只要返回size就ok啦。

// 顺序表数据个数
int SLSize(SL* ps)
{assert(ps);return ps->size;
}

---

尾部插入

• 尾部插入就是在最末尾插入数据，首先当然是要检查一下容量，然后将要插入的数据插入进去，最后size计数一次，该函数的功能就OK啦。

下面是相关功能代码实现：

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

---

尾部删除

• 如果顺序表中没有数据，那还删个啥呢？直接assert暴打，也就是判断一下size是否大于0(判空一下)。

• 尾部删除实际上只要size减一就可以了，至于删除的那个数据改不改为0，都无所谓，因为打印不会打印到那个数据，还有就是，不能在那个位置释放空间（free）,这是规定不允许的，要有占着茅坑不拉屎的原则。

下面是相关功能代码实现：

void SLPopBack(SL* ps)
{assert(ps && !SLEmpty(ps));ps->size--;
}

---

头部插入

• 对顺序表头部的操作相比于尾部的操作麻烦的多，主要是因为，顺序表是一段连续的空间，在头部插入或者删除需要挪动后面的数据，这样以来，整个程序的效率也会降低，但这是没办法的，该挪动还是嘚挪动，不然怎么进行操作对吧。（顺序表最明显的缺点）

• 挪动的时候，只要从后面开始依次将每一个数据向后挪动一位，直到将第一个数据挪动完停止挪动，再将要插入的数据放在头部即可，这里需要注意以下边界问题。

• 当然size要计数一次，可不敢忘记了。

下面是相关功能代码实现：

void SLPushFront(SL* ps, SLDateType x)
{assert(ps);SLCheckCapacity(ps);for (int i = ps->size; i > 0; i--) ps->a[i] = ps->a[i - 1];ps->a[0] = x;ps->size++;
}

---

头部删除

• 只要是删除就要assert判断是否要暴打。

• 有了头部插入的经验，头部删除显得游刃有余了，相反的，只要将每个数据向前挪动，也就是依次覆盖即可，最终第一个数据被覆盖的无影无踪。

• 当然size要减一，可不敢忘记了。

下面是相关功能代码实现：

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

---

在pos位置插入数据

• 首先插入需要检查容量。

• 在pos位置插入数据，首先对这个pos理解一下：本章的pos不是下标，注意！他不是下标，而是规规矩矩的第几个位置，比如一串数列1，2，3，4，第一个位置就是只1所占的位置，如果要在第一个位置插入，那么1就会到当前的2的位置上去，也就是所谓的第二个位置。所以，这个pos，是以用户角度出发，但我们实现函数的时候要脑子清醒：我们操作的实际上是下标。

• 同样的，与头插差不多，都是要挪动数据，只不过挪动的数据范围不同，要操作的数的位置也不同，这也就更加要注意边界问题了。

• 当然，操作完成后，要记得size计数一次噢。

下面是相关功能代码实现：

// 在pos位置插入,pos表示在第几个位置插入，不是下标
void SLInsert(SL* ps, int pos, SLDateType x)
{assert(ps);SLCheckCapacity(ps);for (int i = ps->size; i > pos - 1; i--) ps->a[i] = ps->a[i - 1];ps->a[pos - 1] = x;ps->size++;
}

有了该函数之后，前面的头插尾插都可以复用这个函数。

---

删除pos位置的数据

• 既然是删除，首先就要来一套assert检查看是否要毒打。

• 删除，就是将pos后面的数据依次往前挪，最终pos这个位置上的数据会被覆盖，因为会挪动数据，依次效率也不是很高。

• 当然别忘了size减一噢。

下面是相关功能代码实现：

// 删除第pos个数据，pos不是下标，表示删除第几个
void SLErase(SL* ps, int pos)
{assert(ps && !SLEmpty(ps) && pos > 0 && pos <= ps->size);for (int i = pos - 1; i < ps->size - 1; i++) ps->a[i] = ps->a[i + 1];ps->size--;
}

有了该函数后，前面的头删，尾删都可以复用这个函数。

---

查找数据

• 查找数据就是遍历一遍顺序表，如果找到了就返回下标加一，没找到就返回-1。

下面是相关功能代码实现：

// 查找数据，返回正常对应位置，不是下标位置, 没找到返回-1
int SLFind(SL* ps, SLDateType val)
{assert(ps);for (int i = 0; i < ps->size; i++)if (ps->a[i] == val) return i + 1;return -1;
}

---

修改数据

• 修改数据也是根据pos位置来修改的，传入你想修改的位置，然后传入修改后的新数据，然后直接在pos - 1(下标)位置修改，不需要遍历。

• 如果传入的pos不正确，直接暴打。

• 当然也可以先查找，在修改，也就是说，查找数据和修改数据两个接口函数可以一起用。

**下面是相关功能代码实现：**```c
// 修改数据,修改pos正常对应位置，不是下标
void SLModify(SL* ps, int pos, SLDateType Mval)
{assert(ps && pos > 0 && pos <= ps->size);ps->a[pos - 1] = Mval;
}

---

销毁顺序表

• 由于向堆申请了空间，因此程序结束后需要将空间返还给系统，这里说的粗暴了点，销毁顺序表。

下面是相关功能代码实现：

// 销毁顺序表
void SLDestroy(SL* ps)
{assert(ps);free(ps->a);ps->capacity = 0;ps->size = 0;
}

---

整体代码

SeqList.h

// 防止SeqList.h被重复包含
#pragma once// 所需头文件：
// 输入输出所需头文件
#include <stdio.h>
// realloc，free所需头文件
#include <stdlib.h>
// 判空所需头文件
#include <stdbool.h>
// assert断言所需头文件
#include <assert.h>// 初始化容量，每次增容也是增加这个数量
#define INIT_CAPACITY 8
// 这个为顺序表的数据类型
typedef int SLDateType;// 顺序表
typedef struct SeqList
{// a指向一个在堆上的空间（就是顺序表）SLDateType* a;// 顺序表数据个数int size;// 顺序表容量int capacity;
}SL;  // typedef将struct SeqList重新命名为SL// 初始化顺序表
void SLInit(SL* ps);
// 打印顺序表
void SLPrint(SL* ps);// 检查容量
void SLCheckCapacity(SL* ps);// 尾插 尾删 头插 头删
void SLPushBack(SL* ps, SLDateType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDateType x);
void SLPopFront(SL* ps);
// 在pos位置插入,pos表示在第几个位置插入，不是下标
void SLInsert(SL* ps, int pos, SLDateType x);
// 删除第pos个数据，pos不是下标，表示删除第几个
void SLErase(SL* ps, int pos);// 查找数据，返回对应位置，不是下标位置, 没找到返回-1
int SLFind(SL* ps, SLDateType val);
// 修改数据
void SLModify(SL* ps, int pos, SLDateType Mval);// 判空
bool SLEmpty(SL* ps);
// 顺序表数据个数
int SLSize(SL* ps);// 使用了realloc，在堆上申请了空间，程序结束时要返还空间给系统
// 销毁顺序表
void SLDestroy(SL* ps);

SeqList.c

#include "SeqList.h"// 初始化顺序表
void SLInit(SL* ps)
{assert(ps);ps->a = NULL;ps->size = 0;ps->capacity = 0;
}
// 打印顺序表
void SLPrint(SL* ps)
{assert(ps);for (int i = 0; i < ps->size; i++) printf("%d ", ps->a[i]);printf("\n");
}// 检查容量
void SLCheckCapacity(SL* ps)
{assert(ps);if (ps->size == ps->capacity){int newcapacity = ps->capacity == 0 ? INIT_CAPACITY : ps->capacity + INIT_CAPACITY;// 开始没有空间，其功能相当于mallocSLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * newcapacity);assert(tmp);ps->a = tmp;ps->capacity = newcapacity;}
}// 尾插 尾删 头插 头删
void SLPushBack(SL* ps, SLDateType x)
{//assert(ps);//SLCheckCapacity(ps);//ps->a[ps->size++] = x;SLInsert(ps, ps->size + 1, x);
}
void SLPopBack(SL* ps)
{//assert(ps && !SLEmpty(ps));//ps->size--;SLErase(ps, ps->size);
}
void SLPushFront(SL* ps, SLDateType x)
{//assert(ps);//SLCheckCapacity(ps);//for (int i = ps->size; i > 0; i--) ps->a[i] = ps->a[i - 1];//ps->a[0] = x;//ps->size++;SLInsert(ps, 1, x);
}
void SLPopFront(SL* ps)
{//assert(ps && !SLEmpty(ps));//for (int i = 0; i < ps->size - 1; i++) ps->a[i] = ps->a[i + 1];//ps->size--;SLErase(ps, 1);
}
// 在pos位置插入,pos表示在第几个位置插入，不是下标
void SLInsert(SL* ps, int pos, SLDateType x)
{assert(ps);SLCheckCapacity(ps);for (int i = ps->size; i > pos - 1; i--) ps->a[i] = ps->a[i - 1];ps->a[pos - 1] = x;ps->size++;
}
// 删除第pos个数据，pos不是下标，表示删除第几个
void SLErase(SL* ps, int pos)
{assert(ps && !SLEmpty(ps) && pos > 0 && pos <= ps->size);for (int i = pos - 1; i < ps->size - 1; i++) ps->a[i] = ps->a[i + 1];ps->size--;
}// 查找数据，返回正常对应位置，不是下标位置, 没找到返回-1
int SLFind(SL* ps, SLDateType val)
{assert(ps);for (int i = 0; i < ps->size; i++)if (ps->a[i] == val) return i + 1;return -1;
}
// 修改数据,修改pos正常对应位置，不是下标
void SLModify(SL* ps, int pos, SLDateType Mval)
{assert(ps && pos > 0 && pos <= ps->size);ps->a[pos - 1] = Mval;
}// 判空
bool SLEmpty(SL* ps)
{assert(ps);return ps->size == 0;
}
// 顺序表数据个数
int SLSize(SL* ps)
{assert(ps);return ps->size;
}// 销毁顺序表
void SLDestroy(SL* ps)
{assert(ps);free(ps->a);ps->capacity = 0;ps->size = 0;
}

test.c

#include "SeqList.h"void test1()
{SL s;SLInit(&s);SLPushBack(&s, 1);SLPrint(&s);SLPushBack(&s, 2);SLPrint(&s);SLPushBack(&s, 3);SLPrint(&s);SLPushBack(&s, 4);SLPrint(&s);SLPushBack(&s, 5);SLPrint(&s);SLPushBack(&s, 6);SLPrint(&s);SLDestroy(&s);
}void test2()
{SL s;SLInit(&s);SLPushFront(&s, 1);SLPrint(&s);SLPushFront(&s, 2);SLPrint(&s);SLPushFront(&s, 3);SLPrint(&s);SLPushFront(&s, 4);SLPrint(&s);SLPushFront(&s, 5);SLPrint(&s);SLPushFront(&s, 6);SLPrint(&s);SLPopFront(&s);SLPrint(&s);SLPopFront(&s);SLPrint(&s);SLPopFront(&s);SLPrint(&s);SLPopFront(&s);SLPrint(&s);SLPopFront(&s);SLPrint(&s);SLPopFront(&s);SLPrint(&s);SLDestroy(&s);
}void test3()
{SL s;SLInit(&s);SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);SLPushBack(&s, 5);SLPrint(&s);SLInsert(&s, 3, 99999);SLPrint(&s);SLErase(&s, 3);SLPrint(&s);SLModify(&s, SLFind(&s, 3), 99999);SLPrint(&s);SLDestroy(&s);
}int main()
{//test1();//test2();test3();return 0;
}

---

写在最后

学到这里，数据结构总算是入门了，当然数据结构后面还有很长的路要走，要继续努力！

感谢阅读本小白的博客，错误的地方请严厉指出噢！