C語言數(shù)據(jù)結(jié)構(gòu)與算法之鏈表(一)
引言
在存儲一大波數(shù)的時候，我們通常使用的是數(shù)組，但是數(shù)組有時候又會顯得不夠靈活，比如下面這個例子：
有一串已經(jīng)排序好的數(shù) 2，3，5，8，9 ，10
如果我們想要往數(shù)組中插入6 這個元素，需要把 8 以后的元素全部往后挪一位
這樣操作顯然很耗費時間，如果使用鏈表的話則會快很多。那么什么是鏈表呢？請看下圖：
此時如果需要在8前面加入一個6，那么只需要向下圖一樣更改一下就可以了，而不用向像最開始那樣把每個數(shù)向后挪。
鏈表的相關(guān)思考
為了實現(xiàn)鏈表這樣的數(shù)據(jù)結(jié)構(gòu)，我們需要使用指針和malloc這樣的函數(shù)。
注意 ： malloc 函數(shù)的返回值是 void * 類型，我們需要對其進行強制類型轉(zhuǎn)換?
使用malloc時需要調(diào)用頭文件 <stdlib.h>
為什么我們要用這么復雜的辦法來儲存類型呢？
因為按照之前的方法，我們必須預先準確地知道所需變量的個數(shù)，也就是說我們必須我們必須定義出所有的變量。假如說你現(xiàn)在定義了100個變量，而實際上則需要101個變量，那么就不得不對這個程序進行修改。
而有了malloc函數(shù)，我們可以在程序運行的過程中根據(jù)實際情況來申請空間。
鏈表結(jié)點結(jié)構(gòu)
每一個結(jié)點都由兩個部分組成。左邊的部分用來存放具體的值，那么用一個整型變量就可以；右邊的部分則需要儲存下一個點的地址，則可以用指針來實現(xiàn)（也稱為后繼指針）。
這里我們定義一個結(jié)構(gòu)體類型來存儲這個結(jié)點：
struct node
{
int date;
struct node* next;
};
因為下一個結(jié)點的類型也是 struct node ，所以我們指針的類型也必須是 struct node * 類型。
建立鏈表
首先，我們需要一個頭指針 head 指向鏈表的最開始。當鏈表還沒有建立的時候頭指針head為空（也可以理解指向空結(jié)點）。
struct node* head; head = NULL; //頭指針初始為空
現(xiàn)在，我們來創(chuàng)立第一個結(jié)點，并用臨時指針p指向這個結(jié)點
struct node* p; //動態(tài)申請一塊空間，用來存放一個結(jié)點，并用臨時指針p指向這個結(jié)點 p = (struct node*)malloc(sizeof(struct node));
接下來分別設置新建的結(jié)點的左半部分和右半部分
scanf("%d", &a);
p->date = a; //將數(shù)據(jù)存儲到當前結(jié)點的date域中
p->next = NULL; //設置當前結(jié)點的后繼指針為空，也就是當前結(jié)點的下一個結(jié)點為空
下面來設置頭指針并設置新創(chuàng)結(jié)點的 *next 指向空 。頭指針的作用是方便以后從頭遍歷整個鏈表
if (head == NULL) head = p; //如果這是第一個創(chuàng)建的結(jié)點，則將頭指針指向這個結(jié)點 else q->next = p; //如果不是第一個創(chuàng)建的結(jié)點，則將上一個結(jié)點的后繼指針指向當前結(jié)點
如果是第一個創(chuàng)立的結(jié)點，則將頭指針指向這個結(jié)點?
如果不是第一個創(chuàng)建的結(jié)點，則將上一個結(jié)點的后繼節(jié)點指向當前結(jié)點。
最后要將指針q也指向當前結(jié)點，因為待會臨時指針p將會指向新創(chuàng)建的結(jié)點。
q = p; //指針q也要指向當前結(jié)點
#include <stdio.h>
#include <stdlib.h>
//這里創(chuàng)建一個結(jié)構(gòu)體用來表示鏈表的結(jié)點類型
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);
//動態(tài)申請一塊空間，用來存放一個結(jié)點，并用臨時指針p指向這個結(jié)點
p = (struct node*)malloc(sizeof(struct node));
p->date = a;
p->next = NULL; //設置當前結(jié)點的后繼指針為空，也就是下一個結(jié)點為空
if (head == NULL)
head = p; //如果這是第一個創(chuàng)建的結(jié)點，則將頭指針指向這個點
else
q->next = p;//如果不是第一個創(chuàng)建的結(jié)點，則將上一個結(jié)點的后繼節(jié)點指向當前結(jié)點
q = p; //指針q也指向當前結(jié)點
}
//輸出鏈表中的所有數(shù)
t = head;
while (t != NULL)
{
printf("%d ", t->date);
t = t->next; //繼續(xù)下一個結(jié)點
}
}
效果圖
實現(xiàn)插入操作
首先用一個臨時指針t從鏈表的頭部開始遍歷
t = head; //從鏈表的頭部開始遍歷
等到指針t的下一個結(jié)點的值比6大的時候，將6插到中間。
即 t -> next -> date 大于 6 的時候進行插入
代碼實現(xiàn)
scanf("%d", &a); //讀入待插入的數(shù)
t = head; //從鏈表的頭部開始遍歷
while (t != NULL)
{
if (t->next->date > a || t->next->next == NULL)
{
//如果當前結(jié)點是最后一個結(jié)點或者下一個結(jié)點的值大于待插入的值的時候插入
p = (struct node*)malloc(sizeof(struct node)); //申請一塊空間，來存放新增結(jié)點
p->date = a;
p->next = t->next;//新增結(jié)點的后繼指針指向當前結(jié)點的后繼指針所指向的結(jié)點
t->next = p; //當前結(jié)點的后繼指針指向新增結(jié)點
break; //插入完畢退出循環(huán)
}
t = t->next; //繼續(xù)下一個結(jié)點
}
完整代碼
效果圖：
#include <stdio.h>
#include <stdlib.h>
//這里創(chuàng)建一個結(jié)構(gòu)體用來表示鏈表的結(jié)點類型
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);
//動態(tài)申請一塊空間，用來存放一個結(jié)點，并用臨時指針p指向這個結(jié)點
p = (struct node*)malloc(sizeof(struct node));
p->date = a;
p->next = NULL; //設置當前結(jié)點的后繼指針為空，也就是下一個結(jié)點為空
if (head == NULL)
head = p; //如果這是第一個創(chuàng)建的結(jié)點，則將頭指針指向這個點
else
q->next = p;//如果不是第一個創(chuàng)建的結(jié)點，則將上一個結(jié)點的后繼節(jié)點指向當前結(jié)點
q = p; //指針q也指向當前結(jié)點
}
scanf("%d", &a); //讀入待插入的數(shù)
t = head; //從鏈表的頭部開始遍歷
while (t != NULL)
{
if (t->next->date > a || t->next->next == NULL)
{
//如果當前結(jié)點是最后一個結(jié)點或者下一個結(jié)點的值大于待插入的值的時候插入
p = (struct node*)malloc(sizeof(struct node)); //申請一塊空間，來存放新增結(jié)點
p->date = a;
p->next = t->next;//新增結(jié)點的后繼指針指向當前結(jié)點的后繼指針所指向的結(jié)點
t->next = p; //當前結(jié)點的后繼指針指向新增結(jié)點
break; //插入完畢退出循環(huán)
}
t = t->next; //繼續(xù)下一個結(jié)點
}
//輸出鏈表中的所有數(shù)
t = head;
while (t != NULL)
{
printf("%d ", t->date);
t = t->next; //繼續(xù)下一個結(jié)點
}
}
以上就是C語言數(shù)據(jù)結(jié)構(gòu)與算法之鏈表(一)的詳細內(nèi)容，更多關(guān)于C語言數(shù)據(jù)結(jié)構(gòu) 鏈表的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
這篇文章主要為大家詳細介紹了C++懶漢模式和餓漢模式，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
這篇文章主要介紹了C語言解線性方程的四種方法,大家參考使用，學習線性代數(shù)的同學一定能用到2013-11-11
一文掌握C++ const與constexpr及區(qū)別
C++ 11標準中,const 用于為修飾的變量添加“只讀”屬性而 constexpr關(guān)鍵字則用于指明其后是一個常量,編譯器在編譯程序時可以順帶將其結(jié)果計算出來,而無需等到程序運行階段,這樣的優(yōu)化極大地提高了程序的執(zhí)行效率,本文重點介紹C++ const與constexpr區(qū)別介紹,一起看看吧2024-02-02
枚舉法的本質(zhì)就是從所有候選答案中去搜索正確的解，枚舉算法簡單粗暴，他暴力的枚舉所有可能，盡可能地嘗試所有的方法，感興趣的朋友來看看吧2022-05-05
這里給大家分享的是一個C語言string.h頭文件檢驗字符串函數(shù)的仿寫，非常的簡單實用，小編覺得這篇文寫的還不錯，希望能夠給你帶來幫助2021-11-11
C++?LeetCode1827題解最少操作使數(shù)組遞增
這篇文章主要為大家介紹了C++?LeetCode1827題解最少操作使數(shù)組遞增示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-12-12
C++數(shù)據(jù)結(jié)構(gòu)之實現(xiàn)鄰接表與鄰接矩陣的相互轉(zhuǎn)換
這篇文章主要為大家學習介紹了C++如何實現(xiàn)鄰接表與鄰接矩陣的相互轉(zhuǎn)換，文中的示例代碼簡潔易懂，感興趣的小伙伴可以跟隨小編一起學習一下2023-07-07
C++動態(tài)規(guī)劃中關(guān)于背包問題講解
可能有些讀者有接觸過動態(tài)規(guī)劃，可能也有一些讀者以前完全不知道動態(tài)規(guī)劃這個東西，別擔心，我這篇文章會為讀者做一個入門，好讓讀者掌握這個重要的知識點2023-03-03
下面小編就為大家?guī)硪黄P(guān)于移位操作的一點重要說明。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-12-12
C語言之結(jié)構(gòu)體定義 typedef struct 用法詳解和用法小結(jié)
這篇文章主要介紹了C語言的結(jié)構(gòu)體定義typedef struct用法詳解和用法小結(jié)，typedef是類型定義，typedef struct 是為了使用這個結(jié)構(gòu)體方便，感興趣的同學可以參考閱讀2023-03-03