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

1、数据结构课程设计（Curriculum Design of Data Structures）课程代码：06460089学分：1周数：1周（其中：讲课 学时；设计 学时；上机16学时；答辩4学时） 先修课程：程序设计基础A,面向对象程序设计A,离散数学，数据结构B 适用专业：信息安全教材：数据结构-C+实现（第二版），缪淮扣，科学出版社，2014年第二版一、课程性质与目标（一）课程性质（说明课程设计在本科人才培养体系中的定位与主要作用）数据结构课程设计是必修的实践性教学环节之，是在学习数据结构B课程之后 的综合性实验课程，是利用该课程所学知识进行的一次全面综合训练。数据结构课程设计着 眼于原理与

2、应用的结合点，使学生学会如何把书上学到的理论知识用于解决实际问题，培养软 件工作所需要的动手能力；另一方面，能使书本上的知识变“活”，起到深化理解和灵活掌握教 学内容的目的。数据结构课程设计的题目是软件设计的综合训练，包括问题分析、总体结构设 计、用户界面设计、程序设计基本技能和技巧、以至一整套软件工作规范的训练和科学作风的 培养。（二）课程目标课程目标1：全面梳理所学的数据结构相关知识，进一步深入理解数据结构的基本概念、 逻辑特性、存储表示方法、算法描述及其性能分析方法。课程目标2：熟悉软件开发的基本过程，初步掌握软件开发过程的问题分析、系统设计、 程序编码、测试等基本方法和技能。课程目标3

3、：具备利用数据结构相关知识解决实际问题的初步的独立分析和设计能力。课程目标4：具备使用程序开发语言编写和调试代码的能力。（三）课程目标与专业毕业要求指标点的对应关系本课程支撑专业培养计划中毕业要求指标点1-2、3-1和5-2o.毕业要求1-2：掌握计算机基础知识。.毕业要求3T：掌握对计算机系统进行分析和总体设计的方法与过程。.毕业要求5-2：针对信息安全复杂工程问题，具备对所需工具进行分析及二次开发的能 力。标毕业要求指标殴课程目标1课程目标2课程目标3课程目标4毕业要求1-2/毕业要求3-1/毕业要求5-2/注：课程目标与毕业要求指标点对接的单元格中可输入也可标注“H、M、L”。二、内容与

4、进度安排1.内容及要求（1）课程设计题目及内容课程设计可选参考题目如下，任课教师可以根据实际情况进行安排或重新设计题目。选题1：学生信息管理系统设计个学生信息管理系统，实现对学生基本信息的添加、删除、修改和查询等操作。 要求：程序采用文本界面或图形界面下进行交互的工作方式，完成如下功能：（I）多种方式建立学生信息。每个学生信息由学号、姓名、数学、英语和语文组成；可以通过手工录入每个学生信息，并在C盘下以SiudeniFile.lxi保存；也可以导入某个路径下存放学生信息的文本文件。（II）浏览所有学生信息。（III）按照学号对所有学生信息进行升序、降序排列，并输出。可选用冒泡、选择等算法；不仅

5、输出屏幕显示，还需要写入存放学生信息的文件。（IV）按姓名、学号等方式，实现对学生信息精确查询、模糊查询，并输出屏幕显示。精确查询结果演示;查询“姓名是王五”同学信息，则输出:学号姓名高数英语离散数学7007112011889078 模糊查询结果演示；查询姓“刘”的同学信息（输入“刘”），则输出学号姓名高数英语离散数学2007112011刘梅刘强889078 2007112011878098 2007112011刘星867058 能够实现连续多次查询。（V）学生信息的插入、删除、修改。通过插入、删除和修改后，保持所有学生信息的有序性；插入、删除和修改后，对存放所有学生信息的文件及时更新。（VI

6、）数据的统计功能。统计每个学生的平均分和总分；统计每个科目的平均分和最高分、最低分；将上述统计结果，写入存放学生信息的文件。选题2：银行业务的模拟系统设计一个银行业务模拟系统，模拟银行的业务运行并计算一天中客户在银行逗留的平均时 间。银行有N （N的取值自己定义）个窗口对外接待客户，从早晨银行开门起不断有客户进入 银行。由于每个窗口在某个时刻只能接待一个客户，因此在客户人数众多时需在每个窗口前顺 次排队，对于刚进入银行的客户，如果某个窗口的业务员正空闲，则可上前办理业务；反之， 若N个窗口均有客户所占，他便会排在人数最少的队伍后面。要求：（I）界面上可以设定银行的对外营业时间（银行的开门时间以

