紫薇星上的数据结构（2）紫薇星上的数据结构

这部分主要整理一下线性表的知识点，线性表分为顺序表和链表，同时会有一些代码来实现概念。

2.1线性表抽象数据结构线性表的定义
零个或多个数据元素的有限序列就可以说是线性表，比如学生名单，十二生肖等都是符合线性表定义的。
线性表的特点
线性表是一个序列，整个表中的数据元素之间是有序的；数据元素之间是一对一的关系；具有有限性，线性表的数据元素个数是有限的；零个数据元素的有限序列又被称为空表。
线性表常见的操作：创建和初始化；查找；插入；删除；清空。简单来说就是：增、删、改、查。
接下来我们整理一下线性表的定义：

ADT 线性表(SequenceList) Data 1、线性表的数据元素是一个集合{a_1，a_2，a_3，...，a_n} 数据元素的类型DataType(int，double，或自定义) 2、除了第一个元素a_1之外，每个元素有且只有一个直接的前驱元素。 3、除了最后一个元素a_n之外，每个元素有且只有一个直接的后继元素。 4、每个数据元素之间的关系是一对一的关系。 Operation InitList(*List)初始化线性表：创建一个新的线性表List InsertElement(*List, index, elem)在线性表List的index下标处插入元素elem DeleteElement(*List, index, *elem)删除线性表List的index下标处的元素，并返回删除元素指针*elem GetLength(*List)返回线性表List的长度 IsEmpty(*List)检查是否为空线性表 ClearList(*List)清楚线性表 GetElement(*List, index, elem)返回线性表List的index下标处元素elem endADT

这就是线性表的基本定义方式了。
2.2顺序表顺序存储结构的线性表，就是顺序表。线性表的顺序存储结构示意图如下：

文章图片

线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。看起来是不是有点像数组？没错，这其实是顺序表的底层原理。当然刚才我们展示了线性表的定义，真正使用程序来实现的时候我们选择C语言来实现。

// 1、我们首先要定义线性表中的最大存储空间 #define MAX_SIZE 255// 2、线性表中需要有同一类型的元素集合 typedef int ElemType; // 这个地方使用ElemType来代替 int，只是代替名称，实质还是 int typedef struct{ //这个地方使用ElementType来定义这个struct，这是我们自己定义的类型 int id; //每个元素可能都有id char *name; //每个元素可能都有名字 }ElementType; //我们可以在这里存储任何的类型，可以是游戏中的某一个角色，也可能是某个账户的信息// 3、定义顺序表结构 typedef struct{ ElementType datas[MAX_SIZE]; //这里表示定义一个ElementType的数组datas，长度为MAX_SIZE int length; //这个length表示保存当前线性表的长度 };

上面这段代码描述了线性表的顺序存储结构需要的三个属性：

储存空间的起始位置：数组datas的存储位置；
线性表的最大存储容量：MAX_SIZE;
线性表的当前长度：length。

地址计算方法

文章图片

第 1 个元素的内存地址 = 数组的内存地址 + 第一个元素的下标 0；
第 2 个元素的内存地址 = 数组的内存地址 + 第一个元素的下标 1；
第 i 个元素的内存地址 = 数组的内存地址 + 第一个元素的下标 ( i - 1 )；
第( i + 1 )个元素的内存地址 = 数组的内存地址 + 第一个元素的下标 i ；
第 n 个元素的内存地址 = 数组的内存地址 + 第一个元素的下标 ( n - 1 )；
在上面的代码中，datas为存储位置，那么访问第一个数组元素的时候就要用 *(datas + 0); 访问第二个数组元素的时候就要用 *(datas + 1)；访问第 n 个数组元素的时候就要用 *(datas +n - 1)。
后面我们还会经常用到两个单词：position、index，position代表的是位置，从 1 开始；index代表的是下标，从 0 开始。
2.3顺序表的算法插入算法
首先我们打开编辑器，新建一个项目，然后我们建一个头文件：DataElement.h，这个头文件是用来定义数据元素和数据类型的。创建完成之后界面应该是这样的：

文章图片

然后我们就可以在DataElements里面定义数据元素了：

#ifndef DATAELEMENT_H_INCLUDED #define DATAELEMENT_H_INCLUDED #define MAX_SIZE 255 //1、定义数据元素 //typedef int ElementType; typedef struct{ int id; char *name; }ElementType; #endif // DATAELEMENT_H_INCLUDED

可以使用我们刚才讲的两种定义，上面代码使用的是第二种。现在我们来定义顺序表：

//2、定义顺序表结构 typedef struct{ ElementType datas[MAX_SIZE]; int length; }SeqList;

