#《数据结构》课程设计指导书1

1、数据结构课程设计指导书 （共 13 题）、课程设计的目的课程设计的目的是培养学生综合程序设计的能力， 训练学生灵活使用所学数 据结构知识， 独立完成问题分析、 总体设计、详细设计和编程实现等软件开发全 过程的综合实践能力。巩固、深化学生的理论知识，提高编程水平，并在此过程 中培养他们严谨的科学态度和良好的学习作风。 为今后学习其他计算机课程打下 基础。课程设计为学生提供了一个既动手又动脑， 独立实践的机会， 将书本上的理 论知识和工作、 生产实际有机地结合起来， 从而锻炼学生分析问题、 解决实际问 题的能力，提高学生的编程序能力和创新意识。二、课程设计的要求在处理每个题目时， 要求从分析题目的

2、需求入手， 按设计抽象数据类型、 构 思算法、通过算法的设计实现抽象数据类型、 编制上机程序和上机调试等若干步 骤完成题目， 最终写出完整的课程设计和程序分析报告。 前期准备工作完备和否 直接影响到后序上机调试工作的效率。三、课程设计的学生分组情况 每组三至五人，共同研究、共同讨论，可以共同编写算法，但必须各自独立 完成各自的程序。四、课程设计的时间安排课程设计前两周：将各项任务及问题进行讲解、分析。课程设计一周： 星期一：学生对任务进行讨论、研究和分析，初步设计出算法。 星期二到星期四：设计出详细算法，并上机调试程序。 星期五到星期六：写出课程设计报告并考核。五、课程设计的主要内容【课程设计

3、题目一】一元稀疏多项式加法、乘法器【问题描述】 设计一个一元稀疏多项式加法、乘法器用于计算两个多项式的加法和乘法。例如(x2+4x5+2x9) +(x+3x4)或(7x4+4x6+2x9) *(x 4+3x9)【基本要求】( 1) 输入并建立两个多项式 f(x) 和 g(x) ；( 2 ) 输出每个多项式，要求输出时按指数从小到大输出。( 3) 两个多项式完成加法、乘法运算。( 4) 输出两个多项式的加法之和及乘积的结果。( 5 ) 写出课程设计报告【实现提示】 用带表头结点的单链表存储多项式。【测试数据】 分别选定三组测试数据进行测试，验证程序的正确性。【课程设计题目二】局域网的架设问题【问

