資料結構（一）—鏈表-有解無憂

一、背景
二、鏈表概念及特點
- 概念
- 適用場合
- 基本操作
- 分類
三、單鏈表的實作

一、背景

作為機械狗轉行，資料結構當然是不可缺少的，疫情假期里閑來在家無事，剛好接下給小孩教資料結構的活，所以自學了簡單的資料結構用法，算是資料結構的入門吧，做個筆記記下來，其實平常喜歡用思維導圖進行記錄，這算復習一遍，所以再用MarkDown進行記錄，順便發個博，

話不多說，今天先來記錄一下鏈表簡單的概念、實作等，

二、鏈表概念及特點

概念

鏈表是物理存盤單元上非連續的、非順序的存盤結構，它是由一個個結點，通過指標來聯系起來的，其中每個結點包括資料和指標，

適用場合

大記憶體空間分配
元素頻繁洗掉和插入
若資料以查找為主，很少涉及增刪，則選擇陣列

基本操作

書上主要都是利用抽象資料型別進行定義的，我這里直接用大白話，最終目的還是要理解每種資料結構的特點及實作，

初始化
插入
洗掉
查詢
取值

三、單鏈表的實作

本文只先實作單鏈表，利用C++編碼，鏈表這里的代碼加了一些自己的方法和書本的不完全一樣，直接上碼，注意主函式的呼叫在最后哦，

單鏈表的存盤結構及初始化鏈表

首先是定義單鏈表的存盤結構及初始化鏈表：

#include<iostream>
using namespace std;

//單鏈表的存盤結構
typedef char ElemType; //存盤元素型別
typedef struct LNode
{
	ElemType data;//結點資料域
	struct LNode *next;//結點指標域，指向下一結點
}LNode,*LinkList;//LinkList為指向結構體LNode的指標型別

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

? 注意我們這里的頭結點是一直不用的結點，資料域不存資料，第一個資料存到的是首元結點，不要混淆，如下圖：

? OK，這三個概念不要搞混淆，繼續下一步，

創建單鏈表

創建單鏈表，創建單鏈表又可以分為前插法和后插法，顧名思義，就是在鏈表頭結點后插入新結點，還是鏈表尾部插入新結點，

//創建單鏈表
//前插法
void CreateList_H(LinkList &L,int n)
{//這里輸入一個n，限定了鏈表的長度，可以不這么做，利用其它方式停止鏈表插入，
 //這里為了方便展示頭插法的演算法邏輯，因此不必在意這點
	InitList(L);//先建立一個帶頭結點的空鏈表
	for(int i;i<n;i++)
	{
		LNode *p=new LNode;//生成新結點*p
		cin>>p->data;//輸入資料
		p->next=L->next;//令新結點指標域指向原首元結點
		L->next=p;//令頭結點指向新結點
	} 
}

//尾插法
void CreateList_R(LinkList &L,int n)
{
	InitList(L);//先建立一個帶頭結點的空鏈表
	LNode *r=L;//臨時指標r指向頭結點
	for(int i=0;i<n;i++)
	{
		LNode *p=new LNode;//生成新結點
		cin>>p->data;//輸入資料，填充資料域
		p->next=NULL;//新結點指標域初始化為NULL
		r->next=p;//將新結點*p插入尾結點 r->next后
		r=p; //令r指向新的尾結點p
	} 
}

插入

下面我們來實作鏈表在任意位置的插入，先拿一個圖來表示該插入程序，以便理解：

? ①查找第a_i-1個結點，并將指標p指向該結點；

? ②生成新結點*s；

? ③將新結點*s的資料域置為e；

? ④將新結點*s的指標域指向a_i;

? ⑤將結點p的指標域指向新結點s，

