數(shù)據(jù)結(jié)構(gòu): 線性表(帶頭雙向循環(huán)鏈表實(shí)現(xiàn))

這篇具有很好參考價(jià)值的文章主要介紹了數(shù)據(jù)結(jié)構(gòu): 線性表(帶頭雙向循環(huán)鏈表實(shí)現(xiàn))。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

之前一章學(xué)習(xí)了單鏈表的相關(guān)操作, 但是單鏈表的限制卻很多, 比如不能倒序掃描鏈表, 解決方法是在數(shù)據(jù)結(jié)構(gòu)上附加一個(gè)域, 使它包含指向前一個(gè)單元的指針即可.

那么怎么定義數(shù)據(jù)結(jié)構(gòu)呢? 首先我們先了解以下鏈表的分類

1. 鏈表的分類

鏈表的結(jié)構(gòu)非常多樣, 以下情況組合起來就有 8 中鏈表結(jié)構(gòu)

單向或者雙向
帶頭或者不帶頭
循環(huán)或者非循環(huán)

雖然有這么多的鏈表的結(jié)構(gòu), 但是我們實(shí)際上最常用的還是兩種結(jié)構(gòu):

數(shù)據(jù)結(jié)構(gòu): 線性表(帶頭雙向循環(huán)鏈表實(shí)現(xiàn)),數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表

無頭單向非循環(huán)鏈表

結(jié)構(gòu)簡(jiǎn)單,一般不會(huì)單獨(dú)用來存放數(shù)據(jù).實(shí)際上更多是作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)構(gòu), 如哈希桶, 圖的鄰接表等等. 另外這種結(jié)構(gòu)在筆試面試中出現(xiàn)很多

帶頭雙向循環(huán)鏈表

結(jié)構(gòu)最復(fù)雜, 一般用于單獨(dú)存儲(chǔ)數(shù)據(jù).實(shí)際上使用的鏈表數(shù)據(jù)結(jié)構(gòu), 都是帶頭雙向循環(huán)鏈表. 雖然結(jié)構(gòu)復(fù)雜, 但是實(shí)現(xiàn)相關(guān)功能比較簡(jiǎn)單.

嚴(yán)格來說只用實(shí)現(xiàn) Insert 和 Erase 兩個(gè)功能, 就可以實(shí)現(xiàn) “二十分鐘” 寫完一個(gè)鏈表的任務(wù).

2. 帶頭雙向循環(huán)鏈表

2.1 帶頭雙向循環(huán)鏈表的定義

typedef int LTDataType;     //LTDataType = int
typedef struct ListNode
{
  LTDataType data;          //數(shù)據(jù)域
  struct ListNode* prev;    //指向前一個(gè)結(jié)點(diǎn)
  struct ListNode* next;    //指向后一個(gè)結(jié)點(diǎn)
}ListNode;  //重命名為 ListNode

相比較單鏈表的數(shù)據(jù)結(jié)構(gòu), 只需要多一個(gè)域用來指向前面一個(gè)結(jié)點(diǎn)就可以了.

這里使用ListNode來命名這個(gè)數(shù)據(jù)結(jié)構(gòu), 方便后續(xù)學(xué)習(xí) STL 進(jìn)行知識(shí)遷移

2.2 接口函數(shù)

// 創(chuàng)建并返回鏈表的頭結(jié)點(diǎn)
ListNode* ListCreate();
// 雙向鏈表銷毀
void ListDestroy(ListNode* phead);
// 雙向鏈表打印
void ListPrint(ListNode* phead);
// 雙向鏈表尾插
void ListPushBack(ListNode* phead, LTDataType x);
// 雙向鏈表尾刪
void ListPopBack(ListNode* phead);
// 雙向鏈表頭插
void ListPushFront(ListNode* phead, LTDataType x);
// 雙向鏈表頭刪
void ListPopFront(ListNode* phead);
// 雙向鏈表查找
ListNode* ListFind(ListNode* phead, LTDataType x);
// 雙向鏈表在 pos 的前面進(jìn)行插入
void ListInsert(ListNode* pos, LTDataType x);
// 雙向鏈表刪除 pos 位置的結(jié)點(diǎn)
void ListErase(ListNode* pos);

