算法程序设计实验报告.docx
《算法程序设计实验报告.docx》由会员分享，可在线阅读，更多相关《算法程序设计实验报告.docx（28页珍藏版）》请在冰点文库上搜索。
算法程序设计实验报告
A幺上火孝
TilVL地NIIMLVER弓ITYOFTECHNOLOCY
《程序设计》课程设计
姓
名：
王
学
号：
20100034
班
级：
软件工程00班
指导教师：
王会青
成
绩：
2010年6月
实验一.构造可以使n个城市连接的最小生成树
专业：
_软件工程_班级：
—软件姓名：
_王_学号：
—20100034
完成日期：
2010/6/26
【问题描述】
给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法
建立最小生成树，并计算得到的最小生成树的代价。
1城市间的道路网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个
城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。
显示出城市间道路网的邻接矩阵。
最小生成树中包括的边及其权值，并显示得到的最小生成树的总代价。
出最小生成树
【问题分析】
1.抽象数据类型结构体数组的定义
#ifndefADJACENCYMATRIXED/防止该头文件被重复引用
#defineADJACENCYMATRIXED//而引起的数据重复定义
#defineINFINITY32767//最大值
#defineMAX_VERTEX_NUM20//最大顶点个数
typedefint
typedefchar
typedefcharVertexType[MAX_VERTEX_NUM];//顶点类型
VRType;//权值，即边的值
InfoType;//附加信息的类型，后面使用时会定义成一个指针
typedefenum{DG=1,DN,UDG,UDN}GraphKind;//{有向图，有向网，无向图，无向网typedefstructArcCell
{
对带权图,
VRTypeadj;//VRType是顶点关系类型。
对无权图，用1或0表示相邻否;则为权值类型。
InfoType*info;//该弧关系信息的指针
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedefstruct
{
VertexTypevexs[MAX_VERTEX_NUM];//顶点向量
AdjMatrixarcs;//邻接矩阵
int
GraphKind
}MGraph;
vexnum,arcnum;kind;
//图的当前顶点数和弧数
//图的种类标志
adjvex;lowcost;
}closedge[MAX_VERTEX_NUM];
#endif
//结束if
2程序模块
//网G,唯一的全局变量
//主函数
MGraphG;
intmain（intargc,char*argv[]）;
StatusLocateVex（MGraphG,VertexTypev）;//判断城市v在网G中的位置StatusCreateUDN（MGraph&G）;//创建网G的邻接矩阵
voidDisplayNet（MGraphG）;//以邻接矩阵的形式显示网G
voidMiniSpanTree_KRUSKAL（MGraphG）;//最小生成树的Kruskal算法
voidMiniSpanTree_PRIM（MGraphG,VertexTypeu）;//最小生成树的Prim算法
StatusMinimum（closedgecloseEdge,intn）;//Prim算法中求下一个城市的函数voidDeletelnfo（MGraph&G）;//释放堆内存上动态申请的空间
3.流程图
创建用邻接矩阵表示的城市道路网
输入城市数G.vexnum、
道路数G.arcnum
输入城市名G.vexs[i]
Prim算法
化辅助数组closeEdge
for（i=1;ivG.vexnum;++i）
求下一个城市k=Minimum（closeEdge,
G.vexnum）
输出找到的道路
标记城市，避免重复
输出总耗费
4.数据类型定义
为了用邻接矩阵表示图
G，先是定义二维数组的每一个元素含道路值然后在图的定义中定义
一个此二维数组的结构成员。
并且在图中还定义一个用来存放城市的一维数组及
int型的城市数级
道路数。
用二维数组的两个下标表示道路，这两个下标又在一位数组中对应两个城市。
这样就建立起了一个城市到城市之间的道路网。
4.程序主要模块
说明：
该程序共含5个模块，本人负责其中2个模块构造:
***************LocateVex（MGraphG,VertexTypev）****************
StatusLocateVex（MGraphG,VertexTypev）;
while（strcmp（G.vexs[i],v））{i++;}
返回i;
****************createUDN*************************
输入城市数、道路数;
for（i=0;i＜城市数；++i）输入城市名;
for（i=0;i<城市数；++i）
for（j=0;j<城市数；++j）
初始化邻接矩阵：
道路值=INFINITY;
for（i=0;i<城市数；++i）
for（j=0;j<城市数；++j）
输入两个城市表示道路，输入道路值;
PRIM算法
**************************MiniSpanTreePRIM*********voidMiniSpanTree_PRIM（MGraphG,VertexTypeu）
定义辅助数组：
closedgecloseEdge;
初始化：
strcpy（closeEdge[j].adjvex,u）;
closeEdge[j].lowcost=G.arcs[k][j].adj;
for（i=1;ivG.vexnum;++i）
在其余G.vexnum-1个城市中找到离辅助数组中标记的道路最小值;
显示找到的道路;
标记新找到的城市;
**********************Minimum*****************
StatusMinimum（closedgecloseEdge,intn）
在辅助数组中找到道路值最小的道路的两点城市:
if（（closeEdge[i].lowcost!
=0）&&（minTemp>closeEdge[i].lowcost））
返回该城市在G中的位置
【功能实现】
#include#include#include#include
#include"TypeDefine.h"#include"AdjacencyMatrix.h"#include"InitializeFunction.h"#include"MiniSpanTree_KRUSKAL.h"#include"MiniSpanTree_PRIM.h"#include"DisplayNet.h"#include"DeleteInfo.h"
intmain（intargc,char*argv[]）;//主函数
StatusCreateUDN（MGraph&G）;//创建网G的邻接矩阵
voidDisplayNet（MGraphG）;//以邻接矩阵的形式显示网
Prim算法
voidMiniSpanTree_PRIM（MGraphG,VertexTypeu）;//最小生成树的
StatusMinimum（closedgecloseEdge,intn）;//Prim算法中求下一个城市的函数
voidDeleteInfo（MGraph&G）;//释放堆内存上动态申请的空间intmain（intargc,char*argv[]）
CreateGraph（G）;
DisplayNet（G）;
MiniSpanTree_KRUSKAL（G）;
MiniSpanTree_PRIM（G,G.vexs[0]）;
DeleteInfo（G）;
cout<system（"pause"）;
return0;
//intializeFunction.h
StatusCreateDG（MGraph&G）{return0;};
StatusCreateDN（MGraph&G）{return0;};
StatusCreateUDG（MGraph&G）{return0;};
StatusCreateUDN（MGraph&G）;
StatusLocateVex（MGraphG,VertexTypev）
//判断输入的顶点v在G中的位置。
//根据顶点的类型，可重载此函数。
目前为char
inti=0;
while（strcmp（G.vexs[i],v））{i++;}
returni;
StatusCreateGraph（MGraph&G）
//米用数组（邻接矩阵）表示法，构造图G.
G.kind=UDN;//默认构造无向网
printf（"|1:
有向图2:
无向图3:
有向网4:
无向网\n"）;
printf（"|请选择:
[]\b\b"）;
scanf（"%d",&G.kind）;
switch（G.kind）
caseDG:
returnCreateDG（G）;//构造有向图
caseDN:
returnCreateDN（G）;//构造有向网
caseUDG:
returnCreateUDG（G）;//构造无向图
caseUDN:
returnCreateUDN（G）;//构造无向网
default:
returnERROR;
}//CreateGraph
StatusCreateUDN（MGraph&G）
inti,j,k;
VertexTypev1,v2;
VRTypew;
//构造顶点向量
cin>>G.vexnum>>G.arcnum;
for（i=0;i
printf（"请输入第%d个城市名
（共
%d个）：
",i+1,G.vexnum）;
cin>>G.vexs[i];
for（i=0;i//初始化邻接矩阵
for（j=0;jG.arcs[i][j].adj=INFINITY;
//
G.arcs[i][j].info=NULL;
printf（”
请输入一条道路连接的两个城市名及权值:
\n"）;
for（k=0;k//构造邻接矩阵
printf（"共％3d条道路，第％3d条道路：
",G.arcnum,k+1）;
cin>>v1>>v2>>w;
//输入一条边依附的顶点及权值
i=LocateVex（G,v1）;
//确定v1、v2在G中的位置
j=LocateVex（G,v2）;
returnOK;
}//CreateUDN
//MiniSpanTreePRIM.h
StatusMinimum（closedgecloseEdge,intn）
inti,flag,minTemp=INFINITY;
for（i=0;iif（（closeEdge[i].lowcost!
=0）&&（minTemp>closeEdge[i].lowcost））
minTemp=closeEdge[i].lowcost;
flag=i;
returnflag;
voidMiniSpanTree_PRIM（MGraphG,VertexTypeu）
//用普里姆算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边。
inti,j,k,totalCost=0;
closedgecloseEdge;
k=LocateVex（G,u）;
for（j=0;jif（j!
=k）
strcpy（closeEdge[j].adjvex,u）;
closeEdge[j].lowcost=G.arcs[k][j].adj;
coutvv"\n\n+AA八八八八八八八八八八八八八八八八八八八八八八八八八八八八八八八八八八八八八八八八八八\\\n";
H.
cout<<"|用Prim算法求最小生成树的各条边依次为：
\n
closeEdge[k].lowcost=0;//初始，U={u};
for（i=1;i
//此时closeEdge[k].lowcost=MIN{closeEdge[vi].lowcost|closeEdge[vi].lowcost>0,vi€V-U}
cout<<'<'<';//输出生成树的边
totalCost+=closeEdge[k].lowcost;
for（j=0;jif（G.arcs[k][j].adjstrcpy（closeEdge[j].adjvex,G.vexs[k]）;
closeEdge|j].lowcost=G.arcs[k]|j].adj;
coutw"]总代价：
"wtotalCostwendl;
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
；用卩im算法求最小生戍树的各条边依次为5
；总代价：
385
五、【心得体会】
通过本周的课程设计，我有不少收获。
既巩固和加深了对数据结构的理解，认识到《数据结构》是计算机专业一门重要的专业技术基础课程，还提高了我综合运用本课程所学知识的能力。
而且，并不是单纯的看看教材就能解决我们的实际问题，所以还要去查找各种我们所需要的资料,所以这次课程设计也培养了我选用参考书，查阅手册及文献资料的能力。
要完成一个课程设计的课题并不是一次就能编译成功的，中间会出现很多的大问题小问题，改错是个很繁琐的问题。
通过这次课程设计培养了我独立思考，深入研究，分析问题，解决问题的能力。
在以后的学习过程中我将要注意以下几点：
1、认真上好专业实验课，多在实践中锻炼自己。
2、
写程序的过程要考虑周到，严密。
3、在做设计的时候要有信心，有耐心，切勿浮躁。
4、认真的
学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。
5、在课余时间里多写程序，
熟练掌握在调试程序的过程中所遇到的常见错误，以便能节省调试程序的时间。
实验
学号：
20100034
专业：
软件工程班级：
软件姓名：
王
完成日期：
2010/6/281.【问题描述】
某次科研调查时得到了n个自然数，每个数均不超过1500000000（1.5*109）。
已知不相同的数不
超过10000个，现在需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出统计结果。
2【设计需求及分析】
（1）设计要求
原始数据保存在文件COUnt.in中，文件包含n+1行。
第1行是整数n（1<=n<=200000），表示自然数的个数；第2~n+1行每行一个自然数。
结果保存在文件count的尾部，其中结果包含m行（m为n个自然数中不相同数的个数），按照
自然数从小到大的顺序输出。
每行输出两个整数，分别是自然数和该数出现的次数，其间用一个空格隔开。
（2）设计思路
首先必须有文件的打开和关闭语句，将文件的内容读取到数组a[]中，然后对数组进行排列和对比，
计数。
最终输出数据和次数。
并写入文件的尾部。
fopen为文件打开函数，fscanf为文件读取函数，然后进行冒泡排序。
排序
if进行判断。
在不等于时，中间嵌套了一个while循环，进行往
A[]为容纳数据的数组，
之后的内容由while设置条件，用后的排查。
最后输出数据和次数。
下面是关键步骤：
FILE*fp=fopen（"count.txt","a+"）;if（fp==NULL）{
printf（”无文件"）;
return-1;}
for（i=0;i<9;i++）{
fscanf（fp,"%d",&a[i]）;
fscanf（fp,"\n"）;}
intj,t;
for（i=1;i<9;i++）for（j=0;j<9-i;j++）if（a[j]>a[j+1]）{t=a[j];
a[j]=a[j+1];a[j+1]=t;
}
for（i=0;i<9;i++）{
count=1;
if（a[i]!
=a[i+1]）{
printf（”％d\t%d\n",a[i],count）;
//用只读/的方式打开文件
//若没有文件则返回一1
//读取文件
//冒泡排序
fprintf（fp,"%d\t%d\n",a[i],a[i]）;i++;
}
if（a[i]==a[i+1]）
{
对数字的循环查找和控制条件，
while（a[i]==a[i+1]）{
count++;
i++;
}
}
（3）输入时，为竖行依此输入文件，且为数字。
且为数据，第二列为次数。
3.
#includeintmain（）{
inta[100];
FILE*fp=fopen（"count.txt","a+"）;printf（”无文件"）;
for（i=0;i<9;i++）{
fscanf（fp,"%d",&a[i]）;
intj,t;
for（i=1;i<9;i++）
for（j=0;j<9-i;j++）if（a[j]>a[j+1]）
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;}
printf（”结果为：
\n数据for（i=0;i<9;i++）{
count=1;
if（a[i]!
=a[i+1]）{
printf（"%d\t%d\n",a[i],count）;
printf（fp,"%d\t%d\n",a[i],a[i]）;i++;
}
if（a[i]==a[i+1]）
{
while（a[i]==a[i+1]）
{
count++;
i++;
}
printf（"%d\t%d\n",a[i],count）;
输出输入格式
9个以内的数字。
输出时，分为两行，第一列为【设计功能的实现】
//创建容纳文件数据的数组
//用只读/的方式打开文件
//若没有文件则返回一1
inti;
if（fp==NULL）{return-1;}
//读取文件
//冒泡排序
fscanf（fp,"\n"）;}
结果\n"）;
intcount;
fprintf（fp,"%d\t%d\n",a[i],count）;}
//关闭文件
}fclose（fp）;return0;
本次实验使我对于文件的打开和关闭语句有了更深的理解。
有打开必须有关闭。
同时在这次的设计中，我学习到了用泛洪算法解决实际问题的基本思维和步骤。
使我对算法的层次性更加清楚，更加加深了对算法的理解。
实验三.送
—20100034
专业：
_软件工程—班级：
—软件姓名：
_王_学号:
完成日期：
2010/6/26
输入：
输出：
45
124134
12
13
14
24
34
城市的地图和小明的路径如下图所示。
测试数据二
输入：
输出：
46
-1
12
13
14
24
34
23
输出说明：
城市的地图如下图所示，不存在满足条件的路径。
该算法使用欧拉回路，对于欧拉图，从一个节点出发，从某个节
点开始，然后查出一个从这个出发回到这个点的环路径。
这种方法不保证
每个边都被遍历。
如果有某个点的边没有被遍历就让这个点为起点，这条
边为起始边，把它和当前的环衔接上。
这样直至所有的边都被遍历。
这样,
整个图就被连接到一起了。
具体步骤:
1。
如果此时与该点无相连的点，那么就加入路径中
2。
如果该点有相连的点，那么就加入队列之中，遍历这些点，直到没
有相连的点。
3。
处理当前的点，删除走过的这条边，并在其相邻的点上进行同样的
操作，并把删除的点加入到路径中去。
4。
这个其实是个递归过程。
3【功能实现】
#inelude
#inelude
#inelude
#inelude
#inelude
#inelude
usingnamespacestd;constintmaxn=10005;
staekst;
veetorvee[maxn];
boolmap[maxn][maxn];intvis[maxn];
intcp[maxn];
intn,m;
voidpd（inta）{
ep[a]=1;
veetor:
:
iteratorit;
for（it=vee[a].begin（）;it!
=vec[a].endO;it++）
{
if（!
ep[*it]）pd（*it）;
}
}
dfs（inta）
void{
veetor:
:
iteratorit;
for（it=vec[a].begin（）;it
升级会员 