数据结构 实验报告-4

1. 六度空间

1.1 实验内容

“六度空间”理论又称作“六度分隔（Six Degrees of Separation）”理论。这个理论可以通俗地阐述为：“你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过五个人你就能够认识任何一个陌生人”。

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
149
150
151
152
153
154
155
156
157
158
159
160
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 10005  // 最大顶点数

/* 邻接表节点, 表示无向边 */
typedef struct adj_node_s {
    int              vertex;
    struct adj_node_s *next;
} adj_node_t;

/* 图结构 */
typedef struct graph_s {
    int m;  //   边数
    int n;  // 顶点数

    adj_node_t **heads;  // 每个顶点的邻接链表头
} graph_t;

/* BFS 队列节点 */
typedef struct queue_node_s {
    int vertex;
    int  depth;
} queue_node_t;

/**
 * @brief 创建图
 * 
 * @param n     图顶点数量
 * @return graph_t* 图指针
 */
graph_t* create_graph(int n)
{
    graph_t *g = (graph_t *)malloc(sizeof(graph_t));

    g->n = n;
    g->heads = (adj_node_t **)malloc((n + 1) * sizeof(adj_node_t *));
    for (int i = 1; i <= n; i++) {
        g->heads[i] = NULL;
    }
    return g;
}

/**
 * @brief 添加无向边
 * 
 * @param g 图指针
 * @param u 顶点 1
 * @param v 顶点 2
 */
void add_edge(graph_t *g, int u, int v)
{
    // u -> v
    adj_node_t *node1 = (adj_node_t *)malloc(sizeof(adj_node_t));
    node1->vertex = v;
    node1->next = g->heads[u];
    g->heads[u] = node1;

    // v -> u
    adj_node_t *node2 = (adj_node_t *)malloc(sizeof(adj_node_t));
    node2->vertex = u;
    node2->next = g->heads[v];
    g->heads[v] = node2;
}

/**
 * @brief 释放图内存
 * 
 * @param g 图指针
 */
void free_graph(graph_t *g)
{
    for (int i = 1; i <= g->n; i++) {
        adj_node_t *cur = g->heads[i];

        while (cur) {
            adj_node_t *tmp = cur;
            cur = cur->next;
            free(tmp);
        }
    }

    free(g->heads);
    free(g);
}

/**
 * @brief BFS 统计距离 <= 6 的顶点数
 * 
 * @param g     图指针
 * @param start 顶点值
 * @return int  顶点数
 */
int bfs_count(graph_t *g, int start)
{
    // 记录每个顶点是否已经被访问过
    int visited[MAX] = { 0 };

    // 简单顺序队列
    queue_node_t queue[MAX * 6];
    int front = 0;
    int rear  = 0;

    // 符合标准的顶点数
    int count = 0;

    visited[start]     =     1;
    queue[rear].depth  =     0;
    queue[rear].vertex = start;
    rear++;

    while (front < rear) {
        queue_node_t cur = queue[front++];
        count++;

        if (cur.depth >= 6) {
            continue;
        }

        adj_node_t *adj = g->heads[cur.vertex];

        while (adj) {
            int v = adj->vertex;

            if (!visited[v]) {
                visited[v] = 1;
                queue[rear].vertex = v;
                queue[rear].depth = cur.depth + 1;
                rear++;
            }
            adj = adj->next;
        }
    }

    return count;
}

int main()
{
    int N;  // 顶点数
    int M;  //   边数
    scanf("%d %d", &N, &M);

    graph_t *g = create_graph(N);
    for (int i = 0; i < M; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        add_edge(g, u, v);
    }

    for (int i = 1; i <= N; i++) {
        int cnt = bfs_count(g, i);
        double percent = (cnt * 100.0) / N;
        printf("%d: %.2f%%\n", i, percent);
    }

    free_graph(g);
    return 0;
}

1.4 调试步骤

  1. 输入测试数据
1
2
3
4
5
6
7
8
9
10
10 9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
  1. 程序输出
1
2
3
4
5
6
7
8
9
10
1: 70.00%
2: 80.00%
3: 90.00%
4: 100.00%
5: 100.00%
6: 100.00%
7: 100.00%
8: 90.00%
9: 80.00%
10: 70.00%

1.5 分析与思考