3. 接口函數(shù)的實(shí)現(xiàn)

因?yàn)橛刑摂M結(jié)點(diǎn)的存在, 所以除了創(chuàng)建頭結(jié)點(diǎn)的函數(shù), 其余接口函數(shù)都不會(huì)修改結(jié)構(gòu)體指針, 只是修改結(jié)構(gòu)體.

為了統(tǒng)一接口形式, 統(tǒng)一使用一級(jí)指針作為函數(shù)的形參類型. 需要修改頭結(jié)點(diǎn)的函數(shù)接口, 直接用返回值的方法達(dá)到修改頭結(jié)點(diǎn)指針的目的.

3.1 創(chuàng)建并返回鏈表的頭結(jié)點(diǎn) (ListCreate)

數(shù)據(jù)結(jié)構(gòu): 線性表(帶頭雙向循環(huán)鏈表實(shí)現(xiàn)),數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表

創(chuàng)建鏈表即為創(chuàng)建頭結(jié)點(diǎn), 它是一個(gè)虛擬結(jié)點(diǎn)(dummy node), 實(shí)際的值沒有意義.它的兩個(gè)指針都指向自己.

ListList.h

#pragma once 

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int LTDataType;
typedef struct ListNode
{
  LTDataType data;        //數(shù)據(jù)域
  struct ListNode* prev;  //指向前一個(gè)結(jié)點(diǎn)
  struct ListNode* next;  //指向后一個(gè)結(jié)點(diǎn)
}ListNode;

// 創(chuàng)建并返回鏈表的頭結(jié)點(diǎn)
ListNode* ListCreate();

修改頭結(jié)點(diǎn)指針, 使用返回值接受頭結(jié)點(diǎn)的指針

ListList.c

// 創(chuàng)建返回鏈表的頭結(jié)點(diǎn)
ListNode* ListCreate()
{
  // 動(dòng)態(tài)開辟空間創(chuàng)建頭結(jié)點(diǎn), 如果開辟失敗直接結(jié)束程序
  ListNode* head = BuyListNode(0);
  
  // 處理鏈表數(shù)據(jù), 數(shù)據(jù)域隨機(jī)值, 兩個(gè)指針指向自己
  head->next = head;
  head->prev = head;

  return head;
}

這里的 BuyListNode() 是一個(gè)我自己定義的靜態(tài)函數(shù), 方便后續(xù)復(fù)用. 函數(shù)的功能是用來從堆中申請(qǐng)空間用來創(chuàng)建一個(gè)新結(jié)點(diǎn).
// 創(chuàng)建一個(gè)新結(jié)點(diǎn)
static ListNode* BuyListNode(LTDataType x)
{
  ListNode* newNode = (ListNode*)malloc(sizeof(struct ListNode));

  if (newNode == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }

  newNode->data = x;
  newNode->next = NULL;
  newNode->prev = NULL;

  return newNode;
}

創(chuàng)建頭結(jié)點(diǎn)后, 使頭結(jié)點(diǎn)指向自己

test.c

void LinkListTest1()
{
  ListNode* head = ListCreate();

  free(head);
}

測(cè)試調(diào)試結(jié)果如下:

頭結(jié)點(diǎn)創(chuàng)建成功, 并且頭結(jié)點(diǎn)兩個(gè)指針都指向了自己

3.2 雙向鏈表打印 (ListPrint)

從第一個(gè)結(jié)點(diǎn)開始遍歷鏈表每個(gè)結(jié)點(diǎn), 并且將結(jié)點(diǎn)的數(shù)據(jù)域打印出來, 直到遇到頭結(jié)點(diǎn)結(jié)束
數(shù)據(jù)結(jié)構(gòu): 線性表(帶頭雙向循環(huán)鏈表實(shí)現(xiàn)),數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表

ListList.h

void ListPrint(ListNode* phead);

ListList.c

