devbox
繁依Fanyi0
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

[数据结构]：22-图（邻接矩阵）（C语言实现）_补齐代码,新建一个图,完成以下功能: (1)判断两个结点之间是否有边存在; (2)输入任

作者：繁依Fanyi0 | 2024-06-21 15:52:31

赞

踩

补齐代码,新建一个图,完成以下功能: (1)判断两个结点之间是否有边存在; (2)输入任

目录

前言

已完成内容

图实现

01-开发环境

02-文件布局

03-代码

01-主函数

02-头文件

03-AdjMatrixCommon.cpp

04-AdjMatrixFunction.cpp

结语

前言

        此专栏包含408考研数据结构全部内容，除其中使用到C++引用外，全为C语言代码。使用C++引用主要是为了简化指针的使用，避免二重指针的出现。

已完成内容

[数据结构]：01-顺序表（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：02-单链表（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：03-栈（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：04-循环队列（数组）（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：05-循环队列（链表）（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：06-队列（链表带头结点）（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：07-二叉树（无头结点）（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：08-顺序查找（顺序表指针实现形式）（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：09-二分查找（顺序表指针实现形式）（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：10-二叉排序树（无头结点）（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：11-冒泡排序（顺序表指针实现形式）（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：12-快速排序（顺序表指针实现形式）（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：13-插入排序（顺序表指针实现形式）（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：14-选择排序（顺序表指针实现形式）（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：15-堆排序（顺序表指针实现形式）（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：16-归并排序（顺序表指针实现形式）（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：17-双链表（带头结点）（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：18-链栈（不带头结点）（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：19-串KMP模式匹配（数组）（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：20-线索二叉树（无头结点）（C语言实现）_Chandni.的博客-CSDN博客

[数据结构]：21-并查集（数组）（C语言实现）_Chandni.的博客-CSDN博客

图实现

01-开发环境

        语言：C/C++14

        编译器：MinGW64

        集成开发环境：CLion2022.1.3

02-文件布局

        请在CLion集成开发环境中创建C++可执行程序，否则无法运行，原因上面已解释。

                        ​​​​​             

03-代码

