GDPU 数据结构天码行空11

文章目录

数据结构实验十一图的创建与存储
- 一、实验目的
- 二、实验内容
- 三、【实验源代码】
- - 🍻 CPP版
  - 🍻 c 语言版
  - 🍻 java版
- 四、【实验结果】
- 五、【实验总结】

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

一、实验目的

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; // 设置节点数为6
	char 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; // 设置节点数为6
    char 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();

	}
}