C語言?超詳細介紹與實現(xiàn)線性表中的無頭單向非循環(huán)鏈表
一、本章重點
- 無頭單向非循環(huán)鏈表介紹
- 無頭單向非循環(huán)鏈表常用接口實現(xiàn)
- 在線oj訓(xùn)練
二、鏈表介紹
概念:鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲結(jié)構(gòu),數(shù)據(jù)元素的邏輯順序是通過鏈表 中的指針鏈接次序?qū)崿F(xiàn)的。
簡單的說:鏈表就是一些結(jié)構(gòu)體相互關(guān)聯(lián)起來,而關(guān)聯(lián)的手段就是指針,通過存儲下一個結(jié)構(gòu)體的地址,就能挨個訪問存在結(jié)構(gòu)體里的數(shù)據(jù)。
相比于順序表來說。鏈表能夠解決順序表的一些缺點。
- 從內(nèi)存角度來說:無論是靜態(tài)順序表還是動態(tài)順序表都會有一定的內(nèi)存浪費,鏈表則是用一個節(jié)點申請一個節(jié)點,無內(nèi)存浪費。
- 從效率角度上來說:順序表不管是頭插還是中間插入與刪除都要移動數(shù)據(jù),時間復(fù)雜度是O(N)。而鏈表則只要改變指針指向即可達到插入和刪除的效果。
實際中要實現(xiàn)的鏈表的結(jié)構(gòu)非常多樣,以下情況組合起來就有8種鏈表結(jié)構(gòu):
1. 單向、雙向
2. 帶頭、不帶頭
3. 循環(huán)、非循環(huán)
帶頭:
存在一個哨兵位的節(jié)點,該節(jié)點不存儲任何有效數(shù)據(jù),屬于無效節(jié)點,但通過這個無效節(jié)點當(dāng)頭節(jié)點讓我們在某些方面使用會有一些優(yōu)勢。
比如,你頭插新節(jié)點時,不需要傳二級指針,因為我們的頭節(jié)點始終指向這個無效節(jié)點。
帶頭單向非循環(huán)鏈表
雙向:
指的是節(jié)點中不再只有一個指針,而是有兩個指針,一個指向前一個節(jié)點,另一個指向后一個節(jié)點。
無頭雙向非循環(huán)鏈表
循環(huán):
尾指針不再指向NULL,而是指向頭節(jié)點。?
無頭單向循環(huán)鏈表
三、無頭單向非循環(huán)鏈表常用接口實現(xiàn)
3.1動態(tài)申請一個節(jié)點
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é)點
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移除鏈表元素(力扣)
給你一個鏈表的頭節(jié)點?head
?和一個整數(shù)?val
?,請你刪除鏈表中所有滿足?Node.val == val
?的節(jié)點,并返回?新的頭節(jié)點?。
輸入: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.
就進行刪除,刪除步驟為prev->next==cur->next;cur=cur->next。迭代過程為:prev=cur,cur==cur->next。
特殊情況,如果要刪除的val為頭節(jié)點,則刪除步驟為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é)點?head
?,請你反轉(zhuǎn)鏈表,并返回反轉(zhuǎn)后的鏈表。
輸入:head = [1,2,3,4,5]
輸出:[5,4,3,2,1]
輸入:head = []
輸出:[]
這里提供一個頭插思路: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;此時如果next往后走,next=next->next;會出現(xiàn)NULL解引用的問題。
其次要考慮cur==NULL的問題,不然ListNode* next=cur->next也是對空指針解引用。
其實可以化簡為:
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語言?超詳細介紹與實現(xiàn)線性表中的無頭單向非循環(huán)鏈表的文章就介紹到這了,更多相關(guān)C語言 無頭單向非循環(huán)鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C語言修煉之路數(shù)據(jù)類型悟正法?解析存儲定風(fēng)魔上篇
使用編程語言進行編程時,需要用到各種變量來存儲各種信息。變量保留的是它所存儲的值的內(nèi)存位置。這意味著,當(dāng)您創(chuàng)建一個變量時,就會在內(nèi)存中保留一些空間。您可能需要存儲各種數(shù)據(jù)類型的信息,操作系統(tǒng)會根據(jù)變量的數(shù)據(jù)類型,來分配內(nèi)存和決定在保留內(nèi)存中存儲什么2022-02-02淺析VSCode tasks.json中的各種替換變量的意思 ${workspaceFolder} ${file} ${
這篇文章主要介紹了關(guān)于VSCode tasks.json中的各種替換變量的意思 ${workspaceFolder} ${file} ${fileBasename} ${fileDirname}等,本文給大家介紹的非常詳細,對大家的學(xué)習(xí)或工作具有參考借鑒價值,需要的朋友可以參考下2020-03-03Qt6遠程連接MySQL數(shù)據(jù)庫的簡單易上手版
在Qt應(yīng)用程序里,可實現(xiàn)遠程MySQL服務(wù)器的連接操作,本文就來介紹一下Qt6遠程連接MySQL數(shù)據(jù)庫,具有一定的參考價值,感興趣的可以了解一下2023-11-11