4、题描述】若要在8个城市(A、B、C、D E、F、G H之间架设局域网，如何以最低 的经济代价架设这个局域网。【基本要求】( 1 ) 利用三种方法( Prim 算法、克鲁斯卡尔( Kruskual 和矩阵运算)算 法生成局域网的架设方案( 2) 写出课程设计报告。【测试数据】 分别对每种方法选定一组测试数据进行测试，验证程序的正确性。【课程设计题目三】 二叉树的创建、二叉树的遍历【问题描述】 创建一棵二叉树，并对二叉树进行中序、前序、后序和层次遍历，分别写出它们的递归、非递归遍历算法【基本要求】 创建多种（五种以上）不同形态的二叉树，验证上述算法。【课程设计题目四】 校园导游咨询系统【问题描述】

5、设计一个你所在学校的校园导游程序，为来访的客人提供各种信息查询服 务。【基本要求】（1）设计你所在学校的校园平面图，所含景点不少于10 个。以图中顶点表示校内各景点，存放景点名称，代号，简介等信息；以边表示路径，存放路径 长度等相关信息。（2）为来访客人提供图中任意景点相关信息的查询。（3）为来访客人提供图中任意景点的问路查询， 即查出任意两个景点之间 的一条最短的简单路径。（4）写出课程设计报告【测试数据】 选定一组测试数据进行测试，验证程序的正确性。【课程设计题目五】通信网络的架设问题【问题描述】若要在n （10）个城市之间建设通信网络，只需要架设 n-1条线路即可， 如何以最低的经济代价

6、建设这个通信网，是一个网的最小生成树问题。【基本要求】（ 1 ）利用三种方法（ Prim 算法、克鲁斯卡尔（ Kruskual 和矩阵运算）生成 网中的最小生成树（ 2）写出课程设计报告。【测试数据】 分别对每种方法选定三组测试数据进行测试，验证程序的正确性。【课程设计题目六】内部排序的比较【问题描述】 比较内部排序冒泡排序、 插入排序、二分插入排序、 选择排序的运行时 间。给出算法执行的时间阶或每个程序的运行时间，精确到秒。【基本要求】（1）比较下列几种内部排序：冒泡排序、插入排序、二分插入排序、选择 排序的运行时间。 要求随机生成 20000 个测试数据进行测试， 并输出每个程序的 运行时

7、间，精确到秒。（2）写出课程设计报告【测试数据】 选定一批测试数据进行测试，验证程序的正确性并对计算时间进行比较。【课程设计题目七】 算法表达式的求值演算【问题描述】 以字符序列的形式从终端输入语法正确的、 不含变量的整数表达式。 利用教 科书给出的算符优先关系，加上乘方（A）和求除（%运算符，实现对算术混合运 算表达式的求值。【基本要求】（ 1）用顺序栈实现（ 2）含有乘方 （A） 、加（+） 、减（-） 、乘（*） 、除（/） 、求除（ %）等运算；并 含有括号。（3）分别以五组不同的表达式作为测试实例，每个实例中含有上述所有运 算符，测试其结果的正确性。（ 4）写出课程设计报告【测试数据

8、】 选定五组测试数据进行测试，验证程序的正确性。【课程设计题目八】 设计一个矩阵运算器【问题描述】设计一个矩阵运算器，对矩阵进行乘方(八)、加(+)、减(-)、乘(*)运算；【基本要求】(1) 参见数据结构题集P136页4.1(2) 求含有乘方(A)、加(+)、减(-)、乘(*)运算；。( 3) 写出课程设计报告【测试数据】分别选定一组测试数据进行测试，验证程序的正确性。【课程设计题目九】自来水管理架设问题【问题描述】若要在扬州大学的八个居民区(A区、B区、C区、D区、E区、F区、G区、 H区)之间架设自来水管道，如何以最低的经济代价架设这个自来水管道。【基本要求】( 1 )利用三种方法( P

9、rim 算法、克鲁斯卡尔 Kruskual 和矩阵运算)算法生成自来水管道的架设方案( 2)写出课程设计报告。【测试数据】分别对每种方法选定三组测试数据进行测试，验证程序的正确性。【课程设计题目十】校园网架设的方案设计问题【问题描述】若要在扬州大学的八个校区(江阳路南校区、江阳路北校区、盐阜校区、瘦 西湖校区、农学院校区、工学院校区、水利学院校区、医学院校区)之间架设校 园网，如何以最低的经济代价架设这个校园网。【基本要求】( 1 )利用三种方法( Prim 算法、克鲁斯卡尔( Kruskual )和矩阵运算)算 法生成校园网的架设方案( 2)写出课程设计报告。【测试数据】分别对每种方法选定一

10、组测试数据进行测试，验证程序的正确性。 【课程设计题目十一】学生成绩管理系统【问题描述】现有学生成绩信息文件 1（1.txt ），内容如下姓名学号语文数学英语张明明01677882李成友02789188张辉灿03688256王露04564577陈东明05673847学生成绩信息文件2（ 2.txt ）, 内容如下:姓名学号语文数学英语陈果31576882李华明32889068张明东33484256李明国34504587陈道亮35475877【基本要求】试编写一管理系统 , 要求如下 :1）实现对两个文件数据进行合并 , 生成新文件 3.txt2）抽取出三科成绩中有补考的学生并保存在一个新文件

11、4.txt3）对合并后的文件 3.txt 中的数据按总分降序排序 （ 至少采用两种排序方 法实现）4）输入一个学生姓名后 , 能查找到此学生的信息并输出结果 （ 至少采用两种 查找方法实现 ）5）要求使用结构体和链表实现上述要求【课程设计题目十二】学生成绩管理系统【问题描述】现有学生成绩信息文件 1（1.txt ），内容如下姓名学号语文数学英语张明明01677882李成友02789188张辉灿03688256王露04564577陈东明05673847学生成绩信息文件2（ 2.txt ）, 内容如下:姓名学号语文数学英语陈果31576882李华明32889068张明东33484256李明国345

12、04587陈道亮 35475877【基本要求】试编写一管理系统 , 要求如下 :1) 实现对两个文件数据进行合并 , 生成新文件 3.txt2) 抽取出三科成绩中有补考的学生并保存在一个新文件 4.txt3) 对合并后的文件 3.txt 中的数据按总分降序排序 ( 至少采用两种排序方 法实现)4) 输入一个学生姓名后 , 能查找到此学生的信息并输出结果 ( 至少采用两种 查找方法实现 )5) 要求使用结构体和数组实现上述要求 .【课程设计题目十三】算法表达式的求值演算【问题描述】以字符序列的形式从终端输入语法正确的、 不含变量的整数表达式。 利用教 科书给出的算符优先关系，加上乘方(八)和求除

