線性表的鏈式存儲結構

數據結構系列文章 第三章 循環鏈表、雙向鏈表

---

文章目錄

• 線性表的鏈式存儲結構
• 前言
• 一、循環鏈表
• • （一）定義
  • （二）尾指針
• 二、雙向鏈表
• • （一）定義
  • （二）代碼
• 總結

---

前言

提示：本系列文章均使用Visual Studio 2019編程，編程語言為c語言。

一、循環鏈表

（一）定義

將單鏈表的終端結點的指針端由空指針改為指向頭結點，這樣就讓整個單鏈表形成一個循環，這時頭尾相連的單鏈表就稱為單循環鏈表，即循環鏈表，下圖的head，即為頭指針。

將循環鏈表和單鏈表相比較，其實就在循環的判斷條件上差別，單鏈表判斷是否為空（p!=null 或 p->null!=null），循環鏈表是否等于頭結點(p!=head 或 p->next!=head)。

（二）尾指針

事實上我們不用頭指針，而改用指向終端結點的尾指針來表示循環鏈表，這樣就使查找開始結點和終端結點就很方便。

我們通過一張圖，進一步了解其尾指針的作用：

二、雙向鏈表

（一）定義

在單鏈表結構中，結點只有一個指向后繼的指針域next，若要查找某個結點只能順著單鏈表尋找它的后繼結點，為了能夠高效地查找一個結點，我們只需從頭指針出發查找其前驅，即我們增加一個指向其直接前驅的指針域prior，這樣我們就構成了一個雙向鏈表。其中第一個結點的前趨結點為NULL，最后一個結點的后繼結點也為NULL。

指針域（prior）數據域指針域（next）

即，數據域為data數據，存儲一個數據元素的信息；prior指針域為前驅指針域，用于存儲其直接前驅存儲地址的信息；next指針域為后繼指針域，用于存儲其后繼存儲地址的信息。

（二）代碼

雙向單鏈表的建立
分別定義數據域，前驅指針域以及后繼指針域。

typedef char DataType; typedef struct dunode {DataType data; //數據域struct dunode *prior; //前驅指針域struct dunode *next; //后繼指針域 }DuLinkList;

雙向單鏈表的插入
若要將新結點s（x為其值）插入到雙向鏈表中兩個結點o、p之間，即在p結點之前插入結點s，首先我們應該將要插入的新結點s的前驅指針域指向結點p的前一個結點o，將結點o的后繼指針域指向要插入的新結點s，然后將結點s的后繼指針域指向p結點，并將結點p的前驅指針域指向結點s。

void InsertList(InsertElem *p,DataType x) {InsertElem *s;s=(InsertElem *)malloc(sizeof(InsertElem)); //生成新結點ss->data=x;s->prior=p->prior; //也可寫成s->prior=op->prior->next=s; //也可寫成o->next=ss->next=p;p->prior=s; //也可寫成o=s }

雙向鏈表的刪除
若要刪除表中的結點p，我們首先應該將結點p的前一個結點的后繼指針域指向結點p的后繼指針域，將結點p后一個結點的前驅指針域指向結點p的后繼指針域，然后釋放結點p的空間。

void DeleteElem(DeleteList *p,DataType *x) {*x=p->data;p->prior->next=p->next;p->next->prior=p->prior;free(p); }

總結

以上就是本次的筆記內容，本文介紹了循環鏈表、雙向鏈表的各項操作，筆記若有錯誤，還望指出！！！

---

附：在下一文章會介紹棧的各項操作，持續更新ing……

總結

以上是生活随笔為你收集整理的《数据结构》c语言版学习笔记——其他链表（线性表的链式存储结构Part2）的全部內容，希望文章能夠幫你解決所遇到的問題。

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