791      阿裏雲  技術社區[雲棲]

[C/C++基礎知識] 那些被遺忘的鏈表知識

最近快畢業了,複試又複習了一些知識.其中就包括那些被遺忘的鏈表知識,而它又是C語言中非常重要一個知識點.同時發現很多同學都會忘記該知識,所以通過這篇文章一方麵幫助大家回憶鏈表知識,同時對剛接觸C語言的同學也有幫助.我采用問答的方式回顧那些知識,希望能接受!
提示:該文章引用李鳳霞(北理)的《C語言程序設計教程》及課件和譚浩強(清華)的《C程序設計》.

一.鏈表基本概念

1.什麼是鏈表?
鏈表是一種常見的動態進行存儲分配的數據結構.
2.為什麼會出現鏈表這種結構呢?
(1).C語言中使用數組存放數據時,須先定義固定數組長度,確定元素個數.如果數據超過其容量就會發生數組溢出;為防止該溢出,往往會定義很大的數組,但這樣又造成資源空間浪費.如果程序采用動態數組方法複製增長的數據,方法可行但效率太低;
(2).如果在數組中需要刪除一個數據或插入一個數據時,此時需要將刪除或插入點數組後麵的數據依次移動,這樣的移動也會導致程序效率非常低.
3.此時,鏈表這種動態存儲數據的結構油然而生.你是否看到了數組與鏈表兩者一些簡單區別呢?那麼鏈表的基本單位又是什麼呢?
結點是鏈表的基本存儲單位,在鏈表中所有元素都存儲在一個具有相同數據結構的結點中.一個結點對應一組數據元素,每個結點在內存中使用一塊連續的存儲空間(一個結點可由多種數據域組成),每個結點之間使用不連續的存儲空間,結點之間通過指針鏈接.結點由數據域和指針域/鏈組成.常用定義如下:

struct node
{
	dadatype data;         //數據域
	struct node *next;     //指針域:指向node結點指針
};

4.知道了鏈表的基本存儲單位後,那鏈表的基本組成部分是什麼呢?
鏈表一般由三部分組成:
(1).表頭指針:指向鏈表頭結點的指針,頭指針是鏈表的標誌,通常用head定義頭指針;
(2).表頭結點:鏈表的第一個結點,一般不保存數據信息.鏈表中可沒有表頭結點(後麵講述),它是為方便引入結點.
(3).數據結點:實際保存數據信息的結點.示意圖如下:

5.前麵講到可能鏈表中沒有表頭結點,那麼鏈表常見形式有哪些呢?
常見的形式包括:有表頭結點的單向鏈表、無表頭結點的單向鏈表、有表頭的單向循環表、無表頭的單向循環表.其中有表頭與無表頭的差別在於是否有表頭結點,插入刪除操作對應不同的判斷;單向鏈表與單向循環鏈表的區別在於最後一個數據結點指針是NULL還是指向表頭結點.雙向鏈表即兩個指針分別指向前一個位置和後一個位置的鏈表.

6.那麼鏈表中的常見操作包括哪些呢?
鏈表的常見操作包括:建立鏈表、遍曆鏈表、求鏈表表長、插入數據、刪除結點.下麵將詳細解決.

二.鏈表基本操作

1.建立鏈表
建立鏈表前先定義一個包含數據域與指針域的結構類型,然後建立指向表頭結點的頭指針head,通過malloc函數動態申請內存作為表頭結點.其中void *malloc(int size)的頭文件為"stdlib.h".動態分配長度size字節存儲區.

//定義結構類型
typedef struct node
{
	char name[20];              //數據域
	struct node *next;          //指針域
}NODE;
NODE *head,*p;                  //說明指針
//建立空鏈表(僅表頭結點)
p=(NODE *)malloc(sizeof(NODE));
p->next=NULL;
head=p;
//插入一個數據結點
p=(NODE *)malloc(sizeof(NODE));
gets(p->name);                   //輸入姓名
p->next=head->next;              //p指向下一個結點=head指向下一個及誒單
head->next=p;                    //p結點插入表頭結點head後

//建立n個結點的鏈表
void create(NODE *head,int n)
{
	NODE *p;
	for(;n>0;n--)
	{
		p=(NODE *)malloc(sizeof(NODE));
		gets(p->name);
		p->next=head->next;
		head->next=p;
	}
}

//遍曆輸出結果
void output(NODE *head)
{
	NODE *p;
	p=head->next;     //含表頭結點
	while(p!=NULL)
	{
		puts(p->name);
		p=p->next;
	}
}

//計算鏈表長度
int count(NODE *head)
{
	int number=0;
	NODE *p;
	p=head->next;
	while(p!=NULL)
	{
		number++;
		p=p->next;
	}
	return number;
}

自定義main函數調用其函數,程序測試結果如下圖所示,是不是反序一目了然.

3.插入數據
在鏈表中第i個結點後麵插入一個新節點的算法如下:
(1).定位第i個結點.讓指針q指向第i個結點,指針p指向要插入的結點.
(2).鏈接後麵的指針:p->next=q->next.
(3).鏈接前麵指針:q->next=p.
如下圖所示過程:

具體代碼如下圖所示,其中采用insert函數插入新結點時,可能遇到兩種特殊情況:其一是向空表中插入新節點,其二是向鏈表最後一個元素後麵插入一個新結點.

//插入新結點 head頭指針 p插入指針 i位置
void insert(NODE *head,NODE *p,int i)
{
	NODE *q;
	int n = 0;
	q = head;
	//第一步 尋找到第i個結點位置
	while(n<i&&q->next!=NULL)
	{
		q = q->next; n++;
	}
	//第二步 鏈接後麵的指針
	p->next = q->next;
	//第三步 鏈接前麵的指針
	q->next = p;
}

