3.7 单链表的读取
在线性表的顺序存储结构中，我们要计算任意一个元素的存储位置是很容易的。但在单链表中，由于第i个元素到底在哪？没办法一开始就知道，必须得从头开始找。
获得链表第i个数据的算法思路：
- 声明一个结点p指向链表第一个结点，初始化j从1开始；
- 当j < i 时,就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1；
- 若到链表末尾p为空，则说明第i个元素不存在；
- 否则查找成功，返回结点p的数据。
说白了，就是从头开始找，直到第i个元素为止，由于这个算法的时间复杂度取决于i的位置，当i=1时，则不需要遍历，第一个就取出数据了，而当i=n时则遍历n-1次才行。因此最坏情况的时间复杂度是O(n)。
由于单链表的结构中没有定义表长，所以不能事先知道要循环多少次，因此也就不方便使用for来控制循环。其主要核心思想就是“工作指针后移”，这其实也是很多算法的常用技术。
3.8 单链表的插入和删除
3.8.1 单链表的插入
s->next = p->next,p->next = s;
解读这两句代码，也就是说让p的后继结点改成s的后继结点，再把结点s变成p的后继结点。
**单链表第i个数据插入结点的算法思路: **
- 声明一结点p指向链表的第一个结点，初始化j从1开始。
- 当j < i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j累加1。
- 若到链表末尾p为空，则说明第i个元素不存在
- 否则查找成功，在系统中生成一个空结点s
- 将数据元素e赋值给s->data
- 单链表的插入标准语句s->next = p->next,p->next = s;
- 返回成功
在这段算法代码中，我们用到了C语言的malloc标准函数，它的作用就是生成一个新的结点，其类型与Node是一样的，其实质就是在内存中找了一小块空地，准备用来存放e数据s结点。
3.8.2 单链表的删除
设存储元素ai的结点为q,要实现将结点q删除单链表的操作，其实就是将它的前继结点的指针绕过，指向它的后继结点即可。
q = p->next; p->next = q->next
单链表第i个数据删除结点的算法思路：
- 声明一结点p指向链表第一个结点，初始化j从1开始
- 当j<1时，就遍历链表，让p的指针向后移动，不断指向下一个结点，j累加1
- 若到链表末尾p为空，则说明第i个元素不存在
- 否则查找成功，将欲删除的节点p->next赋值给q。
- 单链表的标准删除语句p->next = q->next。
- 将q结点中的数据赋值给e,作为返回。
- 释放q结点。
- 返回成功。
这段算法代码里，我们又用到了另一个C语言的标准函数free。它的作用就是让系统回收一个Node结点，释放内存。分析一下刚才我们讲解的单链表插入和删除算法，我们发现他们其实都是由两部分组成：第一部分就是遍历查找第i个元素，第二部分就是插入和删除元素。
从整个算法来说，我们很容易推导出：他们的时间复杂度都是O(n)。如果在我们不知道第i个元素的指针位置，单链表数据结构在插入和删除操作上，与线性表的顺序存储结构是没有太大优势的。但如果，我们希望从第i个位置，插入10个元素对于顺序寻出结构意味着，每一次插入都意味着要移动n-i个元素，每次都是O(n)。而单链表，我们只需要在第一次时，找到第i个位置的指针，此时为O(n),接下来只是简单里通过赋值移动指针而已，时间复杂度都是O(1),显然，对于插入或删除数据越频繁的操作，单链表的效率优势就越是明显。
3.9 单链表的整表创建
回顾一下，顺序存储结构的创建，其实就是一个数组的初始化，即声明一个类型和大小的数组并赋值的过程。而单链表和顺序存储结构不一样，它不像顺序存储结构那么集中，它可以很散，是一种动态结构。对于每个链表来说，它所占用空间的大小和位置是不需要预先分配划定的，可以根据系统的情况和实际的需求即时生成。
单链表整表创建的算法思路：
- 声明一结点p和计数器变量i
- 初始化一空链表L
- 让L的头结点的指针指向NULL,即建立一个带头结点的单链表
- 循环
* 生成一新结点赋值给p
* 随机生成一数字赋值给p的数据域p->data
* 将p插入到头结点与前一新结点之间。
这段算法代码里，我们其实用的是插队的办法，就是始终让新结点在第一的位置。这种算法简称为头插法。
我们把每次新结点都插在终端结点的后面，这种算法称为尾插法。
注意L与r的关系，L是指整个单链表，而r是指向尾结点的变量，r会随着循环不断地变化结点，而L则是随着循环增长为一个多结点的链表。
对于r->next = p的理解
它的意思，就是本来r是在ai-1元素的结点，可现在它已经不是最后的节点了，现在最后的节点是ai,所以应该要让p结点这个最后的结点赋值给r。此时r又是最终的尾结点了。
循环结束后，那么应该让这个链表的指针域置空，因此有了“r->next = NULL”,以便以后遍历时可以确定其是尾部。
3.10 单链表的整表删除
也就是在内存中将它释放掉。
单链表整表删除的算法思路：
- 声明一结点p和q
- 将第一个结点赋值给p
- 循环
* 将下一节点赋值给q
* 释放p
* 将q赋值给p
3.11 单链表结构与顺序存储结构优缺点
- 若线性表需要频繁的查找，很少进行插入和删除操作时，宜采用顺序存储结构。若需要频繁插入和删除时，宜采用单链表结构。
- 当线性表中的元素个数变化较大或则根本不知道有多大时，最好用单链表结构。这样可以不需要考虑存储空间的大小问题。而如果事先知道线性表的大致长度，这种用顺序存储结构效率会高很多。
3.12 静态链表
其实C语言真是好东西，它具有的指针能力，使得它可以非常容易地操作内存中的地址和数据，这比其他高级语言更加灵活方便。
首先我们让数组的元素都是由两个数据域组成，data和cur。也就是说，数组的每个下标都对应一个data和cur。数据域data，用来存放数据元素，也就是我们通常要处理的数据；而游标cur相当于单链表中的next指针，存放该元素的后继在数组中的下标。
我们把这种用数组描述的链表叫做静态链表，这种描述方法还有起名叫做游标实现法。
另外我们对数组第一个和最后一个元素作为特殊元素处理，不存数据。我们通常把未被使用的数组元素称为备用链表。而数组第一个元素，即下表为0的元素的cur就存放备用链表的第一个结点的下标；而数组的最后一个元素的cur则存放第一个有数值的元素的下标，相当于单链表中的头结点作用，当整个链表为空时，则为O^2。
此时，“甲”这里就存有下一元素“乙”的游标2，“乙”则存有下一元素“丁”的下标3。而“庚”是最后一个有值元素，所以它的cur设置为0，而最后一个元素的cur则因“甲”第一有值元素而存有它的下标为1。而第一个元素则因空闲空间的第一个元素下标为7，所以它的cur存有7。
3.12.1 静态链表的插入操作
静态链表中要解决的是：如何用静态模拟动态链表结构的存储空间的分配，需要时申请，无用时释放。
为了辨明数组中哪些分量未被使用，解决的办法是将所有未被使用过的及已被删除的分量用游标链成一个备用的链表，每当进行插入时，便可以从备用链表上取得第一个结点作为带插入的新节点。
这段代码有意思，一方面它的作用就是返回一个下标值，这个值就是数组头元素的cur存的第一个空闲的下标。从上面的图示例子来看，其实就是返回7。
那么既然下标为7的分量准备使用了，就得有接替者，所以就把分量7的cur值赋值给头元素，也就是把8给space[0].cur。之后就可以继续分配新的空闲分量，实现类似malloc()函数的作用。
- 当我们执行插入语句时，我们的目的是要在“乙”和“丁”之间插入“丙”。调用代码时，输入i值为3。
- 第4行让k=MAX_SIZE-1=999
- 第7行，j=Malloc_SSL(L) = 7。此时下标为0的cur也因为7要被占用而更改备用链表的值为8。
- 第11~12行，for循环1由1到2，执行两次。代码k= L[k].cur;使得k=999,得到k=L[999].cur = 1;在得到k=L[1].cur = 2。
- 第13行，L[j].cur = L[k].cur;因j=7,而k=2得到L[7].cur = L[2].cur = 3.这就是刚才我所的让“丙”把它的cur改为3的意思。
- 第14行，L[k].cur = j;意思就是L[2].cur= 7.也就是让“乙”得点好处，把它的cur改为指向“丙”的下标7.
3.12.2 静态链表的删除操作
这一节我没看懂释放怎么做的
3.12.2 静态链表的删除操作优缺点
