数据结构与算法7Word文件下载.docx
《数据结构与算法7Word文件下载.docx》由会员分享，可在线阅读，更多相关《数据结构与算法7Word文件下载.docx（23页珍藏版）》请在冰点文库上搜索。
15
∞
1
{v1,v3}
v3
25
75
2
{v1,v3,v2}
v2
40
3
{v1,v3,v2,v4}
v4
65
4
{v1,v3,v2,v4,v5}
v5
5
{v1,v3,v2,v4,v5,v6}
v6
#include<
iostream>
usingnamespacestd;
intmincost（EdgeDataD[NumVertices],BOOLEANS[NumVertices],intn）
{
intw;
EdgeDatatemp=MaxValue;
w=0;
for（inti=1;
i<
n;
i++）
if（!
S[i]&
&
D[i]<
temp）
{
temp=D[i];
w=i;
}
returnw;
}
voidDijkstra（MTGraphG,EdgeDataD[NumVertices],intP[NumVertices]）
BOOLEANS[NumVertices]={FALSE};
inti,v,w;
EdgeDatasum;
D[0]=MaxValue;
for（i=1;
G.n;
{
D[i]=G.edge[0][i];
S[i]=FALSE;
S[0]=TRUE;
for（i=1;
i++）
w=mincost（D,S,G.n）;
S[w]=TRUE;
for（v=1;
v<
G.n;
v++）
if（S[v]!
=TRUE&
G.edge[w][v]!
=MaxValue）
sum=D[w]+G.edge[w][v];
if（sum<
D[v]）
D[v]=sum;
P[v]=w;
}
}
voidmain（）
{
MTGraphG;
IniMGraph_directed（&
G）;
VertexDatav[6]={'
v1'
'
v2'
v3'
v4'
v5'
'
v6'
};
EdgeDatae[6][NumVertices]={
{MaxValue,45,15,30,15,MaxValue},
{MaxValue,MaxValue,MaxValue,20,15,15},
{10,10,MaxValue,60,MaxValue,MaxValue},
{MaxValue,30,MaxValue,MaxValue,MaxValue,20},
{MaxValue,MaxValue,MaxValue,MaxValue,MaxValue,MaxValue},
{MaxValue,MaxValue,MaxValue,MaxValue,MaxValue,MaxValue}};
CreateMGraph_directed（&
G,v,e,6）;
PrintMT（&
cout<
<
endl;
EdgeDataD[6];
intP[6]={0};
Dijkstra（G,D,P）;
for（inti=1;
6;
cout<
D[i]<
'
\t'
;
G.vexlist[P[i]]<
"
->
G.vexlist[i]<
四、应用Floyd算法，编程求下图所示有向图的每对顶点之间的最短路径（写出相应的矩阵），并求该图的中心点。
并利用Warshall算法，编程求该图的传递闭包（矩阵）。
最短路径矩阵：
中心点为：
d
voidFloyd（intA[NumVertices][NumVertices],MTGraphC,intP[NumVertices][NumVertices],intn）
inti,j,k;
for（i=0;
i<
n;
for（j=0;
j<
n;
j++）
{
A[i][j]=C.edge[i][j];
P[i][j]=-1;
for（k=0;
k<
k++）
j<
if（A[i][k]+A[k][j]<
A[i][j]）
{
A[i][j]=A[i][k]+A[k][j];
P[i][j]=k;
}
}
voidPath（intP[NumVertices][NumVertices],inti,intj）
intk=P[i][j];
if（k!
=-1）
{
Path（P,i,k）;
k+1<
Path（P,k,j）;
voidCenterPoint（EdgeDataA[NumVertices][NumVertices],intn,int&
cp）
EdgeDataE[NumVertices]={0};
intmin=MaxValue/2;
for（intj=0;
j++）
for（inti=0;
if（A[i][j]<
MaxValue/2）
E[j]+=A[i][j];
if（E[j]==0）
E[j]=MaxValue/2;
if（E[j]<
min）
min=E[j];
cp=j;
}
}
inti,j,cp;
a'
b'
c'
d'
e'
f'
{MaxValue/2,3,MaxValue/2,4,MaxValue/2,5},
{MaxValue/2,MaxValue/2,1,MaxValue/2,MaxValue/2,1},
{MaxValue/2,MaxValue/2,MaxValue/2,2,MaxValue/2,MaxValue/2},
{MaxValue/2,3,MaxValue/2,MaxValue/2,MaxValue/2,MaxValue/2},
{MaxValue/2,MaxValue/2,MaxValue/2,3,MaxValue/2,2}
{MaxValue/2,MaxValue/2,MaxValue/2,2,MaxValue/2,MaxValue/2}};
EdgeDataA[NumVertices][NumVertices]={0};
intA1[NumVertices][NumVertices]={0};
intP[NumVertices][NumVertices];
Floyd（A,G,P,G.n）;
每一对顶点之间的最短路径:
for（i=0;
for（intj=0;
cout<
A[i][j]<
CenterPoint（A,G.n,cp）;
\n\n中心点为:
"
G.vexlist[cp+1]<
传递闭包：
voidWarshall（intA[NumVertices][NumVertices],MTGraphC,intn）
if（C.edge[i][j]!
=MaxValue/2）
A[i][j]=1;
else
A[i][j]=0;
if（A[i][k]&
A[k][j]）
A[i][j]=A[i][j]||（A[i][k]&
A[k][j]）;
Warshall（A1,G,G.n）;
\n传递闭包为:
A1[i][j]<
五、依次输入表（30,15,28,20,24,10,12,68,35,50,46,55）中的元素，生成一棵二叉排序数，要求：
1、试画出生成之后的二叉排序树。
2、对该二叉排序数作中根遍历，写出遍历序列。
3、编程构建一个二叉排序数，并中根遍历验证上述结果。
二叉排序树：
中根遍历：
101215202428303546505568
typedefstructTreeNode
intkey;
structTreeNode*left;
structTreeNode*right;
}treeNode;
classBiSortTree
public:
BiSortTree（void）;
voiddesplayTree（void）;
voidinsertTree（intkey）;
deleteTree（intkey）;
treeNode*searchTree（intkey）;
~BiSortTree（）;
private:
treeNode*buildTree（treeNode*head,intnumber）;
treeNode*search（treeNode*head,intkey）;
treeNode*BiSortTree:
:
searchParent（treeNode*head,treeNode*p）;
searchMinRight（treeNode*head）;
voidshowTree（treeNode*head）;
voiddestroyTree（treeNode*head）;
treeNode*Head;
BiSortTree:
BiSortTree（）
建立一棵二叉排序树,请输入你要建树的所有数（以-1作为结束标志!
）:
Head=NULL;
intnumber;
cin>
>
number;
while（number!
Head=buildTree（Head,number）;
buildTree（treeNode*head,intnumber）
treeNode*p;
p=newtreeNode;
p->
key=number;
p->
left=p->
right=NULL;
if（head==NULL）
returnp;
else
if（p->
key<
head->
key）
left=buildTree（head->
left,number）;
else
head->
right=buildTree（head->
right,number）;
returnhead;
六、试画出从空树开始，有字符序列（t,d,e,s,u,g,b,j,a,k,r,i）构成的二叉平衡树，并为每一次平衡处理指明旋转类型。
思考题1：
Poj1125Floyd算法
StockbrokerGrapevine
Description
Stockbrokersareknowntooverreacttorumours.Youhavebeencontractedtodevelopamethodofspreadingdisinformationamongstthestockbrokerstogiveyouremployerthetacticaledgeinthestockmarket.Formaximumeffect,youhavetospreadtherumoursinthefastestpossibleway.
Unfortunatelyforyou,stockbrokersonlytrustinformationcomingfromtheir"
Trustedsources"
Thismeansyouhavetotakeintoaccountthestructureoftheircontactswhenstartingarumour.Ittakesacertainamountoftimeforaspecificstockbrokertopasstherumourontoeachofhiscolleagues.Yourtaskwillbetowriteaprogramthattellsyouwhichstockbrokertochooseasyourstartingpointfortherumour,aswellasthetimeitwilltakefortherumourtospreadthroughoutthestockbrokercommunity.Thisdurationismeasuredasthetimeneededforthelastpersontoreceivetheinformation.
Input
Yourprogramwillinputdatafordifferentsetsofstockbrokers.Eachsetstartswithalinewiththenumberofstockbrokers.Followingthisisalineforeachstockbrokerwhichcontainsthenumberofpeoplewhotheyhavecontactwith,whothesepeopleare,andthetimetakenforthemtopassthemessagetoeachperson.Theformatofeachstockbrokerlineisasfollows:
Thelinestartswiththenumberofcontacts（n）,followedbynpairsofintegers,onepairforeachcontact.Eachpairlistsfirstanumberreferringtothecontact（e.g.a'
1'
meanspersonnumberoneintheset）,followedbythetimeinminutestakentopassamessagetothatperson.Therearenospecialpunctuationsymbolsorspacingrules.
Eachpersonisnumbered1throughtothenumberofstockbrokers.Thetimetakentopassthemessageonwillbebetween1and10minutes（inclusive）,andthenumberofcontactswillrangebetween0andonelessthanthenumberofstockbrokers.Thenumberofstockbrokerswillrangefrom1to100.Theinputisterminatedbyasetofstockbrokerscontaining0（zero）people.
Output
Foreachsetofdata,yourprogrammustoutputasinglelinecontainingthepersonwhoresultsinthefastestmessagetransmission,andhowlongbeforethelastpersonwillreceiveanygivenmessageafteryougiveittothisperson,measuredinintegerminutes.
Itispossiblethatyourprogramwillreceiveanetworkofconnectionsthatexcludessomepersons,i.e.somepeoplemaybeunreachable.Ifyourprogramdetectssu
升级会员 