3.6 单链表的读取
在线性表的顺序存储结构中，我们要计算任意-一个元素的存储位置是很容易的。但在单链表中，由于第i个元素到底在哪?没办法-开始就知道，必须得从头开始找。因此，对于单链表实现获取第i个元素的数据的操作GetElem,在算法上，相对要麻烦一些。
获得链表第i个数据的算法思路:
1.声明一个结点p指向链表第一个结点，初始化j从1开始;
2.当j<i时，就遍历链表，让p的指针向后移动，不断指向下一结点，j 累加1;
3.若到链表末尾p为空，则说明第i个元素不存在;
4.否则查找成功，返回结点p的数据。.
/*初始条件:顺序线性表L已存在，1≤i≤ListLength (L) */ /*操作结果:用e返回L中第i个数据元素的值*/ Status GetElem ( LinkList L,int i, ElemType*e) { int j; LinkList P; /*声明一结点 p*/ P= L->next; /*让p指向链表L的第一个结点*/ j=1; /*j为计数器*/ while (p && j<i) /*p不为空或者计数器j还没有等于i时，循环继续*/ { p= p->next; /*让p指向下一个结点*/ ++j; } if (!pHI j>i ) return ERROR; /*第i个元素不存在*/ *e = p->data; /*取第i个元素的数据*/ return OK; }
说白了，就是从头开始找，直到第i个元素为止。由于这个算法的时间复杂度取
决于i的位置，当i=1时，则不需遍历，第一个就取出数据了，而当i=n时则遍历n-1次才可以。因此最坏情况的时间复杂度是O(n)。
由于单链表的结构中没有定义表长，所以不能事先知道要循环多少次，因此也就不方便使用for来控制循环。其主要核心思想就是‘工作指针后移”， 这其实也是很多算法的常用技术。
3.7 单链表的插入与删除
3.7.1 单链表的插入
先来看单链表的插入。假设存储元素e的结点为s,要实现结点p、p->next 和s .
之间逻辑关系的变化，只需将结点s插入到结点p和p->next之间即可。可如何插入呢?
根本用不着惊动其他结点，只需要让s->next和p->next的指针做一点改 变即可。
s->next=p->next; p->next=s;
就是说让p的后继节节点改成s的后继节点，再把s变成p的后继节点
这段话需要多去体会，看不懂的可以再往前复习一下！很久好理解的
如果先p->next = s;再s->next= p->next行不行呢？
不行哦，因为第一句会使得p->next给覆盖成s的地址了。那么s->next = p->next，其实就等于s->next = s
这一点要是不懂的话一定要自己画个图，然后再写上过程
对于单链表的表头和表尾的特殊情况，操作是相同的
单链表第i个数据插入结点的算法思路:
1.声明一结点p指向链表第一个结点，初始化j从1开始;
2.当j<i时，就遍历链表，让p的指针向后移动，不断指向下一-结点，j累加1;
3.若到链表末尾p为空，则说明第i个元素不存在;
4.否则查找成功，在系统中生成-一个空结点s;
5.将数据元素e赋值给s->data;
6.单链表的插入标准语句s->next=p->next p->next=s;
7.返回成功。
代码实现：
#include <stdio.h>/*初始条件:顺序线性表L已存在，1≤i≤ListLength (L)，/*操作结果: 在L中第1个位置之前插入新的数据元素 e,L的长度加 1*/Status ListInsert(LinkList *L, int i, ElemType e){ int j; LinkList p, s; p = *L; j = 1; while (p && j < i) //寻找第i个结点，通过让p指针一直向后指，直到找到目标元素为止 { p = p->next; ++j; } if(!p || j > i) return ERROR; s = (LinkList)malloc(sizeof(Node));//生成新的结点 s->data = e; s->next = p->next; p->next = s; return OK; }
实际代码是执行不通的，主要是学习这个思想
核心思想就是工作指针后移
3.7.2 单链表的删除
删除结点只需要将删除结点的前驱指针绕过，指向它的后继结点即可
我们所要做的，实际上就是一步，p->next=p->next>next, 用q来取代p->next,即是
q = p->next;p->next=q->next
解读这两句代码，也就是说让p的后继的后继结点改成p的后继结点。
单链表第i个数据删除结点的算法思路
1.声明一结点p指向链表第一一个结点， 初始化j从1开始
2.当j<i时，就遍历链表，让p的指针向后移动，不断指向下一个结点, j累加1
3.若到链表末尾p为空，则说明第i个元素不存在
4.否则查找成功，将欲删除的结点p->next赋值给q
5.单链表的删除标准语句p->next=q->next
6.将q结点中的数据赋值给e,作为返回
7.释放q结点
8.返回成功
代码实现
初始条件:顺序线性表L已存在，1≤i≤ListLength (L)
操作结果: 删除L中的第i个数据元素，并用e返回其值，L中的长度减1
Status ListDelete (LinkList *L, int i, ElemType *e){ int j; LinkList p,q; P = *L; j = 1; while (p->next && j< i) /*遍历寻找第 i个元素*/ { P = P->next; ++j; } if (!(p->next) || j > i) return ERROR; /*第i个元素不存在*/ q = p->next; p->next = q->next; /*将q的后继赋值给p的后继*/ *e= q->data; /*将q结点中的数据给e*/ free (q) ; /*让系统回收此结点，释放内存*/ return OK;}
代码看不懂的，可以再回去画一遍图
分析一下刚才我们讲解的单链表插入和删除算法，我们发现，它们其实都是由两部分组成:第一部分就是遍历查找第i个元素;第二部分就是插入和删除元素。
从整个算法来说，我们很容易推导出:它们的时间复杂度都是O(n)。 如果在我们不知道第i个元素的指针位置，单链表数据结构在插入和删除操作上，与线性表的顺序存储结构是没有太大优势的。但如果，我们希望从第i个位置,插入10个元素，对于顺序存储结构意味着，每一次插入都需要移动n-i个元素，每次都是O(n)。 而单链表，我们只需要在第一次时，找到第i个位置的指针，此时为0(n)，接下来只是简单地通过赋值移动指针而已，时间复杂度都是0(1)。显然，对于插入或删除数据越频繁的操作，单链表的效率优势就越是明显。
