GDPU 数据结构 天码行空11

数据结构实验十一 图的创建与存储

一、实验目的

1、 理解图的存储结构与基本操作；
2、 掌握图的创建过程

二、实验内容

1.请把下图以邻接矩阵的结构存储，并打印输出此邻接矩阵。
图的创建代码参考教材例题.
提示:首先构建图的逻辑模型，得出该图的顶点集和边集，调用相应的函数生成图的邻接矩阵，并打印出邻接矩阵。
2.用邻接表存储上图，并输出邻接表。（此题为选做）

三、【实验源代码】

🍻 CPP版

#include<iostream>
using namespace std;const int MAX_N = 6;
const int MAX_M = 6 * 5;int g[MAX_N][MAX_N]; // 邻接矩阵
int h[MAX_N], e[MAX_M], w[MAX_M], ne[MAX_M]; // 邻接表
int n = 6, m = 0, idx = 0; // n为节点数，m为边数，idx为邻接表中下一条边的索引void add(int a, int b, int c)
{// 邻接矩阵加边g[a][b] = c;// 邻接表加边 (头插法)e[idx] = b; // b表示当前边的终点w[idx] = c; // c表示当前边的权值ne[idx] = h[a]; // h[a]表示节点a的第一条边在邻接表中的位置，ne[idx]表示a节点的下一条边在邻接表中的位置h[a] = idx++; // 更新节点a的第一条边的位置
}void init()
{// A B C D E F// 0 1 2 3 4 5// 初始化邻接表的头结点for (int i = 0; i < n; i++)h[i] = -1;// 加边add(1, 0, 2);add(2, 1, 15);add(0, 2, 5);add(0, 3, 30);add(2, 5, 7);add(1, 4, 8);add(4, 3, 4);add(5, 3, 10);add(5, 4, 18);
}void print()
{// 输出邻接矩阵cout << "输出邻接矩阵:" << endl;cout << "   A  B  C  D  E  F" << endl;char c = 'A';for (int i = 0; i < n; i++){cout << c++ << "  ";for (int j = 0; j < n; j++)printf("%-2d ",g[i][j]);
//          cout << g[i][j] << " ";cout << endl;}// 输出邻接表cout << "\n	输出邻接表:" << endl;for (int i = 0; i < n; i++){cout << (char)('A' + i); // 输出当前节点的名称int x = h[i]; // 获取当前节点的第一条边在邻接表中的位置while (x != -1){cout << " --[" << w[x] << "]--> " << (char)('A' + e[x]); // 输出当前边的权值和终点x = ne[x]; // 移动到下一条边}cout << endl;}
}int main()
{n = 6; // 设置节点数为6char nodes[] = { 'A', 'B', 'C', 'D', 'E', 'F' }; // 节点名称init(); // 初始化图print(); // 输出邻接矩阵和邻接表return 0;
}

🍻 c 语言版

#include <stdio.h>#define MAX_N 6
#define MAX_M (6 * 5)int g[MAX_N][MAX_N]; // 邻接矩阵
int h[MAX_N], e[MAX_M], w[MAX_M], ne[MAX_M]; // 邻接表
int n = 6, m = 0, idx = 0; // n为节点数，m为边数，idx为邻接表中下一条边的索引void add(int a, int b, int c)
{// 邻接矩阵加边g[a][b] = c;// 邻接表加边 (头插法)e[idx] = b; // b表示当前边的终点w[idx] = c; // c表示当前边的权值ne[idx] = h[a]; // h[a]表示节点a的第一条边在邻接表中的位置，ne[idx]表示a节点的下一条边在邻接表中的位置h[a] = idx++; // 更新节点a的第一条边的位置
}void init()
{// A B C D E F// 0 1 2 3 4 5// 初始化邻接表的头结点for (int i = 0; i < n; i++)h[i] = -1;// 加边add(1, 0, 2);add(2, 1, 15);add(0, 2, 5);add(0, 3, 30);add(2, 5, 7);add(1, 4, 8);add(4, 3, 4);add(5, 3, 10);add(5, 4, 18);
}void print()
{// 输出邻接矩阵printf("输出邻接矩阵:\n");printf("   A  B  C  D  E  F\n");char c = 'A';for (int i = 0; i < n; i++){printf("%c  ", c++);for (int j = 0; j < n; j++)printf("%-2d ", g[i][j]);printf("\n");}// 输出邻接表printf("\n	输出邻接表:\n");for (int i = 0; i < n; i++){printf("%c", (char)('A' + i)); // 输出当前节点的名称int x = h[i]; // 获取当前节点的第一条边在邻接表中的位置while (x != -1){printf(" --[%d]--> %c", w[x], (char)('A' + e[x])); // 输出当前边的权值和终点x = ne[x]; // 移动到下一条边}printf("\n");}
}int main()
{n = 6; // 设置节点数为6char nodes[] = { 'A', 'B', 'C', 'D', 'E', 'F' }; // 节点名称init(); // 初始化图print(); // 输出邻接矩阵和邻接表return 0;
}

🍻 java版

package 数据结构实验;public class 图的创建和存储
{static int[][] g;// （邻接矩阵）static int n = 6, m = 6 * 5, idx = 0;static int[] h = new int[n];static int[] e = new int[m];static int[] w = new int[m];static int[] ne = new int[m];static void add(int a, int b, int c){
//		邻接矩阵加边g[a][b] = c;
//		邻接表加边 (头插法)e[idx] = b;ne[idx] = h[a];w[idx] = c;h[a] = idx++;}static void init(){
//		A B C D E F
//		0 1 2 3 4 5
//		初始化邻接表的头结点for (int i = 0; i < n; i++)h[i] = -1;//		加边add(1, 0, 2);add(2, 1, 15);add(0, 2, 5);add(0, 3, 30);add(2, 5, 7);add(1, 4, 8);add(4, 3, 4);add(5, 3, 10);add(5, 4, 18);}static void print(){
//		输出邻接矩阵System.out.println("输出邻接矩阵:");// 表头System.out.println("   A  B  C  D  E  F");char c = 'A';for (int i = 0; i < n; i++){System.out.print(c++ + "  ");for (int j = 0; j < n; j++)System.out.printf("%-2d ", g[i][j]);System.out.println();}
//		输出邻接表System.out.println("\n输出邻接表:");for (int i = 0; i < n; i++){System.out.print((char) ('A' + i));int x = h[i];while (x != -1){System.out.print(" --" + w[x] + "--> " + (char) ('A' + e[x]));x = ne[x];}System.out.println();}}public static void main(String[] args){n = 6;char[] nodes = { 'A', 'B', 'C', 'D', 'E', 'F' };g = new int[n][n];init();print();}
}

四、【实验结果】

五、【实验总结】

balabala