C語言手把手帶你掌握帶頭雙向循環(huán)鏈表
前言
關(guān)于鏈表這一塊,寫了多篇博客,學(xué)習(xí)了順序表、單鏈表、及其一些練習(xí)題
順序表:傳送門:順序表
鏈表OJ:傳送門:鏈表OJ
今天,我又來水一水博客, 介紹關(guān)于雙鏈表。
帶頭雙向循環(huán)鏈表的結(jié)構(gòu)
實際上,單鏈表也存在一個比較大的缺陷:
1.不能從后往前遍歷
2.無法找到前驅(qū)
除了單鏈表之外,我們自然還有雙向鏈表,我們要說的就是帶頭雙向循環(huán)鏈表,簡單理解為:帶頭結(jié)點的,有兩個方向的。循環(huán)的。結(jié)構(gòu)圖如下:
結(jié)構(gòu)雖然比較復(fù)雜,但是極大方便我們找結(jié)點,比如可以直接找到尾結(jié)點,然后再進(jìn)入相關(guān)的操作。實際代碼的操作將會比單鏈表簡單,極為方便,這里不做過多說明,直接上手代碼
代碼操作
我們直奔主題,進(jìn)入代碼實現(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; }
到此這篇關(guān)于C語言手把手帶你掌握帶頭雙向循環(huán)鏈表的文章就介紹到這了,更多相關(guān)C語言帶頭雙向循環(huán)鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C語言實現(xiàn)順序表的基本操作指南(注釋很詳細(xì))
線性表是最簡單的數(shù)據(jù)結(jié)構(gòu),而順序表又是最簡單的線性表,其基本思想是用一段地址連續(xù)的儲存單元依次存儲線性表的數(shù)據(jù)元素,下面這篇文章主要給大家介紹了關(guān)于C語言實現(xiàn)順序表的基本操作,需要的朋友可以參考下2021-10-10C++構(gòu)造函數(shù)的一些注意事項總結(jié)
構(gòu)造函數(shù)是創(chuàng)建類對象,并且在創(chuàng)建完成前,對類進(jìn)行初始化的特殊函數(shù),下面這篇文章主要給大家介紹了關(guān)于C++構(gòu)造函數(shù)的一些注意事項,需要的朋友可以參考下2021-11-11C語言中結(jié)構(gòu)體、聯(lián)合體的成員內(nèi)存對齊情況
這篇文章主要給大家介紹了關(guān)于C語言中結(jié)構(gòu)體、聯(lián)合體的成員內(nèi)存對齊情況的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-05-05