您好,登錄后才能下訂單哦!
本篇內(nèi)容介紹了“C語言如何實現(xiàn)單鏈表操作”的有關(guān)知識,在實際案例的操作過程中,不少人都會遇到這樣的困境,接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧!希望大家仔細閱讀,能夠?qū)W有所成!
概念:鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲結(jié)構(gòu),數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈 接次序?qū)崿F(xiàn)的 。
注意:
1. 從上圖可以看出,鏈式結(jié)構(gòu)在邏輯上是連續(xù)的,但是在物理上不一定是連續(xù)
2. 現(xiàn)實中的節(jié)點一般是從堆上申請出來的
3. 從對上申請的空間,是按照一定的策略來分配的,兩次申請的空間可能連續(xù),也可能不連續(xù)
實際中鏈表的結(jié)構(gòu)非常多樣,以下情況組合起來就有8種鏈表結(jié)構(gòu):
1、單向或者雙向鏈表
2、帶頭或者不帶頭鏈表
3、循環(huán)或非循環(huán)鏈表
最常用的有兩種:無頭單向非循環(huán)鏈表、帶頭雙向循環(huán)鏈表
無頭單向非循環(huán)鏈表:結(jié)構(gòu)簡單,一般不會單獨用來存數(shù)據(jù)。實際中更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié) 構(gòu),如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多。
帶頭雙向循環(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)了就知道了。
typedef int SLTDataType;// typedef struct SListNode { int data;//val,存儲的數(shù)據(jù),此處假設(shè)存儲的數(shù)據(jù)為int型 struct SListNode* next;//存儲下一個節(jié)點的位置 }SListNode,SLN;
void SListPrint(SListNode* phead) { SListNode* cur = phead; while (cur != NULL) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); }
void SListPushBack(SListNode** pphead, SLTDataType x) { SListNode* newnode = BuySListNode(x); if (*pphead == NULL) { *pphead = newnode; } else { //找尾 SListNode* tail = *pphead; while (tail->next != NULL) { tail = tail->next; } tail->next = newnode; } }
在找尾的過程中,務(wù)必不能寫成下面的代碼:
while(tail!=NULL) { tail = tail->next; } tail->next = newnode;
當然,上面的介紹的是尾刪的情況。
尾插其實也是類似的,尾插的話像上面的代碼中,當tail!=NULL
不成立之后,tail等于空,然后執(zhí)行賦值操作,tail->next = newnode
這行代碼相當于下面的代碼:
(*tail).next
,此處相當于是對空指針進行解引用,其實就是非法訪問了,并還試圖非法修改未授權(quán)內(nèi)存中的數(shù)據(jù),這將必然會引發(fā)程序的崩潰。而且也并沒有將新節(jié)點的地址存儲到之前為節(jié)點的next中。
這個地方需要弄明白鏈表進行遍歷的根本原理:
鏈表是一個相對靜態(tài)的存儲在堆區(qū)中的數(shù)據(jù)空間,我們通過改變棧區(qū)中的局部變量tail中的數(shù)據(jù)(即每一個鏈表節(jié)點的地址)來進行遍歷,之所以能夠通過tail變量能夠進行訪問并且修改節(jié)點數(shù)據(jù)的原因就是因為tail的數(shù)據(jù)類型是SListNode*,即指向節(jié)點的指針,指針的類型決定了對指針解引用能夠訪問的數(shù)據(jù)類型,所以*tail能夠訪問堆區(qū)中的節(jié)點的數(shù)據(jù)并且能夠進行修改。
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; }
void SListPushFront(SListNode** pphead, SLTDataType x) { SListNode* newnode = BuySListNode(x); newnode->next = *pphead; *pphead = newnode; }
需要考慮三種情況:
空
一個節(jié)點
多個節(jié)點
兩種寫法:
第一種:
void SListPopBack(SListNode** pphead) { assert(pphead); if (*pphead == NULL)//空鏈表 { return; } else if ((*pphead)->next == NULL)//一個節(jié)點 { free(*pphead);//*pphead就是plist的值 *pphead = NULL; } else//多個節(jié)點 { SListNode* tail = *pphead; SListNode* prev = NULL;//為什么要置為空呢?因為這個地方相當于是指向第一個節(jié)點之前的節(jié)點,這個節(jié)點并不存在,設(shè)為空 while (tail->next != NULL) { prev = tail; tail = tail->next; } free(tail); tail = NULL; prev->next = NULL; } }
這種方式在面對只有一個節(jié)點時也不會出現(xiàn)問題。
第二種:
void SListPopBack(SListNode** pphead) { assert(pphead); if (*pphead == NULL)//空鏈表 { return; } else if ((*pphead)->next == NULL)//一個節(jié)點 { free(*pphead);//*pphead就是plist的值 *pphead = NULL; } else//多個節(jié)點 { SListNode* tail = *pphead; while (tail->next->next != NULL) { tail = tail->next; } free(tail->next);//釋放尾節(jié)點 tail->next = NULL;//將新尾節(jié)點的next置為NULL } }
void SListPopFront(SListNode** pphead) { assert(pphead); if (*pphead == NULL)//空鏈表 { return; } else//非空鏈表 { SListNode* next = (*pphead)->next;//next作為臨時變量存放的是被刪除的節(jié)點中next存儲的第二個節(jié)點的地址 free(*pphead); *pphead = next; } }
void SListInsertBefore(SListNode** pphead, SListNode* pos,SLTDataType x) { assert(pphead); if (*pphead == pos)//pos是第一個節(jié)點,相當于頭插 { SListPushFront(pphead, x); } else { SListNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } SListNode* newnode = BuySListNode(x); prev->next = newnode; newnode->next = pos; } }
兩種實現(xiàn)方式:
方式一:
void SListInsertAfter(SListNode* pos, SLTDataType x) { assert(pos); SListNode* newnode = BuySListNode(x); newnode->next = pos->next; pos->next = newnode; //這兩行代碼順序是固定的,只能這個順序,無法進行改變 }
圖示:
方式二:
void SListInsertAfter(SListNode* pos, SLTDataType x) { assert(pos); SListNode* next = pos->next; SListNode* newnode = BuySListNode(x); newnode->next = next; pos->next = newnode; //這兩行代碼可以任意改變順序,誰先誰后都不影響最后的結(jié)果 }
圖示:
void SListErase(SListNode** pphead, SListNode* pos) { assert(pphead); assert(pos); if (pos == *pphead)//當pos為頭節(jié)點的時候 { SListPopFront(pphead); } else//當pos為非頭節(jié)點的時候 { SListNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); pos = NULL; } }
圖示:
void SListEraseBefore(SListNode** pphead, SListNode* pos)//pos即為任意位置 { assert(pphead); assert(pos); if (pos == *pphead) { return; } else if(pos==(*pphead)->next) { SListPopFront(pphead); } else { SListNode* prev = *pphead;//prev用來存儲pos的前一個位置的前一個位置 while (prev->next->next != pos) { prev = prev->next; } SListNode* next = prev->next;//保存pos前一個節(jié)點的地址 prev->next = prev->next->next;//將prev和pos的兩個節(jié)點進行連接 free(next);//刪除pos的前一個節(jié)點 } }
void SListEraseAfter(SListNode* pos) { assert(pos); SListNode* next = pos->next; if (next == NULL)//當pos是最后一個節(jié)點的時候 { return; } else { pos->next = next->next; free(next); next = NULL; } }
圖示:
void SListDestory(SListNode** pphead) { assert(pphead); SListNode* cur = *pphead; SListNode* next = *pphead;//是為了存儲cur下一個節(jié)點的地址,因為free(cur)之后,cur指針指向的內(nèi)存中的數(shù)據(jù)可能已經(jīng)稱為亂碼了,即不能再正常的使用 while (cur) { next = cur->next; free(cur); cur = next; } *pphead = NULL; }
“C語言如何實現(xiàn)單鏈表操作”的內(nèi)容就介紹到這里了,感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注億速云網(wǎng)站,小編將為大家輸出更多高質(zhì)量的實用文章!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。