管道铺设施工的最佳方案问题Word文件下载.doc
《管道铺设施工的最佳方案问题Word文件下载.doc》由会员分享，可在线阅读，更多相关《管道铺设施工的最佳方案问题Word文件下载.doc（23页珍藏版）》请在冰点文库上搜索。
Pleaseinputtheinformationofthevertices<
v>
输入极点信息，而后进入循环，创立各个顶
点的毗邻表，即依据提示信息
Pleaseinput
theinformation
ofedges<
p,q>
和"
Pleaseinputtheinformationofweight:
挨次输入各极点与其余极点本
身以及二者之间的权值，创立图完成。
用户输入完成后，程序自动输出运转结果。
输入值一定为字母和浮点数，能够不用划分大小写。
3.测试数据要求：
用户输入字母时，输入大写或小写，都能够被该程序辨别，正常运转。
但必
须依据提示信息后边给出的参照形式，有针对性地输入逗号。
三．纲要设计
为了实现上述功能，该程序以毗邻表来储存图，所以需要图这个抽象数据类
型。
1.图抽象数据种类定义：
ADTALGraph{
数据 对象 ：
D={
ai
bi
ci
|ai
AdjList,bi
int,ci
int
，
i=1,2,3....,n,n
0}
数据关系：
R=;
基本操作：
Create_ALGraph（G）；
程序保护模块：
主函数模块
图模块
调用关系：
主函数模块 图模块
3.主要算法流程图：
Create_ALGraph（）算法流程图：
Create_WLGraph（） 算法流程图：
开始
读入极点
数和边数 i=0
i=0
i<
n
T
F
读入顶
点信息
i=i+1
K=0
s！
=NULL
F T
该权值还未
存入W中
读入该权值
及左右极点
编号
K<
2e
s=s->
next
读入边<
Vi,Vj>
的对应极点及
权值
将新边表结点
插入到极点Vi
的边表头部
结束
k=k+1
Create_TLGraph（）算法流程图：
初始化储存各顶
点被接见状况及
地点信息的结构
体指针vp
i=1
e
调用
judge_vertex（
）函数
若两极点都已
被接见过
若两极点地点
不一样
将该权值加入 T
中，并把地点
改同样
若左极点未被
接见，右极点
已被接见
若左极点已被
未被接见
若两极点都未
被接见
将该权值加入T
中，并把左极点
中，并把右极点
中，并把两极点
的地点改为和右
的地点改为和左
的地点改为同样
极点同样
输出最小生
成树的各边
四．详尽设计
1.有关头文件的调用说明：
#include<
>
#defineMaxVerNum100
2.元素种类、结点种类和结点指针种类：
staticvoidforcefloat（float*p）
{
floatf=*p;
forcefloat（&
f）;
}
typedefstructnode
{intadjvex;
floatinfo;
structnode*next;
}EdgeNode;
typedefstructvnode
{charvertex;
EdgeNode*firstedge;
}VertexNode;
typedefVertexNodeAdjList[MaxVerNum];
structbian
{intz,y;
floatinfo;
};
typedefstruct
{charv[MaxVerNum];
structbiane[MaxVerNum];
}WGraph;
structvisit
{visited[MaxVerNum];
position[MaxVerNum];
vvpp[MaxVerNum][MaxVerNum];
3.毗邻表种类：
{AdjListadjlist;
intn,e;
}ALGraph;
ertex））;
G->
adjlist[i].firstedge=NULL;
/*if（G->
adjlist[i].vertex!
='
'
&
\n'
'
）
x++;
*/
for（k=0;
k<
2*（G->
e）;
k++）
{printf（"
Pleaseinputtheinformationofedges<
\n"
）;
getchar（）;
scanf（"
%c,%c"
&
p,&
q）;
s=（EdgeNode*）malloc（sizeof（EdgeNode））;
s->
adjvex=q-64;
i=p-64;
printf（"
%f"
（s->
info））;
next=G->
adjlist[i-1].firstedge;
adjlist[i-1].firstedge=s;
}/*
Pleaseoutputtheinformation:
%d,%d\n"
G->
n,G->
x=%d\n"
x）;
for（i=0;
n;
i++）
%c\n"
adjlist[i].vertex）;
s=G->
adjlist[i].firstedge;
while（s!
=NULL）
thelinbianis%d,theinfois%.1f\n"
s->
adjvex,s->
info）;
next;
}*/
intPanduan_Vertex（intk,inti,WGraph*w,EdgeNode*s）
{intt;
for（t=0;
t<
k;
t++）
if（（w->
e[t]）.y==i+1&
（w->
e[t]）.z==s->
adjvex）
return1;
return0;
voidselect_info（WGraph*W,ALGraph*G）
{inti,j,p,k;
floatt;
（G->
{p=i;
for（j=i+1;
j<
j++）
if（W->
e[j].info<
W->
e[p].info）p=j;
if（p!
=i）
{t=W->
e[p].info;
e[p].info=W->
e[i].info;
e[i].info=t;
k=W->
e[p].z;
e[p].z=W->
e[i].z;
e[i].z=k;
e[p].y;
e[p].y=W->
e[i].y;
e[i].y=k;
for（i=0;
%.1f"
W->
e[i].info）;
intjudge_vertex（WGraph*w,inti,structvisit*vp）
if（vp->
visited[w->
e[i].z-1]==-1&
vp->
e[i].y-1]==-1）
elseif（vp->
e[i].y-1]==1）
return2;
e[i].y-1]==-1&
e[i].z-1]==1）
return3;
e[i].z-1]==1&
return4;
voidCreate_TLGraph（WGraph*w,ALGraph*G）
{WGraphT;
inti,j,t,h,k=2;
intm=1;
intabc,bcd;
structvisit*vp;
vp=（structvisit*）malloc（sizeof（structvisit））;
n）;
{vp->
visited[i]=-1;
position[i]=-1;
vvpp[i][0]=i+1;
for（j=1;
vvpp[i][j]=0;
[0]=w->
v[w->
e[0].z-1];
[1]=w->
e[0].y-1];
e[0].z-1]=1;
position[w->
e[0].z-1]=w->
e[0].z;
for（j=0;
vvpp[w->
e[0].z-1][j]==0）
e[0].z-1][j]=w->
e[0].y;
break;
e[0].y-1]=1;
e[0].y-1]=w->
[0].info=w->
e[0].info;
[0].z=w->
[0].y=w->
for（i=1;
{t=judge_vertex（w,i,vp）;
if（t==4）
{if（vp->
e[i].z-1]==vp->
e[i].y-1]）
continue;
else{abc=0;
bcd=0;
vvpp[vp->
e[i].y-1]-1][j]!
=0）
abc++;
e[i].z-1]-1][j]!
bcd++;
for（j=bcd,h=0;
n&
h<
abc;
j++,h++）
vvpp[（vp->
e[i].z-1]）-1][j]=vp->
position[w->
e[i].y-1]）-1][h];
e[i].y-1]-1][h]=0;
for（h=bcd;
abc+bcd;
h++）
position[（vp->
e[i].z-1]-1][h]）-1]=vp->
position[w->
e[i].z-1];
[m].info=w->
[m].z=w->
[m].y=w->
m++;
elseif（t==1）
{vp->
e[i].z-1]=1;
vp->
e[i].y-1]=1;
[k++]=w->
e[i].y-1];
e[i].z-1]=w->
e[i].y-1]=w->
e[i].z-1][1]=w->
e[i].y-1][0]=0;
elseif（t==2）
e[i].z-1]=vp->
e[i].y-1]-1][j]==0）
e[i].y-1]-1][j]=w->
e[i].z-1][0]=0;
elseif（t==3）
e[i].y-1]=vp->
e[i].z-1]-1][j]==0）
e[i].z-1]-1][j]=w->
n）-1;
（%c,%c）\n"
[i].z+64,[i].y+64）;
voidCreate_WLGraph（ALGraph*G）
{inti,j,t,m,k=0;
EdgeNode*s,*p;
WGraph*W;
W=（WGraph*）malloc（sizeof（WGraph））;
v[0]=G->
adjlist[0].vertex;
adjlist[0].firstedge;
{W->
e[k].z=1;
e[k].y=s->
adjvex;
e[k].info=s->
info;
k++;
v[i]=G->
adjlist[i].vertex;
{m=Panduan_Vertex（k,i,W,s）;
if（m==1）
{s=s->
else
{W->
e[k].z=i+1;
v[i]）;
e;
%d,%d,%.1f\n"
e[i].z,W->
e[i].y,W->
select_info（W,G）;
Create_TLGraph（W,G）;
4.主函数的伪码：
main（）
{ALGraph*G;
5.函数调用关系：
调用 调用
Create_ALGrap Panduan_Ver
h（）函数 tex（）函数
Create_WLGrCreate_TLGrjudge_verte
函数
aph（）函数
x（）函数
select_info
（）函数
五．调试剖析
1.出现问题及解决方法：
在刚开始写程序时，因为考虑不全面，在去除连通图闭合回路的算法中碰到
很大困难，以后采纳以下方法解决了这个问题：
将每个极点分别放在一个结构体中，结构体中的数组 visited[i] 记录极点
Vi能否被接见过的状况，position[i] 记录极点Vi的详细地点，二维数组
vvpp[i][j] 记录已经将以该极点为左极点或右极点的权值存入 T中后，该权值的
右极点或左极点的编号。
其详细思想是：
只需将一个权值存入 T中，就将相应的
左右极点放到同一个二维数组中， 以后每欲将一个权值加入 T中，先查验该权值
的两极点能否在同一个二维数组中。
若不在，则将该权值存入 T中；
若在，将该
权值舍去（因为再将该权值加入 T中，就会出现回路）。
2.方法优弊端剖析：
长处：
①思想比较简单，简单令人理解；
②在写中默算法时，先将字母极点用相应的数字取代，所以在将数字转变成字母回去时，利用数字与ASCII码值的固定差值，能够保证用户在输
入时的大小写字母都能够被该程序辨别。
弊端：
因为采纳数字来取代字母， 中间的变换关系比较复杂，特别是将对应关系
理清需要足够的耐心和仔细。
3．主
升级会员 