https://www.toutiao.com/a6598287148695159303/

今天將給大家講述鏈表的學(xué)習心得。學(xué)習數據結構，毋庸置疑鏈表必須學(xué)好，后面的棧、隊列、樹(shù)、圖都是以鏈表為基礎的；鏈表的種類(lèi)很多，有單鏈表、雙鏈表、循環(huán)鏈表、非循環(huán)鏈表；在此，我們以非循環(huán)單鏈表為例，來(lái)講鏈表的創(chuàng )建、求長(cháng)度、排序、插入和排序。

1.什么是鏈表

鏈表我的理解要包含以下特征：

（1）.由n個(gè)節點(diǎn)離散分配；

（2）.每個(gè)節點(diǎn)通過(guò)指針連接

（3）每一個(gè)節點(diǎn)由一個(gè)前驅節點(diǎn)和一個(gè)后驅節點(diǎn)

（4）.首節點(diǎn)沒(méi)有前驅節點(diǎn)，尾節點(diǎn)沒(méi)有后驅節點(diǎn)；

滿(mǎn)足上面的4條，我們就稱(chēng)為鏈表；鏈表既然由很多個(gè)節點(diǎn)，那節點(diǎn)又由什么組成？節點(diǎn)由兩個(gè)部分組成，一是數據域，用來(lái)存放有效數據；二是指針域，用來(lái)指向下一個(gè)節點(diǎn)；下面用C語(yǔ)言來(lái)構建鏈表數據結構，首先應該構造出節點(diǎn)，然后再把所有的節點(diǎn)連起來(lái)，就構成了鏈表；

（1）節點(diǎn)的構造

typedef struct Node
{
	int data;//數據域，用來(lái)存放數據域；
	struct Node *pNext;//定義一個(gè)結構體指針，指向下一次個(gè)與當前節點(diǎn)數據類(lèi)型相同的節點(diǎn)
}NODE,*PNODE; //NODE等價(jià)于 struct Node; PNODE等價(jià)于struct Node *； 此處用大寫(xiě)是為了與變量區分，可以讓人容易變出是個(gè)數據類(lèi)型

typedef 只是給數據類(lèi)型取個(gè)別名，即 typedef 數據類(lèi)型 別名；我們知道struct Node 是我們定義的數據類(lèi)型；

（2）鏈表的創(chuàng )建

在創(chuàng )建鏈表之前，我們需要需要了解一下專(zhuān)業(yè)術(shù)語(yǔ)：

首節點(diǎn)：存放第一個(gè)有效數據的節點(diǎn)；

尾節點(diǎn)：存放最后一個(gè)有效數據的節點(diǎn)；

頭節點(diǎn)：頭節點(diǎn)的數據類(lèi)型與首節點(diǎn)的數據類(lèi)型相同，并且頭節點(diǎn)是首節點(diǎn)前面的那個(gè)節點(diǎn)，并不存放有效數據；頭節點(diǎn)的存在只是為了方便鏈表的操作。

頭指針：指向頭節點(diǎn)的指針；

尾指針：指向尾節點(diǎn)的指針；

首先，我們應該創(chuàng )建一個(gè)頭節點(diǎn)，并用頭指針指向它，用C語(yǔ)言描述：用malloc向計算機申請一塊內存，并定義一個(gè)指向與頭節點(diǎn)數據類(lèi)型相同的指針（一定要判斷申請內存是否成功）；

然后，要知道要創(chuàng )建鏈表的長(cháng)度，用一個(gè)循環(huán)來(lái)每次創(chuàng )建一個(gè)節點(diǎn)，并把每個(gè)節點(diǎn)連在一起；

假如我們要在頭節點(diǎn)phead后面插入節點(diǎn)p：

（1）把頭節點(diǎn)的指針域指向P節點(diǎn)，即pHead->pNext=p;

（2）把p節點(diǎn)的指針域指向NULL，即p->pNext=NULL;

這樣就可以了嗎？ 想想我們就可以發(fā)現，當我們要插入多個(gè)節點(diǎn)時(shí)，頭節點(diǎn)始終指向最后添加的一個(gè)數據，以前的節點(diǎn)通過(guò)頭指針此時(shí)已經(jīng)找不到了；我們定義一個(gè)尾指針pTail，始終用來(lái)指向鏈表的結尾，每次只在pTail后面添加節點(diǎn)。

偽算法：

（1）定義一個(gè)尾指針pTail，并初始化，使它指向頭節點(diǎn)，即pTail=pHead；

（2）在pTail后面添加節點(diǎn)，修改指針：

pTail->pNext=p;

p->pNext=NULL;

pTail=p; //使pTail指向鏈表最后一個(gè)元素

