16.单向链表的一些基本操作实现(链表反转,链表有环无环判断,链表冒泡排序,链表快速排序)

运行截图:
链表快速排序原理:

链表定义

struct LinkNode
{
    int data;
    struct LinkNode *pNext;
};
typedef struct LinkNode node;

尾部添加节点

void addback(node **phead, int data)
{
    //先创建新的结点
    node *pnew = (node *)malloc(sizeof(node));
    pnew->data = data;
    pnew->pNext = NULL;

    //如果头结点为空
    if (*phead == NULL)
    {
        //头结点指向pnew
        *phead = pnew;
    }
    else
    {
        //否则备份首地址,找到最后一个
        node *ptemp = *phead;
        while (ptemp->pNext != NULL)
        {
            ptemp = ptemp->pNext;
        }
        ptemp->pNext = pnew;
    }

    
}

显示链表

 1 void showall(node *phead)
 2 {
 3     if (phead == NULL)
 4     {
 5         return;
 6     }
 7     else
 8     {
 9         printf("%5d    本节点地址:%p    下一个节点地址:%p
", phead->data, phead, phead->pNext);
10         showall(phead->pNext);//跳到下一个节点
11     }
12 }

反转显示

void revshowall(node *phead)
{
    if (phead == NULL)
    {
        return;
    }
    else
    {
        showall(phead->pNext);//跳到下一个节点
        printf("%d   ,%p,%p
", phead->data, phead, phead->pNext);
    }
}

头部插入

 1 void addhead(node **pphead, int data)
 2 {
 3     node *pnew = (node *)malloc(sizeof(node));
 4     pnew->data = data;
 5     pnew->pNext = NULL;//赋值
 6 
 7     if (*pphead==NULL)
 8     {
 9         *pphead = pnew;
10     }
11     else
12     {
13         pnew->pNext = *pphead;
14         *pphead = pnew;
15     }
16 }

寻找第一个指定元素的位置

 1 node *searchfirst(node *phead, int finddata)
 2 {
 3     for (node *p = phead; p != NULL; p = p->pNext)
 4     {
 5         if (p->data == finddata)
 6         {
 7             return p;//返回找到的地址
 8         }
 9     }
10     return NULL;
11 }

改变第一个指定元素的值

 1 void changefirst(node *phead, int finddata,int newdata)
 2 {
 3     for (node *p = phead; p != NULL; p = p->pNext)
 4     {
 5         if (p->data == finddata)
 6         {
 7             p->data = newdata;
 8         }
 9     }
10 }

删除第一个指定元素

 1 void deleteFirst(node **phead, int finddata)
 2 {
 3     node *p1 = NULL, *p2 = NULL;//p1向前,p2保存p1的上一个位置
 4     p1 = *phead;//保存头结点
 5     while (p1 != NULL)
 6     {
 7         if (p1->data != finddata)
 8         {
 9             p2 = p1;
10             p1 = p1->pNext;
11         }
12         else
13         {
14             break;
15         }
16     }
17 
18     if (p1 == NULL)
19     {
20         return;
21     }
22     //如果是头结点
23     if (p1 == *phead)
24     {
25         *phead = (*phead)->pNext;
26         free(p1);//头部删除
27     }
28     else
29     {
30         p2->pNext = p1->pNext;
31         free(p1);
32     }
33 
34 }

插入元素(在找到的元素之前插入)

 1 void insertFirstHead(node **phead, int finddata,int newdata)
 2 {
 3     node *p1 = NULL, *p2 = NULL;//p1向前,p2保存p1的上一个位置
 4     p1 = *phead;//保存头结点
 5     while (p1 != NULL)
 6     {
 7         if (p1->data != finddata)
 8         {
 9             p2 = p1;
10             p1 = p1->pNext;
11         }
12         else
13         {
14             break;
15         }
16     }
17 
18     if (p1 == NULL)
19     {
20         return;
21     }
22     
23 
24     node *pnew = (node *)malloc(sizeof(node));//新的结点
25     pnew->data = newdata;
26     pnew->pNext = NULL;//赋值
27 
28      //如果是头结点
29     if (p1 == *phead)
30     {
31          pnew->pNext = p1;
32          *phead = pnew;
33     }
34     else
35     {
36         p2->pNext = pnew;
37         pnew->pNext = p1;
38     }
39 }

插入元素(在找到的元素之后插入)

 1 void insertFirstBack(node **phead, int finddata, int newdata)
 2 {
 3     node *p1 = NULL, *p2 = NULL;//p1向前,p2保存p1的上一个位置
 4     p1 = *phead;//保存头结点
 5     while (p1 != NULL)
 6     {
 7         if (p1->data != finddata)
 8         {
 9             p2 = p1;
10             p1 = p1->pNext;
11         }
12         else
13         {
14             break;
15         }
16     }
17 
18     if (p1 == NULL)
19     {
20         return;
21     }
22 
23     //创建新的结点
24     node *pnew = (node *)malloc(sizeof(node));
25     pnew->data = newdata;
26     pnew->pNext = NULL;//赋值
27 
28     //如果是头结点
29     if (p1 == *phead)
30     {
31         p1->pNext = pnew;
32     }
33     else
34     {
35         pnew->pNext = p1->pNext;
36         p1->pNext = pnew;
37     }
38 }

链表冒泡排序

 1 void  bubblesort(node *phead)
 2 {
 3     for (node *p1 = phead; p1->pNext != NULL; p1 = p1->pNext)
 4     {
 5         for (node *p2 = phead; p2 ->pNext != NULL; p2 = p2->pNext)
 6         {
 7             
 8             if (p2->data > p2->pNext->data)
 9             {
10                 int tmp = p2->data;
11                 p2->data = p2->pNext->data;
12                 p2->pNext->data = tmp;
13             }
14         }
15     }
16 }

链表分段,返回中间点,用于递归快速排序链表

 1 node *fen(node *pbegin, node *pback)
 2 {
 3     int key = pbegin->data;//以第一个数据为分段
 4     //核心思想:保证p,q直接的数据都大于等于key,q在p的后面
 5     node *p = pbegin;//标识第一个节点
 6     node *q = pbegin->pNext;//游标标识第二个节点
 7 
 8     while (q != pback)
 9     {
10         //找到小于key的数据,然后交换
11         if (q->data < key)
12         {
13             //循环下一个节点,并进行赋值(p,q之间的值都大于key)
14             p = p->pNext;
15 
16             int temp = p->data;
17             p->data = q->data;
18             q->data = temp;//交换
19         }
20         q = q->pNext;//循环游标
21     }
22     int temp = p->data;
23     p->data = pbegin->data;
24     pbegin->data = temp;//交换
25 
26     return p;
27 }

快速排序

1 void quicksort(node *pbegin,node *pback)
2 {
3     if (pbegin != pback)
4     {
5         node *pfen = fen(pbegin, pback);//取中间点
6         quicksort(pbegin, pfen);
7         quicksort(pfen->pNext, pback);
8     }
9 }

获取链表的长度

 1 int getnum(node *phead)
 2 {
 3     int i = 0;
 4     while (phead != NULL)
 5     {
 6         i++;
 7         phead = phead->pNext;
 8     }
 9     return i;
10 }

链表反转

 1 void rewind(node **phead)
 2 {
 3     
 4     //备份头节点的地址    位置关系:front back tail
 5     node *front = *phead;
 6     //back在from的后面
 7     node *back = (*phead)->pNext;
 8     //反转后头结点的pNext为NULL
 9     (*phead)->pNext = NULL;
10     //当后一个不为尾节点
11     while ( back != NULL)
12     {
13         //back节点的后一个节点,用于给back节点赋值
14         node *tail = back->pNext;
15         //back节点的pNext为front
16         back->pNext = front;
17         //front移到back节点位置
18         front = back;
19         back = tail;//back移到tail节点位置
20     }
21     *phead = front;
22 }

递归反转

 1 node *digui_rew(node *phead)
 2 {
 3     //在结尾处返回
 4     if (phead == NULL || (phead)->pNext == NULL)
 5     {
 6         return phead;
 7     }
 8     else
 9     {
10         node *next = phead->pNext;
11         node *head = digui_rew(next);
12         next->pNext = phead;
13         phead->pNext = NULL;
14 
15         //第一步递归返回
16         return head;
17     }
18 }

判断链表是否有环(追击相遇,一个一次前进一个,一个一次前进两个,如果有环则一定能相遇)

 1 int isCir(node *phead)
 2 {
 3     node *p1 = phead;//一次前进一个
 4     node *p2 = phead;//一次前进两个
 5 
 6     int flag = 0;//0表示没有环
 7     while (p1 != NULL && p2 != NULL && p2->pNext != NULL)
 8     {
 9         p1 = p1->pNext;
10         p2 = p2->pNext->pNext;
11         if (p1 == p2)
12         {
13             flag = 1;
14             break;
15         }
16     }
17 
18     return flag;
19 }

有序链表合并,把link2合并到link1

 1 void merge(node **head1, node **head2)
 2 {
 3     //备份head2的头结点地址,一直循环结束
 4     node *p2 = *head2;
 5     while (p2 != NULL)
 6     {
 7         //如果比头节点的值要小,则把p2变成p1的头结点
 8         if (p2->data < (*head1)->data)
 9         {
10             node *p2tmp = p2->pNext;//备份p2后一个元素
11             //把头结点地址*head1传给p2->pNext
12             p2->pNext = *head1;
13             //p2的地址传给*head1
14             *head1 = p2;
15             //向后遍历
16             p2 = p2tmp;
17         }
18         else
19         {
20             //p1是第一个后面的节点的data大于p2->data的节点,核心思想是把P2插入到p1之后
21             node *p1;
22             node *p2tmp = p2->pNext;//备份p2后一个元素
23             for (p1 = *head1; p1->pNext != NULL; p1 = p1->pNext)
24             {
25                 if (p1->pNext->data > p2->data)
26                 {
27                     break;
28                 }
29             }
30             p2->pNext = p1->pNext;
31             p1->pNext = p2;
32             
33             p2 = p2tmp;
34         }
35     }
36 }

链表取中间值

 1 node *findmid(node *phead)
 2 {
 3     if (isCir(phead))
 4     {
 5         return NULL;
 6     }
 7 
 8     node *p1 = phead;
 9     node *p2 = phead;
10     while (p1 != NULL && p2 != NULL && p2->pNext != NULL)
11     {
12         p1 = p1->pNext;
13         p2 = p2->pNext->pNext;
14     }
15     return p1;
16 }

完整代码:

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 struct LinkNode
  5 {
  6     int data;
  7     struct LinkNode *pNext;
  8 };
  9 typedef struct LinkNode node;
 10 
 11 //尾部添加节点
 12 void addback(node **phead, int data);
 13 //头部插入
 14 void addhead(node **pphead, int data);
 15 //显示链表
 16 void showall(node *phead);
 17 //反转显示
 18 void revshowall(node *phead);
 19 //寻找第一个元素的位置
 20 node *searchfirst(node *phead, int finddata);
 21 //改变第一个元素的值
 22 void changefirst(node *phead, int finddata, int newdata);
 23 //删除第一个元素
 24 void deleteFirst(node **phead, int finddata);
 25 //插入元素(在找到的元素之前插入)
 26 void insertFirstHead(node **phead, int finddata, int newdata);
 27 //插入元素(在找到的元素之后插入)
 28 void insertFirstBack(node **phead, int finddata, int newdata);
 29 //链表冒泡排序
 30 void  bubblesort(node *phead);
 31 //快速排序
 32 void quicksort(node *pbegin, node *pback);
 33 //链表分段,返回中间点
 34 node *fen(node *pbegin, node *pback);
 35 //获取链表的长度
 36 int getnum(node *phead);
 37 //链表反转
 38 void rewind(node **phead);
 39 //递归反转
 40 void digui_rew(node **phead);
 41 //有序链表合并,把link2合并到link1
 42 void merge(node **link1, node **link2);
 43 //链表取中间值
 44 node *findmid(node *phead);
 45 
 46 //尾部添加节点
 47 void addback(node **phead, int data)
 48 {
 49     //先创建新的结点
 50     node *pnew = (node *)malloc(sizeof(node));
 51     pnew->data = data;
 52     pnew->pNext = NULL;
 53 
 54     //如果头结点为空
 55     if (*phead == NULL)
 56     {
 57         //头结点指向pnew
 58         *phead = pnew;
 59     }
 60     else
 61     {
 62         //否则备份首地址,找到最后一个
 63         node *ptemp = *phead;
 64         while (ptemp->pNext != NULL)
 65         {
 66             ptemp = ptemp->pNext;
 67         }
 68         ptemp->pNext = pnew;
 69     }
 70 
 71     
 72 }
 73 
 74 //显示链表
 75 void showall(node *phead)
 76 {
 77     if (phead == NULL)
 78     {
 79         return;
 80     }
 81     else
 82     {
 83         printf("%5d    本节点地址:%p    下一个节点地址:%p
", phead->data, phead, phead->pNext);
 84         showall(phead->pNext);//跳到下一个节点
 85     }
 86 }
 87 
 88 //反转显示
 89 void revshowall(node *phead)
 90 {
 91     if (phead == NULL)
 92     {
 93         return;
 94     }
 95     else
 96     {
 97         showall(phead->pNext);//跳到下一个节点
 98         printf("%d   ,%p,%p
", phead->data, phead, phead->pNext);
 99     }
100 }
101 
102 //头部插入
103 void addhead(node **pphead, int data)
104 {
105     node *pnew = (node *)malloc(sizeof(node));
106     pnew->data = data;
107     pnew->pNext = NULL;//赋值
108 
109     if (*pphead==NULL)
110     {
111         *pphead = pnew;
112     }
113     else
114     {
115         pnew->pNext = *pphead;
116         *pphead = pnew;
117     }
118 }
119 
120 //寻找第一个指定元素的位置
121 node *searchfirst(node *phead, int finddata)
122 {
123     for (node *p = phead; p != NULL; p = p->pNext)
124     {
125         if (p->data == finddata)
126         {
127             return p;//返回找到的地址
128         }
129     }
130     return NULL;
131 }
132 
133 //改变第一个指定元素的值
134 void changefirst(node *phead, int finddata,int newdata)
135 {
136     for (node *p = phead; p != NULL; p = p->pNext)
137     {
138         if (p->data == finddata)
139         {
140             p->data = newdata;
141         }
142     }
143 }
144 
145 //删除第一个元素
146 void deleteFirst(node **phead, int finddata)
147 {
148     node *p1 = NULL, *p2 = NULL;//p1向前,p2保存p1的上一个位置
149     p1 = *phead;//保存头结点
150     while (p1 != NULL)
151     {
152         if (p1->data != finddata)
153         {
154             p2 = p1;
155             p1 = p1->pNext;
156         }
157         else
158         {
159             break;
160         }
161     }
162 
163     if (p1 == NULL)
164     {
165         return;
166     }
167     //如果是头结点
168     if (p1 == *phead)
169     {
170         *phead = (*phead)->pNext;
171         free(p1);//头部删除
172     }
173     else
174     {
175         p2->pNext = p1->pNext;
176         free(p1);
177     }
178 
179 }
180 
181 //插入元素(在找到的元素之前插入)
182 void insertFirstHead(node **phead, int finddata,int newdata)
183 {
184     node *p1 = NULL, *p2 = NULL;//p1向前,p2保存p1的上一个位置
185     p1 = *phead;//保存头结点
186     while (p1 != NULL)
187     {
188         if (p1->data != finddata)
189         {
190             p2 = p1;
191             p1 = p1->pNext;
192         }
193         else
194         {
195             break;
196         }
197     }
198 
199     if (p1 == NULL)
200     {
201         return;
202     }
203     
204 
205     node *pnew = (node *)malloc(sizeof(node));//新的结点
206     pnew->data = newdata;
207     pnew->pNext = NULL;//赋值
208 
209      //如果是头结点
210     if (p1 == *phead)
211     {
212          pnew->pNext = p1;
213          *phead = pnew;
214     }
215     else
216     {
217         p2->pNext = pnew;
218         pnew->pNext = p1;
219     }
220 }
221 
222 //插入元素(在找到的元素之后插入)
223 void insertFirstBack(node **phead, int finddata, int newdata)
224 {
225     node *p1 = NULL, *p2 = NULL;//p1向前,p2保存p1的上一个位置
226     p1 = *phead;//保存头结点
227     while (p1 != NULL)
228     {
229         if (p1->data != finddata)
230         {
231             p2 = p1;
232             p1 = p1->pNext;
233         }
234         else
235         {
236             break;
237         }
238     }
239 
240     if (p1 == NULL)
241     {
242         return;
243     }
244 
245     //创建新的结点
246     node *pnew = (node *)malloc(sizeof(node));
247     pnew->data = newdata;
248     pnew->pNext = NULL;//赋值
249 
250     //如果是头结点
251     if (p1 == *phead)
252     {
253         p1->pNext = pnew;
254     }
255     else
256     {
257         pnew->pNext = p1->pNext;
258         p1->pNext = pnew;
259     }
260 }
261 
262 //链表冒泡排序
263 void  bubblesort(node *phead)
264 {
265     for (node *p1 = phead; p1->pNext != NULL; p1 = p1->pNext)
266     {
267         for (node *p2 = phead; p2 ->pNext != NULL; p2 = p2->pNext)
268         {
269             
270             if (p2->data > p2->pNext->data)
271             {
272                 int tmp = p2->data;
273                 p2->data = p2->pNext->data;
274                 p2->pNext->data = tmp;
275             }
276         }
277     }
278 }
279 
280 //链表分段,返回中间点
281 node *fen(node *pbegin, node *pback)
282 {
283     int key = pbegin->data;//以第一个数据为分段
284     //核心思想:保证p,q直接的数据都大于等于key,q在p的后面
285     node *p = pbegin;//标识第一个节点
286     node *q = pbegin->pNext;//游标标识第二个节点
287 
288     while (q != pback)
289     {
290         //找到小于key的数据,然后交换
291         if (q->data < key)
292         {
293             //循环下一个节点,并进行赋值(p,q之间的值都大于key)
294             p = p->pNext;
295 
296             int temp = p->data;
297             p->data = q->data;
298             q->data = temp;//交换
299         }
300         q = q->pNext;//循环游标
301     }
302     int temp = p->data;
303     p->data = pbegin->data;
304     pbegin->data = temp;//交换
305 
306     return p;
307 }
308 
309 //快速排序
310 void quicksort(node *pbegin,node *pback)
311 {
312     if (pbegin != pback)
313     {
314         node *pfen = fen(pbegin, pback);//取中间点
315         quicksort(pbegin, pfen);
316         quicksort(pfen->pNext, pback);
317     }
318 }
319 
320 //获取链表的长度
321 int getnum(node *phead)
322 {
323     int i = 0;
324     while (phead != NULL)
325     {
326         i++;
327         phead = phead->pNext;
328     }
329     return i;
330 }
331 
332 //链表反转
333 void rewind(node **phead)
334 {
335     
336     //备份头节点的地址    位置关系:front back tail
337     node *front = *phead;
338     //back在from的后面
339     node *back = (*phead)->pNext;
340     //反转后头结点的pNext为NULL
341     (*phead)->pNext = NULL;
342     //当后一个不为尾节点
343     while ( back != NULL)
344     {
345         //back节点的后一个节点,用于给back节点赋值
346         node *tail = back->pNext;
347         //back节点的pNext为front
348         back->pNext = front;
349         //front移到back节点位置
350         front = back;
351         back = tail;//back移到tail节点位置
352     }
353     *phead = front;
354 }
355 
356 //递归反转
357 node *digui_rew(node *phead)
358 {
359     //在结尾处返回
360     if (phead == NULL || (phead)->pNext == NULL)
361     {
362         return phead;
363     }
364     else
365     {
366         node *next = phead->pNext;
367         node *head = digui_rew(next);
368         next->pNext = phead;
369         phead->pNext = NULL;
370 
371         //第一步递归返回
372         return head;
373     }
374 }
375 
376 //判断链表是否有环(追击相遇,一个一次前进一个,一个一次前进两个,如果有环则一定能相遇)
377 int isCir(node *phead)
378 {
379     node *p1 = phead;//一次前进一个
380     node *p2 = phead;//一次前进两个
381 
382     int flag = 0;//0表示没有环
383     while (p1 != NULL && p2 != NULL && p2->pNext != NULL)
384     {
385         p1 = p1->pNext;
386         p2 = p2->pNext->pNext;
387         if (p1 == p2)
388         {
389             flag = 1;
390             break;
391         }
392     }
393 
394     return flag;
395 }
396 
397 //有序链表合并,把link2合并到link1
398 void merge(node **head1, node **head2)
399 {
400     //备份head2的头结点地址,一直循环结束
401     node *p2 = *head2;
402     while (p2 != NULL)
403     {
404         //如果比头节点的值要小,则把p2变成p1的头结点
405         if (p2->data < (*head1)->data)
406         {
407             node *p2tmp = p2->pNext;//备份p2后一个元素
408             //把头结点地址*head1传给p2->pNext
409             p2->pNext = *head1;
410             //p2的地址传给*head1
411             *head1 = p2;
412             //向后遍历
413             p2 = p2tmp;
414         }
415         else
416         {
417             //p1是第一个后面的节点的data大于p2->data的节点,核心思想是把P2插入到p1之后
418             node *p1;
419             node *p2tmp = p2->pNext;//备份p2后一个元素
420             for (p1 = *head1; p1->pNext != NULL; p1 = p1->pNext)
421             {
422                 if (p1->pNext->data > p2->data)
423                 {
424                     break;
425                 }
426             }
427             p2->pNext = p1->pNext;
428             p1->pNext = p2;
429             
430             p2 = p2tmp;
431         }
432     }
433 }
434 
435 //链表取中间值
436 node *findmid(node *phead)
437 {
438     if (isCir(phead))
439     {
440         return NULL;
441     }
442 
443     node *p1 = phead;
444     node *p2 = phead;
445     while (p1 != NULL && p2 != NULL && p2->pNext != NULL)
446     {
447         p1 = p1->pNext;
448         p2 = p2->pNext->pNext;
449     }
450     return p1;
451 }
452 
453 void main()
454 {
455     node *phead = NULL;//头结点不存放数据
456     node *phead2 = NULL;
457     //尾部插入
458     for (int i = 1; i < 10; i++)
459     {
460         addback(&phead, i);
461     }
462 
463     addback(&phead2, -3);
464     addback(&phead2, 16);
465     addback(&phead2, 8);
466     
467     merge(&phead, &phead2);
468     printf("合并后的链表:
");
469     showall(phead);
470     
471     //获取中间节点
472     node *mid = findmid(phead);
473     printf("

中间节点的值:%d

", mid->data);
474     ////头部插入
475     //addhead(&phead, 20);
476     //addhead(&phead, 21);
477     //
478     ////查找第一个并修改
479     //node *pfind = searchfirst(phead, 4);
480     //pfind->data = 22;
481 
482     ////删除结点
483     //deleteFirst(&phead, 21);
484 
485     ////插入结点
486     //insertFirstHead(&phead, 0, 100);
487     //showall(phead);
488     //printf("链表长度:%d", getnum(phead));
489     //printf("

");
490     ////冒泡排序
491     ////bubblesort(phead);
492     ////快速排序
493     //quicksort(phead, NULL);
494     //printf("快速排序后:
");
495     //showall(phead);
496     //printf("

");
497     ////链表反转
498     ////rewind(&phead);
499     //phead = digui_rew(phead);
500     //printf("递归链表反转后:
");
501     //showall(phead);
502 
503     ////phead->pNext->pNext = phead;
504     ////判断是否有环
505     //printf("

链表是否有环:%d
", isCir(phead));
506     system("pause");
507 }