亚洲一区综合,成人亚洲,国产精品二区三区在线观看

雙向循環(huán)鏈表

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

結(jié)構(gòu)示意圖

C語言實現(xiàn)帶頭雙向環(huán)形鏈表

帶頭雙向循環(huán)鏈表在邏輯上大概就是這樣的一個樣子，鏈表的最后一個節(jié)點的后繼指向的是頭結(jié)點。而頭結(jié)點的前驅(qū)則是指向鏈表的最后一個結(jié)點。所以，一個空的帶頭雙向循環(huán)鏈表的邏輯結(jié)構(gòu)應該是這樣的：

C語言實現(xiàn)帶頭雙向環(huán)形鏈表

它的前驅(qū)和后繼都是指向的頭結(jié)點。

實現(xiàn)帶頭雙向循環(huán)鏈表

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

// 創(chuàng)建返回鏈表的頭結(jié)點.
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位置的節(jié)點
void ListErase(LTNode* pos);

首先我們得定義一個結(jié)點的結(jié)構(gòu)，它由前驅(qū)指針、后繼指針和數(shù)據(jù)這三部分組成。

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

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

**注意：**頭結(jié)點創(chuàng)建的時候，它的data部分是不存數(shù)據(jù)的，它的前驅(qū)和后繼都是指向它自己

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

創(chuàng)建好頭結(jié)點之后就可以向鏈表中插入數(shù)據(jù)了，首先實現(xiàn)尾插，就是在鏈表的最后一個結(jié)點后面再插入一個結(jié)點。然后就是頭插法，頭插法就是在頭結(jié)點的后面插入一個新節(jié)點。

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

}

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

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

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

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

// 雙向鏈表查找
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;
}

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

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

打印雙向循環(huán)鏈表，也是通過遍歷鏈表來打印

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

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

// 雙向鏈表銷毀
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;
}

以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持服務器之家。

原文鏈接：https://blog.csdn.net/aiyubaobei/article/details/121528681