数据结构课程设计/校园导游程序及通信线路设计 #0
本文章将根据编者的数据结构课程设计，讲解关于最短路径，最小生成树，关键路径等内容，涉及邻接矩阵和邻接表存储图结构； prim ** 算法；djstl迪杰斯特拉算法；关键路径AOE网；程序设计相关内容。
题目：
设计校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。
- 为来访客人提供图中任意景点相关信息的查询。
- 为来访客人提供图中任意2个景点的问路查询,即查询任意两个景点之间的一条最短的简单路径。 //
- 以尽可能低的造价建造景点间的通信网络把这些景点联系在一起，每条通信线路的造价与景点间的距离成正比。 // 最小生成树
按照从北向南的顺序建设学校的景点，请输出完成北门建设的最短工期，并输出关键路径。
现在，跟着编者的思路，来看看我是怎么完成这个课程设计的吧。
内容总览：
涉及到图，那么必不可少存储结构选择临界矩阵或邻接表，但是我们需要求关键路径，采用邻接表的形式方便使用。思路比较清晰，首先写一个菜单页面，然后分别完成各个功能即可。
菜单页面：
使用switch语句搭建菜单页面，并编写防止误输入语句。
void open(MGraph &G) { while (true) { showMenu(); // 显示菜单 cout<<"请输入选项(1/2/3/4/5):"; int choice; if (!(cin >> choice)){ cin.clear(); // 清除错误状态 cin.ignore(); system("cls"); continue; } switch (choice) { case 1: system("cls"); queryScenicInfo(G); // 景点信息查询 break; case 2: queryPath(G); // 景点路径查询 system("pause"); break; case 3: communicationPlan(G); // 通信线路铺设方案 system("pause"); break; case 4: system("pause"); break; case 5: exitSystem(G); return; default: cout << "无效选项，请重新选择！" << endl; system("pause"); } system("cls"); }}
showMenu()函数进行我们图的显示，打印一张图给用户：
图的结构如下：
相应函数：
void showMenu(){ cout<<endl; cout << " A.北校门" << endl; cout << " | 5" << endl; cout << " B.雕塑" << endl; cout << " /3 4\\ " << endl; cout << " / \\ " << endl; cout << " C.图书馆 D.艺术馆" << endl; cout << " / \\ " << endl; cout << " /5 7\\ " << endl; cout << " E.教学楼A F.行政楼" << endl; cout << " \\ / \\ " << endl; cout << " \\ 3 /3 3\\ " << endl; cout << " G.科技楼 H.体育馆" << endl; cout << " / | " << endl; cout << " /4 2| " << endl; cout << " I.食堂 J.教学楼B" << endl; cout << " | \\ |"<<endl; cout << " | \\ | " << endl; cout << " |6 \\7 2| "<<endl; cout << " K.梅园(宿) L.竹园(宿)" << endl; cout << " | /" << endl; cout << " | / "<<endl; cout << " |5 7/ "<<endl; cout << " M.南校门" << endl; cout<<" **************************"<<endl; cout<<" ** 欢迎使用校园导游系统 **"<<endl; cout<<" ** 1.景点信息查询 **"<<endl; cout<<" ** 2.景点路径查询 **"<<endl; cout<<" ** 3.通信线路铺设方案 **"<<endl; cout<<" ** 4.北门建设工期查询 **"<<endl; cout<<" ** 5.退出系统 **"<<endl; cout<<" **************************"<<endl; }
然后，我们开始存储结构的搭建。基于邻接表的关键路径实现是我们的最终要求，这也决定着图的存储结构要求三个结构体：边，顶点，图。
存储结构：
邻接表，边存储顶点索引，权值，指向下一条边的指针。
struct Node { int index; // 边的目标顶点的索引 Node* next; // 下一条边的指针 int distance; // 边的权重（距离）};
而顶点存储它的名字，代号，数据和邻接表头指针。
struct vNode { string name; // 顶点名称 string nickname; // 代号 string data; // 顶点的附加信息，如简介 Node* firstarc; // 指向该顶点的邻接链表的头指针};
图则有一个顶点数组，存储顶点数和边数，以及一个存储了顶点入度的数组（关键路径需求）。
struct MGraph { vNode* vArray; // 顶点数组 int vexnum; // 顶点数 int arcnum; // 边数 int *indegree; // 入度数组};
以上就是我们所有的存储结构的定义。
图的创建：
为了直观的调整和修改，我们采用二维数组存储，并转化为邻接表。为什么编者采用这样的思路呢？主要是因为图邻接表创建要想内置必须进行复杂的链表构造，而手动植入很繁琐并且不直观，编写程序进行二维数组的转化就轻松多了，而且咱们数据结构也涉及过邻接矩阵转邻接表。
与上文图相对应的矩阵：
int edges[13][13] = {// A B C D E F G H I J K L M {no, 5, no, no, no, no, no, no, no, no, no, no, no}, // A { 5, no, 3, 4, no, no, no, no, no, no, no, no, no}, // B {no, 3, no, no, 5, no, no, no, no, no, no, no, no}, // C {no, 4, no, no, no, 7, no, no, no, no, no, no, no}, // D {no, no, 5, no, no, no, 3, no, no, no, no, no, no}, // E {no, no, no, 7, no, no, 3, 3, no, no, no, no, no}, // F {no, no, no, no, 3, 3, no, no, 4, no, no, no, no}, // G {no, no, no, no, no, 3, no, no, no, 2, no, no, no}, // H {no, no, no, no, no, no, 4, no, no, no, 6, 7, no}, // I {no, no, no, no, no, no, no, 2, no, no, no, 2, no}, // J {no, no, no, no, no, no, no, no, 6, no, no, no, 5}, // K {no, no, no, no, no, no, no, no, 7, 2, no, no, 7}, // L {no, no, no, no, no, no, no, no, no, no, 5, 7, no} // M};
这个是无向图！因为我们要先实现前三个功能，而前三个功能最短路径和生成树是要求无向图的（因为景点间的路也不是单项的嘛~dog）。所以我们最后在用有向图。哎！这就体现出编者之前编写程序进行二维数组转化的优势了，我们只需要将矩阵保留上三角，它就是个有向图了，邻接表自动就成有向的了。
以下是存储结构和数据的定义相关代码，大家可粘贴到头文件下，这个是全局定义：
// 定义无穷大常量#define no 10000using namespace std;struct Node { int index; // 边的目标顶点的索引 Node* next; // 下一条边的指针 int distance; // 边的权重（距离）}; struct vNode { string name; // 顶点名称 string nickname; // 代号 string data; // 顶点的附加信息，如简介 Node* firstarc; // 指向该顶点的邻接链表的头指针}; struct MGraph { vNode* vArray; // 顶点数组 int vexnum; // 顶点数 int arcnum; // 边数 int *indegree; // 入度数组}; int vexnum = 13;int arcnum = 15; string names[] = { "北校门", // A "雕塑", // B "图书馆", // C "艺术馆", // D "教学楼A", // E "行政楼", // F "科技楼", // G "体育馆", // H "食堂", // I "教学楼B", // J "梅园(宿)",// K "竹园(宿)",// L "南校门" // M}; string nicknames[] = {"A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M"}; string descriptions[] = { "北校门作为学校的主要入口，拥有强大的吞吐量和安保措施", "这座雕塑代表了学校的精神面貌，旨在激励学生追求卓越。", "图书馆是学校学术资源的核心，收藏了大量的书籍与期刊。", "艺术馆作为学校的文化展示中心，展出各种艺术作品。", "教学楼A是学校的教学活动的主要场所，提供各种教学资源。", "行政楼是学校管理和办公的核心，承担着学校的日常行政工作。", "科技楼专门用于学术研究和技术开发，是学校科研的主要基地。", "体育馆是学校体育活动的场所，提供各种体育设施和运动空间。", "学校的食堂是学生日常就餐的主要场所。这里提供多样化的菜品，满足不同口味的需求，是学生们交流和放松的场所。", "教学楼B是学校的一栋教学建筑，里面设有多个教室、实验室和自习室，供学生上课、学习和进行学术活动。它是学术氛围浓厚的地方，也是老师和学生互动交流的中心。", "梅园是学校的一个宿舍区，通常用于安排学生住宿。这里环境安静、绿树成荫", "竹园是学校的另一处宿舍区，布局与梅园相似，享受宁静和舒适的住宿环境。", "校门是学校的一个主要出入口，常常是学生、教职工进出校园的交通要道。"}; int edges[13][13] = {// A B C D E F G H I J K L M {no, 5, no, no, no, no, no, no, no, no, no, no, no}, // A { 5, no, 3, 4, no, no, no, no, no, no, no, no, no}, // B {no, 3, no, no, 5, no, no, no, no, no, no, no, no}, // C {no, 4, no, no, no, 7, no, no, no, no, no, no, no}, // D {no, no, 5, no, no, no, 3, no, no, no, no, no, no}, // E {no, no, no, 7, no, no, 3, 3, no, no, no, no, no}, // F {no, no, no, no, 3, 3, no, no, 4, no, no, no, no}, // G {no, no, no, no, no, 3, no, no, no, 2, no, no, no}, // H {no, no, no, no, no, no, 4, no, no, no, 6, 7, no}, // I {no, no, no, no, no, no, no, 2, no, no, no, 2, no}, // J {no, no, no, no, no, no, no, no, 6, no, no, no, 5}, // K {no, no, no, no, no, no, no, no, 7, 2, no, no, 7}, // L {no, no, no, no, no, no, no, no, no, no, 5, 7, no} // M}; // 有向图 int edge_goto[13][13] = { {no, 5, no, no, no, no, no, no, no, no, no, no, no}, {no, no, 3, 4, no, no, no, no, no, no, no, no, no}, {no, no, no, no, 5, no, no, no, no, no, no, no, no}, {no, no, no, no, no, 7, no, no, no, no, no, no, no}, {no, no, no, no, no, no, 3, no, no, no, no, no, no}, {no, no, no, no, no, no, 3, 3, no, no, no, no, no}, {no, no, no, no, no, no, no, no, 4, no, no, no, no}, {no, no, no, no, no, no, no, no, no, 2, no, no, no}, {no, no, no, no, no, no, no, no, no, no, 6, 7, no}, {no, no, no, no, no, no, no, no, no, no, no, 2, no}, {no, no, no, no, no, no, no, no, no, no, no, no, 5}, {no, no, no, no, no, no, no, no, no, no, no, no, 7}, {no, no, no, no, no, no, no, no, no, no, no, no, no}};// 用于选择的数组指针 int (*selectedArray)[13];
而接下来便是初始化图的函数啦，大家根据代码中的注释看一遍估计就理解了。
void initG(MGraph &G, int pattern = 0) { G.vexnum = vexnum; G.arcnum = arcnum; G.vArray = new vNode[G.vexnum]; for (int i = 0; i < G.vexnum; i++) { G.vArray[i].name = names[i]; // 设置顶点名 G.vArray[i].data = descriptions[i]; // 设置顶点简介 G.vArray[i].firstarc = NULL; // 初始化邻接链表为空 G.vArray[i].nickname = nicknames[i]; } if(pattern == 1) selectedArray = edge_goto; // 这是有向图 else selectedArray = edges; // 将邻接矩阵的数据转化为邻接表 for (int i = 0; i < G.vexnum; i++) { for (int j = 0; j < G.vexnum; j++) { if (selectedArray[i][j] != no) { // 如果有边 Node* newNode = new Node{j, G.vArray[i].firstarc, selectedArray[i][j]}; // 创建新边节点 G.vArray[i].firstarc = newNode; // 更新链表头指针 } } } // 存储图的入度 ，用于问题四 G.indegree = new int[G.vexnum]; for (int i = 0; i < G.vexnum; i++) G.indegree[i] = 0; for (int i = 0; i < G.vexnum; i++) { for (int j = 0; j < G.vexnum; j++) { if (selectedArray[j][i] != no) { G.indegree[i]++; } } } // 打印图的邻接表（用于调试）// for (int i = 0; i < G.vexnum; i++) {// cout << G.vArray[i].name << ": " << G.vArray[i].data << endl;//// Node* p = G.vArray[i].firstarc; // 获取当前顶点的邻接链表// if (p == NULL) {// cout << "(没有出边)" << endl;// } else {// while (p != NULL) {// cout << G.vArray[p->index].name << "(" << p->distance << ") ";// p = p->next;// }// cout << endl;// }// }}
大家可以将打印图的相关注释取消，调用init函数观察一下有没有问题。
好啦，现在一个由邻接表表示的无向图已经创建好了，我们可以着手解决前三个问题了。
本篇就到这里，感兴趣或有需求的同学可以查看专栏下的下一部分文章。