数据结构 大作业

1. 找出湖景房

1.1 实验内容

在湖边有一排东西向排列的房子。如果一个房子比它东边的所有房子都高，我们称之为湖景房。如图 1-1 所示，阴影的房子都是湖景房。一位旅行者从西往东走至湖景处，决定逗留几天。假设每栋房子的高度存放于数组 A[1…n] 中，请你帮他找出所有的湖景房。

1.2 实现步骤

因为房子从左向右排列，但是找出湖景房需要将房子与其右侧的所有房子做比较，且最右方的房子必然为湖景房。

可以利用栈后进先出的特性，先把房子高度数组元素正序压入栈 s1，然后按照房子高度数组元素的逆序弹出栈顶元素，因为第一个栈顶元素对应最右侧湖边的房子，其必定为湖景房，所以直接压入栈 s2 中。

然后按照题中对湖景房的定义，将每一个从栈 s1 弹出的栈顶元素放入 height 并与储存湖景房高度的 s2 中的栈顶元素进行比较，若弹出的栈顶元素 height 比 s2 中的栈顶元素大，则 height 为湖景房并压入栈 s2。最后将栈 s2 进行遍历，输出所有的湖景房的高度。

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
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX 100

/* 栈的定义 */
typedef struct stack_s {
    int data[MAX];
    int       top;
} stack_t;

/**
 * @brief 初始化栈
 * 
 * @param s 栈指针
 */
void init_stack(stack_t *s)
{
    s->top = -1;
}

/**
 * @brief 判断栈是否为空
 * 
 * @param s 栈指针
 * @return true  空栈
 * @return false 非空栈
 */
bool is_empty(stack_t *s)
{
    return s->top == -1;
}

/**
 * @brief 判断栈是否已满
 * 
 * @param s 栈指针
 * @return true  满栈
 * @return false 非满栈
 */
bool is_full(stack_t *s)
{
    return s->top == MAX - 1;
}

/**
 * @brief 入栈操作
 * 
 * @param s      栈指针
 * @param data   数据
 * @return true  成功
 * @return false 失败
 */
bool push(stack_t *s, int data)
{
    if (is_full(s)) {
        return false;
    }

    s->data[++(s->top)] = data;
    return true;
}

/**
 * @brief 出栈操作
 * 
 * @param s      栈指针
 * @param data   数据
 * @return true  成功
 * @return false 失败
 */
bool pop(stack_t *s, int *data)
{
    if (is_empty(s)) {
        return false;
    }

    *data = s->data[(s->top)--];
    return true;
}

/**
 * @brief 获取栈顶元素
 * 
 * @param s      栈指针
 * @param data   数据
 * @return true  成功
 * @return false 失败
 */
bool peek(stack_t *s, int *data)
{
    if (is_empty(s)) {
        return false;
    }

    *data = s->data[s->top];
    return true;
}

int main()
{
    int height = 0;
    stack_t     s1;  // 所有的房子高度
    stack_t     s2;  // 湖景房房子高度

    init_stack(&s1);
    init_stack(&s2);

    int n = 0;
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        scanf("%d", &height);

        if (height == 0) {
            break;
        }

        if (!push(&s1, height)) {
            return -1;
        }
    }

    // 最右方的房子必然为湖景房
    pop(&s1, &height);
    push(&s2, height);

    while (!is_empty(&s1)) {
        int top;

        pop(&s1, &height);
        peek(&s2, &top);
        if (height > top) {
            push(&s2, height);
        }
    }

    while (!is_empty(&s2)) {
        pop(&s2, &height);
        printf("%d ", height);
    }
    printf("\r\n");
    return 0;
}

1.4 调试步骤

  1. 输入测试数据
1
2
20
266 86 69 110 120 218 90 177 33 168 99 87 63 134 66 34 100 51 92 71
  1. 程序输出
1
266 218 177 168 134 100 92 71

1.5 分析与思考

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

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

  • 时间复杂度：$O()$

2. 学生数据管理

假设某大学某个专业共有 N (<=1000) 位学生，分为 K 个班。所有学生已完成前三学年的课程，并根据前三年的课程计算出了每个学生的绩点。学生信息包括学号、姓名、性别、专业、班级、绩点。所有学生的学号连续，同一个班的学号也连续。假设用顺序表存储这些信息，请完成以下任务。

2.1 任务一

请用 C 语言表示学生信息的存储结构。

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
#include <stdio.h>
#include <stdlib.h>

#define MAX 1001

/* 学生数据结构体 */
typedef struct student_s {
    int         id;  // 学号
    char  name[88];  // 名称
    char gender[8];  // 性别
    char major[88];  // 专业
    int      class;  // 班级
    double   grade;  // 绩点
} student_t;

typedef struct student_list_s {
    student_t students[MAX];
    int              length;
} student_list_t;

void list_init(student_list_t *s)
{
    s->length = 0;
}

void add_student(student_list_t *s, int num)
{
    char line[256];

    for (int i = 0; i < num; i++) {
        if (fgets(line, sizeof(line), stdin) == NULL) {
            break;
        }

        int matched = sscanf(line, "%d %87s %7s %87s %d %lf", 
                                                &s->students[i].id, 
                                                s->students[i].name, 
                                                s->students[i].gender, 
                                                s->students[i].major, 
                                                &s->students[i].class, 
                                                &s->students[i].grade);

        if (matched == 6) {
            s->length++;
        } else {
            continue;
        }
    }
}

