循環(huán)鏈表+雙向鏈表

循環(huán)鏈表

循環(huán)鏈表是頭尾相接的鏈表(即表中最后一個結點的指針域指向頭結點，整個鏈表形成一個環(huán))(circular linked list)

**優(yōu)點：**從表中任一結點出發(fā)均可訪問全部結點

循環(huán)鏈表與單鏈表的主要差別當鏈表遍歷時，判別當前指針p是否指向表尾結點的終止條件不同。在單鏈表中，判別條件為p!=NULL或p->next=NULL，而循環(huán)單鏈表的判別條件為p!=L或p->next!=L

#include<stdio.h>
#include<stdlib.h>typedef struct Lnode {int data;struct Lnode* next;
}Lnode,*LinkList;/*初始化循環(huán)單鏈表*/
Lnode* InitList(LinkList L)
{L = (Lnode*)malloc(sizeof(Lnode));if (L == NULL){//提示分配失敗}L->next = L;
}//判斷循環(huán)單鏈表是否為空 （終止條件為p或p->next是否等于頭指針）
int Isempty(LinkList L)
{if (L->next == L){return 1;}else {return -1;}
}//判斷結點p是否為循環(huán)單鏈表的表尾結點
int isTail(LinkList L, Lnode* p)
{if (p->next == L){return 1;}else {return -1;}
}

單鏈表和循環(huán)單鏈表的比較：
**單鏈表：**從一個結點出發(fā)只能找到該結點后續(xù)的各個結點；對鏈表的操作大多都在頭部或者尾部；設立頭指針，從頭結點找到尾部的時間復雜度=O(n)，即對表尾進行操作需要O(n)的時間復雜度;
**循環(huán)單鏈表：**從一個結點出發(fā)，可以找到其他任何一個結點；設立尾指針，從尾部找到頭部的時間復雜度為O(1)，即對表頭和表尾進行操作都只需要O(1)的時間復雜度;

雙向鏈表

為了克服單鏈表的這一缺點，老科學家們設計了雙向鏈表(double linked list)是在單鏈表的每個結點中再設計一個指向其前驅結點的指針域。所以在雙向鏈表中的結點有兩個指針域，一個指向直接后繼，另一個指向直接前驅。這樣鏈表中有兩個不同方向的鏈。

與單循環(huán)鏈表類似雙向鏈表也可以有循環(huán)表(首尾相接形成"環(huán)"[2個])

讓頭結點的前驅指針指向鏈表的最后一個結點

最后一個結點的后繼指針指向頭結點

雙向鏈表結構有對稱性(設指針p指向某一個結點)

p->prior->next=p=p->next->prior(前進一步后退一步相當于原地踏步)

在雙向鏈表中有些操作(ListLength,GetElemment等因為只涉及一個方向的指針他們的算法與線性表的相同)但在插入和刪除需要修改兩個方向上的指針兩者的算法復雜度均為O(n)

雙向鏈表的插入

單鏈表只需修改兩個指針，而雙向鏈表修改四個指針

算法復雜度O(n)

總結

鏈式存儲結構的優(yōu)點：

• 結點空間可以動態(tài)申請和釋放；

• 數(shù)據(jù)元素的邏輯次序靠結點的指針來指示，插入和刪除不需要移動元素。

鏈式存儲結構的缺點：

• 存儲密度小，每個結點的指針域需額外占用存儲空間。當每個結點的數(shù)據(jù)域所占的字節(jié)數(shù)不多時，指針域所占的存儲空間的比重顯得很大。

• 存儲密度是指結點數(shù)據(jù)本身占用的空間**/結點占用的空間總量**

鏈式存儲結構是非隨機存取結構。對任一結點的操作都要從頭指針依指針鏈查找到該結點，這增加了算法的復雜度。(對某個結點操作一般要先找到該結點)

代碼總結

雙向鏈表

#include<stdio.h>
#include<stdlib.h>typedef struct Lnode {int data;                       //數(shù)據(jù)域struct Lnode* prior, * next;    //前驅和后繼指針
}DLnode,*DLinkList;DLnode* InitDLinkList(DLinkList L)
{L = (DLnode*)malloc(sizeof(DLnode));if (L == NULL){return -1;     //分配失敗}else{L->prior = NULL;    //頭指針的前驅指針永遠指向NULLL->next = NULL;     }return L;
}void InsertNextDLnode(DLnode* p, DLnode* s) { //將結點 *s 插入到結點 *p之后if (p == NULL || s == NULL) //非法參數(shù)return;s->next = p->next;if (p->next != NULL)   //p不是最后一個結點=p有后繼結點  p->next->prior = s;s->prior = p;p->next = s;return;
}
/*
按位序插入操作：
思路：從頭結點開始，找到某個位序的前驅結點，對該前驅結點執(zhí)行后插操作；
前插操作：
思路：找到給定結點的前驅結點，再對該前驅結點執(zhí)行后插操作；*//*刪除*/
/*刪除p結點的后繼結點*/
void DeleteDLnode_next(DLnode* p)
{if (p == NULL) {return;}DLnode* q = p->next;    //找到p的后繼結點if (q == NULL) {return;}p->next = q->next;if (q->next != NULL)  //q不是最后一個結點{q->next->prior = p;}free(q);
}/*銷毀一個雙向鏈表*/
void DestotyDLinkList(DLinkList L)
{//循環(huán)釋放各個數(shù)據(jù)結點while (L->next != NULL){DeleteDLnode_next(L);  //刪除頭結點的后繼節(jié)點free(L);   //釋放頭結點L = NULL;}
}/*雙鏈表的遍歷操作——前向遍歷*/
while (p != NULL)
{//對接點p做相應處理，并打印p = p->prior;
}/*雙鏈表的遍歷操作——后向遍歷*/
while (p != NULL) {//對結點p做相應處理，eg打印p = p->next;
}

雙向循環(huán)鏈表

#include<stdio.h>
#include<stdlib.h>typedef struct Lnode {int data;                       //數(shù)據(jù)域struct Lnode* prior, * next;    //前驅和后繼指針
}DLnode, * DLinkList;/*初始化空的循環(huán)雙向鏈表*/
void InitDLinkList(DLinkList L)
{L=(DLnode*)malloc(sizeof(DLnode))；if (L == NULL){//提示空間不足，分配失敗return;}L->prior = L;    //頭結點的前驅&后繼指針都指向頭結點L->next = L;
}//判斷循環(huán)雙向鏈表是否為空
int IsEmpty(DLinkList L)
{if (L->next == L){return 1;}else return -1;
}//判斷p結點是否為循環(huán)雙向鏈表的表尾結點
int IsTail(DLinkList L, DLnode* p) {if (p->next == L){return 1;}else return -1;
}//雙向循環(huán)鏈表的插入
void InsertNextDLnode(DLnode* p, DLnode* s)
{s->next = p->next;p->next->prior = s;s->prior = p;p->next = s;
}//雙向鏈表的刪除操作
void DeleteDLnode(DLnode* p)
{if (p == NULL) {return;}DLnode* q = p->next;    //找到p的后繼結點if (q == NULL) {return;}p->next = q->next;if (q->next != NULL)  //q不是最后一個結點{q->next->prior = p;}free(q);
}