《数据结构》课程设计指导书1.doc
《《数据结构》课程设计指导书1.doc》由会员分享，可在线阅读，更多相关《《数据结构》课程设计指导书1.doc（29页珍藏版）》请在冰点文库上搜索。
《数据结构》课程设计指导书（共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.txt
2）抽取出三科成绩中有补考的学生并保存在一个新文件4.txt
3）对合并后的文件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.txt
2）抽取出三科成绩中有补考的学生并保存在一个新文件4.txt
3）对合并后的文件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日
目录
l一、问题描述………………………………………………2
l二、概要设计………………………………………………2
n1抽象数据类型定义……………………………………2
n2程序包含模块………………………………………2
n3函数调用关系………………………………………3
l三、详细设计………………………………………………3
n1顶点、边、图和集合类型…………………………3
n2图的基本操作………………………………………4
n3程序详细代码………………………………………5
n4函数调用关系图……………………………………15
l四、设计和调试分析………………………………………15
l五、用户手册………………………………………………16
l六、测试结果………………………………………………18
l七、附件……………………………………………………19
l八、心得体会………………………………………………20
最小生成树问题
一、问题描述
1、要在n个城市之间建设通信网络，只需要架设n-1条线路即可。
如何以最低的经济代价建设这个通信网络，是一个网的最小生成树问题。
2、利用克鲁斯卡尔算法求网的最小生成树。
假设连通网N=（V，{E}），则令最小生成树的的初始状态为只有n个结点而无边的非连通图T=（V，{}），图中每一个顶点自成一个连通分量。
在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边选择下一条代价最小的边。
依次类推，直至T中所有顶点都在同一连通分量上为止。
3、使用Mfset类表示构造生成树过程中的连通分量。
4、测试数据（附后）。
二、概要设计
1、抽象数据类型定义如下：
ADTGraph{
数据对象V：
V是具有相同特性的数据元素的集合，成为顶点集。
数据关系R：
R={VR}
VR={（v,w）|v,w∈V,（v,w）表示v和w之间存在路径}
基本操作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的最小树。
操作结果：
输出操作。
将最小生成树以文本形式输出到文件中。
}ADTGraph
2、本程序包含5个模块
1）主程序模块，其中主函数为
main（）
{初始化图形界面；
读入用户选择信息；
根据用户选择执行相应模块；
关闭文件及图形界面；
}；
2）汉字显示模块——实现DOS模式下的汉字显示；
3）随机图单元模块——实现随机生成图；
4）读图模块——实现从指定文件中读图；
5）图形输出模块——实现图的仿真输出。
6）集合操作模块——实现集合的查找合并。
7）求最短路径模块——实现Kruskal算法求图最短路径。
3、函数调用关系：
三、详细设计
1、顶点、边、图和集合类型
#definechange（a,b）a=a+b,b=a-b,a=a-b;
//交换两个变量值
#definePi3.14159265358979323846264
//Π值
#defineNYAN
//是否演示树的生成过程
typedefstruct{
intx,y;
//该城市的纵横坐标
inttag;
//该城市的访问标志
charname[64];
//城市名
}verType;
//顶点类型
typedefstruct{
intbg,ed;
//边的两端顶点号
intwt;
//边的权值
inttag;
//边的访问标志
}edgType;
//边类型
typedefstruct{
verType*v;
//指向顶点集合
edgType*e;
//指向边集合
intvn,en;
//顶点及边的数目
charname[64];
//图名字
}GType;
//图类型
GTypeg;
//图全局变量
FILE*fp;
//文件指针变量
2、图的基本操作
voidinitgph（void）;
//初始化函数。
将系统设置为图形工作模式。
voidgetdot（unsignedcharc,unsignedcharn[8]）;
//将c分解为二进制01串，存放在n中。
intpnthz（intx,inty,intfcolor,intbcolor,charos[]）;
//x,y是屏幕坐标，fcolor和bcolor是前景色及背景色，os是汉字字符串；在x,y位置输出汉字串os。
voidcopyedg（edgType*e1,edgType*e2）
//e1和e2是图的两条边。
将e1的内容赋给e2。
voidrandomedg（void）
//初始化。
对边集进行随机赋值。
voidrandomver（void）
//初始化。
对顶点集进行随机赋值。
voidreadver（void）
//读入信息。
将存放在文件里的图顶点信息读入内存。
voidreadedg（void）
//读入信息。
将存放在文件里的图边信息读入内存。
voiddrawver（void）
//绘图操作。
在屏幕上绘制结点。
voiddrawedg（void）
//绘图操作。
在屏幕上绘制边。
voidinitial（void）
//初始化操作。
构造一个由n个子集（每个子集只含单个成员Xi）构成的集合S。
intfind（intv）
//S是已经存在的集合，v是某个子集成员。
返回S中v所属子集Si。
voidmerge（intv1,intv2）
//S1和S2是S中两个互不相交的非空集合。
将S1和S2中的一个并入另一个。
voidkruskal（intv1,intv2）
//求图G的最小生成树。
voidoutput（void）
//输出操作。
将最小生成树以文本形式输出到文件中。
voidfromfile（charfname[]）
//fname是图文件名。
打开文件操作。
打开图信息文件，为读图做准备。
voiduserinput（void）
//由用户输入图文件名。
voidrandomimage（void）
//调用Randomedg（）和Randomver（）函数对边集和顶点集进行随机赋值。
intchoose（void）
//由用户选择图信息的生成方式。
返回选择项的序号。
3、程序详细代码
#include
#include
#include
#include
#include
#include
#definechange（a,b）a=a+b,b=a-b,a=a-b;
#definePi3.1415926535897932384626433832795
#defineNYAN
typedefstruct{
intx,y,tag;
charname[64];
}verType;
typedefstruct{
intbg,ed,wt,tag;
}edgType;
typedefstruct{
verType*v;
edgType*e;
intvn,en;
charname[64];
}GType;
GTypeg;
FILE*fp;
voidinitgph（void）
{intgmode,gdrive;
printf（"\n\n\tInitializtiongraphmode,pleasewait..."）;
gmode=DETECT;
initgraph（&gmode,&gdrive,"C:
\\Tc"）;
}
voidgetdot（unsignedcharc,unsignedcharn[8]）
{chari;
for（i=0;i<8;i++）
n[i]=（（c>>（7-i））&1）;
}
intpnthz（intx,inty,intfcolor,intbcolor,charos[]）
{FILE*hzk=NULL;
unsignedintj,k,cn[2],cx,cy;
unsignedlongi,len,p;
unsignedcharc[32],n[8],ch[2],s[128];
for（i=0,j=0,len=0;os[j]!
='\0';i++,j++,len++）
{if（os[j]>32）
{s[i++]=0xAA;
s[i]=0xA1+（os[j]-33）;
len++;
}
elseif（os[j]==32）
{s[i++]=0xA1;
s[i]=0xA1;
len++;
}
elses[i]=os[j];
}
if（len==0）return（0）;
len/=2;
if（（hzk=fopen（"C:
\\Windows\\Command\\Chs16.fon","rb"））==NULL）
return
（1）;
for（i=0;i{ch[0]=s[i*2];
ch[1]=s[i*2+1];
cn[0]=（ch[0]-0xA1）;
cn[1]=（ch[1]-0xA1）;
p=（cn[0]*94L+cn[1]）*32L;
rewind（hzk）;fseek（hzk,p,0）;
fread（&c,sizeof（char）,32,hzk）;
for（j=0;j<32;j++）
{getdot（c[j],n）;
for（k=0;k<8;k++）
{cx=（k+（j%2）*8+i*16+x）%640;
cy=j/2+y+（（k+（j%2）*8+i*16+x）/640）*16;
if（n[k]==1）putpixel（cx,cy,fcolor）;
elseif（bcolor!
=-1）putpixel（cx,cy,bcolor）;
}}
}
fclose（hzk）;
return（cx）;
}
voidcopyedg（edgType*e1,edgType*e2）
{e1->bg=e2->bg;
e1->ed=e2->ed;
e1->wt=e2->wt;
e1->tag=e2->ta
升级会员 