关于单链表的排序问题

来源：cnblogs　　作者：BlackMaxTime　　时间：2018/12/7 9:31:29　　对本文有异议

　　最近学了单链表，遇到了一些问题，和大家分享一下！

首先看一下带头指针的单链表示意图：

从中可以看到链表的每一个节点（除了尾指针）都有一个指针指向下一个节点（头指针只有只保存了该链表的地址），尾指针指向空。

所以我们要对链表中的某个节点进行操作的话，基本上要使用到该节点的前驱节点和后驱节点。（节点2的前驱节点是节点1，节点2的后驱节点是节点3；）

　　单链表的排序关键在交换，交换有两种方式一种是节点值的交换，另一种是节点的交换。

先讲第一种节点值交换法：

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 //定义STUDENT类型变量 包括了学号、分数
 4 typedef struct student {
 5     int number;
 6     int score;
 7     struct student *pNext;
 8 }STUDENT;
 9 
10 STUDENT *Create(int n) {
11     STUDENT *pHead, *pEnd,*pNew=NULL;
12     int i;
13     pHead=pEnd= (STUDENT*)malloc(sizeof(STUDENT));
14          for (i = 0; i < n; i++)
15      {
16         pNew = (STUDENT*)malloc(sizeof(STUDENT));
17         scanf("%d", &pNew->number);
18         scanf("%d", &pNew->score);
19         pNew->pNext = NULL;
20         pEnd->pNext = pNew;
21         pEnd = pNew;
22 
23     }
24      return pHead;
25 }
26 //输出链表
27 void print(STUDENT *p1) {
28     while (p1->pNext != NULL) {
29         p1 = p1->pNext;
30         printf("%d %d\n", p1->number, p1->score);
31     }
32 }
33 //冒泡排序 节点值交换法
34 void Sort(STUDENT *head) {
35     STUDENT *p, *q;
36     for (p = head->pNext; p != NULL; p = p->pNext)
37         for (q = p->pNext; q != NULL; q = q->pNext)
38             if (p->number > q->number)//根据学号从小到大排序
39             {
40                 int t1 = p->number; p->number = q->number; q->number = t1;
41                 int t2 = p->score; p->score = q->score; q->score = t2;
42             }
43     
44     }
45 
46 int main() {
47     int  n;
48     STUDENT *p;
49     scanf("%d",  &n);
50     p= Create(n);
51     Sort(p);
52     print(p);
53     }

　　根据算法不难看出节点值交换法适用于节点中没有字符串变量以及变量成员较少的情况下，但是实际问题往往是复杂的。

　　比如节点中增加学生的姓名，那么想通过交换节点值的方法是比较复杂的（之后会发博客）。所以我就想能不能想通过交换任意两个节点的位置排序呢？

之后写下了如下代码：

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 //定义STUDENT类型变量 包括学号、姓名、分数
 5 typedef struct student {
 6     unsigned  number;
 7     char name[50];
 8     unsigned score;                                                    
 9     struct  student *pNext;
10 }STUDENT;
11 //寻找前驱节点
12 STUDENT *Find_before(STUDENT* phead, STUDENT* p)
13 {
14     if (!p) return NULL;
15     STUDENT *pbefore = phead;
16     while (pbefore)
17     {
18         if (pbefore->pNext == p)
19             return pbefore;
20         pbefore = pbefore->pNext;
21     }
22     return NULL;
23 }
24 //冒泡排序 按照分数高低排序 交换任意的满足条件的节点
25 //head 为链表的头地址
26 void Sort(STUDENT *head) {
27     STUDENT *p, *pbefore, *q, *qbefore, *t1, *t2;
28     STUDENT *phead = head;
29     for (p = head->pNext; p != NULL; p = p->pNext)
30     {
31         pbefore = Find_before(phead, p);
32         for (q = p->pNext; q != NULL; q = q->pNext)
33         {
34             qbefore = Find_before(phead, q);
35             //当p q节点不相邻
36             if (p->score < q->score && p->pNext != q)
37             {
38                 t1 = pbefore->pNext;              //保存p节点地址
39                 pbefore->pNext = qbefore->pNext;  //把q节点赋值给p节点
40                 qbefore->pNext = t1;             //p节点赋值给q节点
41                 t2 = q->pNext;                   //保存q的后驱节点
42                 q->pNext = p->pNext;            //把p的后驱节点赋值给q的后驱节点
43                 p->pNext = t2;                 //把q的后驱节点赋值给p的后驱节点
44             }
45             //当p q节点相邻
46             else if (p->score < q->score  && p->pNext == q)
47             {
48                 t1 = pbefore->pNext;
49                 pbefore->pNext = p->pNext;
50                 p->pNext = t1;
51                 t1 = q->pNext;
52             }
53 
54         }
55 
56     }
57 
58 }

