打开数据结构大门——实现小小顺序表

前言

• 刚刚认识了一门C语言，现在即将走入一个新的世界——数据结构，这是对之前所学知识的检验也是一种对自我的提升，而恰好顺序表又是数据结构的入门课，今天让咱们一起来认识它吧！
• 通过对顺序表的学习咱们才能慢慢了解啥是数据结构，会对数据结构有一个初步的认识，同时明白它在咱们以后的学习中有多么重要。
• 相信大家对之前的通讯录还有印象吧，总体来说跟通讯录区别不大；也就相当于是对通讯录的一个复习巩固吧。
• 顺序表的实质就是在一个数组上进行增删查改等等一系列操作。

顺序表的概念及分类

将一个线性表存储到计算机中，可以采取很多种不同的方法，其中既简单有自然的方法是顺序存储方法，即把线性表的结点按逻辑顺序依次存放到一组地址连续的粗出单元里，用这种方法存储的线性表简称为顺序表。

搭建项目（Seqlist）

• 实现一个顺序表需要三个文件：包括一个后缀为 .h的文件Seqlist.h来存放项目所需的头文件、结构体声明、宏定义和函数的声明；一个 .c为后缀的文件 Seqlist.c来实现各个函数的接口；一个.c为后缀的文件Test.c来测试各个函数。在 Test.c和 Seqlist.c文件前包含 “Seqlist.h”，就能将这三个文件链接起来。
  

🍎搭建一个顺序表结构&&定义所需头文件&&函数

用C语言，顺序表可定义如下：
上代码：

typedef int SLDataType;
typedef struct SepList
{SLDataType* a;int size;     //有效数据个数int capacity; // 容量
}SL;

#pragma once#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <assert.h>

//初始化
void SLInit(SL* ps1);//检查容量是否超过
void SLCheckCapacity(SL* ps1);//释放空间
void SLDestroy(SL* ps1);//打印
void SLPrint(SL* ps1);//尾插
void SLPushBack(SL* ps1, SLDataType x);
//尾删
void SLPopBack(SL* ps1);
//头插
void SLPushFront(SL* ps1, SLDataType x);
//头插
void SLPopFront(SL* ps1);//任意位置插入
void SLInsert(SL* ps1, int pos, SLDataType x);
//任意位置删除
void SLErase(SL* ps1, int pos);bool SLEmpty(SL* ps1);int SLFind(SL* ps1, SLDataType x);void SLModify(SL* ps1, int pos, SLDataType x);

🍌初始化

• 定义好这些函数之后，就要对顺序表进行初始化了。因为以上只是定义了顺序表中的元素并未进行初始化，咱们的第一步就是要对这些元素进行初始化。
• 初始化的内容就是将开辟的数组置空，给数据个数的值赋为0，给容量的大小也赋值为0。 这里我们还需要注意一下的就是因为我们的函数传参会用到一级指针，所以为了保险起见，我们可以用暴力的方法来检查是否为空指针。还可以给大家一个小建议：凡是遇到指针就要判断是否为空。
• 在初始化之前我们还可以开辟一点点空间，若指针为空我们还可以perror一下，报告文件出错的位置和原因。
  上代码：

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

🍐打印

• 将打印这个函数放在前面是为了让我们实现一个函数就能马上进行打印测试，当项目大时会比较方便。因为这个函数可以让我们直观的看到我们各个函数的实现的结果，并且发现其中的问题。
  上代码：

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

🍉数据个数

• 这个函数的功能很简单就只需要返回数据的个数size就行了。
  上代码：

int SLsize(SL* ps1)
{assert(ps1);return ps1->size;
}

😄检查容量

