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

wangyuans

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. #define MAXVEX 20
   
5. #define MAX 10
   
6. typedef char VertexType;
   
7. 
   
8. //边表结点
   
9. typedef struct EdgeNode{
   
10.     int adjvex;  //邻接点在数组中的位置下标
    
11.     struct EdgeNode *next;  //指向下一个邻接点的指针
    
12. }EdgeNode;
    
13. 
    
14. //顶点表结点
    
15. typedef struct VertexNode{
    
16.     VertexType data;  //顶点的数据域
    
17.     EdgeNode *firstedge;  //指向邻接点的指针
    
18. }VertexNode,AdjList[MAXVEX];  //存储各链表头结点的数组
    
19. 
    
20. typedef struct{
    
21.     AdjList adjlist;  //存储图中顶点及各邻接点的数组
    
22.     int vexnum,arcnum;  //记录图中顶点数和边或弧数
    
23. }GraphAdjList;
    
24. 
    
25. //创建邻接表
    
26. void Create(GraphAdjList *G){
    
27.     //总顶点个数，总边数
    
28. 
    
29.     int i,j,k;
    
30.     EdgeNode *p;
    
31. 
    
32.     printf("输入顶点数和边数:\n");
    
33.     scanf("%d%d",&G->vexnum,&G->arcnum);  //获取顶点数和边数
    
34. 
    
35.     //输入顶点信息
    
36.     printf("输入顶点信息:\n");
    
37.     for(i=0;i<G->vexnum;i++){
    
38.         getchar();
    
39.         scanf("%c",&G->adjlist[i].data);  //获取顶点值
    
40.         G->adjlist[i].firstedge=NULL;           //将指向边表的指针初始化,置空
    
41.     }
    
42. 
    
43.     //建立边表
    
44.     printf("输入边(Vi,Vj)中的下标i,j:\n");
    
45.     for(k=0;k<G->arcnum;k++){
    
46.         scanf("%d%d",&i,&j);  //输入i,j 在图中有i指向j
    
47.         p=(EdgeNode *)malloc(sizeof(EdgeNode));
    
48.         p->adjvex=j;                                //存储弧头
    
49.         p->next=G->adjlist[i].firstedge;            //头插法插入边结点
    
50.         G->adjlist[i].firstedge=p;
    
51. 
    
52.         p=(EdgeNode *)malloc(sizeof(EdgeNode));
    
53.         p->adjvex=i;                                //存储弧头
    
54.         p->next=G->adjlist[j].firstedge;            //头插法插入边结点
    
55.         G->adjlist[j].firstedge=p;  //把新建的结点链接在顶点后面
    
56.     }
    
57. }
    
58. void PrintfList(GraphAdjList *G){
    
59.     //打印邻接表
    
60.         int i;
    
61.         EdgeNode *p;
    
62.     printf("邻接表为:\n");
    
63.     for(i=0;i<G->vexnum;i++){
    
64.         p=G->adjlist[i].firstedge;
    
65.         while(p){
    
66.             printf("(%c,%c)",G->adjlist[i].data,G->adjlist[p->adjvex].data);
    
67.             p=p->next;
    
68.         }
    
69.         printf("\n");
    
70. 
    
71.     }
    
72.                         getchar();
    
73. }
    
74. 
    
75. int visited[MAX];
    
76. 
    
77. //深度优先搜索
    
78. void DFS(GraphAdjList *G,int vi){
    
79.         int v;
    
80.         EdgeNode *p;
    
81.         visited[vi] = 1;  //0没有被访问过，1访问过
    
82.         printf("%d：%s",vi , G->adjlist[vi].data);  //问题可能出现在这里！！！
    
83. 
    
84.         p = G->adjlist[vi].firstedge;
    
85.         while(p != NULL)
    
86.         {
    
87.                 v = p->adjvex;
    
88.                 if(visited[v] == 0)
    
89.                 {
    
90.                         DFS(G,v);
    
91.                 }
    
92.                 p = p->next;
    
93.         }
    
94. }
    
95. 
    
96. //深度优先遍历
    
97. void DFSTraverse(GraphAdjList *G){
    
98.         int vi;
    
99.         printf("深度优先遍历：\n");
    
100.         for(vi = 0;vi < G->vexnum;vi++)
     
101.         {
     
102.                 visited[vi] = 0;
     
103.         }
     
104.         for(vi = 0;vi < G->vexnum;vi++)
     
105.         {
     
106.                 if (visited[vi] == 0)
     
107.                 {
     
108.                         DFS(G,vi);
     
109.                 }
     
110.         }
     
111. }
     
112. int main(){
     
113. 
     
114.     GraphAdjList G;
     
115.     Create(&G);
     
116.         PrintfList(&G);
     
117.         DFSTraverse(&G);
     
118.         getchar();
     
119.         return 0;
     
120. }
     

复制代码

运行的时候会中断，可能是深度优先搜索里面的输入语句有问题，因为我把那一句注释掉程序就不会中断了，这一句是我看书上的代码，不知道怎么改，改过但是不正确。
中断时候报的是：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类型的

若雨心晨

可以

空间和空间

太强了