数据结构自用

guhusf

1. #include<stdlib.h>
   
2. #include<stdio.h>
   
3. #define MAX 20
   
4. 
   
5. typedef struct
   
6. {
   
7.         int vexs[MAX];
   
8.         int arcs[MAX][MAX];
   
9.         int len,ArcNum,VexNum;
   
10. }NetGraph;
    
11. 
    
12. void buigra(NetGraph *G)
    
13. {
    
14.         int i,j,k,s;
    
15.         printf("请输入结点数和边数:");
    
16.         scanf("%d %d",&G->VexNum,&G->ArcNum);
    
17.         printf("请输入结点:\n");
    
18.         for(i=0;i<G->VexNum;i++)
    
19.         {
    
20.                 scanf("%d",&G->vexs[i]);
    
21.         }
    
22.         printf("请输入边两端和权值:\n");
    
23.         for(i=0;i<G->VexNum;i++)
    
24.         {
    
25.                 for(j=0;j<G->VexNum;j++)
    
26.                 {
    
27.                         G->arcs[i][j] = 0;
    
28.                 }
    
29.         }
    
30.         for(k=0;k<G->ArcNum;k++)
    
31.         {
    
32.                 scanf("%d %d %d",&i,&j,&s);
    
33.                 G->arcs[i-1][j-1] = s;
    
34.                 G->arcs[j-1][i-1] = s;
    
35.         }
    
36. }
    
37. 
    
38. void disng(NetGraph G)
    
39. {
    
40.         int i,j;
    
41.         printf("%*s",2," ");
    
42.         for(i=0;i<G.VexNum;i++)
    
43.         {
    
44.                 printf("%d ",G.vexs[i]);
    
45.         }
    
46.         printf("\n");
    
47.         for(i=0;i<G.VexNum;i++)
    
48.         {
    
49.                 printf("%d ",G.vexs[i]);
    
50.                 for(j=0;j<G.VexNum;j++)
    
51.                 {
    
52.                         printf("%d ",G.arcs[i][j]);
    
53.                 }
    
54.                 printf("\n");
    
55.         }
    
56. }
    
57. 
    
58. void sholen(NetGraph G)
    
59. {
    
60.         int i, j, k=0, si, sj;
    
61.         for(i=0;i<G.VexNum;i++)
    
62.                 for(j=0;j<G.VexNum;j++)
    
63.                 {
    
64.                         if(G.arcs[i][j]!=0 && k==0)
    
65.                         {
    
66.                                 k = G.arcs[i][j];
    
67.                                 si = G.vexs[i];
    
68.                                 sj = G.vexs[j];
    
69.                         }
    
70.                         else if(G.arcs[i][j]!=0 && G.arcs[i][j]<k)
    
71.                         {
    
72.                                 k = G.arcs[i][j];
    
73.                                 si = G.vexs[i];
    
74.                                 sj = G.vexs[j];
    
75.                         }
    
76.                 }
    
77.                 printf("最短的边是%d---%d",si,sj);
    
78. }
    
79. 
    
80. void insertarc(NetGraph *G)
    
81. {
    
82.         int i, j, s;
    
83.         printf("请输入插入的边两端和权值:\n");
    
84.         scanf("%d %d %d",&i,&j,&s);
    
85.         G->arcs[i-1][j-1] = s;
    
86.         G->arcs[j-1][i-1] = s;
    
87.         printf("Finished!");
    
88. }
    
89. 
    
90. void delarc(NetGraph *G)
    
91. {
    
92.         int i, j;
    
93.         printf("请输入要删除的边:\n");
    
94.         scanf("%d %d",&i,&j);
    
95.         G->arcs[i-1][j-1] = 0;
    
96.         G->arcs[j-1][i-1] = 0;
    
97.         printf("Finished!");
    
98. }
    
99. 
    
100. void getdu(NetGraph G)
     
101. {
     
102.         int i,j,n;
     
103.         for(i=0;i<G.VexNum;i++)
     
104.         {
     
105.                 n = 0;
     
106.                 for(j=0;j<G.VexNum;j++)
     
107.                 {
     
108.                         if(G.arcs[i][j]!=0)
     
109.                                 n++;
     
110.                 }
     
111.                 printf("第%d个结点的度是%d\n",i+1,n);
     
112.         }
     
113. }
     
114. 
     
115. void arrive(NetGraph G,int v,int key,int *flag,int visited[])
     
116. {
     
117.         int i;
     
118.         if(G.vexs[v]==key)
     
119.         {
     
120.                 printf("Yes!");
     
121.                 *flag = 1;
     
122.                 return;
     
123.         }
     
124.         visited[v] = 1;
     
125.         for(i=0;i<G.VexNum;i++)
     
126.         {
     
127.                 if(G.arcs[v][i]!=0 && visited[i]==0)
     
128.                         arrive(G,i,key,flag,visited);
     
129.         }
     
130. }
     
131. 
     
132. int menu()
     
133. {
     
134.         int n;
     
135.         while(1)
     
136.         {
     
137.                 system("cls");
     
138.                 printf("1.创建\t\t2.输出\t\t3.最短边\n");
     
139.                 printf("4.插入边\t5.删除边\t6.求度\n");
     
140.                 printf("7.可达性\t8.退出\n");
     
141.                 printf("请选择功能:");
     
142.                 scanf("%d",&n);
     
143.                 return n;
     
144.         }
     
145. }
     
146. 
     
147. void main()
     
148. {
     
149.         NetGraph G;
     
150.         int n;
     
151.         while(1)
     
152.         {
     
153.                 n = menu();
     
154.                 switch(n)
     
155.                 {
     
156.                 case 1:{
     
157.                         buigra(&G);
     
158.                         system("pause");
     
159.                         getchar();
     
160.                         break;
     
161.                            }
     
162.                 case 2:{
     
163.                         disng(G);
     
164.                         system("pause");
     
165.                         getchar();
     
166.                         break;
     
167.                            }
     
168.                 case 3:{
     
169.                         sholen(G);
     
170.                         system("pause");
     
171.                         getchar();
     
172.                         break;
     
173.                            }
     
174.                 case 4:{
     
175.                         insertarc(&G);
     
176.                         system("pause");
     
177.                         getchar();
     
178.                         break;
     
179.                            }
     
180.                 case 5:{
     
181.                         delarc(&G);
     
182.                         system("pause");
     
183.                         getchar();
     
184.                         break;
     
185.                            }
     
186.                 case 6:{
     
187.                         getdu(G);
     
188.                         system("pause");
     
189.                         getchar();
     
190.                         break;
     
191.                            }
     
192.                 case 7:{
     
193.                         int key,v,flag=0,visited[MAX]={0};
     
194.                         printf("请输入两个点:");
     
195.                         scanf("%d %d",&v,&key);
     
196.                         arrive(G,v,key,&flag,visited);
     
197.                         if(flag == 0) printf("NO!");
     
198.                         system("pause");
     
199.                         getchar();
     
200.                         break;
     
201.                            }
     
202.                 case 8:{
     
203.                         exit(0);
     
204.                            }
     
205.                 }
     
206.         }
     
207. }

复制代码