• 把这个功能单独拿出来能够方便我们去调用，因为在后续会多次用到这个函数。
• 这个函数的作用就是在我们的顺序表插入数据之前，要检验我们当前的容量够不够，若不够，则需要扩容，否则就会非法访问空间的问题，执行程序时终端就会报错。
• 如何判断容量是否已满呢？因为我们前面设置了一个size函数用来统计个数，所以只需要size等于capacity，就能够说明当前容量已经满了，接下来再插入数据就需要扩容了。我们就简单的设置每次扩容增加SLDataType* 4的大小。
• 还需注意：别忘了每次插入数据之前都要进行此操作来检查容量。
  上代码：

void SLCheckCapacity(SL* ps1)
{//如果满了需要增容assert(ps1);if (ps1->size == ps1->capacity){SLDataType* tmp = (SLDataType*)realloc(ps1->a, sizeof(SLDataType) * ps1->capacity * 2);if (tmp == NULL){perror("realloc  fail");return;}ps1->a = tmp;ps1->capacity *= 2;}
}

🎆判空

• 这一步操作算是很简单的一步了，只需要判断通讯录是否为空，若为空，返回真；否则，返回假。
  上代码：

bool SLEmpty(SL* ps1)
{assert(ps1);return ps1->size == 0;
}

🍵在尾部插入数据

• 在尾部插入数据就是在当前开辟空间的末尾依次向后插入数据，竟然是插入数据，那就不能忘了要检查容量，操作也很简单，只需要调用前面我们实现的函数即可。将需要插入的数插入进去，记得size++，就没啦。
  上代码：

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

🍅在尾部删除数据

• 尾部删除其实也会有两种具体情况嘛，首先，如果顺序表中没有数据，还需要删除吗？那不妨直接用（assert）暴力检查，size不能为0或者说size大于0，直接判空。
• 如果有数据呢？那就要进行删除咯。删除其实真的不复杂，只需要将size–即可，也不需要将删除的那个位置的数据初始化为0了，因为我们最后打印的时候并不会打印那个数据。但是咱们也不采取直接释放当前位置空间（free），因为顺序表是基于数组实现的，而数组是一段连续的内存空间。当删除一个元素时，如果直接将该位置的空间释放掉，那么该位置之后的所有元素都需要向前移动一位，这样的操作是非常耗时的，效率很低。
  上代码：

void SLPopBack(SL* ps1)
{assert(ps1->size > 0);ps1->size--;
}

🍋在头部插入数据

• 其实咱们可以顺着尾插的思路想象一下，头插应该要比尾插复杂吧。因为咱们始终要知道顺序表是基于数组实现的，而数组又是一段连续的空间，所以头插需要将插入元素外的所有元素都向后移动一位，从而腾出空间给新元素。
• 咱们再仔细想想，要是顺序表中的元素的量很大时，头插的效率岂不是会变得非常低，这也是顺序表最大的缺点。
• 在移动数据的时候是从最后一个元素开始移动，直到移动完第一个数据为止，然后再将元素插入即可，当然也别忘了size++。
  上代码：

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

🍍在头部删除数据

• 和尾删一样，首先要判断是否为空，用assert暴力检查一下。
• 其实头部的删除并没有像头部插入那样麻烦，只要是删除就不会太麻烦，试想一下是拥有容易还是失去容易呢？那当然是失去显得格外容易。
• 让每个元素向前移动，覆盖前一个，只要size还大于1，就继续，当然不敢忘了将size–。
  上代码：

void SLPopFront(SL* ps1)
{assert(ps1);int start = 1;while (start < ps1->size){ps1->a[start - 1] = ps1->a[start];start++;}ps1->size--;
}

🍊在任意位置插入数据

• 老规矩首先暴力检查容量。
• 与头部插入的思路基本一样，但是这里会多一个数据，用来识别插入的位置，当然这里的数字是代表数组的下标，并不是代表的数据的实际位置。其他的逻辑操作就和头部插入一样啦。当然这里也别忘了要size++。
  上代码：

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

🍑将任意位置的数据删除

