数据结构课程实训指导书.doc

南 昌 工 程 学 院数据结构专题实训指导书主撰人：谭德坤 主审人：2010年6月本课程实训指导书根据数据结构专题实训教学大纲编写，适用于计算机科学与技术专业。一、本课程实训的性质与目的课程专题实训是学生对课程所学知识的综合运用，它与课堂听讲、上机实验、课外练习、自学研究相辅相成，构成一个完整的课程教学体系。数据结构是一门实践性强的课程，其中对算法设计和程序编写的掌握尤为重要。学生虽然可以通过与课堂教学同步的上机实验完成相关内容的练习，但却往往局限于一些功能简单、彼此之间关系独立的算法和程序。课程实训是一种综合训练，致力于培养学生全面、灵活的算法设计思想和较高的编程能力，为今后从事计算机开发与应用打下基础。新世纪需要具有丰富科学知识、独立解决实际问题、有创造能力的新型人才，这也是该专题实训教学的最终目的。通过本课程专题实训，巩固学生对数据结构课程中的几大数据类型链表、有序表、图、树的建立、添加、删除、查找以及排序的操作。使学生能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养良好的程序设计技能。二、本课程实训教学内容与时间安排序号实训内容实践要求时间（天）备注1运动会分数统计编程实现运动会成绩统计101人完成2十进制四则运算计算器利用二叉树和栈求算术表达式的值。101人完成3飞机订票系统设计存储结构存放航班信息，设计程序完成订票、退票、查询功能。101人完成4哈夫曼编码/译码器设计一个哈夫曼编码/译码系统，对一个文本文件进行编码/解码。101人完成5个人通讯录设计散列表实现通讯录查找系统。101人完成6猴子选大王编程实现猴子选大王问题101人完成7迷宫问题可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；101人完成8小型文本编辑器实现一个简单的文本编辑器。101人完成9校园导航问题找出校园旅游的最佳路径（旅客不重复游览）101人完成10排序问题用三种以上算法实现20000个数据的排序101人完成11学生搭配问题编程实现学生搭配问题101人完成(一) 实训1 运动会分数统计问题描述：参加运动会有n个学校,学校编号为1n.比赛分成m个男子项目,和w个女子项目.项目编号为男子1.m,女子m+1.m+w.不同的项目取前五名或前三名积分;取前五名的积分分别为:7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m<=20,n<=20）。功能要求：1) 可以输入各个项目的前三名或前五名的成绩；2) 能统计各学校总分，3) 可以按学校编号、学校总分、男女团体总分排序输出；4) 可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。规定：输入数据形式和范围：20以内的整数（如果做得更好可以输入学校的名称，运动项目的名称）输出形式：有中文提示，各学校分数为整形界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。编程提示：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构。(二) 实训2 十进制四则运算器问题描述：设计一个简单的计算器，可以做加、减、乘、除等基本运算。功能要求：1）计算任意一个算术表达式的加法、减法、除法以及乘法。2）运算数为整数和小数3）人机界面自定义，要友好。如用户输入错误在计算之前可以修改。编程提示：1）设置运算符栈和运算数栈辅助分析算符优先关系。2）在输入表达式的字符序列的同时，完成运算符和运算数（整数）的识别处理，以及相应的运算。3）在识别出运算数的同时，要将其字符序列形式转换成整数形式。(三) 实训3 飞机订票系统问题描述：1）录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）2）查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；3）订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；4）退票： 可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。5）修改航班信息：当航班信息改变可以修改航班数据文件功能要求：根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能。编程提示：航班信息和订票信息定义为一个结构体，并用链表实现。(四) 实训4 哈夫曼编码/译码器问题描述：设计一个哈夫曼编码/译码系统，对一个文本文件中的字符进行哈夫曼编码，生成编码文件（压缩文件，后缀名.cod）；反过来，可将一个压缩文件译码还原为一个文本文件(.txt)。功能要求：1) 输入一个待压缩的文本文件名， 统计文本文件中各字符的个数作为权值，生成哈夫曼树；2) 将文本文件利用哈夫曼树进行编码，生成压缩文件（后缀名cod），3) 输入一个待解压的压缩文件名称,并利用相应的哈夫曼树将编码序列译码；4) 显示指定的压缩文件和文本文件；5) 界面友好，易与操作。采用菜单方式进行选择。编程提示：解本题要注意两个问题：1） 要熟悉C语言的文件操作。2） 掌握哈夫曼树的原理(五) 实训5 个人通讯录问题描述：设计散列表实现通讯录查找系统。功能要求：1) 设每个记录有下列数据项：电话号码、用户名、地址；2) 从键盘输入各记录，分别以电话号码为关键字建立散列表；3) 采用二次探测再散列法解决冲突；4) 查找并显示给定电话号码的记录；5) 通讯录信息文件保存；6) 要求人机界面友好，使用图形化界面；编程提示：主函数：根据选单的选项调用各函数，并完成相应的功能。Menu()的功能：显示英文提示选单。Quit()的功能：退出选单。Create()的功能：创建新的通讯录。Append()的功能：在通讯录的末尾写入新的信息，并返回选单。Find()：查询某人的信息，如果找到了，则显示该人的信息，如果没有则提示通讯录中没有此人的信息，并返回选单。Alter()的功能：修改某人的信息，如果未找到要修改的人，则提示通讯录中没有此人的信息，并返回选单。Delete()的功能：删除某人的信息，如果未找到要删除的人，则提示通讯录中没有此人的信息，并返回选单。List()的功能：显示通讯录中的所有记录。Save()的功能：保存通讯录中的所有记录到指定文件中。Load()的功能：从指定文件中读取通讯录中的记录。(六) 实训6 猴子选大王问题描述：一堆猴子都有编号，编号是1，2，3 .m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。功能要求： 输入数据：输入m,n m,n 为整数，n<m输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号 ，建立一个函数来实现此功能。编程提示：用循环队列实现。(七) 实训7 迷宫问题问题描述：用m行n列的m*n个正方格表示一个迷宫，其中划有斜线的方格表示不可通行，未划有斜线的方格表示可以通行。请编写寻找从入口到出口的一条最短路径的程序。功能要求：1)迷宫的规格（即行数与列数）,状态设置(即各方格能否通行的状态)，以及入口和出口的位置，均应由输入随机确定。2)求得的最短路径，应该以从入口到出口的路径上的各个方格的坐标的线性序列输出。当无通路时，应该报告无路径的信息。3)尽量采用结构化程序设计方法，要求对各个模块的功能及参数作必要的说明。编程提示：(1)迷宫可以采用matrix类型的二维数组A表示。A.rownum与A.colnum分别表示迷宫的实际的行数与列数。而A.mazeij表示迷宫中第i行第j列的一个方格，用A.mazeij=0表示该方格可以通行，用A.mazeij=1表示该方格不可以通行。(2)由于要寻找从入口到出口的一条最短路径，最好将迷宫看作是一个图结构。则问题转化为寻找从对应于入口顶点到对应于出口顶点的一条最短路径的问题。该问题可以采用从入口顶点出发，进行广度优先搜索遍历，直到遇到出口顶点或者遍历完毕也没有遇到出口顶点为止。这二种情况分别对应于最短路径探索成功与查无通路的事实。(八) 实训8 小型文本编辑器问题描述：实现一个类似于记事本的文本编辑器。功能要求：1)具有图形菜单界面；2)查找，替换（等长，不等长），插入（插串，文本块的插入）、块移动（行块，列块移动），删除3)可正确存盘、取盘；4)正确显示总行数。编程提示：关键是对字符数据结构进行操作。(九) 实训9 校园导航问题问题描述：设计一个校园导游程序，为来访的客人提供各种信息查询服务。功能要求：(1) 设计南昌工程学院的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。(2) 为来访客人提供图中任意景点相关信息的查询。 (3) 为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。（并且景点不重复）编程提示：本题是求某个源点到其余顶点之间的最短路径。可由Dijkstra算法求得。(十) 实训10 排序问题问题描述：利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。功能要求：1)至少采用三种方法实现上述问题求解（提示，可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序）。并把排序后的结果保存在不同的文件中。2)统计每一种排序方法的性能（以上机运行程序所花费的时间为准进行对比），找出其中两种较快的方法。3)如果采用4种或4种以上的方法者，可适当加分。编程提示：本题的关键是：） 随机数产生函数；） 程序运行时间统计函数。(十一) 实训11 男女搭配问题问题描述： 一班有m个女生，有n个男生(m不等于n)，现要开一个舞会。男女生分别编号坐在舞池的两边的椅子上，每曲开始时，依次从男生和女生中各出一人配对跳舞，本曲没成功配对者坐着等待下一曲找舞伴。功能要求：请设计一系统模拟动态地显示出上述过程,要求如下:1)输出每曲配对情况；2)计算出任何一个男生(编号为X)和任意女生(编号为Y),在第K曲配对跳舞的情况。至少求出K的两个值。编程提示：本题用两个队列求解比较方便，一个男生队列，一个女生队列。三、注意事项学生课程实训完成后，必须提交课程实训报告。课程实训报告要求：课程实训报告可采用统一规范的稿纸书写，也可以用A4纸双面打印，并装订成册。内容包括：（1） 设计题目、专业、班级、学生姓名、学生学号、指导教师姓名、起止时间（2） 具体任务（3） 软件环境（4） 算法设计思想及流程图（5） 源代码（6） 运行结果（7） 收获及体会（8） 参考文献课程设计报告封面格式见附录1。四、上交成果及成绩评定（一）上交成果课程实训结束后，每个学生必须以如下形式展现自己的成果：） 课程实训报告；） 当场向指导教师演示系统运行结果。（二）成绩评定课程实训成绩评定标准：根据完成任务的情况(必须进行系统演示)、课程实训报告书的质量和课程实训过程中的工作态度等按照40%、40%、20%加权综合打分。附录1南 昌 工 程 学 院数据结构课程实训报告设计题目： 专 业 班 级 学 生 学 号 指导教师 起止时间 年 学期