// 雙向鏈表打印
void ListPrint(ListNode* phead)
{
  assert(phead);  //確保頭結(jié)點(diǎn)存在

  printf("head <=> ");

  ListNode* cur = phead->next;  //從第一個(gè)結(jié)點(diǎn)開始遍歷, 直到遇到頭結(jié)點(diǎn)結(jié)束
  while (cur != phead)
  {
    printf("%d <=> ", cur->data);
    cur = cur->next;
  }

  printf("\n");
}

確保頭結(jié)點(diǎn)存在

cur第一次定位到頭結(jié)點(diǎn)后面一個(gè)結(jié)點(diǎn), 即第一個(gè)有效結(jié)點(diǎn)

順序遍歷并且打印

test.c

后續(xù)調(diào)試其他函數(shù)功能都會(huì)使用到 ListPrint 函數(shù), 這里就先不調(diào)試了.

3.3 雙向鏈表尾插 (ListPushBack)

先找到鏈表尾結(jié)點(diǎn)的位置, 在尾結(jié)點(diǎn)和頭結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)

數(shù)據(jù)結(jié)構(gòu): 線性表(帶頭雙向循環(huán)鏈表實(shí)現(xiàn)),數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表

ListList.h

void ListPushBack(ListNode* phead, LTDataType x);

ListList.c

// 雙向鏈表尾插
void ListPushBack(ListNode* phead, LTDataType x)
{
  assert(phead);  //確保頭結(jié)點(diǎn)存在

  ListNode* newNode = BuyListNode(x); //創(chuàng)建新結(jié)點(diǎn) 
  ListNode* tail = phead->prev;       //找到尾結(jié)點(diǎn)
  
  //更改鏈接關(guān)系
  tail->next = newNode;
  newNode->prev = tail;
  phead->prev = newNode;
  newNode->next = phead;

}

確保頭結(jié)點(diǎn)存在

更改鏈接關(guān)系, 需要修改一共四根指針的指向關(guān)系

test.c

void LinkListTest1()
{
  ListNode* head = ListCreate();
  ListPushBack(head, 1);
  ListPushBack(head, 2);
  ListPushBack(head, 3);
  ListPushBack(head, 4);
  ListPushBack(head, 5);
  ListPrint(head);
}

測(cè)試結(jié)果如下:

3.4 雙向鏈表尾刪 (ListPopBack)

找到新的尾結(jié)點(diǎn)位置, 更改鏈接關(guān)系后將原尾結(jié)點(diǎn)刪除
數(shù)據(jù)結(jié)構(gòu): 線性表(帶頭雙向循環(huán)鏈表實(shí)現(xiàn)),數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表

ListList.h

void ListPopBack(ListNode* phead);

ListList.c

// 雙向鏈表尾刪
void ListPopBack(ListNode* phead)
{
  assert(phead);                    //確保頭結(jié)點(diǎn)存在
  assert(phead->next != phead);     //確保有結(jié)點(diǎn)可刪

  ListNode* tail = phead->prev;     //找到要?jiǎng)h除的尾結(jié)點(diǎn)
  ListNode* tailPrev = tail->prev;  //找到新的尾結(jié)點(diǎn)

  //更改鏈接關(guān)系
  tailPrev->next = phead;
  phead->prev = tailPrev;

  free(tail); //釋放空間
}

test.c

void LinkListTest1()
{
  ListNode* head = ListCreate();
  ListPushBack(head, 1);
  ListPushBack(head, 2);
  ListPushBack(head, 3);
  ListPushBack(head, 4);
  ListPushBack(head, 5);
  ListPrint(head);

  ListPopBack(head);
  ListPrint(head);

  ListPopBack(head);
  ListPrint(head);
  
  ListPopBack(head);
  ListPopBack(head);
  ListPopBack(head);
  ListPrint(head);
  
  ListPopBack(head);
  ListPrint(head);
  
  ListDestroy(head);
}

測(cè)試結(jié)果如下:

3.5 雙鏈表頭插 (ListPushFront)

找到原第一個(gè)有效節(jié)點(diǎn), 在頭結(jié)點(diǎn)和這個(gè)結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)
數(shù)據(jù)結(jié)構(gòu): 線性表(帶頭雙向循環(huán)鏈表實(shí)現(xiàn)),數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表

