数据结构 实验报告-6

1. 寻找大富翁

1.1 实验内容

胡润研究院的调查显示，截至2017年底，中国个人资产超过1亿元的高净值人群达15万人。假设给出N个人的个人资产值，请快速找出资产排前M位的大富翁。

1.2 实验目的

掌握选择、插入、冒泡三种排序方法，根据实际问题选择合适的排序算法。

1.3 程序清单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <stdio.h>
#include <stdlib.h>

/**
 * @brief 快速读取一个 long long 整数, 支持负数
 * 
 * @return long long 整数值
 */
long long read_ll()
{
    long long    x = 0;
    long long sign = 1;
    char c = getchar();

    while (c == ' ' || c == '\n' || c == '\t' || c == '\r') {
        c = getchar();
    }

    // 处理负号
    if (c == '-') {
        sign = -1;
        c = getchar();
    }

    // 读取数字部分
    while (c >= '0' && c <= '9') {
        x = x * 10 + (c - '0');
        c = getchar();
    }
    return sign * x;
}

/**
 * @brief 降序比较函数
 * 
 * @param a A 值
 * @param b B 值
 * @return int -1->A 在 B 后 | 0->相等 | 1->A 在 B 前
 */
int cmp_desc(const void *a, const void *b)
{
    long long va = *(const long long *)a;
    long long vb = *(const long long *)b;

    if (va < vb) {
        return 1;
    }
    if (va > vb) {
        return -1;
    }

    return 0;
}

/**
 * @brief 最小堆的上浮操作
 * 
 * @param heap 最小堆数组
 * @param idx  上浮节点下标
 */
void heap_swim(long long heap[], int idx)
{
    while (idx > 0) {
        int parent = (idx - 1) / 2;

        if (heap[idx] < heap[parent]) {
            long long tmp = heap[idx];
            heap[idx] = heap[parent];
            heap[parent] = tmp;
            idx = parent;
        } else {
            break;
        }
    }
}

/**
 * @brief 最小堆的下沉操作
 * 
 * @param heap 最小堆数组
 * @param size 当前堆大小
 */
void heap_sink(long long heap[], int size)
{
    int idx = 0;

    while (1) {
        int left     = idx * 2 + 1;
        int right    = idx * 2 + 2;
        int smallest = idx;

        if (left < size && heap[left] < heap[smallest]) {
            smallest = left;
        }
        if (right < size && heap[right] < heap[smallest]) {
            smallest = right;
        }
        if (smallest == idx) {
            break;
        }

        long long tmp = heap[idx];
        heap[idx] = heap[smallest];
        heap[smallest] = tmp;
        idx = smallest;
    }
}

int main()
{
    int n;
    int m;
    scanf("%d %d", &n, &m);

    int heap_size = 0;
    int cap = m < n ? m : n;
    long long *heap = (long long *)malloc(sizeof(long long) * cap);

    for (int i = 0; i < n; i++) {
        long long val = read_ll();

        if (heap_size < cap) {
            // 堆未满, 直接插入末尾, 然后上浮
            heap[heap_size] = val;
            heap_swim(heap, heap_size);
            heap_size++;
        }
        else if (val > heap[0]) {
            // 堆已满，且当前值大于最小堆顶，替换堆顶并下沉
            heap[0] = val;
            heap_sink(heap, heap_size);
        }
    }

    // 对堆中的元素进行降序排序
    qsort(heap, heap_size, sizeof(long long), cmp_desc);

    for (int i = 0; i < heap_size; ++i) {
        if (i > 0) {
            putchar(' ');
        }
        printf("%lld", heap[i]);
    }
    putchar('\r\n');

    free(heap);
    return 0;
}

1.4 调试步骤

  1. 输入测试数据
1
2
8 3
8 12 7 3 20 9 5 18
  1. 程序输出
1
20 18 12

1.5 分析与思考

设 n 为总人数，m 为需要找出的前 m 名。

  • 空间复杂度：$O(m)$

  • 时间复杂度：$O(n \log m)$

2. 奥运排行榜

2.1 实验内容

每年奥运会各大媒体都会公布一个排行榜，但是细心的读者发现，不同国家的排行榜略有不同。比如中国金牌总数列第一的时候，中国媒体就公布“金牌榜”。而美国的奖牌总数第一，于是美国媒体就公布“奖牌榜”。如果人口少的国家公布一个“国民人均奖牌榜”，说不定非洲的国家会成为榜魁……现在就请你写一个程序，对每个前来咨询的国家按照对其最有利的方式计算它的排名。

