1.概述：
對于一個循環鏈表來說,其首節點和末節點被連接在一起。這種方式在單向和雙向鏈表中皆可實現。要轉換一個循環鏈表，可以選擇開始于任意一個節點然后沿著列表的任一方向直到返回開始的節點。再來看另一種方法，循環鏈表可以被視為“無頭無尾”。這種列表很利于節約數據存儲緩存， 假定你在一個列表中有一個對象并且希望所有其他對象迭代在一個非特殊的排列下。
指向整個列表的指針可以被稱作訪問指針。
用單向鏈表構建的循環鏈表
循環鏈表中第一個節點之前就是最后一個節點，反之亦然。循環鏈表的無邊界使得在這樣的鏈表上設計算法會比普通鏈表更加容易。對于新加入的節點應該是在第一個節點之前還是最后一個節點之后可以根據實際要求靈活處理，區別不大(詳見下面實例代碼)。當然，如果只會在最后插入數據（或者只會在之前），處理也是很容易的。
另外有一種模擬的循環鏈表，就是在訪問到最后一個節點之后的時候，手工的跳轉到第一個節點。訪問到第一個節點之前的時候也一樣。這樣也可以實現循環鏈表的功能，在直接用循環鏈表比較麻煩或者可能會出現問題的時候可以用。
2.程序實現：
|
1
2
3
4
5
6
7
|
/* c2-2.h 線性表的單鏈表存儲結構 */ struct LNode { ElemType data; struct LNode *next; }; typedef struct LNode *LinkList; /* 另一種定義LinkList的方法 */ |
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
|
/* bo2-4.c 設立尾指針的單循環鏈表(存儲結構由c2-2.h定義)的12個基本操作 */ Status InitList_CL(LinkList *L) { /* 操作結果：構造一個空的線性表L */ *L=(LinkList)malloc(sizeof(struct LNode)); /* 產生頭結點,并使L指向此頭結點 */ if(!*L) /* 存儲分配失敗 */ exit(OVERFLOW); (*L)->next=*L; /* 指針域指向頭結點 */ return OK; } Status DestroyList_CL(LinkList *L) { /* 操作結果：銷毀線性表L */ LinkList q,p=(*L)->next; /* p指向頭結點 */ while(p!=*L) /* 沒到表尾 */ { q=p->next; free(p); p=q; } free(*L); *L=NULL; return OK; } Status ClearList_CL(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; /* 頭結點指針域指向自身 */ return OK; } Status ListEmpty_CL(LinkList L) { /* 初始條件：線性表L已存在。操作結果：若L為空表，則返回TRUE，否則返回FALSE */ if(L->next==L) /* 空 */ return TRUE; else return FALSE; } int ListLength_CL(LinkList L) { /* 初始條件：L已存在。操作結果：返回L中數據元素個數 */ int i=0; LinkList p=L->next; /* p指向頭結點 */ while(p!=L) /* 沒到表尾 */ { i++; p=p->next; } return i; } Status GetElem_CL(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_CL(L)) /* 第i個元素不存在 */ return ERROR; while(j<i) { /* 順指針向后查找,直到p指向第i個元素 */ p=p->next; j++; } *e=p->data; /* 取第i個元素 */ return OK; } int LocateElem_CL(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_CL(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_CL(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_CL(LinkList *L,int i,ElemType e) /* 改變L */ { /* 在L的第i個位置之前插入元素e */ LinkList p=(*L)->next,s; /* p指向頭結點 */ int j=0; if(i<=0||i>ListLength_CL(*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_CL(LinkList *L,int i,ElemType *e) /* 改變L */ { /* 刪除L的第i個元素,并由e返回其值 */ LinkList p=(*L)->next,q; /* p指向頭結點 */ int j=0; if(i<=0||i>ListLength_CL(*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; } Status ListTraverse_CL(LinkList L,void(*vi)(ElemType)) { /* 初始條件:L已存在。操作結果:依次對L的每個數據元素調用函數vi()。一旦vi()失敗,則操作失敗 */ LinkList p=L->next->next; while(p!=L->next) { vi(p->data); p=p->next; } printf("\n"); return OK; } |
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
/* main2-4.c 單循環鏈表,檢驗bo2-4.c的主程序 */ #include"c1.h" typedef int ElemType; #include"c2-2.h" #include"bo2-4.c" Status compare(ElemType c1,ElemType c2) { if(c1==c2) return TRUE; else return FALSE; } void visit(ElemType c) { printf("%d ",c); } void main() { LinkList L; ElemType e; int j; Status i; i=InitList_CL(&L); /* 初始化單循環鏈表L */ printf("初始化單循環鏈表L i=%d (1:初始化成功)\n",i); i=ListEmpty_CL(L); printf("L是否空 i=%d(1:空 0:否)\n",i); ListInsert_CL(&L,1,3); /* 在L中依次插入3,5 */ ListInsert_CL(&L,2,5); i=GetElem_CL(L,1,&e); j=ListLength_CL(L); printf("L中數據元素個數=%d,第1個元素的值為%d。\n",j,e); printf("L中的數據元素依次為："); ListTraverse_CL(L,visit); PriorElem_CL(L,5,&e); /* 求元素5的前驅 */ printf("5前面的元素的值為%d。\n",e); NextElem_CL(L,3,&e); /* 求元素3的后繼 */ printf("3后面的元素的值為%d。\n",e); printf("L是否空 %d(1:空 0:否)\n",ListEmpty_CL(L)); j=LocateElem_CL(L,5,compare); if(j) printf("L的第%d個元素為5。\n",j); else printf("不存在值為5的元素\n"); i=ListDelete_CL(&L,2,&e); printf("刪除L的第2個元素：\n"); if(i) { printf("刪除的元素值為%d,現在L中的數據元素依次為：",e); ListTraverse_CL(L,visit); } else printf("刪除不成功！\n"); printf("清空L：%d(1: 成功)\n",ClearList_CL(&L)); printf("清空L后，L是否空：%d(1:空 0:否)\n",ListEmpty_CL(L)); printf("銷毀L：%d(1: 成功)\n",DestroyList_CL(&L)); } |
