@TOC
链式存储相关概念
- 用一组物理地址任意的存储单元来存放线性表的数据元素；
- 这组存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置；
- 链表中元素的逻辑次序和物理次序不一定相同。
结点：数据元素的存储映像。由数据域和指针两部分组成。
链表：n个结点由指针链组成一个链表。
它是线性表的链式存储映像，称为线性表的链式存储结构。
单链表、双链表、循环链表：
- 结点只有一个指针域的链表，称为单链表或线性链表
- 结点有两个指针域的链表，称为双链表
- 收尾相连的链表称为循环链表
头指针、头结点和首元结点：
- 头指针：是指向链表中第一个结点的指针
- 首元结点：是指链表中存储第一个数据元素a~1~的结点
- 头结点：是在链表的首元结点之前附设的一个结点
链表（链式存储结构）的特点
- 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻；
- 访问是只能通过头指针进入链表，并通过每个结点的指针域依次向后顺序扫描其余结点，所以寻找第一个结点和最后一个结点所花的时间不等。
单链表
单链表的存储结构
typedef struct Lnode { //声明结点的类型和指向结点的指针类型
ElemType data ; //结点的数据域
struct Lnode *next; //指针域
}LNode,*LinkList; //LinkList为指向结构体Lnode的指针类型例如，存储学号、姓名、成绩的单链表结点类型定义如下：
typedef Struct {
char num[8]; //数据域
char name[8]; //数据域
int score; //数据域
}ElemType;
typedef struct Lnode {
ElemType data ; //结点的数据域
struct LNode *next; //指针域
} 单链表的操作
单链表的初始化
即构造一个空表
Status InitList_L(LinkList &L) {
L = new LNode; //或L = (LinkList)malloc (sizeof(LNode))
L->next = NULL;
return OK;
}销毁单链表L
Status DeleteList_L(LinkList &L){
LNode *p;
while(L){
p=L;
L=L->next;
delete p;
}
}清空链表L
Status ClearList_L(LinkList &L){ //将L重置为空表
LNode *p,*q;
p = L->next;
while(p){
q = p->next;
delete p;
p = q;
}
L->next = NULL;
return OK;
}求单链表的表长
int ListLength_L(LinkList L){ //返回L中元素个数
LinkList p;
p = L->next;
i=0;
while(p){
i++;
p = p->next;
}
return i;
}查找第i个元素
Status GetElem_L(LinkList L,int i,ElenType &e){
//获取线性表L中第i个元素的内容，通过变量e返回
p = L->next;
j = 1;
while(p&&j<i){
p = p->next;
j++;
}
if(!p||j>i){
return ERROR;
}
e = p->data;
return OK;
}安值查找
int LocateElem_L(LinkList L,ElenType e){
//在线性表L中查找值为e的数据元素的位置序号
p = L->next;
j=1;
while(p&&p->data!=e){
p = p->next;
j++;
}
if(p) return j;
else return 0;
}单链表的插入
Status ListInsert_L(LinkList &L,int i,ElemType e){
//在L中第i个元素前插入数据元素e
p = L;
j = 0;
while(p&&j<i-1){
p = p->next;
j++;
}
if(p||j>i-1) return ERROR;
s = new LNode;
s->data = e;
s->next = p->next;
p->next = s;
}单链表的删除
Status ListDelete_L(LinkList &L,int i,ElemType &e){
//将L中第i个数据元素删除
p = L;
j = 0;
while(p&&j<i-1){
p = p->next;
j++;
}
if(p->next||j>i-1) return ERROR;
q = p->next;
p->next = q->next;
e = q->data;
delete q;
return OK;
}头插法建立链表
void CreateList_H(LinkList &l,int n){
L = new LNode;
L->next = NULL;
for(i = n;i>0;i--){
p = new LNode;
cin>>p->data;
p->next = L->next;
L->next = p;
}
}尾插法建立链表
void CreateList_R(LinkList &l,int n){
L = new LNode;
L->next = NULL;
r = L;
for(i = 0;i<n;i++){
p = new LNode;
cin>>p->data;
p->next = NULL;
r->next = p;
r = p;
}
}循环链表
一种头尾相连的链表（即：表中最后一个结点的指针域指向头结点，整个链表形成一个环）。
从表中任一结点出发均可找到表中其他结点。
双向链表
在单链表的每个结点里在增加一个指向其直接前驱的指针域prior，这样链表中就形成了有两个方向不同的链。
双向链表的存储结构
typede struct DuLNode {
ElemType data;
struct DuLNode *prior,*next;
}DuLNode,*DulLinkList;双向链表的操作
双向链表的插入
void ListInsert_DuL(DuLinkList &L,int i,ElemType e){
//在带头结点的双向链表L中第i个位置之前插入元素e
if(!(p = GetElemP_DuL(L,i))) return ERROR; //得到第i个位置的结点p
s = new DuLNode;
s->data = e;
s->prior = p->prior;
p->prior->next = s;
s->next = p;
p->prior = s;
return OK;
}双向链表的删除
void ListDelete_DuL(DuLinkList &L,int i,ElemType &e){
//删除带头结点的双向链表L的第i个元素，并用e返回
if(!(p = GetElemP_DuL(L,i))) return ERROR; //得到第i个位置的结点p
e = p->data;
p->prior->next = p->next;
p->next->prior = p->prior;
free(p);
return OK;
}链式存储总结
优点：
- 结点空间可以动态申请和释放；
- 数据元素的逻辑次序靠结点的指针指示，插入和删除时不需要移动元素。
缺点：
-存储密度小，每个结点的指针域需额外占用存储空间。当每个结点的数据域所占字节不多时，指针域所占存储空间的比重显得很大；
链式存储结构是非随机存取结构。对任一结点的操作都要从头指针链查到该结点，这增加了算法的复杂度。
顺序表和链表的比较