ListList.h

void ListPushFront(ListNode* phead, LTDataType x);

ListList.c

// 雙向鏈表頭插
void ListPushFront(ListNode* phead, LTDataType x)
{
  assert(phead);  //確保頭結(jié)點(diǎn)存在

  ListNode* newNode = BuyListNode(x); //創(chuàng)建新結(jié)點(diǎn)
  ListNode* first = phead->next;      //找到原來的第一個(gè)結(jié)點(diǎn)

  //更新鏈接關(guān)系
  phead->next = newNode;
  newNode->prev = phead;
  newNode->next = first;
  first->prev = newNode;
}

確保頭結(jié)點(diǎn)存在

在頭結(jié)點(diǎn)和第一個(gè)有效結(jié)點(diǎn)之間插入新結(jié)點(diǎn)

test.c

void LinkListTest2()
{
  ListNode* head = ListCreate();

  ListPushFront(head, 1);
  ListPushFront(head, 2);
  ListPushFront(head, 3);
  ListPushFront(head, 4);
  ListPushFront(head, 5);
}

測(cè)試運(yùn)行結(jié)果如下:

3.6 雙鏈表頭刪 (ListPopFront)

先找到第一個(gè)和第二個(gè)有效結(jié)點(diǎn), 更新頭結(jié)點(diǎn)和第二個(gè)有效結(jié)點(diǎn)之間的鏈接關(guān)系后, 釋放第一個(gè)結(jié)點(diǎn)的空間.
數(shù)據(jù)結(jié)構(gòu): 線性表(帶頭雙向循環(huán)鏈表實(shí)現(xiàn)),數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表

ListList.h

void ListPopFront(ListNode* phead);

ListList.c

// 雙向鏈表頭刪
void ListPopFront(ListNode* phead)
{
  assert(phead);  //確保哨兵結(jié)點(diǎn)存在
  assert(phead->next != phead); //確保鏈表不為空

  ListNode* first = phead->next;  //找到頭結(jié)點(diǎn)位置
  ListNode* second = first->next; //找到頭結(jié)點(diǎn)后一個(gè)結(jié)點(diǎn)的位置

  //更新鏈接關(guān)系
  phead->next = second;
  second->prev = phead;

  free(first); //釋放空間
}

test.c

void LinkListTest2()
{
  ListNode* head = ListCreate();

  ListPushFront(head, 1);
  ListPushFront(head, 2);
  ListPushFront(head, 3);
  ListPushFront(head, 4);
  ListPushFront(head, 5);

  ListPrint(head);
  
  ListPopFront(head);
  ListPrint(head);

  ListPopFront(head);
  ListPopFront(head);
  ListPopFront(head);
  ListPopFront(head);
  ListPrint(head);

  ListPopFront(head);
  ListPrint(head);

  ListDestroy(head);
}

測(cè)試結(jié)果如下:

3.7 雙鏈表查找 (ListFind)

從第一個(gè)有效結(jié)點(diǎn)開始向后遍歷鏈表, 判斷是否有想要查找的數(shù)據(jù), 直到遇到頭結(jié)點(diǎn). 未查找到返回空指針, 查找到返回該結(jié)點(diǎn)的地址
數(shù)據(jù)結(jié)構(gòu): 線性表(帶頭雙向循環(huán)鏈表實(shí)現(xiàn)),數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表

ListList.h

ListNode* ListFind(ListNode* phead, LTDataType x);

ListList.c

// 雙向鏈表查找
ListNode* ListFind(ListNode* phead, LTDataType x)
{
  assert(phead);  //確保哨兵結(jié)點(diǎn)存在

  ListNode* cur = phead->next;

  while (cur != phead)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }

  return NULL;
}

test.c

void LinkListTest3()
{
  ListNode* head = ListCreate();
  ListPushBack(head, 1);
  ListPushBack(head, 2);
  ListPushBack(head, 3);
  ListPushBack(head, 4);
  ListPushBack(head, 5);
  ListPrint(head);

  ListNode* pos;
  pos = ListFind(head, 2);
  printf("pos <=> ");
  while (pos && pos != head)
  {
    printf("%d <=> ", pos->data);
    pos = pos->next;
  }
  puts("\n");

  pos = ListFind(head, 6);
  printf("pos <=> ");
  while (pos && pos != head)
  {
    printf("%d <=> ", pos->data);
    pos = pos->next;
  }
  puts("\n");
}

