1.线性表的联试存储结构
1.1线性表链式存储结构定义
在解释这个思路之前，我们先来谈另一个话题。前几年，有一本书风靡了全世界，它叫《达·芬奇密码》，成为世界上最畅销的小说之一，书的内容集合了侦探、惊使和阴谋论等多种风格，很好看。这本书和绝大部分负小说一样，都是同一种处理办法。那就是，作者不会让你事先知道整个过程的全部，而是在一步一步地到这某个环节，才根据现场的信息，获得或推断出下一步是什么，也就是说，每一步除了对你侦破的信息进一步确认外（之前信息也不一定都是对的，有时是证明某个信息不正确)，还有就是对下一步如何操作或行动的指引。
不过，这个例子也不完全与线性表相符合，因为案件侦破的线案可能是错综复杂的，有点像我们之后要讲到的树和图的数据结构。今天，我们要讲的是单线索，无分支的情况。即线性表的链式存储结构。
线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意 味着，这些数据元素可以存在内存未被占用的任意位置
(如下图所示)。
以前在顺序结构中，每个数据元素只需要存储数据 元素信息就可以了。现在链式结构中，除了要存储数据 元素信息外，还要存储它的后继元素的存储地址。
因此，为了表示每个数据元素ai与其直接后继数据 元素ai+1(i是下标)之间的逻辑关系，对数据元素ai来说，除了存储 其本身的信息之外，还需存储一个指示其直接后继的信息(即直接后继的存储位置)。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称作指针或链。这两部分信息组成数据元素ai的存储映像，称为结点(Node)。
n个结点(a的存储映像)链结成一个链表，即为线性表(a，ay·，a)的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表。单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在一起。
对于线性表来说，总得有个头有个尾，链表也不例外。我们把链表中第一个结点的存储位置叫做头指针，那么整个链表的存取就必须是从头指针开始进行了。之后的每一个结点，其实就是上一个的后继指针指向的位置。想象一下，最后一个结点，它的指针指向哪里？
最后一个，当然就意味着直接后继不存在了，所以我们规定，线性链表的最后一个结点指针为“空”(通常用NULL或“^”符号表示，如下图所示)。
有时，我们为了更加方便地对链表进行操作，会在单链表的第一个结点前附设一个结点，称为头结点。头结点的数据域可以不存储任何信息，谁叫它是第一个呢，有这个特权。也可以存储如线性表的长度等附加信息，头结点的指针域存储指向第一个结点的指针，如下图所示。
1.2头指针与头结点的异同
头指针与头结点的异同点，如下图所示：
1.3线性表链式存储结构代码描述
若线性表为空，则头结点的指针域为“空”，如下图所示：
这里我们大概用图示表达了内存中单链表的存储状态。看着满图的省略号“…”，就知道是有多么不方便。而我们真正关心的它在内存中的实际位置吗？不是的。这只是它所表示的线性表中的数据元素及数据元素之间色逻辑关系。所以我们改用更方便的存储示意图来表示单链表，如下图所示：
若带有头结点的单链表，则如下图所示：
空链表如下图所示：
单链表中，我们在c语言中可用结构指针来描述：
//线性表的单链表的存储结构： typedef struct Node { ElemType data; struct Node*next; }Node; typedef struct Node*LinkList;//定义linkList
从这个结构定义中，我们也就知道，结点由存放数据元素的数据域和存放后继结点地址的指针域组成。假设p是指向线性表第i个元素的指针，则该结点ai 的数据域我们可以用p->data来表示，p->data的值是一个数据元素，结点ai的指针域可以用p->next来表示，p->next的值是一个指针。p->next指向谁呢？当然是指向第i+1个元素，即指向ai+l的指针。也就是说，如果p->data等于a，那么p>next->data等于ai+1(如下图所示)。
2.单链表的具体实现：
2.1开辟节点
首先创建一个新项目，分为三个模块：SList.c用来实现接口函数；SList.h用来结构体创建与函数声明；test.c则用来进行测试我们的接口函数。
创建节点如下：
2.2遍历链表以及开辟新节点
咱们首先用一个cur来存放头结点的地址；
那后面节点的数据怎么访问呢？咱们可以让cur->next赋给cur;
依次内推；当cur为空时；说明已经访问结束。 最后打印即可。
为方便测试我们可以先写一个交互性的链表测试：
写交互性测试的时候，会涉及到开辟新节点，这里我们可以抽离一个函数来专门进行开辟新节点。
测试结果如下：
3.接口函数的实现（增删查改）
3.1尾插
那么如何实现尾插呢？尾插我们首先得先找到尾。
那么如何找呢？
先看下面这个代码。
如果要是这样找尾的话，就会出现一个问题。我们画图分析一下。
这个代码是不是首先有三个指针变量 plisttailnewnode;
随着代码运行，最后taill的地址为空，假设新节点的地址为0x0012ff00,那节点newnode存放的地址也就是0x0012ff00，最后呢，又把newnode的地址给了taill,看起来没问题，但有没有想过，这三个指针变量出了作用域呢？
出了作用域，这三个指针变量是不是都销毁了，这不仅造成了内存泄漏还没有吧链表链接起来。基于这个问题，我们在回过来思考这个问题，如何找尾？
所以我们的尾用taii找的时候，条件不是null结束，而是存放null前一个的地址。
继续思考一下，我们写完了吗？那如果本身就是个空链表呢？也就是说空链表传过来的时候。第一次尾插怎么插呢？看下面这个代码。
这个代码就会有一个明显的错误，插入不进去。为什么会这样呢？
看phead=newnode这一步，这一步是把0x0012ffcc给了phead,出了作用域，phead,newnode****销毁，那么显然我们的plist的地址并没有发生任何变化，所以插入不进去。
这就是典型的形参与实参之间的区别，形参只是实参的一份临时拷贝。那么怎们样才能改变呢，那就需要传地址了。
经过以上的不断修改，最终尾插的接口函数完整代码如下：
测试结果如下：
总结一下：
3.2头插
有了尾插的思想，头插就简单了。
实质也就是修改plist，所以还是传值还是用二级指针。
完整代码如下：
测试结果如下：
