循環鏈表

（1）單循環鏈表——在單鏈表中，將終端結點的指針域NULL改為指向表頭結點或開始結點即可。

（2）多重鏈的循環鏈表——將表中結點鏈在多個環上。

判斷空鏈表的條件是

head==head->next;

rear==rear->next;

用尾指針rear表示的單循環鏈表對開始結點a1和終端結點an查找時間都是O(1)。而表的操作常常是在表的首尾位置上進行，因此，實用中多採用尾指針表示單循環鏈表。帶尾指針的單循環鏈表可見下圖。

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

循環鏈表的特點是無須增加存儲量，僅對錶的鏈接方式稍作改變，即可使得表處理更加方便靈活。

【例】在鏈表上實現將兩個線性表（a1，a2，…，an）和（b1，b2，…，bm）連接成一個線性表（a1，…，an，b1，…bm）的運算。

分析：若在單鏈表或頭指針表示的單循環表上做這種鏈接操作，都需要遍歷第一個鏈表，找到結點an，然後將結點b1鏈到an的後面，其執行時間是O(n)。若在尾指針表示的單循環鏈表上實現，則只需修改指針，無須遍歷，其執行時間是O(1)。

相應的演演算法如下：

LinkListConnect(LinkListA,LinkListB)

{//假設A，B為非空循環鏈表的尾指針

LinkListp=A->next;//①保存A表的頭結點位置

A->next=B->next->next;//②B表的開始結點鏈接到A表尾

free(B->next);//③釋放B表的頭結點

B->next=p;//④

returnB;//返回新循環鏈表的尾指針

}

注意：

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

②在單鏈表中，從一已知結點出發，只能訪問到該結點及其後續結點，無法找到該結點之前的其它結點。而在單循環鏈表中，從任一結點出發都可訪問到表中所有結點，這一優點使某些運算在單循環鏈表上易於實現。

void InitList(LinkList *L) {

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

if(!*L)

exit(OVERFLOW);

(*L)->next=*L;

}

void DestroyList(LinkList *L) {

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

while(p!=*L) {

q=p->next;

free(p);

p=q;

}

free(*L);

*L=NULL;

}

void ClearList(LinkList *L)

{

LinkList p,q;

*L=(*L)->next;

p=(*L)->next;

while(p!=*L)

{

q=p->next;

free(p);

p=q;

}

(*L)->next=*L;

}

Status ListEmpty(LinkList L) {

if(L->next==L)

return TRUE;

else

return FALSE;

}

int ListLength(LinkList L) {

int i=0;

LinkList p=L->next;

while(p!=L)

{

i++;

p=p->next;

}

return i;

}

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

int j=1;

LinkList p=L->next->next;

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

return ERROR;

while(j< i) {

p=p->next;

j++;

}

*e=p->data; return OK;

}

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

int i=0;

LinkList p=L->next->next; while(p!=L->next) {

i++;

if(compare(p->data,e))

return i;

p=p->next;

}

return 0;

}

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

LinkList q,p=L->next->next; q=p->next;

while(q!=L->next) {

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) {

LinkList p=L->next->next; while(p!=L) {

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) {

LinkList p=(*L)->next,s; int j=0;

if(i<=0||i>ListLength(*L)+1)

return ERROR;

while(j< i-1) {

p=p->next;

j++;

}

s=(LinkList)malloc(sizeof(struct LNode)); s->data=e; s->next=p->next;

p->next=s;

if(p==*L)

*L=s;

return OK;

}

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

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

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

return ERROR;

while(j< i-1) {

p=p->next;

j++;

}

q=p->next; p->next=q->next;

*e=q->data;

if(*L==q)

*L=p;

free(q); return OK;

}

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

LinkList p=L->next->next; while(p!=L->next) {

vi(p->data);

p=p->next;

}

printf("\n");

}