《数据结构课程设计大纲》课程教学大纲（本科）.docx

数据结构课程设计大纲(Curriculum Design of Data Structures)课程代码：06460044学分：L5周数：1.5周（其中：讲课2学时；设计 学时；上机30学时；答辩 学时）先修课程：程序设计基础、离散数学、数据结构A适用专业：计算机科学与技术教 材：无一、课程性质与目标（一）课程性质数据结构课程设计是必修的实践性教学环节之一，是学习了数据结构A 课程后的综合性实验课程，是对该课程所学知识进行的一次全面的综合训练。数据结 构课程设计着眼于原理与应用结合点，使学生学会如何把书上学到的知识用于解决实 际问题，培养软件工作所需要的动手能力；另一方面，能使书本上的知识变“活”，起 到深化理解和灵活掌握教学内容的目的。数据结构课程设计的题目是软件设计的综合训 练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧、以至一 整套软件工作规范的训练和科学作风的培养。（二）课程目标课程目标1.知识方面1.1 全面梳理所学的数据结构的相关知识，进一步深入理解数据结构的基本概念、 逻辑特性、存储表示方法、算法描述及其性能分析方法。1.2 熟悉软件开发的基本过程，初步掌握软件开发过程的问题分析、系统设计、 程序编码、测试等基本方法和技能。课程目标2.能力与素质方面具备利用数据结构相关知识解决实际问题的初步的独立分析和设计能力。2.1 具有针对实际问题的特点选用合适的数据结构、设计相应的算法并加以实现的能力。2.2 具有撰写比较完善的课程设计报告进行论述的能力。二、课程目标与专业毕业要求指标点的对应关系本课程支撑专业培养计划中毕业要求指标点1.4、3.3、3.4、6.3、12.2。毕业要求指标点L4能够应用专业知识解决工程计算问题；毕业要求指标点3. 3能够针对特定软件需求、可复用模块或组件完成数据结构和 算法的设计；毕业要求指标点3. 4能够在设计中体现创新意识；毕业要求指标点6. 3能够撰写各类软件工程文档并进行评价；毕业要求指标点12.2能够养成主动惯并表现出不断探索的成效，能够自我评价。毕业要求课程目标指标点1.4指标点3. 3指标点3. 4指标点6. 3指标点12. 2课程目标L1VV课程目标1.2VV课程目标2.1VVV课程目标2.2VVV课程目标2.3VVV二、内容与进度安排L内容及要求a.设计内容课程设计选题和一般要求参见附录1,课程设计选题可以由任课教师根据实际情 况适当安排。要求通过设计，在数据结构的逻辑特性和物理表示、数据结构的选择应用、算 法的设计及其实现等方面加深对课程基本内容的理解和综合运用。b.其他要求：(1)认真上机编程，不得从事与课程设计无关的活动。(2)课程设计报告包括封面、目录、报告正文、参考文献。报告正文中要给出对课程 项目功能的简要介绍、总体设计(功能模块结构)、详细设计(采用的逻辑结构 和存储结构的分析与设计)、算法设计以及关键算法的描述或流程图、程序测试（测试用例和程序运行结果）。报告需打印提交，代码无需打印。（3）报告提交要求。每位学生需将报告和代码程序代码压缩，文件名命名格式为：学 号+姓名+专业班级.rar,如：3140602026+张三+计算机1401 .rar,并上传到指定的 ftp服务器，班长收齐所有同学的课程设计报告后一起提交给指导教师。C.实验环境普通PC机，软件要求安装VS.net开发环境。2.进度安排本课程设计为1.5周，共7天，上机为30学时，学生需在上机前做好准备工作, 最后两天为现场检查时间，每位学生需现场演示并回答老师提出的问题。序号设计内容时间支撑的课程目标1环境搭建和系统需求分析1天1.1, 1.2, 2.1, 2.22系统数据结构分析选 择与设计1天1.1, 1.2, 2.1, 2.23系统数据结构相关算 法功能设计与实现 （一）1天1.1, 1.2, 2.1, 2.24系统数据结构相关算 法功能设计与实现 （-）1天1.1, 1.2, 2.1, 2.25系统数据结构相关算 法功能设计与实现 （三）1天1.1, 1.2, 2.1, 2.26系统联调与测试1天1.1, 1.2, 2.1, 2.27系统总结及演示以及 对指导教师提出的关 键问题进行分析汇报1天1.1, 1.2, 1.3, 2.1, 2.2, 2.3三、考核与成绩评定1.考核材料平时考勤情况，预习准备情况，程序实现与演示情况，回答问题情况，课程设 计报告、程序。2.考核要求及权重注：具体评分细则详见附录2考核内容考核要求考核权重备注平时考勤共考勤5次，每缺勤1次扣1分5%预习准备情况根据上机前的准备情况评分25%功能实现与演示根据现场演示功能情况评分50%回答问题根据现场演示对提问问题的回答情况 评分10%课程设计报告根据设计报告格式和内容情况评分10%四' 大纲说明1 .学生在本课程设计前应学习了程序设计基础、离散数学、数据结构A 等课程，时间上可安排在数据结构A课程学习结束之后。2 .参考文献1数据结构:C+实现，缪淮扣，科学出版社，2014年第2版。2数据结构（C语言版），严蔚敏，清华大学出版社，1997年第1版。3数据结构（用面向对象方法与C+语言描述），殷人昆，清华大学出版 社，2007年第2版。4数据结构、算法与应用:C+语言描述数据结构、算法与应用：C+语言描 述 （Data Structures,Algorithms,and Application in C+）（美）Sartaj, Sahni 著，王立柱 等译，机械工业出版社，2015年第2版。2017年8月附录1课程设计建议选题选题一、学生信息管理系统问题描述：设计一个学生信息管理系统，实现对学生基本信息的添加、删除、修改和查询等操作。要求：程序采用文本界面或图形界面下进行交互的工作方式，完成如下功能:（1） 多种方式建立学生信息每个学生信息由学号、姓名、数学、英语和语文组成； 可以通过手工录入每个学生信息，并在C盘下以StudentFile.txt保存；也可以导入某个路径下存放学生信息的文本文件。（2） 浏览所有学生信息。（3） 按照学号对所有学生信息进行升序、降序排列，并输出可选用冒泡、选择等算法；不仅输出屏幕显示，还需要写入存放学生信息的文件。（4） 按姓名、学号等方式，实现对学生信息精确查询、模糊查询，并输出屏幕显示精确查询结果演示查询“姓名是王五”同学信息，则输出学号 姓名高数英语离散数学2007112011 王五 889078 模糊查询结果演示查询姓“刘”的同学信息（输入“刘”），则输出学号 姓名2007112011 刘梅2007112011 刘强2007112011 刘星学号 姓名2007112011 刘梅2007112011 刘强2007112011 刘星高数888786英语离散数学9078 8098 7058 能够实现连续多次查询（5） 学生信息的插入、删除、修改。通过插入、删除和修改后，保持所有学生信息的有序性;插入、删除和修改后，对存放所有学生信息的文件及时更新。（6） 数据的统计功能统计每个学生的平均分和总分； 统计每个科目的平均分和最高分、最低分；将上述统计结果，写入存放学生信息的文件。选题二、银行业务的模拟系统 问题描述：设计一个银行业务模拟系统，模拟银行的业务运行并计算一天中客户在银行逗留的平均时间。 银行有N （N的取值自己定义）个窗口对外接待客户，从早晨银行开门起不断有客户进入银行。由 于每个窗口在某个时刻只能接待一个客户，因此在客户人数众多时需在每个窗口前顺次排队，对于 刚进入银行的客户，如果某个窗口的业务员正空闲，则可上前办理业务；反之，若N个窗口均有客 户所占，他便会排在人数最少的队伍后面。要求：（1） 在界面上可以设定银行的对外营业时间（银行的开门时间以及银行的关门时间）。（2）用人机交互的方式来输入客户的到达时间以及客户的离开时间，用队列来存储客户的到 达事件和客户的离开事件。（3） 可以友好的显示出在某一天中整个银行系统中客户在银行逗留的平均时间。选题三、停车场管理系统问题描述：设计一个停车场管理系统，模拟停车场的运作。要求：（1） 要求以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行 模拟管理；要求处理的数据元素包括如下数据项：汽车“到达”或“离去”信息、汽车牌照及“到 达”或“离去”的时刻；（2） 若是车辆到达，就输出汽车在停车场内或便道上的停车位置；若是车离去，就输出汽车 在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。（3） 完成该停车场的一些信息统计功能（如每天到达/离开的车次，停车总时数、每天的停 车费用等）。选题四、哈夫曼编码/译码器问题描述：设计一个哈夫曼编码/译码系统，对一个文本文件中的字符进行哈夫曼编码，生成编码文件（后 缀名.COd）;反过来，可将一个编码文件还原为一个文本文件（txt）。要求：（1） 输入一个待压缩的文本文件名，统计文本文件中各字符的个数作为权值，生成哈夫曼树;将文本文件利用哈夫曼树进行编码，生成编码文件（后缀名cod）；（2） 输入一个待解压的压缩文件名称，并利用相应的哈夫曼树将编码序列译码；显示指定的编码文件和文本文件；选题五、最小生成树问题问题描述：已知一个无向连通网表示n个城市以及城市间可能设置的通信线路，其中网的顶点表示城市， 边表示两个城市之间的线路，赋于边上的权值表示相应的代价。对于n个点的连通网可以建立许多 不同的生成树，每一棵生成树都可以是一个通信网。现在，我们要选择这样一棵生成树，使总的耗 费最小。即构造连通网的最小生成树的问题。要求：（1） 建立城市交通网的存储结构。（注：数据输入可以是键盘输入或文件输入两种方式）分别用Prim算法和Kruskal算法构造最小生成树，并输出最小生成树的代价及生成树的 边。（注：结果的输出可以是屏幕输出和文件输出两种方式）选题六、二叉排序树的操作演示问题描述：设计一个二叉排序树的各种操作的演示系统，完成对二叉排序树的建立、插入、删除和查找操 作的演示。要求：（1） 给出一组关键值，建立相应的二叉排序树，并显示建立的二叉排序树；删除一个结点的操作。要求可以实现删除根结点、叶子结点以及其它任意结点的功能， 并显示操作前、后的二叉排序树；（2） 插入一个新结点的操作，并显示操作前、后的二叉排序树；对给定的值在二叉排序树进行查找，并给出查找结果。选题七、内部排序算法的性能分析 问题描述：设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。要求：（1） 对起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法进行比较；待排序表的表长不小于1000,表中数据随机产生，至少用3组不同数据作比较，比较指 标有：关键字参加比较次数和关键字的移动次数（关键字交换记为3次移动）；（2） 输出比较结果。附录2数据结构课程设计评分细则（按100分计算）项目优秀 (100-90)良好 (80-89)中等 (70-79)及格 (60-69)不及格 （60以下）预习准备情况预习准备内预习准备内预习准备内有一定的预预习准备内容25%容很充分容充分容较充分习准备内容没有或极少实现所有功实现所有功有1个必须有2个必须有2个功能未实能，并有所增能；提示清实现的功能实现的功能现；基本没有提功能实现与演加;提示很清晰；演示过不完善；提不完善；有示；无法正常演示50%晰;演示过程程熟练；示较清晰；一定提示；示；非常熟练；演示过程熟演示过程不练程度一般熟练回答问题10%完全正确，回 答流利正确基本正确存在错误错误项目齐全，格项目较齐项目较齐项目不够齐项目不齐全，格式清晰，分析全，格式清全，格式较全，格式不式混乱，不能表过程完整，设晰，分析过清晰，分析够清晰，能达设计过程和设计报告10%计完善，表达程完整，设过程基本完表达出一定思路准确计较完善，整，设计基的设计过程表达较准确本完善，表和思路达基本准确