1、数据结构课程设计指导书 （共13题）一、课程设计的目的课程设计的目的是培养学生综合程序设计的能力，训练学生灵活应用所学数据结构知识，独立完成问题分析、总体设计、详细设计和编程实现等软件开发全过程的综合实践能力。巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的学习作风。为今后学习其他计算机课程打下基础。课程设计为学生提供了一个既动手又动脑，独立实践的机会，将书本上的理论知识和工作、生产实际有机地结合起来，从而锻炼学生分析问题、解决实际问题的能力，提高学生的编程序能力和创新意识。二、课程设计的要求在处理每个题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思
2、算法、通过算法的设计实现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的课程设计与程序分析报告。前期准备工作完备与否直接影响到后序上机调试工作的效率。三、课程设计的学生分组情况每组三至五人，共同研究、共同讨论，可以共同编写算法，但必须各自独立完成各自的程序。四、课程设计的时间安排课程设计前两周：将各项任务及问题进行讲解、分析。课程设计一周： 星期一：学生对任务进行讨论、研究与分析，初步设计出算法。 星期二到星期四：设计出详细算法，并上机调试程序。 星期五到星期六：写出课程设计报告并考核。五、课程设计的主要内容【课程设计题目一】一元稀疏多项式加法、乘法器【问题描述】设计一个
3、一元稀疏多项式加法、乘法器用于计算两个多项式的加法和乘法。例如（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）之间架设局域网，如何以最低的经济
4、代价架设这个局域网。【基本要求】（1） 利用三种方法（Prim算法、克鲁斯卡尔（Kruskual和矩阵运算）算法生成局域网的架设方案（2） 写出课程设计报告。【测试数据】分别对每种方法选定一组测试数据进行测试，验证程序的正确性。【课程设计题目三】二叉树的创建、二叉树的遍历【问题描述】创建一棵二叉树，并对二叉树进行中序、前序、后序和层次遍历，分别写出它们的递归、非递归遍历算法。【基本要求】创建多种（五种以上）不同形态的二叉树，验证上述算法。【课程设计题目四】校园导游咨询系统【问题描述】设计一个你所在学校的校园导游程序，为来访的客人提供各种信息查询服务。【基本要求】（1） 设计你所在学校的校园平面
5、图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称，代号，简介等信息；以边表示路径，存放路径长度等相关信息。（2） 为来访客人提供图中任意景点相关信息的查询。（3） 为来访客人提供图中任意景点的问路查询，即查出任意两个景点之间的一条最短的简单路径。（4） 写出课程设计报告【测试数据】选定一组测试数据进行测试，验证程序的正确性。【课程设计题目五】通信网络的架设问题【问题描述】若要在n（10）个城市之间建设通信网络，只需要架设n-1条线路即可，如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。【基本要求】（1）利用三种方法（Prim算法、克鲁斯卡尔（Kruskual和矩阵
6、运算）生成网中的最小生成树（2）写出课程设计报告。【测试数据】分别对每种方法选定三组测试数据进行测试，验证程序的正确性。【课程设计题目六】内部排序的比较【问题描述】比较内部排序冒泡排序、插入排序、二分插入排序、选择排序的运行时间。给出算法执行的时间阶或每个程序的运行时间，精确到秒。【基本要求】（1）比较下列几种内部排序：冒泡排序、插入排序、二分插入排序、选择排序的运行时间。要求随机生成20000个测试数据进行测试，并输出每个程序的运行时间，精确到秒。（2）写出课程设计报告【测试数据】选定一批测试数据进行测试，验证程序的正确性并对计算时间进行比较。【课程设计题目七】算法表达式的求值演算【问题描述
7、】以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。利用教科书给出的算符优先关系，加上乘方()和求除（%）运算符，实现对算术混合运算表达式的求值。【基本要求】（1） 用顺序栈实现（2） 含有乘方()、加(+)、减(-)、乘(*)、除(/)、求除（%）等运算；并含有括号。（3） 分别以五组不同的表达式作为测试实例，每个实例中含有上述所有运算符，测试其结果的正确性。（4） 写出课程设计报告【测试数据】选定五组测试数据进行测试，验证程序的正确性。【课程设计题目八】设计一个矩阵运算器【问题描述】设计一个矩阵运算器，对矩阵进行乘方()、加(+)、减(-)、乘(*)运算；【基本要求】（1） 参见
8、数据结构题集P136页4.1（2） 求含有乘方()、加(+)、减(-)、乘(*)运算；。（3） 写出课程设计报告【测试数据】分别选定一组测试数据进行测试，验证程序的正确性。【课程设计题目九】自来水管理架设问题【问题描述】若要在扬州大学的八个居民区（A区、B区、C区、D区、E区、F区、G区、H区）之间架设自来水管道，如何以最低的经济代价架设这个自来水管道。【基本要求】（1）利用三种方法（Prim算法、克鲁斯卡尔Kruskual和矩阵运算）算法生成自来水管道的架设方案（2）写出课程设计报告。【测试数据】分别对每种方法选定三组测试数据进行测试，验证程序的正确性。【课程设计题目十】校园网架设的方案设计
9、问题【问题描述】若要在扬州大学的八个校区（江阳路南校区、江阳路北校区、盐阜校区、瘦西湖校区、农学院校区、工学院校区、水利学院校区、医学院校区）之间架设校园网，如何以最低的经济代价架设这个校园网。【基本要求】（1）利用三种方法（Prim算法、克鲁斯卡尔（Kruskual）和矩阵运算）算法生成校园网的架设方案（2）写出课程设计报告。【测试数据】分别对每种方法选定一组测试数据进行测试，验证程序的正确性。【课程设计题目十一】学生成绩管理系统【问题描述】现有学生成绩信息文件1（1.txt），内容如下姓名 学号 语文 数学 英语 张明明 01 67 78 82李成友 02 78 91 88张辉灿 03 6
10、8 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) 输入一个学生姓名后,能查找到此学
11、生的信息并输出结果(至少采用两种查找方法实现)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.
12、. . . 【基本要求】试编写一管理系统,要求如下:1) 实现对两个文件数据进行合并,生成新文件3.txt2) 抽取出三科成绩中有补考的学生并保存在一个新文件4.txt3) 对合并后的文件3.txt中的数据按总分降序排序(至少采用两种排序方法实现)4) 输入一个学生姓名后,能查找到此学生的信息并输出结果(至少采用两种查找方法实现)5) 要求使用结构体和数组实现上述要求.【课程设计题目十三】算法表达式的求值演算【问题描述】以字符序列的形式从终端输入语法正确的、不含变量的整数表达式。利用教科书给出的算符优先关系，加上乘方()和求除（%）等运算符，实现对算术混合运算表达式的求值。【基本要求】(1)
13、用链栈实现(2) 含有乘方()、加(+)、减(-)、乘(*)、除(/)、求除（%）等运算；并含有括号。(3) 分别以五组不同的表达式作为测试实例，每个实例中含有上述所有运算符，测试其结果的正确性。(4) 写出课程设计报告【测试数据】选定五组测试数据进行测试，验证程序的正确性。六、课程设计报告的主要内容课程设计报告主要包括以下几方面的内容：（1） 课程设计的题目（2） 课程设计的目的（3） 分析系统的主要功能及用途（4） 分析和描述系统的基本要求（5） 问题实现的主要算法与分析（6） 源程序（7） 使用方法与说明（8） 课程设计的小结（9） 参考文献七、课程设计的考核结合学生的动手能力，独立分析
14、解决问题的能力和创新精神，总结报告和答辩水平以及学习态度综合考评。考核成绩分优、良、中、及格和不及格五等。考核主要包含以下几方面内容：1） 运行所设计的系统2） 回答相关题目的问题3） 提交课程设计报告4） 提交软盘（含源程序、执行程序和课程设计报告）5） 内容要有创新。八、附录(课程设计报告示例)数 据 结 构课 程 设 计 报 告课题名称最小生成树问题 姓名 学院 广陵学院 系科班级 计科81101 指导老师 陈宏建 日期2013年1月12日 目录l 一、问题描述 2l 二、概要设计 2n 1抽象数据类型定义2n 2程序包含模块 2n 3函数调用关系 3l 三、详细设计 3n 1顶点、边、
15、图和集合类型 3n 2图的基本操作 4n 3程序详细代码 5n 4函数调用关系图 15l 四、设计和调试分析15l 五、用户手册16l 六、测试结果18l 七、附件19l 八、心得体会20最小生成树问题一、 问题描述1、 要在n个城市之间建设通信网络，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信网络，是一个网的最小生成树问题。2、 利用克鲁斯卡尔算法求网的最小生成树。假设连通网N=（V，E），则令最小生成树的的初始状态为只有n个结点而无边的非连通图T=（V，），图中每一个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，
16、否则舍去此边选择下一条代价最小的边。依次类推，直至T中所有顶点都在同一连通分量上为止。3、 使用Mfset类表示构造生成树过程中的连通分量。4、 测试数据（附后）。二、 概要设计1、 抽象数据类型定义如下：ADT Graph数据对象V：V是具有相同特性的数据元素的集合，成为顶点集。数据关系R：R=VRVR=(v,w)|v,wV,(v,w)表示v和w之间存在路径基本操作P：CreatGraph(&G);操作结果：初始化一个图。Initial(&S,n,x1,x2,xn);操作结果：初始化操作。构造一个由n个子集（每个子集只含单个成员Xi）构成的集合S。Find(S,v);初始条件：S是已经存在的
17、集合，v是某个子集成员。操作结果：查找函数。返回S中v所属子集Si。Merge(&S,i,j);初始条件：Si和Sj是S中两个互不相交的非空集合。操作结果：归并操作。将Si和Sj中的一个并入另一个。Kruskal(void);初始条件：图G存在。操作结果：求图G的最小生成数。Output(void);初始条件：已经生成图G的最小树。操作结果：输出操作。将最小生成树以文本形式输出到文件中。ADT Graph2、 本程序包含5个模块1） 主程序模块，其中主函数为main() 初始化图形界面； 读入用户选择信息； 根据用户选择执行相应模块； 关闭文件及图形界面； ；2） 汉字显示模块实现DOS模式下
18、的汉字显示；3） 随机图单元模块实现随机生成图；4） 读图模块实现从指定文件中读图；5） 图形输出模块实现图的仿真输出。6） 集合操作模块实现集合的查找合并。7） 求最短路径模块实现Kruskal算法求图最短路径。3、 函数调用关系：三、 详细设计1、 顶点、边、图和集合类型#define change(a,b) a=a+b,b=a-b,a=a-b;/交换两个变量值#define Pi 3.14159265358979323846264/值#define NYAN /是否演示树的生成过程typedef struct int x,y;/该城市的纵横坐标 int tag;/该城市的访问标志 cha
19、r name64;/城市名verType;/顶点类型typedef struct int bg,ed;/边的两端顶点号 int wt;/边的权值 int tag;/边的访问标志edgType;/边类型typedef struct verType *v;/指向顶点集合 edgType *e;/指向边集合 int vn,en;/顶点及边的数目 char name64;/图名字GType;/图类型GType g;/图全局变量FILE *fp;/文件指针变量2、 图的基本操作void initgph(void);/初始化函数。将系统设置为图形工作模式。void getdot(unsigned char
20、 c,unsigned char n8);/将c分解为二进制01串，存放在n中。int pnthz(int x,int y,int fcolor,int bcolor,char os);/x,y是屏幕坐标，fcolor和bcolor是前景色及背景色，os是汉字字符串；在x,y位置输出汉字串os。void copyedg(edgType *e1,edgType *e2)/ e1和e2是图的两条边。将e1的内容赋给e2。void randomedg(void)/初始化。对边集进行随机赋值。void randomver(void)/初始化。对顶点集进行随机赋值。void readver(void)/
21、读入信息。将存放在文件里的图顶点信息读入内存。void readedg(void)/读入信息。将存放在文件里的图边信息读入内存。void drawver(void)/绘图操作。在屏幕上绘制结点。void drawedg(void)/绘图操作。在屏幕上绘制边。void initial(void)/初始化操作。构造一个由n个子集（每个子集只含单个成员Xi）构成的集合S。int find(int v)/S是已经存在的集合，v是某个子集成员。返回S中v所属子集Si。void merge(int v1,int v2)/S1和S2是S中两个互不相交的非空集合。将S1和S2中的一个并入另一个。void kr
22、uskal(int v1,int v2)/求图G的最小生成树。void output(void)/输出操作。将最小生成树以文本形式输出到文件中。void fromfile(char fname)/fname是图文件名。打开文件操作。打开图信息文件，为读图做准备。void userinput(void)/由用户输入图文件名。void randomimage(void)/调用Randomedg()和Randomver()函数对边集和顶点集进行随机赋值。int choose(void)/由用户选择图信息的生成方式。返回选择项的序号。3、 程序详细代码#include#include#include#
23、include#include#include#define change(a,b) a=a+b,b=a-b,a=a-b;#define Pi 3.1415926535897932384626433832795#define NYANtypedef struct int x,y,tag; char name64;verType;typedef struct int bg,ed,wt,tag;edgType;typedef struct verType *v; edgType *e; int vn,en; char name64;GType;GType g;FILE *fp;void initg
24、ph(void)int gmode,gdrive; printf(nntInitializtion graph mode, please wait.); gmode=DETECT; initgraph(&gmode,&gdrive,C:Tc);void getdot(unsigned char c,unsigned char n8)char i; for(i=0;i(7-i)&1);int pnthz(int x,int y,int fcolor,int bcolor,char os)FILE *hzk=NULL; unsigned int j,k,cn2,cx,cy; unsigned lo
25、ng i,len,p; unsigned char c32,n8,ch2,s128; for(i=0,j=0,len=0;osj!=0;i+,j+,len+) if(osj32) si+=0xAA; si=0xA1+(osj-33); len+; else if(osj=32) si+=0xA1; si=0xA1; len+; else si=osj; if(len=0) return(0); len/=2; if(hzk=fopen(C:WindowsCommandChs16.fon,rb)=NULL) return(1); for(i=0;ilen;i+) ch0=si*2; ch1=si*2+1; cn0=(ch0-0xA1); cn1=(ch1-0xA1); p=(cn0*94L+cn1)*32L; rewind(hzk); fseek(hzk,p,0); fread(&c,sizeof(char),32,hzk); for(j=0;j32;j+) getdot(cj,n); for(k=0;kbg=e2-bg; e1-ed=e2-ed; e1-wt=e2-wt; e1-tag=e2-ta
