C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)與算法之鏈表(一)

更新時(shí)間：2021年12月13日 14:09:23 作者：玄澈_

鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)方式。鏈表的內(nèi)存是不連續(xù)的，前一個(gè)元素存儲(chǔ)地址的下一個(gè)地址中存儲(chǔ)的不一定是下一個(gè)元素。小編今天就將帶大家深入了解一下鏈表，快來(lái)學(xué)習(xí)吧

引言

在存儲(chǔ)一大波數(shù)的時(shí)候，我們通常使用的是數(shù)組，但是數(shù)組有時(shí)候又會(huì)顯得不夠靈活，比如下面這個(gè)例子：

有一串已經(jīng)排序好的數(shù) 2，3，5，8，9 ，10

如果我們想要往數(shù)組中插入6 這個(gè)元素，需要把 8 以后的元素全部往后挪一位

這樣操作顯然很耗費(fèi)時(shí)間，如果使用鏈表的話則會(huì)快很多。那么什么是鏈表呢？請(qǐng)看下圖：

此時(shí)如果需要在8前面加入一個(gè)6，那么只需要向下圖一樣更改一下就可以了，而不用向像最開(kāi)始那樣把每個(gè)數(shù)向后挪。

鏈表的相關(guān)思考

為了實(shí)現(xiàn)鏈表這樣的數(shù)據(jù)結(jié)構(gòu)，我們需要使用指針和malloc這樣的函數(shù)。

注意： malloc 函數(shù)的返回值是 void * 類型，我們需要對(duì)其進(jìn)行強(qiáng)制類型轉(zhuǎn)換?

使用malloc時(shí)需要調(diào)用頭文件 <stdlib.h>

為什么我們要用這么復(fù)雜的辦法來(lái)儲(chǔ)存類型呢？

因?yàn)榘凑罩暗姆椒?，我們必須預(yù)先準(zhǔn)確地知道所需變量的個(gè)數(shù)，也就是說(shuō)我們必須我們必須定義出所有的變量。假如說(shuō)你現(xiàn)在定義了100個(gè)變量，而實(shí)際上則需要101個(gè)變量，那么就不得不對(duì)這個(gè)程序進(jìn)行修改。

而有了malloc函數(shù)，我們可以在程序運(yùn)行的過(guò)程中根據(jù)實(shí)際情況來(lái)申請(qǐng)空間。

鏈表結(jié)點(diǎn)結(jié)構(gòu)

每一個(gè)結(jié)點(diǎn)都由兩個(gè)部分組成。左邊的部分用來(lái)存放具體的值，那么用一個(gè)整型變量就可以；右邊的部分則需要儲(chǔ)存下一個(gè)點(diǎn)的地址，則可以用指針來(lái)實(shí)現(xiàn)（也稱為后繼指針）。

這里我們定義一個(gè)結(jié)構(gòu)體類型來(lái)存儲(chǔ)這個(gè)結(jié)點(diǎn)：

struct node
{
	int date;
	struct node* next;
};

因?yàn)橄乱粋€(gè)結(jié)點(diǎn)的類型也是 struct node ，所以我們指針的類型也必須是 struct node * 類型。

建立鏈表

首先，我們需要一個(gè)頭指針 head 指向鏈表的最開(kāi)始。當(dāng)鏈表還沒(méi)有建立的時(shí)候頭指針head為空（也可以理解指向空結(jié)點(diǎn)）。

struct node* head;
head = NULL;  //頭指針初始為空

現(xiàn)在，我們來(lái)創(chuàng)立第一個(gè)結(jié)點(diǎn)，并用臨時(shí)指針p指向這個(gè)結(jié)點(diǎn)

struct node* p;
//動(dòng)態(tài)申請(qǐng)一塊空間，用來(lái)存放一個(gè)結(jié)點(diǎn)，并用臨時(shí)指針p指向這個(gè)結(jié)點(diǎn)
p = (struct node*)malloc(sizeof(struct node));

接下來(lái)分別設(shè)置新建的結(jié)點(diǎn)的左半部分和右半部分

