3. 图综合练习–构建邻接表
题目描述
已知一有向图，构建该图对应的邻接表。
邻接表包含数组和单链表两种数据结构，其中每个数组元素也是单链表的头结点，数组元素包含两个属性，属性一是顶点编号info，属性二是指针域next指向与它相连的顶点信息。
单链表的每个结点也包含两个属性，属性一是顶点在数组的位置下标，属性二是指针域next指向下一个结点。
输入
第1行输入整数t，表示有t个图
第2行输入n和k，表示该图有n个顶点和k条弧。
第3行输入n个顶点。
第4行起输入k条弧的起点和终点，连续输入k行
以此类推输入下一个图
输出
输出每个图的邻接表，每行输出格式：数组下标 顶点编号-连接顶点下标-…-^，数组下标从0开始。
具体格式请参考样例数据，每行最后加入“^”表示NULL。
输入样例
1
5 7
A B C D E
A B
A D
A E
B D
C B
C E
E D
输出样例
0 A-1-3-4-^
1 B-3-^
2 C-1-4-^
3 D-^
4 E-3-^
参考代码
#include <iostream> using namespace std; class Node { public: int pos; Node *next; Node() : next(NULL){}; Node(int t) : pos(t), next(NULL){}; }; class Map { public: int Vexnum; Node *head; char *Vex; int index(char c) { for (int i = 0; i < Vexnum; i++) { if (c == Vex[i]) return i; } return -1; } Map(int n, int k) { Vexnum = n; Vex = new char[Vexnum]; head = new Node[Vexnum]; for (int i = 0; i < n; i++) { cin >> Vex[i]; } for (int i = 0; i < k; i++) { char c1, c2; cin >> c1 >> c2; int num1 = index(c1), num2 = index(c2); Node *p = &head[num1]; while (p->next) p = p->next; Node *p1 = new Node(); p1->pos = num2; p->next = p1; } } ~Map() { delete[] Vex; for (int i = 0; i < Vexnum; i++) { Node *p = head[i].next; while (p) { Node *p1 = p; p = p->next; delete p1; } } delete[] head; } void display() { for (int i = 0; i < Vexnum; i++) { cout << i << " " << Vex[i]; Node *p = head[i].next; while (p) { cout << "-" << p->pos; p = p->next; } cout << "-^" << endl; } } }; int main() { int t; cin >> t; while (t--) { int n, k; cin >> n >> k; Map m(n, k); m.display(); } }
4. DS图—图的邻接矩阵存储及度计算
题目描述
假设图用邻接矩阵存储。输入图的顶点信息和边信息，完成邻接矩阵的设置，并计算各顶点的入度、出度和度，并输出图中的孤立点（度为0的顶点）
–程序要求–
若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio
程序中若include多过一个头文件，不看代码，作0分处理
不允许使用第三方对象或函数实现本题的要求
输入
测试次数T，每组测试数据格式如下：
图类型 顶点数 （D—有向图，U—无向图）
顶点信息
边数
每行一条边（顶点1 顶点2）或弧（弧尾 弧头）信息
输出
每组测试数据输出如下信息（具体输出格式见样例）：
图的邻接矩阵
按顶点信息输出各顶点的度（无向图）或各顶点的出度 入度 度（有向图）。孤立点的度信息不输出。
图的孤立点。若没有孤立点，不输出任何信息。
输入样例
2
D 5
V1 V2 V3 V4 V5
7
V1 V2
V1 V4
V2 V3
V3 V1
V3 V5
V4 V3
V4 V5
U 5
A B C D E
5
A B
A C
B D
D C
A D
输出样例
0 1 0 1 0
0 0 1 0 0
1 0 0 0 1
0 0 1 0 1
0 0 0 0 0
V1: 2 1 3
V2: 1 1 2
V3: 2 2 4
V4: 2 1 3
V5: 0 2 2
0 1 1 1 0
1 0 0 1 0
1 0 0 1 0
1 1 1 0 0
0 0 0 0 0
A: 3
B: 2
C: 2
D: 3
E
参考代码
#include <iostream> using namespace std; class Node { public: int in = 0, out = 0, total = 0; void inadd() { in++; total++; } void outadd() { out++; total++; } }; class Map { public: int Vexnum; char type; Node *head; string *Vex; int **Matrix; int index(string c) { for (int i = 0; i < Vexnum; i++) { if (c == Vex[i]) return i; } } Map(int n, char t) { Vexnum = n; type = t; Vex = new string[Vexnum]; Matrix = new int *[Vexnum]; for (int i = 0; i < Vexnum; i++) Matrix[i] = new int[Vexnum]; head = new Node[Vexnum]; for (int i = 0; i < Vexnum; i++) { cin >> Vex[i]; } for (int i = 0; i < Vexnum; i++) for (int j = 0; j < Vexnum; j++) { Matrix[i][j] = 0; } int k; cin >> k; while (k--) { string c1, c2; cin >> c1 >> c2; int num1 = index(c1), num2 = index(c2); head[num1].outadd(); head[num2].inadd(); if (type == 'U') { Matrix[num1][num2] = 1; Matrix[num2][num1] = 1; } else if (type == 'D') { Matrix[num1][num2] = 1; } } } ~Map() { delete[] Vex; delete[] head; for (int i = 0; i < Vexnum;i++) delete[] Matrix[i]; delete[] Matrix; } void display() { for (int i = 0; i < Vexnum; i++) for (int j = 0; j < Vexnum; j++) { cout << Matrix[i][j]; if (j != Vexnum - 1) cout << " "; if (j == Vexnum - 1) cout << endl; } for (int i = 0; i < Vexnum; i++) { cout << Vex[i]; if (head[i].total != 0) { cout << ":"; if (type == 'D') { cout << " " << head[i].out << " " << head[i].in << " " << head[i].total; } else if (type == 'U') { cout << " " << head[i].total; } } cout << endl; } } }; int main() { int t; cin >> t; while (t--) { char c; int k; cin >> c >> k; Map m(k, c); m.display(); } }
5. DS图—图非0面积
题目描述
编程计算由"1"围成的下列图形的面积。面积计算方法是统计"1"所围成的闭合曲线中"0"点的数目。如图所示，在10*10的二维数组中，"1"围住了15个点，因此面积为15。
输入
测试次数t
每组测试数据格式为：
数组大小m,n
一个由0和1组成的m*n的二维数组
输出
对每个二维数组，输出符号"1"围住的"0"的个数，即围成的面积。假设一定有1组成的闭合曲线，但不唯一。
输入样例
2
10 10
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 1 0 0 1 0
0 0 1 0 0 0 1 0 1 0
0 1 0 1 0 1 0 0 1 0
0 1 0 0 1 1 0 1 1 0
0 0 1 0 0 0 0 1 0 0
0 0 0 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0
5 8
0 1 1 0 0 1 1 0
1 0 1 0 1 0 0 1
0 1 0 1 0 0 1 0
0 1 0 0 1 1 1 0
0 0 0 0 0 0 0 0
输出样例
15
5
参考代码
#include <iostream> #include <queue> using namespace std; int n, m; int nx[4] = {0, 0, 1, -1}; int ny[4] = {1, -1, 0, 0}; void bfs(int M[40][40], queue<int> x, queue<int> y, int a, int b) { x.push(a); y.push(b); while (!x.empty()) { for (int i = 0; i < 4; i++) { if (x.front() + nx[i] <= n && x.front() + nx[i] >= 0 && y.front() + ny[i] <= m && y.front() + ny[i] >= 0 && M[x.front() + nx[i]][y.front() + ny[i]] == 0) { x.push(x.front() + nx[i]); y.push(y.front() + ny[i]); M[x.front() + nx[i]][y.front() + ny[i]] = 1; } } x.pop(); y.pop(); } } int main() { int T; cin >> T; while (T--) { int M[40][40] = {0}; queue<int> x; queue<int> y; int num = 0; cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cin >> M[i][j]; bfs(M, x, y, 0, 0); for (int i = 0; i <= n; i++) { for (int j = 0; j <= m; j++) { if (M[i][j] == 0) { num++; } } } cout << num << endl; } return 0; }
