ʕ·͡ˑ·ཻ ʕ•̫͡• ʔ•̫͡•ཻʕ•̫͡•ʔ•͓͡•ʔ

校园导航-STD

这是之前数据结构做的一个图的实验。

一、题目要求

图是应用极为广泛的数据结构，也是这门课程的重点。它的特点在于非线性。稀疏矩阵 的十字链表存储结构也是图的一种存储结构，故也把它们归在这次实习中。本 章 实习继续突 出了数据结构加操作的程序设计观点，但根据这两种结构的非线性特点，将 操 作 进一步集中 在遍历操作上，因为遍历操作是其他众多操作的基础。遍历逻辑的（或符号形式的）结构， 访问动作可是任何操作。本 次 实习还希望达到熟悉各种存储结构的特征，以及如何应用树和 图结构解决具体问题（即原理与应用的结合）等目的。

图的基本操作

[问题描述]

分别用邻接矩阵和邻接表实现以下操作：图的创建、遍历、插入、删除、最短路径。

[基本要求]

熟悉图的常用存储结构和基本操作

二、设计思路

先构造数据

所有地点:春晖楼 开元楼 图书馆 十栋 基教 学院楼 消社

任意两个地点的路径长度：

春晖楼 开元楼 50

春晖楼 图书馆 300

春晖楼 基教 400

开元楼 基教 200

基教 学院楼 50

学院楼 图书馆 10

十栋 开元楼 250

十栋 消社 20

消社 基教 100

增加的地点:

消社 招待所 700

学院楼 招待所 450

构建一个无向网

用邻接矩阵来存储任意两个地点的关系。

图的遍历用DFS递归来输出地点，任意两点间的最短路径用弗洛伊德算法。

三、代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
#include<iostream>
#include<stack>
#include<cstring>
using namespace std;

#define MaxInt 32767
#define MVNum 100

typedef string VerTexType;
typedef int ArcType;

int vis[MVNum]={0};
int n=0;
int Path[MVNum][MVNum];
int D[MVNum][MVNum];

typedef struct{
	VerTexType vexs[MVNum];
	ArcType arcs[MVNum][MVNum];
	int vexnum,arcnum;
}AMGraph;

int LocateVex(AMGraph G,string u){
	for(int i=1;i<=G.vexnum;i++){
		if(u==G.vexs[i]) {
		    return i;
		    break;
			}
	    else continue;
	}
}

void Create(AMGraph &G){
	int w;
	string v1,v2;
	printf("请输入总地点数和路径数:");
	cin>>G.vexnum>>G.arcnum;
	printf("请输入所有地点:\n");//春晖楼 开元楼 图书馆 十栋 基教 学院楼消社 
	for(int i=1;i<=G.vexnum;i++){ 
		cin>>G.vexs[i];
	} 
	for(int i=1;i<=G.vexnum;i++)
	for(int j=1;j<=G.vexnum;j++)
	    G.arcs[i][j]=MaxInt;
	for(int k=1;k<=G.arcnum;k++){
		printf("请输入两个地点及其路径:");
	    cin>>v1>>v2>>w;
	int m=LocateVex(G,v1);
	int n=LocateVex(G,v2);
	G.arcs[m][n]=w;
	G.arcs[n][m]=w;
}
} 

void Display(AMGraph G,int v){
	if(n>G.vexnum) return;
	if(!vis[v]){
	vis[v]=1;
    cout<<G.vexs[v]<<" ";
    for(int i=1;i<=G.vexnum;i++){
    	if(G.arcs[v][i]!=MaxInt&&vis[i]==0) {
		    n++;
		    Display(G,i);
	}
	else continue;
}
}
}

void Insert(AMGraph &G){
	int w;
	string v1,v2;
	printf("请输入你要增加的地点和路径的数目:");
	int p,q;
	cin>>p>>q;
	int t=G.vexnum;
	G.vexnum+=p;
	G.arcnum+=q;
	for(int k=t+1;k<=G.vexnum;k++){
	for(int i=1;i<=G.vexnum;i++)
	    G.arcs[i][k]=MaxInt;
	for(int j=1;j<=G.vexnum;j++)
	    G.arcs[k][j]=MaxInt;
	}
	cout<<"请输入增加的地点:";
	for(int i=t+1;i<=G.vexnum;i++)
	cin>>G.vexs[i];
	for(int i=1;i<=q;i++){
		printf("请输入两个地点及其路径:");
	    cin>>v1>>v2>>w;
	    int m=LocateVex(G,v1);
	    int n=LocateVex(G,v2);
	    G.arcs[m][n]=w;
	    G.arcs[n][m]=w;
	}
	}
	
