文章目錄

• 前言
• 實現
• • （1）結構定義
  • （2）基本函數
  • （3）操作實現
• 測試
• 代碼

前言

鏈表的類型有很多種（根據帶頭或不帶頭，循環或非循環等等），但是我們重點研究的只有兩種，一種結構非常簡單是無頭單向非循環鏈表，有關它的操作見

數據結構-線性表之單鏈表

這種結果在開發中基本不會使用，因為因為結構簡單往往意味著操作復雜，比如在OJ題，有關鏈表的題使用的都是這種結構，關于這些OJ題感興趣的見

鏈表經典題

另一種則是鏈表中結構最為復雜的——帶頭結點的雙向循環鏈表

這種鏈表結構復雜，但卻操作很簡單，比如最常用的尾插操作，其時間復雜度為O(1)。同時C++中STL中的list就是這種結構
對于這種結構，由于它帶了頭結點（也稱為哨兵結點），所以很多操作不用像單鏈表那樣還要額外處理第一個結點為空的情況，而又因為它帶了尾節點，所以也方便尾插等操作

注意其鏈表的空的判斷情況

head->prev=head haed->next=head

實現

（1）結構定義

typedef struct DListNode {struct ListNode* next;//指向前一個結點struct ListNode* prev;//指向后一個結點DLdatatype val; }DListNode;

（2）基本函數

1：申請結點、

2：打印
對于打印稍加注意，在這種結構中是沒有NULL的，也就是判斷結束的條件不能去找NULL，而是要找頭

（3）操作實現

1：尾插


2：尾刪


3：頭插

4：頭刪

5：找結點

6：任意位置插入（某節點之后）

7：在任意位置插入（某節點之前）

8：任意位置刪除

9：銷毀

測試

代碼

Dlist.h

#pragma once #include <stdio.h> #include <assert.h> #include <stdlib.h>typedef int DLdatatype; typedef struct DListNode {struct DListNode* next;struct DListNode* prev;DLdatatype val;}DListNode;void printlist(DListNode* head);//打印 DListNode* CreatNode(DLdatatype x);//申請結點void ListPushBack(DListNode* head, DLdatatype x);//尾插 void ListPopBack(DListNode* head);//尾刪 void listPushFront(DListNode* head, DLdatatype x);//頭插 void listPopFront(DListNode* head);//頭刪DListNode* find(DListNode* head, DLdatatype x);//找某個元素 void listinseret_behind(DListNode* head,DLdatatype pos, DLdatatype x);//任意位置插入(后面) void listinseret_front(DListNode* head,DLdatatype pos, DLdatatype x);//任意位置插入(前面) void listdelete(DListNode* head,DLdatatype pos);//任意位置刪除void listdestory(DListNode* head);//鏈表銷毀

Dlist.c

#include "DList.h"DListNode* CreatNode(DLdatatype x) {DListNode* NewNode = (DListNode*)malloc(sizeof(DListNode));NewNode->val = x;NewNode->next = NULL;NewNode->prev = NULL;return NewNode; }void printlist(DListNode* head) {assert(head);DListNode* cur = head->next;while (cur!=head){printf("%d->", cur->val);cur = cur->next;}if (head->next == head)printf("NULL");}void ListPushBack(DListNode* head, DLdatatype x) {assert(head);DListNode* NewNode=CreatNode(x);NewNode->next = head;(head->prev)->next = NewNode;NewNode->prev = head->prev;head->prev = NewNode; }void ListPopBack(DListNode* head) {assert(head);assert(head->next != head);//如果鏈表為空，斷言DListNode* delelte = head->prev;head->prev = delelte->prev;delelte->prev->next = head;free(delelte); }void listPushFront(DListNode* head, DLdatatype x) {assert(head);DListNode* NewNode = CreatNode(x);NewNode->next = head->next;NewNode->prev = head;head->next->prev = NewNode;head->next = NewNode;} void listPopFront(DListNode* head) {assert(head);assert(head->next != head);DListNode* first = head->next;first->next->prev = head;head->next = first->next;free(first);}DListNode* find(DListNode* head, DLdatatype x) {assert(head);DListNode* cur = head->next;while (cur->next != head && cur->val != x){cur = cur->next;}if (cur->next == head && cur->val!=x){return NULL;//未找到}else{return cur;//否則返回}}void listinseret_behind(DListNode* head, DLdatatype pos, DLdatatype x) {assert(head);DListNode* insert = find(head, pos);if (insert == NULL){printf("%d不存在\n", pos);}else{DListNode* NewNode = CreatNode(x);NewNode->next = insert->next;NewNode->prev = insert;insert->next->prev = NewNode;insert->next = NewNode;}}void listinseret_front(DListNode* head, DLdatatype pos, DLdatatype x) {assert(head);DListNode* insert = find(head, pos);if (insert == NULL){printf("%d不存在\n", pos);}{DListNode* NewNode = CreatNode(x);NewNode->next = insert;NewNode->prev = insert->prev;NewNode->prev->next = NewNode;insert->prev = NewNode;}}void listdelete(DListNode* head, DLdatatype pos) {assert(head);assert(pos != head);DListNode* delete = find(head, pos);if (delete == NULL){printf("%d不存在\n", pos);}else{delete->prev->next = delete->next;delete->next->prev = delete->prev;free(delete);}}void listdestory(DListNode* head) {assert(head);DListNode* cur = head->next;DListNode* pre = NULL;while (cur->next != head){pre = cur;cur = cur->next;free(pre);}head->next =head;head->prev = head;}

test.c

#include "DList.h"void test() {DListNode* head=(DListNode*)malloc(sizeof(DListNode));head->prev = head;head->next = head;printf("尾插4個結點\n");ListPushBack(head, 1);ListPushBack(head, 2);ListPushBack(head, 3);ListPushBack(head, 4);printlist(head);printf("\n");printf("\n");printf("尾刪2個結點\n");ListPopBack(head);ListPopBack(head);printlist(head);printf("\n");printf("\n");printf("頭插4個結點\n");listPushFront(head, 5);listPushFront(head, 6);listPushFront(head, 7);listPushFront(head, 8);printlist(head);printf("\n");printf("\n");printf("頭刪2個結點\n");listPopFront(head);listPopFront(head);printlist(head);printf("\n");printf("\n");printf("在5后面插入7\n");listinseret_behind(head, 5, 7);printlist(head);printf("\n");printf("\n");printf("刪除1\n");listdelete(head, 1);printlist(head);printf("\n");printf("\n");printf("銷毀\n");listdestory(head);printlist(head);printf("\n");printf("\n");}int main() {test(); }

總結

以上是生活随笔為你收集整理的数据结构-线性表之带头结点的双向循环链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。