线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储，但是把最后一个数据元素的尾指针指向了首位结点）。
---百度百科

这里对于线性表的概念不多赘述，百度上或是书上都解释的很详细了，我们直接进入主题：使用C语言构造一个完整的线性表。

线性表在内存中有两种储存形式：

• 顺序存储
• 链式存储

所谓顺序存储，就是数据在内存中是连续不断地存储的，中间没有间隔，类似的存储方式我们最熟悉的就是 数组，比如：

int arr[10];

这表示在内存中给一个名叫 arr 的东西分配了 10 个 int 类型大小的空间，它的空间排列是这样的：

具体是怎么找到我们到后面再来讨论，现在来看看顺序存储的线性表是怎么实现的。在此之前有一些必备的知识需要掌握。

基础知识

假如我们现在有 1 2 3 4 5 6 7 8 9 10 这 10个数据需要保存，该怎么办呢？最简单的就是直接用一个数组来保存:

void* malloc (size_t size){

}

• @param size_t size 一个整型数据，表示要分配的字节数
• @return 指向分配成功的空间的首地址，类型为空，分配失败指向空
• 点击查看具体用法

说白了，它的用法就是在括号里面填一个整数表示你要分配多少字节的空间，一般用sizeof() 这样来表示，然后它会返回这块空间的首地址给你，用法挺简单的，但有几点需要注意：

• 返回的地址类型为空，所以需要强制转换类型才能使用
• 分配空间有可能会失败(极小可能)
• 使用这个函数申请的内存是在 "堆" 上面分配出来的，而之前定义数组是在 "栈" 上面分配出来的，那具体 "堆" 是什么 "栈" 是什么不在这过多讨论，只需要知道 "堆"空间比 "栈" 空间大得多，"栈" 很容易被填满造成溢出，而 "堆" 很少会被填满

总的来说，这个函数一般是这样用的：

其中三个 int 必须保持一致，可以同时换为别的数据类型(char double或者是自己定义的数据类型等等)，乘10表示分配10个空间，如果分配失败就打印提示信息并终止程序

因此上述程序可以改为：

加上了输出，如果内存分配失败，直接打印错误信息并终止程序

可以看到输出了10个数据，但是这样怎么解决最开始的问题呢？
其实，通过 malloc() 函数申请的空间是可以扩充的，即可以在原来的基础上继续申请空间，并且原来的数据不会丢失，这要用到另一个函数 realloc()

void* realloc (void* ptr, size_t size){

}

• @param ptr 要修改的空间的首地址
• @param size_t size 一个整数，表示重新分配空间的大小
• @return 指向分配成功的空间的首地址，类型为空，分配失败指向空
• 点击查看具体用法

说白了就是，如果我的内存不够用了，就用这个函数来申请扩充空间，不过也有几点注意事项：

• 返回的地址可能与 ptr 的地址一样，也可能不同
• 尽量用一个临时变量来保存返回的地址，因为申请有可能失败

所以这个函数一般的用法是这样的：

同样，对应的三个int得要相同，乘20表示重新分配20个大小的空间，同时arr中的数据迁移到新空间

这样我们就可以修改程序了：

顺序表

首先来讨论一下顺序表的结构：

• 一个结构体怎样才能保存一个完整的顺序表呢？
  由于我们构造的顺序表在内存中的结构就跟数组差不太多，因此可以考虑用类似的方法保存一个顺序表，也就是说，我们在结构体中需要保存表的首地址，可以通过它来找到整张表
• 怎么通过首地址就可以操作整张表呢？
  因为这个表中数据的所有地址都是连在一起的，因此可以像访问数组一样访问表中的元素，但是，访问数组是需要一个下标来指明访问哪一个地址的，当访问表时怎样才能知道此时是不是已经访问完了整张表呢，因此还需要一个尾地址，当访问的地址跟尾地址相同时我们就知道这个元素是整张表中的最后一个元素，不要再往后访问了。实际上我们只需要元素的个数就行了，通过下标就可以找到尾地址，并不需要真正的尾地址

其实这样就已经差不多定下了顺序表的结构了，但是在实际操作中我们发现，这种结构的表需要不断地扩充内存，因为通过元素个数 n 我可以知道此时顺序表中有多少个元素，但同时，这个 n 也表示这个顺序表只能存这么 n 个数据，你要是再想存更多数据，只能 realloc 更多的内存，并且每一次都要，那么有没有一种结构可以使存数据变得不那么复杂呢？当然是有的，只需要在上述结构的基础上加以改进：

上述结构中 n 既是当前表的元素个数，也是最大容量，我们可以另外规定一个最大容量 MAXSIZE ，只有当 n 等于这个最大容量的时候我们才额外申请空间，同时，我们申请空间每次也可以稍微多申请一点，为下一次输入数据留足空间