void show_students(const student_list_t *s)
{
    for (int i = 0; i < s->length; i++) {
        printf("%d %s %s %s %d %.2lf\r\n", 
                s->students[i].id, 
                s->students[i].name, 
                s->students[i].gender, 
                s->students[i].major, 
                s->students[i].class, 
                s->students[i].grade);
    }
}

int get_student(const student_list_t sl, int idx, student_t *s)
{
    if (idx < 1 || idx > sl.length) {
        return -1;
    }

    *s = sl.students[idx - 1];
    return 0;
}

int insert_student(student_list_t *sl, int idx, student_t s)
{
    if (idx < 1 || idx > sl->length + 1) {
        return -1;
    }

    if (sl->length >= MAX) {
        return -1;
    }

    for (int j = sl->length - 1; j >= idx - 1; j--) {
        sl->students[j + 1] = sl->students[j];
    }

    sl->students[idx - 1] = s;
    sl->length++;
    return 0;
}

int delete_student(student_list_t *sl, int idx, student_t *s)
{
    if (idx < 1 || idx > sl->length) {
        return -1;
    }

    *s = sl->students[idx - 1];

    for (int j = idx; j < sl->length; j++) {
        sl->students[j - 1] = sl->students[j];
    }

    sl->length--;
    return 0;
}

2.2 任务二

假设每个班的学生信息按学号顺序存储，设计一个算法找出该班绩点的中位数，要求不能对绩点完全排序，复杂度不高于 $O(n log n)$。

因为不能对绩点完全排序，且复杂度不得高于 $O(n log n)$。我用的是基于分治策略的中位数查找算法。

首先在所有的学生数据中取中间学生的位次记为 mid，绩点数据记为 value。然后利用 value 这一值，将全班学生按照绩点分为三个组，大于 value 的分到 big，等于 value 的分到 middle，小于 value 的分到 small。如果 small 组的长度大于 mid，则中位数在 small 组中。如果 small < mid <= small + middle，则中位数为 value。如果 mid >= small + middle，则中位数在 big 组中。

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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
#include <stdio.h>
#include <stdlib.h>

#define MAX 1001

/* 学生数据结构体 */
typedef struct student_s {
    int         id;  // 学号
    char  name[88];  // 名称
    char gender[8];  // 性别
    char major[88];  // 专业
    int      class;  // 班级
    double   grade;  // 绩点
} student_t;

typedef struct student_list_s {
    student_t students[MAX];
    int              length;
} student_list_t;

void list_init(student_list_t *sl)
{
    sl->length = 0;
}

void add_student(student_list_t *sl, int num)
{
    char line[256];

    for (int i = 0; i < num; i++) {
        if (fgets(line, sizeof(line), stdin) == NULL) {
            break;
        }

        student_t tmp;
        int matched = sscanf(line, "%d %87s %7s %87s %d %lf", 
                             &tmp.id, tmp.name, tmp.gender, 
                             tmp.major, &tmp.class, &tmp.grade);

        if (matched == 6) {
            sl->students[sl->length] = tmp;
            sl->length++;
        } else {
            continue;
        }
    }
}

void show_students(const student_list_t *sl)
{
    for (int i = 0; i < sl->length; i++) {
        printf("%d %s %s %s %d %.2lf\r\n", 
                sl->students[i].id, 
                sl->students[i].name, 
                sl->students[i].gender, 
                sl->students[i].major, 
                sl->students[i].class, 
                sl->students[i].grade);
    }
}

int get_student(const student_list_t sl, int idx, student_t *s)
{
    if (idx < 1 || idx > sl.length) {
        return -1;
    }

    *s = sl.students[idx - 1];
    return 0;
}

int insert_student(student_list_t *sl, int idx, student_t s)
{
    if (idx < 1 || idx > sl->length + 1) {
        return -1;
    }

    if (sl->length >= MAX) {
        return -1;
    }

    for (int j = sl->length - 1; j >= idx - 1; j--) {
        sl->students[j + 1] = sl->students[j];
    }

    sl->students[idx - 1] = s;
    sl->length++;
    return 0;
}

int delete_student(student_list_t *sl, int idx, student_t *s)
{
    if (idx < 1 || idx > sl->length) {
        return -1;
    }

    *s = sl->students[idx - 1];

    for (int j = idx; j < sl->length; j++) {
        sl->students[j - 1] = sl->students[j];
    }

    sl->length--;
    return 0;
}

/**
 * @brief Lomuto 分区算法
 *        将 arr[left..right] 按 pivot 分成 小于 | 等于 | 大于 三部分
 *        返回等于区的起始和结束索引
 * 
 * @param arr     数组指针
 * @param left    数组起始索引
 * @param right   数组结束索引
 * @param p_start 等于区起始索引
 * @param p_end   等于区结束索引
 */
