[已解决]链表排序

jackz007

1. #include<stdio.h>
   
2. #include<malloc.h>
   
3. #include<stdlib.h>
   
4. 
   
5. struct data{
   
6.         int n;
   
7.         struct data *next;
   
8. };
   
9. 
   
10. #define LEN sizeof(struct data)
    
11. 
    
12. int m ;
    
13. int N ; //全局变量，用来记录存放了多少数据。
    
14. 
    
15. struct data * creat(void)//创建链表函数
    
16. {
    
17.         struct data * head , * p1 , * p2                                             ;
    
18.         int d , k                                                                    ;
    
19.         for(N = 0 , k = 0 ;; k ++ , N ++) {
    
20.                 printf("Please enter a number(-1 for ending input) : ")              ;
    
21.                 scanf("%d" , & d)                                                    ;
    
22.                 if(d != -1) {
    
23.                         if((p2 = malloc(sizeof(struct data))) != NULL) {
    
24.                                 p2 -> n = d                                          ;
    
25.                                 p2 -> next = NULL                                    ;
    
26.                                 if(! k) head = p2                                    ;
    
27.                                 else p1 -> next = p2                                 ;
    
28.                                 p1 = p2                                              ;
    
29.                         } else {
    
30.                                 fprintf(stderr , "\n")                               ;
    
31.                                 fprintf(stderr , "\tError : can't alloc memory !\n") ;
    
32.                                 fprintf(stderr , "\n")                               ;
    
33.                                 exit(1)                                              ;
    
34.                         }
    
35.                 } else {
    
36.                         break                                                        ;
    
37.                 }
    
38.                 printf("\n")                                                         ;
    
39.         }
    
40.         return head                                  ;
    
41. }
    
42. 
    
43. void output(struct data * head)//定义打印输出链表函数
    
44. {
    
45.         struct data * p                                           ;
    
46.         for(p = head ; p ; p = p -> next) printf("%d\n" , p -> n) ;
    
47. }
    
48. 
    
49. struct data * sort(struct data * head)
    
50. {
    
51.         struct data * h , * p , * q , * r , * t                   ;
    
52.         int f                                                     ;
    
53.         for(f = 1 , h = head ; f ;) {
    
54.                 f = 0                                             ;
    
55.                 for(r = NULL , q = h , p = q -> next ; q && p ; r = q , q = p , p = q -> next) {
    
56.                         if(q -> n > p -> n) {
    
57.                                 t = p -> next                     ;
    
58.                                 p -> next = q                     ;
    
59.                                 q -> next = t                     ;
    
60.                                 if(r) {
    
61.                                         r -> next = p             ;
    
62.                                 } else {
    
63.                                         h = p                     ;
    
64.                                 }
    
65.                                 f ++                              ;
    
66.                         }
    
67.                 }
    
68.         }
    
69.         return h                                                  ;
    
70. }
    
71. 
    
72. int main()//主函数
    
73. {
    
74.         int remove_n;//定义存放需要删除的数值的变量·
    
75.         struct data * stu , node;//声明结构指针变量
    
76.         stu = creat() ;//函数返回链表第一个节点的地址
    
77.         output(stu)   ;//打印输出链表
    
78.         printf("\n");//换行
    
79.         stu = sort(stu);//排序
    
80.         printf("The result of ascending sorting:\n");
    
81.         output(stu);//升序输出
    
82. }

复制代码

        编译、运行实况

1. D:\00.Excise\C>cl x.c
   
2. 用于 x86 的 Microsoft (R) C/C++ 优化编译器 19.28.29334 版
   
3. 版权所有(C) Microsoft Corporation。保留所有权利。
   
4. 
   
5. x.c
   
6. Microsoft (R) Incremental Linker Version 14.28.29334.0
   
7. Copyright (C) Microsoft Corporation.  All rights reserved.
   
8. 
   
9. /out:x.exe
   
10. x.obj
    
11. 
    
12. D:\00.Excise\C>x
    
13. Please enter a number(-1 for ending input) : 9
    
14. 
    
15. Please enter a number(-1 for ending input) : 8
    
16. 
    
17. Please enter a number(-1 for ending input) : 7
    
18. 
    
19. Please enter a number(-1 for ending input) : 6
    
20. 
    
21. Please enter a number(-1 for ending input) : 5
    
22. 
    
23. Please enter a number(-1 for ending input) : 4
    
24. 
    
25. Please enter a number(-1 for ending input) : 3
    
26. 
    
27. Please enter a number(-1 for ending input) : 2
    
28. 
    
29. Please enter a number(-1 for ending input) : 1
    
30. 
    
31. Please enter a number(-1 for ending input) : -1
    
32. 9
    
33. 8
    
34. 7
    
35. 6
    
36. 5
    
37. 4
    
38. 3
    
39. 2
    
40. 1
    
41. 
    
42. The result of ascending sorting:
    
43. 1
    
44. 2
    
45. 3
    
46. 4
    
47. 5
    
48. 6
    
49. 7
    
50. 8
    
51. 9
    
52. 
    
53. D:\00.Excise\C>

复制代码