與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)相關(guān)的術(shù)語
1、結(jié)點(diǎn)：數(shù)據(jù)元素的存儲(chǔ)映像。由數(shù)據(jù)域和指針域兩部分組成

• 數(shù)據(jù)域：存放元素?cái)?shù)值數(shù)據(jù)
• 指針域：存放直接后繼結(jié)點(diǎn)的存儲(chǔ)位置

2、鏈表：n個(gè)結(jié)點(diǎn)由指針鏈組成一個(gè)鏈表

• 它是線性表的鏈?zhǔn)酱鎯?chǔ)映像，稱為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

3、單鏈表、雙鏈表、循環(huán)鏈表

• 結(jié)點(diǎn)只有一個(gè)指針域的 鏈表，稱為單鏈表或線性鏈表
• 結(jié)點(diǎn)有兩個(gè)指針域的鏈表，稱為雙鏈表
• 首尾相接的鏈表稱為循環(huán)鏈表

4、頭指針、頭結(jié)點(diǎn)和首元結(jié)點(diǎn)

• 頭指針：是指向鏈表中第一個(gè)結(jié)點(diǎn)的指針
  單鏈表是由表頭唯一確定，因此單鏈表可以用頭指針的名字來命名
  若頭指針名是L，則把鏈表稱為表L
• 首元結(jié)點(diǎn)：是指鏈表中存儲(chǔ)第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)
• 頭結(jié)點(diǎn)：是在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn)

5、鏈表可分為帶頭結(jié)點(diǎn)和不帶頭結(jié)點(diǎn)

• 無頭結(jié)點(diǎn)時(shí)，頭指針為空時(shí)表示空表
• 有頭結(jié)點(diǎn)時(shí)，當(dāng)頭指針的指針域?yàn)榭諘r(shí)表示空表

在鏈表中設(shè)置頭結(jié)點(diǎn)有什么好處？

• 1、便于首元結(jié)點(diǎn)的處理
  首元結(jié)點(diǎn)的地址保存在頭結(jié)點(diǎn)的指針域中，所以在鏈表的第一個(gè)位置上的操作和其他位置上一致，無須進(jìn)行特殊處理；
• 2、便于空表和非空表的統(tǒng)一處理
  無論鏈表是否為空，頭指針都是指向頭結(jié)點(diǎn)的非空指針，因此空表和非空表的處理也就統(tǒng)一了。

頭結(jié)點(diǎn)的數(shù)據(jù)域內(nèi)裝的是什么？

• 頭結(jié)點(diǎn)的數(shù)據(jù)域可以為空，也可以存放線性表長度等附加信息，但此結(jié)點(diǎn)不能計(jì)入鏈表長度值

鏈表（鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）的特點(diǎn)

• （1）結(jié)點(diǎn)在存儲(chǔ)器中的位置是任意的，即邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰。
• （2）訪問時(shí)只能通過頭指針進(jìn)入鏈表，并通過每個(gè)結(jié)點(diǎn)的指針域依次向后順序掃描其余結(jié)點(diǎn)，（這種存取元素的方法稱為順序存取法）所以尋找第一個(gè)結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)所花費(fèi)的時(shí)間不等。

單鏈表的定義和表示

typedef struct LNode//聲明結(jié)點(diǎn)的類型和指向結(jié)點(diǎn)的指針類型
{
	ElemType date;//結(jié)點(diǎn)的數(shù)據(jù)域
	struct LNode *next;//結(jié)點(diǎn)的指針域
}LNode,*LinkList;//LinkList為指向結(jié)構(gòu)體LNode的指針類型

• 定義鏈表L:LinkList L;
• 定義結(jié)點(diǎn)指針p:LNode *p; 也可以LinkList p;
• 重要操作
  p指向頭結(jié)點(diǎn)： p=L;
  s指向首元結(jié)點(diǎn)： s=L->next;
  p指向下一個(gè)結(jié)點(diǎn)： p=p->next;

單鏈表基本操作的實(shí)現(xiàn)

單鏈表的初始化

• 即構(gòu)造一個(gè)空表
• 算法步驟
  （1）生成新結(jié)點(diǎn)做頭指針，用頭指針L指向頭結(jié)點(diǎn)。
  （2）將頭結(jié)點(diǎn)的指針域置空

判斷鏈表是否為空

• 空表：鏈表中無元素稱為空鏈表（頭指針和頭結(jié)點(diǎn)仍然存在）
• 算法思路
  判斷頭結(jié)點(diǎn)的指針域是否為空

單鏈表的銷毀

