日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

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

作者：玄澈_ ? 更新時間： 2021-12-09 編程語言

引言

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

有一串已經排序好的數 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;  //繼續下一個結點
	}
 
}

原文鏈接：https://blog.csdn.net/forever_bryant/article/details/121758158

欄目分類
最近更新