一翀 2019-06-30 11:00 采纳率: 0%
浏览 745

c语言,建立无向图进行广度优先遍历产生问题

c语言,建立无向图进行广度优先遍历但是不论从哪个头开始,都只输出起始结点A的邻接结点,查了好久没发现错误,请大神帮忙


#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define x 10

typedef struct Head{//构建结点 
    struct Head *next;
    int num;//头结点编号,如A-0,B-1,......
    int weight;//边权重 
}Head;

typedef struct Node{//构建头 
    struct Head *head;
    char name;//name代表头结点的名字 
}good,Adj[x];

typedef struct{//构建单链表
    Adj Adjlist;
    int m,n;//m边个数为17,n结点个数为10
}undigraph;

Head* Creat(){//创建一个结点 
    Head *node = (Head *)malloc(sizeof(Head));//为结 点分配空间 
    return node;
}

int readfile(char *file_name_path)//读取文件数据,file_name_path为文件路径。 
{                                 //这里因为无向图不是特别复杂,我打算用列表读入数据        
    char b[100];
    FILE *fp;
    fp = fopen(file_name_path,"r");
    fscanf(fp,"%[^\n]", b);//利用正则表达式以换行符为结尾读取数据
    printf("内容为:\n%s\n",b);
    fclose(fp);
}

void creatUndigraph(undigraph *L){//创建无向图 


    int n = 10;//结点个数为10
    int m = 17;//边个数为17

//  也可利用scanf进行人机交互 ,则下方n和m都要替换为L->n和L->m 
//  printf("输入结点个数“);
//  scanf("%d",&L->n);
//  printf("输入边个数“);
//  scanf("%d",&L->m);

    //建立头表
    char head_name[] = "ABCDEFGHIJ";//头结点名称 
    char edges_relationship[]= "0102060512192627233435363845567889";//为两个相邻结点的下标集合,2个为一组代表一对有邻接关系的结点 
    int weight[] = {2,5,1,3,2,5,3,3,4,2,3,5,6,3,1,4,7};//为与边相对应的权重 

    //printf("输入头结点名字:\n");
    for(int i = 0;i<n;i++)
    {
        L->Adjlist[i].name = head_name[i];
        //scanf(" %c",&L->Adjlist[i].name);//(若采用人机交互)%c前要加一个空格,来输入n个字符,否则只能输入n/2个字符 
        L->Adjlist[i].head = NULL;
    }

    //建立边关系 
    for(int j = 1;j<1+m;j++)
    {   
        //printf("输入两个邻接结点的2个下标:\n");
        Head *node_head;
        Head *node_end;
        node_head = Creat();
        node_end = Creat();//创建头尾结点 
        node_head->num = int(edges_relationship[2*j-2]-48);
        node_end->num = int(edges_relationship[2*j-1]-48);//输入两个邻接结点的2个下标
        node_end->weight =  weight[j-1];
        node_head->weight =  weight[j-1];//输入边权重 

        //scanf("%d",&node_head->num);//若采用人机交互)输入开始结点编号 
        //scanf("%d",&node_end->num);//若采用人机交互)输入结尾结点编号 

        node_head->next = L->Adjlist[node_end->num].head;
        L->Adjlist[node_end->num].head = node_head;

        node_end->next = L->Adjlist[node_head->num].head;
        L->Adjlist[node_head->num].head = node_end;
    }

    //打印 
    printf("邻接表为:\n");
    for(int y = 0;y<n;y++){
        Head *p;
        p=Creat();
        p = L->Adjlist[y].head;
        while(p){
            printf("(%c,%c),weight:%d\n",L->Adjlist[y].name,L->Adjlist[p->num].name,p->weight);
            p=p->next;
        }
    }
}

typedef struct{//定义环形列表
    int data[x]; //存放列表中元素 
    int front,rear; //定义头尾指针 
}circle;