• 鏈表銷毀后不存在
• 算法思路
  從頭指針開始，依次釋放所有結(jié)點(diǎn)

清空鏈表

• 鏈表仍然存在，但鏈表中無元素，成為空鏈表（頭指針和頭結(jié)點(diǎn)仍然在）

• 算法思路
  依次釋放所有結(jié)點(diǎn)，并將頭結(jié)點(diǎn)指針域設(shè)置為空

求單鏈表的表長

• 算法思路
  從首元結(jié)點(diǎn)開始，依次計(jì)數(shù)所有結(jié)點(diǎn)

取值–取單鏈表中第i個(gè)元素的內(nèi)容

• 算法思路
  從鏈表的頭指針出發(fā)，順著鏈域next逐個(gè)結(jié)點(diǎn)往下搜索，直至搜索到第i個(gè)結(jié)點(diǎn)為止。因此，鏈表不是隨機(jī)存取結(jié)構(gòu)。

按值查找–根據(jù)指定數(shù)據(jù)獲取該數(shù)據(jù)所在的位置（地址）

• 算法步驟
  1、從第一個(gè)結(jié)點(diǎn)起，依次和e相比較
  2、如果找到一個(gè)其值與e相等的數(shù)據(jù)元素，則返回其在鏈表中的“位置”或地址
  3、如果查遍整個(gè)鏈表都沒有找到其值與e相等的元素，則返回0或者NULL；

插入–在第i個(gè)結(jié)點(diǎn)前插入值為e的新結(jié)點(diǎn)

• 算法步驟
  1、首先找到i-1個(gè)元素的存儲(chǔ)位置p
  2、生成一個(gè)數(shù)據(jù)域?yàn)閑的新結(jié)點(diǎn)s
  3、插入新結(jié)點(diǎn)：
  ①新結(jié)點(diǎn)的指針域指向結(jié)點(diǎn)i s->next=p->next;
  ②結(jié)點(diǎn)i-1的指針域指向新結(jié)點(diǎn) p->next=s;

刪除–刪除第i個(gè)結(jié)點(diǎn)

• 算法步驟
  1、首先找到第i-1的存儲(chǔ)位置p，保存要?jiǎng)h除的第i個(gè)元素的值
  2、令p->next指向原本第i+1個(gè)元素
  3、釋放原本第i個(gè)結(jié)點(diǎn)的空間

單鏈表的查找、插入、刪除算法的時(shí)間效率分析

• 1、查找：
  因線性鏈表只能順序存取，即在查找時(shí)要從頭指針找起，查找的時(shí)間復(fù)雜度為O(n)。
• 2、插入和刪除
  因線性鏈表不需要移動(dòng)元素，只要修改指針，一般情況下時(shí)間復(fù)雜度為為O(1)。
  但是，如果要在單鏈表中進(jìn)行前插或刪除操作，由于要從頭查找前驅(qū)結(jié)點(diǎn)，所耗時(shí)間復(fù)雜度為O(n)。

建立單鏈表：頭插法–元素插入在鏈表頭部，也叫前插法

• 算法步驟
  1、從一個(gè)空表開始，重復(fù)讀入數(shù)據(jù)
  2、生成新結(jié)點(diǎn)，將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中
  3、從最后一個(gè)結(jié)點(diǎn)開始，依次將各結(jié)點(diǎn)插入到鏈表的前端

建立單鏈表：尾插法–元素插入在鏈表尾部，也叫后插法

• 算法步驟
  1、從一個(gè)空表L開始，將新結(jié)點(diǎn)逐個(gè)插入到鏈表的尾部，尾指針r指向鏈表的尾結(jié)點(diǎn)。
  2、初始時(shí)，r同L一起指向頭結(jié)點(diǎn)，每讀入一個(gè)數(shù)據(jù)元素則申請(qǐng)一個(gè)新結(jié)點(diǎn)，將新結(jié)點(diǎn)插入到尾結(jié)點(diǎn)后，r指向新結(jié)點(diǎn)

#include<iostream>
using namespace std;

typedef struct student {
	int id;
	struct student* next;
}LNode,*linklist;

int InitList(linklist& L)//初始化一個(gè)空鏈表-
{
	L = new LNode;//或L=(linklist)malloc(sizeof(LNode));
	L->next = NULL;
	return 0;
 }

int ListEmpty(linklist L)//判斷是否為空
{
	if (L->next == NULL)//為空
		return 0;
	else
		return 1;
}

void DestroyList(linklist& L)//銷毀鏈表
{
	LNode* p;
	
	while (L)
	{
		p = L;//將p指向頭結(jié)點(diǎn)
		L = L->next;//指向下一個(gè)
		delete p;
	}
}