　　　　上面的代码看似没有问题但却忽略了一个问题--交换之后的p,q 将for语句的循环破坏了! 我们来看一下p q不相邻情况下的交换图：

如果按照for语句中执行语句q=q->pNext ，q更新后为节点3，而不是我们想要的节点5。所以这种交换任意节点排序的方法是错误的

　　之后我又换了个思路：（假设按分数从高到低为链表节点排序）在链表a中找到最高分节点q，然后将q节点接在b链表（空链表）的头指针后面，

再通过q的前后驱动节点将q从a链表中剔除，接下来又在a链表中寻找最高分节点q'，如此循环直到a链表为空。

　　代码如下：

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 //创建STUDENT类型变量 包括学号、姓名、成绩
 5 typedef struct student {
 6     int  number;
 7     char name[50];
 8     int  score;
 9     struct  student *pNext;
10 }STUDENT;
11 //创建链表
12 STUDENT *Create(int n) {
13     STUDENT *pHead, *pEnd, *pNew = NULL;
14     int i; char str[100][50];
15     pHead = pEnd = (STUDENT*)malloc(sizeof(STUDENT));
16     for (i = 0; i < n; i++)
17     {
18         pNew = (STUDENT*)malloc(sizeof(STUDENT));
19         scanf("%d%s%d", &pNew->number, &str[i], &pNew->score);
20         strcpy(pNew->name, str[i]);//只有字符串初始化时才能使用“=”赋值
21         pNew->pNext = NULL;
22         pEnd->pNext = pNew;
23         pEnd = pNew;
24 
25     }
26     return pHead;
27 }
28 //寻找前驱节点
29 STUDENT *Find_before(STUDENT* phead, STUDENT* p)
30 {
31     if (!p) return NULL;
32     STUDENT *pbefore = phead;
33     while (pbefore)
34     {
35         if (pbefore->pNext == p)
36             return pbefore;
37         pbefore = pbefore->pNext;
38     }
39     return NULL;
40 }
41 
42 STUDENT *Sort(STUDENT *head) {
43     STUDENT *pHead,*pEnd,*q=NULL,*qbefore=NULL,*p=NULL;
44     int maxscore;
45     pHead=pEnd = (STUDENT*)malloc(sizeof(STUDENT));
46     while (head->pNext != NULL)
47     {
48         maxscore = head->pNext->score;
49         q = p = head->pNext;
50         //寻找最高分节点p
51         while (p->pNext!=NULL)
52         {
53             if(maxscore<p->pNext->score)
54             {
55                 maxscore = p->pNext->score; q = p->pNext;
56             }
57             p = p->pNext;
58         }
59         pEnd->pNext = q;    //将头指针指向q
60         q->pNext = NULL;    //q节点指向空
61         pEnd = q;            //更新尾节点
62         qbefore = Find_before(head,q);  //寻找q节点的前驱节点
63         qbefore->pNext = q->pNext; //将q的前驱节点指向q的后驱节点 从而将q节点从a链表中剔除
64     }
65     free(head);//释放head链表头节点
66     return pHead;
67 }
68 void print(STUDENT *q) {
69     while (q->pNext != NULL)
70     {
71         q = q->pNext; printf("%s\n", q->name);
72     }
73     free(q);//释放使用完的链表
74 }
75 int main() {
76     int n, i = 1; STUDENT *p,*q;
77     scanf("%d", &n);
78     p = Create(n);
79     q=Sort(p);
80     print(q);
81 }