《数据结构课程设计》教学大纲
课程名称： 课程编号： 适用专业： 总 学 分： 总 学 时： 其中实验学时 主 撰 人： 撰写日期：
一、目的与任务
《数据结构》是计算机软件的一门基础课程，计算机科学各领域及有关的应用软件都要用到各种类型的数据结构。学好数据结构对掌握实际编程能力是很有帮助的。为了学好《数据结构》，必须编写一些在特定数据结构上的算法，通过上机调试，才能更好地掌握各种数据结构及其特点，同时提高解决计算机应用实际问题的能力。
二、教学基本要求
1．设计和调试过程要规范化
需求分析：将题目中要求的功能进行叙述分析，并且设计解决此问题的数据存储结构，（有些题目已经指定了数据存储的，按照指定的设计），设计或叙述解决此问题的算法，描述算法建议使用流程图，进行算法分析指明关键语句的时间复杂度。
给出实现功能的一组或多组测试数据，程序调试后，将按照此测试数据进行测试的结果列出来 。
对有些题目提出算法改进方案，比较不同算法的优缺点。
如果程序不能正常运行，写出实现此算法中遇到的问题，和改进方法。②源程序（可以是一组源程序，即详细设计部分）
源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。
程序能够运行，要有基本的容错功能。尽量避免出现操作错误时出现死循环。 2．课程设计实习报告的书写格式
① 设计题目
数据结构 408104 计算机科学与技术
4 72 30 2012．6
436104 软件工程
审 核 人：
②运行环境（软、硬件环境） ③算法设计的思想 ④算法的流程图 ⑤算法设计分析 ⑥源代码 ⑦运行结果分析 ⑧收获及体会 3．实施方式
可设3-4人一题，安排在《数据结构》课程开课学期布置题目，然后在期末两周时间内完成。
4．答辩：课题的论述、测试及问题回答
三、课程设计内容
1、背包问题的求解：
假设有一个能装入总体积为T的背包和n件体积分别为w1 , w2 , … , wn 的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1 +w2 + … + wn=T，要求找出所有满足上述条件的解。例如：当T=10，各件物品的体积{1，8，4，3，5，2}时，可找到下列4组解：（1，4，3，2）， （1，4，5）， （8，2）， （3，5，2）。
提示：可利用回溯法的设计思想来解决背包问题。首先将物品排成一列，然后顺序选取物品装入背包，假设已选取了前i 件物品之后背包还没有装满，则继续选取第i+1件物品，若该件物品\"太大\"不能装入，则弃之而继续选取下一件，直至背包装满为止。但如果在剩余的物品中找不到合适的物品以填满背包，则说明\"刚刚\"装入背包的那件物品\"不合适\"，应将它取出\"弃之一边\"，继续再从\"它之后\"的物品中选取，如此重复，直至求得满足条件的解，或者无解。
由于回溯求解的规则规则是\"后进先出\"因此自然要用到栈。
2、订票系统 （1）问题描述
通过此系统可以实现如下功能： 1）录入：
可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定） 2）查询： 可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；
可以输入起飞抵达城市，查询飞机航班情况；
3）订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；
4）退票： 可退票，退票后修改相关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。
5）修改航班信息：当航班信息改变可以修改航班数据文件 （2）要求
根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；
3、迷宫求解 （1）问题描述
可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出； （2）要求
在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；
4、dijkstra算法求最短路径
问题描述：从键盘上输入一个图的基本信息（图用邻矩阵表示）
1)首先输入图的结点数->num 2)依次输入图的各条边
3）程序所能达到的功能：输出用dijkstra算法求出的一条最短路径。
5、joseph环 （1）问题描述
编号是1，2，„„,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。 （2）要求 利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。 （3）测试数据：
m的初值为20，n=7 ,7个人的密码依次为3，1，7，2，4，7，4，首先m=6,则正确的输出是什么？
（4）输入数据：建立输入处理输入数据，输入m的初值，n ，输入每个人的密码，建立单循环链表。
（5）输出形式：建立一个输出函数，将正确的输出序列
6、建立二叉树，层序、先序遍历（ 用递归或非递归的方法都可以） （1）问题描述：建立二叉树，并实行层序、先序遍历等算法
（2）要求：能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数；
7、赫夫曼树的建立
（1）问题描述：建立建立最优二叉树函数
（2）要求：可以建立函数输入二叉树，并输出其赫夫曼树
在上交资料中请写明：存储结构、基本算法（可以使用程序流程图）、输入输出、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法；
8、图的建立及输出
（1）问题描述：建立图的存储结构（图的类型可以是有向图、无向图、有向网、无向网，学生可以任选两种类型）
（2）要求：能够输入图的顶点和边的信息，并存储到相应存储结构中，而后输出图的邻接矩阵。
9、拓扑排序
（1）问题描述：编写函数实现图的拓扑排序。 （2）要求：能够以一定的方式输入数据结点
10、各种排序
（1）问题描述：对30000个随机整数，利用插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序等排序方法进行排序，并统计每一种排序上机所花费的时间。 （2）要求：输入的数据形式为任何一个正整数，大小不限。
输出的形式：数字大小逐个递增的数列
11、图的遍历 对任意给定的图（顶点数和边数自定），建立它的邻接表并输出，然后利用队列的五种基本运算（置空队列、进队、出队、取队头元素、判队空）实现图的广度优先搜索周游。
12、线性表的操作
利用链表的插入运算建立线性链表，然后利用链表的查找、删除、计数、输出等运算反复实现链表的这些操作（插入、删除、查找、计数、输出单独写成函数的形式），并能在屏幕上输出操作前后的结果。
13、长整数四则运算
*问题描述：设计一个实现任意长的整数进行加法运算的演示程序。*基本要求：利用双向循环链表实现长整数的存储，每个结点含一个整形变量。任何整形变量的范围是 -(2^151)。输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。 *测试数据：
（1）0；0；应输出“0”。
（2）-2345,6789；-7654,3211；应输出“-1,0000,0000”。 （3）-9999,9999；1,0000,0000,0000；应输出“999 （4）1,0001,0001；-1,0001,0001；应输出“0”。 （5）1,0001,0001；-1,0001,0000；应输出“1”。
（6）-9999,9999,9999；-9999,9999,9999；应输出“1,9999,9999,9998”。 （7）1,0000,9999,9999；1；应输出“1,0001,0000,0000”。 *实现提示：
（1）每个结点中可以存放的最大整数为32767，才能保证两数相加不会溢出，但若这样存放，即相当于按32768进制存放，在十进制与32768进制数之间的转换十分不方便，故可以在每个结点中仅存十进制的4位，即不超过9999的非负整数，整个链表表示为万进制。
（2）可以利用头结点数据域的符号代表长整数的符号。用其绝对值表示元素结
点数目。相加过程中不要破坏两个操作数链表。两操作数的头指针存于指针数组中是简化程序结构的一种方法。不能给长整数位数规定上限。
14、克鲁斯尔算法求最小生成树
问题描述：从键盘上输入一个图的基本信息（图用邻矩阵表示）
1)首先输入图的结点数->num 2)依次输入图的各条边
3)程序所能达到的功能：能够输出这个图的一棵最小生成树
15、算术表达式求值演示
（1）问题描述：表达式求值是实现程序设计语言的基本问题之一，也是栈的应用的一个典型例子。设计一个程序，演示用算符优先法对算术表达式求值的过程。 （2）基本要求：以字符序列的形式从终端上输入语法正确的、不含变量的整数表达式。利用教材中给出的算符优先关系，实现对算术四则混合运算表达式的求值，并仿照教材例3-1演示在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程。
16．稀疏矩阵运算器
*问题描述：稀疏矩阵是指那些多数元素为0的矩阵。利用“稀疏”特点进行存储和计算可以大大节省存储空间，提高计算效率。实现一个能进行稀疏矩阵基本原酸的运算器。
*基本要求：以“带行逻辑链接信息”的三元组顺序表示稀疏矩阵，实现两个矩阵相加、相减和相乘的运算。稀疏矩阵的输入形式采用三元组表示，而运算结构的矩阵则以通常的阵列形式列出。
*实现提示：（1）首先应输入矩阵的行数和列数，并判别给出的两个矩阵的行、列数对于所要求作的运算是否匹配。可设矩阵的行数和列数均不超过20。（2）程序可以对三元组的输入顺序加以限制，例如，按行优先。注意研究教科书中的算法，以便提高计算效率。（3）在用三元组表示稀疏矩阵时，相加或相减所得结果矩阵应该另生成，乘积矩阵也可以用二维数组存放。
四、时间安排
《数据结构课程设计》安排在第三学期进行，时间2周（17-18周）。
五、组织管理
1．由院、系指派经验丰富的专业教师担任指导教师。
2．课程设计实行指导教师负责制，由指导教师全面负责课程设计的指导与管理工作。
六、成绩考核与评定
学生课程设计结束后写出总结报告，对设计的内容和效果进行总结，按照学生在设计期间的表现，指导老师对每位学生写出评语和鉴定，系课程设计领导小组组织答辩，最后确定每位学生课程设计成绩，课程设计成绩分为优、良、中、及格和不及格五个等级。
课程设计成绩为平时表现30%、设计报告50%、答辩20%。 评分标准：
① 优秀：目的明确，态度端正，模范遵守学校的各项纪律。工作认真，积极 主动，吃苦耐劳，能出色的完成设计任务。撰写了高质量的总结报告。答辩准确流利。
② 良好：目的明确，态度端正，能遵守学校的各项纪律，工作比较积极主动。 能较好地完成设计任务，成绩较突出，表现良好；撰写了质量比较高的实习报告。答辩较准确流利。
③ 及格：目的明确，态度基本端正，能遵守学校纪律，在督促下能开展工作 并完成一定的设计任务，无大的违纪违规现象；撰写了实习报告。通过了答辩。
④ 不及格：实习态度端正，不能遵守实习单位的纪律，不服从领导，自由散漫，工作消极被动，不能完成实习任务，实习期间有失职、旷工、打架、酗酒等大的过失。或无实习报告，没有通过答辩。
2．成绩评定
依据上述考核内容，最后采用优（>90分）、良（80～89分）、中（70～79分）及格（60～69分）、不及格（
七、主要参考资料
《数据结构 C语言》 严蔚敏 清华大学出版社 2006.2 《c语言程序设计》 谭浩强 清华大学出版社 2010.8 《数据结构习题》 李春保 清华大学出版社 2006.4 《数据结构习题》 严蔚敏 清华大学出版社 2006.2 《c语言与数据结构》 王立柱 清华大学出版社 2010.6 《数据结构（C语言篇）习题与解析》李春葆 清华大学出版社2006.4
