数据结构课程设计最小生成树解读.doc

软件1501-02班软件卓越1501班《数据结构课程设计》选题 要求： 本课程设计要求在16-17周完成，课程设计题目如附件所示，共有48题，题目分配方案如下：。难度为2*及以下的单人为一组完成选题，难度为3*及以上的最多2人一组完成选题，每个班的各组选题不可重复选择，确定后在学习委员处做好登记，软件1501班及卓越1501班在18周周二上午9:00-11:30在2205答辩（按学号来），软件1502班班18周周二下午14:00-16：00在我办公室2205答辩（按学号来），课程设计的源程序学习委员将其汇总起来，然后一个班刻录成一个光盘答辩时给我交过来，答辩人则只需带好课程设计报告和手提（演示程序）过来（答辩时间暂定上面时间，若有变化将另行通知）。课程设计报告规范见另外一个文件，请大家重视这次课程设计，我会根据你的课程设计报告和答辩情况当时给该门课程的成绩，不再另外安排时间接收课程设计报告的答辩要求，谢谢配合！ -戴成秋 2016-12-14 课程设计题目： 运动会分数统计　　任务：参加运动会有个学校，学校编号为1……。比赛分成个男子项目，和个女子项目。项目编号为男子1……，女子……30。不同的项目取前三名积分，前三名的积分分别为：5、3、2　　功能要求：可以输入各个项目的前三名的成绩；能统计各学校总分可以按学校编号、学校总分、男女团体总分排序输出；规定：输入数据形式和范围：可以输入学校的名称，运动项目的名称　　输出形式：有中文提示，各学校分数为整　　存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构；测试数据：测试数据及测试结果请在上交的资料中写明；订票系统　　任务：通过此系统可以实现如下功能：　　录入：　　可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）　　查询：　　可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；　　可以输入起飞抵达城市，查询飞机航班情况；　　订票：（订票情况可以存在一个数据文件中，结构自己设定）　　可以订票，如果该航班已经无票，可以提供相关可选择航班；　　退票： 可退票，退票后修改相关数据文件；　　客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。　　要求：　　根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能； 文章编辑功能：静态存储要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。　　存储结构使用线性表，分别用几个子函数实现相应的功能；　　输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出全部字母数、数字个数、空格个数、文章总字数（3）输出删除某一字符串后的文章；[问题描述]针对某个集体中人名设计一个哈希表，使得平均查找长度不超过R，并完成相应的建表和查表程序。[基本要求]　　假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用线性探测再散列法或链地址法处理冲突。[测试数据]　　取读者周围较熟悉的30个人名。[选作内容]　　（1） 从教科书上介绍的集中哈希函数构造方法中选出适用者并设计几个不同的哈希函数，比较他们的地址冲突率（可以用更大的名字集合作实验）。　　（2） 研究这30个人名的特点，努力找一个哈希函数，使得对于不同的拼音名一定不发生地址冲突。　　（3） 在哈希函数确定的前提下尝试各种不同处理冲突的方法，考察平均查找长度的变化和造好的哈希表中关键字的聚集性。宿舍管理查询软件任务：为宿舍管理人员编写一个宿舍管理查询软件, 程序设计要求：（1）建立数据文件 ，数据文件按关键字（姓名、学号、房号）进行排序(冒泡、选择、插入排序等任选一种)查询: 按姓名查询 按学号查询 按房号查询打印任一查询结果（可以连续操作） 校园导航问题 设计要求：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。”； 最小生成树问题（难度**） 设计要求：在n个城市之间建设网络，只需保证连通即可，求最