数据构造课程设计教学任务书.docx

《数据构造课程设计教学任务书.docx》由会员分享，可在线阅读，更多相关《数据构造课程设计教学任务书.docx（24页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数据构造课程设计教学任务书（数据构造）课程设计教学任务书计算机2007-1课程设计周数：第20周指导教师：刘文娟一、课程设计的目的数据构造课程主要是研究非数值计算的程序设计问题中所出现的计算机操作对象以及它们之间的关系和操作的学科。数据构造是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。学习数据构造是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。通过课程设计能够提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。通过此次课程设计主要到达下面目

2、的：?了解并把握数据构造与算法的设计方法，具备初步的独立分析和设计能力；?初步把握软件开发经过的问题分析、系统设计、程序编码、测试等基本方法和技能；?提高综合运用所学的理论知识和方法独立分析和解决问题的能力；?训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。二、课程设计的基本要求1、独立考虑，独立完成：课程设计中各任务的设计和调试要求独立完成，碰到问题能够讨论，但不能够拷贝。2、做好上机准备：每次上机前，要事先编制好准备调试的程序，认真想好调试步骤和有关环境的设置方法，准备好有关的文件。3、根据课程设计的详细要求建立的功能模块，每个模块要求根据如下

3、几个内容认真完成；其中包括：a需求分析：在该部分中叙述，每个模块的功能要求b概要设计在此讲明每个部分的算法设计讲明能够是描绘算法的流程图，每个程序中使用的存储构造设计讲明假如指定存储构造请写出该存储构造的定义。c具体设计各个算法实现的源程序，对每个题目要有相应的源程序能够是一组源程序，每个功能模块采用不同的函数实现源程序要根据写程序的规则来编写。要构造明晰，重点函数的重点变量，重点功能部分要加上明晰的程序注释。d调试分析测试数据，测试输出的结果，时间复杂度分析，和每个模块设计和调试时存在问题的考虑问题是哪些？问题怎样解决？，算法的改良设想。e课程设计总结：保存在word文档中总结能够包括：课程

