单向循环链表释放等函数&约瑟夫问题：单向循环链表实现
头文件：
1 #ifndef __LOOPLINK_H__
2 #define __LOOPLINK_H__
3 #include<stdio.h>
4 #include<stdlib.h>
5
6 typedef int datatype;
7 typedef struct node
8 {
9 union
10 {
11 datatype data;
12 int len;
13 };
14 struct node * next;
15 }node , * looplink;
16 //create a new looplink
17 looplink create_looplink();
18
19 //judge size
20 int judge_looplink(looplink h);
21
22 //data package assemble into node
23 looplink create_node(datatype x);
24
25 //insert after head
26 int insert_after_head(looplink h , datatype x);
27
28 //show all
29 void show_all_node(looplink h);
30
31 //delete tail node
32 int delete_tail(looplink h);
33
34 //insert to tail
35 int insert_tail(looplink h , datatype x);
36
37 //delete head
38 looplink kill_head(looplink h);
39
40 //show all after delete head
41 void show_all_after_headkilled(looplink p1st);
42
43 //free looplink
44 int free_looplink(looplink p);
45
46 //delete one node return next node address
47 looplink delete_current_node(looplink p_cur);
48
49 #endif
~ 函数文件
1 #include"looplink.h"
2
3 looplink create_looplink()
4 {
5 looplink p = (looplink)malloc(sizeof( node ) );
6 if(NULL == p)
7 {
8 puts("create looplink failed at malloc");
9 return NULL;
10 }
11 p->len = 0;
12 p->next = p;
13 puts("create looplink succeed");
14 return p;
15 }
16 //-----------------judge size 0 means only head 1 means at least one body node
17 int judge_looplink(looplink h)
18 {
19 if(NULL == h)
20 {
21 puts("judge failed at looplink");
22 return -1;
23 }
24 return h->next == h ? 0:1;
25 }
26 //----------------assemble data into node
27 looplink create_node(datatype x)
28 {
29 looplink p = (looplink)malloc(sizeof(node) );
30 if(NULL == p)
31 {
32 puts("create node failed at apply space");
33 return NULL;
34 }
35 p->data = x;
36 p->next = NULL;
37 return p;
38 }
39
40 //---------------------insert after head
41 int insert_after_head(looplink h , datatype x )
42 {
43 if(NULL == h)
44 {
45 puts("insert after head failed at looplink");
46 return -1;
47 }
48 looplink p = create_node(x);
49
50 p->next = h->next;
51 h->next = p;
52 h->len++;
53 puts("insert after head succeed");
54 return 0;
55 }
56
57 //--------------------show all
58 void show_all_node(looplink h)
59 {
60 if(NULL == h || !judge_looplink(h))
61 {
62 puts("show all node failed at looplink");
63 return;
64 }
65 looplink p = h->next;
66 while(p != h)
67 {
68 printf("%d\t",p->data);
69 p = p->next;
70 }
71 puts("\nshow all succeed");
72 return;
73 }
74
75 //------------------delete tail node
76 int delete_tail(looplink h)
77 {
78 if(NULL == h || !judge_looplink(h))
79 {
80 puts("delete tail failed at looplink");
81 return -1;
82 }
83 looplink p = h;
84 while(p->next->next != h)
85 {
86 p=p->next;
87 }
88 looplink q = p->next;
89 p->next = p->next->next;
90 free(q);
91 q = NULL;
92 h->len--;
93 puts("delete tail succeed");
94 return 0;
95 }
96 //------------------insert to tail
97 int insert_tail(looplink h , datatype x)
98 {
99 if(NULL == h)
100 {
101 puts("insert to tail failed at looplink");
102 return -1;
103 }
104 looplink p = create_node(x);
105 looplink q = h;
106 while(1)
107 {
108 if(q->next == h)
109 {
110 break;
111 }
112 q = q->next;
113 }
114 q->next = p;
115 p->next = h;
116 h->len++;
117 puts("insert to tail succeed");
118 return 0;
119 }
120 //------------------delete head return first body node address
121 looplink kill_head(looplink h)
122 {
123 if(NULL == h)
124 {
125 puts("kill head failed at looplink");
126 }
127 looplink p = h;
128 while(p->next != h)
129 {
130 p = p->next;
131 }
132 p->next = h->next;
133 free(h);
134 h = NULL;
135 puts("kill head succeed");
136 return p->next;
137 }
138
139 //--------------------show all after delete head
140 void show_all_after_headkilled(looplink p1st)
141 {
142 if(NULL == p1st)
143 {
144 puts("show all after kill head failed at p1st");
145 return;
146 }
147 looplink q = p1st;
148 while(1)
149 {
150 printf("%d\t", q->data);
151 q = q->next;
152 if(q == p1st)
153 break;
154 }
155 puts("\nshow all after kill head succeed");
156 return;
157 }
158 //------------------------free looplink
159 int free_looplink(looplink pf)
160 {
161 if(NULL == pf)
162 {
163 puts("looplink not exist");
164 return -1;
165 }
166 looplink pt = pf;
167 do
168 {
169 pt = pt->next;
170 }while(pt->next != pf);
171 pt->next = NULL; //cut the loop at tail add null to tail node
172 looplink p = pf;
173 while(p != NULL)
174 {
175 looplink q = p;
176 p = p->next;
177 free(q);
178 }
179 pt = NULL;
180 p = NULL;
181 pf = NULL;
182 puts("free whole looplink succeed");
183 return 0;
184 }
185 //---------------------delete current node return next node address
186 looplink delete_current_node(looplink p_cur)
187 {
188 if(NULL == p_cur)
189 {
190 puts("delete current node failed at looplink");
191 return NULL;
192 }
193 if(p_cur->next == p_cur) //single node return NULL
194 {
195 free(p_cur);
196 p_cur = NULL;
197 return NULL;
198 }
199 looplink p_prio = p_cur;
200 while(p_prio->next != p_cur)
201 {
202 p_prio = p_prio->next;
203 }
204 p_prio->next = p_cur->next;
205
206 free(p_cur);
207 p_cur = NULL;
208 return p_prio->next;
209 }
210
211
212
213
214
215
216
~
~
~ 主函数实现
1 #include"looplink.h"
2 int main()
3 {
4 looplink h = create_looplink(); //1 looplink to revolve and delete
5 if(NULL == h)
6 {
7 return -1;
8 }
9 insert_after_head(h , 8);
10 insert_after_head(h , 7);
11 insert_after_head(h , 6);
12 insert_after_head(h , 5);
13 insert_after_head(h , 4);
14 insert_after_head(h , 3);
15 insert_after_head(h , 2);
16 insert_after_head(h , 1);
17
18 looplink p1st = kill_head(h);
19 show_all_after_headkilled(p1st);
20
21 looplink h2 = create_looplink(); //2 looplink to receive
22 if(NULL == h2)
23 {
24 return -1;
25 }
26 insert_after_head(h2 , 8);
27 insert_after_head(h2 , 7);
28 insert_after_head(h2 , 6);
29 insert_after_head(h2 , 5);
30 insert_after_head(h2 , 4);
31 insert_after_head(h2 , 3);
32 insert_after_head(h2 , 2);
33 insert_after_head(h2 , 1);
34
35 looplink q1st = kill_head(h2);
36 show_all_after_headkilled(q1st);
37
38 looplink q = q1st;
39 while(p1st != NULL)
40 {
41 for(int i = 1;i < 4;i++ )
42 {
43 p1st = p1st->next;
44 }
45 q->data = p1st->data;
46 q = q->next;
47 p1st = delete_current_node(p1st);
48 }
49
50 show_all_after_headkilled(q1st); //show the answer
51 return 0;
52 }
53
54
更多推荐
2022-9-16 task
发布评论