?作者簡(jiǎn)介：嵌入式入坑者，與大家一起加油，希望文章能夠幫助各位?。。?！
📃個(gè)人主頁(yè)：@rivencode的個(gè)人主頁(yè)
🔥系列專(zhuān)欄：玩轉(zhuǎn)數(shù)據(jù)結(jié)構(gòu)
💬推薦一款模擬面試、刷題神器，從基礎(chǔ)到大廠面試題👉點(diǎn)擊跳轉(zhuǎn)刷題網(wǎng)站進(jìn)行注冊(cè)學(xué)習(xí)
線性表
線性表（linear list）是n個(gè)具有相同特性的數(shù)據(jù)元素的有限序列。 線性表是一種在實(shí)際中廣泛使用的數(shù)據(jù)結(jié)構(gòu)，常見(jiàn)的線性表：順序表、鏈表、棧、隊(duì)列等，線性表在邏輯上是線性結(jié)構(gòu)，也就說(shuō)是連續(xù)的一條直線。但是在物理結(jié)構(gòu)（存儲(chǔ)結(jié)構(gòu)）上并不一定是連續(xù)的，線性表在物理上存儲(chǔ)時(shí)，通常以順序表和鏈?zhǔn)浇Y(jié)構(gòu)的形式存儲(chǔ)。
線性表的順序存儲(chǔ)—>順序表
是用一段物理地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)數(shù)據(jù)元素的線性結(jié)構(gòu)，一般情況下采用數(shù)組存儲(chǔ)。在數(shù)組上完成數(shù)據(jù)的增刪查改。
線性表的鏈?zhǔn)酱鎯?chǔ)
線性表中的數(shù)據(jù)結(jié)點(diǎn)在內(nèi)存中的位置是任意的，即邏輯上相鄰的數(shù)據(jù)元素在物理位置（內(nèi)存存儲(chǔ)的位置）上不一定相鄰。
鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)：
鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的缺點(diǎn)：
順序表因?yàn)橹挥袛?shù)據(jù)域，沒(méi)有指針域所以它的存儲(chǔ)密度為大1
不過(guò)這個(gè)問(wèn)題，一個(gè)結(jié)點(diǎn)也就多幾個(gè)指針，最多8個(gè)字節(jié)，所以若是在現(xiàn)代計(jì)算機(jī)這點(diǎn)空間已經(jīng)不算什么，不過(guò)如果是像單片機(jī)這種嵌入式設(shè)備內(nèi)存較小，所以還是會(huì)有一點(diǎn)點(diǎn)影響的
順序表的優(yōu)點(diǎn)：
順序表的缺點(diǎn)：
重慶分公司
重慶分公司
數(shù)據(jù)結(jié)點(diǎn)在內(nèi)存中的位置是任意的，即邏輯上是線性的數(shù)據(jù)元素在物理位置（內(nèi)存存儲(chǔ)的位置）上不一定相鄰。
結(jié)點(diǎn)為什么在內(nèi)存中是隨機(jī)存儲(chǔ)的呢
因?yàn)槲覀儺a(chǎn)生一個(gè)結(jié)點(diǎn)要給他分配內(nèi)存是動(dòng)態(tài)分配出來(lái)的（malloc），而分配的結(jié)點(diǎn)的內(nèi)存的地址是隨機(jī)的，所以結(jié)點(diǎn)的地址是隨機(jī)的，也就是說(shuō)結(jié)點(diǎn)在內(nèi)存中的存儲(chǔ)是隨機(jī)的。
單鏈表的一個(gè)結(jié)點(diǎn)
我們只要知道一個(gè)結(jié)構(gòu)體的指針（地址），就能訪問(wèn)該結(jié)構(gòu)體的成員（如果成員里面又包含下一個(gè)結(jié)點(diǎn)（結(jié)構(gòu)體）指針，又可以訪問(wèn)下一個(gè)結(jié)點(diǎn)的成員）
若基礎(chǔ)不好的先請(qǐng)參考：
《指針詳解》
《結(jié)構(gòu)體詳解》
其實(shí)鏈表你把結(jié)構(gòu)體與指針搞明白了，鏈表真的隨便拿捏。
不帶頭結(jié)點(diǎn)單向不循序鏈表：
當(dāng)鏈表為空時(shí)，頭指針指向空，當(dāng)鏈表不為空時(shí)頭指針必須指向第一個(gè)結(jié)點(diǎn)
void SListPrint(SLTNode *phead)
{SLTNode *cur = phead;
while (cur != NULL)
{printf("%d->", cur->data);
cur=cur->next;
}
printf("NULL\n");
}
//清空單鏈表
void SListClear(SLTNode **pphead)
{SLTNode *cur = *pphead;
SLTNode *next = NULL;
while (cur != NULL)
{next = cur->next;
free(cur);
cur = next;
}
*pphead = NULL;
}
如果要改變頭指針的值，雖然頭指針是一個(gè)指針，但是指針一樣有它的地址，如果在一個(gè)函數(shù)中要改變它的值，照樣要傳頭指針的地址，在解引用改變頭指針的值，如果你只是值傳遞，則傳過(guò)去的只是該頭指針的臨時(shí)拷貝，一旦出函數(shù)會(huì)自動(dòng)銷(xiāo)毀并不會(huì)影響頭指針本身的值。
SLTNode* CreateSListNode(SLTDataType x)
{SLTNode* NewNode = (SLTNode*)malloc(sizeof(SLTNode));
NewNode->data = x;
NewNode->next = NULL;
return NewNode;
}因?yàn)椴迦朐貢r(shí)都先要?jiǎng)?chuàng)建一個(gè)新結(jié)點(diǎn)，所以為了避免代碼冗余，將創(chuàng)建新結(jié)點(diǎn)單獨(dú)封裝成一個(gè)函數(shù)。
尾插結(jié)點(diǎn)void SListPushBack(SLTNode **pphead, SLTDataType x)
{SLTNode*NewNode = CreateSListNode(x);
//當(dāng)鏈表為空
if (*pphead == NULL)
{*pphead = NewNode;
}
else
{SLTNode* tail = *pphead;
while (tail->next != NULL)
{ tail=tail->next;
}
tail->next = NewNode;
}
}
不要寫(xiě)了if不寫(xiě)else，搞得后面又插入一個(gè)結(jié)點(diǎn)
//鏈表頭部插入一個(gè)節(jié)點(diǎn)
void SListPushFront(SLTNode **pphead, SLTDataType x)
{SLTNode*NewNode = CreateSListNode(x);
NewNode->next = *pphead;
*pphead = NewNode;
}
void SListPopBack(SLTNode **pphead)
{//鏈表為空
if (*pphead == NULL)
{return;
}
//只有一個(gè)節(jié)點(diǎn)
else if ((*pphead)->next == NULL)
{free(*pphead);
*pphead = NULL;
}
//有多個(gè)節(jié)點(diǎn)
else
{SLTNode*prev = NULL;
SLTNode*tail = *pphead;
while (tail->next != NULL)
{ prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}
}
有以下幾種情況：
void SListPopFront(SLTNode **pphead)
{if (*pphead == NULL)
{return;
}
SLTNode *next = (*pphead)->next;
free(*pphead);
*pphead = next;
}
查找值為x的節(jié)點(diǎn)并返回節(jié)點(diǎn)的指針
//查找值為x的節(jié)點(diǎn)并返回節(jié)點(diǎn)的指針
SLTNode * SListFind(SLTNode *phead, SLTDataType x)
{SLTNode *cur = phead;
while (cur != NULL)
{if (cur->data == x)
{ //找到返回該結(jié)點(diǎn)指針
return cur;
}
cur = cur->next;
}
//找不到返回NULL指針
return NULL;
}在pos指針指向的結(jié)點(diǎn)的前一個(gè)位置插入一個(gè)結(jié)點(diǎn)
//在pos指針前一個(gè)插入一個(gè)節(jié)點(diǎn)
void SListInsert(SLTNode **pphead, SLTNode *pos, SLTDataType x)
{//pos在第一個(gè)節(jié)點(diǎn)，相當(dāng)與頭插
if (*pphead== pos)
{SListPushFront(pphead, x);
}
else
{SLTNode *NewNode = CreateSListNode(x);
SLTNode *prev = *pphead;
while (prev->next != pos)
{ prev = prev->next;
}
prev->next = NewNode;
NewNode->next = pos;
}
}
如果pos的位置是第一個(gè)結(jié)點(diǎn)，則在第一個(gè)結(jié)點(diǎn)前一個(gè)插入結(jié)點(diǎn)則為頭插，直接調(diào)用頭插的接口函數(shù)即可。
pos在其他位置：
void SListErese(SLTNode **pphead, SLTNode *pos)
{if (*pphead == pos)
{SListPopFront(pphead);
}
else
{SLTNode *prev = *pphead;
while (prev->next != pos)
{ prev = prev->next;
}
prev->next=pos->next;
free(pos);
}
}
一樣的如果pos的位置是第一個(gè)結(jié)點(diǎn)，則在第一個(gè)結(jié)點(diǎn)前一個(gè)刪除結(jié)點(diǎn)則為頭刪，直接調(diào)用頭刪的接口函數(shù)即可。
pos在其他位置：
頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)(存儲(chǔ)該節(jié)點(diǎn)的地址)。如果鏈表中有頭結(jié)點(diǎn)，則頭指針指向頭結(jié)點(diǎn)；若鏈表中沒(méi)有頭結(jié)點(diǎn)，則頭指針指向鏈表中第一個(gè)數(shù)據(jù)結(jié)點(diǎn)。
不存儲(chǔ)任何數(shù)據(jù)，若鏈表有頭結(jié)點(diǎn)則頭指針一直指向頭指針。
鏈表帶頭結(jié)點(diǎn)的優(yōu)點(diǎn)：
當(dāng)鏈表為空表時(shí)，插入，刪除結(jié)點(diǎn)都是在頭結(jié)點(diǎn)后面，頭結(jié)點(diǎn)指向了第一個(gè)帶數(shù)據(jù)的結(jié)點(diǎn)。
當(dāng)我們單鏈表無(wú)頭結(jié)點(diǎn)時(shí)當(dāng)我們頭插，頭插的時(shí)候，我們都需要移動(dòng)頭指針的位置指向新的第一個(gè)結(jié)點(diǎn)，當(dāng)鏈表為空時(shí)又要將頭結(jié)點(diǎn)置NULL，這些操作我們都需要去改變頭指針的值，而改變頭指針要傳頭指針的地址的，用二級(jí)指針來(lái)操作，無(wú)疑是增加了編程的難度，如果鏈表有頭結(jié)點(diǎn)，而頭指針一直指向頭結(jié)點(diǎn)，不管是頭刪，頭插，都是在頭結(jié)點(diǎn)后面增加刪除，而頭指針一直指向頭結(jié)點(diǎn)不用發(fā)生改變，只需要一級(jí)指針就搞定
注意：
循環(huán)鏈表中沒(méi)有NULL指針，故遍歷鏈表時(shí)，其終止條件是判斷是不是等于頭指針。
所以雙向鏈表：在單鏈表的每一個(gè)結(jié)點(diǎn)再增加一個(gè)指向其直接前驅(qū)的指針域prev，這樣鏈表中就形成了有兩個(gè)方向不同的鏈
單向不帶頭不循環(huán)
單向帶頭不循環(huán)
單向不帶頭循環(huán)
單向帶頭循環(huán)
雙向不帶頭不循環(huán)
prev的值也為空
雙向不帶頭循環(huán)
雙向帶頭不循環(huán)
prev的值也為空
雙向帶頭循環(huán)
ListNode*CreateListNode(LTDataType x)
{ListNode*NewNode = (ListNode*)malloc(sizeof(ListNode));
NewNode->data = x;
NewNode->next = NULL;
NewNode->prev = NULL;
return NewNode;
}一個(gè)新的結(jié)點(diǎn)，先將next，prev置空
鏈表初始化//鏈表初始化
ListNode *ListInit()
{ListNode*phead = CreateListNode(0);
phead->next = phead;
phead->prev = phead;
return phead;
}空表
void ListDestory(ListNode**pphead)
{ListNode*cur = (*pphead)->next;
while (cur != *pphead)
{ ListNode* next = cur->next;
free(cur);
cur = next;
}
free(*pphead);
*pphead = NULL;
}
//清空鏈表
void ListClear(ListNode*phead)
{ListNode*cur = phead->next;
while (cur != phead)
{ListNode* next = cur->next;
free(cur);
cur = next;
}
phead->next = phead;
phead->prev = phead;
}只清空的話(huà)不需要釋放頭結(jié)點(diǎn)，不過(guò)要將頭結(jié)點(diǎn)的兩個(gè)指針域都指向自己（回到空表狀態(tài)）
打印鏈表//打印鏈表
void Listprint(ListNode*phead)
{ListNode*cur = phead->next;
while (cur != phead)
{printf("%d ",cur->data);
cur = cur->next;
}
printf("NULL\n");
}
遍歷是看是否遍歷到了頭結(jié)點(diǎn)才停下來(lái)。
尾插結(jié)點(diǎn)//尾插
void ListPushBack(ListNode*phead, LTDataType x)
{ assert(phead != NULL);
ListNode*NewNode = CreateListNode(x);
ListNode*tail = phead->prev;
tail->next = NewNode;
NewNode->prev = tail;
NewNode->next = phead;
phead->prev = NewNode;
}
可以怎么寫(xiě)：但是這里水太深你可能把握不住
我們只要抓住一點(diǎn)：把要操作的結(jié)點(diǎn)事先存儲(chǔ)起來(lái)，不管我們?cè)趺催B接結(jié)點(diǎn)，我們都找的到要操作的結(jié)點(diǎn)
//頭插
void ListPushFront(ListNode*phead, LTDataType x)
{ assert(phead != NULL);
ListNode*NewNode = CreateListNode(x);
ListNode*first = phead->next;
phead->next = NewNode;
NewNode->prev = phead;
NewNode->next = first;
first->prev = NewNode;
}//尾刪
void ListPopBack(ListNode*phead)
{ assert(phead != NULL);
assert(phead->next != phead);
ListNode*tail = phead->prev;
ListNode*prev = tail->prev;
prev->next = phead;
phead->prev = prev;
free(tail);
tail = NULL;
}
//頭刪
void ListPopFront(ListNode*phead)
{ assert(phead != NULL);
assert(phead->next != phead);
ListNode*first = phead->next;//除掉頭結(jié)點(diǎn)第一個(gè)結(jié)點(diǎn)
ListNode*second = first->next;//除掉頭結(jié)點(diǎn)第二個(gè)結(jié)點(diǎn)
phead->next = second;
second->prev = phead;
free(first);
first = NULL;
}
查找節(jié)點(diǎn)值為x的結(jié)點(diǎn)，返回指向節(jié)點(diǎn)的指針
//查找節(jié)點(diǎn)值為x，返回指向節(jié)點(diǎn)的指針
ListNode* ListFind(ListNode*phead, LTDataType x)
{ ListNode*cur = phead->next;
while (cur != phead)
{ if (cur->data == x)
{ return cur;
}
cur = cur->next;
}
return NULL;
}//在pos指針指向的節(jié)點(diǎn)前插入一個(gè)節(jié)點(diǎn)
void ListInsert(ListNode*pos, LTDataType x)
{ assert(pos != NULL);
ListNode*NewNode = CreateListNode(x);
ListNode*prev = pos->prev;
prev->next = NewNode;
NewNode->prev = prev;
NewNode->next = pos;
pos->prev = NewNode;
}
void ListErase(ListNode*pos)
{ assert(pos !=NULL);
ListNode*next = pos->next;
ListNode*prev = pos->prev;
prev->next = next;
next->prev = prev;
free(pos);
pos = NULL;
}//鏈表長(zhǎng)度
int ListLength(ListNode*phead)
{int len = 0;
ListNode*cur = phead->next;
while (cur != phead)
{len++;
cur = cur->next;
}
return len;
}只要搞懂結(jié)構(gòu)體指針，明白鏈表的概念，直接拿捏，相信很多人學(xué)完了鏈表還是不知道鏈表會(huì)用在什么地方，因?yàn)槲覀兤綍r(shí)編程基本上用不到鏈表，但是鏈表在操作系統(tǒng)中的使用非常廣泛，所以鏈表是非常重要重要的數(shù)據(jù)結(jié)構(gòu)，有興趣的可以看看在實(shí)際項(xiàng)目中鏈表的應(yīng)用->《FreeRTOS實(shí)時(shí)操作系統(tǒng)-鏈表的源碼解析》
結(jié)束語(yǔ)：
最近發(fā)現(xiàn)一款刷題神器，如果大家想提升編程水平，玩轉(zhuǎn)C語(yǔ)言指針，還有常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)（最重要的是鏈表和隊(duì)列）后面嵌入式學(xué)習(xí)操作系統(tǒng)的時(shí)如freerots、RT-Thread等操作系統(tǒng)，鏈表與隊(duì)列知識(shí)大量使用。
大家可以點(diǎn)擊下面連接進(jìn)入?？途W(wǎng)刷題
點(diǎn)擊跳轉(zhuǎn)進(jìn)入網(wǎng)站(C語(yǔ)言方向)
點(diǎn)擊跳轉(zhuǎn)進(jìn)入網(wǎng)站(數(shù)據(jù)結(jié)構(gòu)算法方向)
你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧
