链表定义：
采用链式存储结构的线性表称为链表 。 现在我们从两个角度来讨论链表：
1.从实现角度看，链表可分为动态链表和静态链表；
2.从链接方式的角度看，链表可分为单链表、循环链表和双链表。
2.3.1 单链表结点（Node）为了正确地表示结点间的逻辑关系，必须在存储线性表的每个数据元素值的同时，存储指示其后继结点的地址（或位置）信息，这两部分信息组成的存储映象叫做结点（Node）。
单链表：链表中的每个结点只有一个指针域，我们将这种链表称为单链表。
单链表包括两个域：数据域用来存储结点的值；指针域用来存储数据元素的直接后继的地址（或位置）。
头指针 ：指向链表头结点的指针。
单链表的示例图： 带头结点的单链表示意图有时为了操作的方便，还可以在单链表的第一个结点之前附设一个头结点。
单链表的存储结构描述typedef struct Node / * 结点类型定义 * /
{ ElemType data；
struct Node * next；
}Node, *LinkList；
2单链表上的基本运算：
建立单链表
头插法建表：
算法描述：从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头结点之后，直至读入结束标志为止。
Linklist CreateFromHead()
{ LinkList L; Node *s; int flag=1;
L=(Linklist)malloc(sizeof(Node))；
L->next=NULL;
while(flag)
{ c=getchar();
if(c!=’$’)
{ s=(Node*)malloc(sizeof(Node)); s->data=c;
s->next=L->next; L->next=s; }
else flag=0;
}
}
尾插法建表
尾插法建表算法
Linklist CreateFromTail()
{ LinkList L; Node *r, *s; int flag =1;
L=(Node * )malloc(sizeof(Node));
L->next=NULL; r=L;
while(flag)
{ c=getchar();
if(c!=’$’)
{ s=(Node*)malloc(sizeof(Node)); s->data=c;
r->next=s; r=s }
else { flag=0; r->next=NULL; }
}
}
单链表查找
按序号查找
算法描述：设带头结点的单链表的长度为n，要查找表中第i个结点，则需要从单链表的头指针L出发，从头结点（L->next）开始顺着链域扫描，用指针p指向当前扫描到的结点,初值指向头结点（pL->next），用j做记数器，累计当前扫描过的结点数（初值为0），当j = i 时，指针p所指的结点就是要找的第i个结点 。算法实现，算法演示。
按序号查找算法实现
/ * 在带头结点的单链表L中查找第i个结点，若找到(1≤i≤n)，则返回该结点的存储位置; 否则返回NULL * /
Node * Get(LinkList L, int i)
{ Node *p；
p=L；j=0； / * 从头结点开始扫描 * /
while ((p->next!=NULL)&&(jnext； j++； / * 扫描下一结点 * /
} / * 已扫描结点计数器 * /
if（i= =j）return p； / * 找到了第i个结点 * /
else return NULL； / * 找不到，i≤0或i>n * /
}
按值查找
算法描述：按值查找是指在单链表中查找是否有结点值等于e的结点，若有的话，则返回首次找到的其值为e的结点的存储位置，否则返回NULL。查找过程从单链表的头指针指向的头结点出发，顺着链逐个将结点的值和给定值e作比较。算法实现，算法演示。
/ * 在带头结点的单链表L中查找其结点值等于key的结点，若找到则返回该结点的位置p，否则返回NULL * /
Node *Locate( LinkList L,ElemType key)
{ Node *p;
p=L->next; / * 从表中第一个结点比较 * /
while (p!=NULL)
if (p->data!=key)
p=p->next;
else break; / * 找到结点key，退出循环 * /
return p;
}
单链表插入操作
算法描述：要在带头结点的单链表L中第i个数据元素之前插入一个数据元素e，需要首先在单链表中找到第i-1个结点并由指针pre指示，然后申请一个新的结点并由指针s指示，其数据域的值为e，并修改第i-1个结点的指针使其指向s，然后使s结点的指针域指向第i个结点。
单链表插入操作算法实现
void InsList(LinkList L,int i,ElemType e)
{
Node *pre,*s; pre=L; int k=0;
while(pre!=NULL&&knext; k=k+1; }
if(k!=i-1)
{ printf(“插入位置不合理！”)； return; }
s=(Node*)malloc(sizeof(Node));
s->data=e;
s->next=pre->next; pre->next=s;
}
单链表删除
算法描述：欲在带头结点的单链表L中删除第i个结点，则首先要通过计数方式找到第i-1个结点并使p指向第i-1个结点，而后删除第i个结点并释放结点空间。
单链表删除算法实现
void DelList(LinkList L,int i,ElemType *e)
{
Node *p,*r; p=L; int k =0;
while(p->next!=NULL&&knext; k=k+1; }
if(k!=i-1)
{ printf(“删除结点的位置i不合理！”); return ERROR; }
r=p->next; p->next=p->next->next
free(r);
}
求单链表的长度
算法描述：可以采用“数”结点的方法来求出单链表的长度，用指针p依次指向各个结点,从第一个元素开始“数”，一直“数”到最后一个结点（p->next=NULL）。
int ListLength(LinkList L)
{ Node *p; p=L->next;
j=0;
while(p!=NULL)
{ p=p->next; j ++; }
return j;
}
求两个集合的差
2.3.3 循环链表
2.3.4 双向链表
2.3.5 静态链表
2.3.6 顺序表和链表的比较
