回 帖 发 新 帖 刷新版面

主题:[讨论]邻接多重链表的深度优先遍历和广度优先遍历

下面是我写的数据结构上的一道关于对邻接多重表的遍历的程序,采用深度优先遍历和广度优先遍历并打印结点访问序列和相应生成树的边集。用gcc编译时提出了一大堆警告,但我检查源程序后找不出该如何匹配,请帮帮忙。下面是源代码,附件中是编译的截图.

[code=c]
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_VERTEX_NUM 30
#define CHNUM   50
#define MAX 1000

int visited[MAX_VERTEX_NUM];   //访问标志数组

typedef struct storage{
    char name[CHNUM];
}storage[MAX];

typedef struct EBox{
    int mark;       //访问标记
    int ivex, jvex;     //该边依附的两个顶点的位置
    struct EBox *ilink, *jlink;     //分别指向依附这两个顶点的下一条边
}EBox;

typedef struct VexBox{
    char *name;
    EBox *firstedge;    //指向第一条依附该顶点的边
}VexBox;

typedef struct {
    VexBox adjmulist[MAX_VERTEX_NUM];
    int vexnum, edgenum;    //无向图的当前顶点数和边数
}AMLGraph;  

typedef struct QNode{
    int num;
    struct QNode *next;
}QNode, *QueuePtr;

typedef struct LinkQueue{
    QueuePtr front;     
    QueuePtr rear;
}LinkQueue;


int LocateVex(AMLGraph Graph, char *name);    //返回顶点*name在图Graph中的位置
void CreateAMLGraph(AMLGraph *Graph);   //构造连通的无向图

void DFSTraverse(AMLGraph Graph, int starting);      //对图Graph作深度优先遍历
void DFS(AMLGraph Graph, int v);    
//从第v个顶点出发递归地深度优先遍历图Graph并打印节点访问序列和相应生成树的边集 

void InitQueue(LinkQueue *Q);       //初始化辅助队列
void EnQueue(LinkQueue *Q, int v);  //v入队列
int DeQueue(LinkQueue *Q);  //队头元素出队并置为u
int QueueEmpty(LinkQueue Q);    //判断队列是否为空,若为空,返回1,否则返回0
void BFSTraverse(AMLGraph Graph, int starting); 
//按广度优先非递归遍历图Graph并打印节点访问序列和相应生成树的边集

int main(){
    AMLGraph Graph;
    LinkQueue Q;
    char *name;
    int vertex;
    int i, starting;

    CreateAMLGraph(&Graph);     
    
    printf("Please indicate the starting vertex using DFSTraverse method:\t");
    scanf(" %s", name);
    starting = LocateVex(Graph, name);
    DFSTraverse(Graph, starting);

    printf("Please indicate the starting vertex using BFSTraverse method:\t");
    scanf(" %s", name);
    starting = LocateVex(Graph, name);
    BFSTraverse(Graph, starting);

    return 0;
}


//返回顶点*name在图Graph中的位置
int LocateVex(AMLGraph Graph, char *name){
    int i;

    for (i = 0; i < Graph.vexnum; i++)
        if (strcmp(name, Graph.adjmulist[i].name))
            return i;
    return -1;
}


//构造连通的无向图
void CreateAMLGraph(AMLGraph *Graph){
    int i, j, k;
    char *v1, *v2;
    EBox *p, *tmp;

    printf("Please enter the number of vertex and edge:\t");
    scanf("%d %d", &Graph->vexnum, &Graph->edgenum);

    printf("Please enter the data of each vertex:\n");
    for (i = 0; i < Graph->vexnum; i++){             //构造表头向量
        scanf("%s", Graph->adjmulist[i].name);       //输入顶点值
        Graph->adjmulist[i].firstedge = NULL;        //初始化指针
    }

    printf("Please enter the two vertexs of each edge:\n");
    for (k = 0; k < Graph->edgenum; k++){            //输入各边并构造邻接多重表
        scanf("%s %s", v1, v2);                   //输入一条边的两个端点
        i = LocateVex(*Graph, v1);
        j = LocateVex(*Graph, v2);

    if (!(p = (EBox *) malloc(sizeof(EBox)))){
        printf("No enough memory!\n");
        exit (0);
    }  

    p->mark = 0;
    p->ivex = i;
    p->jvex = j;
    p->ilink = p->jlink = NULL;

    if (Graph->adjmulist[i].firstedge == NULL)
        Graph->adjmulist[i].firstedge = p;
    else if (Graph->adjmulist[i].firstedge != NULL){
        tmp = Graph->adjmulist[i].firstedge->ilink;
        while (tmp->ilink != NULL)
            tmp = tmp->ilink;
        tmp = p;
    }
    else if (Graph->adjmulist[j].firstedge == NULL)
        Graph->adjmulist[j].firstedge = p;
    else if (Graph->adjmulist[j].firstedge != NULL){
        tmp = Graph->adjmulist[j].firstedge->jlink;
        while (tmp->jlink != NULL)
            tmp = tmp->jlink;
        tmp = p;
    }
    }
}


