資訊專(zhuān)欄INFORMATION COLUMN
摘要：雖然有這么多的鏈表的結(jié)構(gòu)，但是我們實(shí)際中最常用還是這兩種結(jié)構(gòu)單向無(wú)頭不循環(huán)鏈表，雙向帶頭循環(huán)鏈表，下面我們來(lái)學(xué)習(xí)這兩種鏈表。
在學(xué)了順序表之后，我們發(fā)現(xiàn)順序表有一定的缺陷。第一個(gè)缺陷，從頭部和中間的插入刪除，都要移動(dòng)后面的數(shù)據(jù)，時(shí)間復(fù)雜度為O(N)。第二個(gè)缺陷，增容需要申請(qǐng)新空間，拷貝數(shù)據(jù)，釋放舊空間，會(huì)有不小的消耗。第三個(gè)缺陷，增容一般是呈2倍的增長(zhǎng)，這會(huì)造成一定的空間浪費(fèi)。比如說(shuō)當(dāng)前順序表數(shù)據(jù)有1024個(gè)，容量也恰好是1024，這時(shí)我們只想插入一個(gè)數(shù)據(jù)，但是擴(kuò)容卻要擴(kuò)大到2048個(gè)，這樣有1023個(gè)空間大小就浪費(fèi)了。剛剛提到的這些問(wèn)題，鏈表就能很好地解決。下面我們就來(lái)一起學(xué)習(xí)一下鏈表，看看鏈表是怎么去解決這些問(wèn)題的，鏈表又存在什么缺陷？
malloc向內(nèi)存申請(qǐng)的，用的時(shí)候再申請(qǐng)。從下圖我們可以看出，鏈表的每個(gè)節(jié)點(diǎn)都有一個(gè)next指針指向下一個(gè)節(jié)點(diǎn)的地址，從邏輯上每個(gè)節(jié)點(diǎn)都是鏈接起來(lái)的。從內(nèi)存的地址上看，每一個(gè)節(jié)點(diǎn)地址之間的距離大小都是不一樣的，所以物理結(jié)構(gòu)上他們不在的空間是不連續(xù)的。單向和雙向
帶頭和不帶頭
循環(huán)和不循環(huán)
實(shí)際中鏈表的結(jié)構(gòu)非常多樣，以上情況組合起來(lái)就有8種鏈表結(jié)構(gòu)。雖然有這么多的鏈表的結(jié)構(gòu)，但是我們實(shí)際中最常用還是這兩種結(jié)構(gòu)：單向無(wú)頭不循環(huán)鏈表，雙向帶頭循環(huán)鏈表，下面我們來(lái)學(xué)習(xí)這兩種鏈表。
data和一個(gè)next，data是用來(lái)存放數(shù)據(jù)的，next是一個(gè)指向下一個(gè)節(jié)點(diǎn)地址的指針，最后一個(gè)節(jié)點(diǎn)的next指向NULL。在實(shí)現(xiàn)鏈表上，一個(gè)創(chuàng)建了三個(gè)文件，分別是SList.h，SList.c，main.c，下面內(nèi)容我們先定義鏈表的結(jié)構(gòu)體和實(shí)現(xiàn)各個(gè)函數(shù)接口的代碼，最后再把三個(gè)文件的代碼展示出來(lái)。// 重定義數(shù)據(jù)類(lèi)型名typedef int SLTDataType;// 定義鏈表結(jié)構(gòu)體typedef struct SListNode{ // 定義一個(gè)指向下一個(gè)節(jié)點(diǎn)地址的指針 struct SListNode* next; // 定義一個(gè)存放數(shù)據(jù)的變量 SLTDataType data;}SListNode;int型，后面要存儲(chǔ)char型的或者其他類(lèi)型的數(shù)據(jù)，需要把代碼里面的int都改一遍，非常麻煩。如果我們重新定義了類(lèi)型名，并且在代碼里用重新定義好的名字，下次需要存儲(chǔ)其他類(lèi)型的數(shù)據(jù)，直接在重定義那里把int改成想存儲(chǔ)的類(lèi)型就好了。// 申請(qǐng)一個(gè)節(jié)點(diǎn)SListNode* BuySListNode(SLTDataType x){ // 向內(nèi)存申請(qǐng)一個(gè)節(jié)點(diǎn) SListNode* newnode = (SListNode*)malloc(sizeof(SListNode)); // 判斷申請(qǐng)是否成功 assert(newnode); // 對(duì)節(jié)點(diǎn)初始化以及賦值 newnode->next = NULL; newnode->data = x; return newnode;}// 頭插/*********************** 為什么會(huì)用到二級(jí)指針 ** 后面3.7會(huì)講到 ***********************/void SListPushFront(SListNode** pplist, SLTDataType x){ // 防止傳進(jìn)來(lái)的pplist是空指針 assert(pplist); // 申請(qǐng)一個(gè)新節(jié)點(diǎn) SListNode* newnode = BuySListNode(x); // 判斷鏈表是否為空 if (*pplist == NULL) { *pplist = newnode; } else { 方法一 申請(qǐng)一個(gè)指針指向當(dāng)前的頭節(jié)點(diǎn) //SListNode* next = *pplist; //*pplist = newnode; //newnode->next = next; // 方法二 newnode->next = *pplist; *pplist = newnode; }}// 方法一和方法二的補(bǔ)充// 從上面我們可以看到方法一多定義了一個(gè)指針，指向當(dāng)前頭節(jié)點(diǎn)的地址//這樣做的好處是，在接下來(lái)的兩條代碼的順序你可以隨意變換// 你可以這樣寫(xiě)*pplist = newnode;newnode->next = next;// 也可以這樣寫(xiě)newnode->next = next;*pplist = newnode;// 如果你像方法二那樣沒(méi)有定義指針的話(huà)，你的代碼只能寫(xiě)成上面這個(gè)順序// 要是你順序?qū)懛吹脑?huà)，*pplist會(huì)直接放棄原來(lái)的頭節(jié)點(diǎn)去指向newnode，而當(dāng)newnode的next想去指向原來(lái)的頭節(jié)點(diǎn)時(shí)，已經(jīng)找不到地址了。// 所以正確的順序是上面那樣，先讓newnode的next先指向原來(lái)的頭節(jié)點(diǎn)，后面*pplist才去指向newnode。// 總結(jié)，方法一多定義一個(gè)變量更加省心，方法二相對(duì)來(lái)說(shuō)要思考得細(xì)一點(diǎn)，也便于我們更好地去理解鏈表結(jié)構(gòu)。assert是一個(gè)斷言函數(shù)，程序運(yùn)行的時(shí)候，當(dāng)括號(hào)里面的結(jié)果為假時(shí)，就會(huì)停止運(yùn)行并且報(bào)錯(cuò)。報(bào)錯(cuò)顯示的信息包括斷言的內(nèi)容和斷言的位置，還有一個(gè)錯(cuò)誤框，如下圖所示。斷言能夠快速地幫我們定位程序的錯(cuò)誤，在實(shí)際開(kāi)發(fā)中可以減少很多不必要的麻煩，所以建議大家在寫(xiě)代碼的時(shí)候也盡量在需要的時(shí)候加上斷言。
溫馨提示在使用assert函數(shù)時(shí)，記得包含一下assert.h這個(gè)頭文件。
// 尾插void SListPushBack(SListNode** pplist, SLTDataType x){ assert(pplist); // 申請(qǐng)一個(gè)新節(jié)點(diǎn) SListNode* newnode = BuySListNode(x); // 分兩種情況，鏈表為空和非空 if (*pplist == NULL) { *pplist = newnode; } else { // 定義一個(gè)指針，去遍歷尋找尾節(jié)點(diǎn) SListNode* tail = *pplist; while (tail->next) { tail = tail->next; } // 插入節(jié)點(diǎn) tail->next = newnode; }}// 在pos之后插入一個(gè)節(jié)點(diǎn)void SListInsertAfter(SListNode* pos, SLTDataType x){ assert(pos); // 申請(qǐng)一個(gè)新節(jié)點(diǎn) SListNode* newnode = BuySListNode(x); 這里也是有兩個(gè)方法，跟之前頭插的差不多 方法一 定義一個(gè)指針指向pos的next //SListNode* posNext = pos->next; //newnode->next = posNext; //pos->next = newnode; // 方法二 newnode->next = pos->next; pos->next = newnode;}// 在pos之前插入一個(gè)節(jié)點(diǎn)void SListInsertBefore(SListNode** pplist, SListNode* pos, SLTDataType x){ assert(pplist); assert(pos); // 申請(qǐng)一個(gè)新節(jié)點(diǎn) SListNode* newnode = BuySListNode(x); // 判斷pos是否為第一個(gè)節(jié)點(diǎn) if (*pplist == pos) { newnode->next = pos; *pplist = newnode; } else { // 先找到pos之前的一個(gè)節(jié)點(diǎn) SListNode* prev = *pplist; while (prev->next != pos) { prev = prev->next; } // 插入新節(jié)點(diǎn) newnode->next = pos; prev->next = newnode; }}// 頭刪void SListPopFront(SListNode** pplist){ // 防止pplist指針為空 assert(pplist); // 防止pplist指向的地址為空，即鏈表為空 assert(*pplist); // 定義一個(gè)指針指向第一個(gè)節(jié)點(diǎn)的地址，后面釋放空間需要用到 SListNode* temp = *pplist; // 讓*pplist直接指向它的下一個(gè)節(jié)點(diǎn) *pplist = (*pplist)->next; // 釋放被刪節(jié)點(diǎn)空間,并把temp指針置空 free(temp); temp = NULL;}// 尾刪void SListPopBack(SListNode** pplist){ assert(pplist); assert(*pplist); // 分兩種情況，鏈表只有一個(gè)節(jié)點(diǎn)，和有一個(gè)以上節(jié)點(diǎn) if ((*pplist)->next == NULL) { free(*pplist); *pplist = NULL; } else { // 找到尾節(jié)點(diǎn)之前的一個(gè)節(jié)點(diǎn) SListNode* tail = *pplist; while (tail->next->next) { tail = tail->next; } SListNode* temp = tail->next; tail->next = NULL; free(temp); temp = NULL; }}// 刪去pos節(jié)點(diǎn)void SListErase(SListNode** pplist, SListNode* pos){ assert(pplist); assert(*pplist); // 分兩種情況，pos為第一個(gè)節(jié)點(diǎn)和不是第一個(gè)節(jié)點(diǎn) if (*pplist == pos) { free(*pplist); *pplist = NULL; } else { // 找到pos之前的節(jié)點(diǎn) SListNode* posPrev = *pplist; while (posPrev->next != pos) { posPrev = posPrev->next; } posPrev->next = pos->next; free(pos); pos = NULL; }}// 查找SListNode* SListFind(SListNode* plist, SLTDataType x){ // 當(dāng)鏈表為空，返回NULL if (plist == NULL) { return NULL; } // 鏈表不為空，遍歷鏈表 SListNode* find = plist; while (find) { // 判斷是否為所找節(jié)點(diǎn)，是則返回節(jié)點(diǎn)地址 if (find->data == x) { return find; } // 繼續(xù)迭代 find = find->next; } // 沒(méi)有找到，返回NULL return NULL;}// 修改void SListModify(SListNode* pos, SLTDataType x){ assert(pos); pos->data = x;}// 銷(xiāo)毀void SListDestroy(SListNode** pplist){ assert(pplist); SListNode* temp = NULL; // 頭刪，依次釋放空間 while (*pplist) { temp = *pplist; *pplist = (*pplist)->next; free(temp); } temp = NULL;}#pragma once // 防止頭文件被重復(fù)包含// 包含頭文件#include#define _CRT_SECURE_NO_WARNINGS // 這句是我的VS2019用scanf報(bào)錯(cuò)才加的，大家可以不用理#include"SList.h"// 打印void SListPrint(SListNode* plist){ while (plist) { printf("%d", plist->data); printf("-->"); plist = plist->next; } printf("NULL");}// 申請(qǐng)一個(gè)節(jié)點(diǎn)SListNode* BuySListNode(SLTDataType x){ // 向內(nèi)存申請(qǐng)一個(gè)節(jié)點(diǎn) SListNode* newnode = (SListNode*)malloc(sizeof(SListNode)); // 判斷申請(qǐng)是否成功 assert(newnode); // 對(duì)節(jié)點(diǎn)初始化以及賦值 newnode->next = NULL; newnode->data = x; return newnode;}// 頭插void SListPushFront(SListNode** pplist, SLTDataType x){ // 防止傳進(jìn)來(lái)的pplist是空指針 assert(pplist); // 申請(qǐng)一個(gè)新節(jié)點(diǎn) SListNode* newnode = BuySListNode(x); // 判斷鏈表是否為空 if (*pplist == NULL) { *pplist = newnode; } else { 方法一 申請(qǐng)一個(gè)指針指向當(dāng)前的頭節(jié)點(diǎn) //SListNode* next = *pplist; //*pplist = newnode; //newnode->next = next; // 方法二 newnode->next = *pplist; *pplist = newnode; }}// 尾插void SListPushBack(SListNode** pplist, SLTDataType x){ assert(pplist); // 申請(qǐng)一個(gè)新節(jié)點(diǎn) SListNode* newnode = BuySListNode(x); // 分兩種情況，鏈表為空和非空 if (*pplist == NULL) { *pplist = newnode; } else { // 定義一個(gè)指針，去遍歷尋找尾節(jié)點(diǎn) SListNode* tail = *pplist; while (tail->next) { tail = tail->next; } // 插入節(jié)點(diǎn) tail->next = newnode; }}// 在pos之前插入一個(gè)節(jié)點(diǎn)void SListInsertBefore(SListNode** pplist, SListNode* pos, SLTDataType x){ assert(pplist); assert(pos); // 申請(qǐng)一個(gè)新節(jié)點(diǎn) SListNode* newnode = BuySListNode(x); // 判斷pos是否為第一個(gè)節(jié)點(diǎn) if (*pplist == pos) { newnode->next = pos; *pplist = newnode; } else { // 先找到pos之前的一個(gè)節(jié)點(diǎn) SListNode* prev = *pplist; while (prev->next != pos) { prev = prev->next; } // 插入新節(jié)點(diǎn) newnode->next = pos; prev->next = newnode; }}// 在pos之后插入一個(gè)節(jié)點(diǎn)void SListInsertAfter(SListNode* pos, SLTDataType x){ assert(pos); // 申請(qǐng)一個(gè)新節(jié)點(diǎn) SListNode* newnode = BuySListNode(x); 這里也是有兩個(gè)方法，跟之前頭插的差不多 方法一 定義一個(gè)指針指向pos的next //SListNode* posNext = pos->next; //newnode->next = posNext; //pos->next = newnode; // 方法二 newnode->next = pos->next; pos->next = newnode;}// 頭刪void SListPopFront(SListNode** pplist){ // 防止pplist指針為空 assert(pplist); // 防止pplist指向的地址為空，即鏈表為空 assert(*pplist); // 定義一個(gè)指針指向第一個(gè)節(jié)點(diǎn)的地址，后面釋放空間需要用到 SListNode* temp = *pplist; // 讓*pplist直接指向它的下一個(gè)節(jié)點(diǎn) *pplist = (*pplist)->next; // 釋放被刪節(jié)點(diǎn)空間，并把temp指針置空 free(temp); temp = NULL;}// 尾刪void SListPopBack(SListNode** pplist){ assert(pplist); assert(*pplist); // 分兩種情況，鏈表只有一個(gè)節(jié)點(diǎn)，和有一個(gè)以上節(jié)點(diǎn) if ((*pplist)->next == NULL) { free(*pplist); *pplist = NULL; } else { // 找到尾節(jié)點(diǎn)之前的一個(gè)節(jié)點(diǎn) SListNode* tail = *pplist; while (tail->next->next) { tail = tail->next; } SListNode* temp = tail->next; tail->next = NULL; free(temp); temp = NULL; }}// 刪去pos節(jié)點(diǎn)void SListErase(SListNode** pplist, SListNode* pos){ assert(pplist); assert(*pplist); // 分兩種情況，pos為第一個(gè)節(jié)點(diǎn)和不是第一個(gè)節(jié)點(diǎn) if (*pplist == pos) { *pplist = pos->next; free(pos); } else { // 找到pos之前的節(jié)點(diǎn) SListNode* posPrev = *pplist; while (posPrev->next != pos)
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/123619.html
摘要：之所以這樣說(shuō)不要認(rèn)為學(xué)就不需要學(xué)語(yǔ)言，是因?yàn)橐晃兜闹粚W(xué)而沒(méi)有語(yǔ)言等這些基礎(chǔ)語(yǔ)言的支撐，是很難深入理解的很多東西的。 之所以這樣說(shuō)不要認(rèn)為學(xué)PHP就不需要學(xué)C語(yǔ)言，是因?yàn)橐晃兜闹粚W(xué)PHP而沒(méi)有C語(yǔ)言等這些基礎(chǔ)語(yǔ)言的支撐，是很難深入理解PHP的很多東西的。 這樣的例子其實(shí)很多，這里我就舉這個(gè)例子吧：PHP的數(shù)組和C語(yǔ)言的數(shù)組的區(qū)別和聯(lián)系。 學(xué)過(guò)C語(yǔ)言的朋友當(dāng)然知道C語(yǔ)言里有數(shù)組； PHP里...
閱讀 1963·2023-04-25 14:28
閱讀 2035·2021-11-19 09:40
閱讀 3010·2021-11-17 09:33
閱讀 1475·2021-11-02 14:48
閱讀 1806·2019-08-29 16:36
閱讀 3427·2019-08-29 16:09
閱讀 3010·2019-08-29 14:17
閱讀 2483·2019-08-29 14:07