• 既然申请空间那么麻烦，那为什么不一开始就申请足够的空间备用呢？反正堆空间那么多？
  关于这一点，首先一开始并不知道会有多少数据，因此申请的空间要么就会造成浪费，要么就不够了，就算堆空间很大，但是也没必要随意浪费，毕竟它的空间不是无限的，因此一开始选择一块合适的空间，然后在需要的时候申请空间并留有一点冗余，这样既不会浪费空间，也不会频繁的申请空间。

因此，我们可以得到顺序表的结构如下：

经过上述的分析，这个结构体还是比较好理解的，下面对不是很熟悉结构体的读者解释一下。结构体，就是自定义类型，定义完成之后其实就跟 int，char等基本类型差不太多了，这个结构体有三个成员：

• int * data 整型指针，保存着顺序表的首地址，其实把它定义为整型只是因为上面的需求是整型数据，用通用的 ElemType 会更具有普遍型，具体之后再考虑
• int sqSize 整型数字，保存着当前顺序表的元素个数
• int sqMaxSize 整型数字，保存着顺序表的最大容量

typedef ，给一个数据类型起别名，比如你可以 typedef int size_t; 这样就表示给 int 起了一个别名叫做 size_t，此时你要定义一个整型变量可以写 size_t a; 这样跟直接 int a; 的作用是一样的。上面就是给我们自己定义的数据类型起了两个别名，分别是 sqList 和 LPsqList，此时这两个名字的作用跟 size_t 差不多，都是可以用来直接定义变量，比如 sqList a; 表示定义了 a 这个变量，它是 sqList 类型的，它包含了三个成员 data，sqSize，sqMaxSize，可以使用 " . "操作符来引用这三个结构体成员。当然，仔细看两个别名会发现一个有指针符号一个没有，其实这两个别名能定义的数据类型有一点点区别，sqList ，没有指针符号，类似于 int，定义完之后可以用 " . "来引用结构体成员，LPsqList，有指针符号，类似于 int*，用它来定义的变量是指针类型的，定义完之后可以用 " -> "来引用结构体成员

注意，这里的"有指针符号"表示的是指针符号已经写入到 LPsqList 中了，意思就是你用 LPsqList 定义的变量其实已经是一个指向结构体的指针了，如果再加一个指针符号就是双重指针了
这样定义出来的两个别名，其实有这么一个关系： sqList *a 和 LPsqList a 中两个 a 是一摸一样的，都是指向结构体的指针变量
另外，LP 开头的一般都是指针

了解了 typedef 之后可以把上面的结构改的更加普遍一点了：

这样虽然实质上还是 int * data，但假如你要保存的数据变成了 A B C D 这样的字符，那我们修改程序的时候只需要把 typedef int ElemType 改成 typedef char ElemType就可以直接用了。

到此，顺序表的结构已经推出来了。

接下来，我们开始建表的过程。

初始化顺序表

要在一个表里存数据，那当然是首先得要有这个表，这个从无到有的过程就是初始化顺序表的过程，在这里专门写一个函数来初始化。

因为是初始化一个表，显然这个函数没有参数，初始化过后，表中应该是空的，没有数据(因为根本没数据输入)，也就是说初始化的表的 sqSize 这个成员应该是 0，而sqMaxSize 这个成员应该是你一开始自己规定的大小，表示顺序表的容量，函数的返回值呢？显然初始化完之后的空表保存在一个结构体中，因此要把整个结构体返回。

实现如下：

初始化过程就是先定义一个结构体变量 newSqList，为它的成员 data 分配一段空间(这里因为 data 是 ElemType 类型的所以 malloc 那边都写成 ElemType)，分配的大小是 MAXSIZE ，这是在程序开头宏定义的一个值：

将其定义为100，用宏定义也是为了程序的普遍适用性，如果有一个表初始就需要存1000个数据，那可以直接在宏上把他改成更大的数，这样程序可扩展性会很强，分配好空间之后就是判断空间是否分配成功(改成英文是因为中文容易出现乱码......能用英文最好就用英文吧)，这和之前讲的 malloc 一般用法一致，然后就是给顺序表的另外两个成员赋值，显然此时表中没有任何数据，因此成员 sqSize 赋为0，最大容量 sqMaxSize 为 MAXSIZE，这些表的基本属性都定好了之后就可以把带有表属性的结构体返回了。

这样，初始化表的工作就算完成了，我们可以在主函数之创建一个空表了：

当然还可以检查一下表是不是创建成功了：

这里将 list 的两个成员打印出来发现是0和100，并且分配失败时的错误信息没有打印，说明分配成功，跟我们的预期一致，可以基本判断表创建成功。

很多书上写的时侯会用 status 作为函数的返回值，表示返回函数的执行状态，并且还有把C++中的"传引用"的思想放在这里，其实这样是不太好的。