2.2 实验目的

掌握结构体排序，熟悉基本排序算法。

2.3 程序清单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
#include <stdio.h>
#include <float.h>
#include <stdlib.h>

#define MAX 224

typedef struct country_s {
    int    pop;  // 人口数
    int   gold;  // 金牌数
    int medals;  // 奖牌数
} country_t;

country_t countries[MAX];
double   cur_scores[MAX];

int cmp_desc(const void *a, const void *b)
{
    int va = *(int *)a;
    int vb = *(int *)b;
    if (cur_scores[va] > cur_scores[vb]) return -1;
    if (cur_scores[va] < cur_scores[vb]) return  1;
    return 0;
}

int main()
{
    int n, m;
    scanf("%d %d", &n, &m);

    for (int i = 0; i < n; i++) {
        scanf("%d %d %d", &countries[i].gold, &countries[i].medals, &countries[i].pop);
    }

    int ranks[MAX][5];
    int      idx[MAX];

    // 按金牌数排名
    for (int i = 0; i < n; i++) {
        cur_scores[i] = (double)countries[i].gold;
        idx[i] = i;
    }
    qsort(idx, n, sizeof(int), cmp_desc);

    {
        int rank = 1;
        for (int i = 0; i < n; i++) {
            if (i > 0 && cur_scores[idx[i]] < cur_scores[idx[i - 1]]) {
                rank = i + 1;
            }
            ranks[idx[i]][1] = rank;
        }
    }

    // 按奖牌数排名
    for (int i = 0; i < n; i++) {
        cur_scores[i] = (double)countries[i].medals;
        idx[i] = i;
    }
    qsort(idx, n, sizeof(int), cmp_desc);

    {
        int rank = 1;
        for (int i = 0; i < n; i++) {
            if (i > 0 && cur_scores[idx[i]] < cur_scores[idx[i - 1]]) {
                rank = i + 1;
            }
            ranks[idx[i]][2] = rank;
        }
    }

    // 按人均金牌数排名
    for (int i = 0; i < n; i++) {
        if (countries[i].pop == 0) {
            if (countries[i].gold == 0) {
                cur_scores[i] = 0.0;
            } else {
                cur_scores[i] = DBL_MAX;
            }
        } else {
            cur_scores[i] = (double)countries[i].gold / countries[i].pop;
        }
        idx[i] = i;
    }
    qsort(idx, n, sizeof(int), cmp_desc);

    {
        int rank = 1;
        for (int i = 0; i < n; i++) {
            if (i > 0 && cur_scores[idx[i]] < cur_scores[idx[i - 1]]) {
                rank = i + 1;
            }
            ranks[idx[i]][3] = rank;
        }
    }

    // 按人均奖牌数排名
    for (int i = 0; i < n; i++) {
        if (countries[i].pop == 0) {
            if (countries[i].medals == 0) {
                cur_scores[i] = 0.0;
            } else {
                cur_scores[i] = DBL_MAX;
            }
        } else {
            cur_scores[i] = (double)countries[i].medals / countries[i].pop;
        }
        idx[i] = i;
    }
    qsort(idx, n, sizeof(int), cmp_desc);

    {
        int rank = 1;
        for (int i = 0; i < n; i++) {
            if (i > 0 && cur_scores[idx[i]] < cur_scores[idx[i - 1]]) {
                rank = i + 1;
            }
            ranks[idx[i]][4] = rank;
        }
    }

    for (int q = 0; q < m; q++) {
        int country;
        scanf("%d", &country);

        int best_rank = ranks[country][1];
        int best_method = 1;

        for (int m = 2; m <= 4; m++) {
            if (ranks[country][m] < best_rank) {
                best_rank = ranks[country][m];
                best_method = m;
            }
        }

        if (q > 0) {
            printf(" ");
        }
        printf("%d:%d", best_rank, best_method);
    }
    printf("\r\n");

    return 0;
}

2.4 调试步骤

  1. 输入测试数据
1
2
3
4
5
6
4 4
51 100 1000
36 110 300
6 14 32
5 18 40
0 1 2 3
  1. 程序输出
1
1:1 1:2 1:3 1:4

2.5 分析与思考

设 n 为国家总数，m 为查询次数。

  • 空间复杂度：$O(n)$

  • 时间复杂度：$O(n \log n + m)$

3. PTA 排名汇总

3.1 实验内容

计算机程序设计能力考试（Programming Ability Test，简称 PAT）旨在通过统一组织的在线考试及自动评测方法客观地评判考生的算法设计与程序设计实现能力，科学的评价计算机程序设计人才，为企业选拔人才提供参考标准（网址）。