測(cè)試運(yùn)行結(jié)果如下:

3.8 雙向鏈表在 pos 的前面進(jìn)行插入 (LinkInsert)

先找到 pos 的前面一個(gè)結(jié)點(diǎn)的位置, 隨后在這個(gè)結(jié)點(diǎn)和 pos 之間插入新結(jié)點(diǎn)
數(shù)據(jù)結(jié)構(gòu): 線性表(帶頭雙向循環(huán)鏈表實(shí)現(xiàn)),數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表

LinkList.h

void ListInsert(ListNode* pos, LTDataType x);

LinkList.c

// 雙向鏈表在 pos 之前插入
void ListInsert(ListNode* pos, LTDataType x)
{
  assert(pos);  //確保pos合法

  ListNode* newNode = BuyListNode(x); //創(chuàng)建新結(jié)點(diǎn)
  ListNode* posPrev = pos->prev;      //找到 pos 前一個(gè)結(jié)點(diǎn)的位置

  //更新鏈接方式
  posPrev->next = newNode;
  newNode->prev = posPrev;

  newNode->next = pos;
  pos->prev = newNode;
}

test.c

void LinkListTest3()
{
  ListNode* head = ListCreate();

  ListPushBack(head, 1);
  ListPushBack(head, 2);
  ListPushBack(head, 3);
  ListPushBack(head, 4);
  ListPushBack(head, 5);
  ListPrint(head);

  ListNode* pos;

  pos = ListFind(head, 1);
  if (pos)
  {
    ListInsert(pos, -1);
    ListPrint(head);
  }

  pos = ListFind(head, 4);
  if (pos)
  {
    ListInsert(pos, -4);
    ListPrint(head);
  }

  pos = ListFind(head, 6);
  if (pos)
  {
    ListInsert(pos, -6);
    ListPrint(head);
  }

  ListDestroy(head);
}

測(cè)試運(yùn)行結(jié)果如下:

3.9 雙向鏈表刪除 pos 位置的結(jié)點(diǎn) (ListErase)

先找到 pos 的前后兩個(gè)結(jié)點(diǎn)的位置, 隨后更新兩個(gè)結(jié)點(diǎn)之間的鏈接關(guān)系, 最后刪除 pos 結(jié)點(diǎn)
數(shù)據(jù)結(jié)構(gòu): 線性表(帶頭雙向循環(huán)鏈表實(shí)現(xiàn)),數(shù)據(jù)結(jié)構(gòu),數(shù)據(jù)結(jié)構(gòu),鏈表

LinkList.h

void ListErase(ListNode* pos);

LinkList.c

// 雙向鏈表刪除 pos 位置的結(jié)點(diǎn)
void ListErase(ListNode* pos)
{
  assert(pos);  //確保 pos 合法

  ListNode* posPrev = pos->prev;    //找到 pos 前一個(gè)結(jié)點(diǎn)的位置
  ListNode* posNext = pos->next;    //找到 pos 后一個(gè)結(jié)點(diǎn)的位置

  //更新鏈接方式
  posPrev->next = posNext;
  posNext->prev = posPrev;

  free(pos);  //釋放空間
}

test.c

void LinkListTest3()
{
  ListNode* head = ListCreate();

  ListPushBack(head, 1);
  ListPushBack(head, 2);
  ListPushBack(head, 3);
  ListPushBack(head, 4);
  ListPushBack(head, 5);
  ListPrint(head);

  ListNode* pos;

  pos = ListFind(head, 1);
  if (pos)
  {
    ListErase(pos);
    ListPrint(head);
  }

  pos = ListFind(head, 4);
  if (pos)
  {
    ListErase(pos);
    ListPrint(head);
  }

  pos = ListFind(head, 6);
  if (pos)
  {
    ListErase(pos);
    ListPrint(head);
  }

  ListDestroy(head);
}

