void createudn(amgraph &G) { int w; char v1,v2; printf("请输入总定点数和总边数:\n"); scanf("%d %d",&G.vexnum,&G.arcnum); printf("请输入各点信息:\n"); for(i=0;i<G.vexnum;++i) { scanf("%c",&G.vexs[i]); } for(i=0;i<G.vexnum;++i) { for(j=0;j<G.vexnum;++j) { G.arcs[i][j]=maxint; } } for(i=0;i<G.arcnum;i++) { scanf("%c %c %d",&v1,&v2,&w); G.arcs[vexlocate(G,v1)][vexlocate(G,v2)]=w; G.arcs[vexlocate(G,v2)][vexlocate(G,v1)]=w; } }问题出在哪
时间: 2024-02-01 22:02:50 浏览: 30
问题出在输入顶点信息时,应该在读取完数字后再读取字符,因为输入数字后会有一个换行符留在缓冲区中,会被误认为是输入的字符。可以在读取字符前加上一个空格来解决这个问题。修改后的代码如下:
```c
void createudn(amgraph &G) {
int w;
char v1,v2;
printf("请输入总定点数和总边数:\n");
scanf("%d %d",&G.vexnum,&G.arcnum);
printf("请输入各点信息:\n");
getchar(); // 读取换行符
for(i=0;i<G.vexnum;++i) {
scanf(" %c",&G.vexs[i]); // 加上空格
}
for(i=0;i<G.vexnum;++i) {
for(j=0;j<G.vexnum;++j) {
G.arcs[i][j]=maxint;
}
}
for(i=0;i<G.arcnum;i++) {
scanf(" %c %c %d",&v1,&v2,&w); // 加上空格
G.arcs[vexlocate(G,v1)][vexlocate(G,v2)]=w;
G.arcs[vexlocate(G,v2)][vexlocate(G,v1)]=w;
}
}
```
相关问题
#include <iostream> #define MVNum 100 #define MaxInt 32767 using namespace std; struct edge{ char adjvex; int lowcost; }closedge[MVNum]; typedef struct{ char vexs[MVNum]; int arcs[MVNum][MVNum]; int vexnum,arcnum; }AMGraph; int LocateVex(AMGraph G , char v);//实现细节隐藏 int CreateUDN(AMGraph &G);//实现细节隐藏 int Min(AMGraph G){ int i; int index = -1; int min = MaxInt; for(i = 0 ; i < G.vexnum ; ++i){ if( ){ min = closedge[i].lowcost; index = i; } } return index; } void MiniSpanTree_Prim(AMGraph G, char u){ int k , j , i; char u0 , v0; k =LocateVex(G, u); for(j = 0; j < G.vexnum; ++j){ if(j != k){ closedge[j].adjvex = ; closedge[j].lowcost = ; } } closedge[k].lowcost = ; for(i = 1; i < G.vexnum; ++i){ k = ; u0 = closedge[k].adjvex; v0 = G.vexs[k]; cout << u0 << "->" << v0 << endl; closedge[k].lowcost = ; for(j = 0; j < G.vexnum; ++j) if(G.arcs[k][j] < closedge[j].lowcost){ closedge[j].adjvex = ; closedge[j].lowcost = ; } } } int main(){ AMGraph G; CreateUDN(G); char u; cin >> u; MiniSpanTree_Prim(G , u); return 0; } 补充代码
在代码中,需要完成以下部分的补充:
1. 在 Min 函数中,需要添加判断条件来判断 closedge[i].lowcost 是否小于 min。
2. 在 MiniSpanTree_Prim 函数中,需要根据 Prim 算法的步骤补充代码,并且需要实现 LocateVex 函数来找到对应顶点在图中的位置。
补充后的代码如下:
```
#include <iostream>
#define MVNum 100
#define MaxInt 32767
using namespace std;
struct edge{
char adjvex;
int lowcost;
}closedge[MVNum];
typedef struct{
char vexs[MVNum];
int arcs[MVNum][MVNum];
int vexnum,arcnum;
}AMGraph;
int LocateVex(AMGraph G , char v);//实现细节隐藏
int CreateUDN(AMGraph &G);//实现细节隐藏
int Min(AMGraph G){
int i;
int index = -1;
int min = MaxInt;
for(i = 0 ; i < G.vexnum ; ++i){
if(closedge[i].lowcost < min){
min = closedge[i].lowcost;
index = i;
}
}
return index;
}
void MiniSpanTree_Prim(AMGraph G, char u){
int k , j , i;
char u0 , v0;
k =LocateVex(G, u);
for(j = 0; j < G.vexnum; ++j){
if(j != k){
closedge[j].adjvex = G.vexs[k];
closedge[j].lowcost = G.arcs[k][j];
}
}
closedge[k].lowcost = 0;
for(i = 1; i < G.vexnum; ++i){
k = Min(G);
u0 = closedge[k].adjvex;
v0 = G.vexs[k];
cout << u0 << "->" << v0 << endl;
closedge[k].lowcost = 0;
for(j = 0; j < G.vexnum; ++j)
if(G.arcs[k][j] < closedge[j].lowcost){
closedge[j].adjvex = G.vexs[k];
closedge[j].lowcost = G.arcs[k][j];
}
}
}
int LocateVex(AMGraph G , char v){
int i;
for(i = 0 ; i < G.vexnum ; ++i){
if(G.vexs[i] == v){
return i;
}
}
return -1;
}
int CreateUDN(AMGraph &G){
int i , j , k;
cout << "请输入顶点数和边数:";
cin >> G.vexnum >> G.arcnum;
cout << "请依次输入每个顶点的信息:";
for(i = 0 ; i < G.vexnum ; ++i){
cin >> G.vexs[i];
}
for(i = 0 ; i < G.vexnum ; ++i){
for(j = 0 ; j < G.vexnum ; ++j){
G.arcs[i][j] = MaxInt;
}
}
cout << "请依次输入每条边的两个顶点及其权值:";
for(k = 0 ; k < G.arcnum ; ++k){
char v1 , v2;
int w;
cin >> v1 >> v2 >> w;
i = LocateVex(G , v1);
j = LocateVex(G , v2);
G.arcs[i][j] = w;
G.arcs[j][i] = w;
}
return 1;
}
int main(){
AMGraph G;
CreateUDN(G);
char u;
cin >> u;
MiniSpanTree_Prim(G , u);
return 0;
}
```
#include<iostream> #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define MVNum 100 //最大顶点数 #define MaxInt 32767 using namespace std; typedef struct {//图的邻接矩阵存储表示 int vexnum,arcnum; //图的当前顶点数和边数 int vexs[MVNum]; //顶点表 int arcs[MVNum][MVNum]; //邻接矩阵 }AMGraph; int CreateUDN(AMGraph &G,int vexnum,int arcnum) {//采用邻接矩阵表示法,创建无向网G G.vexnum=vexnum; //输入总顶点数 G.arcnum=arcnum; //输入总边数 if(G.vexnum>MVNum) return ERROR; //超出最大顶点数则结束函数 int i,j,a,b,c; for(i=1;i<=G.vexnum;i++) G.vexs[i]=i; for(i=1;i<=G.vexnum;i++) //初始化邻接矩阵,边的权值均置为极大值 for(j=1;j<=G.vexnum;j++) G.arcs[i][j]=MaxInt; for(i=0;i<G.arcnum;i++) //顶点a和顶点b之间有一条长度为c的路 { cin>>a>>b>>c; G.arcs[a][b]=c; G.arcs[b][a]=c; } return OK; } void ShortPathMAX(AMGraph G,int v0) {//用Dijkstra算法求图G中距离顶点v0的最短路径长度最大的一个顶点 /**begin/ /**end/ } int main() { int n,m; while(cin>>n>>m) { if(n==0&&m==0) break; AMGraph G; CreateUDN(G,n,m); //创建无向网G int v; cin>>v; ShortPathMAX(G,v); //最长的最短路径的求解 } return 0; }补全代码,测试输入: 4 4 1 2 1 2 3 1 3 4 1 2 4 1 4 4 3 1 2 3 2 3 2 2 4 6 3 0 0 预期输出: 1 2 4 8
#include<iostream>
#include<algorithm>
#include<cstring>
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MVNum 100 //最大顶点数
#define MaxInt 32767
using namespace std;
typedef struct {//图的邻接矩阵存储表示
int vexnum,arcnum; //图的当前顶点数和边数
int vexs[MVNum]; //顶点表
int arcs[MVNum][MVNum]; //邻接矩阵
}AMGraph;
int CreateUDN(AMGraph &G,int vexnum,int arcnum) {//采用邻接矩阵表示法,创建无向网G
G.vexnum=vexnum; //输入总顶点数
G.arcnum=arcnum; //输入总边数
if(G.vexnum>MVNum)
return ERROR; //超出最大顶点数则结束函数
int i,j,a,b,c;
for(i=1;i<=G.vexnum;i++)
G.vexs[i]=i;
for(i=1;i<=G.vexnum;i++) //初始化邻接矩阵,边的权值均置为极大值
for(j=1;j<=G.vexnum;j++)
G.arcs[i][j]=MaxInt;
for(i=0;i<G.arcnum;i++) //顶点a和顶点b之间有一条长度为c的路
{
cin>>a>>b>>c;
G.arcs[a][b]=c;
G.arcs[b][a]=c;
}
return OK;
}
void ShortPathMAX(AMGraph G,int v0) {//用Dijkstra算法求图G中距离顶点v0的最短路径长度最大的一个顶点
int dist[MVNum];//存储源点v0到其他顶点的最短距离
bool visited[MVNum]={false};//记录顶点是否已被访问
memset(dist,0,sizeof(dist));
for(int i=1;i<=G.vexnum;i++)//初始化dist数组
if(i!=v0)
dist[i]=MaxInt;
for(int i=1;i<=G.vexnum;i++) //循环n次,每次找出一个顶点的最短路径
{
int maxDist=-1,u;
for(int j=1;j<=G.vexnum;j++)
{
if(!visited[j]&&dist[j]>maxDist)
{
maxDist=dist[j];
u=j;
}
}
visited[u]=true;
for(int v=1;v<=G.vexnum;v++)
{
if(!visited[v]&&G.arcs[u][v]<MaxInt)
{
int newDist=max(dist[u],G.arcs[u][v]);
if(newDist<dist[v])
dist[v]=newDist;
}
}
}
for(int i=1;i<=G.vexnum;i++)
if(dist[i]!=MaxInt)
cout<<dist[i]<<" ";
cout<<endl;
}
int main() {
int n,m;
while(cin>>n>>m) {
if(n==0&&m==0)
break;
AMGraph G;
CreateUDN(G,n,m); //创建无向网G
int v;
cin>>v;
ShortPathMAX(G,v); //最长的最短路径的求解
}
return 0;
}