今天將給大家講述鏈表的學習心得。學習數據結構，毋庸置疑鏈表必須學好，後面的棧、隊列、樹、圖都是以鏈表為基礎的；鏈表的種類很多，有單鏈表、雙鏈表、循環鏈表、非循環鏈表；在此，我們以非循環單鏈表為例，來講鏈表的創建、求長度、排序、插入和排序。

1.什麼是鏈表

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

（1）.由n個節點離散分配；

（2）.每個節點通過指針連接

（3）每一個節點由一個前驅節點和一個後驅節點

（4）.首節點沒有前驅節點，尾節點沒有後驅節點；

滿足上面的4條，我們就稱為鏈表；鏈表既然由很多個節點，那節點又由什麼組成？節點由兩個部分組成，一是數據域，用來存放有效數據；二是指針域，用來指向下一個節點；下面用C語言來構建鏈表數據結構，首先應該構造出節點，然後再把所有的節點連起來，就構成了鏈表；

（1）節點的構造

typedef struct Node
{
	int data;//數據域，用來存放數據域；
	struct Node *pNext;//定義一個結構體指針，指向下一次個與當前節點數據類型相同的節點 

}NODE,*PNODE; //NODE等價於 struct Node; PNODE等價於struct Node *； 此處用大寫是為了與變量區分，可以讓人容易變出是個數據類型

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

（2）鏈表的創建

在創建鏈表之前，我們需要需要了解一下專業術語：

首節點：存放第一個有效數據的節點；

尾節點：存放最後一個有效數據的節點；

頭節點：頭節點的數據類型與首節點的數據類型相同，並且頭節點是首節點前面的那個節點，並不存放有效數據；頭節點的存在只是為了方便鏈表的操作。

頭指針：指向頭節點的指針；

尾指針：指向尾節點的指針；

首先，我們應該創建一個頭節點，並用頭指針指向它，用C語言描述：用malloc向計算機申請一塊內存，並定義一個指向與頭節點數據類型相同的指針（一定要判斷申請內存是否成功）；

然後，要知道要創建鏈表的長度，用一個循環來每次創建一個節點，並把每個節點連在一起；

假如我們要在頭節點phead後面插入節點p：

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

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

這樣就可以了嗎？ 想想我們就可以發現，當我們要插入多個節點時，頭節點始終指向最後添加的一個數據，以前的節點通過頭指針此時已經找不到了；我們定義一個尾指針pTail，始終用來指向鏈表的結尾，每次只在pTail後面添加節點。

偽算法：

（1）定義一個尾指針pTail，並初始化，使它指向頭節點，即pTail=pHead；

（2）在pTail後面添加節點，修改指針：

pTail->pNext=p;

p->pNext=NULL;

pTail=p; //使pTail指向鏈表最後一個元素

PNODE Create_List(void)
{
	int len; //存放鏈表的長度 

	int i; //循環變量
	int val;//用來臨時存放用戶輸入的結點的值
	PNODE List;
	PNODE pHead=(PNODE)malloc(sizeof(NODE));//分配一個頭節點
	if(NULL==pHead)
	{
		printf("Memory allocation failure");
		exit(-1);
	}
	else
	{ PNODE pTail=pHead;
		pHead->pNext=NULL; 
		printf("please input the length of list: "); //需要一個指針始終指向鏈表的結尾
		scanf("%d",&len);
		for(i=0;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.向鏈表中插入元素

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

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

（2）q->pNext=p;

程序代碼如下：

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

 
}

3.刪除鏈表中的元素

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

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

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

（3）free(q); //釋放節點2所佔的內存；

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

4.鏈表元素的排序

快速排序和冒泡排序的思想對於鏈表這個數據結構同樣適用，下面是一個用選擇排序來實現鏈表的排序；

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

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

和數組排序很像，只是這裡需要兩個指針p、q不停地移動，來獲取鏈表中的數據元素；

寫在最後

喜歡此篇文章或覺得這篇文章對你有幫助的讀者可以點播關注或者轉發，私信小編001即可獲得小編自己整理的一份2018最新的C/C++資料和0基礎入門教程，歡迎初學和進階中的小夥伴

閱讀更多 ccc雲志 的文章

關鍵字: 節點 鏈表 C語言