C語言手把手帶你掌握帶頭雙向循環(huán)鏈表
前言
關于鏈表這一塊,寫了多篇博客,學習了順序表、單鏈表、及其一些練習題
順序表:傳送門:順序表
鏈表OJ:傳送門:鏈表OJ
今天,我又來水一水博客, 介紹關于雙鏈表。
帶頭雙向循環(huán)鏈表的結(jié)構(gòu)
實際上,單鏈表也存在一個比較大的缺陷:
1.不能從后往前遍歷
2.無法找到前驅(qū)
除了單鏈表之外,我們自然還有雙向鏈表,我們要說的就是帶頭雙向循環(huán)鏈表,簡單理解為:帶頭結(jié)點的,有兩個方向的。循環(huán)的。結(jié)構(gòu)圖如下:
結(jié)構(gòu)雖然比較復雜,但是極大方便我們找結(jié)點,比如可以直接找到尾結(jié)點,然后再進入相關的操作。實際代碼的操作將會比單鏈表簡單,極為方便,這里不做過多說明,直接上手代碼
代碼操作
我們直奔主題,進入代碼實現(xiàn)的操作,之前的操作如果理解了,那我相信這個對于你來說肯定是不難的。下面直接給出源碼:
List.h
#pragma once #include <stdio.h> #include <stdlib.h> #include <malloc.h> #include <assert.h> #include <stdbool.h> typedef int LTDataType; //帶頭雙向循環(huán)--最優(yōu)鏈表結(jié)構(gòu),在任意位置插入刪除數(shù)據(jù)都是O(1) typedef struct listNode { struct ListNode* next; struct ListNode* prev; LTDataType data; }ListNode; //初始化 ListNode*ListInit(); //銷毀 void ListDestory(ListNode* phead); //打印 void ListPrint(ListNode* phead); //尾插 void ListPushBack(ListNode* phead, LTDataType x); //頭插 void ListPushFront(ListNode* phead, LTDataType x); //頭刪 void ListPopFront(ListNode* phead); //尾刪 void ListPopBack(ListNode* phead); ListNode* ListFind(ListNode* phead, LTDataType x); //在pos位置之前插入x void ListInsert(ListNode* pos, LTDataType x); //刪除pos位置的值 void ListErase(ListNode* pos);
List.c
#include "List.h" //開辟一個新結(jié)點 ListNode* BuyListNode(LTDataType x) { ListNode* newnode =(ListNode*)malloc(sizeof(ListNode)); newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; } //初始化 ListNode* ListInit() { ListNode*phead = BuyListNode(0); phead->next = phead; phead->prev = phead; return phead; } //銷毀 void ListDestory(ListNode* phead) { assert(phead); ListNode* cur = phead->next; while (cur != phead) { ListNode* next = cur->next; free(cur); cur = next; } free(phead); phead = NULL; } //打印 void ListPrint(ListNode* phead) { ListNode* cur = phead->next; while (cur != phead) { printf("%d ", cur->data); cur = cur->next; } printf("\n"); } //尾插 void ListPushBack(ListNode* phead, LTDataType x) { assert(phead); ListNode* tail = phead->prev; ListNode* newnode = BuyListNode(x); tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; } //頭插 void ListPushFront(ListNode* phead, LTDataType x) { assert(phead); ListNode* first = phead->next; ListNode* newnode = BuyListNode(x); newnode->next = first; first->prev = newnode; phead->next = newnode; newnode->prev = phead; } //頭刪 void ListPopFront(ListNode* phead) { assert(phead); assert(phead->next != phead); ListNode* first = phead->next; ListNode* second = first->next; phead->next = second; second->prev = phead; free(first); first = NULL; } //尾刪 void ListPopBack(ListNode* phead) { assert(phead); assert(phead->next != phead); ListNode* tail = phead->prev; ListNode* prev = tail->prev; prev->next = phead; phead->prev = prev; free(tail); tail = NULL; } ListNode* ListFind(ListNode* phead, LTDataType x) { assert(phead); ListNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } //在pos位置之前插入x void ListInsert(ListNode* pos, LTDataType x) { assert(pos); ListNode* prev = pos->prev; ListNode* newnode = BuyListNode(x); prev->next = newnode; newnode->prev = prev; newnode->next = pos; pos->prev = newnode; } //刪除pos位置的值 void ListErase(ListNode* pos) { assert(pos); ListNode* prev = pos->prev; ListNode* next = pos->next; prev->next = next; next->prev = prev; free(pos); }
Test.c
#include "List.h" void TestList1() { ListNode* plist = ListInit(); ListPushBack(plist, 1); ListPushBack(plist, 2); ListPushBack(plist, 3); ListPushBack(plist, 4); ListPrint(plist); ListPushFront(plist, 0); ListPushFront(plist, -1); ListPrint(plist); ListPopFront(plist); ListPopFront(plist); ListPopFront(plist); ListPrint(plist); ListPopBack(plist); ListPrint(plist); } void TestList2() { ListNode* plist = ListInit(); ListPushBack(plist, 1); ListPushBack(plist, 2); ListPushBack(plist, 3); ListPushBack(plist, 4); ListPrint(plist); ListNode* pos = ListFind(plist, 3); if (pos) { pos->data *= 10; printf("找到了,并且*10\n"); } else { printf("沒找到\n"); } ListPrint(plist); ListInsert(pos, 300); ListPrint(plist); ListErase(pos); ListPrint(plist); } int main() { TestList2(); return 0; }
到此這篇關于C語言手把手帶你掌握帶頭雙向循環(huán)鏈表的文章就介紹到這了,更多相關C語言帶頭雙向循環(huán)鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
相關文章
C++構(gòu)造函數(shù)的一些注意事項總結(jié)
構(gòu)造函數(shù)是創(chuàng)建類對象,并且在創(chuàng)建完成前,對類進行初始化的特殊函數(shù),下面這篇文章主要給大家介紹了關于C++構(gòu)造函數(shù)的一些注意事項,需要的朋友可以參考下2021-11-11C語言中結(jié)構(gòu)體、聯(lián)合體的成員內(nèi)存對齊情況
這篇文章主要給大家介紹了關于C語言中結(jié)構(gòu)體、聯(lián)合體的成員內(nèi)存對齊情況的相關資料,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2021-05-05