void three_way_partition(double arr[], int left, int right, int *start_p, int *end_p)
{
    double pivot = arr[left];  // 取左端点作为 pivot
    int        i =      left;  // arr[left..i] < pivot
    int        k =      left;  // arr[i+1..k] == pivot
    int        j =     right;  // arr[j..right] > pivot

    while (k < j) {
        if (arr[k + 1] < pivot) {
            // 交换到小于区
            double tmp = arr[i + 1];
            arr[i + 1] = arr[k + 1];
            arr[k + 1] = tmp;
            i++;
            k++;
        }
        else if (arr[k + 1] == pivot) {
            k++;
        }
        else {
            // 交换到大于区
            double tmp = arr[j];
            arr[j] = arr[k + 1];
            arr[k + 1] = tmp;
            j--;
        }
    }

    // 把 pivot 放到小于区末尾
    double tmp = arr[left];
    arr[left] = arr[i];
    arr[i] = tmp;
    i--;

    *start_p = i + 1;
    *end_p   =     k;
}

/**
 * @brief 在 arr[left..right] 中查找第 k 小的元素, k 从 0 开始
 * 
 * @param arr     数组指针
 * @param left    数组起始索引
 * @param right   数组结束索引
 * @param k       第 k 小
 * @return double 元素值
 */
double quick_select(double arr[], int left, int right, int k)
{
    if (left >= right) {
        return arr[left];
    }

    int eq_start;
    int   eq_end;

    three_way_partition(arr, left, right, &eq_start, &eq_end);

    if (k < eq_start) {
        // 中位数在小于区
        return quick_select(arr, left, eq_start - 1, k);
    }
    else if (k > eq_end) {
        // 中位数在大于区
        return quick_select(arr, eq_end + 1, right, k);
    }
    else {
        // 中位数就在等于区内
        return arr[eq_start];
    }
}

/**
 * @brief 计算学生列表中绩点的中位数
 * 
 * @param sl 学生列表指针
 * @return double 中位数值
 */
double median_calc(const student_list_t *sl)
{
    if (sl->length == 0) {
        return -1.00;
    }

    // 拷贝绩点到临时数组
    double *grades = (double *)malloc(sl->length * sizeof(double));
    if (grades == NULL) {
        return -1.00;
    }

    for (int i = 0; i < sl->length; i++) {
        grades[i] = sl->students[i].grade;
    }

    // 快速选择求中位数
    double median;
    int mid = sl->length / 2;

    if (sl->length % 2 == 1) {
        // 奇数个
        median = quick_select(grades, 0, sl->length - 1, mid);
    } else {
        // 偶数个
        double a = quick_select(grades, 0, sl->length - 1, mid - 1);
        double b = quick_select(grades, 0, sl->length - 1, mid);
        median = (a + b) / 2.00;
    }

    free(grades);
    return median;
}

int main()
{
    student_list_t list;
    list_init(&list);

    int n;
    if (scanf("%d", &n) != 1 || n <= 0) {
        return -1;
    }

    while (getchar() != '\n');

    add_student(&list, n);

    show_students(&list);

    printf("%.2f\r\n", median_calc(&list));
    return 0;
}

2.3 任务三

设计一个算法对一个班的学生按绩点进行升序排序，绩点相同的学生按学号升序排序，要求算法时间复杂度为 $O(n log n)$。

时间复杂度为 $O(n log n)$ 的排序算法有希尔排序、堆排序、快速排序和归并排序。这里我使用的是快速排序，同样利用分治策略，先取一个基准值，然后将比基准值的大的元素放到基准值右边，比基准值小的放到左边，然后多次重复直到各区间只有一个数。

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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
#include <stdio.h>
#include <stdlib.h>

#define MAX 1001

/* 学生数据结构体 */
typedef struct student_s {
    int         id;  // 学号
    char  name[88];  // 名称
    char gender[8];  // 性别
    char major[88];  // 专业
    int      class;  // 班级
    double   grade;  // 绩点
} student_t;

typedef struct student_list_s {
    student_t students[MAX];
    int              length;
} student_list_t;

void list_init(student_list_t *sl)
{
    sl->length = 0;
}

void add_student(student_list_t *sl, int num)
{
    char line[256];

    for (int i = 0; i < num; i++) {
        if (fgets(line, sizeof(line), stdin) == NULL) {
            break;
        }

        student_t tmp;
        int matched = sscanf(line, "%d %87s %7s %87s %d %lf", 
                             &tmp.id, tmp.name, tmp.gender, 
                             tmp.major, &tmp.class, &tmp.grade);

        if (matched == 6) {
            sl->students[sl->length] = tmp;
            sl->length++;
        } else {
            continue;
        }
    }
}

void show_students(const student_list_t *sl)
{
    for (int i = 0; i < sl->length; i++) {
        printf("%d %s %s %s %d %.2lf\r\n", 
                sl->students[i].id, 
                sl->students[i].name, 
                sl->students[i].gender, 
                sl->students[i].major, 
                sl->students[i].class, 
                sl->students[i].grade);
    }
}

int get_student(const student_list_t sl, int idx, student_t *s)
{
    if (idx < 1 || idx > sl.length) {
        return -1;
    }

    *s = sl.students[idx - 1];
    return 0;
}

