3.8 单链表的整表创建
顺序存储结构的创建，其实就是一个数组的初始化，即声明一个类型和大小的数组并赋值的过程。而单链表和顺序存储结构就不一样，它不像顺序存储结构这么集中，它可以很散，是一种动态结构。对于每个链表来说，它所占用空间的大小和位置是不需要预先分配划定的，可以根据系统的情况和实际的需求即时生成。
所以创建单链表的过程就是一个动态生成链表的过程。即从空表的初始状态起，依次建立各个元素结点，并逐个插入链表
单链表整表创建的算法思路：
1.声明一结点p和计数器变量i；
2.初始化一空链表L
3.让L的头结点的指针指向null，即建立一个带头结点的单链表
4.循环：
生成一新结点赋值给p
随机生成一数字赋值给p的数据域p-》data；
将p插入到头结点与前一新结点之间
随机产生n个元素的值，建立带表头结点的单链线性表L(头插法)
void CreateListHead(LinkList *L,int n){ LinkList p; int i; srand (time(0)) ; /*初始化随机数种子*/ *L = (LinkList) malloc (sizeof (Node)); (*L) -> next = NULL; /*先建立一个带头结点的单链表*/ for(i=0; i<n; i++ ) { P = (LinkList) malloc(sizeof (Node) ); /*生成新结点*/ p->data = rand()%100+1; /*随机生成100以内的数字*/ p->next = (*L)->next; (*L)->next = p; /*插入到表头*/ }}
在算法代码里，最长用的是插队的办法，就是始终让新结点在第一的位置。这种算法简称为头插法
为什么新来的到第一的位置，每次把新结点都插在终端结点的后面，这种算法称之为尾插法
代码如下：
void CreateListTail(LinkList *L,int n){ LinkList p,r; int i; srand(time(0)); *L = (LinkList) malloc (sizeof(Node)); //L为整个线性表 r = *L; //*r 为指向尾部的结点; for (i = 0; i < n; i++) { p = (Node *)malloc(sizeof(Node)); //生成新结点 p->data = rand() % 100 +1; r->next = p; r = p; //将当前结点的新结点定义为终端节点 } r->next = NULL; }
注意L与r的关系，L是指整个单链表，而r是指向尾结点的变量, r会随着循环不断地变化结点，而L则是随着循环增长为一个多结点的链表。
注意啊，r是一个变量！！！
值得注意的是r->next = p；的含义，其实就算将刚才的表尾终端结点r的指针指向新结点p
那么r = p是什么意思？？？
它的意思，就是本来r是在ai-1元素的结点，可现在它已经不是最后的结点了，现在最后的结点是ai，所以应该要让将p结点这个最后的结点赋值给r。此时r又是最终的尾节点了
3.9 单链表的整表删除
当我们不打算使用这个单链表时，我们需要把它销毁，其实也就是在内存中将它释放掉，以便于留出空间给其他程序或软件使用。
单链表整表删除的算法思路如下:
1.声明一结点p和q;
2.将第一个结点赋值给p;
3.循环
将下一结点赋值给q;
释放p;
将q赋值给p。
初始条件:顺序线性表L已存在，操作结果:将L重置为空表
Status ClearList ( LinkList *L){ LinkList p,q; p= (*L)->next; /*p指向第一个结点(将第一个结点赋值给p)*/ while (p) /*没到表尾*/ { q=p->next; //将下一节点赋值给q free(p); //释放p p=q; //将q赋值给p } (*L)->next=NULL; /*头结点指针域为空*/ return OK;}
这个蛮好理解的！
其中q的作用，就是一个记录作用，p被释放了，但是谁得到了记录，以便于等当前结点释放后，把下一节点拿回来补充
3.10 单链表结构与顺序存储结构优缺点
1. 存储分配方式
顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素
2.时间性能
●查找
●顺序存储结构0(1)
●单链表0(n)
●插入和删除
●顺序存储结构需要平均移动表长半的元素，时间为0(n)
●单链表在线出某位置的指针后，插入和删除时间仅为0(1)
3.空间性能
●顺序存储结构需要预分配存储空间，分大了，浪费,分小了易发生上溢
●单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制
**若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。**若需要频繁插入和删除时，宜采用单链表结构。比如说游戏开发中，对于用户注册的个人信息，除了注册时插入数据外，绝大多数情况都是读取，所以应该考虑用顺序存储结构。而游戏中的玩家的武器或者装备列表，随着玩家的游戏过程中，可能会随时增加或删除，此时再用顺序存储就不太合适了，单链表结构就可以大展拳脚。当然，这只是简单的类比，现实中的软件开发，要考虑的问题会复杂得多。
当线性表中的元素个数变化较大或者根本不知道有多大时，最好用单链表结构，这样可以不需要考虑存储空间的大小问题。而如果事先知道线性表的大致长度，比如一年12个月，一周就是星期一至星期日共七天,这种用顺序存储结构效率会高很多。
各有优缺点~
3.11 静态链表
这里不做过多的言语
3.12 循环链表
将单链表中终端结点的指针端由空指针改为指向头结点,就使整个单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表(circular linkedlist)。
循环链表解决了一个很麻烦的问题。如何从当中一个结点出发，访问到链表的全部结点。
为了使空链表与非空链表处理一致，我们通常设-一个头结点，当然，这并不是说，循环链表一定要头结点，这需要注意。
非空的循环链表：
其实循环链表和单链表的主要差异就在于循环的判断条件上，原来是判断p->next是否为空，现在则是p -> next不等于头结点，则循环未结束。
在单链表中，有了头结点时，可以用0(1)的时间访问第一个结点，但对于要访问到最后一个结点，却需要0(n)时间，因为我们需要将单链表全部扫描一遍。有没有可能用0(1)的时间由链表指针访问到最后一个结点呢? 当然可以。不过需要改造一下这个循环链表， 不用头指针，而是用指向终端结点的尾指针来表示循环链表
终端结点用尾指针rear（后）指示，则查找终端结点是o(1)
举个程序的例子，要将两个循环链表合并成一个表时，有了尾指针就非常简单了。比如下面的这两个循环链表，它们的尾指针分别是rearA和rearB
p=rearA->next; 保存A表的头结点，即①
rearA->next=rearB->next->next; 将本是指向B表的第一个结点(不是头结点) 賦值給reaA->next,即②
rearB->next=p; 将原A表的头结点赋值给rearB->next,即③
free § ; 释放p
3.13 双向链表
书中的故事很精彩，有时间一定看一遍
为了克服单向性这一缺点， 老科学家们，设计出了双向链表。双向链表(double linked list) 是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。
typedef struct DulNode{ElemType data;struct DuLNode *prior; /*直接前驱指针*/struct DuLNode *next; /*直接后继指针*/}DulNode, *DuLinkList;
既然单链表也可以有循环链表，那么双向链表当然也可以是循环表。
双向链表的循环带头结点的空链表如下：
非空的循环的带头结点的双向链表
由于这是双向链表，那么对于链表中的某一个结点p，它的后继的前驱是谁?当然还是它自己。它的前驱的后继自然也是它自己，即:
p->next->prior = p = p->prior- >next
**就像人生一样，想享乐就得先努力，欲收获就得付代价。**双向链表既然是比单链表多了如可以反向遍历查找等数据结构，那么也就需要付出一-些小的代价:在插入和删除时，需要更改两个指针变量。
插入操作时，其实并不复杂，不过顺序很重要，千万不能写反了。我们现在假设存储元素e的结点为s，要实现将结点s插入到结点p和p -> next之间需要下面几步、
这里的prior值的是s结点的前指针，next指的是s结点的后指针
s->prior = p; 把p赋值给s的前驱，如图中①
s -> next= P -> next; 把p->next赋值给s的后继，如图中②
P -> next-> prior = s; 把s赋值给p->next的前驱，如图中③
P->next = s; 把s赋值给p的后继，如图中④
上面写的代码一定认真看，很好理解~~~
双向链表的删除就比较好理解了，类似链表的删除
p->prior->next=p->next; 把p->next赋值给p->prior的后继，如图中①
p->next->prior=p->prior; 把p->prior赋值给p->next的前驱，如图中②
上面写的代码一定认真看，很好理解~~~
简单总结一下，双向链表相对于单链表来说，要更复杂- -些，毕竟它多了prior指针，对于插入和删除时，需要格外小心。另外它由于每个结点都需要记录两份指针，所以在空间上是要占用略多-些的。 不过,由于它良好的对称性，使得对某个结点的前后结点的操作，带来了方便，可以有效提高算法的时间性能。说白了，就是用空间来换时间。
3.14 总结回顾
这一章主要是学的线性表
知道了它的定义，线性表是零个或多个具有相同类型的数据元素的有限序列。然后说了抽象数据类型，和一些基本操作
之后说顺序存储结构和链式存储结构，顺序存储指的是用一段地址连续的存储单元依次存储线性表的数据元素，通常用数组来实现这一结构
之后说链式存储，它不受固定的存储空间限制，能快速插入和删除
之后说了单链表，循环链表，双向链表和不使用指针如何处理链表结构的静态链表
以上，基础中的基础。对后面又很重要的作用
