搜索
编程论坛 → 开发语言 → 『 C语言论坛 』 → 图广度优先搜索生成二叉树后不知道哪个地方错误了找了半天没找出，请大神指点，谢谢！
标题：图广度优先搜索生成二叉树后不知道哪个地方错误了找了半天没找出，请大神指 ...
只看楼主
zqszqs10
Rank: 1
等　级：新手上路
帖　子：14
专家分：3
注　册：2016-10-27
结帖率：50%
楼主
 已结贴√  问题点数：10 回复次数：10 
图广度优先搜索生成二叉树后不知道哪个地方错误了找了半天没找出，请大神指点，谢谢！

#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#include<windows.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef char VertexType;
#define MAX_VER_NUM 30
char Data[13][2]={{'A','B'},{'A','C'},{'A','F'},{'A','L'},{'L','J'},{'L','M'},{'J','M'},{'M','B'},{'D','E'},{'G','I'},{'G','H'},{'G','K'},{'H','K'}};
FILE *pf;
typedef struct ArcBox//边的信息
{
    int iver;
    struct ArcBox *ilink;
    int jver;
    struct ArcBox *jlink;
    char *info;
    int mark;
}ArcBox;
typedef struct VerBox//顶点的信息
{
    VertexType data;
    ArcBox *firstedge;
}VerBox;
typedef struct Graph//图的信息
{
    int vernum;
    int arcnum;
    VerBox vertexs[MAX_VER_NUM];
}Graph;
typedef struct QNode//队列中的数据
{
    VerBox *data;
    struct QNode *next;
}QNode;
typedef struct Queue//队列
{
    QNode *front;
    QNode *rear;
}Queue;
typedef struct CSNode//兄弟孩子结构体
{
    int data;
    struct CSNode *firstchild;
    struct CSNode *nextsibling;
}CSNode;
int Visited[MAX_VER_NUM];//标记顶点是否被访问过
Status CreateGraph(Graph *G);//创建图
int LocateVer(Graph G,char v);//顶点位置
void ShowVerAdj(Graph *G);//查看顶点的邻接点
int FirstAdjVer(Graph *G ,int v);//第一邻接点
int NextAdjVer(Graph *G ,int v,int w);//下一邻接点
void NDV(ArcBox *p,int v,int w,int *n);//递归查找下一邻接点
void InitArcBoxmark(ArcBox *p);//初始化mark的值
void DFSGraph(Graph *G);//深度优先搜索图
void DFS(Graph *G,int v);//递归深度搜索
void BFSGraph(Graph *G);//广度优先搜索图
void InitQueue(Queue *Q);//初始化队列
void EnQueue(Queue *Q,VerBox *p);//入队
Status EmptyQueue(Queue Q);//队列是否为空
Status DeQueue(Queue *Q,VerBox **p);//出队
void DFSForest(Graph *G,CSNode **T);//图G深度优先生成树
void DFSTree(Graph *G,int v,CSNode *T);//递归生成树
void InOrderTraverseTree(Graph *G,CSNode *T);//中序遍历二叉树
void PreOrderTraverseTree(Graph *G,CSNode *T);//先序遍历二叉树
void BFSForest(Graph *G,CSNode **T);//图G广度优先生成树
void Searchv1(CSNode *T,int v1,CSNode **pr);//剃归搜索顶点v1在二叉树的结点
int main()
{
    Graph G;
    CSNode *DT,*BT;
    CreateGraph(&G);
    printf("图的邻接点信息如下：\n");
    ShowVerAdj(&G);
    printf("深度优先搜索信息如下:\n");
    DFSGraph(&G);
    printf("广度优先搜索信息如下:\n");
    BFSGraph(&G);
    /*深度优先生成二叉树*/
    DFSForest(&G,&DT);
    printf("深度优先搜索生成二叉树先序遍历:\n");
    PreOrderTraverseTree(&G,DT);putchar(10);
    printf("深度优先搜索生成二叉树中序遍历:\n");
    InOrderTraverseTree(&G,DT);putchar(10);
    /*广度优先生成二叉树*/
    printf("\n");
    BFSForest(&G,&BT);
    printf("广度优先搜索生成二叉树先序遍历:\n");
    PreOrderTraverseTree(&G,BT);putchar(10);
    printf("广度优先搜索生成二叉树中序遍历:\n");
    InOrderTraverseTree(&G,BT);putchar(10);
}
Status CreateGraph(Graph *G)//创建图
{
    int i,j,k,flaginfo;
    ArcBox *pnew;
    char v1,v2,c;
    printf("请输入顶点总数,边的总数,边是否含有其它信息(例:5,6,0):");
    //scanf("%d,%d,%d",&G->vernum,&G->arcnum,&flaginfo);
    Sleep(500);
    G->vernum=13;G->arcnum=13;flaginfo=0;
    printf("%d,%d,%d\n",G->vernum,G->arcnum,flaginfo);
    for(i=0;i<G->vernum;i++)
    {
        printf("请输入第%d个顶点的值:",i+1);
        //scanf(" %c",&(G->vertexs[i].data));
        Sleep(500);
        G->vertexs[i].data='A'+i;
        printf("%c\n",G->vertexs[i].data);
        G->vertexs[i].firstedge=NULL;
    }
    /*pf=fopen("F:\\C\\data.txt","r");
    if(pf==NULL)
    {
        printf("打开文件失败!\n");
        exit(-1);
    }*/
    for(k=0;k<G->arcnum;k++)
    {

        printf("请输入第%d条边的信息:",k+1);
        //scanf(" %c %c",&v1,&v2);
        //v1=fgetc(pf);
        //c=fgetc(pf);
        //v2=fgetc(pf);
        //c=fgetc(pf);
        Sleep(500);
        v1=Data[k][0];
        v2=Data[k][1];
        printf("(%c,%c)\n",v1,v2);
        i=LocateVer(*G,v1);
        j=LocateVer(*G,v2);
        if(i>=0 && j>=0)
        {
            pnew=(ArcBox *)malloc(1*sizeof(ArcBox));
            pnew->iver=i;
            pnew->jver=j;
            pnew->ilink=G->vertexs[i].firstedge;
            G->vertexs[i].firstedge=pnew;
            pnew->jlink=G->vertexs[j].firstedge;
            G->vertexs[j].firstedge=pnew;
            pnew->mark=FALSE;
        }
        else printf("顶点%c不存在！\n",i<0?v1:v2);
    }   
    return OK;
}
int LocateVer(Graph G,char v)//顶点位置
{
    int i=-1;
    for(i=0;i<G.vernum;i++)
    {
        if(toupper(G.vertexs[i].data)==toupper(v))
        {
            return i;
        }
    }
    return -1;
}
void ShowVerAdj(Graph *G)//查看顶点的邻接点
{
    int v,w;
    ArcBox *p;
    for(v=0;v<G->vernum;v++)
    {
        printf("[%d|%c]",v,G->vertexs[v].data);
        p=G->vertexs[v].firstedge;
        for(w=FirstAdjVer(G,v);w>=0;w=NextAdjVer(G,v,w))
        {
            printf("->[%d|%c]",w,G->vertexs[w].data);   
        }
        InitArcBoxmark(p);   
        printf("\n");
    }
}
int FirstAdjVer(Graph *G ,int v)
{
    ArcBox *p;
    int w=-1;
    p=G->vertexs[v].firstedge;
    if(p->iver==v)
    {   
        w=p->jver;
        p->mark=TRUE;
    }
    else if(p->jver==v)
    {
        w=p->iver;
        p->mark=TRUE;
    }
    return w;
}
int NextAdjVer(Graph *G,int v,int w)
{
    ArcBox *p;
    int n=-1;
    p=G->vertexs[v].firstedge;
    NDV(p,v,w,&n);
    return n;
}
void NDV(ArcBox *p,int v,int w,int *n)
{
    if((p->iver==v || p->jver==v) && (p->iver!=w && p->jver!=w) &&(p->mark==FALSE))
    {
        if(p->iver==v)
        {
            *n=p->jver;
            p->mark=TRUE;
        }
        else if(p->jver==v)
        {
            *n=p->iver;
            p->mark=TRUE;
        }
    }
    else
    {
        if(p->ilink!=NULL && *n==-1)
        {
            NDV(p->ilink,v,w,n);
        }
        if(p->jlink!=NULL && *n==-1)
        {
            NDV(p->jlink,v,w,n);
        }
    }
}
void InitArcBoxmark(ArcBox *p)//初始化mark的值
{
    p->mark=FALSE;
    if(p->ilink!=NULL)
    {
        InitArcBoxmark(p->ilink);        
    }
    if(p->jlink!=NULL)
    {
        InitArcBoxmark(p->ilink);
    }
}
void DFSGraph(Graph *G)
{
    int v;
    for(v=0;v<G->vernum;v++)
    {
        Visited[v]=FALSE;
    }
    for(v=0;v<G->vernum;v++)
    {
        if(Visited[v]==FALSE)
        {
            DFS(G,v);
        }
    }
    printf("\n");
}
void DFS(Graph *G,int v)
{   
    int w;
    Visited[v]=TRUE;
    printf("%c ",G->vertexs[v].data);
    for(w=FirstAdjVer(G,v);w>=0;w=NextAdjVer(G,v,w))
    {
        if(Visited[w]==FALSE)
        {
            DFS(G,w);
        }
    }
}
void BFSGraph(Graph *G)//广度优先搜索图
{
    int v,w,u;
    VerBox *p;
    Queue Q;
    for(v=0;v<G->vernum;v++)
    {
        Visited[v]=FALSE;
        InitArcBoxmark(G->vertexs[v].firstedge);
    }
    InitQueue(&Q);
    for(v=0;v<G->vernum;v++)
    {
        if(Visited[v]==FALSE)
        {
            Visited[v]=TRUE;
            printf("%c ",G->vertexs[v].data);
            EnQueue(&Q,&G->vertexs[v]);
            while(EmptyQueue(Q)==0)
            {
                DeQueue(&Q,&p);
                u=LocateVer(*G,p->data);
                for(w=FirstAdjVer(G,u);w>=0;w=NextAdjVer(G,u,w))
                {
                    
                    if(Visited[w]==FALSE)
                    {
                        printf("%c ",G->vertexs[w].data);
                        Visited[w]=TRUE;
                        EnQueue(&Q,&G->vertexs[w]);               
                    }
                }
            }
        }
    }
    printf("\n");
}
void InitQueue(Queue *Q)
{
    Q->front=Q->rear=(QNode *)malloc(1*sizeof(QNode));
    Q->front->data=NULL;
    Q->front->next=NULL;
    return;
}
void EnQueue(Queue *Q,VerBox *p)
{
    QNode *pnew;
    pnew=(QNode *)malloc(1*sizeof(QNode));
    pnew->data=p;
    Q->rear->next=pnew;
    Q->rear=pnew;
    pnew->next=NULL;
}
Status EmptyQueue(Queue Q)
{
    if(Q.rear==Q.front)
        return 1;
    else return 0;
}
Status DeQueue(Queue *Q,VerBox **p)
{
    QNode *pDe;
    if(EmptyQueue(*Q)==1)
    {
        printf("队列为空不能出队！\n");
        return ERROR;
    }
    pDe=Q->front->next;
    (*p)=pDe->data;
    Q->front->next=pDe->next;
    if(pDe==Q->rear)
    {
        Q->rear=Q->front;
    }
    free(pDe);
    return OK;
}
void DFSForest(Graph *G,CSNode **T)
{
    CSNode *p,*q;
    int v=0;
    (*T)=p=q=NULL;
    for(v=0;v<G->vernum;v++)
    {
        Visited[v]=FALSE;
        InitArcBoxmark(G->vertexs[v].firstedge);
    }
    for(v=0;v<G->vernum;v++)
    {
        if(Visited[v]==FALSE)
        {
            p=(CSNode *)malloc(1*sizeof(CSNode));
            p->data=LocateVer(*G,G->vertexs[v].data);
            p->firstchild=p->nextsibling=NULL;
            if((*T)==NULL)
            {
                (*T)=p;
            }
            else
            {
                q->nextsibling=p;
            }
            q=p;
            DFSTree(G,v,p);
        }
    }
}
void DFSTree(Graph *G,int v,CSNode *T)
{
    int first,w;
    CSNode *p,*q;
    Visited[v]=TRUE;
    first=TRUE;
    for(w=FirstAdjVer(G,v);w>=0;w=NextAdjVer(G,v,w))
    {
        if(Visited[w]==FALSE)
        {
            (p)=(CSNode *)malloc(1*sizeof(CSNode));
            (p)->data=LocateVer(*G,G->vertexs[w].data);
            (p)->firstchild=NULL;
            (p)->nextsibling=NULL;
            if(first==TRUE)
            {
                (T)->firstchild=p;
                first=FALSE;
            }
            else
            {
                q->nextsibling=p;
            }
            q=p;
            DFSTree(G,w,q);
        }
    }
}
void InOrderTraverseTree(Graph *G,CSNode *T)//中序遍历二叉树
{
    if(T!=NULL)
    {
        if(T->firstchild!=NULL)
        {
            InOrderTraverseTree(G,T->firstchild);
        }
        printf("%c ",G->vertexs[T->data].data);
        if(T->nextsibling!=NULL)
        {
            InOrderTraverseTree(G,T->nextsibling);
        }        
    }
}
void PreOrderTraverseTree(Graph *G,CSNode *T)//先序遍历二叉树
{
    if(T!=NULL)
    {

        printf("%c ",G->vertexs[T->data].data);        
        if(T->firstchild!=NULL)
        {
            InOrderTraverseTree(G,T->firstchild);
        }
        if(T->nextsibling!=NULL)
        {
            InOrderTraverseTree(G,T->firstchild);
        }        
    }
}
void BFSForest(Graph *G,CSNode **T)//图G广度优先生成树
{
    int v,w,first=TRUE,v1;
    CSNode *pnew,*p,*p1,*pN,*pr;
    VerBox *u;
    Queue Q;
    *T=NULL;
    InitQueue(&Q);
    for(v=0;v<G->vernum;v++)
    {
        Visited[v]=FALSE;
        InitArcBoxmark(G->vertexs[v].firstedge);
    }
    for(v=0;v<G->vernum;v++)
    {
        if(Visited[v]==FALSE)
        {
            Visited[v]=TRUE;
            pnew=(CSNode *)malloc(1*sizeof(CSNode));
            pnew->data=LocateVer(*G,G->vertexs[v].data);
            pnew->firstchild=pnew->nextsibling=NULL;
            if((*T)==NULL)
            {
                (*T)=pnew;
            }
            else
            {
                p->nextsibling=pnew;   
            }
            p=pnew;
            EnQueue(&Q,&G->vertexs[v]);
            while(EmptyQueue(Q)==0)
            {
                DeQueue(&Q,&u);
                v1=LocateVer(*G,u->data);
                first=TRUE;
                pr=pN=NULL;
                Searchv1(*T,v1,&pr);
                for(w=FirstAdjVer(G,v1);w>=0;w=NextAdjVer(G,v1,w))
                {   
                    if(Visited[w]==FALSE)
                    {
                        p1=(CSNode *)malloc(1*sizeof(CSNode));
                        p1->data=LocateVer(*G,G->vertexs[w].data);
                        p1->firstchild=NULL;
                        p1->nextsibling=NULL;
                        if(first==TRUE)
                        {
                            pr->firstchild=p1;
                            first=FALSE;
                        }
                        else
                        {
                            pN->nextsibling=p1;
                        }
                        pN=p1;
                        Visited[w]=TRUE;
                        EnQueue(&Q,&G->vertexs[w]);
                    }
                }
            }
        }
    }
}
void Searchv1(CSNode *T,int v1,CSNode **pr)
{
    if(T->data==v1)   
    {
        (*pr)=T;
    }
    else
    {
        if(T->firstchild!=NULL && (*pr)==NULL)
        {
            Searchv1(T->firstchild,v1,&(*pr));
        }
        if(T->nextsibling!=NULL && (*pr)==NULL)
        {
            Searchv1(T->nextsibling,v1,&(*pr));
        }
    }
}