//对图Graph作深度优先遍历
void DFSTraverse(AMLGraph Graph, int starting){
    int i;

    for (i = 0; i < Graph.vexnum; i++)
        visited[i] = 0;
    if (!visited[starting])     
        DFS(Graph, starting);       //对指定的顶点调用DFS

    for (i = 0; i < Graph.vexnum; i++){
        if (i != starting && !visited[i])
            DFS(Graph, i);      //对除指定的顶点外未访问的顶点调用DFS
    }
}


//从第v个顶点出发递归地深度优先遍历图Graph,并打印节点访问序列和相应生成树的边集
void DFS(AMLGraph Graph, int v){
    storage stor;
    EBox *tmp = Graph.adjmulist[v].firstedge;
    int adj,i, indicator = 0;
    int flag = 0;   //标志变量,0表示ivex,1表示jvex;
   
    stor[indicator].name[CHNUM] = *Graph.adjmulist[v].name;
    
    visited[v] = 1;
    
    adj = tmp->jvex;

    while (adj >= 0){
        //对v的尚未访问的邻接顶点now递归调用DFS
        indicator++;
        if (!visited[adj])
            DFS(Graph, adj);

        stor[indicator].name[CHNUM] = *Graph.adjmulist[adj].name; 
        
        //通过对标志变量flag的判断来决定下个邻接点
        if (!flag){
            tmp = tmp->jlink;
            adj = tmp->ivex;
            flag = 1;
        }
        else{
            tmp = tmp->ilink;
            adj = tmp->jvex;
            flag = 0;
        }
    }
    stor[indicator+1].name[CHNUM] = "Empty";

    //打印访问节点次序
    printf("Print the sequence of calling vertex using DFSTraverse:\v");
    for (i = 0; stor[i].name[CHNUM] != "Empty"; i++)
        printf("%s\t", stor[i].name[CHNUM]);

    //打印相应生成树的边集
    printf("Print the set of called edges:\v");
    for (i = 1; stor[i].name[CHNUM] != "Empty"; i++)
        printf("%s----%s\t", stor[i-1].name[CHNUM], stor[i].name[CHNUM]);
}


//初始化辅助队列
void InitQueue(LinkQueue *Q){
    Q->front = Q->rear = (QueuePtr) malloc(sizeof(QNode));
    if (!Q->front){
        printf("No enough memory!\n");
        exit(0);
    }
}

//v入队列
void EnQueue(LinkQueue *Q, int v){
    QueuePtr p = (QueuePtr) malloc(sizeof(QNode));
    if (!p){
        printf("No enough memory!\n");
        exit(0);
    }

    p->num = v;
    p->next = NULL;
    Q->rear->next = p;
    Q->rear = p;
}

//队头元素出队
int DeQueue(LinkQueue *Q){
    QueuePtr p;
    int tmp;
    if (Q->front == Q->rear)
        exit (-1);

    p = Q->front->next;
    tmp = p->num;
    Q->front->next = p->next;
    if (Q->rear == p)
        Q->rear = Q->front;
    
    free(p);

    return tmp;
}


//判断队列是否为空,若为空,返回1,否则返回0
int QueueEmpty(LinkQueue Q){
    if (Q.front == Q.rear)
        return 1;
    else
        return 0;
}