7、及银行的关门时间）。（H）用人机交互的方式来输入客户的到达时间以及客户的离开时间，用队列来存储客户的到达 事件和客户的离开事件。（III）可以友好地显示出在某一天中整个银行系统中客户在银行逗留的平均时间。选题3：停车场管理系统设计一个停车场管理系统，模拟停车场的运作。要求：（I）以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管 理。（II）处理的数据元素包括如下数据项：汽车“到达”或“离去”信息、汽车牌照及“到达”或 “离去”的时刻。（III）若是车辆到达，就输出汽车在停车场内或便道上的停车位置；若是车离去，就输出汽车 在停车场内停留的时间和应交纳的费用（在便道上

8、停留的时间不收费）。（IV）完成该停车场的一些信息统计功能（如每天到达/离开的车次，停车总时数、每天的停车 费用等）。选题4：哈夫曼编码/译码器设计一个哈夫熨编码/译码系统，对一个文本文件中的字符进行哈夫曼编码，生成编码文件 （后缀名.cod）；反过来，可将一个编码文件还原为一个文本文件（.txt）。要求：（I）输入一个待压缩的文本文件名，统计文本文件中各字符的个数作为权值，生成哈夫曼树。（II）将文本文件利用哈夫曼树进行编码，生成编码文件（后缀名cod）。（ill）输入一个待解压的压缩文件名称，并利用相应的哈夫曼树将编码序列译码。（IV）显示指定的编码文件和文本文件。选题5：最小生成树问题已

9、知一个无向连通网表示n个城市以及城市间可能设置的通信线路，其中网的顶点表示城 市，边表示两个城市之间的线路，赋于边上的权值表示相应的代价。对于n个点的连通网可以 建立许多不同的生成树，每一棵生成树都可以是一个通信网。现在，我们要选择这样一棵生成 树，使总的耗费最小，即构造连通网的最小生成树的问题。要求：（I）建立城市交通网的存储结构。（注：数据输入可以是键盘输入或文件输入两种方式）（II）分别用Prim算法和Kruskal算法构造最小生成树，并输出最小生成树的代价及生成 树的边。（注：结果的输出可以是屏幕输出和文件输出两种方式）选题6：二叉排序树的操作演示设计一个二叉排序树的各种操作的演示系统

10、，完成对二叉排序树的建立、插入、删除和查找操作的演示。要求：（I）给出一组关键值，建立相应的二叉排序树，并显示建立的二叉排序树。（ID删除一个结点的操作。要求可以实现删除根结点、叶子结点以及其它任意结点的功能,并显示操作前、后的二叉排序树。（III）插入一个新结点的操作，并显示操作前、后的二叉排序树。（IV）对给定的值在二叉排序树进行查找，并给出查找结果。选题7：内部排序算法的性能分析设计一个测试程序比较几种内部排序算法的关犍字比较次数和移动次数以取得直观感受。要求：（I）对起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法进行比较。（II）待排序表的表长不小于1000,表中数据

11、随机产生，至少用3组不同数据作比较，比 较指标有：关键字参加比较次数和关键字的移动次数（关键字交换记为3次移动）。（III）输出比较结果。（2）课程设计要求（I）认真上机编程，不得从事与课程设计无关的活动。（11）课程设计报告包括封面、成绩评定表、目录和正文。报告正文中要给出对课程项目功 能的简要介绍、总体设计（功能模块结构）、详细设计（采用的逻辑结构、存储结构和算法 的分析与设计）、编码（数据结构定义和程序实现）、程序测试（测试用例和程序运行结果）、 收获与体会。报告需打印提交。（III）报告提交要求。每位学生需将报告和程序代码压缩，压缩包命名格式为：学号+姓 名.rar,如：3140602

12、026+张三.rar,班长收齐后和报告一起提交。2.进度安排序号设计内容时间支撑的课程目标1总体设计2学时22详细设计6学时1、 2、 3、 43编码与测试8学时1、 2、 3、 44演示与答辩4学时1、 2、 3、 4三、考核与成绩评定.考核材料平时检查情况、课程设计程序演示与答辩情况、课程设计报告。.考核要求及权重注：可根据实际情况安排考核内容与考核权重。考核项目考核内容考核要求考核权重支撑的指标点平时学习与工作态度平时出勤率、学习与工作认真程度10%独立工作能力工作进展情况，平时抽查12次/人20%1-2, 3-1, 5-2答辩 检查任务完成情况课题功能完善程度与合理性10%1-2, 3-1, 5-2陈述与回答问题陈述思路、表达能力与回答正确性20%1-2, 3-1课程 设计 报告论证与分析方案论证与综合分析的正确、合理性10%1-2, 3-1设计与实现设计与编码的正确、合理性：实验运行 的合理性与数据的可靠性10%3-1, 5-2报告书质量条理清晰、