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