//按广度优先非递归遍历图Graph,并打印节点访问序列和相应生成树的边集
void BFSTraverse(AMLGraph Graph, int starting){
    storage stor1;
    EBox *tmp = Graph.adjmulist[starting].firstedge;
    int adj, i, u, indicator = 1;
    LinkQueue Q;

    for (i = 0; i < Graph.vexnum; i++)
        visited[i] = 0;

    InitQueue(&Q);

    
    stor1[indicator-1].name[CHNUM] = *Graph.adjmulist[starting].name;
    adj = tmp->jvex;
    stor1[indicator].name[CHNUM] = *Graph.adjmulist[adj].name;

    EnQueue(&Q, adj);
    while (!QueueEmpty(Q)){
        u = DeQueue(&Q);
        tmp = tmp->ilink;
        adj = tmp->jvex;
        while (adj >= 0){
            indicator++;
            visited[adj] = 1;
            EnQueue(&Q, adj);
            stor1[indicator].name[CHNUM] = *Graph.adjmulist[adj].name;
            tmp = tmp->ilink;
            adj = tmp->jvex;
        }
    }
    stor1[++indicator].name[CHNUM] = "Next";       //标志从指定结点开始的广度优先搜索结束

    for (i = 0; i < Graph.vexnum; i++){
        if (!visited[i]){
            indicator++;
            visited[i] = 1;
            stor1[indicator].name[CHNUM] = *Graph.adjmulist[i].name;
            EnQueue(&Q, i);
            while (!QueueEmpty(Q)){
                u = DeQueue(&Q);
                tmp = tmp->ilink;
                adj = tmp->jvex;
                while (adj >= 0){
                    indicator++;
                    visited[adj] = 1;
                    EnQueue(&Q, adj);
                    stor1[indicator].name[CHNUM] = Graph.adjmulist[adj].name;
                    tmp = tmp->ilink;
                    adj = tmp->jvex;
                }
            }
        }
        stor1[++indicator].name[CHNUM] = "Next";       //标志从这个顶点开始的广度优先搜索结束
    }
    stor1[++indicator].name[CHNUM] = "Empty";          //标志广度优先搜索结束

    //打印访问结点次序
    printf("Print the sequentce of calling vertex using BFSTraverse:\n");
    for (i = 0; stor1[i].name[CHNUM] != "Empty"; i++ ){
        if (stor1[i].name[CHNUM] != "Next")
            printf("%s\t", stor1[i].name[CHNUM]);
    }

    //打印相应生成树的边集
    printf("Print the set of called edges:\n");
    int temp = 0;
    for (i = 1; stor1[i].name[CHNUM] != "Empty"; i++){
        if (stor1[i].name[CHNUM] != "Next")
            printf("%s----%s\t", stor1[temp].name[CHNUM], stor1[i].name[CHNUM]);
        else
            temp = ++i;
    }
}
[/code]

回复列表 (共8个回复)

沙发

where is 附件……

板凳

根据报错修改你的错误就行了。
估计粗心的比较多,比如Locate的调用应该是LocateVex吧?
等等等等

3 楼


不好意思,发帖时有些错误没发上附件。下午我又修改了下程序,以下的是修改后的代码。怎么上传附件?刚才我又修改了第一个帖子,还是不能发附件。我感觉提示的warning不知该如何处理,比如它说在DeQueue、EnQueue函数传递的参数类型不对,给字符数组赋值时我用   "字符串"  形式却提示assignment makes integer from pointer without a cast,使用strcmp函数时,提示comparision between pointer and integer.

由于字数太多,我把修改后的程序放在下一个回复中.

4 楼

现在不知怎么,把源代码贴上去提示字数太多,但修改的部分只有几个,麻烦您帮我看下刚才的问题。

5 楼


现在不知怎么,把源代码贴上去提示字数太多,但修改的部分只有几个,麻烦您帮我看下刚才的问题。

6 楼

谢谢提醒,但编译时提出的几个warning我搞不明白该如何处理,请帮帮忙。

7 楼

把编译报的错的文本贴上来总会吧,别告诉我们你用TC编的

8 楼

修改后的代码用gcc编译后的结果是:

Graph_Traverse.c: In function ‘DFS’:
Graph_Traverse.c:190: warning: assignment makes integer from pointer without a cast
Graph_Traverse.c:194: warning: comparison between pointer and integer
Graph_Traverse.c:199: warning: comparison between pointer and integer
Graph_Traverse.c: In function ‘BFSTraverse’:
Graph_Traverse.c:286: warning: assignment makes integer from pointer without a cast
Graph_Traverse.c:302: warning: assignment makes integer from pointer without a cast
Graph_Traverse.c:308: warning: assignment makes integer from pointer without a cast
Graph_Traverse.c:310: warning: assignment makes integer from pointer without a cast
Graph_Traverse.c:314: warning: comparison between pointer and integer
Graph_Traverse.c:315: warning: comparison between pointer and integer
Graph_Traverse.c:322: warning: comparison between pointer and integer
Graph_Traverse.c:323: warning: comparison between pointer and integer

我来回复

您尚未登录,请登录后再回复。点此登录或注册