| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2092 人关注过本帖
标题:在图的广度遍历中用到的队列有问题,麻烦看一下
只看楼主 加入收藏
无妨无妨
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2015-6-8
收藏
 问题点数:0 回复次数:0 
在图的广度遍历中用到的队列有问题,麻烦看一下
这是我写的图的四个基本操作,创建和深度遍历我自己试了没有问题,可是我一用广度遍历就显示Acess Violation.麻烦各位看下我哪个地方出错了
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 100
#define true 1
#define false 0
typedef struct//图
{
    int edges[MAX][MAX];    //邻接矩阵
    int n;                  //顶点数
    int e;                  //边数
}Tu;
int visited[MAX];          //标记顶点是否被访问过
typedef struct QNode
{
    int data;
    struct QNode *next;
}QNode,*QPtr;

typedef struct LinkQueue{
    QPtr front;
    QPtr tail;
}LinkQueue;


void InitQ(LinkQueue Q);//初始化队列

void EnQueue(LinkQueue Q,int e);//从队尾插入元素

void DeQueue(LinkQueue Q,int e);//从队首删除元素

int QEmpty(const LinkQueue Q);//队列是否为空,为空返回1,否则返回0

int firstAjdVex(Tu G,int v);//得到第一个未被访问的相邻节点下标,若无,则返回-1

int nextAjdVex(Tu G,int v,int w);//得到下一个未被访问的相邻节点下标,若无,则返回-1


void InitQ(LinkQueue Q)//初始化队列
{
    Q.front = Q.tail = (QPtr)malloc(sizeof(struct QNode));
    if ( !Q.front )
    {
        printf("InitQ分配内存出错!\n");
        return ;
    }   
    Q.front->next = NULL;
    Q.tail->next=NULL;
}


void EnQueue(LinkQueue Q,int e)//从队尾插入元素
{
    QPtr q;
    q = (QPtr)malloc(sizeof(struct QNode));
    if ( !q )
    {
        printf("EnQueue分配内存出错!\n");
        return ;
    }
    q->data = e;
    q->next = NULL;
    Q.tail->next = q;  //如果是第一次插入,Q.front->next也指向了q
    Q.tail = q;
}


void DeQueue(LinkQueue Q,int e){//从队首删除元素
    QPtr q;
    if ( Q.front == Q.tail )
    {
        printf("DeQueue队列为空,不能删除元素!\n");
        return ;
    }
    q = Q.front->next;
    e = q->data;
    Q.front->next = q->next;
    if ( Q.tail == q )
        Q.tail = Q.front;
    free(q);
}


int QEmpty(const LinkQueue Q)//队列是否为空,为空返回1,否则返回0
{
    if ( Q.front == Q.tail )
    {
        return 1;
    }
    else
    {
        return 0;
    }
}

Tu creat()    //创建图
{
    int i;
    int x;
    int y;
    int s,t;                 //存储顶点编号
    int v;                   //存储边的权值
    Tu G;
    for(i=0;i<MAX;i++)
        visited[i]=false;
    printf("输入顶点数");
    scanf("%d",&x);
    G.n=x;
    printf("输入边数");
    scanf("%d",&y);
    G.e=y;
    for(i=0;i<G.e;i++)      //对矩阵相邻的边赋权值
    {
        printf("输入顶点编号及权值\n");
        scanf("%d %d %d",&s,&t,&v);   //输入边的顶点编号以及权值
        G.edges[s][t]=v;
        G.edges[t][s]=v;
    }
    return G;
}
void DFS(Tu G,int v)      //深度优先搜索
{
    int i,j;
    j=G.n;
    visited[v]=true;
    printf("%d\n",v);
    for(i=0;i<j;i++)       //访问与v相邻的未被访问过的结点
    {
        if(visited[i]==0)
        {
            DFS(G,i);
        }
    }
}

void BFS(Tu G)//广度优先遍历函数
{
    int i,w,v;
    LinkQueue Q;
    Q.tail=NULL;
    Q.front=NULL;
    InitQ(Q);
    v=0;

    for ( i = 0; i < G.n; i++ )
        visited[i] = 0;   //初始化访问标记数组

    for ( i = 0; i < G.n; i++ )
    {
        if ( visited[i]==false )
        {
            visited[i] = true;
            printf("%d",i);
            EnQueue(Q,i);
            while (!QEmpty(Q))
            {
                DeQueue(Q,v);
                for ( w = firstAjdVex(G,v); w >= 0; w = nextAjdVex(G,v,w) )
                {
                    if ( visited[w]==false)
                    {
                        visited[w] = true;
                        printf("%d",w);
                        EnQueue(Q,w);
                    }
                }
            }
        }

    }
   
}

int firstAjdVex(Tu G,int v)//得到第一个未被访问的相邻节点下标,若无,则返回-1
{
    int i;
    int j;
    j=G.n;
    for ( i = 0; i<j; i++ )
    {
        if ( visited[i]==false&&G.edges[v][i]>0)
            return i;
    }
    return -1;   
}



int nextAjdVex(Tu G,int v,int w)//得到下一个未被访问的相邻节点下标,若无,则返回-1
{
    int i;
    for ( i = w; i < G.n; i++ )
    {
        if ( visited[i]==0 && G.edges[v][i] > 0)
            return i;
    }
    return -1;
}
void Destory(Tu G)//销毁图
{
    int i;
    int j;
    for(i=0;i<G.n;i++)      
    {
        for(j=0;j<G.n;j++)
        {
            G.edges[i][j]=0;
        }
    }
    G.n=0;
    G.e=0;
}
void main(){
    Tu G;
    int x;
    for( ; ; ){
        printf("what would you want to do\n");
        printf("1.创建图\n");
        printf("2.深度遍历\n");
        printf("3.广度遍历\n");
        printf("4.销毁\n");
        for(;;){
            scanf("%d",&x);
            if(x<0||x>4)
                printf("输入错误");
            else
                break;
        }
        switch(x)
        {
        case 1:
            printf("图的创建\n");
            G=creat();
            break;
        case 2:
            printf("深度遍历\n");
            DFS(G,0);
            break;
        case 3:
            printf("广度遍历\n");
            BFS(G);
            break;
        case 4:
            printf("销毁\n");
            Destory(G);
            break;
        }
    }
}
搜索更多相关主题的帖子: false include 
2015-06-08 13:25
快速回复:在图的广度遍历中用到的队列有问题,麻烦看一下
数据加载中...
 
   



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

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