C語言怎么實現帶頭雙向環形鏈表

本篇內容主要講解“C語言怎么實現帶頭雙向環形鏈表”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“C語言怎么實現帶頭雙向環形鏈表”吧!

雙向循環鏈表

上一次我們講了單向無頭非循環鏈表的實現，單向無頭非循環鏈表的特點是：結構簡單，一般不會單獨用來存數據。實際中更多是作為其他數據結構的子結構。而帶頭雙向循環鏈表則恰恰與無頭單向非循環鏈表相反，它的結構最復雜，一般用來單獨存儲數據。這個結構雖然復雜，但是使用單嗎實現后會發現，這個結構用起來很簡單。

結構示意圖

帶頭雙向循環鏈表在邏輯上大概就是這樣的一個樣子，鏈表的最后一個節點的后繼指向的是頭結點。而頭結點的前驅則是指向鏈表的最后一個結點。所以，一個空的帶頭雙向循環鏈表的邏輯結構應該是這樣的：

它的前驅和后繼都是指向的頭結點。

實現帶頭雙向循環鏈表

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int LTDataType;
// 定義鏈表的節點
typedef struct ListNode {
 LTDataType data;
 struct ListNode* prev;
 struct ListNode* next;
}LTNode;

// 創建返回鏈表的頭結點.
LTNode* ListCreate();
// 雙向鏈表銷毀
void ListDestory(LTNode* pHead);
// 雙向鏈表打印
void ListPrint(LTNode* pHead);
// 雙向鏈表尾插
void ListPushBack(LTNode* pHead, LTDataType x);
// 雙向鏈表尾刪
void ListPopBack(LTNode* pHead);
// 雙向鏈表頭插
void ListPushFront(LTNode* pHead, LTDataType x);
// 雙向鏈表頭刪
void ListPopFront(LTNode* pHead);
// 雙向鏈表查找
LTNode* ListFind(LTNode* pHead, LTDataType x);
// 雙向鏈表在pos的前面進行插入
void ListInsert(LTNode* pos, LTDataType x);
// 雙向鏈表刪除pos位置的節點
void ListErase(LTNode* pos);

首先我們得定義一個結點的結構，它由前驅指針、后繼指針和數據這三部分組成。

// 定義鏈表的節點
typedef struct ListNode {
 LTDataType data;
 struct ListNode* prev;
 struct ListNode* next;
}LTNode;

定義好之后，我們要創建一個頭結點。我們把創建頭結點的過程也封裝成一個函數，這個函數的返回值就是頭結點的指針。我們在使用的時候就創建一個變量來接收這個指針。

**注意：**頭結點創建的時候，它的data部分是不存數據的，它的前驅和后繼都是指向它自己

LTNode* ListCreate() {
 LTNode* head = (LTNode*)malloc(sizeof(LTNode));
 head->next = head;
 head->prev = head;
 return head;
}
// 在main函數中是這樣使用的
int main(){
    LTNode* head = ListCreate();
    return 0;
}

創建好頭結點之后就可以向鏈表中插入數據了，首先實現尾插，就是在鏈表的最后一個結點后面再插入一個結點。然后就是頭插法，頭插法就是在頭結點的后面插入一個新節點。

// 雙向鏈表尾插
void ListPushBack(LTNode* pHead, LTDataType x) {
 assert(pHead);
 LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); // 創建的新節點
 newnode->data = x;
    // 將新節點插入到鏈表中
 LTNode* prev = pHead->prev;
 prev->next = newnode;
 newnode->prev = prev;
 newnode->next = pHead;
 pHead->prev = newnode;

}

// 雙向鏈表頭插
void ListPushFront(LTNode* pHead, LTDataType x) {
 assert(pHead);
    // 創建新節點
 LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
 newnode->data = x;
    //將新節點插入鏈表
 LTNode* next = pHead->next;
 pHead->next = newnode;
 newnode->prev = pHead;
 newnode->next = next;
 next->prev = newnode;
}

有插入數據就有刪除數據，同樣的刪除數據也有兩種，一個是頭刪一個是尾刪。頭刪就是將頭結點的next指向的那個結點刪除。尾刪，就是將最后一個節點刪掉。帶頭雙向循環鏈表，在我們尾刪的時候就很方便。因為頭結點的前驅指向的節點就是鏈表的最后一個節點，就不需要我們再遍歷鏈表去找最后一個節點的地址。

// 雙向鏈表頭刪
void ListPopFront(LTNode* pHead) {
 assert(pHead);
 assert(pHead->next != pHead);
    // 定義一個臨時變量來保存我們要刪掉的節點的位置
 LTNode* popnode = pHead->next;
    // 將要刪除節點的鏈都斷掉
 LTNode* next = popnode->next;
 pHead->next = popnode->next;
 next->prev = pHead;
    // free掉那個節點
 free(popnode);
 popnode = NULL;
}

// 雙向鏈表尾刪
void ListPopBack(LTNode* pHead) {
 assert(pHead);
 assert(pHead->prev != pHead);
 LTNode* popnode = pHead->prev;
 LTNode* prev = popnode->prev;
 prev->next = pHead;
 pHead->prev = prev;
 free(popnode);
 popnode = NULL;
}

在實現了增加和刪除節點之后，我們就實現查找結點。方法也是遍歷整個鏈表，如果有一個節點的data的值和x相同就返回這個節點的地址。如果沒找到就返回空。

// 雙向鏈表查找
LTNode* ListFind(LTNode* pHead, LTDataType x) {
 if (pHead->next == pHead) {
  return NULL;
 }
 LTNode* find = pHead->next;
 while (find != pHead) {
  if (find->data == x) {
   return find;
  }
  find = find->next;
 }
 return NULL;
}

實現隨機插入數據，這里的隨機插入的意思是，我們把新節點插入到我們指定的節點的后面一個或前面一個。這個節點可以是在鏈表的任何一個地方。我們這個函數會傳入一個節點的地址，通過那個地址可以找到要出入的那個節點，把新節點連接到那個節點后面就可以了

// 雙向鏈表刪除pos位置的節點
void ListErase(LTNode* pos) {
 assert(pos);
 LTNode* prev = pos->prev;
 LTNode* next = pos->next;
 prev->next = next;
 next->prev = prev;
 free(pos);
 pos = NULL;
}

打印雙向循環鏈表，也是通過遍歷鏈表來打印

// 雙向鏈表打印
void ListPrint(LTNode* pHead) {
 assert(pHead);
 LTNode* tail = pHead->next;
 while (tail != pHead) {
  printf("%d->", tail->data);
  tail = tail->next;
 }
}

在我們使用完鏈表后，要記得銷毀鏈表，防止內存泄漏

// 雙向鏈表銷毀
void ListDestory(LTNode* pHead) {
 assert(pHead);
 LTNode* tail = pHead->next;
 while (tail != pHead) {
  LTNode* tmp = tail->next;
  free(tail);
  tail = tmp;
 }
 free(pHead);
 pHead = NULL;
}

到此，相信大家對“C語言怎么實現帶頭雙向環形鏈表”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！