循環(huán)鏈表與雙向鏈表
循環(huán)鏈表：
循環(huán)鏈表也是一種線性表的鏈式存儲結(jié)構(gòu)，其實他和單鏈表很像澜躺，其特點是它是一個環(huán)蝉稳，也就是指單鏈表的最后一個結(jié)點的指針域不為空掘鄙，而是指向頭結(jié)點或是第一個結(jié)點耘戚，這樣整個鏈表就形成了一個環(huán)通铲。循環(huán)鏈表一般可以分為單循環(huán)鏈表和多循環(huán)鏈表，多循環(huán)鏈表也就是將表中的結(jié)點鏈在多個環(huán)上颅夺。
這種方式在單向和雙向鏈表中皆可實現(xiàn)朋截，其轉(zhuǎn)換方法是，選擇從任一結(jié)點開始沿著列表的任一方向直到返回開始的結(jié)點部服。
除此之外，還有一種模擬的循環(huán)鏈表拗慨，就是在訪問最后一結(jié)點之后的時候廓八，手工跳轉(zhuǎn)到第一個結(jié)點赵抢，訪問第一個結(jié)點之前的結(jié)點也一樣剧蹂。通過這樣的方式也可以實現(xiàn)循環(huán)鏈表的功能，在直接運用循環(huán)鏈表比較麻煩或者可能會出現(xiàn)問題的時候可以用烦却。
循環(huán)鏈表的操作：
下面主要講單循環(huán)鏈表宠叼，單循環(huán)鏈表的操作和單鏈表的操作沒什么區(qū)別，只是循環(huán)結(jié)束的條件判斷不再是判斷指針p或p->next是否為空其爵，而是判斷他們是否等于頭結(jié)點冒冬。
有時候，循環(huán)鏈表中會設(shè)置一個指向表尾的尾指針摩渺，這樣對某些操作會很方便
代碼實現(xiàn)
其實絕大部分操作和單鏈表都很相像简烤，這里就不在描述，下面可以講講
兩個單循環(huán)鏈表的合并操作
/*
假設(shè)現(xiàn)在有兩個單循環(huán)鏈表AB摇幻，將其合并的思路如下
A B分別為單循環(huán)鏈表的尾指針
q = B->next; //q指向B的頭結(jié)點
B->next = A->next; //B的指針指向A的頭結(jié)點
A->next = q->next; //A的尾指針指向B的第一個結(jié)點横侦，即B鏈接到A上
A = B; //A指向B挥萌，作為合并后鏈表的尾指針
free(q); //釋放B的頭結(jié)點
*/
LinkList ConnectList(LinkList headA,LinkList headB)
{
Node *p;
Node *tailA,*tailB;
tailA = headA->next;
tailB = headB->next;
//分別找到兩個鏈表的尾結(jié)點
while(tailA->next != headA)
tailA = tailA->next;
while(tailB->next != headB)
tailB = tailB->next;
p = tailB->next;
tailB->next = tailA->next;
tailA->next = p->next;
tailA = tailB;
free(p);
return headA;
}
雙向鏈表：
在單鏈表中，訪問任一結(jié)點丈咐，如果訪問的是后繼結(jié)點瑞眼，直接通過后繼指針就可以輕松完成此操作（O（1）），如果是訪問其前驅(qū)結(jié)點棵逊，就必須從表頭結(jié)點順鏈查找伤疙，其實時間復雜度為O（n），顯然這樣十分不方便辆影，但如果加多一個指針域呢徒像，這樣無論是前驅(qū)結(jié)點還是后繼結(jié)點訪問起來就比較容易了，這種鏈表就是雙向鏈表蛙讥。
雙向聯(lián)表的描述：
typedef struct dualnode
{
ElemType data;
struct dualnode *prior; //指向前驅(qū)結(jié)點的指針域
struct dualnode *next; //指向后繼結(jié)點的指針域
}DNode;
typedef DNode* DLinkList;
對于帶有頭結(jié)點的雙向鏈表來說逐工，其頭結(jié)點的prior域為NULL假颇，尾結(jié)點的next域為NULL杂瘸，所以如果是一個空的雙向鏈表的話粱檀，兩個指針域都為空。
雙向鏈表轉(zhuǎn)化為循環(huán)鏈表時迫像，雙向循環(huán)鏈表的頭結(jié)點的前驅(qū)指針prior指向表尾結(jié)點劈愚，尾結(jié)點的后繼指針指向頭結(jié)點，所以對于一個空的雙向循環(huán)鏈表闻妓，頭結(jié)點的兩個指針均指向自身菌羽。
雙向鏈表的基本操作：
對于一些向計算表長，獲取元素位置和獲取元素等只涉及一個方向的指針的操作由缆，與單鏈表的操作相同注祖。但是對于插入刪除操作來說比起單鏈表就有較大的差異。
//插入操作
Status ListInsert(DLinkList l,int i,ElemType e)
{
int k = 1;
DNode *p,*s;
p = l->next;
while(p->next && k<i)
{
k++;
p = p->next;
}
if(k>i || !p) //插入位置無效
return ERROR;
s = (DNode*)malloc(sizeof(DNode));//為新結(jié)點開辟空間
s->data = e;
s->prior = p->prior; //新結(jié)點的前驅(qū)指針指向p的前驅(qū)結(jié)點
p->prior->next = s; //p的前驅(qū)結(jié)點的后繼指針指向新結(jié)點
s->next = p; //新結(jié)點的后繼指針指向p
p->prior = s; //p的前驅(qū)指針指向s
return OK;
}
//刪除操作
Status DeleteList(DLinkList l,int i,ElemType *e)
{
int k = 1;
DNode *p;
p = l->next;
while(p->next && k<i)
{
p = p->next;
k++;
}
if(!p || k>i) //刪除位置無效
return ERROR;
*e = p->data;
p->prior->next = p->next; //將P的前驅(qū)結(jié)點的后繼指針指向p的后繼結(jié)點
p->next->prior = p->prior; //將p的后繼結(jié)點的前驅(qū)指針指向p的前驅(qū)結(jié)點
free(p); //釋放結(jié)點p
return OK;
}
