C語言?超詳細模擬實現(xiàn)單鏈表的基本操作建議收藏
更新時間：2022年03月30日 16:59:17 作者：鹿九丸
單鏈表是后面要學的雙鏈表以及循環(huán)鏈表的基礎，要想繼續(xù)深入了解數據結構以及C語言，我們就要奠定好這塊基石！接下來就和我一起學習吧
1 鏈表的概念及結構
概念：鏈表是一種物理存儲結構上非連續(xù)、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈 接次序實現(xiàn)的 。
注意：
1. 從上圖可以看出，鏈式結構在邏輯上是連續(xù)的，但是在物理上不一定是連續(xù)
2. 現(xiàn)實中的節(jié)點一般是從堆上申請出來的
3. 從對上申請的空間，是按照一定的策略來分配的，兩次申請的空間可能連續(xù)，也可能不連續(xù)
2 鏈表的分類
實際中鏈表的結構非常多樣，以下情況組合起來就有8種鏈表結構：
1、單向或者雙向鏈表
2、帶頭或者不帶頭鏈表
3、循環(huán)或非循環(huán)鏈表
最常用的有兩種：無頭單向非循環(huán)鏈表、帶頭雙向循環(huán)鏈表
- 無頭單向非循環(huán)鏈表：結構簡單，一般不會單獨用來存數據。實際中更多是作為其他數據結構的子結 構，如哈希桶、圖的鄰接表等等。另外這種結構在筆試面試中出現(xiàn)很多。
- 帶頭雙向循環(huán)鏈表：結構最復雜，一般用在單獨存儲數據。實際中使用的鏈表數據結構，都是帶頭雙向 循環(huán)鏈表。另外這個結構雖然結構復雜，但是使用代碼實現(xiàn)以后會發(fā)現(xiàn)結構會帶來很多優(yōu)勢，實現(xiàn)反而簡單了，后面我們代碼實現(xiàn)了就知道了。
3 鏈表的實現(xiàn)無頭+單向+非循環(huán)鏈表增刪查改實現(xiàn)
3.1 鏈表的定義
typedef int SLTDataType;//
typedef struct SListNode
{
int data;//val，存儲的數據，此處假設存儲的數據為int型
struct SListNode* next;//存儲下一個節(jié)點的位置
}SListNode,SLN;3.2 鏈表數據的打印
void SListPrint(SListNode* phead)
{
SListNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}3.3 鏈表的尾插
void SListPushBack(SListNode** pphead, SLTDataType x)
{
SListNode* newnode = BuySListNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
//找尾
SListNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}在找尾的過程中，務必不能寫成下面的代碼：
while(tail!=NULL)
{
tail = tail->next;
}
tail->next = newnode;
當然，上面的介紹的是尾刪的情況。
尾插其實也是類似的，尾插的話像上面的代碼中，當tail!=NULL不成立之后，tail等于空，然后執(zhí)行賦值操作，tail->next = newnode這行代碼相當于下面的代碼：
(*tail).next，此處相當于是對空指針進行解引用，其實就是非法訪問了，并還試圖非法修改未授權內存中的數據，這將必然會引發(fā)程序的崩潰。而且也并沒有將新節(jié)點的地址存儲到之前為節(jié)點的next中。
這個地方需要弄明白鏈表進行遍歷的根本原理：
鏈表是一個相對靜態(tài)的存儲在堆區(qū)中的數據空間，我們通過改變棧區(qū)中的局部變量tail中的數據（即每一個鏈表節(jié)點的地址）來進行遍歷，之所以能夠通過tail變量能夠進行訪問并且修改節(jié)點數據的原因就是因為tail的數據類型是SListNode*，即指向節(jié)點的指針，指針的類型決定了對指針解引用能夠訪問的數據類型，所以*tail能夠訪問堆區(qū)中的節(jié)點的數據并且能夠進行修改。
3.4 鏈表空間的動態(tài)申請
SListNode* BuySListNode(SLTDataType x)
{
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
if (newnode == NULL)
{
printf("malloc fail\n");
exit(-1);
}
else
{
newnode->data = x;
newnode->next = NULL;
}
return newnode;
}3.5 鏈表的頭插
void SListPushFront(SListNode** pphead, SLTDataType x)
{
SListNode* newnode = BuySListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}3.6 鏈表的尾刪
需要考慮三種情況：
- 空
- 一個節(jié)點
- 多個節(jié)點
兩種寫法：
第一種：
void SListPopBack(SListNode** pphead)
{
assert(pphead);
if (*pphead == NULL)//空鏈表
{
return;
}
else if ((*pphead)->next == NULL)//一個節(jié)點
{
free(*pphead);//*pphead就是plist的值
*pphead = NULL;
}
else//多個節(jié)點
{
SListNode* tail = *pphead;
SListNode* prev = NULL;//為什么要置為空呢？因為這個地方相當于是指向第一個節(jié)點之前的節(jié)點，這個節(jié)點并不存在，設為空
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
tail = NULL;
prev->next = NULL;
}
}
這種方式在面對只有一個節(jié)點時也不會出現(xiàn)問題。
第二種：
void SListPopBack(SListNode** pphead)
{
assert(pphead);
if (*pphead == NULL)//空鏈表
{
return;
}
else if ((*pphead)->next == NULL)//一個節(jié)點
{
free(*pphead);//*pphead就是plist的值
*pphead = NULL;
}
else//多個節(jié)點
{
SListNode* tail = *pphead;
while (tail->next->next != NULL)
{
tail = tail->next;
}
free(tail->next);//釋放尾節(jié)點
tail->next = NULL;//將新尾節(jié)點的next置為NULL
}
}
3.7 鏈表的頭刪
void SListPopFront(SListNode** pphead)
{
assert(pphead);
if (*pphead == NULL)//空鏈表
{
return;
}
else//非空鏈表
{
SListNode* next = (*pphead)->next;//next作為臨時變量存放的是被刪除的節(jié)點中next存儲的第二個節(jié)點的地址
free(*pphead);
*pphead = next;
}
}
3.8 鏈表任意位置的前插入
void SListInsertBefore(SListNode** pphead, SListNode* pos,SLTDataType x)
{
assert(pphead);
if (*pphead == pos)//pos是第一個節(jié)點，相當于頭插
{
SListPushFront(pphead, x);
}
else
{
SListNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
SListNode* newnode = BuySListNode(x);
prev->next = newnode;
newnode->next = pos;
}
}
3.9 鏈表任意位置的后插入
兩種實現(xiàn)方式：
方式一：
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
assert(pos);
SListNode* newnode = BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
//這兩行代碼順序是固定的，只能這個順序，無法進行改變
}圖示：
方式二：
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
assert(pos);
SListNode* next = pos->next;
SListNode* newnode = BuySListNode(x);
newnode->next = next;
pos->next = newnode;
//這兩行代碼可以任意改變順序，誰先誰后都不影響最后的結果
}圖示：
3.10 鏈表的任意位置的刪除
void SListErase(SListNode** pphead, SListNode* pos)
{
assert(pphead);
assert(pos);
if (pos == *pphead)//當pos為頭節(jié)點的時候
{
SListPopFront(pphead);
}
else//當pos為非頭節(jié)點的時候
{
SListNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;
}
}圖示：
3.11 鏈表的任意位置的前刪除
void SListEraseBefore(SListNode** pphead, SListNode* pos)//pos即為任意位置
{
assert(pphead);
assert(pos);
if (pos == *pphead)
{
return;
}
else if(pos==(*pphead)->next)
{
SListPopFront(pphead);
}
else
{
SListNode* prev = *pphead;//prev用來存儲pos的前一個位置的前一個位置
while (prev->next->next != pos)
{
prev = prev->next;
}
SListNode* next = prev->next;//保存pos前一個節(jié)點的地址
prev->next = prev->next->next;//將prev和pos的兩個節(jié)點進行連接
free(next);//刪除pos的前一個節(jié)點
}
}
3.12 鏈表的任意位置的后刪除
void SListEraseAfter(SListNode* pos)
{
assert(pos);
SListNode* next = pos->next;
if (next == NULL)//當pos是最后一個節(jié)點的時候
{
return;
}
else
{
pos->next = next->next;
free(next);
next = NULL;
}
}圖示：
3.13 鏈表的銷毀
void SListDestory(SListNode** pphead)
{
assert(pphead);
SListNode* cur = *pphead;
SListNode* next = *pphead;//是為了存儲cur下一個節(jié)點的地址，因為free(cur)之后，cur指針指向的內存中的數據可能已經稱為亂碼了，即不能再正常的使用
while (cur)
{
next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}3.14 鏈表的總結
總結：單鏈表結構，適合頭插頭刪。尾部或者中間某個位置插入刪除都不適合。如果要使用鏈表結構單獨存儲數據，更適合用雙向鏈表。
單鏈表學習的意義：
- 單鏈表會作為我們以后學習復雜數據結構的子結構（圖的鄰接表、哈希桶）
- 單鏈表會有很多經典的練習題，在筆試面試中會有很多相關的題目。
到此這篇關于C語言 超詳細模擬實現(xiàn)單鏈表建議收藏的文章就介紹到這了,更多相關C語言 單鏈表內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
本文主要介紹了QT打包發(fā)布全流程，文中通過圖文介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-07-07
這篇文章主要介紹了c++ 基于opencv 識別、定位二維碼，幫助大家更好的理解和學習使用c++，感興趣的朋友可以了解下2021-03-03
這篇文章主要介紹了VC多線程編程,實例形式詳細分析了多線程編程的原理與實現(xiàn)方法,具有一定的參考借鑒價值,需要的朋友可以參考下2014-10-10
這篇文章主要介紹了VC++6.0編譯過程中常遇到的一些錯誤提示并給出了錯誤原因與分析，需要的朋友尅參考下2013-07-07
這篇文章主要介紹了C語言實現(xiàn)輸出鏈表中倒數第k個節(jié)點,主要涉及鏈表的遍歷操作,是數據結構中鏈表的常見操作。需要的朋友可以參考下2014-09-09
下面小編就為大家?guī)硪黄獪\談do {...} while (0) 在宏定義中的作用。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-12-12
這篇文章主要介紹了C++實現(xiàn)漢諾塔算法經典實例,代碼簡潔高效,對于學習算法的朋友有一定的借鑒價值,需要的朋友可以參考下2014-07-07
一個函數在它的函數體內調用它自身稱為遞歸調用。這種函數稱為遞歸函數。Ｃ語言允許函數的遞歸調用。在遞歸調用中，主調函數又是被調函數。執(zhí)行遞歸函數將反復調用其自身，每調用一次就進入新的一層2021-09-09
這篇文章主要介紹了C++中的各種容器的使用方法,本文結合示例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2023-01-01
數組是一組有序的數據的集合，數組中元素類型相同，由數組名和下標唯一地確定，數組中數據不僅數據類型相同，而且在計算機內存里連續(xù)存放，地址編號最低的存儲單元存放數組的起始元素，地址編號最高的存儲單元存放數組的最后一個元素2022-05-05