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

《数据结构》课程设计指导书（共11题）

一、程设计的目的。

课程设计的目的是培养学生综合程序设计的能力，训练学生灵活应用所学数据结构知识，独立完成问题分析、总体设计、详细设计和编程实现等软件开发全过程的综合实践能力。巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的学习作风。为今后学习其他计算机课程打下基础。

课程设计为学生提供了一个既动手又动脑，独立实践的机会，将书本上的理论知识和工作、生产实际有机地结合起来，从而锻炼学生分析问题、解决实际问题的能力，提高学生的编程序能力和创新意识。

二、设计的要求。

在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过算法的设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的课程设计与程序分析报告。前期准备工作完备与否直接影响到后序上机调试工作的效率。

三、课程设计的学生分组情况。

每组三至五人，共同研究、共同讨论，可以共同编写算法，但必须各自独立完成各自的程序。

四、课程设计的时间安排。

课程设计前两周：将各项任务及问题进行讲解、分析。

课程设计一周：

星期一：学生对任务进行讨论、研究与分析，初步设计出算法。

星期二到星期四：设计出详细算法，并上机调试程序。

星期五到星期六：写出课程设计报告并考核。

五、课程设计的主要内容。

课程设计题目一】

一元稀疏多项式加法、乘法器。

问题描述】设计一个一元稀疏多项式加法、乘法器用于计算两个多项式的加法和乘法。例如。

x2+4x5+2x9）+(x+3x4)或（7x4+4x6+2x9）*(x4+3x9)

基本要求】1）输入并建立两个多项式f(x)和g(x)；

2）输出每个多项式，要求输出时按指数从小到大输出。

3）两个多项式完成加法、乘法运算。

4）输出两个多项式的加法之和及乘积的结果。

5）写出课程设计报告。

实现提示】用带表头结点的单链表存储多项式。

测试数据】分别选定三组测试数据进行测试，验证程序的正确性。

课程设计题目二】

局域网的架设问题。

问题描述】若要在5个城市（a、b、c、d、e）之间架设局域网，如何以最低的经济代价架设这个局域网。

基本要求】1）利用二种方法（prim算法和克鲁斯卡尔（kruskual）算法生成局域网的架设方案。

2）写出课程设计报告。

测试数据】分别对每种方法选定一组测试数据进行测试，验证程序的正确性。

课程设计题目三】

校园网架设的方案设计问题。

问题描述】若要在扬州大学的七个校区（广陵校区、盐阜校区、瘦西湖校区、农学院校区、工学院校区、水利学院校区、医学院校区）之间架设校园网，如何以最低的经济代价架设这个校园网。

基本要求】1）利用二种方法（prim算法和克鲁斯卡尔（kruskual）算法生成校园网的架设方案。

2）写出课程设计报告。

测试数据】分别对每种方法选定一组测试数据进行测试，验证程序的正确性。

课程设计题目四】

校园导游咨询系统。

问题描述】设计一个你所在学校的校园导游程序，为来访的客人提供各种信息查询服务。

基本要求】1）设计你所在学校的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称，代号，简介等信息；以边表示路径，存放路径长度等相关信息。

2）为来访客人提供图中任意景点相关信息的查询。

3）为来访客人提供图中任意景点的问路查询，即查出任意两个景点之间的一条最短的简单路径。

4）写出课程设计报告。

测试数据】选定一组测试数据进行测试，验证程序的正确性。

课程设计题目五】

通信网络的架设问题。

问题描述】若要在n个城市之间建设通信网络，只需要架设n-1条线路即可，如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。

基本要求】1）利用二种方法（prim算法和克鲁斯卡尔（kruskual）生成网中的最小生成树。

2）写出课程设计报告。

测试数据】分别对每种方法选定三组测试数据进行测试，验证程序的正确性。

课程设计题目六】

内部排序的比较。

问题描述】比较内部排序——冒泡排序、插入排序、二分插入排序、选择排序的运行时间。给出算法执行的时间阶或每个程序的运行时间，精确到秒。

基本要求】1）比较下列几种内部排序：冒泡排序、插入排序、二分插入排序、选择排序的运行时间。要求随机生成1000个测试数据进行测试，并输出每个程序的运行时间，精确到秒。

2）写出课程设计报告。

测试数据】选定一批测试数据进行测试，验证程序的正确性并对计算时间进行比较。

课程设计题目七】

算法表达式的求值演算。

问题描述】以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。利用教科书给出的算符优先关系，加上乘方(^)和求除（%）运算符，实现对算术混合运算表达式的求值。