• 返回函数的运行状态其实是有些多余的，因为程序执行到了那一步就会返回 OK 的，而如果没有到那一步那就说明是分配空间那一步出问题了，但是要是分配失败了是会打印错误信息的，因此专门把返回值用来干这个实在没什么必要
• 其实学习数据结构本身用什么语言不是很重要(当然了用C或者C++是最好的，因为它们俩容易操作内存)，但是你实际编程，把数据结构实现在代码上的时候就很重要了，你不能用着C的编译器写的是C++的代码，这样不说编译能不能通过，首先你的实现过程就有问题了，这样都不能算实现了，本质写的还是伪代码，就比如这个"传引用"，要是你用C++学习数据结构，那传引用当然没问题，但是你用C语言的话问题可就大了，C语言本身没有传引用这个概念，这样写的话编译肯定是不能过的，因此还是规范一点好，C语言不兼容C++但C++完全兼容C语言，虽然是这样但你也最好不要用着C++写C语言的语法，C++有new为什么要用C语言的malloc?完全没必要的啊，所以在实现代码的过程中，用什么语言实现，就用什么语言的语法和函数，不要串了。

当建好一个空表后，整个表就已经存在了，接下来的操作都是维护这个表，一般有五种操作：增、删、改、排、查
在维护表之前我们先写一个打印表的函数，这是为了让我们的维护变得可视化，比如增加或是修改数据后我可以调用这个函数看看数据是否真的增加或修改了。

首先确定函数的参数以及返回值，显然，函数的作用是打印表的数据，并不用返回什么数据，只需在屏幕打印即可，又由于要打印表的数据，那函数肯定得知道是打印哪个表的数据，因此需要表的属性，即把表的结构体传进去，因此函数定义如下：

把表传进来后就可以输出了，显然用一个for循环就可以了，那么循环的终点，或者说结束标志是什么呢，当然是当打印完表的最后一个数据就退出循环，而表的数据个数保存在sqSize 中，所以可以写出函数如下：

这里要注意的是打印的数据全部放在顺序表 list 的 data 成员里面，打印的时候应该用数组或者是指针表示

当然还可以加一点，如果没有数据就打印提示信息：

直接在主函数调用：

可以看到输出了 "No Data"，说明程序没问题，下面可以开始顺序表的操作了。

" 增 "

顾名思义，就是向表中增加数据，假设我有10个数据，最简单的就是这样：

直接在主函数要求用户输入数据，然后打印，也没啥问题啊，0~9不是都打印出来了吗。但是，我们说这种程序可移植性不高，这里就得提到一个叫封装的概念，其实就是打包，相当于写一个函数吧，只不过这个函数可以适用于大部分程序

封装一个模块，其实就是写函数，不过需要探究这个模块最根本的作用，就以上述为例，要向表中增加10个数据，模块的根本作用应该是向表中添加数据，"10个"只不过是数量而已，可以先不考虑，既然是向表中加数据，那么函数的参数就有两个：表，数据。这是毋庸置疑的，返回值呢，不需要返回什么信息，当然也可以把表返回，不过实在没有必要，因为用指针(或C++引用)完全可以传递了，所以定义函数如下：

这里要好好解释一下为什么传过来的顺序表类型由之前的 "sqList" 改成了带指针的 "LPsqList"，首先要明确一个概念，函数形参和实参，当函数接收到参数后，会在内存中开辟一个和实参一摸一样的空间，里面的数据也完全一样，并且跟原来的数据不关联，即修改新的数据不会改变原来空间内的数据，比如刚刚讲的那个输出函数 "printSqList(sqList list)"。这里的 list 跟主函数中传过来的 list 一摸一样，但是不在同一个内存空间，如果对这个函数中的list进行修改，并不会影响到主函数中的 list ，那为什么在这里用 sqList 类型呢，又没办法改变原来的 list，因为这个函数只需要把表中的数据打印在屏幕上就行了，并不需要修改原来表中的数据，所以可以这样传，但是现在我们要增加数据，显然是需要在原来的表中增加的，所以就用了 LPsqList 这种数据类型(也可以用 sqList *，两个完全一样)，把指向表的指针传过来了，这个函数中的 list 的内容只是原来表的地址(也是新开辟的空间，只不过里面的数据是原来的顺序表的地址)，而有了地址就可以对地址的内容操作了，从而修改原表的数据
还有一个参数就是要增加的数据，这里只是一个数据。

具体增加数据的代码，也就是函数体，其实很简单，就是往表中增加这一个数据