13、(%等运算符，实现对算术混合 运算表达式的求值。【基本要求】(1) 用链栈实现(2) 含有乘方(八)、加(+)、减(-)、乘(*)、除(/)、求除(%等运算；并 含有括号。(3) 分别以五组不同的表达式作为测试实例，每个实例中含有上述所有运算符，测试其结果的正确性。(4) 写出课程设计报告【测试数据】 选定五组测试数据进行测试，验证程序的正确性。六、课程设计报告的主要内容课程设计报告主要包括以下几方面的内容:（1）课程设计的题目（2）课程设计的目的（3）分析系统的主要功能及用途（4）分析和描述系统的基本要求（5）问题实现的主要算法和分析（6）源程序（7）使用方法和说明（8）课程设计的小结（9）

14、参考文献七、课程设计的考核结合学生的动手能力，独立分析解决问题的能力和创新精神， 总结报告和答 辩水平以及学习态度综合考评。考核成绩分优、良、中、及格和不及格五等。考核主要包含以下几方面内容：1）运行所设计的系统2）回答相关题目的问题3）提交课程设计报告4）提交软盘（含源程序、执行程序和课程设计报告）5）内容要有创新。八、附录（课程设计报告示例）数据结构 课程设 计报告 课题名称最小牛成树问题 姓名XXX学院广陵学院系科班级计科81101指导老师陈宏建日 期 201目录年1月12日一、问题描述最小生成树问题一、二问题描述计1、2、要在n个城市之间建设通信网络，只需要架设n-1条线路即可。如何以

15、最低的经济代价建设这个通信网络，是一个网的最小生成树问题。利用克抽象数据类型的义小生成树。假设连通网“=(V,E成；则令最小生成1516181920树的的初始状态为只有n个结点而无边的非连通图T= (V, ),图中每一个顶点自成一个连通分量。在E中选择代价最小的边， 若该边依附的顶点落在 T中不同的 连通分量序包则将模边加入到成成,否则舍去此边选择下一条代成最小的边。旅次 类推，直至T中所有顶点都在同一连通分量上为止。3、使用Mfset、类表示构造生成树过程中的连通分量。4、测试数函数附后用关系 概要设计1、三抽象详细设计义如下: 3ADT Graph数据对象V : V是具有相同特性的数据元素

16、的集合，成为顶点集。数据关系点R:边、图和集合类型 3R=VR VR=(v,w)|v,w V,(v,w)表示v和w之间存在路径基本操作图的基本操作 4CreatGraph(&G);操作结果：初始化一个图。Ini tl程序详细代码)； 5操作结果：初始化操作。构造一个由n个子集(每个子集只含单个成员XJ构成的集合SoFin4(SS数调用关系图 15初始条件：S是已经存在的集合，v是某个子集成员。操作结果：查找函数。返回S中v所属子集Si。四、设计，和调试分析初始条件：Si和Sj是S中两个互不相交的非空集合。 操作结果：归并操作。将 Si和Sj中的一个并入另一个。五Krus用户手册初始条件

17、：图G存在。操作结果：求图G的最小生成数。六Outp测试结 果初始条件：已经生成图 G的最小树。 操作结果：输出操作。将最小生成树以文本形式输出到文件中。aIDtg 附件2、本程序包含5个模块,1) 占主程序模块，其中主函数为八ma心得体会初始化图形界面；读入用户选择信息；根据用户选择执行相应模块；关闭文件及图形界面；2) 汉字显示模块一一实现 DOS模式下的汉字显示；3) 随机图单元模块一一实现随机生成图；4) 读图模块一一实现从指定文件中读图；5) 图形输出模块一一实现图的仿真输出。6) 集合操作模块一一实现集合的查找合并。7) 求最短路径模块一一实现 Kruskal算法求图最短路径。3、