void ClearList(linklist& L) //清空鏈表
{
	LNode* p, * q;
	p = L->next;//p指向首元結(jié)點(diǎn)
	while (p)//沒到表尾
	{
		q = p->next;//q指向p的下一個(gè)結(jié)點(diǎn)
		delete p;//釋放p
		p = q;//p指向下一個(gè)結(jié)點(diǎn)
	}
	L->next = NULL;//將頭結(jié)點(diǎn)的指針域置空
}

int ListLength(linklist L)//獲取鏈表長度
{
	linklist p;
	p = L->next;//p指向第一個(gè)結(jié)點(diǎn)
	int i = 0;
	while (p)//遍歷單鏈表，統(tǒng)計(jì)結(jié)點(diǎn)數(shù)
	{
		i++;
		p = p->next;
	}
	return i;//返回統(tǒng)計(jì)的個(gè)數(shù)i
}

int GetElem(linklist L, int i, int& e)//獲取鏈表中某個(gè)位置的元素
{
	LNode* p;
	p = L->next;//p指向首元結(jié)點(diǎn)
	int j = 1;//初始化
	while (p && j < i)//向后掃描，直到p指向第i個(gè)元素或者p為空
	{
		p = p->next;
		++j;
	}
	if (!p || j > i)//第i個(gè)元素不存在
		return -1;
	e = p->id;//取第i個(gè)元素的數(shù)據(jù)域的值
	return 1;
}

LNode* LocateElem(linklist L, int e)//查找某個(gè)元素的地址
{
	LNode* p;
	p = L->next;//p指向首元結(jié)點(diǎn)
	while (p && p->id != e)//沒到尾部并且沒找到值為e的結(jié)點(diǎn)
	{
		p = p->next;
	}
	return p;//返回找到的結(jié)點(diǎn)
}

int LocateELem(linklist L, int e)//根據(jù)指定數(shù)據(jù)查看該數(shù)據(jù)的位置序號(hào)
{
	LNode* p;
	p = L->next;//p指向首元結(jié)點(diǎn)
	int j = 1;//初始化計(jì)數(shù)變量
	while (p && p->id != e)//未到尾部且未找到值為e的結(jié)點(diǎn)
	{
		p = p->next;
		j++;
	}
	if (p)
		return j;//找到返回位置序號(hào)
	else
		return 0;//沒找到返回0

}

int ListInsert(linklist& L, int i, int e)//在指定位置插入數(shù)據(jù)
{
	linklist p = L;//將p指向頭結(jié)點(diǎn)
	int j = 0;//初始化計(jì)數(shù)參數(shù)
	while (p && j < i - 1)//尋找第i-1個(gè)結(jié)點(diǎn)，p指向i-1個(gè)結(jié)點(diǎn)
	{
		p = p->next;
		++j;
	}
	if (!p || j > i-1)//i大于表長+1或者小于1，插入位置非法
		return -1;
	else
	{
		linklist s;
		//InitList(s);
		s = new LNode;//生成新結(jié)點(diǎn)s
		s->id = e;//將結(jié)點(diǎn)s的數(shù)據(jù)域置為e
		s->next = p->next;
		p->next = s;
		return 1;
	}
	
}

int ListDelete(linklist& L, int i,int &e)//刪除第i個(gè)位置的元素
{
	linklist p= L;
	//InitList(p);
	//p = L;
	int j = 0;//初始化計(jì)數(shù)變量
	while (p->next && j < i - 1)//尋找第i個(gè)結(jié)點(diǎn)，并使p指向其前驅(qū)，p指向第i-1個(gè)結(jié)點(diǎn)
	{
		p = p->next;
		++j;
	}
	if (!(p->next) || j > i - 1)//刪除位置不合理
	{
		return -1;
	}
	linklist q;
	q = p->next;//q指向第i個(gè)結(jié)點(diǎn)，臨時(shí)保存被刪結(jié)點(diǎn)的地址以備釋放

	p->next = q->next;//改變刪除結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)的指針域
	e = q->id;//保存刪除結(jié)點(diǎn)的數(shù)據(jù)域
	delete q;//釋放刪除結(jié)點(diǎn)的空間
	return 1;
}

void CreateListHead(linklist& L, int n)//頭插
{
	InitList(L);//先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表
	for (int i = n; i > 0; i--)
	{
		linklist p;//生成新結(jié)點(diǎn)p
		p = new LNode;
		cin >> p->id;//輸入元素值scanf(&p->id)
		p->next = L->next;//插入到表頭
		L->next = p;
	}
}