这样子顺序表就定义完毕了：

#ifndef DATAELEMENT_H_INCLUDED #define DATAELEMENT_H_INCLUDED #define MAX_SIZE 255 //1、定义数据元素 typedef int ElementType; typedef struct{ int id; char *name; }ElementType; //2、定义顺序表结构 typedef struct{ ElementType datas[MAX_SIZE]; int length; }SeqList; #endif // DATAELEMENT_H_INCLUDED

现在我们来写顺序表的操作，首先还是新建一个头文件SequenceList.h，然后就可以在里面添加操作了，也就是我们上面的Operation：

#ifndef SEQUENCELIST_H_INCLUDED #define SEQUENCELIST_H_INCLUDED#include #include #include "DataElement.h"//初始化顺序表，三个参数分别表示：要初始化的顺序表；要初始化添加的元素内容数组；初始化时添加的元素个数。 void InitList(SeqList *seqList, ElementType *elemArray, int length); //向顺序表中插入元素，三个参数分别表示：要插入的顺序表；插入元素处的下标；要插入的元素。 void InsertElement(SeqList *seqList, int index, ElementType *element); //方便起见，还要打印顺序表中内容 void PrintList(SeqList *seqList); #endif // SEQUENCELIST_H_INCLUDED

然后我们为了实现插入的操作，还要再新建一个.c文件:SequenceList.c，这个文件用来实现刚才所写的插入操作：

#include "SequenceList.h"//初始化顺序表，三个参数分别表示：要初始化的顺序表；要初始化添加的元素内容数组；初始化时添加的元素个数。 void InitList(SeqList *seqList, ElementType *elemArray, int length){}//向顺序表中插入元素，三个参数分别表示：要插入的顺序表；插入元素处的下标；要插入的元素。 void InsertElement(SeqList *seqList, int index, ElementType *element){}//方便起见，还要打印顺序表中内容 void PrintList(SeqList *seqList){}

现在我们来思考之前说的如何插入，将元素X插入到顺序表（a_1，a_2，a_3，...，a_n）中下标为 i 的位置，那么就会发生以下操作：

下标为 i 的数据以及 i 以后的数据全部向后移动一位（如果 i 是最后一位那就不需要移动）
将下标 i 的位置放入数据元素X，i + 1 的位置放入元素 ai+1，以此类推直到 i = n 的时候位置上为 an。

这里要注意：

插入元素后顺序表长度为n+1。
插入元素后，最后一个元素的下标为 n。
C语言数组实现时，顺序表长度不能超过它的最大长度。

我们在方法中写好插入操作：

//向顺序表中插入元素，三个参数分别表示：要插入的顺序表；插入元素处的下标；要插入的元素。 void InsertElement(SeqList *seqList, int index, ElementType element){ //1、验证插入元素后元素空间是否超过最大长度MAX_SIZE if(seqList->length + 1 >= MAX_SIZE){ printf("数组已满，插入失败！\n"); return; } //2、验证index的值是否合法，应该是0-MAX_SIZE之间 if(index < 0 || index > MAX_SIZE - 1){ printf("只允许在下标范围内插入元素！【0，%d】", MAX_SIZE - 1); return; } //3、插入的index必须小于length if(index > seqList->length){ printf("插入的下标超过了数组最大长度，插入失败！"); return; } //4、从第length - 1 个下标元素开始，到index，前面的元素赋值给后面的元素 //在C89标准中不允许在for中直接定义变量 //C99之后就允许了 for(int i = seqList->length - 1; i >= index; i--){ seqList->datas[i + 1] = seqList->datas[i]; } //5、将插入的元素赋值给下标为index的元素 seqList->datas[index] = element; //6、顺序表总长度+1，这是非常容易漏掉的地方！ seqList->length++; }

现在我们要开始写初始化操作，写好初始化操作之后就可以插入了：

//初始化顺序表，三个参数分别表示：要初始化的顺序表；要初始化添加的元素内容数组；初始化时添加的元素个数。 void InitList(SeqList *seqList, ElementType *elemArray, int length){ if(length > MAX_SIZE){ printf("超出了数组最大容量，初始化失败！"); return; } seqList->length = 0; for(int i = 0; i < length; i++){ //每次循环都在下标为i的位置插入一个元素 InsertElement(seqList, i, elemArray[i]); } }

然后我们写一下打印操作来验证是否成功：

//方便起见，还要打印顺序表中内容 void PrintList(SeqList *seqList){ for(int i = 0; i < seqList->length; i++){ printf("%d\t%s\n",seqList->datas[i].id, seqList->datas[i].name); } }

