[数据结构]：22 |
您所在的位置：网站首页 › c语言重入 › [数据结构]：22 |
[数据结构]：22
|
目录 前言 已完成内容 图实现 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++可执行程序，否则无法运行，原因上面已解释。 用于测试。 // 默认为无向图，若为有向图或网，请适当修改 #include "./Head/AdjMatrix.h" #include "./Source/AdjMatrixCommon.cpp" #include "./Source/AdjMatrixFunction.cpp" int main() { AdjMGraph AdjMatrix; InitGraph(AdjMatrix); CreateGraph(AdjMatrix); PrintGraph(AdjMatrix); printf("VertexNum = %d,EdgeNum = %d\n", AdjMatrix.VexNum, AdjMatrix.EdgeNum); printf("-----------------------------------\n"); // 判断两结点是否存在某边 if (Adjacent(AdjMatrix, 0, 1)) { printf("true\n"); } else { printf("false\n"); } if (Adjacent(AdjMatrix, 2, 3)) { printf("true\n"); } else { printf("false\n"); } printf("VertexNum = %d,EdgeNum = %d\n", AdjMatrix.VexNum, AdjMatrix.EdgeNum); printf("-----------------------------------\n"); // 列出与x邻接的边 int Edge[MAXSIZE] = {-1, -1, -1, -1, -1}; Neighbors(AdjMatrix, 0, Edge); for (int i = 0; Edge[i] != -1; i++) { printf("%3d", Edge[i]); } printf("\n"); printf("VertexNum = %d,EdgeNum = %d\n", AdjMatrix.VexNum, AdjMatrix.EdgeNum); printf("-----------------------------------\n"); // 删除顶点 DeleteVertex(AdjMatrix, 0); PrintGraph(AdjMatrix); printf("VertexNum = %d,EdgeNum = %d\n", AdjMatrix.VexNum, AdjMatrix.EdgeNum); printf("-----------------------------------\n"); // 添加顶点 InsertVertex(AdjMatrix, 4); // 添加边 AddEdge(AdjMatrix, 1, 4); PrintGraph(AdjMatrix); printf("VertexNum = %d,EdgeNum = %d\n", AdjMatrix.VexNum, AdjMatrix.EdgeNum); printf("-----------------------------------\n"); // 删除边 RemoveEdge(AdjMatrix, 0, 1); RemoveEdge(AdjMatrix, 1, 2); PrintGraph(AdjMatrix); printf("VertexNum = %d,EdgeNum = %d\n", AdjMatrix.VexNum, AdjMatrix.EdgeNum); printf("-----------------------------------\n"); // 寻找第一个邻接点 int Neighbor = FirstNeighbor(AdjMatrix, 1); printf("FirstNeighbor = %d\n", Neighbor); printf("VertexNum = %d,EdgeNum = %d\n", AdjMatrix.VexNum, AdjMatrix.EdgeNum); printf("-----------------------------------\n"); // 寻找除4之外的下一个邻接点 Neighbor = NextNeighbor(AdjMatrix, 1, 4); printf("FirstNeighbor = %d\n", Neighbor); printf("VertexNum = %d,EdgeNum = %d\n", AdjMatrix.VexNum, AdjMatrix.EdgeNum); printf("-----------------------------------\n"); return 0; } 02-头文件用于存储结构体和常量等。 // // Created by 24955 on 2023-04-02. // 默认为无向图，若为有向图或网，请适当修改 // #ifndef INC_01_ADJACENTMATRIX_ADJMATRIX_H #define INC_01_ADJACENTMATRIX_ADJMATRIX_H // 头文件 #include // 常量 #define MAXSIZE 5 typedef int VertexType; typedef int EdgeType; // 结构体-邻接矩阵 typedef struct { VertexType Vex[MAXSIZE]; // 可采用压缩存储 EdgeType Edge[MAXSIZE][MAXSIZE]; int VexNum, EdgeNum; } AdjMGraph; #endif //INC_01_ADJACENTMATRIX_ADJMATRIX_H 03-AdjMatrixCommon.cpp用于存储初始化图、输出图等操作。 // // Created by 24955 on 2023-04-02. // 默认为无向图，若为有向图或网，请适当修改 // // 初始化图 void InitGraph(AdjMGraph &AdjMatrix) { // 初始化顶点 for (int i = 0; i < MAXSIZE; i++) { AdjMatrix.Vex[i] = -1; } // 初始化边 for (int i = 0; i < MAXSIZE; i++) { for (int j = 0; j < MAXSIZE; j++) { AdjMatrix.Edge[i][j] = 0; } } AdjMatrix.VexNum = 0; AdjMatrix.EdgeNum = 0; } // 创建图 - 主要方便测试，并非图的正确创建方式，应根据具体情况具体分析 void CreateGraph(AdjMGraph &AdjMatrix) { AdjMatrix.VexNum = 4; for (int i = 0; i < AdjMatrix.VexNum; i++) { AdjMatrix.Vex[i] = i; } // 无向图 AdjMatrix.Edge[0][1] = 1; AdjMatrix.Edge[1][0] = 1; AdjMatrix.Edge[0][3] = 1; AdjMatrix.Edge[3][0] = 1; AdjMatrix.Edge[1][2] = 1; AdjMatrix.Edge[2][1] = 1; AdjMatrix.EdgeNum = 3; } // 输出邻接矩阵 void PrintGraph(AdjMGraph AdjMatrix) { for (int i = 0; i < MAXSIZE; i++) { printf("%2d\t", AdjMatrix.Vex[i]); for (int j = 0; j < MAXSIZE; j++) { printf("%2d", AdjMatrix.Edge[i][j]); } printf("\n"); } } 04-AdjMatrixFunction.cpp用于存储图的基本操作。 // // Created by 24955 on 2023-04-02. // 默认为无向图，若为有向图或网，请适当修改 // // 获取元素下标 int GetIndex(AdjMGraph AdjMatrix, VertexType x) { /* * 1. 获取元素真实下标*/ int xIndex = -1; for (int i = 0; i < MAXSIZE; i++) { if (AdjMatrix.Vex[i] == x) { xIndex = i; break; } } return xIndex; } // 判断图中是否存在边 bool Adjacent(AdjMGraph AdjMatrix, VertexType x, VertexType y) { /* * 1. 判断x->y是否存在边 * 2. 存在返回true*/ // 避免访问到不存在顶点 if (x >= MAXSIZE || y >= MAXSIZE) { return false; } int xIndex = GetIndex(AdjMatrix, x); int yIndex = GetIndex(AdjMatrix, y); // 适用于无向图、有向图、网 if (AdjMatrix.Edge[xIndex][yIndex] != 0) { return true; } return false; } // 列出图中与顶点x邻接的边 void Neighbors(AdjMGraph AdjMatrix, VertexType x, int *Edge) { /* * 1. 遍历x所在行 * 2. 用数组存储与之邻接的边另一个顶点*/ int xIndex = GetIndex(AdjMatrix, x); // 未找到顶点x if (xIndex == -1) { return; } // 找到顶点x，统计x所在行 for (int i = 0, j = 0; i < MAXSIZE; i++) { if (AdjMatrix.Edge[xIndex][i] != 0) { Edge[j++] = AdjMatrix.Vex[i]; } } } // 插入顶点x void InsertVertex(AdjMGraph &AdjMatrix, VertexType x) { /* * 1. 插入，顶点个数+1*/ if (AdjMatrix.VexNum == MAXSIZE) { return; } for (int i = 0; i < MAXSIZE; i++) { if (AdjMatrix.Vex[i] == -1) { AdjMatrix.Vex[i] = x; break; } } AdjMatrix.VexNum++; } // 删除顶点x void DeleteVertex(AdjMGraph &AdjMatrix, VertexType x) { /* * 1. 清除顶点，并修改顶点个数 * 2. 清除边，并修改边个数*/ // 清除顶点,将其值设为-1表示该顶点为空 int xIndex = GetIndex(AdjMatrix, x); AdjMatrix.Vex[xIndex] = -1; AdjMatrix.VexNum--; // 清除边 for (int i = 0; i < MAXSIZE; i++) { if (AdjMatrix.Edge[xIndex][i]) { AdjMatrix.EdgeNum--; AdjMatrix.Edge[xIndex][i] = 0; AdjMatrix.Edge[i][xIndex] = 0; } } } // 添加边 void AddEdge(AdjMGraph &AdjMatrix, VertexType x, VertexType y) { /* * 1. 获取顶点值实际下标 * 2. 插入边*/ int xIndex = GetIndex(AdjMatrix, x); int yIndex = GetIndex(AdjMatrix, y); if (xIndex == -1 || yIndex == -1) { return; } // 添加边 AdjMatrix.Edge[xIndex][yIndex] = 1; AdjMatrix.Edge[yIndex][xIndex] = 1; AdjMatrix.EdgeNum++; } // 删除边 void RemoveEdge(AdjMGraph &AdjMatrix, VertexType x, VertexType y) { /* * 1. 获取顶点值实际下标 * 2. 删除边*/ int xIndex = GetIndex(AdjMatrix, x); int yIndex = GetIndex(AdjMatrix, y); if (xIndex == -1 || yIndex == -1) { return; } // 删除边 AdjMatrix.Edge[xIndex][yIndex] = 0; AdjMatrix.Edge[yIndex][xIndex] = 0; AdjMatrix.EdgeNum--; } // 寻找图中顶点x的第一个邻接点 int FirstNeighbor(AdjMGraph AdjMatrix, VertexType x) { /* * 1. 寻找第一个不为0的值，并返回顶点值*/ int xIndex = GetIndex(AdjMatrix, x); if (xIndex == -1) { return -1; } for (int i = 0; i < MAXSIZE; i++) { if (AdjMatrix.Edge[xIndex][i]) { return AdjMatrix.Vex[i]; } } return -1; } // 图的下一个邻接点-除y以外的下一个邻接点顶点号 int NextNeighbor(AdjMGraph AdjMatrix, VertexType x, VertexType y) { /* * 1. 寻找y之后第一个不为0的值，并返回顶点值*/ int xIndex = GetIndex(AdjMatrix, x); int yIndex = GetIndex(AdjMatrix, y); if (xIndex == -1 || yIndex == -1) { return -1; } // 寻找y之后的下一个邻接点 for (int i = yIndex + 1; i < MAXSIZE; i++) { if (AdjMatrix.Edge[xIndex][i]) { return AdjMatrix.Vex[i]; } } return -1; } 结语此博客主要用于408考研数据结构C语言实现记录，内有不足，可留言，可讨论。 |
【本文地址】