void CreateListTail(linklist& L, int n)//尾插
{
	InitList(L);
	LNode* r;//新建一個(gè)尾指針r
	r = L;//將其指向頭結(jié)點(diǎn)
	for (int i = 0; i < n; ++i)
	{
		LNode* p;
		p = new LNode;//生成新結(jié)點(diǎn)
		cin >> p->id;//輸入元素值
		p->next = NULL;//將新插入的結(jié)點(diǎn)的指針域置空
		r->next = p;//插入到末尾
		r = p;//r指向新的尾結(jié)點(diǎn)
	}
}

void DeleteLinkList(LinkList& L, int e)//刪除單鏈表中某個(gè)元素為e的所有結(jié)點(diǎn)
{
    Lnode* p, * q;//定義一前一后兩個(gè)指針
    p = new Lnode;
    q = new Lnode;
    p = L->next;//p指向首元結(jié)點(diǎn)
    q = L;//q指向頭結(jié)點(diǎn)
    while (p)//未到末尾
    {
        if (p->date == e)//查看是否為e
        {
            q->next = p->next;//用q暫存p的下一個(gè)結(jié)點(diǎn)的地址
            free(p);//釋放
            p = q->next;//將p從刪除結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)指向后面一個(gè)
        }
        q = p;//讓q指向p
        p = p->next;//p后移一個(gè)
    }
}

void PrintLinkList(LinkList L)//輸出單鏈表中的值
{
    Lnode* p;
    p = new Lnode;
    p = L->next;//將p指向首元結(jié)點(diǎn)
    while (p)//非空
    {
        cout << p->date << " ";
        p = p->next;
    }
}

int main()
{
	linklist L;
	InitList(L);
	int i=ListLength(L);
	cout <<"插入前元素個(gè)數(shù)為：" << i << endl;

	CreateListHead(L, 6);
	i = ListLength(L);
	cout << "頭插后元素個(gè)數(shù)為：" << i << endl;

	cout << "頭插后元素遍歷：" << " ";
	for (int j = 1; j < 7; j++)
	{
		int e_id;
		GetElem(L, j,e_id);
		cout << e_id << " ";
	}
	cout << endl;

	ClearList(L);

	CreateListTail(L, 5);
	i = ListLength(L);
	cout << "尾插后元素個(gè)數(shù)為：" << i << endl;

	cout << "尾插后元素遍歷：" << " ";
	for (int j = 1; j < 6; j++)
	{
		int e_id;
		GetElem(L, j, e_id);
		cout << e_id << " ";
	}
	cout << endl;

	ListInsert(L, 3, 89);

	for (int j = 1; j < 7; j++)
	{
		int e_id;
		GetElem(L, j, e_id);
		cout << e_id << " ";
	}
	cout << endl;

	int e_IDD;
	int result=ListDelete(L, 2, e_IDD);

	cout << "result=" << result << endl;
	for (int j = 1; j < 7; j++)
	{
		int e_id;
		GetElem(L, j, e_id);
		cout << e_id << " ";
	}
	cout << endl;

	return 0;
}

其它鏈表

循環(huán)鏈表

• 是一種頭尾相接的鏈表（即：表中最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)）。
• 優(yōu)點(diǎn)：從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其它結(jié)點(diǎn)。
• 注意：
  由于循環(huán)鏈表中沒有NULL指針，故涉及遍歷操作時(shí)，其終止條件就不再像非循環(huán)鏈表那樣判斷p或者p->next是否為空，而是判斷它們是否等于頭指針。
  循環(huán)條件 p!=L 或 p->next!=L
• 注意：表的操作常常是在表的首尾位置上進(jìn)行。

帶尾指針的循環(huán)鏈表合并（將Tb合并在Ta之后）

• 步驟：
  1、p存表頭節(jié)點(diǎn) p=Ta->next;
  2、Tb表頭連接到Ta表尾 Ta->next=Tb->next->next;
  3、釋放Tb表頭結(jié)點(diǎn) delete Tb->next;
  4、修改指針 Tb->next=p;

//帶尾指針的循環(huán)鏈表合并（將Tb合并在Ta之后）
linklist Connect(linklist Ta, linklist Tb)//假設(shè)Ta,Tb都是非空的單循環(huán)鏈表
{
	LNode* p;
	p = Ta->next;//p存表頭節(jié)點(diǎn)
	Ta->next = Tb->next->next;//Tb表頭連接到Ta表尾
	delete Tb->next;//釋放Tb表頭結(jié)點(diǎn) 
	Tb->next = p;//修改指針
	return Tb;
}

