#《数据结构》课程设计指导书1

《#《数据结构》课程设计指导书1》由会员分享，可在线阅读，更多相关《#《数据结构》课程设计指导书1（29页珍藏版）》请在金锄头文库上搜索。

1、数据结构课程设计指导书 （共 13 题）、课程设计的目的课程设计的目的是培养学生综合程序设计的能力， 训练学生灵活使用所学数 据结构知识， 独立完成问题分析、 总体设计、详细设计和编程实现等软件开发全 过程的综合实践能力。巩固、深化学生的理论知识，提高编程水平，并在此过程 中培养他们严谨的科学态度和良好的学习作风。 为今后学习其他计算机课程打下 基础。课程设计为学生提供了一个既动手又动脑， 独立实践的机会， 将书本上的理 论知识和工作、 生产实际有机地结合起来， 从而锻炼学生分析问题、 解决实际问 题的能力，提高学生的编程序能力和创新意识。二、课程设计的要求在处理每个题目时， 要求从分析题目的

2、需求入手， 按设计抽象数据类型、 构 思算法、通过算法的设计实现抽象数据类型、 编制上机程序和上机调试等若干步 骤完成题目， 最终写出完整的课程设计和程序分析报告。 前期准备工作完备和否 直接影响到后序上机调试工作的效率。三、课程设计的学生分组情况 每组三至五人，共同研究、共同讨论，可以共同编写算法，但必须各自独立 完成各自的程序。四、课程设计的时间安排课程设计前两周：将各项任务及问题进行讲解、分析。课程设计一周： 星期一：学生对任务进行讨论、研究和分析，初步设计出算法。 星期二到星期四：设计出详细算法，并上机调试程序。 星期五到星期六：写出课程设计报告并考核。五、课程设计的主要内容【课程设计

3、题目一】一元稀疏多项式加法、乘法器【问题描述】 设计一个一元稀疏多项式加法、乘法器用于计算两个多项式的加法和乘法。例如(x2+4x5+2x9) +(x+3x4)或(7x4+4x6+2x9) *(x 4+3x9)【基本要求】( 1) 输入并建立两个多项式 f(x) 和 g(x) ；( 2 ) 输出每个多项式，要求输出时按指数从小到大输出。( 3) 两个多项式完成加法、乘法运算。( 4) 输出两个多项式的加法之和及乘积的结果。( 5 ) 写出课程设计报告【实现提示】 用带表头结点的单链表存储多项式。【测试数据】 分别选定三组测试数据进行测试，验证程序的正确性。【课程设计题目二】局域网的架设问题【问