基本要求】1）加乘方(^)加(+)减(-)乘(*)除(/)求除（%）运算；并含有括号。

2）分别以五组不同的表达式作为测试实例，每个实例中含有上述所有运算符，测试其结果的正确性。

3）写出课程设计报告。

测试数据】选定五组测试数据进行测试，验证程序的正确性。

课程设计题目八】

设计一个矩阵运算器。

问题描述】设计一个矩阵运算器，对矩阵进行乘方(^)加(+)减(-)乘(*)运算；

基本要求】1）参见数据结构题集p136页4.1

2）求含有乘方(^)加(+)减(-)乘(*)运算；。

3）写出课程设计报告。

测试数据】分别选定一组测试数据进行测试，验证程序的正确性。

课程设计题目九】

最小生成树和最短路径问题。

问题描述】1）最小生成树问题描述参见数据结构题集p152页5.6。

2）最短路径问题描述：若有n个城市，要求计算出任意城市之间的最短路径。

3）写出课程设计报告。

基本要求】利用kruskal算法生成网中最小生成树；

采用求最短路径的算法求任意城市之间的最短路径，并输出最短路径城市之间的路径结点。

测试数据】分别对每种方法选定二组测试数据进行测试，验证程序的正确性。

课程设计题目十】

自来水管理架设问题。

问题描述】若要在扬州大学的八个居民区（a区、b区、c区、d区、e区、f区、g区、h区）之间架设自来水管道，如何以最低的经济代价架设这个自来水管道。

基本要求】1）利用二种方法（prim算法和克鲁斯卡尔（kruskual）算法生成自来水管道的架设方案。

2）写出课程设计报告。

测试数据】分别对每种方法选定三组测试数据进行测试，验证程序的正确性。

六、课程设计报告的主要内容。

课程设计报告主要包括以下几方面的内容：

1）课程设计的题目。

2）课程设计的目的。

3）分析系统的主要功能及用途。

4）分析和描述的基本要求。

5）问题实现的主要算法与分析。

6）源程序。

7）使用方法与说明。

8）课程设计的小结。

9）参考文献。

七、课程设计报告的主要内容。

结合学生的动手能力，独立分析解决问题的能力和创新精神，总结报告和答辩水平以及学习态度综合考评。考核成绩分优、良、中、及格和不及格五等。

考核主要包含以下几方面内容：

1）运行所设计的系统。

2）回答相关题目的问题。

3）提交课程设计报告。

4）提交软盘（含源程序、执行程序和课程设计报告）

5）内容要有创新。

八、附录(课程设计报告示例)

课程设计报告。

课题名称最小生成树问题

姓名。学院信息工程学院

系科班级信息08 01

指导老师陈宏建

日期 2024年3月7日

最小生成树问题。

一、问题描述。

1、要在n个城市之间建设通信网络，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信网络，是一个网的最小生成树问题。

2、利用克鲁斯卡尔算法求网的最小生成树。假设连通网n=（v，），则令最小生成树的的初始状态为只有n个结点而无边的非连通图t=（v，{}图中每一个顶点自成一个连通分量。在e中选择代价最小的边，若该边依附的顶点落在t中不同的连通分量上，则将此边加入到t中，否则舍去此边选择下一条代价最小的边。

依次类推，直至t中所有顶点都在同一连通分量上为止。

3、使用mfset类表示构造生成树过程中的连通分量。

4、测试数据（附后）。

二、概要设计。

1、抽象数据类型定义如下：

adt graph

vr=基本操作p：

creatgraph(&g);

操作结果：初始化一个图。

initial(&s,n,x1,x2,…,xn);

操作结果：初始化操作。构造一个由n个子集（每个子集只含单个成员xi）构成的集合s。

find(s,v);

初始条件：s是已经存在的集合，v是某个子集成员。

操作结果：查找函数。返回s中v所属子集si。

merge(&s,i,j);

初始条件：si和sj是s中两个互不相交的非空集合。

操作结果：归并操作。将si和sj中的一个并入另一个。

kruskal(void);

初始条件：图g存在。

操作结果：求图g的最小生成数。

output(void);

初始条件：已经生成图g的最小树。

操作结果：输出操作。将最小生成树以文本形式输出到文件中。

adt graph

2、本程序包含5个模块。

1）主程序模块，其中主函数为。

main()

2）汉字显示模块——实现dos模式下的汉字显示；

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

数据结构课程设计指导书

数据结构课程设计指导书

数据结构课程设计指导书

其他用户还读了