数据结构-线性表链式存储结构
链式存储
链式存储 ：用一组任意的存储单元存储线性表中的数据元素。用这种方法存储的线性表简称线性链表。
存储链表中结点的一组任意的存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。 链表中结点的逻辑顺序和物理顺序不一定相同。（即不要求逻辑上相邻的元素在物理位置上也相邻）
为了正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其直接后继结点的地址(或位置)，称为指针(pointer)或链(link)，这两部分组成了数据元素ai的存储映像
链表是通过每个结点的指针域将线性表的n个结点按其逻辑次序链接在一起的。
每一个结点只包含一个指针域的链表，称为单链表。
为操作方便，总是在链表的第一个结点之前附设一个头结点(头指针)head指向第一个结点（即头结点的指针域存放第一个结点的存储位置）。头结点的数据域可以不存储任何信息(或链表长度等信息)。
因为最后一个数据元素没有直接后继，所以线性链表中最后一个结点的指针为空（NULL）。
为操作方便，总是在链表的第一个结点之前附设一个头结点(头指针)head指向第一个结点（即头结点的指针域存放第一个结点的存储位置）。头结点的数据域可以不存储任何信息(或链表长度等信息)。
因为最后一个数据元素没有直接后继，所以线性链表中最后一个结点的指针为空（NULL）。
结点的描述与实现
C语言中用带指针的结构体类型来描述
typedef struct Lnode
{ ElemType data; /*数据域，保存结点的值 */
struct Lnode *next; /*指针域，类型是struct Lnode */
}LNode, *LinkList; /*结点的类型名 */
LNode，结点结构；LinkList：链表结构
//LinkList L；L为单链表名，同时也可作为表的头指针名，指向表中第一个结点，即L的指针域存储第一个结点的地址。
//若L为空，则表示线性表为空表，其长度为0.结点的实现
结点是通过动态分配和释放来的实现，即需要时分配，不需要时释放。实现时是分别使用C语言提供的标准函数：malloc() ，realloc()，sizeof() ，free() 。
动态分配 p=(LNode*)malloc(sizeof(LNode));
函数malloc分配了一个类型为LNode的结点变量的空间，并将其首地址放入指针变量p中。
动态释放 free(p) ;
系统回收由指针变量p所指向的内存区。p必须是最近一次调用malloc函数时的返回值。
算法描述
LNode *create_LinkList(void)
/* 头插入法创建单链表,链表的头结点head作为返回值 */
{ int data ;
LNode *head, *p;
head= (LNode *) malloc( sizeof(LNode));
head->next=NULL; /* 创建链表的表头结点head */
while (1) //一直执行
{ scanf(“%d”, &data) ;
if (data==32767) break ;
p= (LNode *)malloc(sizeof(LNode));
p->data=data; /* 数据域赋值 */
p->next=head->next ; head->next=p ;
/* 钩链，新创建的结点总是作为第一个结点 */
}
return (head);
}
// 返回值是表头结点head，实际就是所创建的链表。此时主函数中只要建一个LNode *类型的变量，即可调用该函数。如
LNode *head; 或者LinkList head;
head=create_LinkList();
尾插入法建表
头插入法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。
该方法是将新结点插入到当前链表的表尾，使其成为当前链表的尾结点。
算法描述
LNode *create_LinkList(void)
/* 尾插入法创建单链表,链表的头结点head作为返回值 */
{ int data ;
LNode *head, *p, *q;
head=p=(LNode *)malloc(sizeof(LNode));
p->next=NULL; /* 创建单链表的表头结点head */
while (1)
{ scanf(“%d”,& data);
if (data==32767) break ;
q= (LNode *)malloc(sizeof(LNode));
q->data=data; /* 数据域赋值 */
q->next=p->next; p->next=q; p=q ;
/*钩链，新创建的结点总是作为最后一个结点*/
}
return (head);
}无论是哪种插入方法，如果要插入建立单链表的结点是n个，算法的时间复杂度均为O(n)。 对于单链表，无论是哪种操作，只要涉及到钩链(或重新钩链)，如果没有明确给出直接后继，钩链(或重新钩链)的次序必须是“先右后左”，否则就会丢掉链表中的一些结点。
单链表的查找
(1) 按序号查找 取单链表中的第i个元素。
对于单链表，不能象顺序表中那样直接按序号i访问结点，而只能从链表的头结点出发，沿链域next逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表不是随机存取结构。
设单链表的长度为n，要查找表中第i个结点，仅当1≦i≦n时，i的值是合法的。
算法思想如下：
从头结点开始顺链扫描，用指针p指向当前扫描到的结点，用j作统计已扫描结点数的计数器，当p扫描下一个结点时，j自动加1。 P的初值指向头结点，j的初值为1。当j=i时，指针p所指的结点就是第i个结点。
算法描述
ElemType Get_Elem(LNode *L ， int i)
{ int j ; LNode *p;
p=L->next; j=1; /* 使p指向第一个结点 */
while (p!=NULL && j<i)
{ p=p–>next; j++; } /* 移动指针p , j计数 */
if ( !p|| j>i) return(ERROR) ;
/* p为NULL 表示i>n; j>i表示i=0 */
else return(p->data);
}
移动指针p的频度：
i=0时：0次; i∈[1,n]：i-1次；i>n：n次。
∴时间复杂度: O(n)。
按值查找
按值查找是在链表中，查找是否有结点值等于给定值key的结点? 若有，则返回首次找到的值为key的结点的存储位置；否则返回NULL。查找时从开始结点出发，沿链表逐个将结点的值和给定值key作比较。
算法描述
LNode *Locate_Node(LNode *L，int key)
/* 在以L为头结点的单链表中查找值为key的第一个结点 */
{ LNode *p=L->next;
while ( p!=NULL&& p->data!=key)
p=p–>next;
if (p->data==key) return p;
else
{ printf(“所要查找的结点不存在!!\n”);
retutn(NULL); }
}
算法的执行与形参key有关，平均时间复杂度为O(n)。