2013年度春季数据结构课程设计.doc

课程设计要求 [选好题目]： 每人必须从下面5题中任意选一题作为设计，独立思考，认真完成，课程设计中各任务的设计和调试要求独立完成，遇到问题可以讨论，但不可以拷贝。 [课程设计报告]: (保存在word 文档中,文件名要求 按照班级_姓名_学号_课程设计报告起名,如文件名为11信科1_张三_001_课程设计报告.doc )按照课程设计的具体要求建立的功能模块,每个模块要求按照如下几个内容认真完成; (1)需求分析： 在该部分中叙述每个模块的功能要求 (2)概要设计 在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明(如果指定存储结构请写出该存储结构的定义。 (3)详细设计 各个算法实现的源程序，对每个题目要有相应的源程序（可以是一组源程序，每个功能模块采用不同的函数实现）源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。 (4)调试分析 测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？），算法的改进设想。 [课设总结]： （保存在word 文档中）总结可以包括 : 课程设计过程的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考、在课程设计过程中对《数据结构》课程的认识等内容； [课设提交]: 提交内容：课程设计报告（具体格式见题目后附录），课程总结和附程序源代码总共一份，统一采用A4纸双面打印输出。并由各班学委将电子版收齐后，统一提交。实现的结果以自愿的原则参与演示，参与者可加5分，具体时间待定。 提交时间: 第17周星期5前， 迟交无成绩。 注意事项：1：请同学们注意课程设计提交时间。 2：请按照附件提供的格式组织课程设计，并附上自评分。 【课程设计题目】： 1、.利用随机函数产生两列(每列个数均为200且每个数均不小于10) 的随机整数,对这两列整数写一个程序实现如下功能操作： (1)两列整数在顺序存储方式中， a)找出这两列数中的素数 b) 把两列数中相同的数转化为二进制数输出。 (2)两列整数在链表存储方式中， a)统计两链表中相同元素的个数; b)合并这两个链表为一个 c)分别删除第一链表中能被2整除的结点和第二个链表中能被3整除的结点。 2、.利用随机函数产生127个(不大于200且各不相同的)随机整数，用这些整数来生成一棵二树，1）分别对二叉树进行先序遍历，中序遍历和后序列遍历输出树中结点元素序列。注意：先序遍历输出要求采用非递归来实现。 2） 输出二叉树中从根到叶子结点间整数和最小的结点路径序 列。 3、题目： 校园导游图 设计一个校园导游程序，随着华农大校园建设越来越漂亮，春季来赏花的游客逐年攀升，请为来访客人提供各种信息查询任务。 基本要求： 1）设计你所在学校的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介信息，以边表示路权，存放路径长度等相关信息。 2）为来访客人提供图中任意景点相关信息的查询（如景点简介，相关交通信息等） 3）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。 4、用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE” 字符 A B C D E F G H I J K L M 频度 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z 频度 57 63 15 1 48 51 80 23 8 18 1 16 1 5 、农夫，狼，羊和菜过河问题 问题描述：有一个农夫带有一条狼，一只羊和一筐菜，想从河的左边乘船去右边，但是由于船太小，每次农夫只能带一样东西过河，而且，如果没有农夫看，则狼会吃羊，羊会吃菜。问农夫怎样过河才能把每样东西安全送过河。 要求：（1）将上面问题用图表示出来；（2）选择图的一种存储结构，编写一个自动生成图的算法。3）在（2）的基础上编写求解问题算法的程序。 ×××××××××××××××××××××× ×××××××课程设计格式要求××××××× ×××××××××××××××××××××× A4打印，按统一封面装订，附页码; 第二 页附上评语评分表格以及自评分数; 报告正文部分主要内容应包括： (保存在word 文档中,文件名要求 按照班级_姓名_学号_课程设计报告起名