4、题描述】若要在8个城市(A、B、C、D E、F、G H之间架设局域网，如何以最低 的经济代价架设这个局域网。【基本要求】( 1 ) 利用三种方法( Prim 算法、克鲁斯卡尔( Kruskual 和矩阵运算)算 法生成局域网的架设方案( 2) 写出课程设计报告。【测试数据】 分别对每种方法选定一组测试数据进行测试，验证程序的正确性。【课程设计题目三】 二叉树的创建、二叉树的遍历【问题描述】 创建一棵二叉树，并对二叉树进行中序、前序、后序和层次遍历，分别写出它们的递归、非递归遍历算法【基本要求】 创建多种（五种以上）不同形态的二叉树，验证上述算法。【课程设计题目四】 校园导游咨询系统【问题描述】

5、设计一个你所在学校的校园导游程序，为来访的客人提供各种信息查询服 务。【基本要求】（1）设计你所在学校的校园平面图，所含景点不少于10 个。以图中顶点表示校内各景点，存放景点名称，代号，简介等信息；以边表示路径，存放路径 长度等相关信息。（2）为来访客人提供图中任意景点相关信息的查询。（3）为来访客人提供图中任意景点的问路查询， 即查出任意两个景点之间 的一条最短的简单路径。（4）写出课程设计报告【测试数据】 选定一组测试数据进行测试，验证程序的正确性。【课程设计题目五】通信网络的架设问题【问题描述】若要在n （10）个城市之间建设通信网络，只需要架设 n-1条线路即可， 如何以最低的经济代价

6、建设这个通信网，是一个网的最小生成树问题。【基本要求】（ 1 ）利用三种方法（ Prim 算法、克鲁斯卡尔（ Kruskual 和矩阵运算）生成 网中的最小生成树（ 2）写出课程设计报告。【测试数据】 分别对每种方法选定三组测试数据进行测试，验证程序的正确性。【课程设计题目六】内部排序的比较【问题描述】 比较内部排序冒泡排序、 插入排序、二分插入排序、 选择排序的运行时 间。给出算法执行的时间阶或每个程序的运行时间，精确到秒。【基本要求】（1）比较下列几种内部排序：冒泡排序、插入排序、二分插入排序、选择 排序的运行时间。 要求随机生成 20000 个测试数据进行测试， 并输出每个程序的 运行时

7、间，精确到秒。（2）写出课程设计报告【测试数据】 选定一批测试数据进行测试，验证程序的正确性并对计算时间进行比较。【课程设计题目七】 算法表达式的求值演算【问题描述】 以字符序列的形式从终端输入语法正确的、 不含变量的整数表达式。 利用教 科书给出的算符优先关系，加上乘方（A）和求除（%运算符，实现对算术混合运 算表达式的求值。【基本要求】（ 1）用顺序栈实现（ 2）含有乘方 （A） 、加（+） 、减（-） 、乘（*） 、除（/） 、求除（ %）等运算；并 含有括号。（3）分别以五组不同的表达式作为测试实例，每个实例中含有上述所有运 算符，测试其结果的正确性。（ 4）写出课程设计报告【测试数据

8、】 选定五组测试数据进行测试，验证程序的正确性。【课程设计题目八】 设计一个矩阵运算器【问题描述】设计一个矩阵运算器，对矩阵进行乘方(八)、加(+)、减(-)、乘(*)运算；【基本要求】(1) 参见数据结构题集P136页4.1(2) 求含有乘方(A)、加(+)、减(-)、乘(*)运算；。( 3) 写出课程设计报告【测试数据】分别选定一组测试数据进行测试，验证程序的正确性。【课程设计题目九】自来水管理架设问题【问题描述】若要在扬州大学的八个居民区(A区、B区、C区、D区、E区、F区、G区、 H区)之间架设自来水管道，如何以最低的经济代价架设这个自来水管道。【基本要求】( 1 )利用三种方法( P

9、rim 算法、克鲁斯卡尔 Kruskual 和矩阵运算)算法生成自来水管道的架设方案( 2)写出课程设计报告。【测试数据】分别对每种方法选定三组测试数据进行测试，验证程序的正确性。【课程设计题目十】校园网架设的方案设计问题【问题描述】若要在扬州大学的八个校区(江阳路南校区、江阳路北校区、盐阜校区、瘦 西湖校区、农学院校区、工学院校区、水利学院校区、医学院校区)之间架设校 园网，如何以最低的经济代价架设这个校园网。【基本要求】( 1 )利用三种方法( Prim 算法、克鲁斯卡尔( Kruskual )和矩阵运算)算 法生成校园网的架设方案( 2)写出课程设计报告。【测试数据】分别对每种方法选定一

10、组测试数据进行测试，验证程序的正确性。 【课程设计题目十一】学生成绩管理系统【问题描述】现有学生成绩信息文件 1（1.txt ），内容如下姓名学号语文数学英语张明明01677882李成友02789188张辉灿03688256王露04564577陈东明05673847学生成绩信息文件2（ 2.txt ）, 内容如下:姓名学号语文数学英语陈果31576882李华明32889068张明东33484256李明国34504587陈道亮35475877【基本要求】试编写一管理系统 , 要求如下 :1）实现对两个文件数据进行合并 , 生成新文件 3.txt2）抽取出三科成绩中有补考的学生并保存在一个新文件

11、4.txt3）对合并后的文件 3.txt 中的数据按总分降序排序 （ 至少采用两种排序方 法实现）4）输入一个学生姓名后 , 能查找到此学生的信息并输出结果 （ 至少采用两种 查找方法实现 ）5）要求使用结构体和链表实现上述要求【课程设计题目十二】学生成绩管理系统【问题描述】现有学生成绩信息文件 1（1.txt ），内容如下姓名学号语文数学英语张明明01677882李成友02789188张辉灿03688256王露04564577陈东明05673847学生成绩信息文件2（ 2.txt ）, 内容如下:姓名学号语文数学英语陈果31576882李华明32889068张明东33484256李明国345

12、04587陈道亮 35475877【基本要求】试编写一管理系统 , 要求如下 :1) 实现对两个文件数据进行合并 , 生成新文件 3.txt2) 抽取出三科成绩中有补考的学生并保存在一个新文件 4.txt3) 对合并后的文件 3.txt 中的数据按总分降序排序 ( 至少采用两种排序方 法实现)4) 输入一个学生姓名后 , 能查找到此学生的信息并输出结果 ( 至少采用两种 查找方法实现 )5) 要求使用结构体和数组实现上述要求 .【课程设计题目十三】算法表达式的求值演算【问题描述】以字符序列的形式从终端输入语法正确的、 不含变量的整数表达式。 利用教 科书给出的算符优先关系，加上乘方(八)和求除

13、(%等运算符，实现对算术混合 运算表达式的求值。【基本要求】(1) 用链栈实现(2) 含有乘方(八)、加(+)、减(-)、乘(*)、除(/)、求除(%等运算；并 含有括号。(3) 分别以五组不同的表达式作为测试实例，每个实例中含有上述所有运算符，测试其结果的正确性。(4) 写出课程设计报告【测试数据】 选定五组测试数据进行测试，验证程序的正确性。六、课程设计报告的主要内容课程设计报告主要包括以下几方面的内容:（1）课程设计的题目（2）课程设计的目的（3）分析系统的主要功能及用途（4）分析和描述系统的基本要求（5）问题实现的主要算法和分析（6）源程序（7）使用方法和说明（8）课程设计的小结（9）

14、参考文献七、课程设计的考核结合学生的动手能力，独立分析解决问题的能力和创新精神， 总结报告和答 辩水平以及学习态度综合考评。考核成绩分优、良、中、及格和不及格五等。考核主要包含以下几方面内容：1）运行所设计的系统2）回答相关题目的问题3）提交课程设计报告4）提交软盘（含源程序、执行程序和课程设计报告）5）内容要有创新。八、附录（课程设计报告示例）数据结构 课程设 计报告 课题名称最小牛成树问题 姓名XXX学院广陵学院系科班级计科81101指导老师陈宏建日 期 201目录年1月12日一、问题描述最小生成树问题一、二问题描述计1、2、要在n个城市之间建设通信网络，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信网络，是一个网的最小生成树问题。利用克抽象数据类型的义小生成树。假设连通网“=(V,E成；则令最小生成1516181920树的的初始状态为只有n个结点而无边的非连通图T= (V