線性表之《鏈表的表示及基本操作的實作》

一、單鏈表

（一）單鏈表的描述

typedef struct LNode {
	ElemType data;//結點資料域
	struct LNode* next;//結點指標域
}LNode ,*LinkList;

變數定義：
LNode* p, * q     LinkList L;
p, q, L都是指標變數，* p, * q, * L都是結點變數

指標變數p : 表示結點地址
結點變數* p：表示一個結點

p->data;//表示資料域
p->next;//表示指標域

typedef struct LNode {
	ElemType data;//結點資料域
	struct LNode* next;//結點指標域
}LNode ,*LinkList;

LinkList p, s, L;//指標變數的定義
L = new LNode;//為指標變數L分配記憶體空間
p = L;//p指向頭結點
s = L->next;//s指向首元結點

（一）單鏈表的操作實作

1、初始化

演算法思想：
（1）、生成新結點作為頭結點，用頭指標L指向頭結點
（2）、頭結點的指標域置為空

/*初始化*/
Status InitList(LinkList& L)
{
	L = new LNode;//生成新結點作為頭結點，用頭指標L指向頭結點
	L->next = NULL;//頭結點的指標域置為空
	return OK;
}

2、查找

演算法思想：
（1）、初始化，p指向第一個結點，j為計數器
（2）、從鏈表頭依次向后掃描，直到p為慷訓p指向第i個元素
（3）、更新p指向當前結點，計數器+1
（4）、i 值不合法（i<=0或者i>n)
（5）、取第i個結點的資料域

/*按序號查找*/
Status GetElem(LinkList L, int i, ElemType& e)
{
	LinkList p;
	int j;
	p = L->next;j = 1;//初始化，p指向第一個結點，j為計數器
	while (p && j < i)//從鏈表頭依次向后掃描，直到p為慷訓p指向第i個元素
	{
		p = p->next;//更新p指向當前結點
		++j;//計數器+1
	}
	if (!p || j > i) return ERROR;//i 值不合法（i<=0或者i>n)
	e = p->data;//取第i個結點的資料域
	return OK;
}

3、插入

演算法思想：
(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)
{
	p = L;
	int j = 0;
	while (p && j < i - 1)//尋找第i - 1個結點
	{
		p = p->next;//指向當前結點
		++j;
	}
	if (!p || j > i - 1) return ERROR;//i值不合法
	LinkList s;
	s = new LNode;//生成新結點s
	s->data = e;//新結點的資料域置為e
	s->next = p->next;//新結點 * s的指標域指向a i
	p->next = s;//結點*p指標域指向結點*s
	return OK;
}

4、洗掉

演算法思想：
(1)查找結點a i-1所在位置，并由指標p指向該結點
(2)臨時保存待洗掉結點ai的地址在q中，以備釋放
(3)將結點*p指向結點ai的直接后繼結點
(4)釋放結點ai的空間

Status LinkDelete(LinkList & L, int i)
{
	p = L;
	j = 0;
	while (p->next && j < i - 1)//尋找第i-1個結點
	{
		p = p->next;
		++j;
	}
	if (!(p->next) || j > i - 1) return ERROR;
	q = p->next;//臨時保存待洗掉結點ai的地址在q中，以備釋放
	p->next = q->next;//將結點*p指向結點ai的直接后繼結點
	delete q;//釋放結點ai的空間
	return OK;
}

5、單鏈表的建立（前插法）

描述：前插法是通過將新結點逐個插入鏈表的頭部（頭結點之后）來創建鏈表，每次申請一個新結點，讀入相應的資料元素值，然后將新結點插入到頭結點之后，

演算法思想
（1）創建一個只有頭結點的空鏈表，
（2）根據待創建鏈表包括的元素個數n，回圈n次執行以下操作：
1、生成一個新結點p;
2、輸入元素值賦值給新結點p的資料域；
3、將新結點*p插入到頭結點之后，

/*單鏈表的建立（前插法）*/
void CreateList(LinkList& L, int n)
{
	L = new LNode;//建立一個帶頭結點的空鏈表
	L->next = NULL;

	for (i = n;i > 0;--i)//回圈插入新結點
	{
		p = new LNode;//生成新結點*p
		scanf_s("%d", &p->data);//輸入元素賦值給p->data
		p->next = L->next;//將新結點*p插入到頭結點后
		L->next = p;
	}
}

6、單鏈表的建立（后插法）

描述：后插法是通過將新結點逐個插入到鏈表的尾部來創建鏈表，同前插法一樣，每次申請一個新結點，讀入相應資料元素值，不同的是，為了使新結點能夠插入到表尾，需要增加一個尾指標r指向鏈表的尾結點，

演算法思想：
（1）創建一個只有頭結點的空鏈表
（2）尾指標r初始化，指向頭結點
（3）根據創建鏈表包括的元素個數n,回圈n次執行以下操作：
1、生成一個新結點p;
2、輸入元素值賦給新結點p的資料域
3、將新結點p插入到尾結點r之后；
4、尾指標r指向新的尾結點*p.

/*單鏈表的建立（后插法）*/
void CreateList(LinkList& L, int n)
{
	L = new LNode;//建立帶頭結點的空鏈表
	L->next = NULL;
	r = L;//尾指標指向頭結點

	for (i = 0;i < n;i++)
	{
		p = new LNode;//生成新結點p
		scanf_s("%d", &p->data);//輸入資料域
		p->next = NULL;
		r->next = p;//插入到尾表
		r = p;//r指向新的尾結點
	}
}

二、回圈鏈表

特點是表中最后一個結點的指標域指向頭結點，整個鏈表形成一個環，

從回圈鏈表中的任何一個結點的位置都可以找到其他所有的結點，而單鏈表做不到，回圈鏈表中沒有明顯的尾端，

實作

p->next = B->next;
B->next = A->next;
A->next = p->next;
delete p;
A = B;

三、雙向鏈表

有兩個指標域的鏈表，稱為雙鏈表

/*雙向鏈表的存盤結構*/
typedef struct DuLNode {
	ElemType data;//資料域
	struct DuLNode *prior;//前指標域
	struct DuLNode* next;//后指標域
}DuLNode,*DuLinkLst;

1、插入

/*雙向鏈表的插入*/
Status ListInsert_DuL(DuLinkList& L, int i, ElemType e)
{
	if (!(p = GetElemP_DuL(L, i)))//在L中確定第i個元素的位置指標p
		retrun ERROR;//p為NULL時，第i個元素不存在
	s = new DuLNode;//生成一個新結點s
	s->data = e;//將資料e存入到結點s的資料域data中
	s->prior = p->prior;//將結點s的前指標指向前一個結點
	p->prior->next = s;//將前一個結點的后指標指向新結點s
	s->next = p;//新結點s的后指標指向p
	p->prior = s;//p的前指標指向新結點
	return OK;
}

1、洗掉

/*雙向鏈表的洗掉*/
Status ListDelete_DuL(DuLinkList& L, int i, ElemType &e)
{
	if (!(p = GetElemP_DuL(L, i)))//在L中確定第i個元素的位置指標p
		retrun ERROR;//p為NULL時，第i個元素不存在
	e = p->data;//保存被洗掉結點的資料域
	p->prior->next = p->next;//修改被洗掉結點的前驅結點的后繼指標
	p->next->prior = p->prior;//修改被洗掉結點的后繼結點的前驅指標
	delete p;//釋放被洗掉結點的空間
	return OK;
}