可以看到有好多 "->" 符号，这个就是结构体指针引用成员的符号，如果是结构体的话就用 " . " 符号。这段代码可以这么分析，有数据需要存入顺序表，必须要先找到存放数据的位置，也就是 data[ ] 这个中括号里应该填什么位置，显然它肯定是一个变化的，因为不可能每次存数据都放在同一个地方，那之前的数据都会被覆盖，顺序表的 sqSize 属性显示了当前表中有多少个元素(数据)，也相当于， sqSize 表示的位置永远是最后一个数据的位置 +1，即 sqSize 表示的位置中永远都没有数据，比如表中没有数据，那 sqSize 就是0，而data[ 0 ]就是下一个数据存放的位置，再比如表中有 10个数据，那么 sqSize 就是10，表示data[ 0 ]~data[ 9 ]这10个位置都存了数据，下一个数据就应该存在data[ 10 ]中。也就是说，下一个数据应该存放在data[ sqSize ]中，所以就得到了上图的代码，之后因为表中多了一个元素，所以 sqSize 要加一。

现在 "增加数据" 这个模块的最底层已经封装好了，可以简单测试一下，在主函数中直接调用几次函数

这里调用函数时传的参数并不是 list，而是它的地址(因为这里的 list是 sqList 类型的，而形参是 LPsqList 类型)，对应于写 "insertData()"这个函数的参数，是一个指针(地址)。
可以看到，调用了4次函数，分别把0、1、2、3加进表中并且打印了，说明函数没有问题。

当然我们不可能直接用这个函数增加数据，要对这个函数进行再封装，这个时候就要考虑到之前没有考虑的 "10个" 的问题了，定义函数如下：

在这个函数中，把表、所有的数据以及数据的个数传进来

只需要在这个函数中调用之前那个封装好的函数就可以实现增加多个数据

这里的 list 本身就已经是指针类型的了，所以调用 "insertData" 时不用再取地址

可以在主函数中测试一下：

主函数中的data，即要入表的数据，可以通过任意方式得到，比如可以用scanf从用户端输入保存在数组中，也可以是从别的函数传过来的

这样，代码的可移植性就提高了不少，而且修改起来也很方便，当出现不同的得到数据的方式时，可以写别的函数调用 "insertData" ，毕竟最核心的地方是什么时候都要用到的。
关于上述增加数据的部分，还有一个很大的BUG，就是溢出的问题：如果顺序表满了，该怎么处理？这里用到的其实是之前讲的malloc的知识，malloc申请的内存空间是可以扩展的，因此只要在插入函数中加上判断就可以

realloc函数用法已经在上文基础知识中讲过了，这里不再赘述，新申请的内存大小应该在原来最大容量的基础上加上一些，这里讲的 "一些" 在程序中就是 INTERBVALSIZE，这也是宏定义的一个数据：

将每次间隔设置为适当的值，因此在不同程序中设置的可能不一样，所以用宏定义，加强程序可移植性，操作起来也更方便。别忘了这里改变了顺序表的最大容量，所以应该在最后修改顺序表的属性，把代表最大容量的sqMaxSize改成新的值。

可以在主函数中测试一下：

一开始设置的顺序表最大长度是100，而这里传过去的数据有150个，但经过上述处理之后150个数据也可以正常保存，并且可以看到，此时顺序表的sqMaxSize也已经变成了150

这样，顺序表的 "增" 操作可以说是全部写完了，值得一提的是，这个 "增"，其实是 "向顺序表尾部插入" ，当然，除了尾部可以插入数据，任意位置都可以，但对于一个无序的表来说，一个数据保存在什么位置并不关键，尤其是，对于顺序表来说，插入操作(非尾部)是非常麻烦的，所以一般不会对顺序表进行什么往中间的某个位置插入某某数据的操作。

"删"

对于顺序表的删除操作有好几种：

• 删除整个表
• 摧毁整个表
• 删除表中的某个数据

• 其中最简单的是删除表，其实就是把表变为空表，回到初始化的状态，本质上表的空间还在；
• 而摧毁表是把表的空间释放(对于malloc申请的空间是可以主动释放的，释放了之后就不能再访问了)，摧毁表相当于把整个表结构摧毁；
• 删除数据可以说是这里面最复杂的了，由于顺序表的性质，空间连续排列，因此删除表中某个数据后，这个数据所占据的空间就空着了，但是由于向表中输入数据是从尾部输入，因此这个空间就永远空着了，但是，内存中的空间不可能真正空着，一般在内存中删除一个东西其实都是用新数据覆盖它，所以当我删除掉某个位置的数据后，还应该把这个数据之后的所有数据都往前移动1个单位，这样才能继续保证顺序表具有正常结构，并且能继续维护。在这里我们简化一下对数据的删除，只删除尾部的数据，这样就不需要移动了，如果要删除中间的某些数据，建议不要用顺序表的结构，改用链表会方便很多，这个在后续讲单链表时会着重介绍。
  下面对这几种删除方式逐个介绍：

• 删除表
  删除表其实就是把表中所有数据删除，而刚刚讲过，数据删除一般都是覆盖，因此，删除表只要用新数据覆盖就行了

函数过于简单应该都能看懂，主要是这种删除的思想，将sqSize直接置0，这样的话等下次输入数据时就会从0开始保存，就把原来的数据覆盖了