int insert_student(student_list_t *sl, int idx, student_t s)
{
    if (idx < 1 || idx > sl->length + 1) {
        return -1;
    }

    if (sl->length >= MAX) {
        return -1;
    }

    for (int j = sl->length - 1; j >= idx - 1; j--) {
        sl->students[j + 1] = sl->students[j];
    }

    sl->students[idx - 1] = s;
    sl->length++;
    return 0;
}

int delete_student(student_list_t *sl, int idx, student_t *s)
{
    if (idx < 1 || idx > sl->length) {
        return -1;
    }

    *s = sl->students[idx - 1];

    for (int j = idx; j < sl->length; j++) {
        sl->students[j - 1] = sl->students[j];
    }

    sl->length--;
    return 0;
}

int cmp_asc(student_t a, student_t b)
{
    if (a.grade != b.grade) {
        return (a.grade < b.grade) ? -1 : 1;
    }
    if (a.id != b.id) {
        return (a.id < b.id) ? -1 : 1;
    }
    return 0;
}

/**
 * @brief Lomuto 分区算法
 *        将 arr[left..right] 按 pivot 分成 小于 | 等于 | 大于 三部分
 *        返回等于区的起始和结束索引
 * 
 * @param arr     数组指针
 * @param left    数组起始索引
 * @param right   数组结束索引
 * @param p_start 等于区起始索引
 * @param p_end   等于区结束索引
 */
void three_way_partition(student_t arr[], int left, int right, int *start_p, int *end_p)
{
    student_t pivot = arr[left];  // 取左端点作为 pivot
    int           i =      left;  // arr[left..i] < pivot
    int           k =      left;  // arr[i+1..k] == pivot
    int           j =     right;  // arr[j..right] > pivot

    while (k < j) {
        int cmp = cmp_asc(arr[k + 1], pivot);

        if (cmp < 0) {
            // 交换到小于区
            student_t tmp = arr[i + 1];
            arr[i + 1]    = arr[k + 1];
            arr[k + 1]    =        tmp;
            i++;
            k++;
        }
        else if (cmp == 0) {
            k++;
        }
        else {
            // 交换到大于区
            student_t tmp = arr[j];
            arr[j] = arr[k + 1];
            arr[k + 1] = tmp;
            j--;
        }
    }

    // 把 pivot 放到小于区末尾
    student_t tmp = arr[left];
    arr[left] = arr[i];
    arr[i] = tmp;
    i--;

    *start_p = i + 1;
    *end_p   =     k;
}

/**
 * @brief 快速排序
 * 
 * @param arr     数组指针
 * @param left    数组起始索引
 * @param right   数组结束索引
 */
void quick_sort(student_t arr[], int left, int right)
{
    if (left >= right) {
        return;
    }

    int eq_start;
    int   eq_end;

    three_way_partition(arr, left, right, &eq_start, &eq_end);

    quick_sort(arr, left, eq_start - 1);
    quick_sort(arr, eq_end + 1,  right);
}

/**
 * @brief 对学生列表按按照绩点和学号升序排序
 * 
 * @param sl 列表指针
 */
void sort_students(student_list_t *sl)
{
    if (sl->length == 0) {
        return;
    }

    quick_sort(sl->students, 0, sl->length - 1);
}

int main()
{
    student_list_t list;
    list_init(&list);

    student_t s1 = {101, "Alice",   "F", "CS", 1, 3.5};
    student_t s2 = {102, "Bob",     "M", "EE", 2, 3.2};
    student_t s3 = {103, "Charlie", "M", "CS", 1, 3.9};
    student_t s4 = {104, "Diana",   "F", "ME", 3, 3.5};
    student_t s5 = {105, "Eve",     "F", "CS", 1, 3.2};

    list.students[list.length++] = s1;
    list.students[list.length++] = s2;
    list.students[list.length++] = s3;
    list.students[list.length++] = s4;
    list.students[list.length++] = s5;

    printf("Before sorting:\r\n");
    show_students(&list);

    sort_students(&list);

    printf("\r\nAfter sorting:\r\n");
    show_students(&list);

    return 0;
}

2.4 任务四

假设每个班的同学都已按绩点排好序 (升序)，设计一个算法把该专业所有同学按绩点进行升序排序，要求算法复杂度为 $O(n)$。

因为各班成绩已经排好序，可以将每个班绩点最低的学生拿出来进行比较，找到年级绩点最低的学生并转到年级绩点排名顺序表中，如此循环，完成排序。

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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
#include <stdio.h>
#include <stdlib.h>

#define MAX 1001

/* 学生数据结构体 */
typedef struct student_s {
    int         id;  // 学号
    char  name[88];  // 名称
    char gender[8];  // 性别
    char major[88];  // 专业
    int      class;  // 班级
    double   grade;  // 绩点
} student_t;

typedef struct student_list_s {
    student_t students[MAX];
    int              length;
} student_list_t;

void list_init(student_list_t *sl)
{
    sl->length = 0;
}

