无向图的建立（邻接表）、遍历（深度优先）

wangyuans

#include <stdio.h>
#include <stdlib.h>

#define MAXVEX 20
#define MAX 10
typedef char VertexType;

//边表结点 
typedef struct EdgeNode{
    int adjvex;  //邻接点在数组中的位置下标
    struct EdgeNode *next;  //指向下一个邻接点的指针
}EdgeNode;

//顶点表结点
typedef struct VertexNode{
    VertexType data;  //顶点的数据域
    EdgeNode *firstedge;  //指向邻接点的指针
}VertexNode,AdjList[MAXVEX];  //存储各链表头结点的数组

typedef struct{
    AdjList adjlist;  //存储图中顶点及各邻接点的数组
    int vexnum,arcnum;  //记录图中顶点数和边或弧数
}GraphAdjList;

//创建邻接表
void Create(GraphAdjList *G){
    //总顶点个数，总边数

    int i,j,k;
    EdgeNode *p;

    printf("输入顶点数和边数:\n");
    scanf("%d%d",&G->vexnum,&G->arcnum);  //获取顶点数和边数

    //输入顶点信息
    printf("输入顶点信息:\n");
    for(i=0;i<G->vexnum;i++){
        getchar();
        scanf("%c",&G->adjlist[i].data);  //获取顶点值
        G->adjlist[i].firstedge=NULL;           //将指向边表的指针初始化,置空 
    } 

    //建立边表
    printf("输入边(Vi,Vj)中的下标i,j:\n"); 
    for(k=0;k<G->arcnum;k++){
        scanf("%d%d",&i,&j);  //输入i,j 在图中有i指向j
        p=(EdgeNode *)malloc(sizeof(EdgeNode));
        p->adjvex=j;                                //存储弧头 
        p->next=G->adjlist[i].firstedge;            //头插法插入边结点 
        G->adjlist[i].firstedge=p;

        p=(EdgeNode *)malloc(sizeof(EdgeNode));
        p->adjvex=i;                                //存储弧头 
        p->next=G->adjlist[j].firstedge;            //头插法插入边结点 
        G->adjlist[j].firstedge=p;  //把新建的结点链接在顶点后面
    }
}
void PrintfList(GraphAdjList *G){
    //打印邻接表
        int i;
        EdgeNode *p;
    printf("邻接表为:\n");
    for(i=0;i<G->vexnum;i++){
        p=G->adjlist[i].firstedge;
        while(p){
            printf("(%c,%c)",G->adjlist[i].data,G->adjlist[p->adjvex].data);
            p=p->next;
        }
        printf("\n");

    } 
                        getchar();
}

int visited[MAX];

//深度优先搜索
void DFS(GraphAdjList *G,int vi){
        int v;
        EdgeNode *p;
        visited[vi] = 1;  //0没有被访问过，1访问过
        printf("%d：%s",vi , G->adjlist[vi].data);  //问题可能出现在这里！！！

        p = G->adjlist[vi].firstedge;
        while(p != NULL)
        {
                v = p->adjvex;
                if(visited[v] == 0)
                {
                        DFS(G,v);
                }
                p = p->next;
        }
}

//深度优先遍历
void DFSTraverse(GraphAdjList *G){
        int vi;
        printf("深度优先遍历：\n");
        for(vi = 0;vi < G->vexnum;vi++)
        {
                visited[vi] = 0;
        }
        for(vi = 0;vi < G->vexnum;vi++)
        {
                if (visited[vi] == 0)
                {
                        DFS(G,vi);
                }
        }
}
int main(){

    GraphAdjList G;
    Create(&G);
        PrintfList(&G);
        DFSTraverse(&G);
        getchar();
        return 0;
}

运行的时候会中断，可能是深度优先搜索里面的输入语句有问题，因为我把那一句注释掉程序就不会中断了，这一句是我看书上的代码，不知道怎么改，改过但是不正确。
中断时候报的是：0x5E45ED6C (msvcr110d.dll) (图.exe 中)处有未经处理的异常: 0xC0000005: 读取位置 0x00000031 时发生访问冲突。

wangyuans

问题已解决，printf("%d：%s",vi , G->adjlist[vi].data);这一行改为printf("%d：%c",vi , G->adjlist[vi].data);因为我前面定义的data是VertexType类型的

若雨心晨

可以

空间和空间

太强了