老生常談C語言鏈表小結(jié)
更新時間：2021年11月09日 09:21:44 作者：會掉發(fā)的程序員
鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的 ，這篇文章主要介紹了C語言鏈表,需要的朋友可以參考下
鏈表的概念及結(jié)構(gòu)
概念
鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的 。
結(jié)構(gòu)
代碼
struct Slist
{
int* a;
struct Slist* next;
};
邏輯結(jié)構(gòu):
物理結(jié)構(gòu)：
注意:
- 從上圖可以看出，鏈?zhǔn)浇Y(jié)構(gòu)在邏輯上是連續(xù)的，但是在物理上是不一定是連續(xù)的。
- 這些結(jié)點一般是從堆上申請出來的。
- 從堆上申請的空間，是按照一定的策劃來分配的，兩次申請的空間可能連續(xù)，大概率是不連續(xù)的。
鏈表的分類
實際中鏈表的結(jié)構(gòu)非常多樣，以下情況組合起來就有8種鏈表結(jié)構(gòu)：
1. 單向或者雙向
①單向
②雙向
2.帶頭或者不帶頭
①帶頭
②不帶頭
3.循環(huán)或者非循環(huán)
①循環(huán)
②非循環(huán)
雖然有這么多種結(jié)構(gòu)的鏈表，但是我們實際中最常用的只有兩種結(jié)構(gòu):
1. 無頭單向非循環(huán)鏈表
2.帶頭雙向循環(huán)鏈表
1. 無頭單向非循環(huán)鏈表：結(jié)構(gòu)簡單，一般不會單獨用來存數(shù)據(jù)。實際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。
2. 帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，一般用在單獨存儲數(shù)據(jù)。實際中使用的鏈表數(shù)據(jù)結(jié)構(gòu)，都是帶頭雙向循環(huán)鏈表。另外這個結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使用代碼實現(xiàn)以后會發(fā)現(xiàn)結(jié)構(gòu)會帶來很多優(yōu)勢，實現(xiàn)反而簡單了，后面我們代碼實現(xiàn)了就知道了。
單鏈表的實現(xiàn)（無頭）
單鏈表結(jié)構(gòu)
typedef int SLTDateType;
typedef struct SListNode
{
SLTDateType data;
struct SListNode* next;
}SListNode;
單鏈表需要的功能
// 動態(tài)申請一個節(jié)點 SListNode* BuySListNode(SLTDateType x); // 單鏈表打印 void SListPrint(SListNode* plist); // 單鏈表尾插 void SListPushBack(SListNode** pplist, SLTDateType x); // 單鏈表的頭插 void SListPushFront(SListNode** pplist, SLTDateType x); // 單鏈表的尾刪 void SListPopBack(SListNode** pplist); // 單鏈表頭刪 void SListPopFront(SListNode** pplist); // 單鏈表查找 SListNode* SListFind(SListNode* plist, SLTDateType x); // 單鏈表在pos位置之后插入x // 分析思考為什么不在pos位置之前插入？ void SListInsertAfter(SListNode* pos, SLTDateType x); // 單鏈表刪除pos位置之后的值 // 分析思考為什么不刪除pos位置？ void SListEraseAfter(SListNode* pos); // 單鏈表的銷毀 void SListDestory(SListNode** pplist);
功能實現(xiàn)
SListNode* BuySListNode(SLTDateType x)
{
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
if (newnode == NULL)
{
exit(-1);
}
newnode->data = x;
return newnode;
}
void SListPrint(SListNode* plist)
{
if (plist == NULL)
{
printf("NULL\n");
return;
}
else
{
while (plist)
{
printf("%d->", plist->data);
plist = plist->next;
}
printf("NULL\n");
}
}
void SListPushBack(SListNode** pplist, SLTDateType x)
{
SListNode* tail = *pplist;
SListNode* newnode = BuySListNode(x);
newnode->next = NULL;
if (tail == NULL)
{
*pplist = newnode;
}
else
{
while (tail->next)
{
tail = tail->next;
}
tail->next = newnode;
}
}
void SListPushFront(SListNode** pplist, SLTDateType x)
{
SListNode* newnode = BuySListNode(x);
newnode->next = *pplist;
*pplist = newnode;
}
void SListPopBack(SListNode** pplist)
{
assert(*pplist);
SListNode* tail = *pplist;
SListNode* Pretail = NULL;
if (tail->next == NULL)
{
*pplist = NULL;
return;
}
else
{
while (tail->next)
{
Pretail = tail;
tail = tail->next;
}
free(tail);
tail = NULL;
Pretail->next = NULL;
}
}
void SListPopFront(SListNode** pplist)
{
assert(*pplist);
SListNode* front = *pplist;
*pplist = front->next;
free(front);
front = NULL;
}
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
assert(plist);
SListNode* pos = plist;
while (pos && pos->data != x)
{
pos = pos->next;
}
return pos;
}
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
assert(pos);
SListNode* newnode = BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
void SListEraseAfter(SListNode* pos)
{
assert(pos);
assert(pos->next);
SListNode* node = pos->next;
pos->next = node->next;
free(node);
}
void SListDestory(SListNode** pplist)
{
SListNode* node = *pplist;
SListNode* PreNode = NULL;
while (node)
{
PreNode = node->next;
free(node);
node = PreNode;
}
}
雙向鏈表的實現(xiàn)
雙向鏈表的結(jié)構(gòu)
SListNode* BuySListNode(SLTDateType x)
{
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
if (newnode == NULL)
{
exit(-1);
}
newnode->data = x;
return newnode;
}
void SListPrint(SListNode* plist)
{
if (plist == NULL)
{
printf("NULL\n");
return;
}
else
{
while (plist)
{
printf("%d->", plist->data);
plist = plist->next;
}
printf("NULL\n");
}
}
void SListPushBack(SListNode** pplist, SLTDateType x)
{
SListNode* tail = *pplist;
SListNode* newnode = BuySListNode(x);
newnode->next = NULL;
if (tail == NULL)
{
*pplist = newnode;
}
else
{
while (tail->next)
{
tail = tail->next;
}
tail->next = newnode;
}
}
void SListPushFront(SListNode** pplist, SLTDateType x)
{
SListNode* newnode = BuySListNode(x);
newnode->next = *pplist;
*pplist = newnode;
}
void SListPopBack(SListNode** pplist)
{
assert(*pplist);
SListNode* tail = *pplist;
SListNode* Pretail = NULL;
if (tail->next == NULL)
{
*pplist = NULL;
return;
}
else
{
while (tail->next)
{
Pretail = tail;
tail = tail->next;
}
free(tail);
tail = NULL;
Pretail->next = NULL;
}
}
void SListPopFront(SListNode** pplist)
{
assert(*pplist);
SListNode* front = *pplist;
*pplist = front->next;
free(front);
front = NULL;
}
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
assert(plist);
SListNode* pos = plist;
while (pos && pos->data != x)
{
pos = pos->next;
}
return pos;
}
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
assert(pos);
SListNode* newnode = BuySListNode(x);
newnode->next = pos->next;
pos->next = newnode;
}
void SListEraseAfter(SListNode* pos)
{
assert(pos);
assert(pos->next);
SListNode* node = pos->next;
pos->next = node->next;
free(node);
}
void SListDestory(SListNode** pplist)
{
SListNode* node = *pplist;
SListNode* PreNode = NULL;
while (node)
{
PreNode = node->next;
free(node);
node = PreNode;
}
}
雙向鏈表的功能
//創(chuàng)建鏈表返回頭結(jié)點 LTNode* ListInit(); // 雙向鏈表銷毀 void ListDestory(LTNode* phead); // 雙向鏈表打印 void ListPrint(LTNode* phead); // 雙向鏈表尾插 void ListPushBack(LTNode* phead, LTDateType x); // 雙向鏈表尾刪 void ListPopBack(LTNode* phead); // 雙向鏈表頭插 void ListPushFront(LTNode* phead, LTDateType x); // 雙向鏈表頭刪 void ListPopFront(LTNode* phead); // 雙向鏈表查找 LTNode* ListFind(LTNode* phead, LTDateType x); // 雙向鏈表在pos的前面進行插入 void ListInsert(LTNode* pos, LTDateType x); // 雙向鏈表刪除pos位置的節(jié)點 void ListErase(LTNode* pos);
功能實現(xiàn)
LTNode* ListInit()
{
//哨兵位頭結(jié)點
LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
if (phead == NULL)
{
printf("開辟空間失敗!!!\n");
exit(-1);
}
phead->next = phead;
phead->prev = phead;
return phead;
}
void ListDestory(LTNode* phead)
{
assert(phead);
LTNode* cur = phead;
LTNode* p = NULL;
LTNode* tail = phead->prev;
while (cur != tail)
{
p = cur;
cur = cur->next;
free(p);
}
free(tail);
}
void ListPrint(LTNode* phead)
{
assert(phead);
LTNode* front = phead->next;
while (front != phead)
{
printf("%d ", front->data);
front = front->next;
}
printf("\n");
}
void ListPushBack(LTNode* phead, LTDateType x)
{
assert(phead);
LTNode* tail = phead->prev;
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
printf("開辟空間失敗!!\n");
exit(-1);
}
newnode->data = x;
tail->next = newnode;
newnode->prev = tail;
newnode->next = phead;
phead->prev = newnode;
}
void ListPopBack(LTNode* phead)
{
assert(phead);
assert(phead != phead->next);
LTNode* tail = phead->prev;
LTNode* TailFront = tail->prev;
TailFront->next = phead;
phead->prev = TailFront;
free(tail);
}
void ListPushFront(LTNode* phead, LTDateType x)
{
assert(phead);
LTNode* next = phead->next;
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
printf("開辟空間失敗!!\n");
exit(-1);
}
newnode->data = x;
phead->next = newnode;
newnode->prev = phead;
newnode->next = next;
next->prev = newnode;
}
void ListPopFront(LTNode* phead)
{
assert(phead);
assert(phead != phead->next);
LTNode* head = phead->next;//頭結(jié)點
phead->next = head->next;
head->next->prev = phead;
free(head);
}
LTNode* ListFind(LTNode* phead, LTDateType x)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
void ListInsert(LTNode* pos, LTDateType x)
{
assert(pos);
LTNode* posPrev = pos->prev;
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
printf("開辟空間失敗!!\n");
exit(-1);
}
newnode->data = x;
posPrev->next = newnode;
newnode->prev = posPrev;
newnode->next = pos;
pos->prev = newnode;
}
void ListErase(LTNode* pos)
{
assert(pos);
LTNode* posPrev = pos->prev;
LTNode* posNext = pos->next;
posPrev->next = posNext;
posNext->prev = posPrev;
free(pos);
}
總結(jié):鏈表和順序表的區(qū)別
到此這篇關(guān)于C語言鏈表的文章就介紹到這了,更多相關(guān)C語言鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C++ 是一門面向?qū)ο蟮木幊陶Z言，理解 C++，首先要理解類（Class）和對象（Object）這兩個概念。下面和小編一起來學(xué)習(xí)吧2021-10-10
C++中對象的常引用、動態(tài)建立和釋放相關(guān)知識講解
這篇文章主要介紹了C++中對象的常引用、動態(tài)建立和釋放相關(guān)知識講解,是C++入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下2015-09-09
C語言這門課程在計算機的基礎(chǔ)教學(xué)中一直占有比較重要的地位，然而要想突破C語言的學(xué)習(xí)，對指針的掌握是非常重要的，本文將具體針對指針的基礎(chǔ)做詳盡的介紹2022-05-05
這篇文章主要為大家介紹了C語言算法之金手指摩爾投票法手撕絕大多數(shù)問題的示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助2022-02-02
C語言是一種編譯型語言，需要把源文件進行編譯之后才能運行，它的編譯過程是：預(yù)處理：展開頭文件、宏替換，去掉注釋，條件編譯；編譯：檢查語法，生成匯編；匯編：把生成的匯編文件匯編成機器碼；鏈接：鏈接到一起生成可執(zhí)行程序2022-04-04
今天小編就為大家分享一篇解決C語言數(shù)組元素循環(huán)右移的問題，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2018-07-07
這篇文中主要為大家詳細介紹了如何利用C語言實現(xiàn)經(jīng)典的掃雷小游戲。掃雷小游戲主要是利用字符數(shù)組、循環(huán)語句和函數(shù)實現(xiàn)，感興趣的小伙伴可以了解一下2022-10-10
C++ OpenCV實戰(zhàn)之文檔照片轉(zhuǎn)換成掃描文件
這篇文章主要為大家介紹一個C++?OpenCV的實戰(zhàn)——文檔照片轉(zhuǎn)換成掃描文件，文中的示例代碼講解詳細，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2022-09-09
這篇文章主要為大家詳細介紹了C++的指針，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
在使用c++做界面開發(fā)的時候，尤其是實現(xiàn)白板功能時需要自己實現(xiàn)一套撤銷重做功能.如果是qt則有QUndoable對象，可以直接拿來用。但是如果是使用gdi繪圖，則可能需要自己實現(xiàn)了。本文就來用C++實現(xiàn)自定義撤銷重做功能，需要的可以參考一下2022-12-12