[已解决]如何用 单链表 做 选择排序

为之不止

我想用单链表做学生成绩管理系统

下面是我的结构体

1. struct Student                                        //声明结构体类型
   
2. {
   
3.     char xuehao[8];     //学号
   
4.         char name[8];       //姓名
   
5.         char kecheng[8];    //课程
   
6.         int day_grade;      //平时成绩
   
7.         int shiyan_grade;   //实验成绩
   
8.         int kaoshi_grade;   //考试成绩
   
9.         int end_grade;                //总评成绩
   
10.         struct Student *next;
    
11. };
    

复制代码

其中，管理系统需要实现：按总评成绩高低排序 功能
我想在不改变原序列基础上排序
有人说可以用选择排序，把选出来的写入新的链表，最后新链表就是有序的，这个时候打印完新的链表，再将新链表销毁就可以了
但是我不懂怎么用单链表实现选择排序
特来求教

最佳答案

月排行榜 / 总排行榜

Seawolf

2019-6-8 16:17:22

qsort是c语言内置的快速排序函数，来自于 C 标准库 - <stdlib.h>

1. void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))
   

复制代码

base -- 指向要排序的数组的第一个元素的指针。
nitems -- 由 base 指向的数组中元素的个数。
size -- 数组中每个元素的大小，以字节为单位。
compar -- 用来比较两个元素的函数。
这里有一个例子：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. int values[] = {34, 423, 545, 75, 7 };
   
5. 
   
6. int cmpfunc (const void * a, const void * b)
   
7. {
   
8.    return ( *(int*)a - *(int*)b );
   
9. }
   
10. 
    
11. int main()
    
12. {
    
13.    int n;
    
14. 
    
15.    printf("排序之前的列表：\n");
    
16.    for( n = 0 ; n < 5; n++ ) {
    
17.       printf("%d ", values[n]);
    
18.    }
    
19. 
    
20.    qsort(values, 5, sizeof(int), cmpfunc);
    
21. 
    
22.    printf("\n排序之后的列表：\n");
    
23.    for( n = 0 ; n < 5; n++ ) {
    
24.       printf("%d ", values[n]);
    
25.    }
    
26.   
    
27.   return(0);
    
28. }

复制代码

运行结果：

1. 排序之前的列表：
   
2. 34 423 545 75 7
   
3. 排序之后的列表：
   
4. 7 34 75 423 545

复制代码

跳转到最佳答案楼层

Seawolf

qsort是c语言内置的快速排序函数，来自于 C 标准库 - <stdlib.h>

1. void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))
   

复制代码

base -- 指向要排序的数组的第一个元素的指针。
nitems -- 由 base 指向的数组中元素的个数。
size -- 数组中每个元素的大小，以字节为单位。
compar -- 用来比较两个元素的函数。
这里有一个例子：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. int values[] = {34, 423, 545, 75, 7 };
   
5. 
   
6. int cmpfunc (const void * a, const void * b)
   
7. {
   
8.    return ( *(int*)a - *(int*)b );
   
9. }
   
10. 
    
11. int main()
    
12. {
    
13.    int n;
    
14. 
    
15.    printf("排序之前的列表：\n");
    
16.    for( n = 0 ; n < 5; n++ ) {
    
17.       printf("%d ", values[n]);
    
18.    }
    
19. 
    
20.    qsort(values, 5, sizeof(int), cmpfunc);
    
21. 
    
22.    printf("\n排序之后的列表：\n");
    
23.    for( n = 0 ; n < 5; n++ ) {
    
24.       printf("%d ", values[n]);
    
25.    }
    
26.   
    
27.   return(0);
    
28. }

复制代码

运行结果：

1. 排序之前的列表：
   
2. 34 423 545 75 7
   
3. 排序之后的列表：
   
4. 7 34 75 423 545

复制代码

scau_pdc

666

Seawolf

你可以参考这段代码，当学生名成绩不同时，按照成绩高低来排列，当学生成绩相同时，按照学生姓名的字母顺序来排列

1. typedef struct
   
2. {
   
3.         char last_name[25];
   
4.         int stu_id;
   
5.         char grade;
   
6. } student;
   
7. 
   
8. student input[5] = {
   
9. {"xiaoming",910017,'A'},
   
10. {"xiaoli",934422,'C'},
    
11. {"xiaozhang",878766,'B'},
    
12. {"xiaowang",123456,'D'},
    
13. {"xiaofang",989420,'A'}
    
14. };
    
15. 
    
16. static int cmpstudents(const void *p1, const void *p2)
    
17. {
    
18.     student *l = (student *)p1;
    
19.     student *r = (student *)p2;
    
20.     if (l->grade==r->grade)
    
21.     {
    
22.         return strcmp(l->last_name,r->last_name);
    
23.     }
    
24.     return (l->grade > r->grade)?(1):(-1);
    
25. }
    
26. 
    
27. int main ()
    
28. {
    
29.     int i;
    
30.     for (i=0;i<5;i++)
    
31.     {
    
32.        printf("%s\t%d\t%c\n",input[i].last_name,input[i].stu_id,input[i].grade);
    
33.     }
    
34.     printf("\n----------------------------\n");
    
35.     qsort(input,5,sizeof(student),cmpstudents);
    
36.     for (i=0;i<5;i++)
    
37.     {
    
38.        printf("%s\t%d\t%c\n",input[i].last_name,input[i].stu_id,input[i].grade);
    
39.     }
    
40. 
    
41.     return 0;
    
42. }

复制代码

为之不止

Seawolf 发表于 2019-6-12 11:47
你可以参考这段代码，当学生名成绩不同时，按照成绩高低来排列，当学生成绩相同时，按照学生姓名的字母顺序 ...

非常感谢您的回答，可是，我没看懂::>_<::，第35行的qsort函数是从哪里来的？

为之不止

Seawolf 发表于 2019-6-13 00:14
qsort是c语言内置的快速排序函数，来自于 C 标准库 -

base -- 指向要排序的数组的第一个元素的指针。

总算懂了，感激涕零无以言表，请受小弟一拜

Seawolf

为之不止 发表于 2019-6-13 00:40
总算懂了，感激涕零无以言表，请受小弟一拜

不客气