void add_student(student_list_t *sl, int num)
{
    char line[256];

    for (int i = 0; i < num; i++) {
        if (fgets(line, sizeof(line), stdin) == NULL) {
            break;
        }

        student_t tmp;
        int matched = sscanf(line, "%d %87s %7s %87s %d %lf", 
                             &tmp.id, tmp.name, tmp.gender, 
                             tmp.major, &tmp.class, &tmp.grade);

        if (matched == 6) {
            sl->students[sl->length] = tmp;
            sl->length++;
        } else {
            continue;
        }
    }
}

void show_students(const student_list_t *sl)
{
    for (int i = 0; i < sl->length; i++) {
        printf("%d %s %s %s %d %.2lf\r\n", 
                sl->students[i].id, 
                sl->students[i].name, 
                sl->students[i].gender, 
                sl->students[i].major, 
                sl->students[i].class, 
                sl->students[i].grade);
    }
}

int get_student(const student_list_t sl, int idx, student_t *s)
{
    if (idx < 1 || idx > sl.length) {
        return -1;
    }

    *s = sl.students[idx - 1];
    return 0;
}

int insert_student(student_list_t *sl, int idx, student_t s)
{
    if (idx < 1 || idx > sl->length + 1) {
        return -1;
    }

    if (sl->length >= MAX) {
        return -1;
    }

    for (int j = sl->length - 1; j >= idx - 1; j--) {
        sl->students[j + 1] = sl->students[j];
    }

    sl->students[idx - 1] = s;
    sl->length++;
    return 0;
}

int delete_student(student_list_t *sl, int idx, student_t *s)
{
    if (idx < 1 || idx > sl->length) {
        return -1;
    }

    *s = sl->students[idx - 1];

    for (int j = idx; j < sl->length; j++) {
        sl->students[j - 1] = sl->students[j];
    }

    sl->length--;
    return 0;
}

/**
 * @brief 合并多个已按绩点升序排列的班级, 得到全专业按绩点升序的列表
 * 
 * @param classes 班级列表数组
 * @param num     班级数量
 * @param major   存放合并后的有序学生列表
 */
void merge_classes(const student_list_t classes[], int num, student_list_t *major)
{
    // 记录每个班级当前已取到的位置
    if (num > MAX) {
        return;
    }

    int pos[MAX];
    for (int i = 0; i < num; ++i) {
        pos[i] = 0;
    }

    int done = 0;
    while (!done) {
        int best_class = -1;
        double best_grade = 0.0;

        // 遍历所有班级, 找出当前绩点最小的学生
        for (int i = 0; i < num; ++i) {
            if (pos[i] < classes[i].length) {
                double cur_grade = classes[i].students[pos[i]].grade;
                if (best_class == -1 || cur_grade < best_grade) {
                    best_grade = cur_grade;
                    best_class = i;
                }
            }
        }

        if (best_class == -1) {
            // 所有班级都已处理完毕
            done = 1;
        } else {
            // 将找到的最小绩点学生加入结果列表
            int idx = pos[best_class];
            major->students[major->length] = classes[best_class].students[idx];
            major->length++;
            pos[best_class]++;
        }
    }
}

int main()
{
    student_list_t c1, c2, c3, major;

    list_init(&c1);
    list_init(&c2);
    list_init(&c3);
    list_init(&major);

    // 班级 1: 已按绩点升序排列
    c1.students[c1.length++] = (student_t){1001, "Alice", "F", "CS", 1, 2.3};
    c1.students[c1.length++] = (student_t){1002, "Bob",   "M", "CS", 1, 3.1};
    c1.students[c1.length++] = (student_t){1003, "Cindy", "F", "CS", 1, 3.9};

    // 班级 2: 已按绩点升序排列
    c2.students[c2.length++] = (student_t){2001, "David", "M", "CS", 2, 1.8};
    c2.students[c2.length++] = (student_t){2002, "Eve",   "F", "CS", 2, 2.6};
    c2.students[c2.length++] = (student_t){2003, "Frank", "M", "CS", 2, 4.0};

    // 班级 3: 已按绩点升序排列
    c3.students[c3.length++] = (student_t){3001, "Grace", "F", "CS", 3, 2.0};
    c3.students[c3.length++] = (student_t){3002, "Hank",  "M", "CS", 3, 3.3};

    student_list_t classes[3] = {c1, c2, c3};

    merge_classes(classes, 3, &major);

    printf("After sorting:\r\n");
    show_students(&major);

    return 0;
}

2.5 任务五

假设学生信息按学号顺序存储，设计一个按学号查询绩点的算法，要求算法复杂度为 $O(log N)$。

因为要求时间复杂度为 $O(log N)$，所以采用二分搜索算法。

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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
#include <stdio.h>
#include <stdlib.h>

#define MAX 1001

/* 学生数据结构体 */
typedef struct student_s {
    int         id;  // 学号
    char  name[88];  // 名称
    char gender[8];  // 性别
    char major[88];  // 专业
    int      class;  // 班级
    double   grade;  // 绩点
} student_t;

typedef struct student_list_s {
    student_t students[MAX];
    int              length;
} student_list_t;

void list_init(student_list_t *sl)
{
    sl->length = 0;
}

