C語言?超詳細(xì)介紹與實(shí)現(xiàn)線性表中的無頭單向非循環(huán)鏈表
一、本章重點(diǎn)
- 無頭單向非循環(huán)鏈表介紹
- 無頭單向非循環(huán)鏈表常用接口實(shí)現(xiàn)
- 在線oj訓(xùn)練
二、鏈表介紹
概念：鏈表是一種物理存儲(chǔ)結(jié)構(gòu)上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表 中的指針鏈接次序?qū)崿F(xiàn)的。
簡單的說：鏈表就是一些結(jié)構(gòu)體相互關(guān)聯(lián)起來，而關(guān)聯(lián)的手段就是指針，通過存儲(chǔ)下一個(gè)結(jié)構(gòu)體的地址，就能挨個(gè)訪問存在結(jié)構(gòu)體里的數(shù)據(jù)。
相比于順序表來說。鏈表能夠解決順序表的一些缺點(diǎn)。
- 從內(nèi)存角度來說：無論是靜態(tài)順序表還是動(dòng)態(tài)順序表都會(huì)有一定的內(nèi)存浪費(fèi)，鏈表則是用一個(gè)節(jié)點(diǎn)申請一個(gè)節(jié)點(diǎn)，無內(nèi)存浪費(fèi)。
- 從效率角度上來說：順序表不管是頭插還是中間插入與刪除都要移動(dòng)數(shù)據(jù)，時(shí)間復(fù)雜度是O（N）。而鏈表則只要改變指針指向即可達(dá)到插入和刪除的效果。
實(shí)際中要實(shí)現(xiàn)的鏈表的結(jié)構(gòu)非常多樣，以下情況組合起來就有8種鏈表結(jié)構(gòu)：
1. 單向、雙向
2. 帶頭、不帶頭
3. 循環(huán)、非循環(huán)
帶頭：
存在一個(gè)哨兵位的節(jié)點(diǎn)，該節(jié)點(diǎn)不存儲(chǔ)任何有效數(shù)據(jù)，屬于無效節(jié)點(diǎn)，但通過這個(gè)無效節(jié)點(diǎn)當(dāng)頭節(jié)點(diǎn)讓我們在某些方面使用會(huì)有一些優(yōu)勢。
比如，你頭插新節(jié)點(diǎn)時(shí)，不需要傳二級指針，因?yàn)槲覀兊念^節(jié)點(diǎn)始終指向這個(gè)無效節(jié)點(diǎn)。
帶頭單向非循環(huán)鏈表
雙向：
指的是節(jié)點(diǎn)中不再只有一個(gè)指針，而是有兩個(gè)指針，一個(gè)指向前一個(gè)節(jié)點(diǎn)，另一個(gè)指向后一個(gè)節(jié)點(diǎn)。
無頭雙向非循環(huán)鏈表
循環(huán)：
尾指針不再指向NULL，而是指向頭節(jié)點(diǎn)。?
無頭單向循環(huán)鏈表
三、無頭單向非循環(huán)鏈表常用接口實(shí)現(xiàn)
3.1動(dòng)態(tài)申請一個(gè)節(jié)點(diǎn)
SLTNode* BuySListNode(SLDataType x)
{
SLTNode* newnode = malloc(sizeof(SLTNode));
if (newnode == NULL)
{
printf("malloc fail\n");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
3.2單鏈表打印
void SListPrint(SLTNode* phead)
{
SLTNode* cur = phead;
while (cur)
{
printf("%d->", cur->data);
cur = cur->next;
}
printf("NULL\n");
}
3.3單鏈表尾插
void SListPushBack(SLTNode** pphead, SLDataType x)
{
if (*pphead==NULL)
{
*pphead = BuySListNode(x);
return;
}
else
{
SLTNode* tail;
tail = *pphead;
while (tail->next)
{
tail = tail->next;
}
tail->next = BuySListNode(x);
return;
}
}
3.4單鏈表的頭插
void SListPushFront(SLTNode** pphead, SLDataType x)
{
SLTNode* newnode = BuySListNode(x);
newnode->next = *pphead;
*pphead = newnode;
}
3.5單鏈表的尾刪
void SListPopBack(SLTNode** pphead)
{
if (*pphead == NULL)
{
return;
}
else if((*pphead)->next==NULL)
{
*pphead = NULL;
}
else
{
SLTNode* prev = NULL;
SLTNode* tail = *pphead;
while (tail->next)
{
prev = tail;
tail = tail->next;
}
free(tail);
prev->next = NULL;
}
}
3.6單鏈表頭刪
void SListPopFront(SLTNode** pphead)
{
if (*pphead == NULL)
{
return;
}
else
{
SLTNode* temp = *pphead;
(*pphead) = (*pphead)->next;
free(temp);
}
}
3.7單鏈表查找
SLTNode* SListSearch(SLTNode* phead, SLDataType x)
{
while (phead)
{
if (phead->data == x)
{
return phead;
}
phead = phead->next;
}
return NULL;
}
3.8單鏈表在pos位置之前插入x
void SListInsert(SLTNode** pphead, SLTNode* pos, SLDataType x)
{
SLTNode* newnode = BuySListNode(x);
if (*pphead == NULL)
{
return;
}
else if(*pphead==pos)
{
newnode->next = pos;
*pphead = newnode;
}
else
{
SLTNode* cur = *pphead;
while (cur->next != pos)
{
cur = cur->next;
}
newnode->next = pos;
cur->next = newnode;
}
}
3.9單鏈表刪除pos位置的節(jié)點(diǎn)
void SListErase(SLTNode** phead, SLTNode* pos)
{
if (*phead == NULL)
{
return;
}
else if (*phead == pos)
{
*phead == NULL;
}
else
{
SLTNode* cur = *phead;
while (cur->next != pos)
{
cur = cur->next;
}
cur->next = pos->next;
free(pos);
}
}
四、在線oj訓(xùn)練
4.1移除鏈表元素（力扣）
給你一個(gè)鏈表的頭節(jié)點(diǎn)?head?和一個(gè)整數(shù)?val?，請你刪除鏈表中所有滿足?Node.val == val?的節(jié)點(diǎn)，并返回?新的頭節(jié)點(diǎn)?。
輸入：head = [1,2,6,3,4,5,6], val = 6
輸出：[1,2,3,4,5]
輸入：head = [7,7,7,7], val = 7
輸出：[]
?思路：
前后指針（跟班指針），初始轉(zhuǎn)態(tài)prev指向NULL，cur指向head，如果出現(xiàn)cur->val==val.
就進(jìn)行刪除，刪除步驟為prev->next==cur->next;cur=cur->next。迭代過程為：prev=cur,cur==cur->next。
特殊情況，如果要?jiǎng)h除的val為頭節(jié)點(diǎn)，則刪除步驟為head=cur->next;free(cur);cur=head。
代碼參考：
typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val)
{
ListNode* cur=head;
ListNode* prev=NULL;
while(cur)
{
if(cur->val==val)
{
if(cur==head)
{
head=cur->next;
free(cur);
cur=head;
}
else
{
prev->next=cur->next;
cur=cur->next;
}
}
else
{
prev=cur;
cur=cur->next;
}
}
return head;
}
4.2反轉(zhuǎn)單鏈表（力扣）
給你單鏈表的頭節(jié)點(diǎn)?head?，請你反轉(zhuǎn)鏈表，并返回反轉(zhuǎn)后的鏈表。
輸入：head = [1,2,3,4,5]
輸出：[5,4,3,2,1]
輸入：head = []
輸出：[]
這里提供一個(gè)頭插思路：newhead=NULL,將head中的數(shù)據(jù)從左到右依次頭插至newhead鏈表中。
typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head)
{
ListNode* newhead=NULL;
ListNode* cur=head;
if(cur==NULL)
{
return cur;
}
ListNode* next=cur->next;
while(cur)
{
cur->next=newhead;
newhead=cur;
cur=next;
if(next)
next=next->next;
}
return newhead;
}
注意:結(jié)束條件是cur==NULL;此時(shí)如果next往后走，next=next->next;會(huì)出現(xiàn)NULL解引用的問題。
其次要考慮cur==NULL的問題，不然ListNode* next=cur->next也是對空指針解引用。
其實(shí)可以化簡為：
struct ListNode* reverseList(struct ListNode* head)
{
struct ListNode* cur = head;
struct ListNode* newhead = NULL;
while(cur)
{
struct ListNode* next = cur->next;
cur->next = newhead;
newhead = cur;
cur = next;
}
return newhead;
}
到此這篇關(guān)于C語言?超詳細(xì)介紹與實(shí)現(xiàn)線性表中的無頭單向非循環(huán)鏈表的文章就介紹到這了,更多相關(guān)C語言 無頭單向非循環(huán)鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了C++ bitset用法，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-08-08
C++機(jī)房預(yù)約系統(tǒng)實(shí)現(xiàn)流程實(shí)例
這篇文章主要介紹了C++機(jī)房預(yù)約系統(tǒng)實(shí)現(xiàn)流程，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)吧2022-10-10
這篇文章主要為大家詳細(xì)介紹了如何通過C++實(shí)現(xiàn)三種不同版本的通訊錄（動(dòng)態(tài)版本、靜態(tài)版本、文件版本），文中的示例代碼講解詳細(xì)，希望對大家有所幫助2022-11-11
C++ 流插入和流提取運(yùn)算符的重載的實(shí)現(xiàn)
這篇文章主要介紹了C++ 流插入和流提取運(yùn)算符的重載的實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-12-12
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)簡單版三子棋，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-10-10
繼友元知識過后，就到了今天的C++運(yùn)算符重載的內(nèi)容了，運(yùn)算符重載是C++里比較重要的內(nèi)容。這篇博文不會(huì)一下子講完各種運(yùn)算符重載，因?yàn)樘嗔肆艘膊缓梦照莆?，所以運(yùn)算符重載我準(zhǔn)備分多次記錄和分享，那么接下來進(jìn)入正文2022-11-11
這篇文章主要介紹了EasyC++單獨(dú)編譯，在上一篇當(dāng)中，我們編寫好了頭文件coordin.h，現(xiàn)在我們要完成它的實(shí)現(xiàn)。需要的小伙伴可以先學(xué)習(xí)上一篇內(nèi)容然后一起與小編一起進(jìn)入本篇內(nèi)容一起學(xué)習(xí)吧2021-12-12
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)Huffman的編解碼，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-04-04
C++?中如何結(jié)束?while?(cin>>str)?的輸入
這篇文章主要介紹了C++?中如何結(jié)束?while?(cin>>str)?的輸入，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-07-07
這篇文章主要介紹了C++中的函數(shù)概念,是C++入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下2015-09-09