[此贴子已经被作者于2017-5-27 21:23编辑过]

搜索更多相关主题的帖子: 信息　二叉树　include　
2017-05-27 21:22
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来　自：长长久久
等　级：贵宾
威　望：52
帖　子：5023
专家分：14003
注　册：2016-10-22
第 2 楼
 得分:3 
很久没弄数据结构了~不学习一下的话一时也看不出来~~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-05-27 23:49
renkejun1942
Rank: 14Rank: 14Rank: 14Rank: 14
来　自：不是这样
等　级：贵宾
威　望：33
帖　子：1645
专家分：5297
注　册：2016-12-1
第 3 楼
 得分:7 
程序代码：
void PreOrderTraverseTree(Graph *G,CSNode *T)//先序遍历二叉树
{
    if(T!=NULL)
    {

        printf("%c ",G->vertexs[T->data].data);        
        if(T->firstchild!=NULL)
        {
            InOrderTraverseTree(G,T->firstchild);//为什么是调用中序遍历函数？完全搞不懂意图。
        }
        if(T->nextsibling!=NULL)
        {
            InOrderTraverseTree(G,T->firstchild);
        }        
    }
}


[此贴子已经被作者于2017-5-28 00:00编辑过]


09：30 05/21 种下琵琶种子，能种活么？等待中……
21：50 05/27 没有发芽。
20：51 05/28 没有发芽。
23：03 05/29 没有发芽。
23：30 06/09 我有预感，要发芽了。
2017-05-27 23:58
zqszqs10
Rank: 1
等　级：新手上路
帖　子：14
专家分：3
注　册：2016-10-27
第 4 楼
 得分:0 
