线性表的链式表示和实现（链表）
线性表链式存储结构的特点，就是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素与其直接后继元素之间的逻辑关系。每个数据元素（称为结点）包括两个域：存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。
//-------单链表的存储结构------
typedef struct LNode{
ElemType data; //结点的数据域
struct LNode *next; //结点的指针域
}LNode,*LinkList; //LinkList为指向结构体LNode的指针类型
（1）单链表的初始化
1.生成新结点作为头结点，用头指针L指向头结点
2.头结点的指针域置空
Status InitList(LinkList &L){
//构造一个空的单链表
L = new LNode; //生成新结点作为头结点，用头指针L指向头结点
L -> next = NULL; //头结点的指针域置空
return OK;
}
（2）单链表的取值
1.用指针p指向首元结点，用j做计数器初值赋为1
2.从首元结点开始依次顺着链域next向下访问，只要指向当前结点的指针p不为空（NULL），并且没有达到序号为i的结点，则循环执行以下操作：
①p指向下一个结点；
②计数器j相应加1。
③退出循环时，如果指针p为空，或者计数器j大于i，说明指定的序号i值不合法（i大于表长n或者i小于等于0），取值失败返回ERROR；否则取值成功，此时j=i时，p所指的结点就是要找的第i个结点，用参数e保持当前结点的数据域，返回OK。
Status GetElem(LinkList L,int i,ElemType &e){
//在带头结点的单链表L中根据序号i获取元素的值，用e返回L中第i个数据元素的值
p = L -> next; //初始化，p指向首元结点
j = 1; //计数器j初值赋为1
while(p && j < i){ //顺链域向后扫描，知道p为空或p指向第i个元素
p = p -> next; //p指向下一个结点
++j; //计数器相应加1
}
if(!p || j > i){ //i值不合法 i>n或i≤0
return ERROR;
}
e = p -> data; //取第i个结点的数据域
return OK;
}
（3）单链表的按值查找
1.用指针p指向首元结点
2.从首元结点开始依次顺着链域next向下查找，只要指向当前结点的指针p不为空，并且p所指结点的数据域不等于给定值e，则循环执行一下操作：p指向下一个结点。
3.返回p。若查找成功，p此时即为结点的地址值，若查找失败，p的值即为NULL。
LNode *LocateElem(LinkList L, ElemType e){
//在头结点的单链表L中查找值为e的元素
p = L -> next; //初始化，p指向首元结点
while(p && p -> data != e){ //顺链域向后扫描，直到p为空或p所指结点的数据域等于e
p = p -> next; //p指向下一个结点
}
return p; //查找成功返回值为e的结点地址p，查找失败p为NULL
}
（4）单链表的插入
1.查找结点a(i-1)并由指针p指向该结点。
2.生成一个新结点s。
3.将新结点s的数据域置为e。
4.将新结点s的指针域指向结点a(i)。
5.将结点p的指针域指向新结点*s。
Status ListInsert(LinkList &L,int i,ElemType e){
//在带头结点的单链表L中第i个位置插入值为e的新结点
p = L;
j = 0;
while(p || (j < i-1)){
p = p -> next; //查找第i-1个结点，p指向该结点
++j;
}
if(!p || j > i-1){ //i>n+1或者i<1
return ERROR;
}
s = new LNode; //生成新结点*s
s -> data = e; //将结点*s的数据域置为e
s -> next = p -> next; //将结点*s的指针域指向结点a(i)
p -> next = s; //将结点*p的指针域指向结点*s
return OK;
}
（5）单链表的删除
1.查找结点a(i-1)并由指针p指向该结点
2.临时保存待删除结点a(i)的地址在q中，以备释放。
3.将结点*p的指针域指向a(i)的直接后继结点。
4.释放结点a(i)的空间
Status ListDelete(LinkList &L, int i){
//在带头结点的单链表L中，删除第i个元素
p = L;
j = 0;
while((p -> next) && (j < i - 1)){ //查找第i-1个结点，p指向该节点
p = p -> next;
++j;
}
if(!(p -> next)||(j > i - 1)){ //当i>n或i<1时，删除位置不合理
return ERROR;
}
q = p -> next; //临时保存被删除结点的地址以备释放
p -> next = q -> next; //改变删除结点前驱结点的指针域
delete q; //释放删除结点的空间
return OK;
}
（6）前插法创建单链表
前插法是通过将新结点逐个插入链表的头部（头结点之后）来创建链表，每次申请一个新结点，读入相应的数据元素值，然后将新结点插入到头结点之后。
1.生成一个只有头结点的空链表。
2.根据待创建链表包括的元素个数n，循环n次执行以下操作：
①生成一个新结点p；
②输入元素值赋给新结点p的数据域；
③将新结点*p插入到头结点之后。
void CreateList_H(LinkList &L,int n){
//逆位序输入n个元素的值，建立带表头结点的单链表L
L = new LNode;
L -> next = NULL; //先建立一个带头结点的空链表
for(i = 0;i < n;++i){
p = new LNode; //生成一个新结点*p
cin >> p -> data; //输入元素值赋给新结点*p的数据域
p -> next = L -> next; //将新结点*p插入到头结点之后
L -> next = p;
}
}
（6）后插法创建单链表
后插法是荣光将新结点逐个插入到链表的尾部来创建链表。通前插法一样，每次申请一个新结点，读入相应的数据元素值。不同的是，为了使新结点能够插入到表尾，需要增加一个尾指针r指向链表的尾节点。
①生成一个新结点p；
②输入元素值赋给新结点p的数据域；
③将新结点p插入到尾节点r之后；
④尾指针r指向新的尾节点*p。
void CreateList_R(LinkList &L,int n){
//正位序输入n个元素的值，建立带表头结点的单链表L
L = new LNode;
L -> next = NULL; //先建立一个带头结点的空链表
r = L; //尾指针r指向头结点
for(i = 0;i < n;++i){
p = new LNode; //生成新结点
cin >> p -> data; //输入元素赋值给新结点*p的数据域
p -> next = NULL;
r -> next = p; //将新结点*p插入尾节点*r之后
r = p; //r指向新的尾节点*p
}
}