• 还是老规矩，是删除就要用assert来一顿暴力检查。
• 删除数据，就是将pos位置后面的数据依次向前移动，直到pos位置的数据被覆盖。
• 最后也别忘了size–。
  上代码：

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

🍓查找数据

• 查找数据的本质就是将整个数据表遍历一遍，如果找到了就返回下标；没有找到就返回-1。

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

🥒修改数据

• 修改数据首先要找到数据的位置，将你想修改的位置输入，若传入的pos不正确直接用assert暴力检查，若正确，再输入修改后的新数据，然后在pos-1位置修改就行。

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

🥕顺序表的销毁

• 销毁其实听起来有点像删除，其实这里也需要用assert暴力检查下，若顺序表本身为空就不需要销毁。
• 如果顺序表不为空，则需要依次销毁顺序表中存储的所有元素。但这里的销毁就比较粗暴了，直接将size大小给为0，再将容量大小给为0，将数组的空间释放掉，然后再置空。

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

完整代码

Seqlist.h

// 防止Seqlist.h被重复包含
#pragma once// 以下是所需头文件：
// 输入和输出所需头文件
#include <stdio.h>
// realloc，free所需头文件
#include <stdbool.h>
// 判空所需头文件
#include <stdlib.h>
// 断言所需头文件
#include <assert.h>// 顺序表的数据类型
typedef int SLDataType;//顺序表的结构体
typedef struct SepList
{SLDataType* a;// a 是指向一个在堆上的空间int size;     //有效数据个数int capacity; // 容量
}SL;//初始化
void SLInit(SL* ps1);//打印
void SLPrint(SL* ps1);//数据个数
int SLSize(SL* ps1);//检查容量是否超过
void SLCheckCapacity(SL* ps1);//判空
bool SLEmpty(SL* ps1);//尾插
void SLPushBack(SL* ps1, SLDataType x);//尾删
void SLPopBack(SL* ps1);//头插
void SLPushFront(SL* ps1, SLDataType x);//头删
void SLPopFront(SL* ps1);//任意位置插入
void SLInsert(SL* ps1, int pos, SLDataType x);//任意位置删除
void SLErase(SL* ps1, int pos);//查找数据，返回对应位置
int SLFind(SL* ps1, SLDataType x);//修改数据
void SLModify(SL* ps1, int pos, SLDataType x);//销毁顺序表
void SLDestroy(SL* ps1);

Seqlist.c

#include "SeqList.h"//顺序表初始化
void SLInit(SL* ps1)
{assert(ps1);ps1->a = (SLDataType*)malloc(sizeof(SLDataType) * 4);if (ps1->a == NULL){perror("malloc fail");return;}ps1->size = 0;ps1->capacity = 4;
}//打印
void SLPrint(SL* ps1)
{assert(ps1);for (int i = 0; i < ps1->size; i++){printf("%d ", ps1->a[i]);}printf("\n");
}//数据个数
int SLSize(SL*ps1)
{assert(ps1);return ps1->size;
}//检查容量
void SLCheckCapacity(SL* ps1)
{//如果满了需要增容assert(ps1);if (ps1->size == ps1->capacity){SLDataType* tmp = (SLDataType*)realloc(ps1->a, sizeof(SLDataType) * ps1->capacity * 2);if (tmp == NULL){perror("realloc  fail");return;}ps1->a = tmp;ps1->capacity *= 2;}
}//判空
bool SLEmpty(SL* ps1)
{assert(ps1);return ps1->size == 0;
}//尾部插入
void SLPushBack(SL* ps1,SLDataType x)
{assert(ps1);SLCheckCapacity(ps1);ps1->a[ps1->size++] = x;
}//尾部删除
void SLPopBack(SL* ps1)
{assert(ps1->size > 0);ps1->size--;
}//头部插入
void SLPushFront(SL* ps1, SLDataType x)
{assert(ps1);SLCheckCapacity(ps1);for (int i = ps1->size; i > 0; i--){ps1->a[i] = ps1->a[i - 1];}ps1->a[0] = x;ps1->size++;
}//头部删除
void SLPopFront(SL* ps1)
{assert(ps1);int start = 1;while (start < ps1->size){ps1->a[start - 1] = ps1->a[start];start++;}ps1->size--;
}//任意位置插入数据
void SLInsert(SL* ps1, int pos, SLDataType x)
{assert(0 <= pos && pos <= ps1->size);SLCheckCapacity(ps1);int end = ps1->size - 1;while (end >= pos){ps1->a[end + 1] = ps1->a[end];--end;}ps1->a[pos] = x;ps1->size++;
}//任意位置删除数据
void SLErase(SL* ps1, int pos)
{assert(0 <= pos && pos < ps1->size);assert(!SLEmpty(ps1));int start = pos + 1;while (start < ps1->size){ps1->a[start - 1] = ps1->a[start];++start;}ps1->size--;
}//查找数据
int SLFind(SL* ps1, SLDataType x)
{assert(ps1);for (int i = 0; i < ps1->size; i++){if (ps1->a[i] == x){return i;}}return -1;
}//修改数据
void SLModify(SL* ps1, int pos, SLDataType x)
{assert(ps1);assert(0 <= pos && pos < ps1->size);ps1->a[pos] = x;
}//销毁顺序表
void SLDestroy(SL* ps1)
{assert(ps1);free(ps1->a);ps1->a = NULL;ps1->size = 0;ps1->capacity = 0;
}

