1 /****************************************************/ 3 File name：no_head_link.c4 Author：SimonKly Version:0.1 Date: 2017.5.205 Description：不帶頭節(jié)點的單鏈表6 Funcion List: 7 *****************************************************/8 9 #include <stdio.h>10 #include <stdlib.h>11 12 typedef struct node13 {14 int id;15 struct node * next;16 }* Link, Node;17 18 /*創(chuàng)建鏈表*/19 void create_link(Link * head)20 {21 *head = NULL;//空鏈表22 }23 24 /*頭插*/25 void insert_node_head(Link * head, Link new_node)26 {27 new_node->next = *head;28 *head = new_node;29 }30 31 #if 132 /*尾插*/33 void insert_node_tail(Link * head, Link new_node)34 {35 Link p = NULL;36 37 if (*head == NULL)38 {39 *head =new_node;40 new_node->next = NULL;41 return ;42 }43 else44 {45 p = *head;46 while (p->next != NULL)47 {48 p = p->next;49 }50 p->next = new_node;51 new_node->next = NULL;52 }53 }54 #endif55 56 /*輸出鏈表*/57 void display_link(Link head)58 {59 Link p = NULL;60 61 p = head;62 63 if(p == NULL)64 {65 printf("link is empty!\n");66 return ;67 }68 69 while (p != NULL)70 {71 printf("id = %d\n", p->id);72 p = p->next;73 }74 75 putchar(10);76 }77 78 /*檢查malloc是否分配成功*/79 void is_malloc_ok(Link new_node)80 {81 if (new_node == NULL)82 {83 printf("malloc error!\n");84 exit(-1);85 }86 }87 88 /*創(chuàng)建節(jié)點*/89 void create_node(Link * new_node)90 {91 *new_node = (Link)malloc(sizeof(Node));92 93 is_malloc_ok(*new_node);94 }95 96 /*釋放節(jié)點*/97 void realse_node(Link * head)98 {99 Link p = NULL; 100 101 p = *head; 102 while (*head != NULL) 103 { 104 *head = (*head)->next;//head移動 105 free(p);//釋放head之前的節(jié)點 106 p = *head; 107 } 108 } 109 110 111 /*中間插入節(jié)點*/ 112 void insert_node_mid(Link * head, Link new_node, int loc) 113 { 114 int i; 115 Link p = NULL; 116 117 p = *head; 118 119 for(i = 1; i < loc; i++) 120 { 121 p = p->next; 122 } 123 124 new_node->next = p->next; 125 p->next = new_node; 126 } 127 128 /*中間插入，前面*/ 129 void insert_node_mid_front(Link * head, Link new_node) 130 { 131 Link p = NULL, q = NULL; 132 133 p = q = *head; 134 135 if (*head == NULL) 136 { 137 printf("link is empty\n"); 138 return ; 139 } 140 141 while (p != NULL && p->id != new_node->id) 142 { 143 q = p; 144 p = p->next; 145 } 146 147 if (p == NULL) 148 { 149 printf("No such node in link!\n"); 150 free(new_node); 151 return ; 152 } 153 if (p->id == (*head)->id) 154 { 155 new_node->next = *head; 156 *head = new_node; 157 } 158 else 159 { 160 q->next = new_node; 161 new_node->next = p; 162 } 163 } 164 #if 1 165 /*刪除節(jié)點*/ 166 void delete_node(Link * head, int data) 167 { 168 Link p = NULL, q = NULL; 169 170 q = p = *head; 171 172 if (p == NULL)//鏈表為空的時候 173 { 174 printf("link is empty!\n"); 175 return ; 176 } 177 else//鏈表不為空的時候 178 { 179 while (p != NULL && p->id != data)//尋找節(jié)點 180 { 181 q = p; 182 p = p->next; 183 } 184 185 if ((*head)->id == data)//刪除節(jié)點為頭節(jié)點時 186 { 187 *head = (*head)->next; 188 free(p);//free(q); 189 } 190 else//刪除節(jié)點不為頭節(jié)點，尾節(jié)點不用考慮 191 { 192 q->next = p->next; 193 free(p); 194 } 195 } 196 } 197 #endif 198 199 #if 0 200 void delete_node(Link * head, int data) 201 { 202 Link p = NULL, q = NULL; 203 204 q = p = *head; 205 206 if (p == NULL)//鏈表為空的時候 207 { 208 printf("link is empty!\n"); 209 return ; 210 } 211 else//鏈表不為空的時候 212 { 213 while (p != NULL && (p->next)->id != data)//尋找節(jié)點 214 { 215 p = p->next; 216 } 217 218 if ((*head)->id == data)//刪除節(jié)點為頭節(jié)點時 219 { 220 *head = (*head)->next; 221 free(p);//free(q); 222 } 223 else//刪除節(jié)點不為頭節(jié)點，尾節(jié)點不用考慮 224 { 225 q = p->next; 226 p->next = q->next; 227 free(q); 228 } 229 } 230 } 231 #endif 232 233 /*插入之后依舊有序*/ 234 void insert_node_seq(Link * head, Link new_node) 235 { 236 Link p = NULL, q = NULL; 237 238 p = q = *head; 239 240 if (p == NULL)//鏈表為空的時候 241 { 242 *head = new_node; 243 new_node->next = NULL; 244 } 245 else 246 { 247 while (p != NULL && p->id < new_node->id)//尋找位置 248 { 249 q = p; 250 p = p->next; 251 } 252 253 if ((*head)->id > new_node->id)//找到的節(jié)點為頭節(jié)點 254 { 255 new_node->next = *head; 256 *head = new_node; 257 } 258 else 259 { 260 q->next = new_node; 261 new_node->next = p; 262 } 263 } 264 } 265 266 #if 1 267 /*插入依舊有序實現方法二*/ 268 void insert_node_seq_1(Link * head, Link new_node) 269 { 270 Link p = NULL; 271 Link q = NULL; 272 273 p = q = *head; 274 275 if (p == NULL)//空鏈表 276 { 277 *head = new_node; 278 new_node->next =NULL; 279 } 280 else 281 { 282 while ((p->id < new_node->id) && (p->next != NULL)) 283 { 284 q = p; 285 p = p->next; 286 } 287 288 if ((*head)->next == NULL)//一個節(jié)點的時候 289 { 290 if (p->id > new_node->id) 291 { 292 new_node->next = *head; 293 *head = new_node; 294 } 295 else 296 { 297 p->next = new_node; 298 } 299 } 300 else 301 { 302 if (p->next == NULL)//尾節(jié)點 303 { 304 if (p->id > new_node->id)//插入前 305 { 306 q->next = new_node; 307 new_node->next = p; 308 } 309 else 310 { 311 p->next = new_node; 312 } 313 } 314 else//不是尾節(jié)點 315 { 316 if((*head)->id > new_node->id)//頭節(jié)點 317 { 318 new_node->next = *head; 319 *head = new_node; 320 } 321 else//中間插入時 322 { 323 q->next = new_node; 324 new_node->next = p; 325 } 326 } 327 }/*end of if()*/ 328 }/*end of if (p == NULL)*/ 329 } 330 #endif 331 332 int main() 333 { 334 Link head = NULL;//防止出現野指針 335 Link new_node = NULL;//防止出現野指針 336 int i; 337 int data; 338 339 create_link(&head);//創(chuàng)建鏈表 340 341 for (i = 0; i < 10; i++)//值域賦值，并插入新節(jié)點 342 { 343 // new_node = (Link)malloc(sizeof(Node));//創(chuàng)建新節(jié)點 344 create_node(&new_node); 345 // new_node->id = i + 1;//賦值 346 // insert_node_head(&head, new_node);//插入節(jié)點，頭插 347 // insert_node_tail(&head, new_node);//插入節(jié)點，尾插 348 349 printf("please input node value:\n"); 350 scanf("%d", &new_node->id); 351 insert_node_seq(&head, new_node); 352 // insert_node_seq_1(&head, new_node); 353 display_link(head);//輸出節(jié)點的值域 354 } 355 356 display_link(head);//輸出節(jié)點的值域 357 358 #if 0 359 create_node(&new_node); 360 new_node->id = i + 1; 361 insert_node_mid(&head, new_node, 3);//指定位置插入，中間插入 362 putchar(10); 363 display_link(head);//輸出節(jié)點的值域 364 365 #if 0 366 create_node(&new_node); 367 scanf("%d", &new_node->id); 368 insert_node_mid_front(&head, new_node); 369 display_link(head);//輸出節(jié)點的值域 370 #endif 371 372 scanf("%d", &i); 373 delete_node(&head, i);//刪除指定節(jié)點 374 display_link(head); 375 376 #if 0 377 378 create_node(&new_node); 379 scanf("%d", &new_node->id); 380 insert_node_seq(&head, new_node);//有序插入指定元素 381 display_link(head); 382 #endif 383 #endif 384 realse_node(&head);//釋放節(jié)點 385 386 display_link(head);//輸出節(jié)點的值域 387 return 0; 388 }

