1 #include<stdio.h>
2 #include<stdlib.h>
3
4 typedef struct Node{
5 int data;
6 struct Node* next;
7 }Node,*LinkList;
8
9 void InitialList(LinkList *L){
10 *L = (LinkList)malloc(sizeof(struct Node));
11 if(!(*L)){
12 printf("malloc failed!\n");
13 exit(1);
14 }
15 (*L)->next = (*L);
16 }
17 void ClearList(LinkList *L){
18 LinkList q,p = (*L)->next;
19 while(p != *L){
20 q = p->next;
21 free(p);
22 p = q;
23 }
24 (*L)->next = *L;
25 }
26 void DestroyList(LinkList *L){
27 LinkList q,p = *L;
28 while(p->next != *L){
29 q = p->next;
30 free(p);
31 p = q;
32 }
33 free(*L);
34 *L = NULL;
35 }
36 int IsEmpty(LinkList L){
37 if(L->next == L)return 1;
38 else return 0;
39 }
40 int Length_SCL(LinkList L){
41 int length = 0;
42 LinkList cursor = L;
43 while(cursor->next != L){
44 length++;
45 cursor = cursor->next;
46 }
47 return length;
48 }
49 void GetElement_SCL(LinkList L,int position){
50 int length = Length_SCL(L);
51 if(position < 1 || position > length){
52 printf("Error:getElemet:position error!\n");
53 }
54 else{
55 int count = 0;
56 while(count < position){
57 L = L->next;
58 count += 1;
59 }
60 printf("getElement in position %d is: %d\n",position,L->data);
61 }
62 }
63 int ElementLocate_SCL(LinkList L,int value){
64 //根據給定的值返回下表，返回0則表示當前表中沒有該元素
65 int index = 1;
66 LinkList p = L->next;
67 while(p != L){
68 if(p->data == value){
69 return index;
70 }
71 p = p->next;
72 index += 1;
73 }
74 return 0;
75 }
76 void PriorElement_SCL(LinkList L,int current_element){
77 if(!ElementLocate_SCL(L,current_element))
78 printf("%d is not belong to this List!\n",current_element);
79 else{
80 if(ElementLocate_SCL(L,current_element) == 1){
81 LinkList p = L;
82 while(p->next != L)
83 p = p->next;
84 printf("PriorElement:before %d is %d\n",current_element,p->data);
85 }
86 else{
87 LinkList p = L->next;
88 LinkList q = L;
89 while(p!=L){
90 if(p->data == current_element){
91 printf("PriorElement:before %d is %d\n",current_element,q->data);
92 break;
93 }
94 q = p;
95 p = p->next;
96 }
97 }
98 }
99 }
100 void NextElement_SCL(LinkList L,int current_element){
101 if(!ElementLocate_SCL(L,current_element))
102 printf("%d is not belong to this list!\n");
103 else{
104 if(ElementLocate_SCL(L,current_element) == Length_SCL(L))
105 printf("NextElement:next %d is %d\n",current_element,L->next->data);
106 else{
107 LinkList p = L;
108 LinkList q = L->next;
109 while(q != L){
110 if(p->data == current_element){
111 printf("NextElement:next %d is %d\n",current_element,q->data);
112 break;
113 }
114 p = q;
115 q = q->next;
116 }
117 }
118 }
119 }
120 void InsertList_SCL(LinkList *L,int position,int value){
121 int length = Length_SCL(*L);
122 if(position < 1 || position > length + 1){
123 printf("Error:insertList:position\n");
124 }
125 else{
126 LinkList s = (LinkList)malloc(sizeof(struct Node));
127 s->data = value;
128 int count = 0;
129 LinkList p = *L;
130 while(count < position-1){
131 p = p->next;
132 count++;
133 }
134 s->next = p->next;
135 p->next = s;
136 printf("inserted %d before index %d\n",value,position);
137 }
138 }
139 void DeleteList_SCL(LinkList *L,int position){
140 int length = Length_SCL(*L);
141 if(position < 1 || position > length){
142 printf("Error:deleteList:position!\n");
143 }
144 else{
145 int count = 0,value;
146 LinkList p = *L;
147 while(count < position - 1){
148 p = p->next;
149 count++;
150 }
151 value = p->next->data;
152 LinkList temp = p->next;
153 p->next = p->next->next;
154 free(temp);
155 printf("deleted %d position is %d\n",value,position);
156 }
157 }
158 void TailCreate_SCL(LinkList *L,int count){
159 LinkList tail = *L,s;
160 int i = 0;
161 for(i = 0;i < count; i++){
162 printf("please enter %d element: ",i+1);
163 s = (LinkList)malloc(sizeof(struct Node));
164 scanf("%d",&(s->data));
165 s->next = tail->next;
166 tail->next = s;
167 tail = s;
168 }
169 }
170 void Display_SCL(LinkList L){
171 printf("------display executed!----------\n");
172 int length = Length_SCL(L);
173 L = L->next;
174 int i;
175 for(i = 1; i <= length; i++){
176 printf("%d ",L->data);
177 L = L->next;
178 }
179 printf("\n");
180 }
181 /*會死循環輸出1,2,3,未定義的數(頭結點的data),說明本文件中的
182 * 循環鏈表尾節點的next指向的是頭結點，而不是第一個節點。
183 * 為了檢測在做了操作之後，是否是保留了"環"的性質
184 * */
185 void Display_SCL_1(LinkList L){
186 while(L->next != NULL){
187 printf("%d ",L->data);
188 L = L->next;
189 }
190 }
191 int main(){
192 LinkList L;
193 InitialList(&L);
194 TailCreate_SCL(&L,3);
195 Display_SCL(L);
196 //DestroyList(&L);
197 ClearList(&L);
198 if(IsEmpty(L))
199 printf("List is Empty!\n");
200 else
201 printf("there is element in List\n");
202 int r1 = Length_SCL(L);
203 printf("the length of list is %d\n",r1);
204 Display_SCL(L);
205 TailCreate_SCL(&L,5);
206 GetElement_SCL(L,4);
207 GetElement_SCL(L,6);
208 GetElement_SCL(L,1);
209 GetElement_SCL(L,5);
210
211 if(ElementLocate_SCL(L,1))
212 printf("the position of 1 is %d\n",ElementLocate_SCL(L,1));
213 else
214 printf("there is no this element is this list!\n");
215 if(ElementLocate_SCL(L,8))
216 printf("the position of 8 is %d\n",ElementLocate_SCL(L,8));
217 else
218 printf("there is no this element is this list!\n");
219 if(ElementLocate_SCL(L,9))
220 printf("the position of 9 is %d\n",ElementLocate_SCL(L,9));
221 else
222 printf("there is no this element is this list!\n");
223 if(ElementLocate_SCL(L,5))
224 printf("the position of 5 is %d\n",ElementLocate_SCL(L,5));
225 else
226 printf("there is no this element is this list!\n");
227
228 //test PriorElement
229 printf("\n++++++++test priorElement++++++\n");
230 PriorElement_SCL(L,1);
231 PriorElement_SCL(L,2);
232 PriorElement_SCL(L,6);
233 PriorElement_SCL(L,9);
234 PriorElement_SCL(L,5);
235 //test NextElement
236 printf("\n++++++++test nextElement+++++++\n");
237 NextElement_SCL(L,5);
238 NextElement_SCL(L,1);
239 NextElement_SCL(L,2);
240 NextElement_SCL(L,17);
241 printf("\n++++++++test InsertList++++++++\n");
242 InsertList_SCL(&L,2,888);
243 Display_SCL(L);
244 InsertList_SCL(&L,1,666);
245 Display_SCL(L);
246 InsertList_SCL(&L,8,999);
247 Display_SCL(L);
248 InsertList_SCL(&L,10,1111);
249 Display_SCL(L);
250 //Display_SCL_1(L);
251 printf("\n++++++++test DeleteList+++++++++\n");
252 DeleteList_SCL(&L,5);
253 Display_SCL(L);
254 DeleteList_SCL(&L,8);
255 Display_SCL(L);
256 DeleteList_SCL(&L,1);
257 Display_SCL(L);
258 //Display_SCL_1(L);
259 return 0;
260 }