void add_student(student_list_t *sl, int num)
{
    char line[256];

    for (int i = 0; i < num; i++) {
        if (fgets(line, sizeof(line), stdin) == NULL) {
            break;
        }

        student_t tmp;
        int matched = sscanf(line, "%d %87s %7s %87s %d %lf", 
                             &tmp.id, tmp.name, tmp.gender, 
                             tmp.major, &tmp.class, &tmp.grade);

        if (matched == 6) {
            sl->students[sl->length] = tmp;
            sl->length++;
        } else {
            continue;
        }
    }
}

void show_students(const student_list_t *sl)
{
    for (int i = 0; i < sl->length; i++) {
        printf("%d %s %s %s %d %.2lf\r\n", 
                sl->students[i].id, 
                sl->students[i].name, 
                sl->students[i].gender, 
                sl->students[i].major, 
                sl->students[i].class, 
                sl->students[i].grade);
    }
}

int get_student(const student_list_t sl, int idx, student_t *s)
{
    if (idx < 1 || idx > sl.length) {
        return -1;
    }

    *s = sl.students[idx - 1];
    return 0;
}

int insert_student(student_list_t *sl, int idx, student_t s)
{
    if (idx < 1 || idx > sl->length + 1) {
        return -1;
    }

    if (sl->length >= MAX) {
        return -1;
    }

    for (int j = sl->length - 1; j >= idx - 1; j--) {
        sl->students[j + 1] = sl->students[j];
    }

    sl->students[idx - 1] = s;
    sl->length++;
    return 0;
}

int delete_student(student_list_t *sl, int idx, student_t *s)
{
    if (idx < 1 || idx > sl->length) {
        return -1;
    }

    *s = sl->students[idx - 1];

    for (int j = idx; j < sl->length; j++) {
        sl->students[j - 1] = sl->students[j];
    }

    sl->length--;
    return 0;
}

/**
 * @brief 使用二分搜索按学号查询绩点
 * 
 * @param sl 学生顺序表
 * @param id 待查询的学号
 * @param grade 保存查到的绩点
 * @return int 0->存在, -1->未存在
 */
int search_grade_by_id(const student_list_t *sl, int id, double *grade)
{
    int low = 0;
    int high = sl->length - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (sl->students[mid].id == id) {
            *grade = sl->students[mid].grade;
            return 0;
        } else if (sl->students[mid].id < id) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return -1;
}

int main()
{
    student_list_t list;
    double grade;
    int id;

    list_init(&list);

    student_t data[] = {
        {2021001, "Alice", "F", "CS", 1, 3.80},
        {2021002, "Bob",   "M", "CS", 1, 3.52},
        {2021003, "Carol", "F", "CS", 2, 3.91},
        {2021004, "David", "M", "CS", 2, 3.45},
        {2021005, "Eve",   "F", "CS", 3, 3.77},
    };
    int n = sizeof(data) / sizeof(data[0]);

    for (int i = 0; i < n; i++) {
        insert_student(&list, list.length + 1, data[i]);
    }

    printf("All students information:\r\n");
    show_students(&list);

    // 查询存在的学号
    id = 2021003;
    if (search_grade_by_id(&list, id, &grade) == 0) {
        printf("ID: %d, Grade: %.2lf.\r\n", id, grade);
    } else {
        printf("Failed to find id: %d.\r\n", id);
    }

    // 查询不存在的学号
    id = 2021000;
    if (search_grade_by_id(&list, id, &grade) == 0) {
        printf("ID: %d, Grade: %.2lf.\r\n", id, grade);
    } else {
        printf("Failed to find id: %d.\r\n", id);
    }

    // 查询最小边界学号
    id = 2021001;
    if (search_grade_by_id(&list, id, &grade) == 0) {
        printf("ID: %d, Grade: %.2lf.\r\n", id, grade);
    } else {
        printf("Failed to find id: %d.\r\n", id);
    }

    // 查询最大边界学号
    id = 2021005;
    if (search_grade_by_id(&list, id, &grade) == 0) {
        printf("ID: %d, Grade: %.2lf.\r\n", id, grade);
    } else {
        printf("Failed to find id: %d.\r\n", id);
    }

    return 0;
}

2.6 任务六

假设学生信息按学号顺序存储，设计一个查询某个绩点都有那些学生的算法，给出算法的复杂度分析。

因为学生信息采用顺序表储存，可以采用直接查找的方式找出相同绩点的学生。时间复杂度和空间复杂度均为 $O(n)$。

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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAX 1001
#define EPS 1e-9

/* 学生数据结构体 */
typedef struct student_s {
    int         id;  // 学号
    char  name[88];  // 名称
    char gender[8];  // 性别
    char major[88];  // 专业
    int      class;  // 班级
    double   grade;  // 绩点
} student_t;

typedef struct student_list_s {
    student_t students[MAX];
    int              length;
} student_list_t;

void list_init(student_list_t *sl)
{
    sl->length = 0;
}

void add_student(student_list_t *sl, int num)
{
    char line[256];

    for (int i = 0; i < num; i++) {
        if (fgets(line, sizeof(line), stdin) == NULL) {
            break;
        }

        student_t tmp;
        int matched = sscanf(line, "%d %87s %7s %87s %d %lf", 
                             &tmp.id, tmp.name, tmp.gender, 
                             tmp.major, &tmp.class, &tmp.grade);

        if (matched == 6) {
            sl->students[sl->length] = tmp;
            sl->length++;
        } else {
            continue;
        }
    }
}