4.刪除數據
在鏈表中可以刪除任意一個數據結點,其中刪除鏈表中第i個結點的算法如下:
(1).定位第i-1個結點位置.指針q指向第i-1個結點,指針p指向被刪除結點.
(2).摘鏈:q->next=p->next.
(3).釋放結點p:free(p).
其中void free(void *p)釋放p所指向的內存空間,頭文件為"stdlib.h".如下圖所示:

具體代碼如下圖所示,同時通常在刪除結點p後,需要把q指向的下一個新的結點賦值為p,可以繼續執行刪除操作.

//刪除第i個結點
void delete_node(NODE *head,int i)
{
	NODE *q,*p;
	int n = 0;
	q = head;
	//第一步 尋找到第i-1個結點位置 q指針指向
	while(n<i-1&&q->next!=NULL)
	{
		q = q->next;
		n++;
	}
	if(q->next!=NULL)
	{
		//第二步 摘鏈 q指向p的下一個結點
		p = q->next;
		q->next = p->next;
		//第三步 釋放結點
		free(p);
	}
}

希望讀者思考一個問題,在刪除結點時,如果鏈指針摘鏈操作後沒有free釋放掉該結點,會導致什麼結果呢?如果你學過C++或Jave,你又能回憶起它的內存管理和泄露知識嗎?

三.鏈表經典問題-約瑟夫循環問題

通過上麵對鏈表的講述,你是否能回憶起一些它的簡單知識呢?下麵我想通過鏈表知識中最經典的題目"約瑟夫循環問題"讓我們看看鏈表如何在實例中應用.
題目:有N個孩子圍成一圈並依次編號(從1起),老師指定從第M個孩子開始報數,當報到第S個孩子時出列,然後下一個孩子從1開始繼續報數,依次出列.求孩子出列的順序或求最後一個孩子的編號.
輸入:輸入n(孩子個數),m(開始報數編號),s(報s出列).
輸出:孩子出列順序或最後一個孩子編號.
分析:如下圖所示,當輸入n=5,m=2,s=3時表示總共有5個孩子,通過單向循環鏈表圍成一圈,m=2表示從第二個孩子開始報數,第二個孩子報數1,第三個報數2,第四個孩子報數3(s=3)出列.依次出列順序為:4-2-1-3-5.

完成該程序需要:
(1).建立單向循環鏈表.注意此時建表是順序建立,前麵講述的在head後插入新結點為逆序建表.此時需要依次插入head->a1->a2.最後在讓q->next=head構建循環鏈表.(代碼無表頭結點)
(2).通過循環找到開始報數的結點,p指向開始報數的結點,q指向其前一個結點,因為刪除p時需要通過前一個結點q摘鏈.
(3).循環依次報數刪除結點,知道p=p->next退出循環,此時僅剩最後一個結點.

#include<stdio.h>
#include<stdlib.h>

//定義結構
typedef struct node
{
	int no;
	struct node * next;
}NODE;

int main()
{
	int i,j,k;
	int n,m,s;            //n個孩子 從m個開始報數 s個出列
	NODE *head,*p,*q;     //頭結點 p插入結點 q插入前一個結點
	printf("請輸入數字:\n");
	scanf("%d %d %d",&n,&m,&s);

	//建表 順序插入無表頭單向循環鏈表
	head=NULL;
	for(i=1;i<=n;i++)   //i存儲序列號
	{
		p=(NODE*)malloc(sizeof(NODE));
		p->no=i;
		if(head==NULL) head=p;        //第一個結點存入head
		else q->next=p;               //q鏈接新插入結點p
		q=p;                          //新插入結點構成鏈尾
	}
	q->next=head;                     //鏈尾鏈接鏈頭構成循環

	//尋找輸出的位置m p為開始的結點 q為其前麵一個結點
	q=head;
	p=head;
	for(k=1;k<m;k++)                  //如果m=1 即第一個位置
	{
		p=p->next;
	}
	while(q->next!=p)                 //尋找q指針 q為p的前一個結點
	{
		q=q->next;
	}

	//刪除結點及輸出
	printf("輸出刪除結點順序:\n");
	while(p->next!=p)
	{
		//尋找到要刪除結點位置
		for(j=1;j<s;j++)
		{
			q=p;
			p=p->next;	
		}
		//輸出結點並刪除
		printf("%d ",p->no);
		q->next=p->next;
		free(p);
		p=q->next;
	}
	printf("\n最後剩餘結點:%d\n",p->no);
	system("PAUSE");
	return 0;
}

測試用例及輸出結果如下所示:
(1).輸入n=5 m=2 s=3

(2).輸入n=35 m=5 s=3

如果你是一位剛接觸C語言的同學,希望文章能令你對鏈表有些認識;
如果你是考研或找工作的同學,希望對你在麵試題或考研題中有所幫助;
如果你對鏈表有很深入的認識,希望當你閱讀該文章時能對我這樣的年輕人慧心一笑;
最後希望該文章對大家有所幫組,同時如果文章中有錯誤或不足之處,還請海涵!同時感謝母校BIT及老師,四年轉瞬即逝,還有很多知識需要學習.這篇文章僅僅是自己對鏈表知識的一些總結及在線筆記,請尊重作者的勞動果實!
(By:Eastmount 2014-3-28 夜2點 原創CSDNhttps://blog.csdn.net/eastmount/)

最後更新：2017-04-03 12:55:52

  上一篇： 位運算

  下一篇： HdfsSink原理解析