01-主函数

        用于测试。

  1. // 默认为无向图，若为有向图或网，请适当修改
  2. #include "./Head/AdjMatrix.h"
  3. #include "./Source/AdjMatrixCommon.cpp"
  4. #include "./Source/AdjMatrixFunction.cpp"
  5.  
  6.  
  7. int main() {
  8.     AdjMGraph AdjMatrix;
  9.     InitGraph(AdjMatrix);
  10.     CreateGraph(AdjMatrix);
  11.     PrintGraph(AdjMatrix);
  12.     printf("VertexNum = %d,EdgeNum = %d\n", AdjMatrix.VexNum, AdjMatrix.EdgeNum);
  13.     printf("-----------------------------------\n");
  14.  
  15.     // 判断两结点是否存在某边
  16.     if (Adjacent(AdjMatrix, 0, 1)) {
  17.         printf("true\n");
  18.     } else {
  19.         printf("false\n");
  20.     }
  21.     if (Adjacent(AdjMatrix, 2, 3)) {
  22.         printf("true\n");
  23.     } else {
  24.         printf("false\n");
  25.     }
  26.     printf("VertexNum = %d,EdgeNum = %d\n", AdjMatrix.VexNum, AdjMatrix.EdgeNum);
  27.     printf("-----------------------------------\n");
  28.  
  29.     // 列出与x邻接的边
  30.     int Edge[MAXSIZE] = {-1, -1, -1, -1, -1};
  31.     Neighbors(AdjMatrix, 0, Edge);
  32.     for (int i = 0; Edge[i] != -1; i++) {
  33.         printf("%3d", Edge[i]);
  34.     }
  35.     printf("\n");
  36.     printf("VertexNum = %d,EdgeNum = %d\n", AdjMatrix.VexNum, AdjMatrix.EdgeNum);
  37.     printf("-----------------------------------\n");
  38.  
  39.     // 删除顶点
  40.     DeleteVertex(AdjMatrix, 0);
  41.     PrintGraph(AdjMatrix);
  42.     printf("VertexNum = %d,EdgeNum = %d\n", AdjMatrix.VexNum, AdjMatrix.EdgeNum);
  43.     printf("-----------------------------------\n");
  44.  
  45.     // 添加顶点
  46.     InsertVertex(AdjMatrix, 4);
  47.  
  48.     // 添加边
  49.     AddEdge(AdjMatrix, 1, 4);
  50.     PrintGraph(AdjMatrix);
  51.     printf("VertexNum = %d,EdgeNum = %d\n", AdjMatrix.VexNum, AdjMatrix.EdgeNum);
  52.     printf("-----------------------------------\n");
  53.  
  54.     // 删除边
  55.     RemoveEdge(AdjMatrix, 0, 1);
  56.     RemoveEdge(AdjMatrix, 1, 2);
  57.     PrintGraph(AdjMatrix);
  58.     printf("VertexNum = %d,EdgeNum = %d\n", AdjMatrix.VexNum, AdjMatrix.EdgeNum);
  59.     printf("-----------------------------------\n");
  60.  
  61.     // 寻找第一个邻接点
  62.     int Neighbor = FirstNeighbor(AdjMatrix, 1);
  63.     printf("FirstNeighbor = %d\n", Neighbor);
  64.     printf("VertexNum = %d,EdgeNum = %d\n", AdjMatrix.VexNum, AdjMatrix.EdgeNum);
  65.     printf("-----------------------------------\n");
  66.     // 寻找除4之外的下一个邻接点
  67.     Neighbor = NextNeighbor(AdjMatrix, 1, 4);
  68.     printf("FirstNeighbor = %d\n", Neighbor);
  69.     printf("VertexNum = %d,EdgeNum = %d\n", AdjMatrix.VexNum, AdjMatrix.EdgeNum);
  70.     printf("-----------------------------------\n");
  71.     return 0;
  72. }

02-头文件

        用于存储结构体和常量等。

  1. //
  2. // Created by 24955 on 2023-04-02.
  3. // 默认为无向图，若为有向图或网，请适当修改
  4. //
  5.  
  6. #ifndef INC_01_ADJACENTMATRIX_ADJMATRIX_H
  7. #define INC_01_ADJACENTMATRIX_ADJMATRIX_H
  8. // 头文件
  9. #include <stdio.h>
  10.  
  11. // 常量
  12. #define MAXSIZE 5
  13. typedef int VertexType;
  14. typedef int EdgeType;
  15.  
  16. // 结构体-邻接矩阵
  17. typedef struct {
  18.     VertexType Vex[MAXSIZE];
  19.     // 可采用压缩存储
  20.     EdgeType Edge[MAXSIZE][MAXSIZE];
  21.     int VexNum, EdgeNum;
  22. } AdjMGraph;
  23. #endif //INC_01_ADJACENTMATRIX_ADJMATRIX_H

