数据结构---图

素颜马尾好姑娘i 2022-05-23 13:56 189阅读 0赞

### main.cpp ###

--------------------

1.  \#include”Graph.h”  
2.  int main()\{  
3.      GraphAdjList G;  
4.      int sp,n;  
5.      while(true)\{  
6.          menu();  
7.          printf(”请输入你的操作:  ”);  
8.          scanf(”%d”,&sp);  
9.          if(sp==6)break;  
10.         switch(sp)\{  
11.             case 1:       
12.                 GreateALGraphF(&G);  
13.                 DispGraphAdjList(&G);  
14.                 break;  
15.             case 2:  
16.                 GreateALGraph(&G);  
17.                 DispGraphAdjList(&G);     
18.                 break;  
19.             case 3:  
20.                 DispGraphdu(&G);  
21.                 break;  
22.             case 4:  
23.                 DFSTraverse(G);  
24.                 break;  
25.             case 5:  
26.                 BFSTraverse(G);  
27.                 break;  
28.         \}  
29.     \}  
30.     system(”pause”);  
31.     return 0;  
32.       
33. \}

### Graph.cpp ###

--------------------

1.  \#include “GRaph.h”  
2.  void menu()\{  
3.      printf(”\\t\\t\\t 1,有向图邻接表的创建并输出!\\n”);  
4.      printf(”\\t\\t\\t 2,无向图邻接表的创建并输出!\\n”);  
5.      printf(”\\t\\t\\t 3,有向图邻接表的个顶点的度!\\n”);  
6.      printf(”\\t\\t\\t 4,无向图邻接表的深度优先遍历!\\n”);  
7.      printf(”\\t\\t\\t 5,无向图邻接表的广度优先遍历!\\n”);  
8.      printf(”\\t\\t\\t 6,退出\\n”);  
9.  \}  
10. void GreateALGraph(GraphAdjList \*G)\{  
11.     int i,j,k;  
12.     EdgeNode \*e;  
13.     printf(”输入定点数和边数:\\n”);  
14.     scanf(”%d,%d”,&G->numVertexes,&G->numEdges);  
15.   
16.     for(i = 0;i<G->numVertexes;i++)\{  
17.         printf(”请输入顶点信息\\n”);  
18.         scanf(”%s”,&G->adjList\[i\].data);  
19.         G->adjList\[i\].firstedge=NULL;  
20.     \}  
21.     for(k = 0;k < G->numEdges;k++)\{  
22.         printf(”输入边（vi,vj）上的顶点序号:\\n”);  
23.         scanf(”%d,%d”,&i,&j);  
24.         e= (EdgeNode\*)malloc(sizeof(EdgeNode));  
25.         e->adjvex=j;  
26.         e->next=G->adjList\[i\].firstedge;  
27.         G->adjList\[i\].firstedge=e;  
28.         e=(EdgeNode\*)malloc(sizeof(EdgeNode));  
29.         e->adjvex=i;  
30.         e->next=G->adjList\[j\].firstedge;  
31.         G->adjList\[j\].firstedge=e;  
32.     \}  
33. \}  
34. void GreateALGraphF(GraphAdjList \*G)\{  
35.     int i,j,k;  
36.     EdgeNode \*e;  
37.     printf(”输入定点数和边数:\\n”);  
38.     scanf(”%d,%d”,&G->numVertexes,&G->numEdges);  
39.   
40.     for(i = 0;i<G->numVertexes;i++)\{  
41.         printf(”请输入顶点信息\\n”);  
42.         scanf(”%s”,&G->adjList\[i\].data);  
43.         G->adjList\[i\].firstedge=NULL;  
44.     \}  
45.     for(k = 0;k < G->numEdges;k++)\{  
46.         printf(”输入边（vi,vj）上的顶点序号:\\n”);  
47.         scanf(”%d,%d”,&i,&j);  
48.         e= (EdgeNode\*)malloc(sizeof(EdgeNode));  
49.         e->adjvex=j;  
50.         e->next=G->adjList\[i\].firstedge;  
51.         G->adjList\[i\].firstedge=e;  
52.   
53.     \}  
54. \}  
55.   
56. void DispGraphAdjList(GraphAdjList \*G)    
57. \{    
58.     int i;    
59.     EdgeNode \*p;    
60.     printf(”\\n”);  
61.     printf(”图的邻接表表示如下\\n”);    
62.     printf(”%6s%6s%12s\\n”,“编号”,“顶点”,“相邻边编号”);    
63.     for(i=0;i< G->numVertexes;i++)    
64.     \{    
65.         printf(”%4d%6c     ”,i,G->adjList\[i\].data);  
66.   
67.         for(p=G->adjList\[i\].firstedge;p!=NULL;p=p->next)\{    
68.             printf(”%2d->”,p->adjvex);    
69.         \}    
70.         printf(”%s”,“ NULL”);  
71.         printf(”\\n”);    
72.     \}    
73. \}    
74. void DispGraphdu(GraphAdjList \*G)\{  
75.   
76.     int i,m,n;  
77.     printf(”%6s%6s%6s\\n”,“编号”,“入度”,“出度”);    
78.     for(i = 0; i<G->numVertexes;i++)\{  
79.         m= getIndu(G,i);  
80.         n= getOutdu(G,i);  
81.         printf(”%3d %3d %3d\\n”,i,m,n);  
82.     \}  
83. \}  
84. int getIndu(GraphAdjList  \*G,int m)\{  
85.     int i,sum=0;  
86.      EdgeNode \*p;    
87.      for(i=0;i< G->numVertexes;i++)    
88.     \{    
89.         for(p=G->adjList\[i\].firstedge;p!=NULL;p=p->next)\{    
90.            if(p->adjvex==m)  
91.                sum++;  
92.         \}    
93.     \}    
94.     return sum;  
95. \}  
96. int getOutdu(GraphAdjList \*G,int m)\{  
97.     int i,sum=0;  
98.     EdgeNode \*p;    
99.         for(p=G->adjList\[m\].firstedge;p!=NULL;p=p->next)\{    
100.            sum++;  
101.         \}    
102.     return sum;  
103. \}  
104. Boolean visited\[MAXSIZE\];  
105. void DFSTraverse(GraphAdjList GL)\{  
106.     int i;  
107.     for(i=0;i<GL.numVertexes;i++)  
108.         visited\[i\]=FALSE;  
109.     for(i=0;i<GL.numVertexes;i++)  
110.         if(!visited\[i\])  
111.             DFS(GL,i);  
112. printf(”\\n”);  
113. \}  
114. void DFS(GraphAdjList GL, int i)\{  
115.     EdgeNode \*p;  
116.     visited\[i\] = TRUE;  
117.     printf(”%c ”,GL.adjList\[i\].data);  
118.     p=GL.adjList\[i\].firstedge;  
119.     while(p)\{  
120.         if(!visited\[p->adjvex\])  
121.             DFS(GL,p->adjvex);  
122.         p=p->next;  
123.     \}  
124.   
125. \}  
126.   
127. void BFSTraverse(GraphAdjList GL)\{  
128.     int i;  
129.     EdgeNode \*p;  
130.     LinkQueue Q;  
131.     for(i =0;i<GL.numVertexes;i++)\{  
132.         visited\[i\]=FALSE;  
133.     \}  
134.     InitQueue(&Q);  
135.     for(i =0;i<GL.numVertexes;i++)\{  
136.         if(!visited\[i\])\{  
137.             visited\[i\] = TRUE;  
138.             printf(”%c ”,GL.adjList\[i\].data);  
139.             EnQueue(&Q,i);  
140.             while(!IsEmptyQueue(Q))\{  
141.               
142.                 DeQueue(&Q,&i);  
143.                 p = GL.adjList\[i\].firstedge;  
144.                 while(p)\{  
145.                     if(!visited\[p->adjvex\])\{  
146.                       
147.                         visited\[p->adjvex\]=TRUE;  
148.                         printf(”%c ”,GL.adjList\[p->adjvex\].data);  
149.                         EnQueue(&Q,p->adjvex);  
150.                     \}  
151.                     p= p->next;  
152.                       
153.                 \}  
154.             \}  
155.       
156.         \}  
157.     \}  
158.     printf(”\\n”);  
159. \}  
160.   
161. Status IsEmptyQueue(LinkQueue Q)\{  
162.     if(Q.front==Q.rear)\{  
163.         return OK;  
164.     \}else\{  
165.         return ERROR;  
166.     \}  
167. \}  
168. Status InitQueue(LinkQueue \*Q)\{  
169.     Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));  
170.     if(!Q->front)  
171.         exit(OVERFLOW);  
172.     Q->front->next=NULL;  
173.     return OK;  
174. \}  
175. Status EnQueue(LinkQueue \*Q,QElemType e )\{  
176.     QueuePtr s=(QueuePtr)malloc(sizeof(QNode));  
177.     if(!s)exit (OVERFLOW);  
178.     s->data=e;  
179.     s->next=NULL;  
180.     Q->rear->next=s;  
181.     Q->rear=s;  
182.     return OK;  
183. \}  
184. Status DeQueue(LinkQueue \*Q,QElemType \*e)\{  
185.     QueuePtr p;  
186.     if(Q->front==Q->rear)\{  
187.     return ERROR;  
188.     \}  
189.     p=Q->front->next;  
190.     \*e=p->data;  
191.     Q->front->next=p->next;  
192.     if(Q->rear==p)  
193.         Q->rear=Q->front;  
194.     free(p);  
195.     return OK;  
196. \}

### DS.h ###

--------------------

1.   \#include<stdio.h>  
2.   \#include<string.h>  
3.   \#include<stdlib.h>  
4.   \#include<io.h>  
5.   \#include<math.h>  
6.   \#define OK 1  
7.   \#define ERROR 0  
8.   \#define TRUE 1  
9.   \#define FALSE 0  
10.  \#define MAXVEX 100  
11.  \#define INFINITY 65535  
12.  \#define MAXSIZE 9   
13.  \#define MAXEDGE 15  
14. typedef int Status;  
15. typedef int Boolean;  
16. typedef char VertexType;  
17. typedef int EdgeType;  
18. typedef int QElemType;

### Graph.h ###

--------------------

1.   \#include “DS.h”  
2.  typedef struct EdgeNode\{  
3.      int adjvex;  
4.      EdgeType weight;  
5.      struct EdgeNode \*next;  
6.  \}EdgeNode;  
7.    
8.  typedef struct VertexNode\{  
9.      VertexType data;  
10.     EdgeNode \*firstedge;  
11. \}VertexNode, AdjList\[MAXVEX\];  
12.   
13. typedef struct \{  
14.     AdjList adjList;  
15.     int numVertexes, numEdges;  
16. \}GraphAdjList;  
17.   
18. typedef struct QNode\{  
19.     QElemType data;  
20.     struct QNode \*next;  
21.   
22. \}QNode,\*QueuePtr;  
23. typedef struct \{  
24.     QueuePtr front ,rear;  
25. \}LinkQueue;  
26. void menu();  
27. void GreateALGraph(GraphAdjList \*G);  
28. void GreateALGraphF(GraphAdjList \*G);  
29. void DispGraphAdjList(GraphAdjList \*G) ;  
30. void DispGraphdu(GraphAdjList \*G);  
31. int getIndu(GraphAdjList  \*G,int m);  
32. int getOutdu(GraphAdjList \*G,int m);  
33. void DFSTraverse(GraphAdjList GL);  
34. void DFS(GraphAdjList GL, int i);  
35. void BFSTraverse(GraphAdjList GL);  
36. Status InitQueue(LinkQueue \*Q);  
37. Status EnQueue(LinkQueue \*Q,QElemType e );  
38. Status DeQueue(LinkQueue \*Q,QElemType \*e);  
39. Status IsEmptyQueue(LinkQueue Q);