-
大小: 392KB文件類型: .rar金幣: 2下載: 0 次發(fā)布日期: 2021-05-28
- 語言: 其他
- 標(biāo)簽: 數(shù)據(jù)結(jié)構(gòu)??
資源簡介
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)——地鐵建設(shè)問題報(bào)告書加實(shí)現(xiàn)源代碼

代碼片段和文件信息
#include?
#define?TRUE?1
#define?FALSE?0
#define?OK?1
#define?ERROR?0
#define?INFINITY?10000????????????????????//最大值
#define?MAXVEX?20?????????????????????????//最大頂點(diǎn)個數(shù)
typedef?int?Status;
typedef?char?VertexType;??????????????????//?頂點(diǎn)類型應(yīng)由用戶定義
typedef?int?EdgeType;?????????????????????//邊上的權(quán)值類型應(yīng)由用戶定義
typedef?struct{
VertexType?vexs[MAXVEX];??????????????//頂點(diǎn)向量
????EdgeType?arc[MAXVEX][MAXVEX];?????????//鄰接矩陣可看作邊表
int?vexnumarcnum;????????????????????//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)
}MGraph;
//建立無向圖的鄰接矩陣表示
void?CreateMGraph(MGraph?*G)
{
int?ijkw;
printf(“Please?enter?the?number?of?station?and?road:\n“);
scanf(“%d%d“&G->vexnum&G->arcnum);?//輸入車站(頂點(diǎn))數(shù)量和道路(邊)數(shù)量
for(i=0;ivexnum;i++)??????????????//讀入頂點(diǎn)信息建立頂點(diǎn)表
scanf(&G->vexs[i]);
for(i=0;ivexnum;i++)
for(j=0;jvexnum;j++)
G->arc[i][j]=INFINITY; ??????//鄰接矩陣初始化
for(k=0;karcnum;k++)??????????????//讀入arcnum條邊建立鄰接矩陣
{
printf(“Enter?road(vivj)‘s?Sign?iSign?j?and?Distance?w:\n“);
scanf(“%d%d%d“&i&j&w);???????//輸入邊(vivj)上的權(quán)w
G->arc[i][j]=w;?
G->arc[j][i]=?G->arc[i][j];???????//因?yàn)槭菬o向圖矩陣對稱
}
}
//Prim算法生成最小生成樹
void?MiniSpanTree_Prim(MGraph?G)
{
int?min?i?j?ksum=0;
int?adjvex[MAXVEX]; ??????????????//保存相關(guān)頂點(diǎn)下標(biāo)
int?lowcost[MAXVEX]; ??????????????//保存相關(guān)頂點(diǎn)間邊的權(quán)值
printf(“The?shortest?line(By?Prim)?is:\n“);
lowcost[0]=0;?????????????????????????//初始化第一個權(quán)值為0即v0加入生成樹
??????????????????????????????//lowcost的值為0在這里就是此下標(biāo)的頂點(diǎn)已經(jīng)加入生成樹
adjvex[0]=0; ??????????????//初始化第一個頂點(diǎn)下標(biāo)為0
for(i=1;i {
lowcost[i]=G.arc[0][i]; ??????????//將v0頂點(diǎn)與之有邊的權(quán)值存入數(shù)組
adjvex[i]=0; ??//初始化都為v0的下標(biāo)
}
for(i=1;i {
min=INFINITY; ??????????????????//初始化最小權(quán)值
j=1;k=0;
while(j {
if(lowcost[j]!=0&&lowcost[j] ??????????????????????????????//如果權(quán)值不為0且權(quán)值小于min
{
min=lowcost[j]; ??????????//則讓當(dāng)前權(quán)值成為最小值
k=j; ??????????//將當(dāng)前最小值的下標(biāo)存入k
}
j++;
}
printf(“(%d%d)\n“adjvex[k]k);??//打印當(dāng)前頂點(diǎn)邊中權(quán)值最小的邊
sum=sum+lowcost[k];???????????????//累加最短路徑
lowcost[k]=0;?????????????????????//將當(dāng)前頂點(diǎn)的權(quán)值設(shè)置為0表示此頂點(diǎn)已經(jīng)完成任務(wù)
for(j=1;j {
if(lowcost[j]!=0&&G.arc[k][j] {?????????????????????????????//如果下標(biāo)為k頂點(diǎn)各邊權(quán)值小于此前這些頂點(diǎn)未被加入生成樹權(quán)值
lowcost[j]=G.arc[k][j];???//將較小的權(quán)值存入lowcost相應(yīng)位置
adjvex[j]=k; ??????//將下標(biāo)為k的頂點(diǎn)存入adjvex
}
}
}
printf(“The?whole?length?is:%d“sum);
}
int?main(void)
{
MGraph?G;
printf(“Data?Structure?Design-The?Construction?of?Subway\n“);
CreateMGraph(&G);
MiniSpanTree_Prim(G);
printf(“\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\tThe?End.“);
printf(“\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\tSoftWare?College?of?LNTU.“);
printf(“\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\tNetWork?Engineer?Class?One?LiuDongnan.“);
printf(“\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\tThank?you.“);
return?0;
}
?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????文件???????3329??2013-01-24?00:21??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告及源代碼\pro.c
?????文件?????347716??2014-01-13?21:39??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告及源代碼\數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì).doc
?????文件??????42043??2013-01-23?23:20??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告及源代碼\課設(shè)圖\1.jpg
?????文件??????34633??2013-01-24?00:17??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告及源代碼\課設(shè)圖\2.jpg
?????文件??????35795??2013-01-24?00:13??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告及源代碼\課設(shè)圖\3.jpg
?????文件??????79903??2013-01-23?22:40??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告及源代碼\課設(shè)圖\4.jpg
?????文件??????40940??2013-01-24?00:05??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告及源代碼\課設(shè)圖\5.jpg
?????文件??????29184??2013-01-23?20:23??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告及源代碼\課設(shè)圖\Doc1.doc
?????文件??????24008??2013-01-24?00:52??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告及源代碼\課設(shè)圖\文檔?1.doc
?????目錄??????????0??2013-05-03?13:35??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告及源代碼\課設(shè)圖
?????目錄??????????0??2014-01-13?21:40??數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告及源代碼
-----------?---------??----------?-----??----
???????????????637551????????????????????11
評論
共有 條評論