線性表——雙向鏈表
- 1. 雙向鏈表的實現
- 1.1 簡單圖例
- 1.2 結點的定義
- 1.3 新結點的創建
- 1.4 鏈表的初始化
- 1.5 結點的插入
- 1.5.1 頭部插入(頭插)
- 1.5.2 尾部插入(尾插)
- 1.5.3 任意位置(前)插入
- 1.6 結點的刪除
- 1.6.1 頭部刪除(頭刪)
- 1.6.2 尾部刪除(尾刪)
- 1.6.3 任意位置刪除
- 1.7 查找結點
- 1.8 鏈表的打印
- 1.9 鏈表的銷毀
- 2. 功能綜合
- 3. 誤區糾正
- 4. 正確使用鏈表
??到目前為止,我們對順序表,鏈表都進行了初步是實現,其中僅完成了單鏈表。要知道,鏈表可不僅僅用是否有頭結點來區分,另外還有單向、雙向,循環和非循環。將這些情況組合起來可以組成 8 種不同的鏈表,由于帶頭雙向循環鏈表的使用情況較多,本章就對帶頭雙向循環鏈表進行實現。
1. 雙向鏈表的實現
1.1 簡單圖例
1.2 結點的定義
typedef int LTDataType;
typedef struct ListNode
{LTDataType val; //數據域struct ListNode* prev; //指針域(存放前驅結點的地址)struct ListNode* next; //指針域(存放后繼結點的地址)
}ListNode;
注意:雙向鏈表有 兩個 指針域,一個指向前驅 結點,一個指向后繼 結點。
1.3 新結點的創建
ListNode* CreateListNode(LTDataType x) { //x為新結點的val部分(數據域)ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); //為新結點開辟新空間if (newnode == NULL) {perror("malloc fail!");return;}newnode->val = x;newnode->next = NULL;newnode->prev = NULL;return newnode; //返回新結點的地址
}
1.4 鏈表的初始化
??這里鏈表的初始化只是針對于頭結點,相當于給頭結點一個初始的值。
ListNode* DListInit() {ListNode* phead = CreateListNode(-1); //給頭結點的值賦為 -1phead->next = phead;phead->prev = phead; //指針域全部指向本身(初始化)return phead;
}
測試時即可使用:
ListNode* Dlist=DListInit();
1.5 結點的插入
1.5.1 頭部插入(頭插)
注意:頭部插入
不是在頭結點之前插入,而是在 頭結點后面第一個結點之前插入。
void DListPushFront(ListNode* phead, LTDataType x) {assert(phead);ListNode* newnode = CreateListNode(x);ListNode* cur = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = cur;cur->prev = newnode;
}
圖解:
1.5.2 尾部插入(尾插)
void DListPushBack(ListNode* phead, LTDataType x) {assert(phead);ListNode* tail = phead->prev;ListNode* newnode = CreateListNode(x);tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;}
圖解:
1.5.3 任意位置(前)插入
??在這部分功能上雙向鏈表就比單鏈表好實現得多,雙向鏈表自帶一個前驅結點的地址,不需要像單鏈表一樣從頭開始遍歷。
void DListInsert(ListNode* pos, LTDataType x) {assert(pos); //判斷pos不為空ListNode* newnode = CreateListNode(x);ListNode* cur = pos->prev;cur->next = newnode;newnode->prev = cur;newnode->next = pos;pos->prev = newnode;}
此部分圖例可參考頭插(同原理)
1.6 結點的刪除
1.6.1 頭部刪除(頭刪)
void DListPopFront(ListNode* phead) {assert(phead);ListNode* front = phead->next;ListNode* back = front->next;phead->next = back;back->prev = phead;free(front);front = NULL;
}
圖解:
1.6.2 尾部刪除(尾刪)
??刪除尾部結點只需要將倒數第二個的結點的位置找到,尾部結點的空間就可以直接釋放了,接下來就直接鏈接頭結點。
void DListPopBack(ListNode* phead) {assert(phead);ListNode* tail = phead->prev;ListNode* tail_prev = tail->prev;free(tail);tail = NULL;tail_prev->next = phead;phead->prev = tail_prev;}
圖解:
1.6.3 任意位置刪除
void DListErase(ListNode* pos) {assert(pos);ListNode* cur = pos->prev;ListNode* back = pos->next;cur->next = back;back->prev = cur;free(pos);pos = NULL;
}
此處圖例可參考頭刪 尾刪(同原理)
1.7 查找結點
??在順序表中,當結點的位置被找到時,函數會返回順序表的下標。在鏈表中,返回的就是結點的地址。
ListNode* DListFind(ListNode* phead, LTDataType x) {assert(phead);ListNode* cur = phead->next;while (cur != phead) {if (cur->val == x) {return cur;}cur = cur->next;}return NULL; //找不到對應的結點返回NULL
}
1.8 鏈表的打印
void DListPrint(ListNode* phead) {assert(phead);ListNode* cur = phead->next;printf("(頭結點)<->");while (cur!=phead) {printf("[%d]<->", cur->val);cur = cur->next;}printf("(頭結點)\n");
}
打印部分可自行美化
1.9 鏈表的銷毀
void DListDestory(ListNode* phead) {assert(phead);ListNode* cur = phead->next;while (cur != phead) {ListNode* Next = cur->next; //先存儲下一個結點的地址free(cur); //再釋放當前結點cur = Next; //然后把Next給cur}free(phead);phead = NULL;
}
2. 功能綜合
??功能整合起來代碼較長,另外也可以通過接口的方式實現(層次分明),有不懂的可參考上文圖解自行消化,main部分可以自行調用函數進行測試。
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//創建新結點
ListNode* CreateListNode(LTDataType x) { //x為新結點的val部分(數據域)ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); //為新結點開辟新空間if (newnode == NULL) {perror("malloc fail!");return;}newnode->val = x;newnode->next = NULL;newnode->prev = NULL;return newnode; //返回新結點的地址
}//初始化頭結點
ListNode* DListInit() {ListNode* phead = CreateListNode(-1); //給頭結點的值賦為 -1phead->next = phead;phead->prev = phead; //指針域全部指向本身(初始化)return phead;
}//頭插
void DListPushFront(ListNode* phead, LTDataType x) {assert(phead);ListNode* newnode = CreateListNode(x);ListNode* cur = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = cur;cur->prev = newnode;
}//尾插
void DListPushBack(ListNode* phead, LTDataType x) {assert(phead);ListNode* tail = phead->prev;ListNode* newnode = CreateListNode(x);tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;}//任意位置(前)插入
void DListInsert(ListNode* pos, LTDataType x) {assert(pos); //判斷pos不為空ListNode* newnode = CreateListNode(x);ListNode* cur = pos->prev;cur->next = newnode;newnode->prev = cur;newnode->next = pos;pos->prev = newnode;}//頭刪
void DListPopFront(ListNode* phead) {assert(phead);ListNode* front = phead->next;ListNode* back = front->next;phead->next = back;back->prev = phead;free(front);front = NULL;
}//尾刪
void DListPopBack(ListNode* phead) {assert(phead);ListNode* tail = phead->prev;ListNode* tail_prev = tail->prev;free(tail);tail = NULL;tail_prev->next = phead;phead->prev = tail_prev;}//任意位置刪除
void DListErase(ListNode* pos) {assert(pos);ListNode* cur = pos->prev;ListNode* back = pos->next;cur->next = back;back->prev = cur;free(pos);pos = NULL;
}//查找結點
ListNode* DListFind(ListNode* phead, LTDataType x) {assert(phead);ListNode* cur = phead->next;while (cur != phead) {if (cur->val == x) {return cur;}cur = cur->next;}return NULL; //找不到對應的結點返回NULL
}//打印鏈表
void DListPrint(ListNode* phead) {assert(phead);ListNode* cur = phead->next;printf("(頭結點)<->");while (cur!=phead) {printf("[%d]<->", cur->val);cur = cur->next;}printf("(頭結點)\n");
}//銷毀鏈表
void DListDestory(ListNode* phead) {assert(phead);ListNode* cur = phead->next;while (cur != phead) {ListNode* Next = cur->next; //先存儲下一個結點的地址free(cur); //再釋放當前結點cur = Next; //然后把Next給cur}free(phead);phead = NULL;
}int main() {ListNode* Dlist = DListInit(); //初始化DListPushBack(Dlist, 1);DListPushBack(Dlist, 2);DListPushBack(Dlist, 3);DListPushBack(Dlist, 5);DListPushBack(Dlist, 4); //尾插DListPrint(Dlist); //打印DListPopBack(Dlist); //尾刪DListPrint(Dlist); //打印DListPushFront(Dlist, 99);DListPushFront(Dlist, 78);DListPushFront(Dlist, 666); //頭插DListPrint(Dlist); //打印DListPopFront(Dlist); //頭刪DListPrint(Dlist); //打印return 0;
}
運行結果:
3. 誤區糾正
- 增刪查改的操作對象的主體不是頭結點,頭的增刪動的是 head->next。
- 頭結點只是起輔助作用,判斷帶頭鏈表是否為空,要從頭結點->next開始判斷。
- 雙向鏈表不能完全替代單鏈表,單鏈表相對于雙向鏈表來說 內存使用少 ,比雙向鏈表少一個指針。
4. 正確使用鏈表
- 理解 prev 和 next 的指向關系。
- 根據實際情況判斷鏈表是否需要 頭結點、循環、雙向 。