測(cè)試運(yùn)行結(jié)果如下:

3.10 雙向鏈表銷毀 (ListDestroy)

LinkList.h

void ListDestroy(ListNode* phead);

LinkList.c

// 雙向鏈表銷毀
void ListDestroy(ListNode* phead)
{
  assert(phead);  //確保哨兵結(jié)點(diǎn)存在

  ListNode* cur = phead->next;

  while (cur != phead)
  {
    ListNode* nextNode = cur->next;
    free(cur);
    cur = nextNode;
  }
  free(phead);
}

4. 總結(jié)

不同點(diǎn)	順序表	鏈表
存儲(chǔ)空間上	物理上一定連續(xù)	邏輯上連續(xù),但物理上不一定連續(xù)
隨機(jī)訪問	支持: $O (1)$	不支持: $O (N)$
任意位置插入或者刪除元素	可能需要搬移元素, 效率低 $O (N)$	只需要修改指針指向
插入	動(dòng)態(tài)順序表, 空間不夠時(shí), 需要擴(kuò)容	沒有容量的概念
應(yīng)用場(chǎng)景	元素高效存儲(chǔ) + 頻繁訪問	任意位置插入和刪除頻繁
緩存利用率	高	低

5. 完整代碼

LinkList.h

#pragma once 

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int LTDataType;
typedef struct ListNode
{
  LTDataType data;        //數(shù)據(jù)域
  struct ListNode* prev;  //指向前一個(gè)結(jié)點(diǎn)
  struct ListNode* next;  //指向后一個(gè)結(jié)點(diǎn)
}ListNode;

// 創(chuàng)建并返回鏈表的頭結(jié)點(diǎn)
ListNode* ListCreate();
// 雙向鏈表銷毀
void ListDestroy(ListNode* phead);
// 雙向鏈表打印
void ListPrint(ListNode* phead);
// 雙向鏈表尾插
void ListPushBack(ListNode* phead, LTDataType x);
// 雙向鏈表尾刪
void ListPopBack(ListNode* phead);
// 雙向鏈表頭插
void ListPushFront(ListNode* phead, LTDataType x);
// 雙向鏈表頭刪
void ListPopFront(ListNode* phead);
// 雙向鏈表查找
ListNode* ListFind(ListNode* phead, LTDataType x);
// 雙向鏈表在 pos 的前面進(jìn)行插入
void ListInsert(ListNode* pos, LTDataType x);
// 雙向鏈表刪除 pos 位置的結(jié)點(diǎn)
void ListErase(ListNode* pos);

LinkList.c

#include "LinkList.h"

// 創(chuàng)建一個(gè)新結(jié)點(diǎn)
static ListNode* BuyListNode(LTDataType x)
{
  ListNode* newNode = (ListNode*)malloc(sizeof(struct ListNode));

  if (newNode == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }

  newNode->data = x;
  newNode->next = NULL;
  newNode->prev = NULL;

  return newNode;
}

// 創(chuàng)建返回鏈表的頭結(jié)點(diǎn)
ListNode* ListCreate()
{
  // 動(dòng)態(tài)開辟空間創(chuàng)建頭結(jié)點(diǎn), 如果開辟失敗直接結(jié)束程序
  ListNode* head = BuyListNode(0);
  
  // 處理鏈表數(shù)據(jù), 數(shù)據(jù)域隨機(jī)值, 兩個(gè)指針指向自己
  head->next = head;
  head->prev = head;

  return head;
}

// 雙向鏈表打印
void ListPrint(ListNode* phead)
{
  assert(phead);  //確保哨兵結(jié)點(diǎn)存在

  printf("head <=> ");

  ListNode* cur = phead->next;  //從頭結(jié)點(diǎn)開始遍歷, 直到遇到哨兵結(jié)點(diǎn)結(jié)束
  while (cur != phead)
  {
    printf("%d <=> ", cur->data);
    cur = cur->next;
  }

  printf("\n");
}

