C語言數據結構超詳細講解單向鏈表
更新時間：2022年03月25日 11:33:04 作者：天影云光
鏈表可以說是一種最為基礎的數據結構了，而單向鏈表更是基礎中的基礎。鏈表是由一組元素以特定的順序組合或鏈接在一起的，不同元素之間在邏輯上相鄰，但是在物理上并不一定相鄰。在維護一組數據集合時，就可以使用鏈表，這一點和數組很相似
1.鏈表概況
1.1 鏈表的概念及結構
概念：鏈表是一種物理存儲結構上非連續(xù)、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現(xiàn)的 。
1.2 鏈表的分類
實際中鏈表的結構非常多樣，以下情況組合起來就有8種鏈表結構
單向或者雙向
帶頭或者不帶頭
循環(huán)或者非循環(huán)
雖然有這么多的鏈表的結構，但是我們實際中最常用還是兩種結構
- 無頭單向非循環(huán)鏈表：結構簡單，一般不會單獨用來存數據。實際中更多是作為其他數據結構的子結構，如哈希桶、圖的鄰接表等等。另外這種結構在筆試面試中出現(xiàn)很多。
- 帶頭雙向循環(huán)鏈表：結構最復雜，一般用在單獨存儲數據。實際中使用的鏈表數據結構，都是帶頭雙向循環(huán)鏈表。另外這個結構雖然結構復雜，但是使用代碼實現(xiàn)以后會發(fā)現(xiàn)結構會帶來很多優(yōu)勢，實現(xiàn)反而簡單了，后面我們代碼實現(xiàn)了就知道了
2. 單向鏈表的實現(xiàn)
單向鏈表結構
2.1 SList.h（頭文件的匯總，函數的聲明）
#pragma once
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
int data;//數據
struct SListNode* next;//下一個節(jié)點的地址
}SListNode;
void SListPrint(SListNode* phead);//打印
SListNode* BuySListNode(SLTDataType x);//搞出一個新節(jié)點
void SListPushBack(SListNode** pphead, SLTDataType x);//尾插
void SListPushFront(SListNode** pphead, SLTDataType x);//頭插
void SListPopBack(SListNode** pphead);//尾刪
void SListPopFront(SListNode** pphead);//頭刪
SListNode* SListFind(SListNode* phead, SLTDataType x);//查找
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x);//在pos位置之前插入
void SListInsertAfter(SListNode* pos, SLTDataType x);//在pos位置之后插入
void SListErase(SListNode** pphead, SListNode* pos);//刪除pos位置
void SListEraseAfter(SListNode* pos);//刪除pos之后位置
void SListDestroy(SListNode** pphead);//銷毀
2.2 SList.c（函數的具體實現(xiàn)邏輯）
2.2.1 打印鏈表
//打印
void SListPrint(SListNode* phead)
{
//assert(phead);//沒必要斷言，空鏈表也能打印
SListNode* cur = phead;
while (cur != NULL)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
//test.c
void TestSList1()
{
SListNode* slist;//結構體指針，用于存節(jié)點的地址
SListNode* n1 = (SListNode *)malloc(sizeof(SListNode));
SListNode* n2 = (SListNode*)malloc(sizeof(SListNode));
SListNode* n3 = (SListNode*)malloc(sizeof(SListNode));
n1->data = 1;
n2->data = 2;
n3->data = 3;
n1->next = n2;
n2->next = n3;
n3->next = NULL;
slist = n1;
SListPrint(slist);
}
2.2.2 搞出一個新節(jié)點（為其他函數服務）
//搞出一個新節(jié)點
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;
}
2.2.3 鏈表尾插
//尾插
void SListPushBack(SListNode** pphead,SLTDataType x)//會改變實參slist，要傳二級指針
{
assert(pphead);//就算鏈表是空，它的二級指針也不為空
SListNode* newnode = BuySListNode(x);
if (*pphead == NULL)
{
*pphead = newnode;
}
else
{
//遍歷找尾
SListNode* tail = *pphead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = newnode;
}
}
void TestSList2()
{
SListNode* slist = NULL;
for (int i = 0; i < 6; i++)
{
SListPushBack(&slist,i);
}
SListPrint(slist);
}
2.2.4 鏈表頭插
//頭插
void SListPushFront(SListNode** pphead, SLTDataType x)
{
assert(pphead);//就算鏈表是空，它的二級指針也不為空
SListNode* newnode = BuySListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
void TestSList2()
{
SListNode* slist = NULL;
for (int i = 0; i < 6; i++)
{
SListPushFront(&slist,i);
}
SListPrint(slist);
}
2.2.5 鏈表尾刪
方法1（用兩個指針，分別找最后一個和倒數第二個）：
方法2（直接找倒數第二個）：
//尾刪
void SListPopBack(SListNode** pphead)//如果只有一個節(jié)點但還要尾刪，就會改變實參slist，建議傳二級指針
{
assert(pphead);//就算鏈表是空，它的二級指針也不為空
//三種情況：
//1.空
//2.一個節(jié)點
//3.多個節(jié)點
if (*pphead == NULL)
{
return;
}
else if ((*pphead)->next == NULL)//優(yōu)先級，記得加括號
{
free(*pphead);
*pphead = NULL;
}
//第一種寫法（用兩個指針，分別找最后一個和倒數第二個）
else
{
SListNode* prev = NULL;//找倒數第二個元素，用于將它指向NULL
SListNode* tail = *pphead;//找尾
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
tail = NULL;//習慣性free掉就將其置空
prev->next = NULL;
}
//方法二（直接找倒數第二個）
//else
//{
//SListNode* tail = *pphead;//找尾
//while (tail->next->next != NULL)
//{
// tail = tail->next;
//}
//free(tail->next);
//tail->next = NULL;
//}
}
2.2.6 鏈表頭刪
//頭刪
void SListPopFront(SListNode** pphead)
{
assert(pphead);
//1.空
//2.非空
if (*pphead == NULL)
{
return;
}
else
{
SListNode* next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
}
2.2.7 查找節(jié)點
//查找
SListNode* SListFind(SListNode* phead, SLTDataType x)
{
SListNode* cur = phead;
while (phead != NULL)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
2.2.8 在pos位置之前插入
//在pos位置之前插入（一般跟find配合使用）
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x)
{
assert(pphead);
assert(pos);//間接檢測鏈表是否為空，因為空鏈表找不到pos
//1.pos是第一個節(jié)點（頭插）
//2.pos不是第一個節(jié)點
if (pos == *pphead)
{
SListPushFront(pphead, x);
}
else
{
SListNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
SListNode* newnode = BuySListNode(x);
prev->next = newnode;
newnode->next = pos;
}
}
2.2.9 在pos位置之后插入
方法1：兩個指針，先連接pos和newnode還是先連接newnode和next都行
方法2：只有一個指針，一定要先通過pos連接newnode和下一個，再連接pos和newnode，否則會找不到下一個的地址。
//在pos位置之后插入
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
assert(pos);
SListNode* newnode = BuySListNode(x);
SListNode* next = pos->next;
newnode->next = next;//順序無所謂
pos->next = newnode;
//或者不定義next
//newnode->next = pos->next;
//pos->next = newnode;//順序要定好，否則會找不到
}
2.2.10 刪除pos位置
//刪除pos位置
void SListErase(SListNode** pphead, SListNode* pos)
{
assert(pphead);
assert(pos);
if (pos == *pphead)
{
SListPopFront(pphead);
}
else
{
SListNode* prev = *pphead;
while (prev->next != pos)
{
prev = prev->next;
}
prev->next = pos->next;
free(pos);
pos = NULL;//好習慣
}
}
2.2.11 刪除pos之后位置
//刪除pos之后位置
void SListEraseAfter(SListNode* pos)
{
assert(pos);
SListNode* next = pos->next;
if (next)//防止pos是最后一個元素
{
pos->next = next->next;
free(next);
next = NULL;
}
}
2.2.12 鏈表銷毀
一個個找，一個個銷毀，最終將slist置空。
//銷毀
void SListDestroy(SListNode** pphead)
{
assert(pphead);
SListNode* cur = *pphead;
while (cur)
{
SListNode* next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
總結：單鏈表結構，適合頭插頭刪。尾部或者中間某個位置插入刪除不適合。如果要使用鏈表單獨存儲數據，那我們之后會學的雙向鏈表更合適。單鏈表學習的意義：
- 單鏈表會作為我們之后學習復雜數據結構的子結構（圖的鄰接表、哈希桶）
- 單鏈表會出很多經典的練習題。
鏈表系列有很多重點內容，我會花不少時間來跟大家講解鏈表，相信大家跟著練習的話編程嚴謹性會大大提升，加油哦！
到此這篇關于C語言數據結構超詳細講解單向鏈表的文章就介紹到這了,更多相關C語言 單向鏈表內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
五子棋游戲是一款很經典的智力游戲，只有學過編程語言的人，把五子棋的編程原理弄懂了，就能用自己熟悉的語言實現(xiàn)出來，在這里給大家分享，c語言五子棋源碼，僅供大家參考借鑒。2016-03-03
這篇文章主要介紹了VC中SDK與MFC的區(qū)別淺析,需要的朋友可以參考下2014-07-07
異常是一種處理錯誤的方式,當一個函數發(fā)現(xiàn)自己無法處理的錯誤時就可以拋出異常,讓函數的直接或間接調用者處理這個錯誤,本文給大家總結了C++中的異常,需要的朋友可以參考下2023-10-10
C++?Boost?StringAlgorithms超詳細講解
Boost是為C++語言標準庫提供擴展的一些C++程序庫的總稱。Boost庫是一個可移植、提供源代碼的C++庫，作為標準庫的后備，是C++標準化進程的開發(fā)引擎之一，是為C++語言標準庫提供擴展的一些C++程序庫的總稱2022-11-11
C++11 新增了很多特性，lambda 表達式是其中之一，本文涉及到C++11這次更新中較為重要的lambda表達式。有需要的朋友們可以參考學習。2016-08-08
這篇文章主要介紹了C++使用JsonCpp庫操作json格式數據,結合實例形式詳細分析了JsonCpp庫的下載及C++使用JsonCpp庫對json格式數據序列化相關操作技巧,需要的朋友可以參考下2017-06-06
Qt6.0+vs2019環(huán)境配置的實現(xiàn)教程
這篇文章主要介紹了Qt6.0+vs2019環(huán)境配置的實現(xiàn)教程，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-03-03
這篇文章主要介紹了講解數據結構中的算法復雜度結與順序表的C語言版示例,包括對時間復雜度和空間復雜度等概念的簡單講解,需要的朋友可以參考下2016-02-02
大家都知道c++里的各種運算符都是用函數實現(xiàn)的，比如=就等號函數，所以當用=給一個對象賦值的時候，實際調用的是=號所對應的=號函數。下面通過本文給大家介紹c/c++賦值函數（重載=號運算符），感興趣的朋友一起看看吧2018-08-08
variant類型在C++14并沒有加入，若想在不支持C++17的編譯器上使用variant類型，我們可以通過boost的variant類型，variant類型可以表示任意一種類型和any類型有些相似，但還是有些區(qū)別下面將淺談variant的幾種訪問方法，感興趣的朋友們下面來一起看看吧。2016-10-10