雙向鏈表

• 在單鏈表的每個(gè)結(jié)點(diǎn)里再增加一個(gè)指向其直接前驅(qū)的指針域prior，這樣鏈表中就形成了有兩個(gè)方向不同的鏈，故稱為雙向鏈表
• 定義

typedef struct DulNode
{
	Elemtype date;//Elemtype是數(shù)據(jù)類型
	struct DulNode* prior, * next;
}DulNode,*DuLinkList;

雙向循環(huán)鏈表

• 和單鏈的循環(huán)鏈表類似，雙向鏈表也可以有循環(huán)表
  （1）讓頭結(jié)點(diǎn)的前驅(qū)指針指向鏈表最后一個(gè)結(jié)點(diǎn)
  （2）讓最后一個(gè)結(jié)點(diǎn)的后繼指針指向頭結(jié)點(diǎn)

雙向鏈表結(jié)構(gòu)的對(duì)稱性

• 設(shè)p指向某一結(jié)點(diǎn)p->prior->next=p=p->next->peior
• 在雙向鏈表中有些操作，因?yàn)閮H涉及一個(gè)方向的指針，故他們的算法和線性鏈表的相同。但在插入、刪除時(shí)，則需要修改兩個(gè)方向上的指針，兩者的操作時(shí)間復(fù)雜度均為O(n)。

雙向鏈表的插入

int ListInsertDul(DuLinkList& L, int i, Elemtype e)//在帶頭結(jié)點(diǎn)的雙向鏈表L中第i個(gè)位置之前插入元素e
{
	DuLinkList p;
	if (!(p = GetElemDul(L, i)))//找到第i個(gè)元素，將p指向它，若沒找到，返回-1
		return -1;
	
	DuLinkList s;
	s = new DulNode;//新建一個(gè)結(jié)點(diǎn)
	s->date = e;//給新結(jié)點(diǎn)數(shù)據(jù)域賦值
	s->prior = p->prior;
	p->prior->next = s;
	s->next = p;
	p->prior = s;
	return 1;
}

雙向鏈表的刪除

int ListDeleteDul(DuLinkList& L, int i, Elemtype& e)//刪除帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表L的第i個(gè)元素，并用e返回
{
	DuLinkList p;
	if (!(p = GetElemDul(L, i)))//找到第i個(gè)元素，將p指向它，若沒找到，返回-1
		return -1;
	e = p->date;//將要?jiǎng)h除的結(jié)點(diǎn)的數(shù)據(jù)域保存到e中
	p->prior->next = p->next;
	p->next->prior = p->prior;
	free(p);//釋放結(jié)點(diǎn)
	return 1;
}

總結(jié)

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)

• 結(jié)點(diǎn)空間可以動(dòng)態(tài)申請(qǐng)和釋放
• 數(shù)據(jù)元素的邏輯次序靠結(jié)點(diǎn)的指針來顯示，插入和刪除時(shí)不需要移動(dòng)數(shù)據(jù)元素

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的缺點(diǎn)

• 存儲(chǔ)密度小，每個(gè)結(jié)點(diǎn)的指針域需要額外占用內(nèi)存空間，當(dāng)每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域所占字節(jié)不多時(shí)，指針域所占用的存儲(chǔ)空間的比重顯得很大。
• 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是非隨機(jī)存儲(chǔ)結(jié)構(gòu)。對(duì)于任一結(jié)點(diǎn)的操作都要從頭指針依指針鏈查找到該結(jié)點(diǎn)，這增加了算法的復(fù)雜度

存儲(chǔ)密度

• 是指結(jié)點(diǎn)數(shù)據(jù)本身所占的存儲(chǔ)量和整個(gè)結(jié)點(diǎn)結(jié)構(gòu)中所占存儲(chǔ)量之比，即
  存儲(chǔ)密度=結(jié)點(diǎn)數(shù)據(jù)本身占用的空間/結(jié)點(diǎn)占用的空間總量
• 一般的，存儲(chǔ)密度越大，存儲(chǔ)空間的利用率就越高。顯然，順序表的存儲(chǔ)密度為1（100%），而鏈表的存儲(chǔ)密度小于1

單鏈表、循環(huán)鏈表和雙向鏈表的時(shí)間效率比較

順序表和鏈表的比較
文章來源地址http://www.zghlxwxcb.cn/news/detail-734920.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)-線性表的鏈?zhǔn)酱鎯?chǔ)（包含代碼實(shí)現(xiàn)）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！