C語言數(shù)據(jù)結(jié)構(gòu)與算法之鏈表(一)
引言
在存儲(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，那么只需要向下圖一樣更改一下就可以了，而不用向像最開始那樣把每個(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ù)雜的辦法來儲(chǔ)存類型呢？
因?yàn)榘凑罩暗姆椒?，我們必須預(yù)先準(zhǔn)確地知道所需變量的個(gè)數(shù)，也就是說我們必須我們必須定義出所有的變量。假如說你現(xiàn)在定義了100個(gè)變量，而實(shí)際上則需要101個(gè)變量，那么就不得不對(duì)這個(gè)程序進(jìn)行修改。
而有了malloc函數(shù)，我們可以在程序運(yùn)行的過程中根據(jù)實(shí)際情況來申請(qǐng)空間。
鏈表結(jié)點(diǎn)結(jié)構(gòu)
每一個(gè)結(jié)點(diǎn)都由兩個(gè)部分組成。左邊的部分用來存放具體的值，那么用一個(gè)整型變量就可以；右邊的部分則需要儲(chǔ)存下一個(gè)點(diǎn)的地址，則可以用指針來實(shí)現(xiàn)（也稱為后繼指針）。
這里我們定義一個(gè)結(jié)構(gòu)體類型來存儲(chǔ)這個(gè)結(jié)點(diǎn)：
struct node
{
int date;
struct node* next;
};
因?yàn)橄乱粋€(gè)結(jié)點(diǎn)的類型也是 struct node ，所以我們指針的類型也必須是 struct node * 類型。
建立鏈表
首先，我們需要一個(gè)頭指針 head 指向鏈表的最開始。當(dāng)鏈表還沒有建立的時(shí)候頭指針head為空（也可以理解指向空結(jié)點(diǎn)）。
struct node* head; head = NULL; //頭指針初始為空
現(xiàn)在，我們來創(chuàng)立第一個(gè)結(jié)點(diǎn)，并用臨時(shí)指針p指向這個(gè)結(jié)點(diǎn)
struct node* p; //動(dòng)態(tài)申請(qǐng)一塊空間，用來存放一個(gè)結(jié)點(diǎn)，并用臨時(shí)指針p指向這個(gè)結(jié)點(diǎn) p = (struct node*)malloc(sizeof(struct node));
接下來分別設(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)為空
下面來設(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)體用來表示鏈表的結(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)一塊空間，用來存放一個(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從鏈表的頭部開始遍歷
t = head; //從鏈表的頭部開始遍歷
等到指針t的下一個(gè)結(jié)點(diǎn)的值比6大的時(shí)候，將6插到中間。
即 t -> next -> date 大于 6 的時(shí)候進(jìn)行插入
代碼實(shí)現(xiàn)
scanf("%d", &a); //讀入待插入的數(shù)
t = head; //從鏈表的頭部開始遍歷
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)一塊空間，來存放新增結(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)體用來表示鏈表的結(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)一塊空間，用來存放一個(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; //從鏈表的頭部開始遍歷
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)一塊空間，來存放新增結(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語言數(shù)據(jù)結(jié)構(gòu)與算法之鏈表(一)的詳細(xì)內(nèi)容，更多關(guān)于C語言數(shù)據(jù)結(jié)構(gòu) 鏈表的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了OpenGL實(shí)現(xiàn)掃描線填充算法，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-02-02
淺析Boost智能指針:scoped_ptr shared_ptr weak_ptr
雖然通過弱引用指針可以有效的解除循環(huán)引用，但這種方式必須在程序員能預(yù)見會(huì)出現(xiàn)循環(huán)引用的情況下才能使用，也可以是說這個(gè)僅僅是一種編譯期的解決方案，如果程序在運(yùn)行過程中出現(xiàn)了循環(huán)引用，還是會(huì)造成內(nèi)存泄漏的2013-09-09
最近正在閱讀關(guān)于C語言的庫,但是我還沒有find關(guān)于目標(biāo)文件的解釋,這篇文章主要給大家介紹了C語言目標(biāo)文件的詳細(xì)講解,文中介紹的非常詳細(xì),需要的朋友可以參考下2023-01-01
C++程序自動(dòng)重啟的實(shí)現(xiàn)代碼
自動(dòng)重啟原理很簡單,用一個(gè)進(jìn)程監(jiān)控另一個(gè)進(jìn)程,掛了就再啟動(dòng)一個(gè),細(xì)節(jié)也不算多,主要是正確判斷進(jìn)程狀態(tài)和啟動(dòng)方式,本文就給大家講講C++程序自動(dòng)重啟的實(shí)現(xiàn)方法,文中有詳細(xì)的代碼示例供大家參考,需要的朋友可以參考下2024-04-04
本文主要介紹了c++智能指針unique_ptr的使用，與shared_ptr作用類似，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-12-12
C語言使用scanf連續(xù)輸入字符串出現(xiàn)的問題
這篇文章主要介紹了C語言使用scanf連續(xù)輸入字符串出現(xiàn)的問題,本文給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-12-12
這篇文中主要為大家詳細(xì)介紹了如何利用C語言實(shí)現(xiàn)經(jīng)典的掃雷小游戲。掃雷小游戲主要是利用字符數(shù)組、循環(huán)語句和函數(shù)實(shí)現(xiàn)，感興趣的小伙伴可以了解一下2022-10-10
M1 Macbook vscode C++ debug調(diào)試實(shí)現(xiàn)
本文主要介紹了M1 Macbook vscode C++ debug調(diào)試，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-08-08
VSCode搭建STM32開發(fā)環(huán)境的方法步驟
當(dāng)我們的工程文件比較大的時(shí)候，編譯一次代碼需要很久可能會(huì)花費(fèi)到四五分鐘，但是我們用vscode編寫和編譯的話時(shí)間就會(huì)大大縮減，本文就介紹一下VSCode搭建STM32開發(fā)環(huán)境，感興趣的可以了解一下2021-07-07
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)航空訂票程序，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-01-01