scanf("%d", &a);
p->date = a;	 //將數(shù)據(jù)存儲(chǔ)到當(dāng)前結(jié)點(diǎn)的date域中
p->next = NULL;  //設(shè)置當(dāng)前結(jié)點(diǎn)的后繼指針為空，也就是當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)為空

下面來(lái)設(shè)置頭指針并設(shè)置新創(chuàng)結(jié)點(diǎn)的 *next 指向空。頭指針的作用是方便以后從頭遍歷整個(gè)鏈表

if (head == NULL)
	head = p;  //如果這是第一個(gè)創(chuàng)建的結(jié)點(diǎn)，則將頭指針指向這個(gè)結(jié)點(diǎn)
else
	q->next = p;	//如果不是第一個(gè)創(chuàng)建的結(jié)點(diǎn)，則將上一個(gè)結(jié)點(diǎn)的后繼指針指向當(dāng)前結(jié)點(diǎn)

如果是第一個(gè)創(chuàng)立的結(jié)點(diǎn)，則將頭指針指向這個(gè)結(jié)點(diǎn)?

如果不是第一個(gè)創(chuàng)建的結(jié)點(diǎn)，則將上一個(gè)結(jié)點(diǎn)的后繼節(jié)點(diǎn)指向當(dāng)前結(jié)點(diǎn)。

最后要將指針q也指向當(dāng)前結(jié)點(diǎn)，因?yàn)榇龝?huì)臨時(shí)指針p將會(huì)指向新創(chuàng)建的結(jié)點(diǎn)。

q = p;  //指針q也要指向當(dāng)前結(jié)點(diǎn)

#include <stdio.h>
#include <stdlib.h>
 
//這里創(chuàng)建一個(gè)結(jié)構(gòu)體用來(lái)表示鏈表的結(jié)點(diǎn)類型
struct node
{
	int date;
	struct node* next;
};
 
int main()
{
	struct node* head, * p, * q = NULL, * t;
	int i, n, a;
	scanf("%d", &n);
	head = NULL;  //頭指針初始化為空
	for (i = 1; i <= n; i++)
	{
		scanf("%d", &a);
		//動(dòng)態(tài)申請(qǐng)一塊空間，用來(lái)存放一個(gè)結(jié)點(diǎn)，并用臨時(shí)指針p指向這個(gè)結(jié)點(diǎn)
		p = (struct node*)malloc(sizeof(struct node));
		p->date = a;
		p->next = NULL; //設(shè)置當(dāng)前結(jié)點(diǎn)的后繼指針為空，也就是下一個(gè)結(jié)點(diǎn)為空
		if (head == NULL)
			head = p;	//如果這是第一個(gè)創(chuàng)建的結(jié)點(diǎn)，則將頭指針指向這個(gè)點(diǎn)
		else
			q->next = p;//如果不是第一個(gè)創(chuàng)建的結(jié)點(diǎn)，則將上一個(gè)結(jié)點(diǎn)的后繼節(jié)點(diǎn)指向當(dāng)前結(jié)點(diǎn)
 
		q = p;  //指針q也指向當(dāng)前結(jié)點(diǎn)
	}
 
	//輸出鏈表中的所有數(shù)
	t = head;
	while (t != NULL)
	{
		printf("%d  ", t->date);
		t = t->next;  //繼續(xù)下一個(gè)結(jié)點(diǎn)
	}
 
}

效果圖

實(shí)現(xiàn)插入操作

首先用一個(gè)臨時(shí)指針t從鏈表的頭部開(kāi)始遍歷

 t = head; //從鏈表的頭部開(kāi)始遍歷

等到指針t的下一個(gè)結(jié)點(diǎn)的值比6大的時(shí)候，將6插到中間。

即 t -> next -> date 大于 6 的時(shí)候進(jìn)行插入

代碼實(shí)現(xiàn)

	scanf("%d", &a);  //讀入待插入的數(shù)
	t = head;		  //從鏈表的頭部開(kāi)始遍歷
	while (t != NULL)
	{
		if (t->next->date > a || t->next->next == NULL)
		{
			//如果當(dāng)前結(jié)點(diǎn)是最后一個(gè)結(jié)點(diǎn)或者下一個(gè)結(jié)點(diǎn)的值大于待插入的值的時(shí)候插入
			p = (struct node*)malloc(sizeof(struct node)); //申請(qǐng)一塊空間，來(lái)存放新增結(jié)點(diǎn)
			p->date = a;
			p->next = t->next;//新增結(jié)點(diǎn)的后繼指針指向當(dāng)前結(jié)點(diǎn)的后繼指針?biāo)赶虻慕Y(jié)點(diǎn)
			t->next = p;	  //當(dāng)前結(jié)點(diǎn)的后繼指針指向新增結(jié)點(diǎn)
			break;			  //插入完畢退出循環(huán)
			 
		}
		t = t->next;   //繼續(xù)下一個(gè)結(jié)點(diǎn)
	}

完整代碼

效果圖：

#include <stdio.h>
#include <stdlib.h>
 
//這里創(chuàng)建一個(gè)結(jié)構(gòu)體用來(lái)表示鏈表的結(jié)點(diǎn)類型
struct node
{
	int date;
	struct node* next;
};
 
int main()
{
	struct node* head, * p, * q = NULL, * t;
	int i, n, a;
	scanf("%d", &n);
	head = NULL;  //頭指針初始化為空
	for (i = 1; i <= n; i++)
	{
		scanf("%d", &a);
		//動(dòng)態(tài)申請(qǐng)一塊空間，用來(lái)存放一個(gè)結(jié)點(diǎn)，并用臨時(shí)指針p指向這個(gè)結(jié)點(diǎn)
		p = (struct node*)malloc(sizeof(struct node));
		p->date = a;
		p->next = NULL; //設(shè)置當(dāng)前結(jié)點(diǎn)的后繼指針為空，也就是下一個(gè)結(jié)點(diǎn)為空
		if (head == NULL)
			head = p;	//如果這是第一個(gè)創(chuàng)建的結(jié)點(diǎn)，則將頭指針指向這個(gè)點(diǎn)
		else
			q->next = p;//如果不是第一個(gè)創(chuàng)建的結(jié)點(diǎn)，則將上一個(gè)結(jié)點(diǎn)的后繼節(jié)點(diǎn)指向當(dāng)前結(jié)點(diǎn)
 
		q = p;  //指針q也指向當(dāng)前結(jié)點(diǎn)
	}
 
	scanf("%d", &a);  //讀入待插入的數(shù)
	t = head;		  //從鏈表的頭部開(kāi)始遍歷
	while (t != NULL)
	{
		if (t->next->date > a || t->next->next == NULL)
		{
			//如果當(dāng)前結(jié)點(diǎn)是最后一個(gè)結(jié)點(diǎn)或者下一個(gè)結(jié)點(diǎn)的值大于待插入的值的時(shí)候插入
			p = (struct node*)malloc(sizeof(struct node)); //申請(qǐng)一塊空間，來(lái)存放新增結(jié)點(diǎn)
			p->date = a;
			p->next = t->next;//新增結(jié)點(diǎn)的后繼指針指向當(dāng)前結(jié)點(diǎn)的后繼指針?biāo)赶虻慕Y(jié)點(diǎn)
			t->next = p;	  //當(dāng)前結(jié)點(diǎn)的后繼指針指向新增結(jié)點(diǎn)
			break;			  //插入完畢退出循環(huán)
			 
		}
		t = t->next;   //繼續(xù)下一個(gè)結(jié)點(diǎn)
	}
 
 
 
 
	//輸出鏈表中的所有數(shù)
	t = head;
	while (t != NULL)
	{
		printf("%d  ", t->date);
		t = t->next;  //繼續(xù)下一個(gè)結(jié)點(diǎn)
	}
 
}

以上就是C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)與算法之鏈表(一)的詳細(xì)內(nèi)容，更多關(guān)于C語(yǔ)言數(shù)據(jù)結(jié)構(gòu) 鏈表的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: