这里10为什么被分割成1了？(语言-c语言)
这是出现的情况：
正常来说最后的那个1应该换成10，然后我又试了其他方式，觉得应该是10被分割成1了，但是0又不见了
代码我反复看都觉得没问题啊…能看下是哪里出了问题吗…
还有选项4的结果好像不太对…
这是实验数据“Graph.txt”，放在D盘下
//下一行为图的标识行
Graph
//图的类型标识，此图为无向图
UDG
//顶点元素数据
1 2 3 4 5 6 7 8 9 10
//以下为边的数据，共24行数据，表示12条边
1 2
1 8
2 1
2 3
2 4
3 2
4 2
4 5
4 6
4 7
5 4
5 6
6 5
6 4
6 7
7 4
7 6
8 1
8 9
8 10
9 8
9 10
10 8
10 9
这是用到的代码
#include<iostream>
using namespace std;
#include"Graph.h"
int main() {
Graph G;
char filename[] = "D:\\Graph.txt";
CreateGraphFromFile(filename, G);
menu();
int i,x;
cout << "请输入要执行的操作：";
cin >> i;
while (i)
{
switch (i)
{
case 1:
cout << "该图的边数为：" << G.ArcNum << endl;
break;
case 2:
GraphIsTree(G);
break;
case 3:
cout << "请输入访问图的起始顶点编号：" << endl;
cin >> x;
cout << "深度优先遍历序列为：" << endl;
DFSTraverse(G, x);
cout << endl;
break;
case 4:
cout << "请输入访问图的起始顶点编号：" << endl;
cin >> x;
cout << "广度优先遍历序列为：" << endl;
BFSTraverse(G, x);
cout << endl;
break;
}
system("pause");
cout << "请输入要执行的操作：";
cin >> i;
}
return 0;
}
#pragma once
#include<iostream>
#include<queue>
using namespace std;
#define INF 999 //定义无穷大
#define MaxVerNum 99 //定义最大顶点数
typedef char elementType; //定义图中顶点的数据类型，这里设为char类型
typedef int cellType; //定义邻接矩阵中元素的数据类型，这里设为int型
//对无权图，1-相邻（有边），0-不相邻（无边）
//对有权图，为边的权值，无边为无穷大
typedef enum { UDG, UDN, DG, DN }GraphKind; //枚举图的类型：无向图，无向网，有向图，有向网
typedef struct GraphAdjMaxtrix {
elementType Data[MaxVerNum]; //顶点数组，存放顶点元素的值
cellType AdjMatrix[MaxVerNum][MaxVerNum]; //邻接矩阵，元素类型为cellType（int）
int VerNum; //顶点数
int ArcNum; //弧（边）数
GraphKind gKind; //图的类型：0-无向图；1-无向网；2-有向图；3-有向网
//此项用以区分图的类型，为可选分量，可以取消
//此项也可直接定义为整型，而不用枚举定义
}Graph; //图的类型名
bool visited[MaxVerNum + 1]; //全局数组，标记顶点是否已经访问，visited[0]单元不用
//声明
int CreateGraphFromFile(char fileName[], Graph& G);
void menu();
void strLTrim(char* str);
void visit(Graph& G, int verID);
int firstAdj(Graph& G, int v);
int nextAdj(Graph& G, int v, int w);
bool GraphIsTree(Graph& G);
void DFS(Graph& G, int verID);
int DFSTraverse(Graph& G, int verID);
/7oid DFS(Graph& G, int v);
/7oid DFSTraverse(Graph& G, int v);
void BFS(Graph& G, int v);
void BFSTraverse(Graph& G, int v);
//从数据文件创建邻接矩阵表示的图
int CreateGraphFromFile(char fileName[], Graph& G)
{
FILE* pFile; //定义文件指针
char str[1000]; //存放读出一行文本的字符串
char strTemp[10]; //判断是否注释行
cellType eWeight; //边的信息，常为边的权值
GraphKind graphType; //图类型枚举变量
pFile = fopen(fileName, "r");
if (!pFile)
{
printf("错误：文件%s打开失败。\n", fileName);
return false;
}
while (fgets(str, 1000, pFile) != NULL)
{
strLTrim(str); //删除字符串左边空格，这是一个自定义的函数
if (str[0] == '\n') //空行，继续读取下一行
continue;
strncpy(strTemp, str, 2);
if (strstr(strTemp, "//") != NULL) //跳过注释行
continue;
else //非注释行、非空行，跳出循环
break;
}
//循环结束，str中应该已经是图的标识Graph，判断标识是否正确
if (strstr(str, "Graph") == NULL)
{
printf("错误：打开的文件格式错误！\n");
fclose(pFile); //关闭文件
return false;
}
//读取图的类型，跳过空行
while (fgets(str, 1000, pFile) != NULL)
{
strLTrim(str); //删除字符串左边空格，这是一个自定义函数
if (str[0] == '\n') //空行，继续读取下一行
continue;
strncpy(strTemp, str, 2);
if (strstr(strTemp, "//") != NULL) //注释行，跳过，继续读取下一行
continue;
else //非空行，也非注释行，即图的类型标识
break;
}
//设置图的类型
if (strstr(str, "UDG"))
graphType = UDG; //无向图
else if (strstr(str, "UDN"))
graphType = UDN; //无向网
else if (strstr(str, "DG"))
graphType = DG; //有向图
else if (strstr(str, "DN"))
graphType = DN; //有向网
else
{
printf("错误：读取图的类型标记失败！\n");
fclose(pFile); //关闭文件
return false;
}
//读取顶点行数据到str。跳过空行
while (fgets(str, 1000, pFile) != NULL)
{
strLTrim(str); //删除字符串左边空格，这是一个自定义函数
if (str[0] == '\n') //空行，继续读取下一行
continue;
strncpy(strTemp, str, 2);
if (strstr(strTemp, "//") != NULL) //注释行，跳过，继续读取下一行
continue;
else //非空行，也非注释行，即图的顶点元素行
break;
}
//顶点数据放入图的顶点数组
char* token = strtok(str, " ");
int nNum = 0;
while (token != NULL)
{
G.Data[nNum] = *token;
token = strtok(NULL, " ");
nNum++;
}
//图的邻接矩阵初始化
int nRow = 0; //矩阵行下标
int nCol = 0; //矩阵列下标
if (graphType == UDG || graphType == DG)
{
for (nRow = 0; nRow < nNum; nRow++)
for (nCol = 0; nCol < nNum; nCol++)
G.AdjMatrix[nRow][nCol] = 0;
}
else
{
for (nRow = 0; nRow < nNum; nRow++)
for (nCol = 0; nCol < nNum; nCol++)
G.AdjMatrix[nRow][nCol] = INF; //INF表示无穷大
}
//循环读取边的数据到邻接矩阵
int edgeNum = 0; //边的数量
elementType Nf, Ns; //边或弧的2个相邻顶点
while (fgets(str, 1000, pFile) != NULL)
{
strLTrim(str); //删除字符串左边空格，这是一个自定义函数
if (str[0] == '\n') //空行，继续读取下一行
continue;
strncpy(strTemp, str, 2);
if (strstr(strTemp, "//") != NULL) //注释行，跳过，继续读取下一行
continue;
char* token = strtok(str, " "); //以空格为分隔符，分割一行数据，写入邻接矩阵
if (token == NULL) //分割为空串，失败退出
{
printf("错误：读取图的边数据失败！\n");
fclose(pFile); //关闭文件
return false;
}
Nf = * token; //获取边的第一个顶点
token = strtok(NULL, " "); //读取下一个子串，即第二个顶点
if (token == NULL) //分割为空串，失败退出
{
printf("错误：读取图的边数据失败！\n");
fclose(pFile); //关闭文件
return false;
}
Ns = * token; //获取边的第二个顶点
//从第一个顶点获取行号
for (nRow = 0; nRow < nNum; nRow++)
{
if (G.Data[nRow] == Nf) //从顶点列表找到第一个顶点的编号
break;
}
//从第二个顶点获取列号
for (nCol = 0; nCol < nNum; nCol++)
{
if (G.Data[nCol] == Ns) //从顶点列表找到第二个顶点的编号
break;
}
//如果为网，读取权值
if (graphType == UDN || graphType == DN)
{ //读取下一个子串，即边的附加信息，常为边的权重
token = strtok(NULL, " ");
if (token == NULL) //分割为空串，失败退出
{
printf("错误：读取图的边数据失败！\n");
fclose(pFile); //关闭文件
return false;
}
eWeight = atoi(token); //取得边的附加信息
}
if (graphType == UDN || graphType == DN) //如果为网，邻接矩阵中对应的边设置权值，否则置为1
G.AdjMatrix[nRow][nCol] = eWeight;
else
G.AdjMatrix[nRow][nCol] = 1;
edgeNum++; //边数加1
}
G.VerNum = nNum; //图的顶点数
if (graphType == UDG || graphType == UDN)
G.ArcNum = edgeNum / 2; //无向图或网的边数等于统计的数字除2
else
G.ArcNum = edgeNum;
G.gKind = graphType; //图的类型
fclose(pFile); //关闭文件
cout << "已从数据文件\"D:\\Graph.txt\"创建邻接矩阵表示的图" << endl;
return true;
}
void menu()
{
cout << "0、退出程序" << endl;
cout << "1、求给定图中边的个数" << endl;
cout << "2、判断该图是否是一棵树" << endl;
cout << "3、输出DFS序列" << endl;
cout << "4、输出BFS序列" << endl;
}
// 删除字符串、字符数组左边的空格
void strLTrim(char* str)
{
int i, j;
int n = 0;
n = strlen(str) + 1;
for (i = 0; i < n; i++)
{
if (str[i] != ' ') //找到左起第一个非空格位置
break;
}
//以第一个非空格字符为手字符移动字符串
for (j = 0; j < n; j++)
{
str[j] = str[i];
i++;
}
}
void visit(Graph& G, int verID)
{ //顶点编号从1开始，数组0单元不用
cout << G.Data[verID] << " ";
visited[verID] = true;
}
//求顶点v的第一个邻接点
int firstAdj(Graph& G, int v)
{
int w;
for (w = 1; w <= G.VerNum; w++)
{
if ((G.AdjMatrix[v][w] >= 1) && (G.AdjMatrix[v][w]) < INF)
return w; //返回第一个邻接点编号
}
return 0; //未找到邻接点，返回0
}
//求顶点v的位于邻接点w后的下一个邻接点
int nextAdj(Graph& G, int v, int w)
{
int k;
for (k = w + 1; k <= G.VerNum; k++)
{
if ((G.AdjMatrix[v][k] >= 1) && (G.AdjMatrix[v][k]) < INF)
return k; //返回v的位于w之后的下一个邻接点k
}
return 0; //不存在下一个邻接点，返回0
}
//判断该图是否是一棵树
bool GraphIsTree(Graph& G)
{
for (int i = 0; i < G.VerNum; i++)
{
visited[i] = false;
}
int VNum = 0;
int ENum = 0;
if (VNum == G.VerNum && ENum == 2 * (G.VerNum - 1)) //是无回路的连通图，且边的个数是“顶点数-1”
{
cout << "该图是一棵树" << endl;
return true;
}
else
{
cout << "该图不是一棵树" << endl;
return false;
}
}
void DFS(Graph& G, int verID)
{
cout << G.Data[verID - 1] << " ";
visited[verID - 1] = true;
for (int w = 0; w < G.VerNum; w++)
{
if ((G.AdjMatrix[verID - 1][w] >= 1) && (G.AdjMatrix[verID - 1][w] < INF) && (!visited[w]))
{
DFS(G,w+1);
}
}
}
int DFSTraverse(Graph& G, int verID)
{
int vID;
int conNum = 0;
for (vID = 0; vID < G.VerNum; vID++)
visited[vID] = false;
DFS(G, verID);
conNum++;
for (vID = 1; vID <= G.VerNum; vID++)
{
if (!visited[vID - 1])
{
DFS(G, vID);
conNum++;
}
}
return conNum;
}
void menu()
{
cout << "0、退出程序" << endl;
cout << "1、求给定图中边的个数" << endl;
cout << "2、判断该图是否是一棵树" << endl;
cout << "3、输出DFS序列" << endl;
cout << "4、输出BFS序列" << endl;
}
// 删除字符串、字符数组左边的空格
void strLTrim(char* str)
{
int i, j;
int n = 0;
n = strlen(str) + 1;
for (i = 0; i < n; i++)
{
if (str[i] != ' ') //找到左起第一个非空格位置
break;
}
//以第一个非空格字符为手字符移动字符串
for (j = 0; j < n; j++)
{
str[j] = str[i];
i++;
}
}
void visit(Graph& G, int verID)
{ //顶点编号从1开始，数组0单元不用
cout << G.Data[verID] << " ";
visited[verID] = true;
}
//求顶点v的第一个邻接点
int firstAdj(Graph& G, int v)
{
int w;
for (w = 1; w <= G.VerNum; w++)
{
if ((G.AdjMatrix[v][w] >= 1) && (G.AdjMatrix[v][w]) < INF)
return w; //返回第一个邻接点编号
}
return 0; //未找到邻接点，返回0
}
//求顶点v的位于邻接点w后的下一个邻接点
int nextAdj(Graph& G, int v, int w)
{
int k;
for (k = w + 1; k <= G.VerNum; k++)
{
if ((G.AdjMatrix[v][k] >= 1) && (G.AdjMatrix[v][k]) < INF)
return k; //返回v的位于w之后的下一个邻接点k
}
return 0; //不存在下一个邻接点，返回0
}
//判断该图是否是一棵树
bool GraphIsTree(Graph& G)
{
for (int i = 0; i < G.VerNum; i++)
{
visited[i] = false;
}
int VNum = 0;
int ENum = 0;
if (VNum == G.VerNum && ENum == 2 * (G.VerNum - 1)) //是无回路的连通图，且边的个数是“顶点数-1”
{
cout << "该图是一棵树" << endl;
return true;
}
else
{
cout << "该图不是一棵树" << endl;
return false;
}
}
void DFS(Graph& G, int verID)
{
cout << G.Data[verID - 1] << " ";
visited[verID - 1] = true;
for (int w = 0; w < G.VerNum; w++)
{
if ((G.AdjMatrix[verID - 1][w] >= 1) && (G.AdjMatrix[verID - 1][w] < INF) && (!visited[w]))
{
DFS(G,w+1);
}
}
}
int DFSTraverse(Graph& G, int verID)
{
int vID;
int conNum = 0;
for (vID = 0; vID < G.VerNum; vID++)
visited[vID] = false;
DFS(G, verID);
conNum++;
for (vID = 1; vID <= G.VerNum; vID++)
{
if (!visited[vID - 1])
{
DFS(G, vID);
conNum++;
}
}
return conNum;
}
/连通图的广度优先遍历
void BFS(Graph & G, int v)
{
queue<int> Q; //队列存放元素的编号
int w;
visit(G, v); //访问定点，并设置其访问标志
Q.push(v); //节点编号入队
while (!Q.empty())
{
v = Q.front();
Q.pop();
w = firstAdj(G, v);
while (w != 0)
{
if (!visited[w] && G.AdjMatrix[v][w] >= 1 && G.AdjMatrix[v][w] < INF)
{
visit(G, w);
Q.push(w);
}
w = nextAdj(G, v, w);
}
}
}
//一般图的广度优先遍历
void BFSTraverse(Graph& G, int v)
{
int i;
for (i = 1; i <= G.VerNum; i++)
{
visited[i] = false; //初始化访问标志为false
}
for (v; v >= 1; v--) //编号1到v
{
if (visited[v] == false) //循环选择未被访问的顶点
BFS(G, v); //每次循环遍历一个连通分量
}
for (v; v <= G.VerNum; v++) //编号v到G.vernum
{
if (visited[v] == false) //循环选择未被访问的顶点
BFS(G, v); //每次循环遍历一个连通分量
}
}
问题在这里：
typedef char elementType; // 定义图中顶点的数据类型，这里设为char类型
elementType Data[MaxVerNum]; //顶点数组，存放顶点元素的值
。。。
G.Data[nNum] = *token;
你用 char 来存放顶点数据，char 本来就只能存储一个字节啊，所以 "10" 就只存了 '1'。
解决：
你想存两位数的话可以改成这样：
#define MaxValueStrLen 2 // 数值位数
elementType Data[MaxVerNum][MaxValueStrLen]; // 顶点数组，存放顶点元素的值
。。。
strcpy(G.Data[nNum], token);
验证：
