詳解C語言中雙向循環鏈表的實現
實現細節
1、帶一個哨兵位(哨兵節點,初始節點,不存儲有效數據,用來方便後期數據的存儲與查找)
2、與單向鏈表不同的是,雙向鏈表中每個數據節點包含兩個指針,分別指向前後兩個節點
3、雙向鏈表是循環的,其尾節點後不是空指針,而是與頭部的哨兵節點通過指針相連
輔助理解圖
具體實現代碼
1、對鏈表進行初始化
初始化:哨兵位的前後指針均指向哨兵節點本身
void ListInit(ListNode** pphead) { *pphead = (ListNode*)malloc(sizeof(ListNode)); if (*pphead == NULL) { perror("ListInit"); exit(-1); } (*pphead)->date = -1; (*pphead)->next = *pphead; (*pphead)->prev = *pphead; }
2、任意位置前的插入
註意:插入位置前後節點中的前後指針要進行相應的更換
void Any_insert(ListNode* pos,Listtype date) { ListNode* Prev = pos->prev; //建立新節點 ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode)); if (NewNode == NULL) { perror("Any_insert"); exit(-1); } NewNode->date = date; NewNode->next = pos; pos->prev = NewNode; Prev->next = NewNode; NewNode->prev = Prev; }
3、任意位置的刪除
細節點:當鏈表中沒有數據時,就不用刪除,因此需要建立一個函數進行判斷
bool Determine(ListNode* pphead) {//判斷鏈表中有無元素 assert(pphead); return pphead == pphead->next; } void Any_delet(ListNode* pos) { assert(!Determine(pos)); ListNode* Next = pos->next; ListNode* Prev = pos->prev; Next->prev = Prev; Prev->next = Next; free(pos); }
4、頭插和尾刪
此處的插入和刪除,十分方便,即:對上面的任插和任刪進行套用
頭插如下:
void Head_insert(ListNode* pphead, Listtype date) { ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode)); if (NewNode == NULL) { perror("Head_insert"); exit(-1); } //單獨實現 //NewNode->date = date; //NewNode->prev = pphead; //NewNode->next = pphead->next; //pphead->next->prev = NewNode; //pphead->next = NewNode; //進行任插的復用 Any_insert(pphead->next ,date); }
尾刪如下:
void Tail_delet(ListNode* pphead) { assert(pphead); //單獨實現 //assert(Determine(pphead)); /*ListNode* tail = pphead->prev; if (tail != pphead) { ListNode* tailprev = tail->prev; tailprev->next = pphead; pphead->prev = tailprev; free(tail); }*/ //尾刪的復用 Any_delet(pphead->prev); }
完整代碼
頭文件
#pragma once #include<stdio.h> #include<malloc.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int Listtype; typedef struct ListNode { struct ListNode* prev; Listtype date; struct ListNode* next; }ListNode; void ListInit(ListNode** pphead); //鏈表初始化 void ListNode_ADD(ListNode* pphead, Listtype date); //尾插 void Head_insert(ListNode* pphead, Listtype date); //頭插 void ListNode_Print(ListNode* pphead); //鏈表打印 void Tail_delet(ListNode* pphead); //尾刪 bool Determine(ListNode* pphead); //判斷表中有無數據 void Any_insert(ListNode* pos, Listtype date); //任插 void Any_delet(ListNode* pos); //任刪 void List_Destory(ListNode* pos); //鏈表清空
具體函數
#define _CRT_SECURE_NO_WARNINGS 1 #include "List.h" //鏈表打印 void ListNode_Print(ListNode* pphead) { assert(pphead); ListNode* phead = pphead; pphead = pphead->next; for (; pphead != phead; pphead = pphead->next) { printf("%d ", pphead->date); } printf("\n"); } bool Determine(ListNode* pphead) {//判斷鏈表中有無元素 assert(pphead); return pphead == pphead->next; } //鏈表初始化 void ListInit(ListNode** pphead) { *pphead = (ListNode*)malloc(sizeof(ListNode)); if (*pphead == NULL) { perror("ListInit"); exit(-1); } (*pphead)->date = -1; (*pphead)->next = *pphead; (*pphead)->prev = *pphead; } //尾插 void ListNode_ADD(ListNode* pphead,Listtype date) { //ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode)); //if (NewNode == NULL) //{ // perror("ADD_malloc"); // exit(-1); //} //NewNode->date = date; //NewNode->prev = pphead->prev; //pphead->prev->next = NewNode; //pphead->prev = NewNode; //NewNode->next = pphead; //任插的復用 Any_insert(pphead, date); } void Head_insert(ListNode* pphead, Listtype date) { ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode)); if (NewNode == NULL) { perror("Head_insert"); exit(-1); } //NewNode->date = date; //NewNode->prev = pphead; //NewNode->next = pphead->next; //pphead->next->prev = NewNode; //pphead->next = NewNode; //進行任插的復用 Any_insert(pphead->next ,date); } void Tail_delet(ListNode* pphead) { assert(pphead); //assert(Determine(pphead)); /*ListNode* tail = pphead->prev; if (tail != pphead) { ListNode* tailprev = tail->prev; tailprev->next = pphead; pphead->prev = tailprev; free(tail); }*/ //尾刪的復用 Any_delet(pphead->prev); } //在任意位置前插入 void Any_insert(ListNode* pos,Listtype date) { ListNode* Prev = pos->prev; ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode)); if (NewNode == NULL) { perror("Any_insert"); exit(-1); } NewNode->date = date; NewNode->next = pos; pos->prev = NewNode; Prev->next = NewNode; NewNode->prev = Prev; } //任意位置刪除 void Any_delet(ListNode* pos) { assert(!Determine(pos)); ListNode* Next = pos->next; ListNode* Prev = pos->prev; Next->prev = Prev; Prev->next = Next; free(pos); } //鏈表清空 void List_Destory(ListNode* pos) { ListNode* head = pos,*Prev = pos->prev; for (pos = pos->prev; head != pos;pos = Prev) { Prev = pos->prev; Any_delet(pos); } printf("\n清空完成\n"); }
測試
#define _CRT_SECURE_NO_WARNINGS 1 #include "List.h" void ListTest(ListNode** pphead) { ListInit(pphead); Head_insert(*pphead, 60); Head_insert(*pphead, 100); Head_insert(*pphead, 60); Head_insert(*pphead, 50); ListNode_Print(*pphead); Tail_delet(*pphead); Tail_delet(*pphead); Tail_delet(*pphead); ListNode_Print(*pphead); } int main() { ListNode* pphead = NULL; ListTest(&pphead); return 0 ; }
以上就是詳解C語言中雙向循環鏈表的實現的詳細內容,更多關於C語言雙向循環鏈表的資料請關註WalkonNet其它相關文章!