//單鏈表插入
//在帶頭結點的單鏈表L中第i個位置插入值為e的新結點
void ListInsert(LinkList &L,int i,ElemType e)
{
	LNode *p=L;
	int j=0;
	while(p!=NULL&&(j<i-1))
	{//查找第i-1個結點，令p指向該結點
		p=p->next;
		j++;
	}	
	if(p==NULL||j>i-1)
	{//這里判斷i值是否存在或合法，當i>n+1或者i<1時，i值非法
		cout<<"i值非法！"<<endl;
		return;
	}
	
	LNode *s=new LNode;//生成新結點*s
	s->data=https://www.cnblogs.com/gentlesunshine/p/e;//新結點資料域填充
	s->next=p->next;//將新結點的指標域指向p->next
	p->next=s;//p->next指向s
}

洗掉

洗掉元素，老樣子，先來個圖，

代碼如下：

//洗掉
//在單鏈表L中，洗掉第i個元素
void ListDelete(LinkList &L,int i)
{
	LNode *p=L;
	int j=0;
	while((p->next!=NULL)&&(j<i-1))
	{//查找第i-1個結點，p指向該結點
		p=p->next;
		j++;
	}
	if(p->next==NULL||(j>i-1))
	{//判斷i值是否合理，當i>n或i<1時，洗掉位置不合理
		cout<<"i值非法，洗掉失敗！"<<endl;
		return;
	}
	LNode *q=p->next;//臨時保存被刪結點，以備釋放
	p->next=q->next;//改變洗掉結點前驅結點的指標域
	delete q; //釋放洗掉結點的空間
}

取值和查找

取值和查找的就簡單了，來一起整，

//取值//在單鏈表L中根據序號i獲取元素的值
ElemType GetElem(LinkList &L,int i)
{
	int j=1;
	LNode *p=L->next;//初始化，p指向鏈表L的頭結點，計數器j初值賦為1
	while((p!=NULL)&&j<i)
	{//順著鏈表向后掃描，直到p為慷訓p指向第i個元素為止
		p=p->next;//p指向下一個結點
		j++;//計數器j++
	} 
	if(p==NULL||j>i)
	{//判斷i值是否合法，i>n或i<=0時，不合法
		cout<<"i值不合法！"<<endl;
		return NULL;
	}
	return p->data;//回傳元素
} 

//查找
//在單鏈表L中查找值為e的結點
LNode* LocateElem(LinkList &L,ElemType e)
{
	LNode *p=L->next;//初始化，令p指向頭結點
	while(p!=NULL&&p->data!=e)
	{//向后掃描，直到p為慷訓p指向結點的資料域為e
		p=p->next;
	} 
	return p;//查找成功回傳值為e的結點地址p，查找失敗則p為NULL
}

呼叫及鏈表列印

這里我們進行呼叫以上方法，進行測驗，同時列印穿件的鏈表，

//列印鏈表
void PrintList(LinkList &L)
{
	LNode *p=L->next;
	while(p!=NULL)
	{
		cout<<p->data<<"\t";
		p=p->next;
	}
	cout<<"\n";
}

int main()
{
	LinkList L1;
	int n;
	cout<<"請輸入鏈表元素數量"<<endl; 
	cin>>n;
	CreateList_R(L1,n);//后插法創建鏈表
	PrintList(L1);//列印鏈表
	ListDelete(L1,2);//鏈表洗掉第2個元素
	PrintList(L1);//列印鏈表
	ListInsert(L1,3,'z');
	PrintList(L1);
	return 0;
}

以上代碼測驗結果如下：

OK，以上查找和查詢功能大家可以自己去測驗，應該都是沒問題的，

歡迎大家留言討論，轉載請注明原文地址就好喲yo~

參考參考：

《資料結構（C語言版第2版）》，好書啊，推薦入門小白去看~例如我，哈哈哈，

寫文不易~因此做以下申明：

1.博客中標注原創的文章，著作權歸原作者煦陽（本博博主）所有；

2.未經原作者允許不得轉載本文內容，否則將視為侵權；

3.轉載或者參考本文內容請注明來源及原作者；

4.對于不遵守此宣告或者其他違法使用本文內容者，本人依法保留追究權等，

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/73564.html

標籤：其他

上一篇：判斷括號是否有效(c++描述)

下一篇：泰迪杯

資料結構（一）—鏈表

一、背景

二、鏈表概念及特點

概念

適用場合

基本操作

分類

三、單鏈表的實作