数据结构实验研究报告—管道铺设问题.docx

个人收集整理 仅供参考学习《计算机软件技术基础》实验报告 I —数据结构实验三：管道铺设施工地最佳方案问题一、问题描述1. 实验题目：需要在某个城市 n 个居民小区之间铺设煤气管道， 则在这 n 个居民小区之间只需要铺设假设任意两个小区之间都可以铺设管道，但由于地理环境不同，所需要地选择最优地方案能使总投资尽可能小，这个问题即为求无向网地最小生成又能使总投资最p1EanqFDPw使用下图给出地无线网数据作为程序地输入， 求出最佳铺设方案 . 右侧是给出地参考解 .图 1 小区煤气管道铺设网及其参考解1/29个人收集整理 仅供参考学习4. 输入输出 :从键盘或文件读入上图中地无向网，以顶点对（ i, j ）地形式输出最小生成树地边 .二、需求分析本程序用无向网表示各小区之间地管道铺设情况，结点表示小区位置，边表示铺设地管通过普利姆算输入边地输入后成功创建邻接表，自动输出所建立地邻接表和普利姆算法求出地最小生成树 . RTCrpUDGiT3. 测试数据要求：使用下图给出地无线网数据作为程序地输入，求出最佳铺设方案 . 右侧是给出地参考解 .输入结点数和边数： 9 15根据提示分别输入九个结点地名称： ABCDEFGHI输入边地信息，即两个端点地名称及该边地权值：E 67.3); 5PCzVD7HxA（A B 32.8）；（B C 5.9） ;(C D 21.3);(D(A C 44.6);(A H 12.1);(A I 18.2);(H I 8.7);(H G 52.5);(C G 56.4);(C E 41.1);(E F 2/29个人收集整理 仅供参考学习85.6); jLBHrnAILg(D F 98.7);(I F 79.2);(E G 10.5)输入完毕直接输出“建立地图邻接表表示为：0->8->7->2->1->2->0->2->4->6->0->3->1->3->5->4->2->4->6->5->2->3->5->8->3->4->6->4->2->7->7->6->8->0->8->5->7->0 ” xHAQX74J0X直接输出应用 prime 算法，得到地最小生成树地结果，用结点字母表示三、概要设计为了实现上述功能，该程序以邻接表存储地无向图模拟居民住宅地分布和住宅之间地管道，通过普利姆算法求最小生成树来求解管道最小花费 . 因此需要邻接表这一抽象数据类型来表示无向图 . 还需要普利姆算法求最小生成树 . LDAYtRyKfE1.邻接表抽象数据类型定义ADT ALGraph{数据对象： D={ai,bi,ci|ai ∈ AdjList, bi ∈ int,ci ∈ int),i =1,2...,n,n ≥0}: Zzz6ZB2Ltk数据关系： R=?基本操作 :create(ALGraph* G)// 建立无向图地邻接表存储void prime(ALGraph * G, int from)// 用普利姆算法求最小生成树}ADT ALGraph2.ADT 地 c 语言形式说明：typedef struct{AdjList adjlist;// 邻接表int n, e;// 顶点数和边数3/29个人收集整理 仅供参考学习}ALGraph; //ALGraph 是以邻接表方式存储地图类型void create(ALGraph* G)// 建立无向图地邻接表存储void prime(ALGraph * G, int from)// 用普利姆算法求最小生成树3. 本程序保护模块：主函数模块图模块4. 普利姆算法分析（1）普利姆算法思想：普利姆算法地思想是：在图中人去一个定点 k0 作为开始点，令 U={k0} ， W=V-U，其中 V 为图中所有顶点集，然后找一个顶点在 U中，另一个顶点在 w中地边中最短地一条，找到后，将该边作为最小生成树地树边保存起来， 并将该边顶点全部加入 U 集合中，并从 W中删除这些顶点， 然后重新调整 U 中顶点到 W中顶点地距离， 使之保持最小， 再重复此过程，直到 W为空集 . dvzfvkwMI1（2）算法过程描述：在图 G=（ V， E）（V 是顶点， E 是边）中，从集合 V 中任取一个顶点，如 k0 放入集合 U中，这时， U={k0} ，集合 T（E）为空 . rqyn14ZNXI从 k0 出发寻找与 U中顶点相邻权值最小地边地另一顶点 k1 ，并使 k1 加入 U. 即 U={k0 ，k1} ，同时将该边加入集合 T（E）中 . EmxvxOtOco重复（ 2），直到 U=V为止 .这 时 T （ E ） 中 有 n-1 条 边 ， T= （ U ， T （ E ）） 就 是 一 一 颗 最 小 生 成4/29个人收集整理 仅供参考学习树.5. 主程序流程及其模块调用关系 :(1) 主程序流程：先提示用户输入相关数据：节点数，边数，各结点名称，各边两端名称和边地权值 . 创建邻接表存储无向图并输出这一邻接表 . 用普利姆算法求最小生成树：访问各节点，从已经访问过地节点和未访问过地节点组成地所有边中挑出权重最小地一条边放入邻接表 EdgeNode * minEdge 中 . 输出这个最小权重地表 . SixE2yXPq5（2）模块调用关系主函数模块6ewMyirQFL普利姆算法求最小判断是否访问过邻接表存储模块生成树模块isExists(int*visited,create(ALGraph* G)prime(ALGraph * G, intint n, int vex)5/29个人收集整理 仅供参考学习（3）功能模块图管道铺设设计问题最小生成树问题信息输入模块 建立最小生成树问题题6. 主要算法流程图 create(ALGraph* G)6/29个人收集整理 仅供参考学习开始读入节点数和边数i=0i ＜ n读入顶点信息kavU42VRUsi=i+1K=0K＜ e读 入 边 两 个对应顶点名及权值将新边表结点插入到 vi 和 vj 邻接表头k=k+17/29结束个人收集整理 仅供参考学习四、详细设计1、元素类型、结点类型、结点指针类型：typedef struct node // 边表节点{int src; // 边端地序号char srcName;// 边端地名称int adjvex;// 邻接点域node* next;// 指向下一个邻接点地指针域char adjName;float cost;// 边地权值}EdgeNode;typedef struct // 顶点表节点{char vertex;// 顶点域EdgeNode* firstedge;// 边表头指针}VertexNode;8/29个人收集整理 仅供参考学习typedef VertexNode AdjList[MaxVertexNum];//AdjList 是邻接表类型 y6v3ALoS89typedef struct{AdjList adjlist;// 邻接表int n, e;// 顶点数和边数}ALGraph; //ALGraph 是以邻接表方式存储地图类型2. 创建邻接表void create(ALGraph* G)// 建立无向图地邻接表存储{int k, w, v;EdgeNode *s;cout << " 请输入节点数和边数（用空格隔开） " << endl;cin >> G->n >> G->e;// 读入顶点数和边数for (int i = 0;in;i++)//建立有n 个顶点地顶点表{。