在主函数中调用一下：

可以看到又输出了 "No Data"，并且sqMaxSize也变回了100

• 第二种是摧毁表，要把表的空间全部释放，在C语言中有一个专门释放malloc申请的空间的函数 "free()"，直接调用即可：

值得注意的是，我们申请的空间是在data中，因此应该把data释放掉，并且释放了之后是不允许在对list这个表进行任何操作的，否则会出现如下情况：

在主函数中我在调用摧毁表这个函数之后，又调用了一个增加数据的函数，在运行之后发现程序崩溃了，这是因为data中已经没有任何空间，而我却依然把数据保存在data中，自然会报错，但这不是编译器给报的错，这个程序在编译过程是没有任何问题的，事实上，在执行到这一条代码之前，整个程序都是正常工作的，因此，这种问题排查起来也是十分的麻烦，很难发现问题所在，所以要时刻注意。

• 最后一个是删除尾部数据，由于不用移动数据，而且有了刚刚删除表的覆盖的思想，这个函数也就非常简单了：

其中n是要覆盖的数据的个数

在主函数中测试：

可以看到一开始表中有20个数据，删除10个之后就变成了10个

值得注意的是，这里还有一个小BUG如下：

一开始输入20个数据，正常输出，然后删除30个数据，超过总数据了，通过打印来看确实没有数据了(空了一行)，但是重新输入20个数据发现出了问题，这个时候其实是内存溢出了(不在可控范围内)，因此需要在删除的函数中加上判断

这样再重新编译就没有问题了

"改"

修改数据，主要是通过索引下标或者索引数据来修改数据，提供索引下标修改过于简单，不多叙述，主要是讲讲通过数据来修改数据(其实也很简单)
函数参数有这么几个，首先是顺序表的地址，肯定得要知道是修改那个表的数据，第二个是要修改的数据，第三个是修改后的数据，函数定义如下：

实现方法也很简单，只需要遍历顺序表，找到这个数据，修改就可以了，注意这里只修改第一个找到的数据，后面如果有相同的不做处理，还有就是如果没有这个数据直接在尾部增加一个，或者是打印提示信息。

这里选择在尾部直接加入，for后面的判断是如果存在原数据，那么循环肯定会提前跳出，i 就会小于顺序表元素个数，没有小于的话就直接调用插入函数把数据插入尾部

主函数中测试一下：

输入0~19一共20个数据，第一次把 "0" 改成 "20"，有这个数据，所以输出的第一个变成了20，第二次把 "0" 改成 "30"，由于第一次已经修改了0，所以表中没有0了，直接在表尾增加了一个数据。
忽略所有主函数中的 system("cls")，这只是一个清屏指令，不影响代码执行

"排"

就是排序，在顺序表这里不做介绍

"查"

查询，在顺序表中找到某个指定数据，跟 "改" 里的差不太多

找到数据就把下标返回(也是返回第一个)，没有找到就打印提示信息并返回-1

测试

输入0~19后在表中找 "0"，可以看到返回了下标0，修改数据之后在找 "0"，打印了提示信息并且没有输出a的值

关于查找其实有更加优秀的算法，但这里主要是讲顺序表而非算法，所以直接就遍历了。
(下方单链表)

顺序表源代码

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
#define INTERVALSIZE 10

typedef int ElemType;   
typedef struct 
{
    ElemType* data;
    int sqSize;
    int sqMaxSize;
}sqList, *LPsqList;

/*
** 创建一个空顺序表
** @return 空表结构
*/
sqList initialSqList()
{
    sqList newSqList;
    newSqList.data = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE);
    if(newSqList.data == NULL)
    {
        printf("Memory allocation failed");
        exit(1);
    }
    newSqList.sqSize = 0;
    newSqList.sqMaxSize = MAXSIZE;
    return newSqList;
}

/*
** 向顺序表尾部插入一个数据
** @param list 顺序表的地址
** @param data 要插入的数据
*/
void insertDataToSqList(LPsqList list, ElemType data)
{
    if(list->sqSize == list->sqMaxSize)
    {
        ElemType* tmp = (ElemType*)realloc(list->data, sizeof(ElemType) * (list->sqMaxSize + INTERVALSIZE));
        if(tmp == NULL)
        {
            printf("Memory allocation failed");
            exit(1);
        }
        list->data = tmp;
        list->sqMaxSize += INTERVALSIZE;
    }
    list->data[list->sqSize] = data;
    ++list->sqSize;
}

/*
** 向顺序表尾部插入多个数据
** @param list 顺序表的地址
** @param data 要插入的所有数据
** @param n 数据的个数
*/
void addDataToSqList(LPsqList list, ElemType* data, int n)
{
    for(int i = 0; i < n; ++i)
    {
        insertDataToSqList(list, data[i]);
    }
}