// 雙向鏈表銷毀
void ListDestroy(ListNode* phead)
{
  assert(phead);  //確保哨兵結(jié)點(diǎn)存在

  ListNode* cur = phead->next;

  while (cur != phead)
  {
    ListNode* nextNode = cur->next;
    free(cur);
    cur = nextNode;
  }
  free(phead);
}

// 雙向鏈表尾插
void ListPushBack(ListNode* phead, LTDataType x)
{
  assert(phead);  //確保哨兵結(jié)點(diǎn)存在

  ListNode* newNode = BuyListNode(x); //創(chuàng)建新結(jié)點(diǎn) 
  ListNode* tail = phead->prev;       //找到尾結(jié)點(diǎn)
  
  //更改鏈接關(guān)系
  tail->next = newNode;
  newNode->prev = tail;
  phead->prev = newNode;
  newNode->next = phead;

}

// 雙向鏈表尾刪
void ListPopBack(ListNode* phead)
{
  assert(phead);                    //確保哨兵結(jié)點(diǎn)存在
  assert(phead->next != phead);     //確保有結(jié)點(diǎn)可刪

  ListNode* tail = phead->prev;     //找到要?jiǎng)h除的尾結(jié)點(diǎn)
  ListNode* tailPrev = tail->prev;  //找到新的尾結(jié)點(diǎn)

  //更改鏈接關(guān)系
  tailPrev->next = phead;
  phead->prev = tailPrev;

  free(tail); //釋放空間
}

// 雙向鏈表頭插
void ListPushFront(ListNode* phead, LTDataType x)
{
  assert(phead);  //確保哨兵結(jié)點(diǎn)存在

  ListNode* newNode = BuyListNode(x); //創(chuàng)建新結(jié)點(diǎn)
  ListNode* first = phead->next;      //找到原來的頭結(jié)點(diǎn)

  //更新鏈接關(guān)系
  phead->next = newNode;
  newNode->prev = phead;
  newNode->next = first;
  first->prev = newNode;

}

// 雙向鏈表頭刪
void ListPopFront(ListNode* phead)
{
  assert(phead);  //確保哨兵結(jié)點(diǎn)存在
  assert(phead->next != phead); //確保鏈表不為空

  ListNode* first = phead->next;  //找到頭結(jié)點(diǎn)位置
  ListNode* second = first->next; //找到頭結(jié)點(diǎn)后一個(gè)結(jié)點(diǎn)的位置

  //更新鏈接關(guān)系
  phead->next = second;
  second->prev = phead;

  free(first); //釋放空間
}

// 雙向鏈表查找
ListNode* ListFind(ListNode* phead, LTDataType x)
{
  assert(phead);  //確保哨兵結(jié)點(diǎn)存在

  ListNode* cur = phead->next;

  while (cur != phead)
  {
    if (cur->data == x)
    {
      return cur;
    }
    cur = cur->next;
  }

  return NULL;
}

// 雙向鏈表在 pos 之前插入
void ListInsert(ListNode* pos, LTDataType x)
{
  assert(pos);  //確保pos合法

  ListNode* newNode = BuyListNode(x); //創(chuàng)建新結(jié)點(diǎn)
  ListNode* posPrev = pos->prev;      //找到 pos 前一個(gè)結(jié)點(diǎn)的位置

  //更新鏈接方式
  posPrev->next = newNode;
  newNode->prev = posPrev;

  newNode->next = pos;
  pos->prev = newNode;
}
// 雙向鏈表刪除 pos 位置的結(jié)點(diǎn)
void ListErase(ListNode* pos)
{
  assert(pos);  //確保 pos 合法

  ListNode* posPrev = pos->prev;    //找到 pos 前一個(gè)結(jié)點(diǎn)的位置
  ListNode* posNext = pos->next;    //找到 pos 后一個(gè)結(jié)點(diǎn)的位置

  //更新鏈接方式
  posPrev->next = posNext;
  posNext->prev = posPrev;

  free(pos);  //釋放空間
}

test.c

#include "LinkList.h"