之后就可以进行实现了，现在我们回到main.c：

#include #include #include "DataElement.h"ElementType dataArray[] = { {1, "钢铁侠"}, {2, "美国队长"}, {3, "紫薇一号"}, {4, "紫薇二号"}, {5, "紫薇三号"} }; void TestSequenceList(); int main(){ //printf("Hello world!\n"); TestSequenceList(); return 0; }void TestSequenceList(){ SeqList seqList; InitList(&seqList, dataArray, sizeof(dataArray) / sizeof(dataArray[0])); PrintList(&seqList); }

建立一个数组和一个方法，数组用来保存数据，方法用来实现操作，写好之后编译通过，运行结果如下：

1钢铁侠 2美国队长 3紫薇一号 4紫薇二号 5紫薇三号Process returned 0 (0x0)execution time : 0.043 s Press any key to continue.

这就是顺序表的插入算法。
删除算法
与插入操作相同，首先要在SeqyenceList.h头文件中添加删除操作：

//删除顺序表中指定下标的元素，参数分别表示：要删除的顺序表；要删除元素的下标。 ElementType *DeleteElement(SeqList *seqList, int index);

这个时候我们就要分析如何删除，将元素X在顺序表（a_1，a_2，a_3，...，a_n）中下标为 i 的位置删除，那么就会发生以下操作：

下标为 i 以后的数据全部向前移动一位（如果 i 是最后一位那就不需要移动）
将顺序表长度减一，i的位置放入元素 ai+1，以此类推直到 i = n - 1 的时候位置上为 an。

这里要注意：

插入元素后顺序表长度为n。
删除元素后，最后一个元素将被直接删除。
被删除的元素要先找到保存以便返回。
C语言数组实现时，顺序表长度不能超过它的最大长度。

所以我们还应该在SeqyenceList.h头文件中添加查找操作：

ElementType *GetElement(SeqList *seqList, int index);

然后来到SeqyenceList.c文件中，添加查找操作：

ElementType *GetElement(SeqList *seqList, int index){ if(index < 0 || index > MAX_SIZE){ //同样的先进行判断 printf("下标越界，查找失败！"); return NULL; } ElementType *element; //要查找的元素 element = &seqList->datas[index]; }

我们将查找到的元素放在element中，然后来写删除操作：

//删除顺序表中指定下标的元素，参数分别表示：要删除的顺序表；要删除元素的下标。 ElementType *DeleteElement(SeqList *seqList, int index){ if(index < 0 || index > MAX_SIZE){ //同样的先进行判断 printf("下标越界，删除失败！"); return NULL; } //1、找到要删除的元素，保存起来以便返回.（保存的是已删除元素的副本） ElementType *deleteElement = (ElementType*)malloc(sizeof(ElementType)); //要删除的元素 //这里应该单独定义并调用查找函数，返回要删除元素的指针 *deleteElement = *GetElement(seqList, index); //2、从指定位置删除，后面一个元素赋值给前面的一个元素 for(int i = index; i < seqList->length - 1; i++){ seqList->datas[i] = seqList->datas[i + 1]; } //3、顺序表长度-1 seqList->length --; return deleteElement; //建议使用完毕后进行ree，否则会造成内存泄漏。 }

这时我们将要查找到的元素分配空间，备份为要删除的元素，然后使用for循环删除，但其实并没有真正删除，只是将要删除的元素从顺序表中拿出来了，备份在deleteElement中，但由于使用了新的内存空间来储存，所以操作完成后可以free来释放内存。现在我们来看一下实际效果怎么样：

void TestSequenceList(){ SeqList seqList; ElementType *deleteElement; InitList(&seqList, dataArray, sizeof(dataArray) / sizeof(dataArray[0])); printf("初始化后：\n"); PrintList(&seqList); deleteElement = DeleteElement(&seqList, 3); printf("删除后：\n"); PrintList(&seqList); printf("被删除的元素：\n"); printf("%d\t%s\n",deleteElement->id, deleteElement->name); free(deleteElement); //一定要记得释放内存 }

编译通过，运行结果如下：

初始化后： 1钢铁侠 2美国队长 3紫薇一号 4紫薇二号 5紫薇三号删除后： 1钢铁侠 2美国队长 3紫薇一号 5紫薇三号被删除的元素： 4紫薇二号Process returned 0 (0x0)execution time : 0.045 s Press any key to continue.

这里要注意我们删除时传入的是下标，所以传入3实际上是删除了datas[3]也就是4号元素：紫薇二号。
检查长度
同样的，先在SeqyenceList.h头文件中添加操作：