/*
** 通过数据索引修改顺序表数据(如果有重复，只修改最先输入的一个)
** @param list 顺序表的地址
** @param preData 要修改的数据
** @param lastData 修改后的数据
*/
void changeDataToSqList(LPsqList list, ElemType preData, ElemType lastData)
{
    int i = 0;
    for(i = 0; i < list->sqSize; ++i)
    {
        if(list->data[i] == preData)
        {
            list->data[i] = lastData;
            break;
        }
    }
    if(i == list->sqSize)
    {
        insertDataToSqList(list, lastData);
    }
}

/*
** 在顺序表中查找数据
** @param list 顺序表的地址
** @param data 要查找的数据
** @return 找到了就返回数据下标，没找到返回 -1
*/
int searchDataFromSqList(LPsqList list, ElemType data)
{
    int i = 0, index = 0;
    for(i = 0; i < list->sqSize; ++i)
    {
        if(list->data[i] == data)
        {
            return i;
        }
    } 
    printf("The Data is not in the SqList\n"); 
    return -1;
}

/*
** 删除顺序表尾部数据
** @param list 顺序表的地址
** @param n 删除的个数
*/
void deleteDataFromSqList(LPsqList list, int n)
{
    list->sqSize -= n;
    if(list->sqSize < 0)
    {
        list->sqSize = 0;
    }
}

/*
** 清空表
** @param list 顺序表的地址
*/
void clearSqList(LPsqList list)
{
    list->sqSize = 0;
    list->sqMaxSize = MAXSIZE;
}

/*
** 摧毁表
** @param list 顺序表的地址
*/
void destorySqList(LPsqList list)
{
    free(list->data);
    list->sqMaxSize = 0;
    list->sqSize = 0;
}

/*
** 打印顺序表内的数据
** @param list 顺序表
*/
void printSqList(sqList list)
{
    if(list.sqSize == 0)
    {
        printf("No Data");
    }
    else
    {
        for(int i = 0; i < list.sqSize; ++i)
        {
            printf("%d ", list.data[i]);
        }
    }
}

int main()
{
    system("cls");
    sqList list = initialSqList();
    ElemType data[20];
    for(int i = 0; i < 20; ++i)
    {
        data[i] = i;
    }
    addDataToSqList(&list, data, 20);
    printSqList(list);
    printf("\n");
    int a = searchDataFromSqList(&list, 0);
    if(a != -1)
    {
        printf("%d\n", a);
    }
    changeDataToSqList(&list, 0, 20);
    printSqList(list);
    printf("\n");
    a = searchDataFromSqList(&list, 0);
    if(a != -1)
    {
        printf("%d", a);
    }
    return 0;
}

单链表

单链表元素与元素之间通过地址来保持 "联系" ，我们知道，通过指针可以访问一个地址的数据，而单链表的每个元素都保存了下一个元素的地址，因此它可以像顺序表一样，只需知道一个地址就可以访问之后的所有数据。
单链表单个的元素结构如下：

在结构中，数据不再是指针的形式，而是一个结构保存一个数据，可以看到， next 的类型声明和这个结构体的类型是一样的，这意味着 next 是指向 struct LinkListNode 这种类型的指针，可以把 struct LinkListNode 看成是 int 来理解，那么 next 就是相当于 int *类型的，它就是指向 int 类型的指针，后面的 Node 和 LPNode 跟定义顺序表时定义的一样

单链表的结构如下：

初始化单链表

单链表的个体结构比顺序表简单许多，在这里就不多说了，直接开始建表吧。
在把整个表建立起来之前，首先这个表要存在，这里跟顺序表差不多，是一个从无到空表的过程。在建空表之前还要考虑一个问题，靠什么来 "引导" 这个空表？意思就是，如果我建好了空表，那我用什么表示呢？一般情况下，都用一个 "头结点" (上图中指向a0的那个结点)来引导一个单链表，顾名思义，它是这个链表的 "头"，并且，它的结构跟链表中的其它元素的结构一摸一样，也就是说，其实 "头结点" 本身就是一个链表结点，只是它一般不保存数据或是保存链表的结点数。而为了更好的表示一个单链表，在头结点前还定义了一个指向头结点的指针，称为 "头指针"(上图中的first)， 到这里我们清楚了，建空表其实就是创建一个头指针。(下面的头结点都是不保存任何数据的)
跟顺序表一样，单独用一个函数实现：

在函数中，为头结点申请了一段内存空间，取名为 headNode ，它就是头指针，它指向的头结点的数据域没有给与值，而指针域指向了空，即现在表中没有任何数据。

在实现插入数据操作之前还是先写一个打印链表的函数以供测试。