18、函数调用关系：主程序图形输岀模块 II 随机图模块文件读图模块汉字显示模块KRUSKAL 模块集合操作模块三、详细设计1、顶点、边、图和集合类型#defi ne cha nge(a,b) a=a+b,b=a-b,a=a-b;#define NY AN交换两个变量值/ nt/是否演示树的生成过程typedef structint x,y;/该城市的纵横坐标int tag;/该城市的访冋标志char n ame64;/城市名verType;/顶点类型typedef structint bg,ed;/边的两端顶点号int wt;/边的权值int tag;/边的访问标志edgType;/边类型type

19、def structverType *v;/指向顶点集合edgType *e;/指向边集合int vn,en;/顶点及边的数目char n ame64;/图名字GType;/图类型GType g;/图全局变量FILE *fp;文件指针变量2、 图的基本操作void initgph(void); /初始化函数。将系统设置为图形工作模式。void getdot(unsigned char c,unsigned char n8);/将 c 分解为二进制 01 串，存放在 n 中。int pnthz(int x,int y,int fcolor,int bcolor,char os);/x,y 是屏幕

20、坐标， fcolor 和 bcolor 是前景色及背景色， os 是汉字字符串；在 x,y 位置输出汉字串 os。void copyedg(edgType *e1,edgType *e2)II el和e2是图的两条边。将el的内容赋给e2。void randomedg(void)II初始化。对边集进行随机赋值。void randomver(void)II初始化。对顶点集进行随机赋值。void readver(void)II读入信息。将存放在文件里的图顶点信息读入内存。void readedg(void)II读入信息。将存放在文件里的图边信息读入内存。void drawver(void)II绘图

21、操作。在屏幕上绘制结点。void drawedg(void)II绘图操作。在屏幕上绘制边。void initial(void)II初始化操作。构造一个由n个子集(每个子集只含单个成员Xi)构成的集合S。int find(int v)IIS是已经存在的集合，v是某个子集成员。返回S中v所属子集Si。void merge(int v1,int v2)IIS1和S2是S中两个互不相交的非空集合。将S1和S2中的一个并入另一个。void kruskal(int v1,int v2)II求图G的最小生成树。void output(void)II输出操作。将最小生成树以文本形式输出到文件中。void fr

22、omfile(char fname)IIfname 是图文件名。打开文件操作。打开图信息文件，为读图做准备。void userinput(void)II由用户输入图文件名。void randomimage(void)II调用Randomedg()和Randomver()函数对边集和顶点集进行随机赋值。int choose(void)II由用户选择图信息的生成方式。返回选择项的序号。3、程序详细代码#include<stdio.h>#include<stdlib.h>#include<string.h>#include<time.h>#includ

23、e<math.h>#include<graphics.h>#define change(a,b) a=a+b,b=a-b,a=a-b;#define Pi #define NYANtypedef structint x,y,tag;char name64;verType;typedef structint bg,ed,wt,tag;edgType;typedef struct verType *v; edgType *e; int vn,en; char name64;GType;GType g;FILE *fp;void initgph(void)int gmode,

24、gdrive;printf("nntInitializtion graph mode, please wait."); gmode=DETECT;initgraph(&gmode,&gdrive,"C:Tc");void getdot(unsigned char c,unsigned char n8)char i;for(i=0;i<8;i+)ni=(c>>(7-i)&1);int pnthz(int x,int y,int fcolor,int bcolor,char os)FILE *hzk=NULL;uns