由于鏈式數據結構中有指針的各種指向問題，所以在紙上畫圖是比較容易理解。

其中在對頭指針（注意是頭指針，不是頭節(jié)點，兩個不是一個概念，頭指針是整個鏈表的操作的基礎，鏈表存在的象征，頭指針是整個“鏈表公司”的一把手，頭頭結點是鏈表中的第一個元素）的操作，除了在插入，刪除和銷毀中頭指針的指向發(fā)生改變，需要直接對頭指針head操作外，其他方法都不要對頭指針進行操作，以免丟失整個鏈表。

在對鏈表中的增加時，需要考慮鏈表中開始存在的元老級的“人物”，所以我們不能隨便就對它們變換“崗位”，我得先找到”接班人“之后再對這些元老級的崗位進行調整。

在對鏈表中的節(jié)點進行刪除時，也需要首先考慮這些元老級的“人物”，畢竟人家沒有功勞也有苦勞，我們得代理好它走后它的”上級“和他的”下級“溝通交流的問題。

代碼中的一些條件編譯和注釋是未完成一些功能的另一種方法。

在銷毀整個鏈表時，相當于整個鏈表公司破產，作為公司一把手的head，依次需要對手下任勞任怨的員工進行思想工作。當整個公司沒有員工時，一把手也什么都沒有了即NULL。

代碼中的功能函數包括：

1.創(chuàng)建鏈表

2.創(chuàng)建節(jié)點

3.插入節(jié)點------------頭插，尾插以及插入即有序，指定位置插入的方法，根據需要選擇合適的方法

　　頭插：實現鏈式棧

　　尾插：實現鏈式隊列

4.刪除節(jié)點

5.銷毀整個鏈

6.判斷malloc函數是否執(zhí)行成功

7.輸出鏈

來源:http://www.cnblogs.com/SimonKly/p/6890287.html

總結

以上是生活随笔為你收集整理的不带头结点的单链表------C语言实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。