数据结构程序设计——山东省城际铁路建设建设
时间：2022-09-06 11:00:00
C山东省城际铁路规划建设语言数据结构课程设计。
在dev在vs code 改一下printf_s啥的也能运行。
使用使用的邻接矩阵用于深度遍历。核心算法是迪杰斯特拉和prim算法，一个计算最短路径，一个计算最小生成树。选取的是山东十七个城市作为节点，和校园导游系统有点类似，就只多了一个最小生成树。因为要存城市名字，是个词语，所以图的节点名称用的二维数组。
将数据存储在函数中，而不是文件中。
这是基于数据的图片。
代码中password这个密码可以在不使用明文的情况下修改或更改为密文。城市选项可以使用每个选项中的输入数字string函数里的strcmp判断，然后输入匹配，就可以输出相应的数据。
以下是完整代码
#include #include #include #include #include #include #define INF 999//表示极大值，∞; #define MVnum 100//最大顶点数； typedef char Type;//顶点数据类型为char类型 typedef int ArcType;////边权值类型整形 typedef int status; char visited[MVnum]; typedef struct { char vexInfo[30][500]; Type vex[MVnum][50] ArcType arcs[MVnum][MVnum];//邻接矩阵 int vexnum, arcnum;///当前点数和边数 } AMGraph; status CreatUND(AMGraph &G); int LocateVex(AMGraph G, char u[]); void DFSsuanfa(AMGraph G, int v);///深度优先搜索 void DFStraverse(AMGraph G); int password(); int menu(); void Info(AMGraph &G); void Prim(AMGraph &G, int start); void Dijkstra(AMGraph G); void man(); void data(AMGraph &G); int main() { AMGraph G = { 0 }; password(); data(G); menu(); return 0; } int password() {//密码 int i = 0; char password[20] = {0}; puts("用户名：admin"); puts("请输入密码："); while (i < 3) { scanf("%s", password); getchar(); if (strcmp(password, "123456") == 0) { printf("登陆成功\n"); printf("查看山东省城际铁路建设规划..."); getchar(); system("cls"); break; } else { i ; printf("密码错误，请重新输入：\n"); } } if (i == 3) { printf("密码错误三次，程序退出\n"); exit(-1); } return 0; } int menu() { while (1) { end: printf("\n*****************************************\n"); printf("*\t欢迎来到山东省城际铁路建设规划\t*\n"); printf("*\t1.深度遍历山东省各城市 \t*\n"); printf("*\t2.查询城市信息 \t\t\t*\n"); printf("*\t3.山东省铁路规划线路 \t\t*\n"); printf("*\t4.查询城市间最短距离 \t\t*\n"); printf("*\t5.制作人名单 \t\t\t*\n"); printf("*\t6.退出系统 \t\t\t*\n"); printf("*****************************************\n"); printf("\n"); printf("\n"); printf("请输入您想要使用的功能："); int choice = 0; int start = 0; scanf("%d", &choice); getchar(); system("cls"); AMGraph G; switch (choice) { case 1: CreatUND(G); DFStraverse(G); break; case 2: Info(G); break; case 3: Prim(G, start); break; case 4: Dijkstra(G); break; case 5: man(); break; case 6: printf("已成功退出"); getchar(); return 0; default: printf("\n\n输入错误，请重新输入选项：\n"); goto end; } getchar(); } } int CreatUND(AMGraph &G) {///改为现有数据 data(G); printf("总城市数为%：d\n", G.vexnum); printf("城市间边数为：%d\n", G.arcnum); int i; int j; for (i = 0; i < G.vexnum; i ) { for (j = 0; j < G.vexnum; j) { G.arcs[i][j] = MVnum; } } int k = 0; return 1; } void DFSsuanfa(AMGraph G, int v) {//深度优先搜索 int w; printf("%s ", G.vex[v]); visited[v] = 1; for (w = 0; w < G.vexnum; w ) { if ((!visited[w]) && (G.arcs[v][w] != 999)) DFSsuanfa(G, w); } } void DFStraverse(AMGraph G) { int i; for (i = 0; i < G.vexnum; i ) //初始化辅助数组 visited[i] = 0; printf("深度优先遍历：\n"); for (i = 0; i < G.vexnum; i ) { if (!visited[i]) DFSsuanfa(G, i); } printf("\n\n按回车键返回..."); getchar(); system("cls"); } void Info(AMGraph &G) {//查询城市信息 data(G); int num; printf("\n\n1.德州 2.滨州 3.东营 4.烟台\n 5.威海 6.聊城 7.济南 8.淄博 \n9.潍坊 10.泰安 11.青岛 12.菏泽 \n13.济宁 14.日照 15.枣庄 16.临沂 \n\n"); printf("请输入选项，查询您想要的城市信息： "); end: scanf("%d", &num); int i = 0; if (num < 1 || num > 16) { printf("\n请输入正确的选项："); goto end; } printf("%s", G.vexInfo[num - 1]); printf("\n\n按回车键返回..."); getchar(); getchar(); system("cls"); } void Dijkstra(AMGraph G) { data(G); int v0, v, w, k = 1, min, t, p; int FIN[MVnum];//FIN[w]=1/0，表示是否要求最短的路径 int Patharc[MVnum];//用于存储最短路径下标的数组 int ShortPathsum[MVnum];///用于存储各点最短路径的权值和 data(G); int num; printf("\n\n1.德州 2.滨州 3.东营 4.烟台\n 5.威海 6.聊城 7.济南 8.淄博 \n9.潍坊 10.泰安 11.青岛 12.菏泽 \n13.济宁 14.日照 15.枣庄 16.临沂 \n\n"); printf("\n请输入一个起始城市的编号："); end: scanf("%d", &v0); v0 = v0 - 1; printf("\n\n"); if (v0 < 0 || v0 > 15) { printf("\n您输入的城市号码不存在\n"); printf("请重新输入："); goto end; } for (v = 0; v < G.vexnum; v ) {///初始化 FIN[v] = 0; ShortPathsum[v] = G.arcs[v0][v]; Patharc[v] = 0; } ShortPathsum[v0] = 0; FIN[v0] = 1; for (v = 0; v < G.vexnum; v ) { min = INF; for (w = 0; w < G.vexnum; w ) { ////找出最近的顶点和权值 if (!FIN[w] && ShortPathsum[w] < min) { //有边 k = w; min = ShortPathsum[w]; } } FIN[k] = 1; for (w = 0; w < G.vexnum; w {
if (!FIN[w] && (min + G.arcs[k][w] < ShortPathsum[w])) {
ShortPathsum[w] = min + G.arcs[k][w];//通过新点得到v0到该点的更短的距离
Patharc[w] = k;
}
}
}
for (t = 0; t <= 15; t++) {
p = t;
if (t != v0) {
printf("%s->", G.vex[v0]);
printf("%s", G.vex[t]);
printf("\n总路线长为: %dkm\n\n", ShortPathsum[t]);
}
}
printf("按回车键返回...");
getchar();
getchar();
system("cls");
}
void Prim(AMGraph &G, int start) {
data(G);
printf("\n\n1.德州 2.滨州 3.东营 4.烟台\n 5.威海 6.聊城 7.济南 8.淄博 \n9.潍坊 10.泰安 11.青岛 12.菏泽 \n13.济宁 14.日照 15.枣庄 16.临沂 \n\n");
printf("请输入你想开始的起点：");
end:
scanf("%d", &start);
start = start - 1;
int i;
if (start < 0 || start > 15) {
printf("\n输入错误，请输入正确的选项：");
goto end;
}
int j = 0, minnum = 0, m = 0, n = 0, sum = 0;
long int min = 0;
int index = 0; // prim最小树的索引，即prims数组的索引
char prims[MVnum][MVnum] {}; // prim最小树的结果数组
int weights[100] {}; // 顶点间边的权值
//用城市信息那个东西就行；
strcpy(prims[0], G.vex[start]);
for (i = 0; i < G.vexnum; i++) {
weights[i] = G.arcs[start][i];
}
weights[start] = 0;
for (i = 0; i < G.vexnum; i++) {
if (start == i)
continue;
j = 0;
minnum = 0;
min = INF;
// 在未被加入到最小生成树的顶点中，找出权值最小的顶点。
while (j < G.vexnum) {
//循环一遍，min变成最小的值
if (weights[j] != 0 && weights[j] < min) {
min = weights[j];
minnum = j;
}
j++;
}
index++;
strcpy(prims[index], G.vex[minnum]);
weights[minnum] = 0;
// 当第minnum个顶点被加入到最小生成树的结果数组中之后，更新其它顶点的权值。
for (j = 0; j < G.vexnum; j++) {
// 当第j个节点没有被处理，并且需要更新时才被更新。
if (weights[j] != 0 && G.arcs[minnum][j] < weights[j])
weights[j] = G.arcs[minnum][j];
}
}
// 计算最小生成树的权值
sum = 0;
for (i = 1; i <= index; i++) {
min = INF;
// 获取prims[i]在G中的位置
n = LocateVex(G, &prims[i][0]);
for (j = 0; j < i; j++) {
m = LocateVex(G, &prims[j][0]);
if (G.arcs[m][n] < min) {
min = G.arcs[m][n];
printf("%s->%s=%d\n", G.vex[m], G.vex[n], min);
}
}
sum = sum + min;
}
printf("\n\n开始起点:%s\n路线图最短距离：%dkm \n", G.vex[start], sum);
printf("所连接城市依次为：");
for (i = 0; i < index; i++)
printf("%s ", prims[i]);
printf("\n\n\n按回车键返回...");
getchar();
getchar();
system("cls");
}
int LocateVex(AMGraph G, Type u[]) {//找下标
int i;
for (i = 0; i < G.vexnum; ++i) {
if (strcmp(u, & G.vex[i][0]) == 0) {
return i;
}
}
return -1;
}
void man() {
char str[] = " 制作人：\n 崔鲁浩 \n 张海龙 \n 李柯均 \n 刘轩豪";
int i = 0, j = 0, k = 0, len = 0;
printf("\n\n**************************\n");
len = strlen(str);
for (i = 0; i < len; i++) {
k++;
Sleep(50);
printf("%c", str[i] );
}
printf("\n*************************");
printf("\n\n\n按回车键返回...");
getchar();
system("cls");
}
void data(AMGraph &G) {
for (int i = 0; i < 100; i++) {
for (int j = 0; j < 100; j++)
G.arcs[i][j] = { INF };
}
G.vexnum = 16;
G.arcnum = 54;
strcpy(G.vex[0], "德州");
strcpy(G.vexInfo[0],
"\n 德州，古称安德，简称德，位于山东省西北部、黄河下游冲积平原，是山东省的西北大门。北接河北省沧州市，南接省会济南市、聊城市，西邻河北省衡水市，东连滨州市。处于环渤海经济圈、京津冀经济圈、山东半岛蓝色经济区以及黄河三角洲高效生态经济区交汇区域。京杭大运河有140多公里流经境内，历史上曾是重要的漕运通道，现如今已定位为京津冀协同发展示范城市。");
strcpy(G.vex[1], "滨州");
strcpy(G.vexInfo[1],
"\n 滨州市位山东省北部、鲁北平原、黄河三角洲腹地，版图面积9600平方公里，地处黄河三角洲高效生态经济区、山东半岛蓝色经济区和环渤海经济圈、济南省会城市群经济圈两区两圈叠加地带，是山东省的北大门。2000年6月18日撤地设市，人口380万(2014年)，现辖滨城区、沾化区、惠民县、阳信县、无棣县、博兴县、邹平县五县二区和滨州经济开发区、滨州高新技术产业开发区、滨州北海经济开发区，是黄河三角洲区域内最大的行政区。 \n");
strcpy(G.vex[2], "东营");
strcpy(G.vexInfo[2],
"\n东营市是山东省地级市，成立于1983年10月，是黄河三角洲的中心城市。位于山东省东北部、黄河入海口的三角洲地带,东营是古代大军事家孙武的故里。山东地方代表戏曲吕剧的发源地。中国第二大石油工业基地胜利油田崛起地。被评为中国“六大最美湿地之一”。\n");
strcpy(G.vex[3], "烟台");
strcpy(G.vexInfo[3],
"\n烟台是环渤海经济圈内重要节点城市、山东半岛蓝色经济区骨干城市、 中国首批14个沿海开放城市之一，中国海滨城市，亚洲唯一的国际葡萄·葡萄酒城、“一带一路”国家战略重点建设港口城市、是国家历史文化名城，全国文明城市， 烟台与威海同为中国著名的“雪窝”。\n");
strcpy(G.vex[4], "威海");
strcpy(G.vexInfo[4],
"\n威海别名威海卫，意为威震海疆。威海是中国大陆距离日本、韩国最近的城市、中国近代第一支海军北洋海军的发源地、甲午海战的发生地，甲午战争后被列强侵占并回归祖国的“七子”之一。 \n");
strcpy(G.vex[5], "聊城");
strcpy(G.vexInfo[5],
"\n聊城城区独具“江北水城”特色，被誉为“中国北方的威尼斯”，黄河与京杭大运河在此交汇。明清时期借助京杭大运河漕运之利，聊城成为沿岸九大商都之一，繁荣昌盛达400年之久，被盛誉为“江北一都会”。市区环抱的东昌湖是中国北方最大的城市湖泊，南岸的聊城摩天轮“水城之眼”为全球十大摩天轮之一，位列第七位。\n");
strcpy(G.vex[6], "济南");
strcpy(G.vexInfo[6],
"\n济南因境内泉水众多，拥有“七十二名泉”，被称为“泉城”，素有“四面荷花三面柳，一城山色半城湖”的美誉。是国家历史文化名城、首批中国优秀旅游城市，史前文化龙山文化的发祥地之一。济南北连首都经济圈，南接长三角经济圈，东西连通山东半岛与华中地区，是环渤海经济区和京沪经济轴上的重要交汇点，环渤海地区和黄河中下游地区中心城市，山东半岛城市群和济南都市圈的核心城市。 \n");
strcpy(G.vex[7], "淄博");
strcpy(G.vexInfo[7],
"\n淄博位于中国华东地区、山东省中部，地处黄河三角洲高效生态经济区、山东半岛蓝色经济区两大国家战略经济区与省会城市群经济圈的重要交汇处，南依沂蒙山区与临沂接壤，北临华北平原与东营、滨州相接，东接潍坊，西与省会济南接壤。 \n");
strcpy(G.vex[8], "潍坊");
strcpy(G.vexInfo[8],
"\n潍坊，古称“潍县”，又名“鸢都”，位于山东半岛的中部，山东省下辖地级市，与青岛、日照、淄博、烟台、临沂等地相邻。地扼山东内陆腹地通往半岛地区的咽喉，胶济铁路横贯市境东西，是半岛城市群地理中心。地处黄河三角洲高效生态经济区、山东半岛蓝色经济区两大国家战略经济区的重要交汇处。是中国最具投资潜力和发展活力的新兴经济强市。 \n");
strcpy(G.vex[9], "泰安");
strcpy(G.vexInfo[9],
"\n泰安是中国华东地区重要的对外开放旅游城市。北距省会济南市66.8千米，南至三孔圣地曲阜市74.6千米，是山东省一山、一水、一圣人旅游热线的中点。北依山东省会济南，南临儒家文化创始人孔子故里曲阜，东连商城临沂，西濒黄河。辖泰山、岱岳两个市辖区，宁阳、东平两个县，代管新泰、肥城2个县级市。 \n");
strcpy(G.vex[10], "青岛");
strcpy(G.vexInfo[10],
"\n青岛，山东省地级市，国家计划单列市、副省级城市，简称青，旧称“胶澳”，别称“琴岛”、“岛城”。青岛是沿海重要中心城市、沿海开放城市、新一线城市、经济中心城市、国家历史文化名城 ，是国际性港口城市、滨海度假旅游城市、幸福宜居城市， 被誉为“东方瑞士”。 \n");
strcpy(G.vex[11], "菏泽");
strcpy(G.vexInfo[11],
"\n菏泽原系天然古泽，济水所汇，菏水所出，连通古济水、泗水两大水系，唐更名龙池，清称夏月湖。清朝雍正十三年（1735年）升曹州为府，附郭设县，因南有“菏山”，北有“雷泽”，赐名菏泽。 \n");
strcpy(G.vex[12], "济宁");
strcpy(G.vexInfo[12],
"\n济宁地区历史文化悠久，是东夷文化、华夏文明、儒家文化、水浒文化、运河文化的重要发祥地之一。儒家创始人至圣孔子、亚圣孟子、复圣颜回、史家左丘明皆出生于此。元明清时期，京杭大运河促进了济宁商品经济的繁荣，使济宁成为京杭大运河沿岸重要的工商业城市。 \n");
strcpy(G.vex[13], "日照");
strcpy(G.vexInfo[13],
"\n日照市属鲁东丘陵，总的地势背山面海，中部高四周低，略向东南倾斜，山地、丘陵、平原相间分布。日照市横跨胶南隆起、胶莱坳陷和沂沭断裂带三个Ⅲ级构造单元，出露地层齐全，构造复杂，岩浆活动强烈，形成了较为丰富的非金属、地下水、矿泉水等矿产资源。 \n");
strcpy(G.vex[14], "枣庄");
strcpy(G.vexInfo[14],
"\n枣庄因多枣树而得名，是著名的煤城，为中国76个四线城市之一。2009年成为国务院政策支持的东部地区唯一转型试点城市，2013年又被国务院列为中国老工业城市重点改造城市。 \n");
strcpy(G.vex[15], "临沂");
strcpy(G.vexInfo[15],
"\n临沂因临沂河得名，古称“琅琊”。临沂历史悠久，是中华文明的重要发祥地之一。秦时属琅琊郡和郯郡。近代中国共产党在临沂地区创建了沂蒙革命根据地，1945年8月在莒南县大店镇成立山东省政府。1994年12月，国务院批准撤销临沂地区和县级临沂市，设立地级临沂市。 \n");
G.arcs[0][1] = 151;
G.arcs[1][0] = 151;
G.arcs[0][5] = 130;
G.arcs[5][0] = 130;
G.arcs[0][6] = 110;
G.arcs[6][0] = 110;
G.arcs[1][2] = 57;
G.arcs[2][1] = 57;
G.arcs[1][7] = 64;
G.arcs[7][1] = 64;
G.arcs[2][3] = 242;
G.arcs[3][2] = 242;
G.arcs[2][8] = 90;
G.arcs[8][2] = 90;
G.arcs[3][4] = 64;
G.arcs[4][3] = 64;
G.arcs[3][10] = 185;
G.arcs[10][3] = 185;
G.arcs[4][6] = 460;
G.arcs[6][4] = 460;
G.arcs[5][9] = 104;
G.arcs[9][5] = 104;
G.arcs[5][11] = 140;
G.arcs[11][5] = 140;
G.arcs[6][12] = 140;
G.arcs[12][6] = 140;
G.arcs[6][9] = 50;
G.arcs[9][6] = 50;
G.arcs[6][7] = 93;
G.arcs[7][6] = 93;
G.arcs[7][8] = 95;
G.arcs[8][7] = 95;
G.arcs[8][10] = 131;
G.arcs[10][8] = 131;
G.arcs[8][15] = 191;
G.arcs[15][8] = 191;
G.arcs[9][14] = 169;
G.arcs[14][9] = 169;
G.arcs[10][13] = 107;
G.arcs[13][10] = 107;
G.arcs[11][12] = 105;
G.arcs[12][11] = 105;
G.arcs[11][14] = 177;
G.arcs[14][11] = 177;
G.arcs[12][15] = 164;
G.arcs[15][12] = 164;
G.arcs[13][15] = 112;
G.arcs[15][13] = 112;
G.arcs[14][15] = 100;
G.arcs[15][14] = 100;
G.arcs[12][14] = 138;
G.arcs[14][12] = 138;
G.arcs[4][8] = 314;
G.arcs[8][4] = 314;
G.arcs[4][10] = 272;
G.arcs[10][4] = 272;
}
代码中迪杰斯特拉和prim，可以好好的看一看，是核心代码，剩下的可以自己适当删减或补充。