void Initial(circle *&d){//初始化,d为指针 
    d = (circle *)malloc(sizeof(circle)) ;
    d->front = d->rear = 0;
}

bool enter(circle *&d,int z){//加入队列,不二判断正确与否,正确则返回true,错误返回false 
    if((d->rear+1)%x==d->front)
        return false;
    d->rear = (d->rear+1)%x;
    d->data[d->rear] = z;
    return true;    
}

bool out(circle *&d,int z){//出队列,不二判断正确与否,正确则返回true,错误返回false 
    if(d->front==d->rear)
        return false;
    d->front = (d->front+1)%x;
    z = d->data[d->front];
    return true; 
}

bool empty(circle *d){//判断是否为空列表
    return(d->front==d->rear); 
}

void wide(undigraph *L,int t){//创建广度优先遍历 ,Z为出发点编号 
    int r;
    int j;
    Head *p;
    circle *bi;   //环形队列 
    Initial(bi);  //初始化 
    int c[x];     //定义访问放入此数组中 
    for(r = 0;r<10/*即L->n,我并未进行人机交互,所以此处为结点个数n=10*/;r++)
        c[r] = 0;
    printf("%c",L->Adjlist[t].name);
    c[t] = 1;        //已访问赋值为1
    enter(bi,t);
    while(!empty(bi))//判断是否为空列表
    {//printf("第\n");
        out(bi,j);             //j顶点出队 
        p = L->Adjlist[j].head;
        while(p!=NULL)
        {//printf("p的num:%d\n",p->num);
            if(c[p->num]==0)
            {
                printf(" %c",L->Adjlist[p->num].name);
                c[p->num] = 1;
                enter(bi,p->num);//加入队列 
                //printf("杀p的num:%d\n",p->num);
            }
            p = p->next;
        }   
    } 
    printf("\n");
} 

int a[x] = {0};                         //定义全局数组 
void depth(undigraph *L,int z){         //创建深度优先遍历,z为出发点编号 
    Head *p;    
    a[z] = 1;                           //已遍历结点赋值为1 
    printf(" %c",L->Adjlist[z].name);
    p = L->Adjlist[z].head;
    while(p!=NULL)
    {
        if(a[p->num]==0)
            depth(L,p->num);            //递归访问顶点的下一点 
        p = p->next;
    }
}

int main() 
{
    undigraph L;
    creatUndigraph(&L); 
    printf("\n广度优先遍历为:");
    wide(&L,);//从下标为0(A)的结点开始广度优先遍历
    printf("\n深度优先遍历为:");
    depth(&L,0);//从下标为0(A)的结点开始遍深度优先历
    return 0;
}

在wide(&L,数字),替换数字,改变开始遍历的结点,结果都是这个结点+邻接的4个结点+F G B C,请问怎么搞(无向图图片(https://img-ask.csdn.net/upload/201906/30/1561863882_448148.png)
图片说明
这是出问题的运行结果图片说明https://img-ask.csdn.net/upload/201906/30/1561872516_966750.png

  • 写回答

1条回答

  • 一翀 2019-07-01 20:16
    关注

    我找到问题所在了只需要把

    bool out(circle *&d,int z)```
    改为
    
    
    ```bool out(circle *&d,int &z)```
    在z前加&取内容,就解决了
    我对比了好几天下午,心态都崩了,数据结构还是不容易啊!
    
    
    评论

报告相同问题?

悬赏问题

  • ¥15 DIFY API Endpoint 问题。
  • ¥20 sub地址DHCP问题
  • ¥15 delta降尺度计算的一些细节,有偿
  • ¥15 Arduino红外遥控代码有问题
  • ¥15 数值计算离散正交多项式
  • ¥30 数值计算均差系数编程
  • ¥15 redis-full-check比较 两个集群的数据出错
  • ¥15 Matlab编程问题
  • ¥15 训练的多模态特征融合模型准确度很低怎么办
  • ¥15 kylin启动报错log4j类冲突