数据结构 —— 顺序表
本文讨论使用c语言实现数据结构中的顺序表。
什么是顺序表？
我们熟悉的数组就是一种顺序表。顺序表中的逻辑上相邻的元素在物理内存中也是连续存放的。简单说就是元素顺着表一个个地挨着往下放。
顺序表能方便地访问元素
我们知道数组中是有下标的。我们可以利用下标访问数组的任意一个元素，查找很快速。这也就是顺序表的优点。例如，我们可以使用下标访问元素来遍历数组：
#include <stdio.h> void func() { int arr[] = {1,2,3,4,5}; int length = sizeof(arr) / sizeof(arr[0]);//获取数组长度 for(int i=0;i<length;i++) { printf("%d ",arr[i]); } }插入和删除元素很麻烦
顺序表能很方便地访问元素，但是新增和删除一个元素就很麻烦。比如我们要删除或新增一个元素，那么后面的所有元素都要往后移动，并且顺序表的容量是一定的，如果超出了容量还需要扩容。
顺序表的实现
下面我们进行使用c语言实现顺序表。我们先准备一个源文件（test.c）存放main函数：
#include <stdio.h> int main() { return 0; }下面我们准备使用一个头文件和一个源文件进行对顺序表的实现。在实现功能的时候，我们需要提高代码的可维护性和可读性，让“接口与实现分离”。因此我们在操作时需要一个头文件和一个源文件。
我们先来书写头文件搭建好框架。首先，我们需要建立顺序表的元素，使用结构体来存放信息：
（SeqList.h 文件）
#pragma once #define Capacity 100 //容量 typedef int SeqType; typedef struct { SeqType data[Capacity]; int length; }SeqList;这里我们将int类型重命名为SeqType是为了方便对类型做修改。如果后面数据类型不使用int了，只需要将SeqType改为我们所需要的类型即可。
这里我们实现的是静态顺序表，直接创建一个数组来存放，但是容量并不能动态变化。
所以，我们也可以将顺序表进行动态实现，此时就需要malloc来开辟空间。那么，我们就需要如下进行设计：
#pragma once #include <stddef.h> #include <stdlib.h> #include <assert.h> #define CAPACITY 4 typedef int SeqType; typedef struct { SeqType* data;//使用指针来实现动态数组 int length;//数组长度 int capacity;//当前容量 }SeqList;下面我们进行函数接口的实现。一个顺序表需要有初始化与销毁函数，并且能够增删改查元素。那么，就至少会有下面的函数：
void InitList();//初始化 void Destroy();//销毁 void InsertHead();//头插入元素 void InsertBack();//尾插如元素 void DeleteHead();//头删除元素 void DeleteBack();//尾删除元素 void LocateList();//查找元素1、初始化函数InitList
下面我们在 SeqList.c文件中对函数进行具体实现。顺序表的初始化肯定要先传入我们的动态数组,之后为动态数组开辟空间：
#include "SeqList.h" #include <stdlib.h> void InitList(SeqList* s) { //malloc开辟空间 s->data = (SeqType*)malloc(sizeof(SeqType) * CAPACITY); //判断是否开辟成功 if (s->data == NULL) { perror("malloc falied"); return; } s->length = 0; s->capacity = CAPACITY; }2、销毁顺序表DestroyList
有初始化那么对应的也有销毁。销毁时需要释放空间，实现简单，代码如下：
void DestroyList(SeqList* s) { assert(s);//防止为空 free(s->data); s->data = NULL; s->length = s->capacity = 0; }3、插入与删除元素
扩容
不管是什么插入，在插入元素之前都先需要判断容量是否足够，如果不够需要扩大容量。我们先实现扩大容量的函数：
void CapacityIncrease(SeqList* s) { if (s->length == s->capacity)//判断是否需要扩容 { SeqType* tmp = (SeqType*)realloc(s->data, sizeof(SeqType) * s->capacity * 2); if (tmp == NULL) { perror("tmp malloc falied"); return; } s->data = tmp; s->capacity *= 2; } }插入
插入函数需要传入动态数组和元素值两个参数；如果我们想要从中间任意一个位置插入一个元素，我们还需要传入一个参数来确定插入的位置。在插入之后需要将后面的元素全部后移。
void Insert(SeqList* s, SeqType value,int pos) { assert(s); assert(pos >= 0 && pos <= s->length);//pos不能超出容量范围 CapacityIncrease(s);//判断是否需要扩容 int end = s->length - 1;//标记最后一个数组元素 //从最后一个元素向前查找到pos位置，将pos后的元素全部后移 while (end >= pos) { s->data[end + 1] = s->data[end]; end--; } //跳出循环说明找到pos位置。插入元素。 s->data[pos] = value; s->length++; }删除
删除操作原理和插入相同。我们可以直接将pos后位置的元素向前覆盖。
void Delete(SeqList* s, int pos) { assert(s); assert(pos >= 0 && pos < s->length); int end = s->length - 1; while (pos < end) { s->data[pos] = s->data[pos + 1]; pos++; } s->length--; }4、查找元素
通过上面的插入和删除操作，我们想查看对应值的元素也是一样的原理。参数需要传入动态数组和需要查找的值。该功能为查找到对应值的元素并返回下标。
int FindElm(SeqList* s, SeqType x) { assert(s); for (int i = 0; i < s->length; i++) { if (s->data[i] == x) return i; } return 0; }5、打印元素
就是简单地遍历数组后打印元素：
void Print(SeqList* s) { assert(s); for (int i = 0; i < s->length; i++) { printf("第%d个元素值为：%d\n", i, s->data[i]); } }运行
这样我们就实现了顺序表的所有基本功能。下面我们可以在main函数中使用我们的顺序表。
为了方便我们查看扩容，我们为扩容函数填上说明：
void CapacityIncrease(SeqList* s) { if (s->length == s->capacity)//判断是否需要扩容 { SeqType* tmp = (SeqType*)realloc(s->data, sizeof(SeqType) * s->capacity * 2); if (tmp == NULL) { perror("tmp malloc falied"); return; } s->data = tmp; s->capacity *= 2; printf("扩容一次\n"); } }下面我们在main函数中进行调用：
#include "SeqList.h" int main() { SeqList a;//在栈上分配 InitList(&a);//初始化 Insert(&a, 3, 0); Insert(&a, 2, 1); Insert(&a, 1, 2); Print(&a); Insert(&a, 9, 3); Insert(&a, 8, 4); Insert(&a, 7, 5); Insert(&a, 6, 6); Print(&a); DestroyList(&a); return 0; }运行结果如下：
可以发现成功运行。删除与查找功能也同样可以使用。
完整代码：
1、SeqList.h
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> #define CAPACITY 4 typedef int SeqType; typedef struct { SeqType* data;//使用指针来实现动态数组 int length;//标记当前的元素个数 int capacity;//当前容量 }SeqList; void InitList(SeqList* s); void DestroyList(SeqList* s); void CapacityIncrease(SeqList* s); void Insert(SeqList* s,SeqType value,int pos); void Delete(SeqList* s,int pos); int FindElm(SeqList* s, SeqType x); void Print(SeqList* s);2、SeqList.c
#include "SeqList.h" void InitList(SeqList* s) { //malloc开辟空间 s->data = (SeqType*)malloc(sizeof(SeqType) * CAPACITY); //判断是否开辟成功 if (s->data == NULL) { perror("malloc falied"); return; } s->length = 0; s->capacity = CAPACITY; } void DestroyList(SeqList* s) { assert(s);//防止为空 free(s->data); s->data = NULL; s->length = s->capacity = 0; } void CapacityIncrease(SeqList* s) { if (s->length == s->capacity)//判断是否需要扩容 { SeqType* tmp = (SeqType*)realloc(s->data, sizeof(SeqType) * s->capacity * 2); if (tmp == NULL) { perror("tmp malloc falied"); return; } s->data = tmp; s->capacity *= 2; printf("扩容一次\n"); } } void Insert(SeqList* s, SeqType value,int pos) { assert(s); assert(pos >= 0 && pos <= s->length);//pos不能超出容量范围 CapacityIncrease(s);//判断是否需要扩容 int end = s->length - 1;//标记最后一个数组元素 //从最后一个元素向前查找到pos位置，将pos后的元素全部后移 while (end >= pos) { s->data[end + 1] = s->data[end]; end--; } //跳出循环说明找到pos位置。插入元素。 s->data[pos] = value; s->length++; } void Delete(SeqList* s, int pos) { assert(s); assert(pos >= 0 && pos < s->length); int end = s->length - 1; while (pos < end) { s->data[pos] = s->data[pos + 1]; pos++; } s->length--; } int FindElm(SeqList* s, SeqType x) { assert(s); for (int i = 0; i < s->length; i++) { if (s->data[i] == x) return i; } return -1;//表示未找到 } void Print(SeqList* s) { assert(s); for (int i = 0; i < s->length; i++) { printf("第%d个元素值为：%d\n", i+1, s->data[i]); } }3、test.c
#include "SeqList.h" int main() { SeqList a;//在栈上分配 InitList(&a);//初始化 Insert(&a, 3, 0); Insert(&a, 2, 1); Insert(&a, 1, 2); Print(&a); Insert(&a, 9, 3); Insert(&a, 8, 4); Insert(&a, 7, 5); Insert(&a, 6, 6); Print(&a); printf("删除元素\n"); Delete(&a, 4); Delete(&a, 4); int tmp = FindElm(&a, 9); Print(&a); printf("查找值为9的元素下标为：%d\n", tmp); DestroyList(&a); return 0; }