void Delete(AMGraph &G){
	int l=0;
	string u;
	cout<<"请输入要删除的地点:";
	cin>>u;
	int t=LocateVex(G,u);
	for(int i=1;i<=G.vexnum;i++){
		if(G.arcs[t][i]!=MaxInt) l++;
	}
	G.arcnum-=l;
	for(int i=1;i<=G.vexnum;i++){
		G.arcs[i][t]=MaxInt;
		G.arcs[t][i]=MaxInt;
	}
	G.vexs[t]="";
}

void Floyd(AMGraph G)
{
	int i,j,k;
	for (i=1;i<=G.vexnum;i++)
		for (j=1;j<=G.vexnum;j++)
		{
			D[i][j] = G.arcs[i][j];
			if (D[i][j]<MaxInt && i!=j)
				 Path[i][j] = i;
			else Path[i][j] = -1;
		}
	for(k=1;k<=G.vexnum;k++)
		for(i=1;i<=G.vexnum;i++)
			for(j=1;j<=G.vexnum;j++)
				if(D[i][k]+D[k][j]<D[i][j])
				{
					D[i][j] = D[i][k] + D[k][j];
					Path[i][j] = Path[k][j];
				}
}
 
void ShortPath(AMGraph G)
{
	string s1,s2;
	int vs,ve,x,temp;
	cout<<"请输入起点和终点:";
	cin>>s1>>s2;
	vs=LocateVex(G,s1);
	ve=LocateVex(G,s2);
	cout<<"最短路径长为：";
	cout<<D[vs][ve]<<endl;
	stack<int> sta;
	sta.push(ve);
	x = ve;
	while (Path[vs][x]!=vs)
	{
		sta.push(Path[vs][x]);
		x = Path[vs][x];
	}
	sta.push(vs);
	cout<<"最短路径为: ";
	temp = sta.top();
	sta.pop();
	cout<<G.vexs[temp];
	while (!sta.empty())
	{
		temp = sta.top();
		sta.pop();
		cout<<"->"<<G.vexs[temp];
	}
	puts("");
}

void menu(){
	cout<<"*********************************************************"<<endl;
	cout<<"-----------------石家庄铁道大学校园导航------------------"<<endl;
	cout<<"*********************************************************"<<endl;
	cout<<"*                    1.  图的创建                       *"<<endl; 
	cout<<"*                    2.  图的遍历                       *"<<endl; 
	cout<<"*                    3.  图的插入                       *"<<endl; 
	cout<<"*                    4.  图的删除                       *"<<endl; 
	cout<<"*                    5.  最短路径                       *"<<endl; 
	cout<<"*                    0. 返回主界面                      *"<<endl; 
} 

int main(){
	AMGraph G;
	int k;
	int t1,t2,t3;
	string v,u;
	menu();
	while(1){
	cout<<"请选择:"<<endl;
	cin>>k;
	switch (k){
		case 1:
			Create(G);break;
		case 2:
	        printf("请输入出发点:");
	        cin>>v;
         	cout<<"从出发点开始遍历的路线为:";
	        t1=LocateVex(G,v);
          	Display(G,t1);
          	cout<<endl;
			break;
		case 3:
		    Insert(G);
	        printf("请输入出发点:");
			cin>>u;
			cout<<"从出发点开始遍历的路线为:";
			t2=LocateVex(G,u);
			n=0;
			memset(vis,0,sizeof(vis));
    		Display(G,t2);
    		cout<<endl;	
    		break;
    	case 4:
    		Delete(G);
    		printf("请输入出发点:");
			cin>>u;
			cout<<"从出发点开始遍历的路线为:";
			t3=LocateVex(G,u);
    		n=0;
			memset(vis,0,sizeof(vis));
    		Display(G,t3);
    		cout<<endl;
    		break;
    	case 5:
    		Floyd(G);
    		ShortPath(G);
    		break;
    	case 0:
    		menu();
    		break;
	}
}
	return 0;
}

四、功能测试

img

img


 Previous

基础编程