在这里要好好解释这个函数，因为其它操作链表的函数实现都跟这个函数差不多(主要是指针方面)，因次理解了这个函数就可以很容易的理解下面的函数中的指针操作。
函数的作用是打印链表，所以返回值为空，函数参数是一个 LPNode 类型的，很明显它表示一个链表的头指针，可能会有人问为什么这里的打印函数要传指针，而在上面顺序表中传的却是结构体，其实是因为我们在初始化链表的时候创建的就是一个头指针，因此用指针会方便一些，但在创建顺序表时创建的是结构体，所以直接传结构体。其实这个地方传结构体会更严谨一些，因为这样就可以防止在这个打印函数中修改链表中的数据，不过我愿意这样，所以就这样写了。回到函数，开头定义了一个指针 moveNode ，顾名思义他就是个可移动的指针，因为 headNode 是链表的头，它是不能随便移动的(其实如果这个地方传的是结构体的话，是可以移动的，不会影响到主函数中的头指针，但像我这样传指针的话是不能轻易改变 headNode 的值的)，一开始moveNode指向的是头指针的下一个结点，然后一个判断，如果它是空，就表示 headNode的下一个结点是空，没有数据；否则就开始遍历链表打印数据，这个 while(moveNode) 其实跟 while(moveNode ！= NULL) 是一模一样的，就是 moveNode 不为空就一直循环，而 moveNode = moveNode->next; 这一句表示 moveNode 指向 moveNode 的下一个，也就是 moveNode 往链表的下一个结点移动。

在主函数中调用

"增"

在顺序表中，插入数据这个操作是很麻烦的，所以我们只实现了在尾部插入，因为这样可以不用移动数据，但在单链表中，由于数据之间是通过地址来连接的，即下一个数据是什么完全由当前数据的 next 来决定，这就非常方便插入数据了，因此在单链表在有很多种插入数据的操作：

• 头插法
• 尾插法
• 指定位置插入
• 有序插入

其中前两种表示了插入数据后数据所在的位置，链表头部或尾部，在头部表示头结点指向的结点是新插入的结点，在尾部表示新插入的结点在单链表最后；指定位置插入表示我要在链表的第几个位置把这个结点插入链表；有序插入则表示每次插入数据后整个链表都是有序的。
下面来实现第1和第3种方法，第四种放到排序章节在来实现，而尾插法和头插法实现方法差不多，但效率不高(因为要先找到链表的尾部)。
当然，在插入结点之前，结点必须存在：

创建一个结点，返回值为创建的结点的地址，即指向新结点的指针

• 头插法

由于每次插入结点都是在头部，所以只需要改变头结点的指向

上图描述的是if成立的情况

这个是else的情况(P图半小时。。。)

调用如下：

在主函数中调用三次函数，分别插入1，2，3，但打印却是3，2，1，这正符合头插法的规则，后插入的更靠近头部

当然，在实际操作中不可能这样插入，而是要另外封装一个函数，调用这个插入函数实现插入(跟顺序表插入类似)

在主函数中调用也是没有问题的，这里要注意，由于C语言中没有方法这一概念，因此没有办法在函数中得到数组的长度，所以必须把数组的长度一并传过去，而且只能小于或等于数组真正的长度，绝不能超过。

可以看到，小于数组长度时没问题，而超过之后就是一些随机数了，其实不仅仅是随机数那么简单，很多时候会因为数组越界而访问了不能访问的数据而造成程序崩溃。

• 指定位置插入
  即在规定的任何位置插入一个带数据的结点，函数定义如下：

  
  
  
  

  表示要在第 pos 个位置前插入一个 data，如果pos大于当前结点的总数，就插入到链表末尾

pos小于0的话什么都不做，否则就是正确的位置，通过循环定位到要插入的结点前，再通过判断确定是到达了结点的位置还是pos超过了当前结点数

测试如下：

"删"

删除结点，操作大致分为两步，先把要删除的结点脱离链表，然后再释放空间(这里按照数据匹配的规则删除指定结点)

当找到第一个符合的数据就直接删除此数据所在的结点，在脱离链表时要注意，必须先把要脱离结点之后的链表记录下来，否则会丢失后面的所有数据

在测试中可以看到，先删除了0和19，再删除0时表中已经没有了0，因此打印提示信息并且没有删除数据

写到这里，之后的 "改"、"查" 比 "增" 和 "删" 简单多了，而且代码也想差不了太多，在最后着重讲一下 "以排序方式插入"

"排"

顾名思义，就是给链表排序，但是并不是真正意义上的排序，而是在插入数据的时候排序，跟数组排序中的直接插入排序差不多

主要实现就是这两个函数，看起来跟尾插法的两个函数差不多，实际上确实差不多，只是在插入单个结点时多加了一个循环和判断，循环的目的就是找到这个数据应该存放的位置(跟ByPos有点像)，而这个位置是第一个比当前数据大的结点就是我们要存放的位置，注意，循环中的 && 两个条件的位置是不能交换的，因为对于 && 运算符，编译器会先比较左边，如果左边满足才会比较右边，否则就不比较右边直接退出循环。

