循環(huán)鏈表特點(diǎn)

循環(huán)鏈表的特點(diǎn)是無(wú)須增加存儲(chǔ)量，僅對(duì)表的鏈接方式稍作改變，即可使得表處理更加方便靈活。

【例】在鏈表上實(shí)現(xiàn)將兩個(gè)線性表（a1，a2，…，an）和（b1，b2，…，bm）連接成一個(gè)線性表（a1，…，an，b1，…bm）的運(yùn)算。

分析：若在單鏈表或頭指針表示的單循環(huán)表上做這種鏈接操作，都需要遍歷第一個(gè)鏈表，找到結(jié)點(diǎn)an，然后將結(jié)點(diǎn)b1鏈到an的后面，其執(zhí)行時(shí)間是O(n)。若在尾指針表示的單循環(huán)鏈表上實(shí)現(xiàn)，則只需修改指針，無(wú)須遍歷，其執(zhí)行時(shí)間是O(1)。

相應(yīng)的算法如下：

LinkListConnect(LinkListA,LinkListB)

{//假設(shè)A，B為非空循環(huán)鏈表的尾指針

LinkListp=A->next;//①保存A表的頭結(jié)點(diǎn)位置

A->next=B->next->next;//②B表的開(kāi)始結(jié)點(diǎn)鏈接到A表尾

free(B->next);//③釋放B表的頭結(jié)點(diǎn)

B->next=p;//④

returnB;//返回新循環(huán)鏈表的尾指針

}

注意：

①循環(huán)鏈表中沒(méi)有NULL指針。涉及遍歷操作時(shí)，其終止條件就不再是像非循環(huán)鏈表那樣判別p或p->next是否為空，而是判別它們是否等于某一指定指針，如頭指針或尾指針等。

②在單鏈表中，從一已知結(jié)點(diǎn)出發(fā)，只能訪問(wèn)到該結(jié)點(diǎn)及其后續(xù)結(jié)點(diǎn)，無(wú)法找到該結(jié)點(diǎn)之前的其它結(jié)點(diǎn)。而在單循環(huán)鏈表中，從任一結(jié)點(diǎn)出發(fā)都可訪問(wèn)到表中所有結(jié)點(diǎn)，這一優(yōu)點(diǎn)使某些運(yùn)算在單循環(huán)鏈表上易于實(shí)現(xiàn)。

/* 設(shè)立尾指針的單循環(huán)鏈表的12個(gè)基本操作 */

void InitList(LinkList *L) {

/* 操作結(jié)果：構(gòu)造一個(gè)空的線性表L */

*L=(LinkList)malloc(sizeof(struct LNode));

/* 產(chǎn)生頭結(jié)點(diǎn)，并使L指向此頭結(jié)點(diǎn) */

if(!*L) /* 存儲(chǔ)分配失敗 */

exit(OVERFLOW);

(*L)->next=*L;

/* 指針域指向頭結(jié)點(diǎn) */

}

void DestroyList(LinkList *L) {

/* 操作結(jié)果：銷毀線性表L */

LinkList q,p=(*L)->next;

/* p指向頭結(jié)點(diǎn) */

while(p!=*L) { /* 沒(méi)到表尾 */

q=p->next;

free(p);

p=q;

}

free(*L);

*L=NULL;

}

void ClearList(LinkList *L)

/* 改變L */

{

/* 初始條件：線性表L已存在。操作結(jié)果：將L重置為空表 */

LinkList p,q;

*L=(*L)->next;

/* L指向頭結(jié)點(diǎn) */

p=(*L)->next;

/* p指向第一個(gè)結(jié)點(diǎn) */

while(p!=*L)

/* 沒(méi)到表尾 */

{

q=p->next;

free(p);

p=q;

}

(*L)->next=*L;

/* 頭結(jié)點(diǎn)指針域指向自身 */

}

Status ListEmpty(LinkList L) {

/* 初始條件：線性表L已存在。操作結(jié)果：若L為空表，則返回TRUE，否則返回FALSE */

if(L->next==L)

/* 空 */

return TRUE;

else

return FALSE;

}

int ListLength(LinkList L) {

/* 初始條件：L已存在。操作結(jié)果：返回L中數(shù)據(jù)元素個(gè)數(shù) */

int i=0;

LinkList p=L->next;

/* p指向頭結(jié)點(diǎn) */

while(p!=L)

/* 沒(méi)到表尾 */

{

i ;

p=p->next;

}

return i;

}

Status GetElem(LinkList L,int i,ElemType *e) {

/* 當(dāng)?shù)趇個(gè)元素存在時(shí)，其值賦給e并返回OK，否則返回ERROR */

int j=1;

/* 初始化，j為計(jì)數(shù)器 */

LinkList p=L->next->next;

/* p指向第一個(gè)結(jié)點(diǎn) */

if(i<=0||i>ListLength(L))

/* 第i個(gè)元素不存在 */

return ERROR;

while(j< i) {

/* 順指針向后查找，直到p指向第i個(gè)元素 */

p=p->next;

j ;

}

*e=p->data; /* 取第i個(gè)元素 */ return OK;

}