PNODE Create_List(void)
{
	int len; //存放鏈表的長(cháng)度
	int i; //循環(huán)變量
	int val;//用來(lái)臨時(shí)存放用戶(hù)輸入的結點(diǎn)的值
	PNODE List;
	PNODE pHead=(PNODE)malloc(sizeof(NODE));//分配一個(gè)頭節點(diǎn)
	if(NULL==pHead)
	{
		printf("Memory allocation failure");
		exit(-1);
	}
	else
	{ PNODE pTail=pHead;
		pHead->pNext=NULL; 
		printf("please input the length of list: "); //需要一個(gè)指針始終指向鏈表的結尾
		scanf("%d",&len);
		for(i=0;i<len;i++)
		{
		 PNODE p=(PNODE)malloc(sizeof(NODE));
		 if(NULL==p)
	 {
		 printf("Memory allocation failure");
		 exit(-1);
	 }
			else
			{ 
				printf("please input the value of list: ");
				scanf("%d",&val);
				p->data=val;
				pTail->pNext=p;
				p->pNext=NULL;
				pTail=p;
			}
 
		}
 
 
	}
	return pHead;
 
}

2.向鏈表中插入元素

假如要在節點(diǎn)2的前面插入節點(diǎn)p，我們首先要找到節點(diǎn)2的前驅節點(diǎn)1，假設現在q指針指向節點(diǎn)1，則

（1）p->pNext=q->pNext;

（2）q->pNext=p;

程序代碼如下：

//鏈表的第pos有效元素前面插入元素val，首先我們應該找到第pos個(gè)元素前面一個(gè)元素的位置；
//當鏈表有3個(gè)元素時(shí)，pos=4，將不會(huì )進(jìn)行插入操作
bool Insert_List(PNODE pHead,int pos,int val)
{
	int i=0;
	PNODE p=pHead;
	while((NULL!=p)&&(i<pos-1)) //
	{
		p=p->pNext;
		i++;
	}
	if(p==NULL||i>pos-1) //把鏈表為空的情況考慮進(jìn)去了；i>pos-1 可以防止用戶(hù)輸入錯誤；
		return false;
 
	//程序執行到這之后，i=pos-1；p指針指向鏈表第pos個(gè)有效節點(diǎn)的前驅?zhuān)粗赶虻趐os-1節點(diǎn)；
	PNODE q=(PNODE)malloc(sizeof(NODE));
	q->data=val;
	q->pNext=p->pNext;
	p->pNext=q;
 
 
}

3.刪除鏈表中的元素

假如要刪除節點(diǎn)2，只需要把節點(diǎn)1指針域指針指向節點(diǎn)3，但不要忘記釋放節點(diǎn)2所占的內存，否則將會(huì )造成內存泄漏；首先必須找到節點(diǎn)2的前驅節點(diǎn)1，假設p指向節點(diǎn)1。

（1）q=p->pNext; //首先用q保存要刪除節點(diǎn)的地址；

（2）p->pNext=q->pNext; //q->pNext=p->pNext->pNext; 修改指針使節點(diǎn)1指向節點(diǎn)3；

（3）free(q); //釋放節點(diǎn)2所占的內存；

bool Delete_List(PNODE pHead,int pos,int *val)
{
	int i=0;
	PNODE p=pHead;
	while((NULL!=p)&&(i<pos-1))
	{
		p=p->pNext;
		i++;
	}
	if(p==NULL||i>pos-1) //把鏈表為空的情況考慮進(jìn)去了；i>pos-1 可以防止用戶(hù)輸入錯誤；
		return false;
 
	//程序執行到這之后，i=pos-1；
	PNODE q=p->pNext; //q指向待刪除的節點(diǎn)；
	*val=q->data;
	p->pNext=q->pNext; //修改鏈表指針指向；
	free(q); //釋放q所指向節點(diǎn)的內存；
	q=NULL;//千萬(wàn)不可以忘記，否則會(huì )出現野指針；
}

4.鏈表元素的排序

快速排序和冒泡排序的思想對于鏈表這個(gè)數據結構同樣適用，下面是一個(gè)用選擇排序來(lái)實(shí)現鏈表的排序；

//鏈表有效元素的個(gè)數
int Length_List(PNODE pHead)
{ int len=0; //定義變量要記得初始化；
 PNODE p=pHead->pNext;
	while(NULL!=p)
	{
		len++;
		p=p->pNext;
	}
	return len;
 
}

//對鏈表中的元素進(jìn)行排序
void Sort_List(PNODE pHead)
{
	int i,j;
	int temp;
	int len=Length_List(pHead);
	PNODE p,q;//指向鏈表第一個(gè)有效元素
 
	for(i=0,p=pHead->pNext;i<len-1;i++,p=p->pNext)
	{
		for(j=i+1,q=p->pNext;j<len;j++,q=q->pNext)
		{
			//交換數據
			if(p->data>q->data)
			{
				temp=p->data;
				p->data=q->data;
				q->data=temp;
			}
		}
	}
}

和數組排序很像，只是這里需要兩個(gè)指針p、q不停地移動(dòng)，來(lái)獲取鏈表中的數據元素；

寫(xiě)在最后

喜歡此篇文章或覺(jué)得這篇文章對你有幫助的讀者可以點(diǎn)播關(guān)注或者轉發(fā)，私信小編001即可獲得小編自己整理的一份2018最新的C/C++資料和0基礎入門(mén)教程，歡迎初學(xué)和進(jìn)階中的小伙伴