《数据结构》课程设计教学大纲
适用专业：计算机科学与技术 课程周数：2周
一、大纲说明
本大纲根据计算机科学与技术专业人才培养方案制订。
（一）课程设计性质
课程设计是学生对课程所学知识的综合运用，它与课堂听讲、上机实验、课外练习、自学研究相辅相成，构成一个完整的课程教学体系。
（二）主要先修课程和后续课程 1.先修课程：《C语言程序设计》 2.后续课程：《计算机组成原理》、《操作系统》、《数据库系统原理》
二、课程设计目的及基本要求
《数据结构》是一门实践性强的课程，其中对算法设计和程序编写的掌握尤为重要。学生虽然可以通过与课堂教学同步的上机实验完成相关内容的练习，但却往往局限于一些功能简单、彼此之间关系独立的算法和程序。课程设计是一种综合训练，致力于培养学生全面、灵活的算法设计思想和较高的编程能力，为今后从事计算机开发与应用打下基础。新世纪需要具有丰富科学知识、独立解决实际问题、有创造能力的新型人才，这也是该课程设计的最终目的。
三、课程设计内容及安排
1、矩阵的转置、加减和相乘
问题描述：采用十字链表存储的稀疏矩阵，完成矩阵转置、加减和相乘功能。 要求：
1）采用函数形式完成转置、相加、相减和相乘； 2）有输入数据合法性检查； 3）矩阵的存储采用动态数组；
4）两个矩阵产生后要分别打印出来，完成相应处理后结果要打印出来； 5）每一个函数要有必要的注释，在课程设计论文中有流程图。
2、线索二叉树
问题描述：实现线索二叉树的生成、遍历、查找、插入和删除操作。 要求：
1）各功能模块必须是单独的函数； 2）线索二叉树是动态生存的； 3）输入数据进行必要的合法性检查；
4）执行每一个功能后，按二叉树广义表的表达方式打印输出，检查结果是否正确； 5）每一个函数要有必要的注释，在课程设计论文中有流程图。
3、根据哈夫曼树的原理求n个自然数相加减后结果最小（中间结果、最后结果不能负）。
问题描述：实现线索二叉树的生成、遍历、查找、插入和删除操作。 要求：
1）可以循环测试，可以选择退出程序；
2）打印这n个自然数进行加减的表达式（注意：中间结果不能为负）； 例如：输入1,2,3，最后打印出3-2-1=0 3）输入数据要进行合法性检查；
4）每一个函数要有必要的注释，在课程设计论文中有流程图。
4、普里姆算法求最小生成树
问题描述：用普里姆算法求有向网图或无向网图的最小生成树。 要求：
1）先生成一个网图，该网图既能是无向网图，有能是有向网图； 2）要求分别采用邻接矩阵和链接表存储来完成； 3）最后打印输出最小生成树；
4）每一个函数要有必要的注释，在课程设计论文中有流程图。
5、克鲁斯卡尔算法求最小生成树
问题描述：用克鲁斯卡尔算法求有向网图或无向网图的最小生成树。 要求：
1）先生成一个网图，该网图既能是无向网图，有能是有向网图； 2）要求分别采用邻接矩阵和链接表存储来完成； 3）最后打印输出最小生成树；
4）每一个函数要有必要的注释，在课程设计论文中有流程图。
6、狄杰斯特算法求最短路径
问题描述：采用狄杰斯特算法求一个顶点到其它顶点的最短路径。 要求：
1）先生成一个带权的有向图，并打印输出； 2）用函数形式完成狄杰斯特算法；
3）打印输出最后的该顶点到其它顶点的路径，并打印最短路径。 4）每一个函数要有必要的注释，在课程设计论文中有流程图。
7、佛洛依德算法求最短路径
问题描述：采用佛洛依德算法求每对顶点到其它顶点的最短路径。 要求：
1）先生成一个带权的有向图，并打印输出； 2）用函数形式完成佛洛依德算法； 3）打印输出每对顶点的最短路径。
4）每一个函数要有必要的注释，在课程设计论文中有流程图。
8、分块查找
问题描述：采用分块查找的方法查找指定的关键码。 要求：
1）可以循环查找，可以选择退出；
2）分别采用顺序存储和链式存储完成分块查找，其中在顺序存储结果下，索引表的查找采用二分查找；
3）分别用函数完成索引表查找和块中查找；
4）每一个函数要有必要的注释，在课程设计论文中有流程图。
9、关键路径
问题描述：建立AOE图，确定其拓扑有序后求关键路径。 要求：
1）建立一个AOE图，并输出结果确保创建成功；
2）判断AOE图是一个拓扑有序序列，如果不是拓扑有序则报错； 3）编写函数求AOE图的关键路径； 4）打印输出关键路径；
5）每一个函数要有必要的注释，在课程设计论文中有流程图。
10、二叉排序树
问题描述：完成二叉排序树的创建、查找、插入和删除操作。 要求：
1）创建一颗二叉排序树，并打印输出；
2）分别编写函数完成二叉排序树的查找、插入和删除； 3）测试二叉排序树的查找、插入和删除，分别打印测试结果； 4）每一个函数要有必要的注释，在课程设计论文中有流程图。
11、B-树
问题描述：完成B-树的创建、查找、插入和删除。 要求：
1）创建一颗B-树，并打印输出；
2）分别编写函数完成B-的查找、插入和删除；
3）测试B-树的查找、插入和删除，分别打印测试结果； 4）每一个函数要有必要的注释，在课程设计论文中有流程图。
12、哈希表查找
问题描述：定义一个哈希表和对哈希表进行插入、查找和删除、打印。 要求：
1）定义一个哈希表，并打印输出结果； 2）分别编写函数完成查找、插入和删除； 3）测试查找、插入和删除，分别打印测试结果；
4）每一个函数要有必要的注释，在课程设计论文中有流程图。
四、指导方式
集体辅导与个别辅导相结合。
五、课程设计考核方法及成绩评定
1、程序清单：代码应具有详细注释，用来说明程序的功能、结构；
2、设计报告：报告中应包含上机时遇到的问题及解决办法，观察到的现象及其分析，对程序设计技巧的总结及分析等；程序的输出结果及对结果的分析；实验的心得体会，以及其它信息；
3、提交时，须向指导教师说明：程序的使用方法，调用方法、操作步骤等；要求输入信息的类型及格式；出错信息的含义及程序的适用范围等。
成绩评定：课程设计成绩分两部分，设计报告占40％，设计作品占60％。
六、课程设计教材及主要参考资料 教学参考书
[1]李素若.《数据结构》.北京：化学工业出版社，2009.参考资料：
[1] 朱蓉，《数据结构实验指导书》
[2]严蔚敏 吴伟民，.数据结构(C语言版)，1999，清华大学出版社； [3]严蔚敏 吴伟民，.数据结构题集(C语言版)，1999，清华大学出版社； [4]徐孝凯，数据结构课程实验，2002，清华大学出版社；
[5]孟佳娜 胡潇琨，算法与数据结构实验与习题，2004，机械工业出版社；
七、其他 i=[1] t=[12] i=[2] t=[4] i=[3] t=[10] i=[4] t=[12] i=[5] t=[1] i=[6] t=[2] i=[7] t=[2] i=[8] t=[11] i=[9] t=[5] i=[10] t=[10] i=[11] t=[11] i=[12] t=[8] i=[13] t=[2] i=[14] t=[3] i=[15] t=[9] i=[16] t=[7] i=[17] t=[5] i=[18] t=[6] i=[19] t=[12] i=[20] t=[7] i=[21] t=[3] i=[22] t=[7] i=[23] t=[8] i=[24] t=[6] i=[25] t=[7] i=[26] t=[8] i=[27] t=[3] i=[28] t=[2] i=[29] t=[7] i=[30] t=[4] i=[31] t=[3] i=[32] t=[8] i=[33] t=[9] i=[34] t=[1] i=[35] t=[1] i=[36] t=[3] i=[37] t=[8] i=[38] t=[1] i=[39] t=[10] i=[40] t=[12] i=[41] t=[10] i=[42] t=[9] i=[43] t=[12] i=[44] t=[2] i=[45] t=[1] i=[46] t=[6] i=[47] t=[4] i=[48] t=[7] i=[49] t=[1]
