|
#2
莫启飞2021-12-16 19:54
回复 楼主 莫启飞
|
只有本站会员才能查看附件，请 登录
只有本站会员才能查看附件，请 登录
程序代码：//头文件：GraphModel.h
#pragma once
#define ok 1
#define ERROR 0
#define Max_VERTEX 100
/** 图的类型枚举*/
typedef enum {
UDG,//无向图
DG, //有向图
DN, //有向网
UDN//无向网
}Graphkind;
/**设置顶点的数据类型为字符型，记得分配内存*/
typedef char* VerTexType;
/**设置权值的整数类型*/
typedef int ArcType;
/**设置返回状态类型*/
typedef int status;
//头文件：MatrixGraph.h
#ifndef MATRIXGRAPH_H_INCLUDED
#define MATRIXGRAPH_H_INCLUDED
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include "GraphModel.h"
typedef struct {
VerTexType vertex[Max_VERTEX]; //顶点的数组存储类型
ArcType arc[Max_VERTEX][Max_VERTEX]; //邻接矩阵的数据存储类型
int vercountry; //顶点的个数
int arccountry; //图的边或弧的个数
Graphkind kind; //图的类型
}MatrixGraph;
#endif
/**创建无向图*/
status creativeGDU(MatrixGraph*G);
status dispaly();
int localver(MatrixGraph*G,VerTexType ver);
//MatrixGraph.c文件
#define _CRT_SECURE_NO_WARNINGS
#include<malloc.h>
#include<string.h>
#include"MatrixGraph.h"
/** 使用邻接矩阵表示法创建无向图*/
//无向图特点：
//1.无向图的邻接矩阵是对称的
//2.顶点的度 = 第i行（列）中1的个数
status creativeGDU(MatrixGraph*G) {
G-> kind = UDG; //设置当前创建图的类型为无向图
printf("请输入顶点的个数:");
scanf("%d", &G->vercountry);
printf("请输入边的个数:");
scanf("%d", &G->arccountry);
printf("请依次输入顶点信息:\n");
for (int i = 0; i < G->vercountry; i++) {
G->vertex[i] = (VerTexType)malloc(sizeof(char) * 10);
printf("顶点%d:", i + 1);
scanf("%s", &G->vertex[i]);
}
//初始化邻接矩阵，所有边的权值设置为0
for (int i = 0; i < G->vercountry; i++) {
for (int j = 0; j < G->vercountry; j++) {
G->arc[i][j] = 0;
}
}
printf("请输入顶点和邻接顶点信息，构建邻接矩阵\n");
for (int i = 0; i < G->arccountry; i++) {
VerTexType ver1 = (VerTexType)malloc(sizeof(char) * 10);/*建立两个临时的内存存储每一次变化的，ver1和ver2
这里出现错误了，之前我是把，ver1和ver2的内存分配放到for循环外面去了，这样是错误的，
因为我在上面建立vertex[i]:每一个顶点数组元素分配内存时都是10个，这样会导致只装得了第一次的
ver1和ver2第二次以上分配的会导致栈溢出。
*/
VerTexType ver2 = (VerTexType)malloc(sizeof(char) * 10);
printf("顶点：");
scanf("%s", ver1);
printf("\n");
printf("邻接点");
scanf("%s", ver2);
//分别获得两个顶点在顶点数组中的坐标
int x = localver(G, ver1);
int y = localver(G, ver2);
if (x == -1 || y == -1) {
return ERROR;
}
G->arc[x][y] = 1;
G->arc[y][x] = G->arc[x][y];
free(ver1); //这里要注意每一次遍历时都要释放这两个临时空间
free(ver2);
}
}
/**返回某个顶点在顶点集合中的下标（从0开始），不存在返回-1*/
int localver(MatrixGraph*G,VerTexType ver) {
int index = 0;
while (index < G->vercountry) { //bug: 这里应该是顶点的数量我写成了边的数量
if (strcmp(G->vertex[index], ver) == 0) { /**
这里也非常关键，ver是用户输入的顶点元素，用到的是
strcmp()字符串比较函数 ，这里是两个字符串相等的意思
*/
break;
}
index++;
}
return index == G->vercountry ? -1 : index; /**
这里非常重要，如果用户输入的不在存在顶点的范围内,等到下标
加到最后一个顶点，就会返回-1，报错ERROR
*/
}
status display(MatrixGraph*G){
status status = creativeGDU(&G);
if (status == ERROR) {
printf("无向图创建失败");
}
printf("邻接矩阵创建无向图\n");
for (int i = 0; i < G->vercountry; i++) {
printf("\t%s", G->vertex[i]);
}
printf("\n");
for (int i = 0; i < G->vercountry; i++) {
printf("\t%s", G->vertex[i]);
for (int j = 0; j < G->vercountry; j++) {
printf("\t%s", G->arc[i][j]);
}
printf("\n");
}
return ok;
}
//main.c
#include"MatrixGraph.h"
#include<stdio.h>
#include<stdlib.h>
int main() {
MatrixGraph G;
display(&G);
return 0;
}