每次考试会在若干个不同的考点同时举行，每个考点用局域网，产生本考点的成绩。考试结束后，各个考点的成绩将即刻汇总成一张总的排名表。现在就请你写一个程序自动归并各个考点的成绩并生成总排名表。

3.2 实验目的

掌握结构体排序，熟悉基本排序算法。

3.3 程序清单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <stdio.h>
#include <stdlib.h>

#define MAX_N 100
#define MAX_K 300
#define MAX_STUDENTS (MAX_N * MAX_K)

typedef struct student_s {
    long long   id;
    int       site;
    int      score;
    int local_rank;
    int final_rank;
} student_t;

int total = 0;
student_t students[MAX_STUDENTS];


/* 按考号递增排序, 用于同分排名时按考号排序 */
int cmp_by_id(const void *a, const void *b)
{
    const student_t *sa = (const student_t *)a;
    const student_t *sb = (const student_t *)b;
    if (sa->id < sb->id) return -1;
    if (sa->id > sb->id) return  1;
    return 0;
}

/* 按分数降序, 分数相同按考号升序 */
int cmp_by_score(const void *a, const void *b)
{
    const student_t *sa = (const student_t *)a;
    const student_t *sb = (const student_t *)b;

    if (sa->score != sb->score) {
        return sb->score - sa->score;
    }

    // 分数相同，考号升序
    if (sa->id < sb->id) return -1;
    if (sa->id > sb->id) return  1;
    return 0;
}

/* 最终排名输出时的比较：按最终排名升序，同排名按考号升序 */
int cmp_by_final_rank(const void *a, const void *b)
{
    const student_t *sa = (const student_t *)a;
    const student_t *sb = (const student_t *)b;

    if (sa->final_rank != sb->final_rank) {
        return sa->final_rank - sb->final_rank;
    }

    if (sa->id < sb->id) return -1;
    if (sa->id > sb->id) return  1;
    return 0;
}

int main()
{
    int n;
    scanf("%d", &n);

    for (int site = 1; site <= n; site++) {
        int k;
        scanf("%d", &k);

        int start = total;

        for (int i = 0; i < k; i++) {
            scanf("%lld %d", &students[total].id, &students[total].score);
            students[total].site = site;
            total++;
        }

        qsort(students + start, k, sizeof(student_t), cmp_by_score);

        // 计算考点内排名
        for (int i = start; i < start + k; i++) {
            if (i == start) {
                students[i].local_rank = 1;
            } else {
                if (students[i].score == students[i - 1].score) {
                    students[i].local_rank = students[i - 1].local_rank;
                } else {
                    students[i].local_rank = (i - start) + 1;
                }
            }
        }
    }

    // 全局按 分数降序 或 考号升序 排序
    qsort(students, total, sizeof(student_t), cmp_by_score);

    // 计算最终排名
    for (int i = 0; i < total; i++) {
        if (i == 0) {
            students[i].final_rank = 1;
        } else {
            if (students[i].score == students[i - 1].score) {
                students[i].final_rank = students[i - 1].final_rank;
            } else {
                students[i].final_rank = i + 1;
            }
        }
    }

    qsort(students, total, sizeof(student_t), cmp_by_final_rank);

    printf("%d\r\n", total);
    for (int i = 0; i < total; i++) {
        printf("%013lld %d %d %d\n",
               students[i].id,
               students[i].final_rank,
               students[i].site,
               students[i].local_rank);
    }
    return 0;
}

3.4 调试步骤

  1. 输入测试数据
1
2
3
4
5
6
7
8
9
10
11
12
2
5
1234567890001 95
1234567890005 100
1234567890003 95
1234567890002 77
1234567890004 85
4
1234567890013 65
1234567890011 25
1234567890014 100
1234567890012 85
  1. 程序输出
1
2
3
4
5
6
7
8
9
10
9
1234567890005 1 1 1
1234567890014 1 2 1
1234567890001 3 1 2
1234567890003 3 1 2
1234567890004 5 1 4
1234567890012 5 2 2
1234567890002 7 1 5
1234567890013 8 2 3
1234567890011 9 2 4

3.5 分析与思考

设 n 为总学生人数。

  • 空间复杂度：$O(n)$

  • 时间复杂度：$O(n \log n)$

课程报告
#河北工业大学 #数据结构
数据结构 实验报告-6
https://flowerdown.org/posts/20220609-193458
作者
Unrealfeathers
发布于
2022年6月9日
许可协议