引言

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

有一串已經排序好的數 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 * 型別，

建立鏈表

1

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

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

2

現在，我們來創立第一個結點，并用臨時指標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;  //繼續下一個結點
	}

}

如果覺得有什么意見或者是需要的話，歡迎在評論區向小玄提出哦！

沖沖沖！！