456456413786.rar_课程设计_数据结构课程设计_数据库编程

<html xmlns="http://www.w3.org/1999/xhtml"> <head> <meta charset="utf-8"> <meta name="generator" content="pdf2htmlEX"> <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1"> <link rel="stylesheet" href="https://static.pudn.com/base/css/base.min.css"> <link rel="stylesheet" href="https://static.pudn.com/base/css/fancy.min.css"> <link rel="stylesheet" href="https://static.pudn.com/prod/directory_preview_static/622b302981ded46b7f1a4e58/raw.css"> <script src="https://static.pudn.com/base/js/compatibility.min.js"></script> <script src="https://static.pudn.com/base/js/pdf2htmlEX.min.js"></script> <script> try{ pdf2htmlEX.defaultViewer = new pdf2htmlEX.Viewer({}); }catch(e){} </script> <title></title> </head> <body> <div id="sidebar" style="display: none"> <div id="outline"> </div> </div> <div id="pf1" class="pf w0 h0" data-page-no="1"><div class="pc pc1 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="https://static.pudn.com/prod/directory_preview_static/622b302981ded46b7f1a4e58/bg1.jpg"><div class="c x0 y1 w2 h2"><div class="t m0 x1 h3 y2 ff1 fs0 fc0 sc0 ls0 ws0">一、需求分析</div><div class="t m0 x2 h4 y3 ff2 fs1 fc0 sc1 ls0 ws0">1.<span class="_ _0"> </span><span class="ff1">问题<span class="_ _1"></span>的描<span class="_ _1"></span>述：<span class="_ _1"></span>假设<span class="_ _1"></span>有<span class="_ _2"> </span></span>n<span class="_ _3"> </span><span class="ff1">个城<span class="_ _1"></span>市之<span class="_ _1"></span>间建<span class="_ _1"></span>立通<span class="_ _1"></span>信网<span class="_ _1"></span>，则<span class="_ _1"></span>连通<span class="_ _4"> </span></span>n<span class="_ _3"> </span><span class="ff1">个城<span class="_ _1"></span>市只<span class="_ _1"></span>需<span class="_ _3"> </span></span>n-1<span class="_"> </span><span class="ff1">条线<span class="_ _1"></span>路。<span class="_ _1"></span>这</span></div><div class="t m0 x3 h4 y4 ff1 fs1 fc0 sc1 ls0 ws0">里自然考虑怎样建立这<span class="_ _3"> </span><span class="ff2">n-1<span class="_ _5"> </span></span>条路是总费用最省。</div><div class="t m0 x2 h4 y5 ff2 fs1 fc0 sc1 ls0 ws0">2.<span class="_ _0"> </span><span class="ff1">把这<span class="_ _3"> </span></span>n<span class="_ _3"> </span><span class="ff1">个城市<span class="_ _1"></span>抽象成一<span class="_ _1"></span>个连通网<span class="_ _1"></span>，网的顶<span class="_ _1"></span>点表示各<span class="_ _1"></span>个城市，<span class="_ _1"></span>顶点与顶<span class="_ _1"></span>点之间的<span class="_ _1"></span>边表示</span></div><div class="t m0 x3 h4 y6 ff1 fs1 fc0 sc1 ls0 ws0">通信线路，赋予边上的权值表示相应的代价。</div><div class="t m0 x2 h4 y7 ff2 fs1 fc0 sc1 ls0 ws0">3.<span class="_ _0"> </span><span class="ff1">本程序的目的是要建立一棵生成树使总费用最少</span></div><div class="t m0 x1 h3 y8 ff1 fs0 fc0 sc0 ls0 ws0">二、概要设计</div><div class="t m0 x2 h4 y9 ff2 fs1 fc0 sc1 ls0 ws0">1.<span class="_ _0"> </span><span class="ff1">抽象数据类型定义如下</span></div><div class="t m0 x2 h5 ya ff2 fs1 fc0 sc1 ls0 ws0">ADT Gra<span class="_ _6"></span>ph{</div><div class="t m0 x2 h4 yb ff2 fs1 fc0 sc1 ls0 ws0"> <span class="ff1">数据对象<span class="_ _5"> </span></span>V<span class="ff1">：</span>V<span class="_ _3"> </span><span class="ff1">是具有相同特性的数据元素的集合，称为顶点集。</span></div><div class="t m0 x2 h4 yc ff2 fs1 fc0 sc1 ls0 ws0"> <span class="ff1">数据关系<span class="_ _5"> </span></span>R<span class="ff1">：</span>R={VR}</div><div class="t m0 x2 h4 yd ff2 fs1 fc0 sc1 ls0 ws0"> VR={(u,v)|u,v<span class="ff3">∈</span>V<span class="_ _7"></span>,w<span class="_ _5"> </span><span class="ff1">是边</span>(v<span class="_ _6"></span>,<span class="_ _6"></span>w)<span class="ff1">的权值</span>,<span class="ff3">∑Wi<span class="_ _5"> </span><span class="ff1">最小</span></span>}</div><div class="t m0 x2 h4 ye ff2 fs1 fc0 sc1 ls0 ws0"> <span class="ff1">基本操作：</span></div><div class="t m0 x1 h5 yf ff2 fs1 fc0 sc1 ls0 ws0"> void CreateGraph (Graph *g)</div><div class="t m0 x2 h4 y10 ff2 fs1 fc0 sc1 ls0 ws0"> <span class="ff1">操作结果：创建一个图包括两个部分顶点集和边集</span></div><div class="t m0 x2 h5 y11 ff2 fs1 fc0 sc1 ls0 ws0"> int smallweight(Graph *g)</div><div class="t m0 x2 h4 y12 ff2 fs1 fc0 sc1 ls0 ws0"> <span class="ff1">初始条件：图已经存在并且初始化</span></div><div class="t m0 x4 h4 y13 ff1 fs1 fc0 sc1 ls0 ws0">操作结果：查找权值最小的边并返回它的地址</div><div class="t m0 x2 h5 y14 ff2 fs1 fc0 sc1 ls0 ws0"> int samefrom(Graph *g ,int x1,int x2)</div><div class="t m0 x4 h4 y15 ff1 fs1 fc0 sc1 ls0 ws0">初始条件：存在图<span class="_ _5"> </span><span class="ff2">g<span class="_ _3"> </span></span>和顶点<span class="_ _5"> </span><span class="ff2">x1,x2</span></div><div class="t m0 x4 h4 y16 ff1 fs1 fc0 sc1 ls0 ws0">操作结果：判断<span class="_ _5"> </span><span class="ff2">x1<span class="_ _3"> </span></span>和<span class="_ _5"> </span><span class="ff2">x2<span class="_ _3"> </span></span>是否属于同一连通分支</div><div class="t m0 x2 h5 y17 ff2 fs1 fc0 sc1 ls0 ws0"> void kruskial(Graph *g)</div><div class="t m0 x1 h4 y18 ff2 fs1 fc0 sc1 ls0 ws0"> <span class="ff1">初始条件：连通图<span class="_ _5"> </span></span>g<span class="_ _3"> </span><span class="ff1">已经存在</span></div><div class="t m0 x1 h4 y19 ff2 fs1 fc0 sc1 ls0 ws0"> <span class="ff1">操作结果：生成一棵最小生成树</span></div><div class="t m0 x2 h5 y1a ff2 fs1 fc0 sc1 ls0 ws0">} <span class="_ _8"></span>ADT Gra<span class="_ _6"></span>ph</div><div class="t m0 x2 h4 y1b ff2 fs1 fc0 sc1 ls0 ws0">2.<span class="_ _0"> </span><span class="ff1">主程序</span></div><div class="t m0 x2 h5 y1c ff2 fs1 fc0 sc1 ls0 ws0">void main()</div><div class="t m0 x5 h5 y1d ff2 fs1 fc0 sc1 ls0 ws0">{</div><div class="t m0 x2 h4 y1e ff2 fs1 fc0 sc1 ls0 ws0"> <span class="ff1">变量定义及初始化；</span></div><div class="t m0 x2 h4 y1f ff2 fs1 fc0 sc1 ls0 ws0"> <span class="ff1">函数调用并输出结果；</span></div><div class="t m0 x2 h5 y20 ff2 fs1 fc0 sc1 ls0 ws0">}</div><div class="t m0 x2 h4 y21 ff2 fs1 fc0 sc1 ls0 ws0">3.<span class="_ _0"> </span><span class="ff1">本程序的模块调用关系</span></div><div class="t m0 x2 h5 y22 ff2 fs1 fc0 sc1 ls0 ws0"> </div><div class="t m0 x1 h3 y23 ff1 fs0 fc0 sc0 ls0 ws0">三、详细设计</div><div class="t m0 x6 h4 y24 ff1 fs1 fc0 sc1 ls0 ws0">主程序<span class="_ _9"> </span>图模块</div></div><div class="t m0 x7 h5 y25 ff2 fs1 fc0 sc1 ls0 ws0"> </div><div class="t m0 x7 h4 y26 ff1 fs1 fc0 sc1 ls0 ws0">题目：若要在<span class="_ _5"> </span><span class="ff2">n<span class="_ _3"> </span></span>个城市之间建立通信网络，只需要假设<span class="_ _3"> </span><span class="ff2">n</span>－<span class="ff2">1<span class="_ _5"> </span></span>条线路即可。如何以最低的经济代价</div><div class="t m0 x7 h4 y27 ff1 fs1 fc0 sc1 ls0 ws0">建设这个通信网，是一个网的最小生成树问题。</div><div class="t m0 x7 h4 y28 ff1 fs1 fc0 sc1 ls0 ws0">班级：计算机学院网络工程班<span class="ff2"> </span>姓名：<span class="ff2"> </span>学号：<span class="ff2"> </span>完成日期：<span class="ff2">2006.6.9</span></div><div class="t m0 x8 h6 y29 ff1 fs2 fc0 sc0 ls0 ws0">实习报告</div></div><div class="pi" data-data='{"ctm":[1.611850,0.000000,0.000000,1.611850,0.000000,0.000000]}'></div></div> </body> </html>