《数据结构》课程设计指导书（共13题）一、课程设计的目的课程设计的目的是培养学生综合程序设计的能力，训练学生灵活应用所学数据结构知识，独立完成问题分析、总体设计、详细设计和编程实现等软件开发全过程的综合实践能力。
巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的学习作风。
为今后学习其他计算机课程打下基础。
课程设计为学生提供了一个既动手又动脑，独立实践的机会，将书本上的理论知识和工作、生产实际有机地结合起来，从而锻炼学生分析问题、解决实际问题的能力，提高学生的编程序能力和创新意识。
二、课程设计的要求在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过算法的设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的课程设计与程序分析报告。
前期准备工作完备与否直接影响到后序上机调试工作的效率。
三、课程设计的学生分组情况每组三至五人，共同研究、共同讨论，可以共同编写算法，但必须各自独立完成各自的程序。
四、课程设计的时间安排课程设计前两周：将各项任务及问题进行讲解、分析。
课程设计一周：星期一：学生对任务进行讨论、研究与分析，初步设计出算法。
星期二到星期四：设计出详细算法，并上机调试程序。
星期五到星期六：写出课程设计报告并考核。
五、课程设计的主要内容【课程设计题目一】一元稀疏多项式加法、乘法器【问题描述】设计一个一元稀疏多项式加法、乘法器用于计算两个多项式的加法和乘法。
例如（x2+4x5+2x9）+(x+3x4)或（7x4+4x6+2x9）*(x4+3x9)【基本要求】（1）输入并建立两个多项式f(x)和g(x)；（2）输出每个多项式，要求输出时按指数从小到大输出。
（3）两个多项式完成加法、乘法运算。
（4）输出两个多项式的加法之和及乘积的结果。
（5）写出课程设计报告【实现提示】用带表头结点的单链表存储多项式。
【测试数据】分别选定三组测试数据进行测试，验证程序的正确性。
【课程设计题目二】局域网的架设问题【问题描述】若要在8个城市（A、B、C、D、E、F、G、H）之间架设局域网，如何以最低的经济代价架设这个局域网。
【基本要求】（1）利用三种方法（Prim算法、克鲁斯卡尔（Kruskual和矩阵运算）算法生成局域网的架设方案（2）写出课程设计报告。
分别对每种方法选定一组测试数据进行测试，验证程序的正确性。
【课程设计题目三】二叉树的创建、二叉树的遍历【问题描述】创建一棵二叉树，并对二叉树进行中序、前序、后序和层次遍历，分别写出它们的递归、非递归遍历算法。
【基本要求】创建多种（五种以上）不同形态的二叉树，验证上述算法。
【课程设计题目四】校园导游咨询系统【问题描述】设计一个你所在学校的校园导游程序，为来访的客人提供各种信息查询服务。
【基本要求】（1）设计你所在学校的校园平面图，所含景点不少于10个。
以图中顶点表示校内各景点，存放景点名称，代号，简介等信息；以边表示路径，存放路径长度等相关信息。
（2）为来访客人提供图中任意景点相关信息的查询。
（3）为来访客人提供图中任意景点的问路查询，即查出任意两个景点之间的一条最短的简单路径。
（4）写出课程设计报告【测试数据】选定一组测试数据进行测试，验证程序的正确性。
【课程设计题目五】通信网络的架设问题若要在n（≥10）个城市之间建设通信网络，只需要架设n-1条线路即可，如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。
【基本要求】（1）利用三种方法（Prim算法、克鲁斯卡尔（Kruskual和矩阵运算）生成网中的最小生成树（2）写出课程设计报告。
【测试数据】分别对每种方法选定三组测试数据进行测试，验证程序的正确性。
【课程设计题目六】内部排序的比较【问题描述】比较内部排序——冒泡排序、插入排序、二分插入排序、选择排序的运行时间。
给出算法执行的时间阶或每个程序的运行时间，精确到秒。
【基本要求】（1）比较下列几种内部排序：冒泡排序、插入排序、二分插入排序、选择排序的运行时间。
要求随机生成20000个测试数据进行测试，并输出每个程序的运行时间，精确到秒。
（2）写出课程设计报告【测试数据】选定一批测试数据进行测试，验证程序的正确性并对计算时间进行比较。
【课程设计题目七】算法表达式的求值演算【问题描述】以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。
利用教科书给出的算符优先关系，加上乘方(^)和求除（%）运算符，实现对算术混合运算表达式的求值。
【基本要求】（1）用顺序栈实现（2）含有乘方(^)、加(+)、减(-)、乘(*)、除(/)、求除（%）等运算；并含有括号。
（3）分别以五组不同的表达式作为测试实例，每个实例中含有上述所有运算符，测试其结果的正确性。
（4）写出课程设计报告【测试数据】选定五组测试数据进行测试，验证程序的正确性。
【课程设计题目八】设计一个矩阵运算器【问题描述】设计一个矩阵运算器，对矩阵进行乘方(^)、加(+)、减(-)、乘(*)运算；【基本要求】（1）参见数据结构题集P136页4.1（2）求含有乘方(^)、加(+)、减(-)、乘(*)运算；。
（3）写出课程设计报告【测试数据】分别选定一组测试数据进行测试，验证程序的正确性。
【课程设计题目九】自来水管理架设问题【问题描述】若要在扬州大学的八个居民区（A区、B区、C区、D区、E区、F区、G区、H区）之间架设自来水管道，如何以最低的经济代价架设这个自来水管道。
【基本要求】（1）利用三种方法（Prim算法、克鲁斯卡尔Kruskual和矩阵运算）算法生成自来水管道的架设方案（2）写出课程设计报告。
【测试数据】分别对每种方法选定三组测试数据进行测试，验证程序的正确性。
【课程设计题目十】校园网架设的方案设计问题【问题描述】若要在扬州大学的八个校区（江阳路南校区、江阳路北校区、盐阜校区、瘦西湖校区、农学院校区、工学院校区、水利学院校区、医学院校区）之间架设校园网，如何以最低的经济代价架设这个校园网。
【基本要求】（1）利用三种方法（Prim算法、克鲁斯卡尔（Kruskual）和矩阵运算）算法生成校园网的架设方案（2）写出课程设计报告。
【测试数据】分别对每种方法选定一组测试数据进行测试，验证程序的正确性。
【课程设计题目十一】学生成绩管理系统【问题描述】现有学生成绩信息文件1（1.txt），内容如下姓名学号语文数学英语张明明 01 67 78 82李成友 02 78 91 88张辉灿 03 68 82 56王露 04 56 45 77陈东明 05 67 38 47…. .. .. .. …学生成绩信息文件2（2.txt）,内容如下:姓名学号语文数学英语陈果 31 57 68 82李华明 32 88 90 68张明东 33 48 42 56李明国 34 50 45 87陈道亮 35 47 58 77…. .. .. .. …【基本要求】试编写一管理系统,要求如下:1) 实现对两个文件数据进行合并,生成新文件3.txt2) 抽取出三科成绩中有补考的学生并保存在一个新文件4.txt3) 对合并后的文件3.txt中的数据按总分降序排序(至少采用两种排序方法实现)4) 输入一个学生姓名后,能查找到此学生的信息并输出结果(至少采用两种查找方法实现)5) 要求使用结构体和链表实现上述要求.【课程设计题目十二】学生成绩管理系统【问题描述】现有学生成绩信息文件1（1.txt），内容如下姓名学号语文数学英语张明明 01 67 78 82李成友 02 78 91 88张辉灿 03 68 82 56王露 04 56 45 77陈东明 05 67 38 47…. .. .. .. …学生成绩信息文件2（2.txt）,内容如下:姓名学号语文数学英语陈果 31 57 68 82李华明 32 88 90 68张明东 33 48 42 56李明国 34 50 45 87陈道亮 35 47 58 77…. .. .. .. …【基本要求】试编写一管理系统,要求如下:1) 实现对两个文件数据进行合并,生成新文件3.txt2) 抽取出三科成绩中有补考的学生并保存在一个新文件4.txt3) 对合并后的文件3.txt中的数据按总分降序排序(至少采用两种排序方法实现)4) 输入一个学生姓名后,能查找到此学生的信息并输出结果(至少采用两种查找方法实现)5) 要求使用结构体和数组实现上述要求.【课程设计题目十三】算法表达式的求值演算【问题描述】以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。
利用教科书给出的算符优先关系，加上乘方(^)和求除（%）等运算符，实现对算术混合运算表达式的求值。
【基本要求】(1)用链栈实现(2)含有乘方(^)、加(+)、减(-)、乘(*)、除(/)、求除（%）等运算；并含有括号。
(3)分别以五组不同的表达式作为测试实例，每个实例中含有上述所有运算符，测试其结果的正确性。
(4)写出课程设计报告【测试数据】选定五组测试数据进行测试，验证程序的正确性。
六、课程设计报告的主要内容课程设计报告主要包括以下几方面的内容：（1）课程设计的题目（2）课程设计的目的（3）分析系统的主要功能及用途（4）分析和描述系统的基本要求（5）问题实现的主要算法与分析（6）源程序（7）使用方法与说明（8）课程设计的小结（9）参考文献七、课程设计的考核结合学生的动手能力，独立分析解决问题的能力和创新精神，总结报告和答辩水平以及学习态度综合考评。
考核成绩分优、良、中、及格和不及格五等。
考核主要包含以下几方面内容：1）运行所设计的系统2）回答相关题目的问题3）提交课程设计报告4）提交软盘（含源程序、执行程序和课程设计报告）5）内容要有创新。
八、附录(课程设计报告示例)数据结构课程设计报告课题名称最小生成树问题姓名×××学院广陵学院系科班级计科81101 指导老师陈宏建日期2013年1月12日目录●一、问题描述 (2)●二、概要设计 (2)⏹1抽象数据类型定义 (2)⏹2程序包含模块 (2)⏹3函数调用关系 (3)●三、详细设计 (3)⏹1顶点、边、图和集合类型 (3)⏹2图的基本操作 (4)⏹3程序详细代码 (5)⏹4函数调用关系图 (15)●四、设计和调试分析 (15)●五、用户手册 (16)●六、测试结果 (18)●七、附件 (19)●八、心得体会 (20)最小生成树问题一、问题描述1、要在n个城市之间建设通信网络，只需要架设n-1条线路即可。
如何以最低的经济代价建设这个通信网络，是一个网的最小生成树问题。
2、利用克鲁斯卡尔算法求网的最小生成树。
假设连通网N=（V，{E}），则令最小生成树的的初始状态为只有n个结点而无边的非连通图T=（V，{}），图中每一个顶点自成一个连通分量。