03-AdjMatrixCommon.cpp

        用于存储初始化图、输出图等操作。

  1. //
  2. // Created by 24955 on 2023-04-02.
  3. // 默认为无向图，若为有向图或网，请适当修改
  4. //
  5. // 初始化图
  6. void InitGraph(AdjMGraph &AdjMatrix) {
  7.     // 初始化顶点
  8.     for (int i = 0; i < MAXSIZE; i++) {
  9.         AdjMatrix.Vex[i] = -1;
  10.     }
  11.     // 初始化边
  12.     for (int i = 0; i < MAXSIZE; i++) {
  13.         for (int j = 0; j < MAXSIZE; j++) {
  14.             AdjMatrix.Edge[i][j] = 0;
  15.         }
  16.     }
  17.     AdjMatrix.VexNum = 0;
  18.     AdjMatrix.EdgeNum = 0;
  19. }
  20.  
  21. // 创建图 - 主要方便测试，并非图的正确创建方式，应根据具体情况具体分析
  22. void CreateGraph(AdjMGraph &AdjMatrix) {
  23.     AdjMatrix.VexNum = 4;
  24.     for (int i = 0; i < AdjMatrix.VexNum; i++) {
  25.         AdjMatrix.Vex[i] = i;
  26.     }
  27.     // 无向图
  28.     AdjMatrix.Edge[0][1] = 1;
  29.     AdjMatrix.Edge[1][0] = 1;
  30.     AdjMatrix.Edge[0][3] = 1;
  31.     AdjMatrix.Edge[3][0] = 1;
  32.     AdjMatrix.Edge[1][2] = 1;
  33.     AdjMatrix.Edge[2][1] = 1;
  34.     AdjMatrix.EdgeNum = 3;
  35. }
  36.  
  37. // 输出邻接矩阵
  38. void PrintGraph(AdjMGraph AdjMatrix) {
  39.     for (int i = 0; i < MAXSIZE; i++) {
  40.         printf("%2d\t", AdjMatrix.Vex[i]);
  41.         for (int j = 0; j < MAXSIZE; j++) {
  42.             printf("%2d", AdjMatrix.Edge[i][j]);
  43.         }
  44.         printf("\n");
  45.     }
  46. }

