【初阶数据结构】详解顺序表（下）（顺序表的代码实现）

前言

在详解顺序表（上）中，给大家讲解了数据结构的定义，数据结构就是计算机存储和管理数据的方式。我还讲解了何为线性表，以及顺序表的基础概念。那么本文将具体讲解如何用代码来实现顺序表。不要眨眼哦。

1. 项目文件的配置

在正式写代码之前，如果我们项目之下的子文件能够配置好的话，不仅能让我们的代码看上去更加的美观，而且还能大大提高我们编程的效率。

什么意思呢？且听我慢慢道来。

在我们创建.c源文件和.h头文件时，它们是允许被创建多个的，学过变编译与链接这个知识点的就知道其原理。那我们可以这样想：

我们之前无论是写main函数还是其他的函数都是在一个.c文件中的，那假设如果我们现在要写一个很多代码的项目，那我们是不可能讲这么多的代码都写到一个.c文件中的，因为这毕竟是要给别的程序员看的。那如果我们也为文件建立其功能加以区分，那这样不就达成我们的目的了。

话不多说，我们马上开干。

1.1 顺序表的项目的文件配置(仅供参考)

具体操作如下（以VS为例）：

OK，创建项目工程任务实现了现在我们正式开始编写顺序表的代码！！！

2. 顺序表的代码实现

先直接给出代码，让大家思考为什么要这样写，后面我会全部向大家讲解代码编写时容易踩的坑。

如果时间比较紧张的读者可以直接拷贝去使用。

2.1 SeqList.h：

//SeqList.h里面的内容是顺序结构的定义以及实现顺序表操作各接口的声明
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#define MAX 100
//静态顺序表的声明
//struct SeqList
//{
//	int arr[MAX];//定长的数组
//	int size;//记录当前数组有效的数据个数
//};//动态顺序表的声明（两者之间，推荐使用这个）
typedef int SLDataType;
typedef struct SeqList
{//int* arr; //这里我们存的数据不只是int类型的，因此我们应该这么写SLDataType* arr;int size; //当前的有效数据个数int capacity; //空间大小
}SL;//打印顺序表中的数据
void SLPrint(SL s);//初始化顺序表
void SLInit(SL* ps);//销毁顺序表
void SLDestory(SL* ps);//添加数据到顺序表中
//1.尾插
void SLPushBack(SL* ps, SLDataType x);//2.头插
void SLPushFront(SL* ps, SLDataType x);//删除数据
//1.头删
void SLPopFront(SL* ps);//2.尾删
void SLPopBack(SL* ps);//指定位置之前添加数据
void SLInsert(SL* ps, int pos, SLDataType x);//删除指定位置的数据
void SLErase(SL* ps, int pos);//找出指定数据所处的位置
int SLFind(SL* ps,SLDataType x);

2.2 SeqList.c:

2.2.1 顺序表初始化的代码实现：

void SLInit(SL* ps)
{ps->arr = NULL;ps->size = ps->capacity = 0;
}

2.2.2 顺序表销毁的代码实现：

void SLDestory(SL* ps)
{if (ps->arr){free(ps->arr);ps->arr = NULL;}ps->size = ps->capacity = 0;
}

2.2.3 顺序表尾插数据的代码实现：

void SLCheckCapacity(SL* ps)
{assert(ps);//空间不足时，申请空间if (ps->capacity == ps->size){SL* tmp = NULL;int newscapacity = (ps->capacity) == 0 ? 2 : 2 * (ps->capacity);tmp = realloc(ps->arr, newscapacity * sizeof(SLDataType));if (tmp == NULL){perror("realloc fail");exit(1);}//申请成功ps->arr = tmp;ps->capacity = newscapacity;}
}void SLPushBack(SL* ps, SLDataType x)
{SLCheckCapacity(ps);ps->arr[ps->size++] = x;
}

2.2.4 顺序表头插数据的代码实现：

void SLPushFront(SL* ps, SLDataType x)
{SLCheckCapacity(ps);//这里的函数在尾插代码中有int i = 0;for (i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i-1];}ps->arr[0] = x;ps->size++;
}

2.2.5 顺序表尾删的代码实现：

void SLPopBack(SL* ps)
{assert(ps);assert(ps->arr);ps->size--;
}

2.2.6 顺序表头删的代码实现：

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

2.2.7 顺序表打印的函数代码实现：

void SLPrint(SL s)
{int i = 0;for (i = 0; i < s.size; i++){printf("%d ",s.arr[i]);}printf("\n");
}

2.2.8 顺序表在指定位置之前插入数据的代码实现：

void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);assert(pos >= 0 && ps->size > pos);SLCheckCapacity(ps);if (pos == 0){SLPushFront(ps, x);}else{int i = 0;for (i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;ps->size++;}}

2.2.9 删除顺序表中指定位置的数据的代码实现：

void SLErase(SL* ps, int pos)
{assert(ps);assert(ps->arr);assert(pos >= 0 && ps->size > pos);int i = 0;for (i = pos; i < ps->size-1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}

2.2.10 查找数据在顺序表中的所处的位置代码实现：

int SLFind(SL* ps, SLDataType x)
{assert(ps);int i = 0;for (i = 0; i < ps->size; i++){if (ps->arr[i] == x){return i;}}//未找到return -1;
}

2.3 test.c

这个文件里的内容可按照自己的测试下想法来编写main函数里面的内容，这里我就不过多展示了。

3. 写代码时注意的细节

总结上面代码中比较容易出错的地方：
1.

这里我为什么会用typedef给int起别名？

原因有二：
第一：我们所说的顺序别是能够存储各种数据类型的，不仅仅局限于整型数据，还有可能是字符型数据、浮点型数据甚至是自定义类型。
第二：用typedef所起别名的变量有助于我们后期对代码的维护，只要我们想更改顺序表所存储的数据类型，我们能一步动作就实现一次性的更改。

2. 以这一个函数为例
   

这个函数的形参为什么是就够结构体指针类型的，不能是结构体类型的吗？

答案是不能的。原因如下：
在调用函数时，我们向函数传递参数时，有两种方式：

1. 传值调用：只是将调用函数时给变量的值传递给了形参，而形参是存储在操作系统给的另一片空间中。本质是：形参是实参的一份临时拷贝。
2. 传址调用：会改变调用函数所传递变量的值。其本质就是通过地址找到该变量，从而进行修改。

针对上面的描述，我想你已经知道为什么我这里会选择传址调用了。

这里主要是注意if的条件判断，有些读者可能会这么写:

if(ps->capacity == 0)
{...
}

注意这种写法仅仅只是考虑到了初始化顺序表的情况，但是没有考虑到可用空间与有效数据个数之间的关系。

到这里，顺序表的代码实现就已经全部讲解完毕了。如果觉得本文不错的话，麻烦给偶点个赞吧！！！💖💖💖