设顶点数为 n，边数为 m。

  • 空间复杂度：$O(n \cdot (n + m))$

  • 时间复杂度：$O(n + 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
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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 10000

typedef struct family_s {
    int          id;  // 家庭最小编号
    int        size;  // 人口数
    double  avg_cnt;  // 人均房产套数
    double avg_area;  // 人均房产面积
} family_t;

int     parent[MAX];  // 并查集父节点
int      exist[MAX];  // 标记该人是否出现
int  house_cnt[MAX];  // 个人名下房产套数
int house_area[MAX];  // 个人名下房产总面积

int   total_cnt[MAX];  // 每个家庭的总房产套数
int  total_area[MAX];  // 每个家庭的总房产面积
int family_size[MAX];  // 每个家庭的人口数

/**
 * @brief 并查集查找, 带路径压缩
 * 
 * @param x 元素值
 * @return int 元素父节点
 */
int find(int x)
{
    if (parent[x] == x) {
        return x;
    } else {
        parent[x] = find(parent[x]);
        return parent[x];
    }
}

/**
 * @brief 合并时让编号较小的作为根，确保 最小编号 作为家庭代表
 * 
 * @param a A 元素
 * @param b B 元素
 */
void merge(int a, int b)
{
    if (a == -1 || b == -1) {
        return;
    }

    int ra = find(a);
    int rb = find(b);

    if (ra == rb) {
        return;
    }

    if (ra < rb) {
        parent[rb] = ra;
    } else {
        parent[ra] = rb;
    }
}

/**
 * @brief 家庭排序比较函数
 * 
 * @param a 指向第一个 family_t 元素的指针
 * @param b 指向第二个 family_t 元素的指针
 * @return int -1->a在b之前 | 0->相等 | 1->a在b之后
 */
int cmp(const void *a, const void *b)
{
    family_t *x = (family_t *)a;
    family_t *y = (family_t *)b;

    // 先按人均面积降序
    if (y->avg_area > x->avg_area) {
        return 1;
    }

    if (y->avg_area < x->avg_area) {
        return -1;
    }

    // 面积相同时按编号升序
    return (x->id - y->id);
}

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

    for (int i = 0; i < MAX; i++) {
        parent[i]     = i;
        exist[i]      = 0;
        house_cnt[i]  = 0;
        house_area[i] = 0;
    }

    for (int i = 0; i < n; i++) {
        int id, father, mother, k;
        scanf("%d %d %d %d", &id, &father, &mother, &k);
        exist[id] = 1;

        if (father != -1) {
            exist[father] = 1;
            merge(id, father);
        }

        if (mother != -1) {
            exist[mother] = 1;
            merge(id, mother);
        }

        int child;
        for (int j = 0; j < k; j++) {
            scanf("%d", &child);
            exist[child] = 1;
            merge(id, child);
        }

        scanf("%d %d", &house_cnt[id], &house_area[id]);
    }

    // 将每个人的房产累加到其家庭代表上
    memset(total_cnt,   0,   sizeof(total_cnt));
    memset(total_area,  0,  sizeof(total_area));
    memset(family_size, 0, sizeof(family_size));

    for (int i = 0; i < MAX; i++) {
        if (!exist[i]) {
            continue;
        }

        int root = find(i);
        total_cnt[root]   +=  house_cnt[i];
        total_area[root]  += house_area[i];
        family_size[root] +=             1;
    }

    // 收集所有家庭代表
    family_t families[MAX];
    int   family_count = 0;

    for (int i = 0; i < MAX; i++) {
        if (exist[i] && parent[i] == i) {
            families[family_count].id       = i;
            families[family_count].size     = family_size[i];
            families[family_count].avg_cnt  = (double)total_cnt[i] / family_size[i];
            families[family_count].avg_area = (double)total_area[i] / family_size[i];
            family_count++;
        }
    }

    qsort(families, family_count, sizeof(family_t), cmp);

    printf("%d\n", family_count);
    for (int i = 0; i < family_count; i++) {
        printf("%04d %d %.3f %.3f\n", 
               families[i].id, 
               families[i].size, 
               families[i].avg_cnt, 
               families[i].avg_area);
    }

    return 0;
}

2.4 调试步骤

  1. 输入测试数据
1
2
3
4
5
6
7
8
9
10
11
10
6666 5551 5552 1 7777 1 100
1234 5678 9012 1 0002 2 300
8888 -1 -1 0 1 1000
2468 0001 0004 1 2222 1 500
7777 6666 -1 0 2 300
3721 -1 -1 1 2333 2 150
9012 -1 -1 3 1236 1235 1234 1 100
1235 5678 9012 0 1 50
2222 1236 2468 2 6661 6662 1 300
2333 -1 3721 3 6661 6662 6663 1 100
  1. 程序输出
1
2
3
4
3
8888 1 1.000 1000.000
0001 15 0.600 100.000
5551 4 0.750 100.000

2.5 分析与思考

设人数上限为 MAX，输入记录数为 n。

  • 空间复杂度：$O(MAX \log MAX + n \cdot \alpha(MAX))$

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

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