void show_students(const student_list_t *sl)
{
    for (int i = 0; i < sl->length; i++) {
        printf("%d %s %s %s %d %.2lf\r\n", 
                sl->students[i].id, 
                sl->students[i].name, 
                sl->students[i].gender, 
                sl->students[i].major, 
                sl->students[i].class, 
                sl->students[i].grade);
    }
}

int get_student(const student_list_t sl, int idx, student_t *s)
{
    if (idx < 1 || idx > sl.length) {
        return -1;
    }

    *s = sl.students[idx - 1];
    return 0;
}

int insert_student(student_list_t *sl, int idx, student_t s)
{
    if (idx < 1 || idx > sl->length + 1) {
        return -1;
    }

    if (sl->length >= MAX) {
        return -1;
    }

    for (int j = sl->length - 1; j >= idx - 1; j--) {
        sl->students[j + 1] = sl->students[j];
    }

    sl->students[idx - 1] = s;
    sl->length++;
    return 0;
}

int delete_student(student_list_t *sl, int idx, student_t *s)
{
    if (idx < 1 || idx > sl->length) {
        return -1;
    }

    *s = sl->students[idx - 1];

    for (int j = idx; j < sl->length; j++) {
        sl->students[j - 1] = sl->students[j];
    }

    sl->length--;
    return 0;
}

/**
 * @brief 查询绩点等于指定值的学生
 * 
 * @param sl    学生顺序表
 * @param grade 目标绩点
 * @param out   保存匹配的学生
 * @return int 匹配的学生数量
 */
int search_students_by_grade(const student_list_t *sl, double grade, student_t out[])
{
    int count = 0;

    for (int i = 0; i < sl->length; i++) {
        if (fabs(sl->students[i].grade - grade) < EPS) {
            out[count++] = sl->students[i];
        }
    }

    return count;
}

int main()
{
    student_list_t list;
    student_t result[MAX];
    double target;
    int count;

    list_init(&list);

    student_t data[] = {
        {2021001, "Alice", "F", "CS", 1, 3.80},
        {2021002, "Bob",   "M", "CS", 1, 3.52},
        {2021003, "Carol", "F", "CS", 2, 3.91},
        {2021004, "David", "M", "CS", 2, 3.45},
        {2021005, "Eve",   "F", "CS", 3, 3.77},
        {2021006, "Frank", "M", "CS", 3, 3.80},
    };
    int n = sizeof(data) / sizeof(data[0]);

    for (int i = 0; i < n; i++) {
        insert_student(&list, list.length + 1, data[i]);
    }

    printf("All students information:\r\n");
    show_students(&list);

    target = 3.80;
    count = search_students_by_grade(&list, target, result);
    printf("\r\nStudents with grade %.2lf (%d found):\r\n", target, count);
    for (int i = 0; i < count; i++) {
        printf("%d %s %s %s %d %.2lf\r\n",
               result[i].id, result[i].name, result[i].gender,
               result[i].major, result[i].class, result[i].grade);
    }

    target = 3.91;
    count = search_students_by_grade(&list, target, result);
    printf("\r\nStudents with grade %.2lf (%d found):\r\n", target, count);
    for (int i = 0; i < count; i++) {
        printf("%d %s %s %s %d %.2lf\r\n",
               result[i].id, result[i].name, result[i].gender,
               result[i].major, result[i].class, result[i].grade);
    }

    target = 3.99;
    count = search_students_by_grade(&list, target, result);
    printf("\r\nStudents with grade %.2lf (%d found):\r\n", target, count);
    for (int i = 0; i < count; i++) {
        printf("%d %s %s %s %d %.2lf\r\n",
               result[i].id, result[i].name, result[i].gender,
               result[i].major, result[i].class, result[i].grade);
    }

    return 0;
}

3. 物流配送路径规划问题

自 2004 年开始，网络购物作为时代的产物不断改变着人们的购物方式，成为生活必不可少的一部分。如图 3-1 所示，截至 2021 年 12 月，中国网购用户已达 8.4 亿人。当我们在享受网络购物便利性的同时，不得不承认快递物流起到的重要作用。消费者选购的商品从商家仓库出发，基于物流系统寄往全国各地，3 至 5 天即可到达消费者手中，享受在家“逛商场”的便利。

但是从 2019 年开始，新冠疫情反复多点爆发，中高风险区为控制疫情外泄风险，出台交通管制政策，因此“封路+停运”成为了物流面临的常态化问题。如图 3-2 所示，截至 5 月 23 日，引自“中国邮政速递物流”网，受疫情管控措施影响，多达 40 多个城市网点收寄业务遭到停发或时效风险。在后疫情背景下，物流系统经过两年多的发展，逐渐成熟，“中心仓+云仓分仓”经营模式应运而生，即：商家可以将库存交给拥有智慧云仓的物流服务商，建立多级的仓储体系，及时进行智慧调拨，云仓多仓发货，不仅快速高效，而且在后疫情时代帮助商家有效降低依靠商家单一仓储带来的停发风险，保障了全国物流系统的稳定运行。目前我国如京东云仓，菜鸟云仓，中通云仓等发展迅速，图 3-3 展示中通云仓科技在全国范围内覆盖的 60 个仓库，实现全国多仓库智慧发货。