void LinkListTest1()
{
  ListNode* head = ListCreate();
  ListPushBack(head, 1);
  ListPushBack(head, 2);
  ListPushBack(head, 3);
  ListPushBack(head, 4);
  ListPushBack(head, 5);
  ListPrint(head);

  ListPopBack(head);
  ListPrint(head);

  ListPopBack(head);
  ListPrint(head);
  
  ListPopBack(head);
  ListPopBack(head);
  ListPopBack(head);
  ListPrint(head);
  
  ListPopBack(head);
  ListPrint(head);
  
  ListDestroy(head);
}

void LinkListTest2()
{
  ListNode* head = ListCreate();

  ListPushFront(head, 1);
  ListPushFront(head, 2);
  ListPushFront(head, 3);
  ListPushFront(head, 4);
  ListPushFront(head, 5);

  ListPrint(head);
  
  ListPopFront(head);
  ListPrint(head);

  ListPopFront(head);
  ListPopFront(head);
  ListPopFront(head);
  ListPopFront(head);
  ListPrint(head);

  ListPopFront(head);
  ListPrint(head);

  ListDestroy(head);
}

void LinkListTest3()
{
  ListNode* head = ListCreate();

  ListPushBack(head, 1);
  ListPushBack(head, 2);
  ListPushBack(head, 3);
  ListPushBack(head, 4);
  ListPushBack(head, 5);
  ListPrint(head);

  ListNode* pos;

  pos = ListFind(head, 1);
  ListInsert(pos, 0);
  ListErase(pos);
  ListPrint(head);

  pos = ListFind(head, 4);
  ListInsert(pos, 10);
  ListPrint(head);

  pos = ListFind(head, 11);
  ListInsert(pos, 12);
  ListPrint(head);

  ListDestroy(head);
}

void LinkListTest4()
{
  ListNode* head = ListCreate();

  ListPushBack(head, 1);
  ListPushBack(head, 2);
  ListPushBack(head, 3);
  ListPushBack(head, 4);
  ListPushBack(head, 5);

  ListNode* pos;

  pos = ListFind(head, 2);
  printf("pos <=> ");
  while (pos && pos != head)
  {
    printf("%d <=> ", pos->data);
    pos = pos->next;
  }
  puts("\n");

  pos = ListFind(head, 6);
  printf("pos <=> ");
  while (pos && pos != head)
  {
    printf("%d <=> ", pos->data);
    pos = pos->next;
  }
  puts("\n");
}

void LinkListTest5()
{
  ListNode* head = ListCreate();

  ListPushBack(head, 1);
  ListPushBack(head, 2);
  ListPushBack(head, 3);
  ListPushBack(head, 4);
  ListPushBack(head, 5);
  ListPrint(head);

  ListNode* pos;

  pos = ListFind(head, 1);
  if (pos)
  {
    ListInsert(pos, -1);
    ListPrint(head);
  }

  pos = ListFind(head, 4);
  if (pos)
  {
    ListInsert(pos, -4);
    ListPrint(head);
  }

  pos = ListFind(head, 6);
  if (pos)
  {
    ListInsert(pos, -6);
    ListPrint(head);
  }

  ListDestroy(head);
}

void LinkListTest6()
{
  ListNode* head = ListCreate();

  ListPushBack(head, 1);
  ListPushBack(head, 2);
  ListPushBack(head, 3);
  ListPushBack(head, 4);
  ListPushBack(head, 5);
  ListPrint(head);

  ListNode* pos;

  pos = ListFind(head, 1);
  if (pos)
  {
    ListErase(pos);
    ListPrint(head);
  }

  pos = ListFind(head, 4);
  if (pos)
  {
    ListErase(pos);
    ListPrint(head);
  }

  pos = ListFind(head, 6);
  if (pos)
  {
    ListErase(pos);
    ListPrint(head);
  }

  ListDestroy(head);
}

int main(void)
{
  //LinkListTest1();
  //LinkListTest2();
  //LinkListTest3();
  //LinkListTest4();
  //LinkListTest5();
  LinkListTest6();
  return 0;
}

本章完.文章來源地址http://www.zghlxwxcb.cn/news/detail-626859.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu): 線性表(帶頭雙向循環(huán)鏈表實(shí)現(xiàn))的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！