7-47 打印选课学生名单 (25分)--桶排

 1 /*每个课程当做一个桶，桶里面用链表按学生姓名字典序存储学生，最后直接输出每个桶的内容，排序的时候使用头插法*/
 2 #include<iostream>
 3 #include <map>
 4 #include <cstring>
 5 #include <algorithm>
 6 using namespace std;
 7 struct Stu
 8 {
 9     char name[5];
10     int course[20];
11     int num;
12 };
13 bool cmp(Stu s1, Stu s2)//后面要使用头插法建链表，所以先按字典序逆序排序
14 {
15     if (strcmp(s1.name, s2.name) > 0)
16     {
17         return true;
18     }
19     else return false;
20 }
21     struct course
22     {
23         char s_name[5];
24         struct course* next;
25     };
26 int main()
27 {
28     int N, K;
29     cin >> N >> K;
30     long long int* course_num = new long long int[K + 1]{ 0 };
31     struct Stu* stu = new struct Stu[N];
32     struct course* crs = new struct course[K + 1];
33     for (int i = 1; i <= K; i++)
34     {
35         crs[i].next = NULL;
36     }
37     for (int i = 0; i < N; i++)
38     {
39     scanf("%s",stu[i].name);
40     scanf("%d",&stu[i].num);
41         for (int j = 0; j < stu[i].num; j++)
42         {
43       scanf("%d",&stu[i].course[j]);
44             course_num[stu[i].course[j]]++;
45         }
46     }
47     sort(stu, stu + N, cmp);
48     for (int i = 0; i < N; i++)
49     {
50         for (int j = 0; j < stu[i].num; j++)
51         {
52             int c = stu[i].course[j];        
53             struct course* s = new course;
54             strcpy(s->s_name, stu[i].name);
55             s->next = NULL;
56             if (NULL == crs[c].next)
57             {
58                 crs[c].next = s;
59             }
60             else
61             {
62                 struct course* p = crs[c].next;
63                 s->next = p;
64                 crs[c].next = s;
65             }
66         }
67     }
68     for (int i = 1; i <= K; i++)
69     {
70         struct course* p = NULL;
71         p = crs[i].next;
72     printf("%d %lld
",i,course_num[i]);
73         while (NULL != p)
74         {
75       printf("%s
",p->s_name);
76             p = p->next;
77         }
78     }
79     return 0;
80 }