单链表综合操作

链表是C语言面试中常见的问题，那么我们今天就实现一个作为练习。之前看过一些关于这方面的资料和文章，写的都不尽人意，这次写一个具有启发性的历程，由于时间关系，有些东西还是不能一一罗列实现，因为必须要跳过进行下面的学习了，而且我留下的也都是主干之后的细枝末叶，需要花点时间优化。

eg：---考虑周全的代码---

 1 /*   main.c   */
 2 
 3 
 4 #include <stdio.h>
 5 #include<malloc.h>
 6 #include<stdlib.h>
 7 #include"Mylist.h"
 8 int main(void)
 9 {
10     Mylist *list1=(Mylist*)malloc(sizeof(Mylist));
11     list1->value = 16;
12     list1->next = NULL;
13     Mylist* root = list1;//创建根节点root和第一个节点
14 
15 
16     insert(&root, 15);//有序插入
17     insert(&root, 13);
18     insert(&root, 13);
19     insert(&root, 20);
20     //print(root);//打印节点数据
21 
22     insert1(&root, 13);//无序插入
23     insert1(&root, 13);
24     insert1(&root, 19);
25     insert1(&root, 13);
26     print(root);//打印节点数据
27 
28     //Del_data1(root, 13);err,将出现错误，具体转到定义查看
29     //Del_data(&root, 13);//删除节点
30     //print(root);
31     
32     search(root, 13);
33     Del_data(&root, 13);
34     print(root);
35     search(root, 13);
36 
37     DestroyList(root);//销毁链表
38     return 0;
39 }

从main函数可以看出，我的创建链表头的方式就需要优化，但是这只是一个模拟，我只需要创建一个链表头，后续用插入或者删除对其进行操作，但是，我们应该优化成一个函数，在这个函数，一般命名creat函数中，实现链表的多个节点创建，这不是本文所关心的，而且实现也是容易的，所以先用一个头节点模拟，但是要注意，请用malloc开辟内存，否则后面free会出错，这个bug把我弄地挺恼火了。

 1 /*   Mylist.h   */
 2 
 3 
 4 #ifndef _MYLIST_H_
 5 #define _MYLIST_H_
 6 typedef int listtyp;
 7 typedef struct _SigList {
 8     listtyp value;
 9     //Mylist *link; err，至于为什么，好好回看c和指针，这里Mylist类型还没有创建
10     struct _SigList *next;
11 }Mylist;
12 
13 int insert(register Mylist **linkp, listtyp new_value);
14 int insert1(register Mylist **linkp, listtyp new_value);
15 
16 void print(Mylist*root);
17 int DestroyList(Mylist* list);
18 int ClearList(Mylist* L);
19 void Del_data1(Mylist* list, listtyp del_value);
20 void Del_data(Mylist** list, listtyp del_value);
21 int search(Mylist* list, listtyp element);
22 #endif