04-AdjMatrixFunction.cpp

        用于存储图的基本操作。

  1. //
  2. // Created by 24955 on 2023-04-02.
  3. // 默认为无向图，若为有向图或网，请适当修改
  4. //
  5. // 获取元素下标
  6. int GetIndex(AdjMGraph AdjMatrix, VertexType x) {
  7.     /*
  8.      *  1. 获取元素真实下标*/
  9.     int xIndex = -1;
  10.     for (int i = 0; i < MAXSIZE; i++) {
  11.         if (AdjMatrix.Vex[i] == x) {
  12.             xIndex = i;
  13.             break;
  14.         }
  15.     }
  16.     return xIndex;
  17. }
  18.  
  19. // 判断图中是否存在边<x,y>
  20. bool Adjacent(AdjMGraph AdjMatrix, VertexType x, VertexType y) {
  21.     /*
  22.      *  1. 判断x->y是否存在边
  23.      *  2. 存在返回true*/
  24.     // 避免访问到不存在顶点
  25.     if (x >= MAXSIZE || y >= MAXSIZE) {
  26.         return false;
  27.     }
  28.     int xIndex = GetIndex(AdjMatrix, x);
  29.     int yIndex = GetIndex(AdjMatrix, y);
  30.     // 适用于无向图、有向图、网
  31.     if (AdjMatrix.Edge[xIndex][yIndex] != 0) {
  32.         return true;
  33.     }
  34.     return false;
  35. }
  36.  
  37. // 列出图中与顶点x邻接的边
  38. void Neighbors(AdjMGraph AdjMatrix, VertexType x, int *Edge) {
  39.     /*
  40.      * 1. 遍历x所在行
  41.      * 2. 用数组存储与之邻接的边另一个顶点*/
  42.     int xIndex = GetIndex(AdjMatrix, x);
  43.     // 未找到顶点x
  44.     if (xIndex == -1) {
  45.         return;
  46.     }
  47.     // 找到顶点x，统计x所在行
  48.     for (int i = 0, j = 0; i < MAXSIZE; i++) {
  49.         if (AdjMatrix.Edge[xIndex][i] != 0) {
  50.             Edge[j++] = AdjMatrix.Vex[i];
  51.         }
  52.     }
  53. }
  54.  
  55. // 插入顶点x
  56. void InsertVertex(AdjMGraph &AdjMatrix, VertexType x) {
  57.     /*
  58.      *  1. 插入，顶点个数+1*/
  59.     if (AdjMatrix.VexNum == MAXSIZE) {
  60.         return;
  61.     }
  62.     for (int i = 0; i < MAXSIZE; i++) {
  63.         if (AdjMatrix.Vex[i] == -1) {
  64.             AdjMatrix.Vex[i] = x;
  65.             break;
  66.         }
  67.     }
  68.     AdjMatrix.VexNum++;
  69. }
  70.  
  71. // 删除顶点x
  72. void DeleteVertex(AdjMGraph &AdjMatrix, VertexType x) {
  73.     /*
  74.      *  1. 清除顶点，并修改顶点个数
  75.      *  2. 清除边，并修改边个数*/
  76.     // 清除顶点,将其值设为-1表示该顶点为空
  77.     int xIndex = GetIndex(AdjMatrix, x);
  78.     AdjMatrix.Vex[xIndex] = -1;
  79.     AdjMatrix.VexNum--;
  80.     // 清除边
  81.     for (int i = 0; i < MAXSIZE; i++) {
  82.         if (AdjMatrix.Edge[xIndex][i]) {
  83.             AdjMatrix.EdgeNum--;
  84.             AdjMatrix.Edge[xIndex][i] = 0;
  85.             AdjMatrix.Edge[i][xIndex] = 0;
  86.         }
  87.     }
  88. }
  89.  
  90. // 添加边
  91. void AddEdge(AdjMGraph &AdjMatrix, VertexType x, VertexType y) {
  92.     /*
  93.      *  1. 获取顶点值实际下标
  94.      *  2. 插入边*/
  95.     int xIndex = GetIndex(AdjMatrix, x);
  96.     int yIndex = GetIndex(AdjMatrix, y);
  97.     if (xIndex == -1 || yIndex == -1) {
  98.         return;
  99.     }
  100.     // 添加边
  101.     AdjMatrix.Edge[xIndex][yIndex] = 1;
  102.     AdjMatrix.Edge[yIndex][xIndex] = 1;
  103.     AdjMatrix.EdgeNum++;
  104. }
  105.  
  106. // 删除边
  107. void RemoveEdge(AdjMGraph &AdjMatrix, VertexType x, VertexType y) {
  108.     /*
  109.      *  1. 获取顶点值实际下标
  110.      *  2. 删除边*/
  111.     int xIndex = GetIndex(AdjMatrix, x);
  112.     int yIndex = GetIndex(AdjMatrix, y);
  113.     if (xIndex == -1 || yIndex == -1) {
  114.         return;
  115.     }
  116.     // 删除边
  117.     AdjMatrix.Edge[xIndex][yIndex] = 0;
  118.     AdjMatrix.Edge[yIndex][xIndex] = 0;
  119.     AdjMatrix.EdgeNum--;
  120. }
  121.  
  122. // 寻找图中顶点x的第一个邻接点
  123. int FirstNeighbor(AdjMGraph AdjMatrix, VertexType x) {
  124.     /*
  125.      *  1. 寻找第一个不为0的值，并返回顶点值*/
  126.     int xIndex = GetIndex(AdjMatrix, x);
  127.     if (xIndex == -1) {
  128.         return -1;
  129.     }
  130.     for (int i = 0; i < MAXSIZE; i++) {
  131.         if (AdjMatrix.Edge[xIndex][i]) {
  132.             return AdjMatrix.Vex[i];
  133.         }
  134.     }
  135.     return -1;
  136. }
  137.  
  138. // 图的下一个邻接点-除y以外的下一个邻接点顶点号
  139. int NextNeighbor(AdjMGraph AdjMatrix, VertexType x, VertexType y) {
  140.     /*
  141.      *  1. 寻找y之后第一个不为0的值，并返回顶点值*/
  142.     int xIndex = GetIndex(AdjMatrix, x);
  143.     int yIndex = GetIndex(AdjMatrix, y);
  144.     if (xIndex == -1 || yIndex == -1) {
  145.         return -1;
  146.     }
  147.     // 寻找y之后的下一个邻接点
  148.     for (int i = yIndex + 1; i < MAXSIZE; i++) {
  149.         if (AdjMatrix.Edge[xIndex][i]) {
  150.             return AdjMatrix.Vex[i];
  151.         }
  152.     }
  153.     return -1;
  154. }

结语

        此博客主要用于408考研数据结构C语言实现记录，内有不足，可留言，可讨论。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/743512
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号