您好,登錄后才能下訂單哦!
這篇“C語(yǔ)言鏈表的操作有哪些”文章的知識(shí)點(diǎn)大部分人都不太理解,所以小編給大家總結(jié)了以下內(nèi)容,內(nèi)容詳細(xì),步驟清晰,具有一定的借鑒價(jià)值,希望大家閱讀完這篇文章能有所收獲,下面我們一起來(lái)看看這篇“C語(yǔ)言鏈表的操作有哪些”文章吧。
編譯工具:vs2019
開始之前:很有必要提醒大家注意二級(jí)指針的使用,為什么會(huì)用到二級(jí)指針,我的博客也有一些相關(guān)介紹,簡(jiǎn)單來(lái)說(shuō),傳值參數(shù)并不改變實(shí)參,傳址參數(shù)改變形參。
簡(jiǎn)單來(lái)說(shuō),就是一條鏈子連接成的表,上面的鏈接也有比較正式規(guī)矩的介紹。
與順序表相比,鏈表的最大特點(diǎn)就是不要求物理空間連續(xù),插入不需要移動(dòng)大量的數(shù)據(jù)
怎么去聯(lián)系各個(gè)結(jié)點(diǎn)呢?
從上圖其實(shí)不難發(fā)現(xiàn),搞個(gè)指針連接起來(lái)就行了。既要有數(shù)據(jù)域和指針域,注意一點(diǎn):最后一個(gè)元素的指針域?yàn)镹ULL。上面的箭頭實(shí)際并不存在,只是為了看起來(lái)比較直接,形象化起來(lái)。那要怎么去表示出來(lái)了?可以用結(jié)構(gòu)體的自引用。
之前并沒說(shuō)到鏈表的類型有哪些,根據(jù)類型的不同,我們實(shí)際上可以對(duì)其進(jìn)行分類,由于都是基于單鏈表實(shí)現(xiàn)操作,因此需要學(xué)好單鏈表,進(jìn)行深化學(xué)習(xí)。
單向/雙向鏈表
帶頭結(jié)點(diǎn)/不帶頭結(jié)點(diǎn)
鏈表的實(shí)現(xiàn)當(dāng)然離不開我們自己動(dòng)手去敲代碼了,這首先需要準(zhǔn)備好我們的編譯環(huán)境,vs2019,同時(shí),每次寫完一塊模板,我們要去測(cè)試一下有沒有bug,方便我們?nèi)フ义e(cuò)誤,進(jìn)行調(diào)試,這樣會(huì)大大減少我們的工作量。
鏈表我們?cè)撊绾稳ケ硎灸兀科鋵?shí),通過(guò)上面的例子,我們大致已經(jīng)知道,需要一個(gè)地方來(lái)存放數(shù)據(jù),另一個(gè)地方存放下一個(gè)結(jié)點(diǎn)的地址。我們可以通過(guò)結(jié)構(gòu)體來(lái)定義,具體代碼如下:
#include <stdio.h> typedef int SLTDataType; typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode;
后續(xù)操作會(huì)頻繁動(dòng)態(tài)開辟一個(gè)頭結(jié)點(diǎn),我們不妨把它封裝成一個(gè)函數(shù),便于后面方便使用。當(dāng)然,你如果覺得自己每次都可以自己寫的話,也不必寫成一個(gè)函數(shù)。
//創(chuàng)建新結(jié)點(diǎn) SLTNode* BuySListNode(SLTDataType x) { SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); newnode->data = x; newnode->next = NULL; return newnode; }
注意點(diǎn):新結(jié)點(diǎn)的指針域置為空!
先別急,我們先來(lái)試試水,先嘗試自己動(dòng)手寫一下打印的函數(shù)。
這里為了比較更加形象起來(lái),每次打印的時(shí)候都會(huì)用->來(lái)連接,同時(shí),最后用NULL結(jié)尾
void SListPrint(SLTNode* phead) { SLTNode*cur = phead; while (cur != NULL) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); }
什么是尾插?根據(jù)字面意思,就是將新結(jié)點(diǎn)插入到到鏈表的尾部。
為了讓大家更好理解,特地上網(wǎng)找了一張圖片,一起來(lái)看看把
每一次插入一個(gè)數(shù)都放在最后一個(gè)位置,同時(shí),最后一個(gè)結(jié)點(diǎn)的指針域置為空,關(guān)鍵的就是,我們?nèi)绾握业疆?dāng)前鏈表的尾結(jié)點(diǎn)呢?前面已經(jīng)說(shuō)了,最后一個(gè)結(jié)點(diǎn)的指針域?yàn)榭眨覀兛梢砸源藶橥黄泣c(diǎn)。注意:當(dāng)鏈表為空時(shí),你會(huì)怎么處理?想想。這里先不說(shuō)了,直接看看我們的代碼。
//尾插 void SListPushBack(SLTNode** pphead, SLTDataType x) { SLTNode* newnode = BuySListNode(x); if (*pphead == NULL) { *pphead = newnode; } else { SLTNode* tail = *pphead; while (tail->next != NULL) { tail = tail->next; } tail->next = newnode; } }
細(xì)心的你應(yīng)該注意到了,這里我們使用的都是二級(jí)指針pphead
因?yàn)榧僭O(shè)我們使用一級(jí)指針,直接傳入頭指針phead時(shí),頭指針本身就是一級(jí)指針的了,當(dāng)我們需要更改該指針指向的地址時(shí),改動(dòng)只會(huì)在函數(shù)內(nèi)部生效,main函數(shù)中的phead指針并沒有被改變。要想改變的話,就需要二級(jí)指針來(lái)進(jìn)行操作了
有尾插自然就會(huì)有頭插,相比較與尾插而言,頭插顯得更加簡(jiǎn)單了,直接把新的結(jié)點(diǎn)放在頭結(jié)點(diǎn)前不就ok了?
//頭插 void SListPushFront(SLTNode** pphead, SLTDataType x) { SLTNode* newnode = BuySListNode(x); newnode->next = *pphead; *pphead = newnode; }
好了,到這里,我們已經(jīng)有一些函數(shù)了,不急,我們先來(lái)測(cè)試測(cè)試效果如何
void TestSList1() { SLTNode* plist = NULL; SListPushBack(&plist, 1); SListPushBack(&plist, 2); SListPushBack(&plist, 3); SListPushBack(&plist, 4); SListPushFront(&plist, 0); SListPrint(plist); } int main() { TestSList1(); }
運(yùn)行結(jié)果如下:
我們必須養(yǎng)成邊寫代碼邊測(cè)試的習(xí)慣,這有利于我們及時(shí)發(fā)現(xiàn)自己的錯(cuò)誤,不易導(dǎo)致后面出現(xiàn)一大堆bug而自己卻不知道錯(cuò)在哪。當(dāng)然,除此之外,我們還可以通過(guò)調(diào)試的方法,快速準(zhǔn)確發(fā)現(xiàn)自己的bug,這也是我們需要養(yǎng)成的。這些都是需要我們?nèi)リP(guān)注的點(diǎn)。
好啦,下面我不會(huì)在像上面那么詳細(xì)的說(shuō)明了,我們直接來(lái)個(gè)頭刪尾刪
有頭插尾插,自然有頭刪尾刪,其實(shí),不知道你們發(fā)現(xiàn),不管是插還是刪,關(guān)于頭部的操作都是比較簡(jiǎn)單了,我們先來(lái)個(gè)開胃菜,頭刪:可不能直接刪哦,我們要記錄頭結(jié)點(diǎn)的下一個(gè)位置,如何直接刪了頭結(jié)點(diǎn)的話,那就麻煩,會(huì)造成野指針的,自己好好捋捋。
//頭刪 void SListpopFront(SLTNode**pphead) { SLTNode* next = (*pphead)->next; free(*pphead); *pphead = next; }
尾刪:說(shuō)起尾刪,就要多注意點(diǎn)了,要看具體情況而言了,直接來(lái)看代碼把
//尾刪 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; } }
尾刪的關(guān)鍵點(diǎn)在于找到最后一個(gè)結(jié)點(diǎn),最后一個(gè)結(jié)點(diǎn)的指針域?yàn)榭铡?/p>
1.鏈表為空時(shí),不需要?jiǎng)h,
2.鏈表只有一個(gè)結(jié)點(diǎn),那它自己就是最后一個(gè)結(jié)點(diǎn)了,
3.多個(gè)結(jié)點(diǎn)就按常規(guī)處理就ok了,該說(shuō)清楚的還是要說(shuō)清楚的。
查找這個(gè)操作其實(shí)是比較簡(jiǎn)單的,在這里說(shuō)是為了后面的使用,想要找到摸個(gè)元素,直接去調(diào)用函數(shù)即可,不用自己一次次去遍歷。
SLTNode* SListFind(SLTNode* phead, SLTDataType x) { SLTNode* cur = phead; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }
除了基本的頭尾增加,我們還可能還需要在某一個(gè)特定節(jié)點(diǎn)前后進(jìn)行插入,這就需要我們玩轉(zhuǎn)起來(lái)了,變得更加靈活。
兩個(gè)核心點(diǎn):
1.pos 的位置
2.插入的操作(這里可能有的同學(xué)會(huì)有一些疑惑,其實(shí)只要知道一點(diǎn),插入的位置是已經(jīng)知道的了)
//在pos的前面插入x void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { if (pos == *pphead) { SListPushFront(pphead,x); } else { SLTNode* newnode = BuySListNode(x); SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = newnode; newnode->next = pos; } }
關(guān)鍵的一點(diǎn),如何找到pos,找到之后鏈表跳過(guò)它,然后刪除即可。
//刪除pos位置的值 void SListErase(SLTNode** pphead, SLTNode* pos) { if (pos == *pphead) { SListpopFront(pphead); } else { SLTNode* prev = *pphead; while (prev->next != pos) { prev = prev->next; } prev->next = pos->next; free(pos); } }
這個(gè)沒啥好說(shuō)的,自己可以去試試
以上就是關(guān)于“C語(yǔ)言鏈表的操作有哪些”這篇文章的內(nèi)容,相信大家都有了一定的了解,希望小編分享的內(nèi)容對(duì)大家有幫助,若想了解更多相關(guān)的知識(shí)內(nèi)容,請(qǐng)關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。