回复 3楼 renkejun1942
就是这儿出问题了，犯这种小错误还没发现。
2017-05-28 00:11
zqszqs10
Rank: 1
等　级：新手上路
帖　子：14
专家分：3
注　册：2016-10-27
第 5 楼
 得分:0 
回复 2楼 九转星河
你辛苦了！
2017-05-28 00:12
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来　自：长长久久
等　级：贵宾
威　望：52
帖　子：5023
专家分：14003
注　册：2016-10-22
第 6 楼
 得分:0 
回复 3楼 renkejun1942
原来这问题……花些时间看看应该可以看出来~话说你在二叉树蹉跎了好些岁月了~期待你什么时候更新一下~~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-05-28 00:13
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来　自：长长久久
等　级：贵宾
威　望：52
帖　子：5023
专家分：14003
注　册：2016-10-22
第 7 楼
 得分:0 
回复 5楼 zqszqs10
辛苦什么~其实我得要去看网上选修视频~今天(已经过了0点)下午要考试了~我其实都没怎么去看~~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-05-28 00:15
zqszqs10
Rank: 1
等　级：新手上路
帖　子：14
专家分：3
注　册：2016-10-27
第 8 楼
 得分:0 
回复 7楼 九转星河
加油，祝你考试顺利通过！我也觉得我在树和图上蹉跎了大量的时间，洗洗睡吧！
2017-05-28 00:24
renkejun1942
Rank: 14Rank: 14Rank: 14Rank: 14
来　自：不是这样
等　级：贵宾
威　望：33
帖　子：1645
专家分：5297
注　册：2016-12-1
第 9 楼
 得分:0 
回复 6楼 九转星河
不急，不急，慢慢来。

[此贴子已经被作者于2017-5-28 06:07编辑过]


09：30 05/21 种下琵琶种子，能种活么？等待中……
21：50 05/27 没有发芽。
20：51 05/28 没有发芽。
23：03 05/29 没有发芽。
23：30 06/09 我有预感，要发芽了。
2017-05-28 06:02
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来　自：长长久久
等　级：贵宾
威　望：52
帖　子：5023
专家分：14003
注　册：2016-10-22
第 10 楼
 得分:0 
回复 9楼 renkejun1942
以下是引用renkejun1942在2017-5-28 06:02:01的发言：

不急，不急，慢慢来。

感觉这样慢慢来能学得比牢固~现在看课时数据结构这一节就学那么一个学期~感觉在这么短的时间内很难做到精通的~按老师的学习进度来说~感觉很多东西学得很表面~没啥时间和精力深入消化~很多东西还需要自己自学和领悟的~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-05-28 06:43



参与讨论请移步原网站贴子：https://bbs.bccn.net/thread-477428-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有，并保留所有权利。
Powered by Discuz, Processed in 0.539347 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved