C語言數據結構與算法之鏈表(一)

Posted on by

引言

在存儲一大波數的時候，我們通常使用的是數組，但是數組有時候又會顯得不夠靈活，比如下面這個例子：

有一串已經排序好的數 2，3，5，8，9 ，10

如果我們想要往數組中插入6 這個元素，需要把 8 以後的元素全部往後挪一位

這樣操作顯然很耗費時間，如果使用鏈表的話則會快很多。那麼什麼是鏈表呢？請看下圖：

此時如果需要在8前面加入一個6，那麼隻需要向下圖一樣更改一下就可以瞭，而不用向像最開始那樣把每個數向後挪。

鏈表的相關思考

為瞭實現鏈表這樣的數據結構，我們需要使用指針和malloc這樣的函數。

註意 ： malloc 函數的返回值是 void * 類型，我們需要對其進行強制類型轉換 

使用malloc時需要調用頭文件 <stdlib.h>

為什麼我們要用這麼復雜的辦法來儲存類型呢？

因為按照之前的方法，我們必須預先準確地知道所需變量的個數，也就是說我們必須我們必須定義出所有的變量。假如說你現在定義瞭100個變量，而實際上則需要101個變量，那麼就不得不對這個程序進行修改。

而有瞭malloc函數，我們可以在程序運行的過程中根據實際情況來申請空間。

鏈表結點結構

每一個結點都由兩個部分組成。左邊的部分用來存放具體的值，那麼用一個整型變量就可以；右邊的部分則需要儲存下一個點的地址，則可以用指針來實現（也稱為後繼指針）。

這裡我們定義一個結構體類型來存儲這個結點：

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

因為下一個結點的類型也是 struct node ，所以我們指針的類型也必須是 struct node * 類型。

建立鏈表

首先，我們需要一個頭指針 head 指向鏈表的最開始。當鏈表還沒有建立的時候頭指針head為空（也可以理解指向空結點）。

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

現在，我們來創立第一個結點，並用臨時指針p指向這個結點

struct node* p;
//動態申請一塊空間，用來存放一個結點，並用臨時指針p指向這個結點
p = (struct node*)malloc(sizeof(struct node));

接下來分別設置新建的結點的左半部分和右半部分

scanf("%d", &a);
p->date = a;	 //將數據存儲到當前結點的date域中
p->next = NULL;  //設置當前結點的後繼指針為空，也就是當前結點的下一個結點為空

下面來設置頭指針並設置新創結點的 *next 指向空 。頭指針的作用是方便以後從頭遍歷整個鏈表

if (head == NULL)
	head = p;  //如果這是第一個創建的結點，則將頭指針指向這個結點
else
	q->next = p;	//如果不是第一個創建的結點，則將上一個結點的後繼指針指向當前結點

如果是第一個創立的結點，則將頭指針指向這個結點 

如果不是第一個創建的結點，則將上一個結點的後繼節點指向當前結點。

最後要將指針q也指向當前結點，因為待會臨時指針p將會指向新創建的結點。

q = p;  //指針q也要指向當前結點
#include <stdio.h>
#include <stdlib.h>
 
//這裡創建一個結構體用來表示鏈表的結點類型
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);
		//動態申請一塊空間，用來存放一個結點，並用臨時指針p指向這個結點
		p = (struct node*)malloc(sizeof(struct node));
		p->date = a;
		p->next = NULL; //設置當前結點的後繼指針為空，也就是下一個結點為空
		if (head == NULL)
			head = p;	//如果這是第一個創建的結點，則將頭指針指向這個點
		else
			q->next = p;//如果不是第一個創建的結點，則將上一個結點的後繼節點指向當前結點
 
		q = p;  //指針q也指向當前結點
	}
 
	//輸出鏈表中的所有數
	t = head;
	while (t != NULL)
	{
		printf("%d  ", t->date);
		t = t->next;  //繼續下一個結點
	}
 
}

效果圖

實現插入操作

首先用一個臨時指針t從鏈表的頭部開始遍歷

 t = head; //從鏈表的頭部開始遍歷

等到指針t的下一個結點的值比6大的時候，將6插到中間。

即 t -> next -> date 大於 6 的時候進行插入

代碼實現

	scanf("%d", &a);  //讀入待插入的數
	t = head;		  //從鏈表的頭部開始遍歷
	while (t != NULL)
	{
		if (t->next->date > a || t->next->next == NULL)
		{
			//如果當前結點是最後一個結點或者下一個結點的值大於待插入的值的時候插入
			p = (struct node*)malloc(sizeof(struct node)); //申請一塊空間，來存放新增結點
			p->date = a;
			p->next = t->next;//新增結點的後繼指針指向當前結點的後繼指針所指向的結點
			t->next = p;	  //當前結點的後繼指針指向新增結點
			break;			  //插入完畢退出循環
			 
		}
		t = t->next;   //繼續下一個結點
	}

完整代碼

效果圖：

#include <stdio.h>
#include <stdlib.h>
 
//這裡創建一個結構體用來表示鏈表的結點類型
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);
		//動態申請一塊空間，用來存放一個結點，並用臨時指針p指向這個結點
		p = (struct node*)malloc(sizeof(struct node));
		p->date = a;
		p->next = NULL; //設置當前結點的後繼指針為空，也就是下一個結點為空
		if (head == NULL)
			head = p;	//如果這是第一個創建的結點，則將頭指針指向這個點
		else
			q->next = p;//如果不是第一個創建的結點，則將上一個結點的後繼節點指向當前結點
 
		q = p;  //指針q也指向當前結點
	}
 
	scanf("%d", &a);  //讀入待插入的數
	t = head;		  //從鏈表的頭部開始遍歷
	while (t != NULL)
	{
		if (t->next->date > a || t->next->next == NULL)
		{
			//如果當前結點是最後一個結點或者下一個結點的值大於待插入的值的時候插入
			p = (struct node*)malloc(sizeof(struct node)); //申請一塊空間，來存放新增結點
			p->date = a;
			p->next = t->next;//新增結點的後繼指針指向當前結點的後繼指針所指向的結點
			t->next = p;	  //當前結點的後繼指針指向新增結點
			break;			  //插入完畢退出循環
			 
		}
		t = t->next;   //繼續下一個結點
	}
 
 
 
 
	//輸出鏈表中的所有數
	t = head;
	while (t != NULL)
	{
		printf("%d  ", t->date);
		t = t->next;  //繼續下一個結點
	}
 
}

以上就是C語言數據結構與算法之鏈表(一)的詳細內容，更多關於C語言數據結構 鏈表的資料請關註WalkonNet其它相關文章！

推薦閱讀：