4、设计经过的收获、碰到问题、碰到问题解决问题经过的考虑、程序调试能力的考虑、对数据构造这门课程的考虑、在课程设计经过中对（数据构造）课程的认识等内容；4、每组实现的结果必须进行检查和演示；程序源代码和程序的讲明文件必须上交，作为考核内容的一部分；上交时每人交一份，文件夹的取名规则为：“学号姓名，如“200413498高魁。该文件夹下至少包括：“源代码、“课程设计报告、“可执行文件。由学习委员采集刻盘按规定时间统一上交。5、报告提交时间：第20周星期五检查，第20周星期五下午5点之前由学习委员采集上交，迟交无成绩。形式：课程设计报告(要求打印和电子文档(统一刻盘。三、课程设计内容：1、排序算法演示

5、系统【问题描绘】设计一个测试程序比拟几种内部排序算法的关键字比拟次数和移动次数以获得直观感受。【基本要求】(1)实现各种内部排序。包括冒泡排序，直接选择排序，希尔排序，快速排序，堆排序。(2)待排序的元素的关键字为整数。其中的数据要用随机数产生(如10000个)，至少用5组不同的数据做比拟，再使用各种算法对其进行排序，记录其排序时间，再汇总比拟。(3)演示程序以人机对话的形式进行。每次测试完毕显示各种比拟指标值的列表，用饼图或条形图进行表示，以便比拟各种排序的优劣。(4)界面友好，易与操作。采用菜单方式进行选择。【选做内容】(1)对不同表长进行比拟；(2)验证各算法的稳定性；(3)输出界面的优

6、化。(4)使用汉字显示。2、校园导游咨询系统【问题描绘】设计一个校园导游程序，为来访的客人提供各种信息查询服务。【基本要求】(1)设计安徽理工大学的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示途径，存放途径长度等相关信息。(2)为来访客人提供图中任意景点相关信息的查询。(3)为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单途径。【选做内容】(1)系统功能的完善；(2)提供求任意两个景点之间的所有途径的功能； (3)提供校园图中多个景点的最佳访问道路查询，即求途经这多个景点的最佳短途径。(4)使用汉字显示。3、通

7、讯录【问题描绘】设计散列表实现通讯录查找系统。【基本要求】(1)设每个记录有下列数据项：电话号码、用户名、地址；(2)从键盘输入各记录，分别以电话号码为关键字建立散列表；(3)采用线性探测再散列法解决冲突；(4)查找并显示给定电话号码的记录；(5)通讯录信息文件保存；(6)要求人机界面友好，使用图形化界面；【选做内容】(1)系统功能的完善；(2)设计不同的散列函数，比拟冲突率；(3)在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。(4)使用汉字显示。【实现提示】假如不用界面编程，可用下面函数实现：主函数：根据选单的选项调用各函数，并完成相应的功能。Menu()的

8、功能：显示英文提示选单。Quit()的功能：退出选单。Create()的功能：创立新的通讯录。Append()的功能：在通讯录的末尾写入新的信息，并返回选单。Find()：查询某人的信息，假如找到了，则显示该人的信息，假如没有则提示通讯录中没有此人的信息，并返回选单。Alter()的功能：修改某人的信息，假如未找到要修改的人，则提示通讯录中没有此人的信息，并返回选单。Delete()的功能：删除某人的信息，假如未找到要删除的人，则提示通讯录中没有此人的信息，并返回选单。List()的功能：显示通讯录中的所有记录。Save()的功能：保存通讯录中的所有记录到指定文件中。Load()的功能：从指定

9、文件中读取通讯录中的记录。4、哈夫曼编码/译码器【问题描绘】设计一个哈夫曼编码/译码系统，对一个文本文件中的字符进行哈夫曼编码，生成编码文件压缩文件，后缀名.cod；反过来，可将一个压缩文件译码复原为一个文本文件(.txt)。【基本要求】(1)输入一个待压缩的文本文件名，统计文本文件中各字符的个数作为权值，生成哈夫曼树；(2)将文本文件利用哈夫曼树进行编码，生成压缩文件后缀名cod，(3)输入一个待解压的压缩文件名称,并利用相应的哈夫曼树将编码序列译码；(4)显示指定的压缩文件和文本文件；(5)界面友好，易与操作。采用菜单方式进行选择。【选做内容】(1)把哈夫曼编码用二进制位紧缩到一个变量中，

10、利用位运算进行真正的数据压缩，并求压缩比。(2)显示哈夫曼树；(3)使用汉字显示。5、二叉树遍历算法集成功能要求：1界面友好，易于操作。可采用菜单或其它人机对话方式进行选择。2实现各种二叉树的遍历。包括先序遍历、中序遍历、后序遍历的递归或非递归算法。3要求能查找任一结点在某种遍历序列中的前驱和后继。4演示程序以人机对话的形式进行。每次测试完毕正确显示各种遍历序列。在上交资料中请写明：存储构造、基本算法能够使用程序流程图、源程序、测试数据和结果、算法的时间复杂度、另外能够提出算法的改良方法；6、航班信息的查询与检索功能要求：1界面友好，易于操作。可采用菜单或其它人机对话方式进行选择。2实现对飞机

11、航班信息进行排序与查找。可按航班的航班号、起点站、到达站、起飞时间以及到达时间等信息进行查询。每个航班记录包括八项：航班号、起点站、到达站、班期、7、学生成绩管理系统图书管理系统、个人账簿管理系统功能要求：1界面友好，易于操作。可采用菜单或其它人机对话方式进行选择。2实现对学生成绩信息进行排序与查找。可按学生学号、姓名等信息进行查询。每个学生信息包含：学号，姓名，班级，语文，数学，英语，物理，化学等项。学生信息的存储构造能够选择顺序构造，可以以选择链式构造。8、表达式求值功能要求：当用户输入一个合法的表达式后，能够返回正确的结果。能够计算的运算符包括：加、减、乘、除、括号；能够计算的数要求在实

12、数范围内。能执行多重括号嵌套运算。对于异常表达式给出错误提示。要求使用静态栈数据构造。9、飞机订票系统功能要求：1录入：能够录入航班情况数据能够存储在一个数据文件中，数据构造、详细数据自定2查询：能够查询某个航线的情况如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班能否满仓；能够输入起飞抵达城市，查询飞机航班情况；3订票：订票情况能够存在一个数据文件中，构造本人设定能够订票，假如该航班已经无票，能够提供相关可选择航班；4退票：可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。5修改航班信息：当航班信息改变能够修改航班数据文件10、

13、多项式运算功能要求：1输入并建立多项式；2输出多项式，输出形式为整数序列n,c1,e1,c2,e2,cn,en,其中n是多项式的项数，ci和ei分别是第i项的系数和指数，序列按指数降序排列；3多项式a和b相加，建立多项式a+b；输出相加的多项式4多项式a和b相减，建立多项式a-b。输出相加的多项式5用带表头结点的单链表存储多项式。11、猴子选大王问题描绘：n只猴子要选大王，选举方法是：所有猴子按1，2，n编号围坐一圈，从第1号开场按1，2，m报数，凡报到m号的退出圈外，如此循环报数，直到圈内剩下一只猴子时，这只猴子就是大王。基本要求：分别选择顺序表和单向循环链表作为存储构造模拟整个经过，并依次

14、输出出列的各猴子的编号和最终所选出猴王的编号。12、停车场管理问题描绘：设停车场是一个能够停放n辆汽车的狭长通道，且只要一个大门能够供车辆进出。车辆按到达停车场时间的早晚依次从停车场最里向大门口处停放最先到达的第一辆车放在停车场的最里面。假如停车场已放满n辆车，则后来的车只能在停车场大门外的便道上等待，一旦停车场内有车开走，则排在便道上的第一辆车就进入停车场。停车场内如有某辆车要开走，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车辆再依原来的次序进场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。假如停留在便道上的车未进停车场就要离去，允许其离去，不

15、收停车费，并且仍然保持在便道上等待的车辆次序。编制一程序模拟该停车场的管理。提示：停车场采用栈式构造，停车场外的便道采用队列构造即使道就是等候队列。13、文本编辑器功能要求：运用链表与数组来处理字符串的各项操作。如插入，删除，查找，替换，显示等等。提示：对于自定义的文本文件“*.txt，其每一行表示一个结点用单链表来实现，能够进行一行的修改，删除，添加等；每一行中的字符可用一维数组来存储，这样能够利用数组的特性方便地进行插入，删除，替换，甚至能够进行排序操作！14、迷宫问题问题描绘:在迷宫中求从入口到出口的一条简单途径。提示：迷宫用一个二维字符数组maze来表示，用x表示纵坐标，y表示横坐标。

16、1定义探索迷宫的四个方向：RIGHT为向右，DOWN向下，LEFT向左，UP向上，用Switch语句根据当前的位置坐标来判定下一步要探索的方向求出下一步要走的位置坐标。2探索迷宫的四个方向的坐标表示：RIGHTx,y+1,DOWN(x+1,y),LEFT(x,y-1),UP(x-1,y)。3对每个方向探索时，用0表示可通过，用1表示不能通过是障碍，对探索过的位置加以标记。把每一个能够通过的位置坐标放入栈中，最后打印输出途径。4根据二维字符数组和加标记的位置坐标，输出迷宫的图形。15、电梯模拟运行问题描绘：模拟我校九层教学楼的电梯系统。该楼有一个自动电梯，能在每层停留。九个楼层由下至上依次称为第

17、一层、第二层、第九层，其中第一层是大楼的进出层，即是电梯的“本垒层，电梯“空闲时，将来到该层候命。乘客可随时地进出于任何层。对于每个人来讲，他有一个能容忍的最长等待时间，一旦等候电梯时间过长，他将放弃。模拟时钟从0开场，时间单位为0.1秒。人和电梯的各种动作均要消耗一定的时间单位简记为t，比方：有人进出时，电梯每隔40t检测一次，若无人进出，则关门；关门和开门各需要20t；每个人进出电梯均需要25t；假如电梯在某层精致时间超过300t，则驶回1层候命。基本要求：按时序显示系统状态的变化经过，即发生的全部人和电梯的动作序列。1用系统计时，每当有新的动作要输入时要暂停计时，等输入完成后即可继续计时

18、。2输入各个动作，最后，输入完毕后，能够保存所有动作序列，并有序输出。四、上交作业及成绩评定1、上交要求上交设计报告和相关光盘。其中设计报告要以打印文稿的形式上交。光盘内容包括程序源码设计报告的电子文档。整个班级的设计均刻在一张光盘上。上交时每人交一份，文件夹的取名规则为：“学号姓名，如“200711111王文。该文件夹下至少包括：“源代码、“课程设计报告、“可执行文件。由学习委员采集刻盘按规定时间统一上交。2、评分标准根据完成任务的情况(必须进行系统演示)、课程设计报告书的质量和课程设计经过中的工作态度等根据30%、50%、20%加权综合打分。成绩评定实行优秀、良好、中等、及格和不及格五个等级。上机程序检查未通过者、无设计报告者以及严重抄袭别人设计者，成绩为不及格。注：1.每个题目最多由5位同学完成，对于同一题目要求不同的同学采用不同的技术道路，杜绝两个同学内容一样的情况出现。2.每位同学保证都能按质按量完成设计任务，学院在设计结束后对每班抽取一定量同学进行答辩。课程设计报告不允许有两位或两位以上的学生报告内容一样或相近，一旦查出，取消设计成绩。3上课时间为上午7：3011：10，下午2：306：10。4可自选题目