int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType)) {

/* 初始條件：線性表L已存在，compare()是數(shù)據(jù)元素判定函數(shù) */ /* 操作結(jié)果：返回L中第1個(gè)與e滿足關(guān)系compare()的數(shù)據(jù)元素的位序。*/ /* 若這樣的數(shù)據(jù)元素不存在，則返回值為0 */ int i=0;

LinkList p=L->next->next; /* p指向第一個(gè)結(jié)點(diǎn) */ while(p!=L->next) {

i ;

if(compare(p->data,e)) /* 滿足關(guān)系 */

return i;

p=p->next;

}

return 0;

}

Status PriorElem(LinkList L,ElemType cur_e,ElemType *pre_e) {

/* 初始條件：線性表L已存在 */ /* 操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是第一個(gè)，則用pre_e返回它的前驅(qū)，*/ /* 否則操作失敗，pre_e無(wú)定義 */ LinkList q,p=L->next->next; /* p指向第一個(gè)結(jié)點(diǎn) */ q=p->next;

while(q!=L->next) { /* p沒(méi)到表尾 */

if(q->data==cur_e) {

*pre_e=p->data;

return TRUE;

}

p=q;

q=q->next;

}

return FALSE; /* 操作失敗 */

}

Status NextElem(LinkList L,ElemType cur_e,ElemType *next_e) {

/* 初始條件：線性表L已存在 */ /* 操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是最后一個(gè)，則用next_e返回它的后繼，*/ /* 否則操作失敗，next_e無(wú)定義 */ LinkList p=L->next->next; /* p指向第一個(gè)結(jié)點(diǎn) */ while(p!=L) { /* p沒(méi)到表尾 */

if(p->data==cur_e) {

*next_e=p->next->data;

return TRUE;

}

p=p->next;

}

return FALSE; /* 操作失敗 */

}

Status ListInsert(LinkList *L,int i,ElemType e) { /* 改變L */

/* 在L的第i個(gè)位置之前插入元素e */ LinkList p=(*L)->next,s; /* p指向頭結(jié)點(diǎn) */ int j=0;

if(i<=0||i>ListLength(*L) 1) /* 無(wú)法在第i個(gè)元素之前插入 */

return ERROR;

while(j< i-1) { /* 尋找第i-1個(gè)結(jié)點(diǎn) */

p=p->next;

j ;

}

s=(LinkList)malloc(sizeof(struct LNode)); /* 生成新結(jié)點(diǎn) */ s->data=e; /* 插入L中 */ s->next=p->next;

p->next=s;

if(p==*L) /* 改變尾結(jié)點(diǎn) */

*L=s;

return OK;

}

Status ListDelete(LinkList *L,int i,ElemType *e) { /* 改變L */

/* 刪除L的第i個(gè)元素，并由e返回其值 */ LinkList p=(*L)->next,q; /* p指向頭結(jié)點(diǎn) */ int j=0;

if(i<=0||i>ListLength(*L)) /* 第i個(gè)元素不存在 */

return ERROR;

while(j< i-1) { /* 尋找第i-1個(gè)結(jié)點(diǎn) */

p=p->next;

j ;

}

q=p->next; /* q指向待刪除結(jié)點(diǎn) */ p->next=q->next;

*e=q->data;

if(*L==q) /* 刪除的是表尾元素 */

*L=p;

free(q); /* 釋放待刪除結(jié)點(diǎn) */ return OK;

}

void ListTraverse(LinkList L,void(*vi)(ElemType)) {

/* 初始條件：L已存在。操作結(jié)果：依次對(duì)L的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)vi() */ LinkList p=L->next->next; /* p指向首元結(jié)點(diǎn) */ while(p!=L->next) { /* p不指向頭結(jié)點(diǎn) */

vi(p->data);

p=p->next;

}

printf(" ");

}

用尾指針rear表示的單循環(huán)鏈表對(duì)開(kāi)始結(jié)點(diǎn)a1和終端結(jié)點(diǎn)an查找時(shí)間都是O(1)。而表的操作常常是在表的首尾位置上進(jìn)行，因此，實(shí)用中多采用尾指針表示單循環(huán)鏈表。帶尾指針的單循環(huán)鏈表。

注意：判斷空鏈表的條件為rear==rear->next;

判斷空鏈表的條件是

head==head->next;

rear==rear->next;

（1）單循環(huán)鏈表——在單鏈表中，將終端結(jié)點(diǎn)的指針域NULL改為指向表頭結(jié)點(diǎn)或開(kāi)始結(jié)點(diǎn)即可。

（2）多重鏈的循環(huán)鏈表——將表中結(jié)點(diǎn)鏈在多個(gè)環(huán)上 。