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