具体代码如下，运行出错，帮忙看看 - 编程论坛

#2

书生牛犊2016-11-17 19:06

看了一遍代码思路貌似没问题。如果可以，提供一下原题链接或者示例输入输出。我想用数据测试看看

程序代码：

#include "stdio.h"
#include"string.h"
#include "malloc.h"
#define OK 1
#define ERROR 0
#define FALSE 0
#define TRUE  1
#define MAX_VERTEX_NUM  20
typedef int Status;
typedef int InfoType;
typedef char VertexType;
int visited[MAX_VERTEX_NUM]={0,0,0,0};/*这四个零和一个零没啥区别，写四个反而容易让人把它想复杂咯*/
typedef struct ArcNode//弧的结构
{
    int adjvex;
    struct ArcNode *nextarc;
    //InfoType  info;
}ArcNode;
typedef struct VNode//顶点的结构
{
    VertexType data;
    ArcNode * firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct //图的结构
{
    AdjList vertices;
    int vexnum,arcnum;
    //int kind;
}AlGraph;

void CreateGraph(AlGraph &G)//创建邻接表
{
    printf("input vexnum and arcnum");
scanf("%d%d",&G.vexnum,&G.arcnum);
    printf("input the xinxi of vex");
    for(int i=0;i<G.vexnum;i++)//输入顶点信息
    {
        scanf("%c",&G.vertices[i].data); /*scanf(%c)会至少读到一个'\n'，至于原因我就不详细说明了，你应该懂吧*/
        G.vertices[i].firstarc=NULL;
    }
    printf("输入弧的信息");//输入弧的信息
    for(int i=0;i<G.arcnum;i++)/*你生成的弧是单向弧，只能通过狐尾访问弧头。所以这应该是一个有向图，并且深度优先遍历的时候也不是根据结点编号输出结果，而是根据输入数据的先后执行DFS*/

    {
        int tail,head;
    //    int info;
        ArcNode *p,*pnew;
        printf("输入弧尾、弧头");
        scanf("%d%d",&tail,&head);
        pnew=(ArcNode *)malloc(sizeof(ArcNode));
        pnew->adjvex=head;
        //pnew->info=info;
        pnew->nextarc=NULL;
        p=G.vertices[tail].firstarc;
        if(!p)
            G.vertices[tail].firstarc=pnew;
        else
        {
            while(p->nextarc!=NULL) p=p->nextarc;
            p->nextarc=pnew;
        }


    }
}
void VisitFunc(AlGraph &G,int v)//访问函数
{
    printf("%c",G.vertices[v].data);
}
int FirstAdjvex(AlGraph &G,int v)
{
    if(G.vertices[v].firstarc)
        return G.vertices[v].firstarc->adjvex;
    else
        return -1;
}
int NextAdjvex(AlGraph &G,int v,int w)//求下一个邻接点
{
    ArcNode *p;
    p=G.vertices[v].firstarc;
    while(p->adjvex!=w)
        p=p->nextarc;
    if(p->nextarc)
        return p->nextarc->adjvex;
    else
        return -1;
}
void DFS(AlGraph &G,int v)//一个节点的深度优先遍历
{
    visited[v]=TRUE;
    VisitFunc(G,v);
    for(int w=FirstAdjvex(G,v);w>=0;w=NextAdjvex(G,v,w))
        if(!visited[w])
        DFS(G,w);

}
void DFS1(AlGraph &G,int v){/*用指针的方法，试试看。我没测试数据，还不知道是不是对的。*/
    visited[v]=TRUE;
    VisitFunc(G,v);
    for(ArcNode *p=G.vertices[v].firstarc;p!=NULL;p=p->nextarc){
        if(!visited[p->adjvex])DFS(G,p->adjvex);
    }
}

void DFSTraverse(AlGraph &G)//图的深度优先遍历
{
    printf("深度优先遍历");
    for(int  v=1;v<=G.vexnum;v++)
    if(!visited[v])
    DFS(G,v);/* DFS1(G,v); */

}
int main()
{
    AlGraph G;


    CreateGraph(G);
    DFSTraverse(G);


    //BFSTraverse(G,VisitFunc);//广度优先，自己完成



    return 0;
}

[此贴子已经被作者于2016-11-17 20:25编辑过]

#3

相思豆2016-11-17 22:31

这是一个有向图的深度优先遍历的程序，运行时输入弧数，顶点数时没问题，输入弧头弧尾时会自动弹出一个框，上面写着出现正在解决的问题，然后没有结果输出了。大体情况就是这样。

#4

xzlxzlxzl2016-11-18 10:52

主要是顶点数数组未初始化造成，如果输入的弧头、尾数目小于顶点数不会出错，否则出错，可将main函数修改如下：
int main()
{
    AlGraph G;
    int i;
    for(i=0;i<MAX_VERTEX_NUM;i++)G.vertices[i].firstarc=NULL;  //初始化顶点数组，可保证输入20以内的数不出错
    CreateGraph(G);
    DFSTraverse(G);

    //BFSTraverse(G,VisitFunc);//广度优先，自己完成


    return 0;
}

#5

相思豆2016-11-18 20:25

回复 4楼 xzlxzlxzl

我按你说的试了试，还是不行，我把下面这个里的 for循环中的 v从0开始<G.vexnum就运行出来了。
void DFSTraverse(AlGraph &G)//图的深度优先遍历
{
    printf("深度优先遍历");
    for(int  v=1;v<=G.vexnum;v++)
    if(!visited[v])
  DFS(G,v);

}

#6

相思豆2016-11-18 20:34

回复 2楼书生牛犊

你说下面的这个地方
for(int i=0;i<G.vexnum;i++)//输入顶点信息
    {
        scanf("%c",&G.vertices[i].data); /*scanf(%c)会至少读到一个'\n'，至于原因我就不详细说明了，你应该懂吧*/
        G.vertices[i].firstarc=NULL;
    }
关于scanf输入时我不太明白，但是这个程序我把那个%c改为%s之后就运行出来了。

#7

书生牛犊2016-11-19 00:50

回复 6楼相思豆

百度一下 “scanf %c”
找些博客文章看看。。。解释起来蛮复杂的