请运用数据结构知识，从以下几个方面思考并分析疫情管控期间全国多仓发货是如何降低电商物流受阻乃至停发风险的？

所用参数说明：城市数量 n，疫情管控城市数量 m，全国云仓发货仓数量 t，要求：n≥𝟏𝟎，m≥𝟑，t≥𝟑。

3.1 任务一

传统商家单一仓发货模式下，物流如何规划最短路径将商品送达。

测试数据：顶点数 10 个，边数 20 条。

边的权值：

1
2
3
4
[0][1] = 1; [0][2] = 5; [1][2] = 3;  [1][3] = 7; [1][4] = 5;
[2][4] = 1; [2][5] = 7; [3][4] = 2;  [3][6] = 3; [4][5] = 3;
[4][6] = 6; [4][7] = 9; [4][9] = 7;  [5][7] = 5; [5][8] = 3;
[6][7] = 2; [6][8] = 7; [6][9] = 10; [7][8] = 4; [7][9] = 3;

实例输出结果：商家仓 a 到买家 e 的最短路径长度为 12。

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
#include <stdio.h>
#include <stdlib.h>

#define MAX 50
#define GRAPH_MAX 3000

typedef struct graph_s {
    int    vertex[MAX];  // 顶点
    int side[MAX][MAX];  // 边
    int     vertex_num;  // 顶点数
    int       side_num;  // 边数
} graph_t;

void create_graph(graph_t *graph)
{
    int i, j;

    // 储存边数和结点数
    graph->side_num = 20;
    graph->vertex_num = 10;

    for (i = 0; i < graph->vertex_num; i++) {
        graph->vertex[i] = i;
    }

    for (i = 0; i < graph->vertex_num; i++) {
        for (j = 0; j < graph->vertex_num; j++) {
            if (i == j) {
                graph->side[i][j] = 0;
            } else {
                graph->side[i][j] = graph->side[j][i] = GRAPH_MAX;
            }
        }
    }

    // 储存边的权值
    graph->side[0][1] = 1;
    graph->side[0][2] = 5;
    graph->side[1][2] = 3;
    graph->side[1][3] = 7;
    graph->side[1][4] = 5;

    graph->side[2][4] = 1;
    graph->side[2][5] = 7;
    graph->side[3][4] = 2;
    graph->side[3][6] = 3;
    graph->side[4][5] = 3;

    graph->side[4][6] = 6;
    graph->side[4][7] = 9;
    graph->side[4][9] = 7;
    graph->side[5][7] = 5;
    graph->side[5][8] = 3;

    graph->side[6][7] = 2;
    graph->side[6][8] = 7;
    graph->side[6][9] = 10;
    graph->side[7][8] = 4;
    graph->side[7][9] = 3;

    for (i = 0; i < graph->vertex_num; i++) {
        for (j = i; j < graph->vertex_num; j++) {
            graph->side[j][i] = graph->side[i][j];
        }
    }
}

/**
 * @brief 使用 Dijkstra 算法求单源最短路径
 * 
 * @param graph  图
 * @param source 源点
 * @param prev   前驱数组, prev[i] 记录顶点 i 在最短路径上的前驱
 * @param dist   距离数组, dist[i] 记录源点到顶点 i 的最短距离
 */
void short_path(graph_t graph, int source, int prev[], int dist[])
{
    int i, j;
    int k, min;
    int final[MAX];

    for (i = 0; i < graph.vertex_num; i++) {
        final[i] = 0;
        dist[i] = graph.side[source][i];
        prev[i] = -1;
    }

    dist[source] = 0;
    final[source] = 1;

    for (i = 1; i < graph.vertex_num; i++) {
        min = GRAPH_MAX;
        k = -1;

        for (j = 0; j < graph.vertex_num; j++) {
            if (!final[j] && dist[j] < min) {
                k = j;
                min = dist[j];
            }
        }

        if (k == -1) {
            // 剩余顶点均不可达
            break;
        }

        final[k] = 1;

        for (j = 0; j < graph.vertex_num; j++) {
            if (!final[j] && (min + graph.side[k][j] < dist[j])) {
                dist[j] = min + graph.side[k][j];
                prev[j] = k;
            }
        }
    }
}

int main()
{
    int source = 0;
    graph_t graph;
    int prev[MAX];
    int dist[MAX];

    create_graph(&graph);
    short_path(graph, source, prev, dist);

    printf("商家仓 a 到买家 e 的最短路径长度为: %d\r\n", dist[9]);

    return 0;
}

3.2 任务二

传统商家单一仓发货模式下，若最短路径中有道路管控，如何选取不含该管控点的最短路径。

1
// 欸嘿, 没写捏, 自己试试吧?

3.3 任务三

全国多仓发货模式下，如何智慧选取发货仓，并构建最短路径将商品送达。

1
// 欸嘿, 没写捏, 自己试试吧?

附录

  1. 文件列表

    • 2022年-数据结构-大作业.pdf

  2. 下载地址

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