重点在于源文件的实现：

  1 #include<stdio.h>
  2 #include<malloc.h>
  3 #include<stdlib.h>
  4 #include"Mylist.h"
  5 
  6 #define FALSE 0
  7 #define TRUE  1
  8 
  9 
 10 /*插入到一个单链表，插入可以有序插入，也可以无序插入，
 11 以有序为例，毕竟这样的场景更实用，
 12 从小到大的顺序。
 13 下面的代码有不好的地方，此时需要二级指针登场
 14 如果忘了有什么不好的地方，P240， c和指针
 15 */
 16 /*
 17 int insert(Mylist * current, listtyp new_value)
 18 {
 19     Mylist *previous;
 20     Mylist *new;
 21     //找到正确的插入位置，从小到大插入
 22     while (current!=NULL && current->value < new_value)
 23 //在这个表达式中，->优先级最高，<优先级大于 !=,&&优先级最低，在不确定优先级的时候应该加括号
 24     {
 25         previous = current;
 26         current = current->next;
 27     }
 28     
 29     new = (Mylist*)malloc(sizeof(Mylist));//
 30     if (new == NULL)
 31     {
 32         return FALSE;
 33     }
 34     new->value = new_value;
 35     new->next = current;
 36     previous->next = new;
 37     return TRUE;
 38 }*/
 39 /*
 40 还是存在特殊情况的讨论，还需要优化
 41 int insert(Mylist **rootp, listtyp new_value)
 42 {
 43     Mylist *current;
 44     Mylist *previous;
 45     Mylist *new;
 46     //得到指向第一个节点的指针
 47     current = *rootp;
 48     previous = NULL;
 49 
 50     //寻找正确的插入位置
 51     while (current!=NULL && current->value<new_value)
 52     {
 53         previous = current;
 54         current = current->next;
 55     }
 56 
 57     //为新节点分配内存
 58     new = (Mylist*)malloc(sizeof(Mylist));
 59     if (new = NULL)
 60         return FALSE;
 61     new->value = new_value;
 62     new->next = current;
 63     if (previous == NULL)
 64         *rootp = new;
 65     else
 66         previous->next = new;
 67     return TRUE;
 68 }
 69 */
 70 //最终版本之插入 ---有序
 71 int insert(register Mylist **linkp, listtyp new_value)
 72 {
 73     register Mylist *current, *new;
 74     
 75     while ((current = *linkp) != NULL && current->value < new_value)
 76     {
 77         linkp = &current->next;//我们只关心节点next字段
 78     }
 79 
 80     new = (Mylist*)malloc(sizeof(Mylist));
 81     if (new == NULL)
 82         return FALSE;
 83     new->value = new_value;
 84     new->next = current;
 85     *linkp = new;
 86     return TRUE;
 87 }
 88 //---无序插入
 89 int insert1(register Mylist **linkp, listtyp new_value)
 90 {
 91     register Mylist *current, *new;
 92 
 93     while ((current = *linkp) != NULL )
 94     {
 95         linkp = &current->next;//我们只关心节点next字段
 96     }
 97 
 98     new = (Mylist*)malloc(sizeof(Mylist));
 99     if (new == NULL)
100         return FALSE;
101     new->value = new_value;
102     new->next = current;
103     *linkp = new;
104     return TRUE;
105 }
106 /*打印函数*/
107 void print(Mylist*root)
108 {
109     while (root != NULL)
110     {
111         printf("%d 
", root->value);
112         root = root->next;
113     }
114 }
115 //销毁链表
116 int DestroyList(Mylist* list)
117 { /* 初始条件：线性表L已存在。操作结果：销毁线性表L */
118   //销毁之后就不要再去访问该链表 ！！！
119     Mylist* q;
120     while (list != NULL)
121     {
122         q = list->next;
123         free(list);
124         list = q;
125     }
126     return 1;
127 }
128 //清空链表
129 int ClearList(Mylist* L) 
130 { /* 初始条件：线性表L已存在。操作结果：将L重置为空表 */
131   //清空之后 还保留链表头，还可以访问该链表
132     Mylist *p,*q;
133     p = L->next; /* p指向第一个结点 */
134     while (p) /* 没到表尾 */
135     {
136         q = p->next;
137         free(p);
138         p = q;
139     }
140     L->next = NULL; /* 头结点指针域为空 */
141     return 1;
142 }
143 /* BUG代码，其他地方都没问题，删除第一个节点将出错，不过在写这个之前我已经
144 想到了，所以用了二级指针的实现方式，还是有进步O(∩_∩)O哈哈~
145 
146 void Del_data1(Mylist* list, listtyp del_value)
147 {
148     Mylist *pre = NULL;
149     Mylist *sav_pre = list;
150     while (sav_pre != NULL && sav_pre->value != del_value)
151     {
152         pre = sav_pre;//保存前一个节点
153         sav_pre = sav_pre->next;
154     }
155     if (sav_pre->value == del_value)
156     {
157         if (sav_pre == (list))//while没有进入，首元素就要删除
158         {
159             //(*list) =sav_pre->next;//和下面一个道理
160             (list) = (list)->next;
161         }
162         else
163         {
164             pre->next = sav_pre->next;
165             printf("delete:%d
", del_value);
166         }
167         free(sav_pre);//sav_pre被删除，故释放其内存，但之后不能再访问，否则内存出错、
168     }
169 }
170 
171 */
172 /*因为上面的代码删除第一个节点时，root会被释放，而后面的打印函数需要root指向第一个节点
173   所以用二级指针，这样可以在函数中改变root的指向，并且释放删除节点的内存
174 */
175 void Del_data(Mylist** list, listtyp del_value)
176 {
177     Mylist *pre = NULL;
178     Mylist *sav_pre = *list;
179     while (sav_pre != NULL && sav_pre->value != del_value)
180     {
181         pre = sav_pre;//保存前一个节点
182         sav_pre = sav_pre->next;
183     }
184     if (sav_pre == NULL)
185     {
186         printf("链表中没有你想删除的数据。
");
187     }
188     else
189     {
190         if (sav_pre->value == del_value)
191         {
192             if (sav_pre == (*list))//while没有进入，首元素就要删除
193             {
194                 //(*list) =sav_pre->next;//和下面一个道理
195                 (*list) = (*list)->next;
196             }
197             else
198             {
199                 pre->next = sav_pre->next;
200             }
201             printf("delete:%d
", del_value);
202             free(sav_pre);//sav_pre被删除，故释放其内存，但之后不能再访问，否则内存出错、
203         }
204     }
205 }
206 
207 int search(Mylist* list, listtyp element)
208 {
209     int toll = 0;
210     int no_or_have = 0;
211     Mylist *s = list;
212     while (s->next!=NULL)//记录一共有多少数据
213     {
214         toll++;
215         s = s->next;
216     }
217     Mylist *pos = list;
218     int count = 0;
219     while (pos != NULL && pos->value != element)//放哨兵
220     {
221         count++;
222         pos = pos->next;
223     }
224     if (pos == NULL)
225     {
226         printf("没有找到查询的值
");
227     }
228     else
229     {
230         if (pos != list)//不是一开头就找到
231         {
232 
233             printf("在第%d节点处找到
", count + 1);
234             count++;
235             //因为上面找到的那个也要占位置，比如上面在2节点处找到了
236             //但是我此时位置还是在2节点，要将其跳过因为，如果在2节点找到，count
237             //并没有计数，所以这里手动加上1
238             while (pos->next != NULL)
239             {
240                 if (pos->next->value == element)
241                 {
242                     //这里的if判断不能写成if(pos->value==element)，
243                     //因为此时pos还是在找的节点处，要跳过该节点
244                     //故写成    if (pos->next->value == element)
245                     printf("在第%d节点处找到
", count + 1);
246                 }
247                 count++;
248                 pos = pos->next;
249 
250             }
251 
252         }
253         else//一开始就找到
254         {
255 
256             printf("在第%d节点处找到
", count + 1);
257             count++;//因为上面找到的那个也要占位置
258 
259             while (pos->next != NULL)
260             {
261                 if (pos->next->value == element)
262                 {
263                     printf("在第%d节点处找到
", count + 1);
264                 }
265                 count++;
266                 pos = pos->next;
267 
268             }
269         }
270     }
271     return 1;
272 }

View Code

这里面的讲究很多。

简要说明，因为大部分都已经有注释。先说插入算法，参考c和指针，经过两个过程，最终实现了一个相对最好的插入程序，再说删除，因为有了上面插入的提示，如果我在删除头结点的时候，会改变root指针，但是我的打印函数print必须要是root指针，自然想到了也用二级指针去del数据，还有就是插入分为有序插入和无序直接插入，有这两个模板应该可以完成大部分插入的要求，再说查找函数，我们要能够查询到一个多次出现的数据，但是删除我是删除的第一个遇到的数据，这也就是需要我们程序员根据需要更改或者优化的地方了，到底是删除第一次遇到的还是只要是这个数据都删除。

NOTE：

其中困扰我很久的一个问题就是链表内存请用堆空间，否则销毁链表free的时候会抛down，明明快要收工的时候，却发现free就失败，最后发现我main函数中的第一个开头点没有用malloc申请空间，改了之后就好了。

插入可以有序可以无序还可以按照你的算法进行插入。

查询函数，一定要可以查询所有存在的数据。

删除函数，根据以后具体业务需要，进行改进，到底是删除全部还是删除第一次遇到的还是删除第N此遇到的，所以删除函数需要根据业务需要进行更改。

二级指针还是必须熟练掌握的。