Test.c

#include "SeqList.h"void TestSeqList1()
{SL s;SLInit(&s);SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);SLPushBack(&s, 5);SLPushBack(&s, 6);SLPrint(&s);printf("\n");SLPopBack(&s);SLPrint(&s);SLPopBack(&s);SLPrint(&s);SLPopBack(&s);SLPrint(&s);SLPopBack(&s);SLPrint(&s);SLPopBack(&s);SLPrint(&s);SLPopBack(&s);SLPrint(&s);SLDestroy(&s);
}void TestSeqList2()
{SL s;SLInit(&s);SLPushFront(&s, 1);SLPushFront(&s, 2);SLPushFront(&s, 3);SLPushFront(&s, 4);SLPushFront(&s, 5);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 TestSeqList3()
{SL s;SLInit(&s);SLInsert(&s, 0, 1);SLPrint(&s);SLInsert(&s, 1, 11);SLPrint(&s);SLInsert(&s, 1, 111);SLPrint(&s);SLInsert(&s, 1, 1111);SLPrint(&s);SLInsert(&s, 1, 11111);SLPrint(&s);SLErase(&s, s.size - 1);SLPrint(&s);SLErase(&s, s.size - 1);SLPrint(&s);SLErase(&s, s.size - 1);SLPrint(&s);SLErase(&s, s.size - 1);SLPrint(&s);SLErase(&s, s.size - 1);SLPrint(&s);SLDestroy(&s);
}void TestSeqList4()
{SL s;SLInit(&s);SLPushBack(&s, 1);SLPushBack(&s, 2);SLPushBack(&s, 3);SLPushBack(&s, 4);SLPushBack(&s, 5);SLPushBack(&s, 6);SLPrint(&s);SLModify(&s, SLFind(&s, 1), 999);SLPrint(&s);SLModify(&s, SLFind(&s, 6), 999);SLPrint(&s);SLDestroy(&s);
}int main()
{TestSeqList1();TestSeqList2();TestSeqList3();TestSeqList4();return 0;
}

写在最后

在学习的过程中，我也了解到了顺序表的一些特点和优缺点。学到这里也初步见识了数据结构的样子，同时，我也深深感受到了学习的乐趣。长长的路我们慢慢的走，还需更加努力！

感谢各位来阅读本小白的博客，其中有错误的地方请大家明确指出喔，我会一直汲取，慢慢改正的！