循環鍊表

循環鍊表

循環鍊表是另一種形式的鏈式存貯結構。它的特點是表中最後一個結點的指針域指向頭結點,整個鍊表形成一個環。

分類

循環鍊表 循環鍊表

(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是否為空,而是判別它們是否等於某一指定指針,如頭指針或尾指針等。

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

/* 設立尾指針的單循環鍊表的12個基本操作 */

void InitList(LinkList *L) {

/* 操作結果:構造一個空的線性表L */

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

/* 產生頭結點,並使L指向此頭結點 */

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

exit(OVERFLOW);

(*L)->next=*L;

/* 指針域指向頭結點 */

}

void DestroyList(LinkList *L) {

/* 操作結果:銷毀線性表L */

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

/* p指向頭結點 */

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

q=p->next;

free(p);

p=q;

}

free(*L);

*L=NULL;

}

void ClearList(LinkList *L)

/* 改變L */

{

/* 初始條件:線性表L已存在。操作結果:將L重置為空表 */

LinkList p,q;

*L=(*L)->next;

/* L指向頭結點 */

p=(*L)->next;

/* p指向第一個結點 */

while(p!=*L)

/* 沒到表尾 */

{

q=p->next;

free(p);

p=q;

}

(*L)->next=*L;

/* 頭結點指針域指向自身 */

}

Status ListEmpty(LinkList L) {

/* 初始條件:線性表L已存在。操作結果:若L為空表,則返回TRUE,否則返回FALSE */

if(L->next==L)

/* 空 */

return TRUE;

else

return FALSE;

}

int ListLength(LinkList L) {

/* 初始條件:L已存在。操作結果:返回L中數據元素個數 */

int i=0;

LinkList p=L->next;

/* p指向頭結點 */

while(p!=L)

/* 沒到表尾 */

{

i++;

p=p->next;

}

return i;

}

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

/* 當第i個元素存在時,其值賦給e並返回OK,否則返回ERROR */

int j=1;

/* 初始化,j為計數器 */

LinkList p=L->next->next;

/* p指向第一個結點 */

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

/* 第i個元素不存在 */

return ERROR;

while(j< i) {

/* 順指針向後查找,直到p指向第i個元素 */

p=p->next;

j++;

}

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

}

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

/* 初始條件:線性表L已存在,compare()是數據元素判定函式 */ /* 操作結果:返回L中第1個與e滿足關係compare()的數據元素的位序。*/ /* 若這樣的數據元素不存在,則返回值為0 */ int i=0;

LinkList p=L->next->next; /* p指向第一個結點 */ 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) {

/* 初始條件:線性表L已存在 */ /* 操作結果:若cur_e是L的數據元素,且不是第一個,則用pre_e返回它的前驅,*/ /* 否則操作失敗,pre_e無定義 */ LinkList q,p=L->next->next; /* p指向第一個結點 */ q=p->next;

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

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已存在 */ /* 操作結果:若cur_e是L的數據元素,且不是最後一個,則用next_e返回它的後繼,*/ /* 否則操作失敗,next_e無定義 */ LinkList p=L->next->next; /* p指向第一個結點 */ while(p!=L) { /* p沒到表尾 */

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個位置之前插入元素e */ LinkList p=(*L)->next,s; /* p指向頭結點 */ int j=0;

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

return ERROR;

while(j< i-1) { /* 尋找第i-1個結點 */

p=p->next;

j++;

}

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

p->next=s;

if(p==*L) /* 改變尾結點 */

*L=s;

return OK;

}

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

/* 刪除L的第i個元素,並由e返回其值 */ LinkList p=(*L)->next,q; /* p指向頭結點 */ int j=0;

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

return ERROR;

while(j< i-1) { /* 尋找第i-1個結點 */

p=p->next;

j++;

}

q=p->next; /* q指向待刪除結點 */ p->next=q->next;

*e=q->data;

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

*L=p;

free(q); /* 釋放待刪除結點 */ return OK;

}

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

/* 初始條件:L已存在。操作結果:依次對L的每個數據元素調用函式vi() */ LinkList p=L->next->next; /* p指向首元結點 */ while(p!=L->next) { /* p不指向頭結點 */

vi(p->data);

p=p->next;

}

printf("\n");

}

相關詞條

相關搜尋

熱門詞條

聯絡我們