《数据结构课程设计》
教学大纲
哈尔滨师范大学
计算机学与信息工程学院
《数据结构课程设计》
一、课程设置的有关说明 1.课程性质
本课程属于集中实践教学环节，是在学习了C语言、面向对象程序设计（C++）和数据结构后开设的。数据结构是一门较为抽象的课程，在学习完该课程后，学生往往会觉得其实际应用难以理解。通过安排相应的实践，可以让学生认识到该课程的实用性和重要性。
2.课程定义
《数据结构课程设计》是计算机科学专业本科学生必修的实践课程，本课程设计旨在培养学生的将理论应用于实践的能力。总学分1学分，在第5学期4周集中进行，主要训练学生综合运用C语言、C++、面向对象程序设计、数据结构知识解决实际问题，使学生能熟练的设计算法并有效的实现。 3.设置课程的目的和教学基本要求 设置课程的目的：
通过对本课程的学习，培养学生进一步理解和掌握所学的各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序设计中的使用方法，使学生具备初步的独立分析和设计能力； 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 训练用系统的观点进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。
基本要求：
1）设计和调试过程要规范化。 ①需求分析
将题目中要求的功能进行叙述分析，并且设计解决此问题的数据存储结构，（有些题目已经指定了数据存储的，按照指定的设计），设计或叙述解决此问题的算法，描述算法建议使用流程图，进行算法分析指明关键语句的时间复杂度。给出实现功能的一组或多组测试数据，程序调试后，将按照此测试数据进行测试的结果列出来 。对有些题目提出算法改进方案，比较不同算法的优缺点。如果程序不能正常运行，写出实现此算法中遇到的问题，和改进方。
②源程序（可以是一组源程序，即详细设计部分）
源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。程序能够运行，要有基本的容错功能。尽量避免出现操作错误时出现死循环。
2）课程设计报告的书写格式 ①设计题目（任选其一） ②运行环境（软、硬件环境） ③算法设计的思想 ④算法的流程图 ⑤算法设计分析
⑥源代码 ⑦运行结果分析 ⑧收获及体会 3）实施方式
可设一人一题，安排在《数据结构》课程开课学期布置题目，然后在期末4周时间内完成。（或在下学期开学4周时间内完成）。 4）考核方式
课程设计结束时，要求学生写出课程设计报告（附源程序），可运行的软件系统 课程设计成绩分两部分，设计报告占30％，设计作品占70％。 按照优秀、良好、中、及格，不及格五级给予成绩。 4.教学内容简介
通过指导教师命题或学生自拟题目的方式，学生要发挥自主学习的能力，充分利用时间，安排好课设的时间计划，并在课设过程中不断检测自己的计划完成情况，及时的向教师汇报。最终按要求上交一份3000字左右数据结构课程设计报告（附源程序）。
二、设计参考题目
1、一元多项式计算 *问题描述：
能够按照指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输入；在上交资料中请写明：存储结构、多项式相加的基本过程的算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；
2、迷宫求解 *问题描述：
可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出； *要求：
在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；
3、joseph环 *问题描述：
编号是1，2，……,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。 *要求：
利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。 *测试数据：
m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？ *输入数据：
建立输入处理输入数据，输入m的初值，n ，输入每个人的密码，建立单循环链表。 *输出形式：建立一个输出函数，将正确的输出序列
4、建立二叉树，层序、先序遍历（ 用递归或非递归的方法都可以） *问题描述：
要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数；
5、赫夫曼树的建立 *问题描述：
建立建立最优二叉树函数 *要求：
可以建立函数输入二叉树，并输出其赫夫曼树。在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、输入输出、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；
6、图的建立及输出 *问题描述：
建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型），能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵
7、拓扑排序 *问题描述：
编写函数实现图的拓扑排序。
8、图的遍历 *问题描述：
对任意给定的图（顶点数和边数自定），建立它的邻接表并输出，然后利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）实现图的广度优先搜索周游。
三、时间进度
学生课程设计时间安排如下： 第1周初，布置题目 第2周末，中期检查
第3周末，个别指导难度突破 第4周末，验收
四、阅读参考书目：
《数据结构 C语言》 严蔚敏 清华大学出版社 2007年3月
《《数据结构》算法实现及解析》（第二版）高一凡 西安电子科技大学出版社 2004年10月
《c语言程序设计》 谭浩强 清华大学出版社
《数据结构习题与解析》 李春保 清华大学出版社 2004年2月 《数据结构习题》 严蔚敏 清华大学出版社 1999年2月 《c/c++与数据结构》 王立柱 清华大学出版社 2008年3月
《数据结构（C语言篇）习题与解析》李春葆 清华大学出版社 2005年4月
