链式存储相关概念

• 用一组物理地址任意的存储单元来存放线性表的数据元素；
• 这组存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置；
• 链表中元素的逻辑次序和物理次序不一定相同。

结点：数据元素的存储映像。由数据域和指针两部分组成。
链表：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;
}

链式存储总结

优点：

• 结点空间可以动态申请和释放；
• 数据元素的逻辑次序靠结点的指针指示，插入和删除时不需要移动元素。

缺点：
-存储密度小，每个结点的指针域需额外占用存储空间。当每个结点的数据域所占字节不多时，指针域所占存储空间的比重显得很大；
链式存储结构是非随机存取结构。对任一结点的操作都要从头指针链查到该结点，这增加了算法的复杂度。

顺序表和链表的比较