25、igned int j,k,cn2,cx,cy;unsigned long i,len,p;unsigned char c32,n8,ch2,s128; for(i=0,j=0,len=0;osj!='0'i+,j+,len+) if(osj>32)si+=0xAA;si=0xA1+(osj-33);len+;else if(osj=32)si+=0xA1;si=0xA1;len+;else si=osj;if(len=0) return(0);len/=2;if(hzk=fopen("C:WindowsCommandChs16.fon","

26、rb")=NULL) return(1);for(i=0;i<len;i+)ch0=si*2;ch1=si*2+1;cn0=(ch0-0xA1);cn1=(ch1-0xA1); p=(cn0*94L+cn1)*32L; rewind(hzk); fseek(hzk,p,0);fread(&c,sizeof(char),32,hzk);for(j=0;j<32;j+)getdot(cj,n);for(k=0;k<8;k+) cx=(k+(j%2)*8+i*16+x)%640; cy=j/2+y+(k+(j%2)*8+i*16+x)/640)*16; if(nk

27、=1) putpixel(cx,cy,fcolor); else if(bcolor!=-1) putpixel(cx,cy,bcolor); fclose(hzk);return(cx);void copyedg(edgType *e1,edgType *e2)e1->bg=e2->bg; e1->ed=e2->ed; e1->wt=e2->wt; e1->tag=e2->tag;void randomedg(void)int i,j,tag;edgType re;if(g.e!=NULL) free(g.e);g.e=(edgType *)m

28、alloc(sizeof(edgType)*g.en);if(g.e=NULL) printf("nMalloc Error!"); return; for(i=0;i<g.en;i+)re.bg=random(g.vn);re.ed=random(g.vn);for(j=0,tag=0;j<i;j+)if(g.ej.bg=re.bg&&g.ej.ed=re.ed) |(g.ej.bg=re.ed&&g.ej.ed=re.bg) tag=1; break;if(re.bg=re.ed|tag=1) i-; continue; re

29、.wt=random(99)+1;re.tag=(-1); for(j=i;(g.ej-1.wt>re.wt)&&(j>0);j-) copyedg(&(g.ej),&(g.ej-1);copyedg(&(g.ej),&re);void randomver(void)int i,xc,yc,r;float dg,st,x,y;if(g.v!=NULL) free(g.v);g.v=(verType *)malloc(sizeof(verType)*g.vn);if(g.v=NULL) printf("nMalloc Erro

30、r!"); return;dg=0.0; st=Pi/g.vn*2.0; xc=getmaxx()/2; yc=getmaxy()/2;r=xc<yc?xc:yc-10;for(i=0,dg=0;i<g.vn;i+,dg+=st)x=xc+r*cos(dg);y=yc+r*sin(dg);g.vi.x=x; g.vi.y=y; g.vi.tag=0; sprintf(,"%02d",i+1);void readver(void)int i,ord;if(g.v!=NULL) free(g.v);g.v=(verType *)mallo

31、c(sizeof(verType)*g.vn);if(g.v=NULL) printf("nMalloc Error in readver!"); return; for(i=0;i<g.vn;i+)fscanf(fp,"%d%s%d%d",&ord,,&g.vi.x,&g.vi.y);g.vi.tag=0;void readedg(void)int i,j;edgType re;if(g.e!=NULL) free(g.e);g.e=(edgType *)malloc(sizeof(edgType)*g.

32、en);if(g.e=NULL) printf("nMalloc Error in read edg!"); return; for(i=0;i<g.en;i+)fscanf(fp,"%d%d%d",&re.bg,&re.ed,&re.wt);re.tag=(-1); for(j=i;(g.ej-1.wt>re.wt)&&(j>0);j-) copyedg(&(g.ej),&(g.ej-1);copyedg(&(g.ej),&re);void drawver(voi

33、d)int i,x1,y1,x2,y2;char s64;sprintf(s,"%s 结点数：d边数：d",,g.vn,g.en);pnthz(640-8*strlen()/3,0,12,-1,s);for(i=0;i<g.vn;i+)setcolor(12);setfillstyle(1,12);fillellipse(g.vi.x,g.vi.y,4,4); pnthz(g.vi.x+8,g.vi.y,15,-1,);void drawedg(void)int i,x1,y1,x2,y2;char s10;for(i=0;i

34、<g.en;i+)if(g.ei.tag<0) setcolor(7);else if(g.ei.tag=0) setcolor(8);else if(g.ei.tag=1) setcolor(10);else setcolor(g.ei.tag);x1=g.vg.ei.bg.x;y1=g.vg.ei.bg.y;x2=g.vg.ei.ed.x;y2=g.vg.ei.ed.y;line(x1,y1,x2,y2);sprintf(s,"%d",g.ei.wt);outtextxy(x1+x2)/2+4,(y1+y2)/2-10,s);void initial(voi

35、d)g.e0.tag=1;int find(int v)int i; for(i=0;(i<g.en)&&(g.ei.tag>=0);i+) if(g.ei.tag=0) continue;if(g.ei.bg=v|g.ei.ed=v) return g.ei.tag;return -1;void merge(int v1,int v2)int i;if(v1>v2) change(v1,v2); for(i=0;(i<g.en)&&(g.ei.tag>=0);i+) if(g.ei.tag=v2) g.ei.tag=v1;void

36、 kruskal(void)int i,j=2,v1,v2;initial(); for(i=1,j=2;i<g.en;i+) v1=find(g.ei.bg); v2=find(g.ei.ed); if(v1=v2&&v1!=(-1) g.ei.tag=0;else if(v1=v2&&v1=(-1) g.ei.tag=j+;else if(v1*v2<0) g.ei.tag=(v1<0?v2:v1);else if(v1!=v2) merge(v1,v2); g.ei.tag=(v1<v2)?v1:v2; #ifdef YANdraw

37、edg(); if(getch()=27) return;#endifvoid output(void)FILE *fout;int i;fout=fopen("OUTFILE.TXT","w"); if(fout=NULL) printf("nCan not open out file!");getch(); return; fprintf(fout,"%sn",);for(i=0;i<g.en;i+)if(g.ei.tag=1) fprintf(fout,"%s - %st%dn&q

38、uot;,,,g.ei.wt); fclose(fout);void fromfile(char fname)fp=fopen(fname,"r");if(fp=NULL)pnthz(20,30,15,-1,"无法打开图文件： ");outtextxy(144,30,fname);pnthz(20,50,15,-1,"任意键返回");getch(); cleardevice(); return;fscanf(fp,"%d%d%s",&g.vn,&a

39、mp;g.en,); readver();readedg();kruskal();drawedg();drawver();output();pnthz(16,getmaxy()-20,15,0," 任意键返回 "); getch();void userinput(void)char name128;int i;char help848=" 图文件结构要求如下 "," 结点数边数图名 ","结点序号X坐标Y坐标名称"," 其他结点信息 "," 起始结点序号终止结点序号权值&q

40、uot;," 其他边信息 ","详细示例参看附带文件CHINAMAP.TXT"for(i=0;i<8;i+) pnthz(36,100+i*20,15,-1,helpi);pn thz(40,30,15,-1," 图形文件名：");gotoxy(18,3); gets(name);cleardevice(); fromfile(name);void randomimage(void)int tag=1;randomize(); while(tag) cleardevice();pn thz(120,95,15,-1,"

41、输入图的结点数：");gotoxy(32,7); scanf("%d",&g.vn);pn thz(136,125,15,-1,"输入图的边数：");gotoxy(32,9); scanf("%d",&g.en); if(g.en<=(g.vn*(g.vn-1)/2)&&g.vn>2&&g.vn<30&&g.vn<g.en) tag=0;else pnthz(136,150,15,-1," 数据错误，请重新输入！ ")

42、; getch();strcpy(," 随机图形 ");cleardevice();randomver();randomedg();kruskal();drawedg();drawver();output();pnthz(16,getmaxy()-20,15,0,"任意键返回 ");getch();int choose(void)int tag=2,key,i;char s632=" 最小生成树问题黄健制作 ","请选择：","【1、演示图(城市通信网络)】","【2、用户

43、输入图文件】","【3、随机生成图信息】","【4、退出系统(ESC)】"cleardevice();while(1)for(i=0;i<6;i+) pnthz(100,20*i+40,15,(i=tag?7:0),si);key=getch();if(key=13) break;else if(key=27) return(0);else if(key>'0'&&key<'5') tag=key-'0'+1;else if(key=0) key=getch();

44、switch(key)case 72: tag-; break;case 80: tag+; break;if(tag<2) tag=2;else if(tag>5) tag=5;while(kbhit() getch();cleardevice();return tag-1;main()int i,tag=1;initgph(); settextstyle(1,0,1); do tag=choose(); switch(tag)case 1: fromfile("ChinaMap.txt"); break; case 2: userinput(); break

45、; case 3: randomimage(); break; case 4: tag=0; break;while(tag); fcloseall(); closegraph();四、设计和调试分析1.的数组表示。原设计另外建立一个数组用来保存集合以及子集。后来发现实现比较困难。只好给边增加一个tag域，其值为所属i该边集合的序Initgp的边赋值CHocS经访问的但不包侖在最小生成树中的边赋值t riandomedg在从文件中读入边的时候，考虑到后面要对边进行升序排序，故采用直接插入排序方式，每读入一条边就进行一次插入排序。算法的时间复杂度为审集合的并运算需要遍历全部已经访问过的边eadv

46、e其uagndon故复age为randomvn条边各扫描一次，时间复杂度为可以达到 o（n） er 芸的区位码和机号。未2.3.o（n）。克鲁斯卡尔算法对 在实现汉字显示时，涉及汉 试后得到转换公式。另外还涉及到文件的二进制读, 由于每一个汉字都是由256个像素构成，时间复杂1五、用户4.内码转换问题，在进行了多次尝 ：?/.,以及二进制移位操作等。所以显示一个长度为Uskaf汉字串的函数调用关系图main考虑到需要使用集合的并等运算，故图的存储方式选用了以存储边（带权）进入序运您境选择菜单操作系统°执行文牛为Ima耐Emerge最小生成树间题一一黄健制作请选择：【1、演示图C城市通

47、信网络）】【2、用户输入图文件】【3、随机生成图信息【4、退出系统（ESU）1图13. 使用上下键或数字键选择一个项目，则进入选项1. 选项一运行结果如下图2所示：中国通信网络 結点数；2 5边数 3 0鲁木齐42LB92114580S42534福州昆明£51r武汉400:成都上海25任意縫返回r一7沈阳37 ”#397图2其中颜色为亮绿色（该处为深灰色）的是在最小生成树中的边。2. 进入选项二后用户会看到提示如图 3 （见下页）。按要求输入图文件名，例如输入Ceshi.txt并回车，调用附带的测试文件，可以看到的输出画面见图4其中颜色为亮绿色（该处为深灰色）的是在最小生成树中的边。

48、3. 选项三的运行效果和选项一类似。4. 程序运行后会将运行结果以文本形式输出到文件OutFile.txt中，供用户查询使用。图文件结构要求如下结点数 边数图名结点序号X坐标Y坐标名称其他结点信息起始结点序号终止结点序号权值其他边信息详细示例参看附带文件CH INAMAPt TXT5.由于图文件的格式要求比较高，故提供了两个示例文件ChinaMap.txt和CeShi.txt，用户可以参考创建其他图文件。其含义如图3中所示。内容如下（为节省空间，分两栏显示）：10 19 189210 20 67610 21 21611 13 25511 24 67212 14 82512 24 36714 22 65115 17 70417 22 67418 23 53418 24 40920 23 51122 23 349六、测试结果测试文件ChinaMap.txt25 30中国通信网络0 北京 363 1081长春520 602 成都 185 2503 大连 475 1534 福州 420 3355 广州 300 3836 贵阳 200 3307哈尔滨570 208呼和浩特2