测试结果如下：

(完)

单链表源代码

#include <stdio.h>
#include <stdlib.h>

typedef int ElemType;

typedef struct LinkListNode
{
    ElemType data;
    struct LinkListNode* next;
}Node, *LPNode;

/**
 * 初始化单链表
 * @return 链表头指针
 */
LPNode initialLinkList()
{
    LPNode headNode = (LPNode)malloc(sizeof(Node));
    headNode->next = NULL;
    return headNode;
}

/**
 * 创建链表结点
 * @param data 结点中要保存的数据
 * @return 创建成功的结点
 */
LPNode createLinkListNode(ElemType data)
{
    LPNode newNode = (LPNode)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

/**
 * 以头插法方式向单链表插入一个结点
 * @param headNode 要插入的链表头指针
 * @param data 要插入的数据
 */
void insertLinkListNodeByHead(LPNode headNode, ElemType data)
{
    LPNode newNode = createLinkListNode(data);
    LPNode firstNode = headNode->next;
    if(firstNode == NULL)
    {
        headNode->next = newNode;
    }
    else
    {
        headNode->next = newNode;
        newNode->next = firstNode;
    }
}

/**
 * 以头插法方式向单链表插入多个数据
 * @param headNode 要插入的链表头指针
 * @param data 要插入的所有数据
 * @param size 数据的个数
 */
void insertDataToLinkListByHead(LPNode headNode, ElemType* data, int size)
{
    for(int i = 0; i < size; ++i)
    {
        insertLinkListNodeByHead(headNode, data[i]);
    }
}

/**
 * 指定位置插入结点
 * @param headNode 要插入的链表头指针
 * @param data 要插入的数据
 * @param pos 插入的位置
 */
void insertNodeByPos(LPNode headNode, int pos, ElemType data)
{
    LPNode moveNode = headNode;
    LPNode newNode = createLinkListNode(data);
    if(pos <= 0)
    {
        printf("Position Wrong\n");
        return;
    }
    while(moveNode->next!=NULL && --pos)
    {
        moveNode = moveNode->next;
    }
    if(pos == 0)
    {
        newNode->next = moveNode->next;
        moveNode->next = newNode;
    }
    else
    {
        moveNode->next = newNode;
    }
}

/**
 * 以排序方式向单链表插入一个结点
 * @param headNode 要插入的链表头指针
 * @param data 要插入的数据
 */
void insertLinkListNodeBySort(LPNode headNode, ElemType data)
{
    LPNode newNode = createLinkListNode(data);
    LPNode moveNode = headNode;
    while(moveNode->next!=NULL && moveNode->next->data < data)
    {
        moveNode = moveNode->next;
    }
    if(moveNode->next == NULL)
    {
        moveNode->next = newNode;
    }
    else
    {
        newNode->next = moveNode->next;
        moveNode->next = newNode;
    }
}

/**
 * 以排序方式向单链表插入多个数据
 * @param headNode 要插入的链表头指针
 * @param data 要插入的所有数据
 * @param size 数据的个数
 */
void insertDataBySort(LPNode headNode, ElemType* data, int size)
{
    for(int i = 0; i < size; ++i)
    {
        insertLinkListNodeBySort(headNode, data[i]);
    }
}

/**
 * 按数据删除一个结点
 * @param headNode 要删除结点的链表头指针
 * @param deleteData 要删除的数据
 */
void deleteNode(LPNode headNode, ElemType deleteData)
{
    LPNode moveNode = headNode;
    while (moveNode->next != NULL)
    {
        if(moveNode->next->data == deleteData)
        {
            LPNode deleteNode = moveNode->next;
            moveNode->next = moveNode->next->next;
            free(deleteNode);
            printf("Deleted\n");
            return;
        }
        moveNode = moveNode->next;
    }
    printf("The Data is not in\n");    
}

/**
 * 从头开始打印链表数据
 * @param headNode 要打印的链表头指针
 */
void printLinkList(LPNode headNode)
{
    LPNode moveNode = headNode->next;
    if(moveNode == NULL)
    {
        printf("No Data\n");
    }
    else
    {
        while(moveNode)
        {
            printf("%d ", moveNode->data);
            moveNode = moveNode->next;
        }
    }
}

int main()
{
    system("cls");
    LPNode list = initialLinkList();
    // ElemType data[20];
    // for(int i = 0; i < 20; ++i)
    // {
    //     data[i] = i;
    // }
    // insertDataToLinkListByHead(list, data, 20);
    // deleteNode(list, 0);
    // printLinkList(list);
    // printf("\n");
    // deleteNode(list, 19);
    // printLinkList(list);
    // printf("\n");
    // deleteNode(list, 0);
    ElemType data[10] = {1, 3, 9, 0, 2, 5, 8, 7, 6, 4};
    insertDataBySort(list, data, 10);
    printLinkList(list);
    return 0;
}