第一篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告
院系：計(jì)算機(jī)學(xué)院
班級(jí)：軟件121班
姓名：程猛
學(xué)號(hào)：201200834122 題目：最小生成樹
軟件121 程猛 201200834122
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告
指導(dǎo)老師：杜獻(xiàn)峰
一、引言..................................................................................................................4
二、設(shè)計(jì)題目..........................................................................................................4 1.問題描述...........................................................................................................4 2.系統(tǒng)要求...........................................................................................................4 3.測試數(shù)據(jù)...........................................................................................................5 4.實(shí)現(xiàn)提示...........................................................................................................5 5.參考文獻(xiàn)...........................................................................................................5 6.運(yùn)行環(huán)境...........................................................................................................6
三、需求分析..........................................................................................................6 1.如何選擇存儲(chǔ)結(jié)構(gòu)去建立一個(gè)帶權(quán)網(wǎng)絡(luò)。...................................................6 2.如何在所選存儲(chǔ)結(jié)構(gòu)下輸出這個(gè)帶權(quán)網(wǎng)絡(luò)。...............................................6 3.如何實(shí)現(xiàn)PRIM算法和Kruskal算法的功能。.............................................6 4.如何從每個(gè)頂點(diǎn)開始找到所有的最小生成樹的頂點(diǎn)。...............................7 5.如何輸出最小生成樹的邊及其權(quán)值。...........................................................7
四、概要設(shè)計(jì)..........................................................................................................7 2.圖的存儲(chǔ)結(jié)構(gòu)...................................................................................................8 3.流程圖...............................................................................................................8
五、詳細(xì)設(shè)計(jì)..........................................................................................................9 1.主函數(shù)模塊.......................................................................................................9 2.對(duì)路徑權(quán)值進(jìn)行排序.....................................................................................10
六、調(diào)試與分析....................................................................................................14
七、測試結(jié)果........................................................................................................17
軟件121 程猛 201200834122 2
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告
八、設(shè)計(jì)心得體會(huì)................................................................................................17
附錄（源代碼）18
軟件121 程猛 201200834122 3
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告
摘要
最小生成樹是數(shù)據(jù)結(jié)構(gòu)中圖的一種重要應(yīng)用，在圖中對(duì)于n個(gè)頂點(diǎn)的連通網(wǎng)可以建立許多不同的生成樹，最小生成樹就是在所有生成樹中總的代價(jià)最小的生成樹。本課程設(shè)計(jì)是以鄰接矩陣作為圖的存儲(chǔ)結(jié)構(gòu),分別采用Prim和Kruskal算法求最小生成樹。Kruskal算法和Prim算法是求最小生成樹的常用算法它們分別適用于稠密圖和稀疏圖。最小生成樹的應(yīng)用非常的廣，如礦井通風(fēng)設(shè)計(jì)和改造最優(yōu)化方面以及如何搭建最短的網(wǎng)絡(luò)線纜, 構(gòu)建造價(jià)最低的通訊網(wǎng)絡(luò)。
一、引言
本課程設(shè)計(jì)我們要解決的問題是圖最小生成樹問題。要用到圖的先相關(guān)數(shù)據(jù)結(jié)構(gòu)和求最小生成樹的兩種數(shù)據(jù)結(jié)構(gòu)算法普里姆算法和克魯斯卡爾算法，以及儲(chǔ)存圖的邊和點(diǎn)的鄰接矩陣。
本課程設(shè)計(jì)要解決的問題構(gòu)造連通網(wǎng)的最小生成樹 ,我們首先要做的是創(chuàng)建一個(gè)鄰接矩陣，用以來存儲(chǔ)圖，然后我們要想好怎樣利用普里姆算法和克魯斯卡爾算法來構(gòu)造最小生成樹。把這兩種算法寫入主函數(shù)，調(diào)試好程序。最后寫好報(bào)告。
二、設(shè)計(jì)題目 1.問題描述
若要在n個(gè)城市之間建設(shè)通信網(wǎng)絡(luò)，只需要假設(shè)n-1條線路即可。如何以最低的經(jīng)濟(jì)代價(jià)建設(shè)這個(gè)通信網(wǎng)，是一個(gè)網(wǎng)的最小生成樹問題。
2.系統(tǒng)要求
利用克魯斯卡爾算法求網(wǎng)的最小生成樹。利用普里姆算法求網(wǎng)的最小生成樹。要求輸出各條邊及它們的權(quán)值。
軟件121 程猛 201200834122 4
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告
3.測試數(shù)據(jù)
4.實(shí)現(xiàn)提示
通信線路一旦建成，必然是雙向的。因此，構(gòu)造最小生成樹的網(wǎng)一定是無向圖。設(shè)圖的頂點(diǎn)數(shù)不超過30個(gè)，并為簡單起見，網(wǎng)中邊的權(quán)值設(shè)成小于100的整數(shù)，100則表示沒有路徑。
5.參考文獻(xiàn)
[1] 嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學(xué)出版社,1997.[2] 譚浩強(qiáng).C程序設(shè)計(jì)（第三版）[M].北京：清華大學(xué)出版社，2005.1.[3] 二霍紅衛(wèi)算法設(shè)計(jì)與分析〔」西安西安電子科技大學(xué)出版社，2005.113-127.[4] 陳杰.計(jì)算機(jī)專業(yè)課程設(shè)計(jì)中的需求分析[J].集美大學(xué)學(xué)報(bào)，2009，10(2)：89—92.[5] 高一凡.數(shù)據(jù)結(jié)構(gòu)算法實(shí)現(xiàn)及解析[M ].西安:西安電子科技大學(xué)出版軟件121 程猛 201200834122
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告
社, 2002 6.運(yùn)行環(huán)境
VC++6.0
三、需求分析
1.如何選擇存儲(chǔ)結(jié)構(gòu)去建立一個(gè)帶權(quán)網(wǎng)絡(luò)。
此問題的關(guān)鍵在于如何實(shí)現(xiàn)PRIM算法和Kruskal算法，實(shí)現(xiàn)的過程中如何得到構(gòu)成最小生成樹的所有頂點(diǎn)，此外輸出也是一個(gè)關(guān)鍵問題所在，在此過程中經(jīng)過了多次調(diào)試。
2.如何在所選存儲(chǔ)結(jié)構(gòu)下輸出這個(gè)帶權(quán)網(wǎng)絡(luò)。
將圖中的所有頂點(diǎn)存儲(chǔ)到一個(gè)一維數(shù)組中，通過一個(gè)二維數(shù)組用鄰接矩陣連實(shí)現(xiàn)對(duì)各邊權(quán)值的存儲(chǔ)
3.如何實(shí)現(xiàn)PRIM算法和Kruskal算法的功能。
首先我們對(duì)prim算法的問題進(jìn)行大致的概要分析：
假設(shè)N=（V，{E}）是連通網(wǎng)，TE是N上最小生成樹中邊的集合。算法從U={u0}（u0∈V），TE={}開始，重復(fù)執(zhí)行下述操作：在所有u∈U，v∈V-U的邊（u，v）∈E中找一條代價(jià)最小的邊（u0,v0）并入集合TE，同時(shí)v0并入U(xiǎn)，直至U=V為止。此時(shí)TE中必有n-1條邊，則T=(V,{TE})為N的最小生成樹。
克魯斯卡爾算法從另一種途徑求網(wǎng)的最小生成樹：
假設(shè)連通網(wǎng)N=(V,{E})，則另最小生成樹的初始狀態(tài)為只有n個(gè)頂點(diǎn)而無邊的非連通圖T=(V,{})，圖中每個(gè)頂點(diǎn)自成一個(gè)連通分量。在E中選擇代價(jià)最小的邊若該邊依附的頂點(diǎn)落在T中不同的連通分量上，則將此邊加入到T中，否則舍去此邊而選擇下一條代價(jià)最小的邊。以此類推直至T中的軟件121 程猛 201200834122
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告
所有頂點(diǎn)都在同一連通分量上為止。
4.如何從每個(gè)頂點(diǎn)開始找到所有的最小生成樹的頂點(diǎn)。
對(duì)于prim算法從圖的點(diǎn)集中任取一個(gè)頂點(diǎn)作為起始頂點(diǎn)，然后找到依附于該頂點(diǎn)的所有邊選取權(quán)值最小的，依次找下去直至圖中所有頂點(diǎn)都在一個(gè)點(diǎn)集中為止。對(duì)于克魯斯卡爾算法則通過對(duì)權(quán)值進(jìn)行排序找出權(quán)值最小的頂點(diǎn)和邊并把該邊的頂點(diǎn)并入點(diǎn)集之中。
5.如何輸出最小生成樹的邊及其權(quán)值。
通過訪問數(shù)組來實(shí)現(xiàn)對(duì)最小生成樹邊和權(quán)值的輸出。
四、概要設(shè)計(jì)
1、設(shè)定圖的抽象數(shù)據(jù)類型: ADT Graph{ 數(shù)據(jù)對(duì)象V:V是具有相同特性的數(shù)據(jù)元素的集合,稱為點(diǎn)集.數(shù)據(jù)關(guān)系R: R={VR} VR={(v,w)|v,w屬于V,(v,w)表示v和w之間存在的路徑} 基本操作P: CreatGraph(&G,V,VR)初始條件:V是圖的頂點(diǎn)集,VR是圖中弧的集合.操作結(jié)果:按V和VR是定義構(gòu)造圖G.Sort(edge* ,MGraph *)初始條件: 圖G存在，各邊權(quán)值已知； 操作結(jié)果:對(duì)權(quán)值進(jìn)行排序； Find(int *, int)初始條件:前者為已存在的集合，后者為集合中的元素； 操作結(jié)果:查找函數(shù)，確定后者所屬子集； Swapn(edge *, int, int)初始條件: 圖G存在，各邊權(quán)值已知； 操作結(jié)果:交換某兩個(gè)邊的權(quán)值；
軟件121 程猛 201200834122
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告
2.圖的存儲(chǔ)結(jié)構(gòu)
typedef struct {
int vexnum,arcnum;}ALGraph;typedef struct //邊的結(jié)構(gòu)體定義 {
int begin,end;//邊的開始和結(jié)束頂點(diǎn)
int cost;//權(quán)值 }EDGE;typedef struct {
int edges[max][max];//
int n,e;}MGraph;3.流程圖
軟件121 程猛 201200834122
數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告
五、詳細(xì)設(shè)計(jì)
在該函數(shù)中有6個(gè)模塊，分別是主函數(shù)模塊、路徑權(quán)值進(jìn)行排序、交換頂點(diǎn)及權(quán)值模塊、判斷是否回環(huán)、prim算法的實(shí)現(xiàn)、Kruskal算法的實(shí)現(xiàn)。
1.主函數(shù)模塊
ALGraph G;MGraph G2;int v,i,j;char a;do {
system(“cls”);
cout<<“t***********************************nn”;
cout<<“t
克魯斯卡爾
n”;
cout<<“t
普
里
姆
n”;
cout<<“t
退
出
nn”;
cout<<“t***********************************n”;
cout<<“請(qǐng)輸入序號(hào)：”;
cin>>a;
switch(a)
{
case '1': MiniSpanTree_Kruskal(G);system(“pause”);break;
case '2': cout<<“請(qǐng)輸入結(jié)點(diǎn)數(shù)：”;
cin>>G2.n;
for(j=1;j<=G2.n;j++)
{
cout<<“請(qǐng)輸入第”< for(i=1;i<=G2.n;i++) cin>>G2.edges[j][i]; } cout<<“請(qǐng)輸入開始頂點(diǎn):”; cin>>v; MiniSpanTree_PRTM(G2,v);system(“pause”);break;軟件121 程猛 201200834122 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 default : break; } }while(a!='3');return 0; 該模塊包含菜單的設(shè)計(jì)以及通過一個(gè)switch語句來實(shí)現(xiàn)對(duì)prim算法和Kruskal算法的實(shí)現(xiàn)。進(jìn)入主菜單后選擇相應(yīng)的序號(hào)執(zhí)行相應(yīng)的操作，每進(jìn)行一步后，按任意鍵繼續(xù)進(jìn)行下一個(gè)操作可重復(fù)執(zhí)行。 2.對(duì)路徑權(quán)值進(jìn)行排序 void Sort(EDGE *edges,ALGraph G)//對(duì)帶權(quán)路徑從小到大排序 { int i,j;for(i=1;i<=G.arcnum;i++)for(j=i;j<=G.arcnum;j++)if(edges[i].cost>edges[j].cost)Swapn(edges,i,j);} 在圖中找到權(quán)值最小的邊 3.交換頂點(diǎn)及權(quán)值 void Swapn(EDGE *edges,int i,int j)// 交換的兩個(gè)頂點(diǎn)及權(quán)值 { int temp;temp=edges[i].begin;edges[i].begin=edges[j].begin;edges[j].begin=temp;temp=edges[i].end;edges[i].end=edges[j].end;edges[j].end=temp;temp=edges[i].cost;edges[i].cost=edges[j].cost;edges[j].cost=temp;軟件121 程猛 201200834122 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 } 該模塊主要用于Kruskal算法，找到圖中權(quán)值最小的一條邊，然后交換它們的頂點(diǎn)和權(quán)值。 4.判斷是否回環(huán) int Find(int *parents,int f)//判斷是否形成環(huán) { while((parents[f])>0&&(f!=parents[f]))f=parents[f];return f;} 在Kruskal算法中初始parents[]為0來設(shè)置訪問未訪問標(biāo)志，以此來判斷圖是否成環(huán)。 5.prim算法的實(shí)現(xiàn) void MiniSpanTree_PRTM(MGraph &G,int v){ int closedge[max];int lowcost[max];int i,j,k,min;for(i=1;i<=G.n;i++){ lowcost[i]=G.edges[v][i]; closedge[i]=v;} for(i=1;i min=INF; for(j=1;j<=G.n;j++) if(lowcost[j]!=0&&lowcost[j] { min=lowcost[j]; k=j; } 軟件121 程猛 201200834122 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 } } printf(“邊(%d,%d)權(quán)為:%dn”,closedge[k],k,min);lowcost[k]=0;for(j=1;j<=G.n;j++)if(G.edges[k][j]!=0&&G.edges[k][j] void MiniSpanTree_Kruskal(ALGraph &G)//MiniSpanTree_Kruskal()函數(shù)實(shí)現(xiàn) { int i,s,v1,v2,value,bnf,edf; int parents[MAX_VERTEX_NUM]; EDGE edges[MAX_VERTEX_NUM]; cout< cin>>G.vexnum; //輸入頂點(diǎn)數(shù) cout<<“請(qǐng)輸入邊數(shù): ”; cin>>G.arcnum; //輸入邊數(shù) cout<<“請(qǐng)輸入(V1和V2), 例如:(V1=1,V2=3),(V1=2,V2=4)...”; cout< //輸入arc(v1,v2) for(i=1;i<=G.arcnum;++i) { cout< cin>>v1; //輸入頭頂點(diǎn) cout<<“請(qǐng)輸入第 ”< cin>>v2; //輸入尾頂點(diǎn) cout<<“請(qǐng)輸入第 ”< : ”; cin>>value; //輸入邊的權(quán)值 edges[i].begin=v1; edges[i].end=v2; while(v1<1||v1>G.vexnum||v2<1||v2>G.vexnum) //如果輸入的非法，重新輸入 { 軟件121 程猛 201200834122 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 cout<<“輸入不合法，請(qǐng)重新輸入！”; cout< cin>>v1; cout<<“請(qǐng)輸入第 ”< cin>>v2; cout<<“請(qǐng)輸入第 ”< : ”; cin>>value; edges[i].begin=v1; edges[i].end=v2; } edges[i].cost=value;} Sort(edges,G); //調(diào)用Sort()函數(shù) cout<<“按照排列好的序列逐個(gè)輸出權(quán)值”< //初始化array parents[] cout< for(i=1,s=1;s<=G.vexnum&&i<=G.arcnum;i++) { bnf=Find(parents,edges[i].begin); edf=Find(parents,edges[i].end); if(bnf!=edf) { parents[bnf]=edf; cout< //輸出最小生成樹 cout< cout< s++; } } } 軟件121 程猛 201200834122 13 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 六、調(diào)試與分析 測試數(shù)據(jù)如下圖 求該圖的最小生成樹 1.進(jìn)入主頁面 2.利用克魯斯卡爾算法求最小生成樹 選擇序號(hào)1使用克魯斯卡爾算法求圖的最小生成樹。 軟件121 程猛 201200834122 14 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 輸入每條邊的頂點(diǎn)和權(quán)值 對(duì)權(quán)值進(jìn)行排序，并且輸出最小生成樹。 軟件121 程猛 201200834122 15 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 3.利用prim算法求最小生成樹 選擇序號(hào)2用prim算法求最小生成樹。通過一個(gè)n階的鄰接矩陣來實(shí)現(xiàn)圖的輸入 輸入起始頂點(diǎn)然后輸出最小生成樹的各邊及其每一條邊的權(quán)值。 4.退出程序 選擇序號(hào)3退出程序 軟件121 程猛 201200834122 16 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 七、測試結(jié)果 克魯斯卡爾算法求得的最小生成樹為3?5?2?1?4?6 Prim算法求得的最小生成樹為1?2?5?3?4?6 八、設(shè)計(jì)心得體會(huì) 在我的努力下，課程設(shè)計(jì)終于完成，由于我們對(duì)數(shù)據(jù)結(jié)構(gòu)和c語言不是很了解，有時(shí)忽略了一些關(guān)鍵的細(xì)節(jié)，使得在編寫程序的過程中出現(xiàn)了一些問題。對(duì)于打字有時(shí)粗心導(dǎo)致出現(xiàn)一些難以發(fā)現(xiàn)的小錯(cuò)誤，在我的耐心，細(xì)致的調(diào)試下最終使得程序能夠運(yùn)行，課程設(shè)計(jì)圓滿完工。 軟件121 程猛 201200834122 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 問題一：求出圖中的最小值 現(xiàn)象：求出的最小值是0 原因：圖中沒有連通的兩個(gè)頂點(diǎn)之間的權(quán)值賦值為0 問題二：求最小生成樹時(shí)，else語句需再調(diào)用一個(gè)函數(shù) 現(xiàn)象：對(duì)某些二叉樹能求出最小生成樹，但不能普遍適應(yīng) 原因：對(duì)于找最小生成樹邊的各種可能沒有考慮全面，代碼才沒有廣泛的適應(yīng)性 問題三：兩個(gè)頂點(diǎn)之間的邊是否是最小生成樹的邊 現(xiàn)象：代碼的功能不能分辨出是否是最小生成樹的邊 原因：把簡單的代碼寫的很復(fù)雜，從而雜亂無章出現(xiàn)錯(cuò)誤。 在課設(shè)過程中，遇到許多問題，通過查閱資料和課本。是我對(duì)數(shù)據(jù)結(jié)構(gòu)有了更進(jìn)一步的認(rèn)識(shí)。當(dāng)然，這中間也有其他人的幫助。我的同學(xué)，以及指導(dǎo)老師都給我提出了非常寶貴的意見。通過與同學(xué)和老師的交流，使我找到了數(shù)據(jù)結(jié)構(gòu)這門課程的學(xué)習(xí)方法。但是，我感覺這不僅僅是數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)方法，他或許就是學(xué)習(xí)軟件工程這門專業(yè)的方法，那就是多動(dòng)手。的確如此，對(duì)于一個(gè)算法，你知道它的算法思想和用計(jì)算機(jī)實(shí)現(xiàn)它卻是另外一回事。這門課程，不僅需要我們用心去理解每一種算法的思想，更需要我們?nèi)?dòng)手來實(shí)現(xiàn)它。 附錄（源代碼） #include “iostream” using namespace std;#define MAX_VERTEX_NUM 30 //定義最大頂點(diǎn)數(shù) #define MAXQSIZE 100 #define max 20 #define INF 10 typedef struct { int vexnum,arcnum;}ALGraph; typedef struct //邊的結(jié)構(gòu)體定義 { 軟件121 程猛 201200834122 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 int begin,end;//邊的開始和結(jié)束頂點(diǎn) int cost;//權(quán)值 }EDGE; ////////////////////////////// typedef struct { int edges[max][max];// int n,e;}MGraph; void Swapn(EDGE *edges,int i,int j); // 交換的兩個(gè)頂點(diǎn)及權(quán)值 void Sort(EDGE *edges,ALGraph G); //對(duì)帶權(quán)路徑從小到大排序 int Find(int *parents,int f); //判斷是否形成環(huán) void MiniSpanTree_Kruskal(ALGraph &G);//MiniSpanTree_Kruskal()函數(shù)實(shí)現(xiàn) void Swapn(EDGE *edges,int i,int j)// 交換的兩個(gè)頂點(diǎn)及權(quán)值 { int temp;temp=edges[i].begin;edges[i].begin=edges[j].begin;edges[j].begin=temp;temp=edges[i].end;edges[i].end=edges[j].end;edges[j].end=temp;temp=edges[i].cost;edges[i].cost=edges[j].cost;edges[j].cost=temp;} void Sort(EDGE *edges,ALGraph G)//對(duì)帶權(quán)路徑從小到大排序 { 軟件121 程猛 201200834122 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 int i,j;for(i=1;i<=G.arcnum;i++)for(j=i;j<=G.arcnum;j++)if(edges[i].cost>edges[j].cost)Swapn(edges,i,j);} int Find(int *parents,int f)//判斷是否形成環(huán) { while((parents[f])>0&&(f!=parents[f]))f=parents[f];return f;} void MiniSpanTree_Kruskal(ALGraph &G)//MiniSpanTree_Kruskal()函數(shù)實(shí)現(xiàn) { int i,s,v1,v2,value,bnf,edf; int parents[MAX_VERTEX_NUM]; EDGE edges[MAX_VERTEX_NUM]; cout< cin>>G.vexnum; //輸入頂點(diǎn)數(shù) cout<<“請(qǐng)輸入邊數(shù): ”; cin>>G.arcnum; //輸入邊數(shù) cout<<“請(qǐng)輸入(V1和V2), 例如:(V1=1,V2=3),(V1=2,V2=4)...”; cout< //輸入arc(v1,v2) for(i=1;i<=G.arcnum;++i) { cout< cin>>v1; //輸入頭頂點(diǎn) cout<<“請(qǐng)輸入第 ”< cin>>v2; //輸入尾頂點(diǎn) cout<<“請(qǐng)輸入第 ”< : ”; cin>>value; //輸入邊的權(quán)值 軟件121 程猛 201200834122 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 edges[i].begin=v1; edges[i].end=v2; while(v1<1||v1>G.vexnum||v2<1||v2>G.vexnum) //如果輸入的非法，重新輸入 { cout<<“輸入不合法，請(qǐng)重新輸入！”; cout< cin>>v1; cout<<“請(qǐng)輸入第 ”< cin>>v2; cout<<“請(qǐng)輸入第 ”< : ”; cin>>value; edges[i].begin=v1; edges[i].end=v2; } edges[i].cost=value;} Sort(edges,G); //調(diào)用Sort()函數(shù) cout<<“按照排列好的序列逐個(gè)輸出權(quán)值”< //初始化array parents[] cout< for(i=1,s=1;s<=G.vexnum&&i<=G.arcnum;i++) { bnf=Find(parents,edges[i].begin); edf=Find(parents,edges[i].end); if(bnf!=edf) { parents[bnf]=edf; cout< //輸出最小生成樹 cout< cout< s++; } } 軟件121 程猛 201200834122 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 } /////////////////////// void MiniSpanTree_PRTM(MGraph &G,int v){ int closedge[max];int lowcost[max];int i,j,k,min;for(i=1;i<=G.n;i++){ lowcost[i]=G.edges[v][i]; closedge[i]=v;} for(i=1;i min=INF; for(j=1;j<=G.n;j++) if(lowcost[j]!=0&&lowcost[j] { min=lowcost[j]; k=j; } printf(“邊(%d,%d)權(quán)為:%dn”,closedge[k],k,min); lowcost[k]=0; for(j=1;j<=G.n;j++) if(G.edges[k][j]!=0&&G.edges[k][j] { lowcost[j]=G.edges[k][j]; closedge[j]=k; } } } int main(){ ALGraph G;軟件121 程猛 201200834122 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 MGraph G2;int v,i,j;char a;do { system(“cls”); cout<<“t***********************************nn”; cout<<“t 克魯斯卡爾 n”; cout<<“t 普 里 姆 n”; cout<<“t 退 出 nn”; cout<<“t***********************************n”; cout<<“請(qǐng)輸入序號(hào)：”; cin>>a; switch(a) { case '1': MiniSpanTree_Kruskal(G);system(“pause”);break; case '2': cout<<“請(qǐng)輸入結(jié)點(diǎn)數(shù)：”; cin>>G2.n; for(j=1;j<=G2.n;j++) { cout<<“請(qǐng)輸入第”< for(i=1;i<=G2.n;i++) cin>>G2.edges[j][i]; } cout<<“請(qǐng)輸入開始頂點(diǎn):”; cin>>v; MiniSpanTree_PRTM(G2,v);system(“pause”);break; default : break; } }while(a!='3');return 0;} 軟件121 程猛 201200834122 23 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 散列表的應(yīng)用:插隊(duì)買票 專業(yè) 計(jì)算機(jī)科學(xué)與技術(shù)（網(wǎng)絡(luò)技術(shù)） 金玲 計(jì)算機(jī)131 1310704114 張靜林 2015年1月23日 學(xué)生姓名 班學(xué)級(jí) 號(hào) 指導(dǎo)教師 完成日期 目錄概述……………………………………………………………………………………1 1.1 課程設(shè)計(jì)目的……………………………………………………………………….1 1.2 課程設(shè)計(jì)內(nèi)容……………………………………………………………………….1 2 系統(tǒng)需求分析……………………………………………………………………….1 2.1 主體功能…………………………………………………………………………....2 3系統(tǒng)概要設(shè)計(jì)…………………………………………………………………………2 3.1 系統(tǒng)流程圖………………………………………………………………………….2 4 系統(tǒng)詳細(xì)設(shè)計(jì)…………………………………………………………………………3 5 測試……………………………………………………………………………………5 5.1 測試方案…………………………………………………………………………….5 5.2 測試結(jié)果…………………………………………………………………………….5 6 小結(jié)……………………………………………………………………………………5 參考文獻(xiàn)…………………………………………………………………………………5 附錄………………………………………………………………………………………7 附錄1 源程序清單……………………………………………………………………...7 概述 1.1 課程設(shè)計(jì)目的 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)是為數(shù)據(jù)結(jié)構(gòu)課程獨(dú)立開設(shè)的實(shí)踐性教學(xué)環(huán)節(jié)。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)對(duì)于鞏固數(shù)據(jù)結(jié)構(gòu)知識(shí)，加強(qiáng)學(xué)生的實(shí)際動(dòng)手能力和提高學(xué)生綜合素質(zhì)是十分必要的。課程設(shè)計(jì)的目的： 1．要求學(xué)生達(dá)到熟練掌握C語言的基本知識(shí)和技能。 2．了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力。3．提高程序設(shè)計(jì)和調(diào)試能力。學(xué)生通過上機(jī)實(shí)習(xí)，驗(yàn)證自己設(shè)計(jì)的算法的正確性。學(xué)會(huì)有效利用基本調(diào)試方法，迅速找出程序代碼中的錯(cuò)誤并且修改。 4．培養(yǎng)算法分析能力。分析所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度，進(jìn)一步提高程序設(shè)計(jì)水平。 5．初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測試等基本方法和技能。 1.2課程設(shè)計(jì)內(nèi)容 本課程設(shè)計(jì)的任務(wù)是寫一個(gè)程序模擬這種情況。每個(gè)隊(duì)伍都允許插隊(duì)。如果你在排隊(duì)，有一個(gè)以上的朋友要求插隊(duì)，則你可以安排他們的次序。每次一個(gè)人入隊(duì)，并且如果這個(gè)入隊(duì)的人發(fā)現(xiàn)隊(duì)伍中有自己的朋友，則可以插入到這個(gè)朋友的后面；當(dāng)隊(duì)伍中的朋友不止一個(gè)的時(shí)候，這個(gè)人會(huì)排在最后一個(gè)朋友的后面；如果隊(duì)伍中沒有朋友，則他只能夠排在這個(gè)隊(duì)伍的最后面。每一個(gè)入隊(duì)的人都先進(jìn)行上述的判斷。當(dāng)隊(duì)伍前面的人買到車票之后，依次出隊(duì)。系統(tǒng)需求分析 2.1 主體功能 程序從“input.txt”文件讀入測試用例，一個(gè)文件可包含多個(gè)測試用例。每個(gè)用例的第一行是朋友組的數(shù)目n（1<=n<=1000)。對(duì)于一個(gè)朋友組以朋友的數(shù)目j（1<=j<=1000）開始，由朋友的個(gè)數(shù)以及他們的名字組成，一個(gè)空格后接該組朋友的名字，以空格分開，并且每個(gè)人的名字都不同。每個(gè)名字不超過四個(gè)字母，由{A，B，...，Z，a，b，...，z}組成。一個(gè)朋友組最多有1000個(gè)人，每個(gè)人只屬于一個(gè)朋友組。n=0時(shí)，測試數(shù)據(jù)結(jié)束。 下面是一些具體命令：.ENQUEUE——X入隊(duì);.DEQUEUE——排隊(duì)頭的人買票，離開隊(duì)伍，即出隊(duì)；.STOP——一個(gè)測試用例結(jié)束。 測試結(jié)果輸出到“output.txt”文件中。每個(gè)測試用例第一行輸出“Scenario#k”，k是測試用例的序號(hào)（從1開始）。對(duì)每一個(gè)出隊(duì)命令，輸出剛買票離開隊(duì)伍的人名。兩個(gè)測試試用例 之間隔一空行，最后一個(gè)用例結(jié)束不輸出空行。系統(tǒng)概要設(shè)計(jì) 3.1 系統(tǒng)流程圖 系統(tǒng)詳細(xì)設(shè)計(jì) 本題目主要解決兩個(gè)問題：一是怎么存放和查找大量數(shù)據(jù)（主要是姓名）；二是怎么操作“ENQUEUE”和“DEQUEUE”命令。 用散列表來存放和查找數(shù)據(jù)。由于最多有1000個(gè)朋友組，每組最多有1000人，使用平方探測法解決沖突，則表的大小是2*（1000*1000），所以選擇TableSize=2000003（2000003是大于2000000的最小素?cái)?shù)）。同一個(gè)組內(nèi)的都是朋友，所以每個(gè)人除了記錄他的名字name，還要記錄他屬于哪個(gè)組group，另外用info來表示該單元是否被占用，數(shù)據(jù)結(jié)構(gòu)如圖4.1所示。散列函數(shù)是根據(jù)Honer法則計(jì)算一個(gè)以64為階的多項(xiàng)式，如圖4.2所示。沖突解決方法采用平方探測法，如圖4.3所示。 #define TabSize 2000003 typedef struct hashtab *PtrToHash;struct hashtab /*散列表數(shù)據(jù)結(jié)構(gòu)*/ { char name[5]; /*名字*/ int group; /*屬于哪個(gè)朋友組*/ char info; /*標(biāo)志位，該單元是否被占用*/ };圖4.1數(shù)據(jù)結(jié)構(gòu)：散列表 Int Hash(char *key,int TableSize){ Int HashVal=0; While(key!=NULL) HashVal=(HashVal<<6)+*key; Return HashVal%TableSize;} 圖4.2散列函數(shù) Long int Find(PtrToHash hash,char *c){ key=c; CurrentPos=Hash(key,TableSize); CollisionNum=0; While((單元被占用)and(單元內(nèi)的名字與查找的名字不同)) { CurrentPos+=2*(++CollisionNum)-1; If(CurrentPos>=TabSize) CurrentPos=TabSize; } Return CurrentPos;} 圖4.3用平方探測法解決沖突 第二個(gè)問題是關(guān)于怎么操作“ENQUEUE”和“DEQUEUE”命令。這可以用隊(duì)列來模擬。由于有插隊(duì)現(xiàn)象的存在，不能單純的用一個(gè)數(shù)組來表示隊(duì)列，因?yàn)檫@樣的話，插入一個(gè)朋友，則他后面的人都要往后移一個(gè)單位，刪除一個(gè)人，則他后面的人都要前移一個(gè)，會(huì)降低效率。所以，采用一個(gè)Index標(biāo)記來表示當(dāng)前元素的后繼元素，最后一個(gè)單元的后繼元素是第0個(gè)，形成環(huán)，數(shù)據(jù)結(jié)構(gòu)如圖4.4所示。不用鏈表是因?yàn)殒湵泶娣胖羔樢残枰臻g，并且鏈表插入、刪除的效率沒有數(shù)組高。 typedef struct Que *PtrToQue;struct Que /*隊(duì)列數(shù)據(jù)結(jié)構(gòu)*/ { long int HashVal; /*散列值*/ long int Index; /*在中的隊(duì)列序號(hào)*/ };圖4.4數(shù)據(jù)結(jié)構(gòu)：隊(duì)列 輸入ENQUEUE命令，如果隊(duì)伍里有朋友，則排在朋友后面；如果沒有朋友，則排在隊(duì)尾。入隊(duì)時(shí)，用一個(gè)數(shù)組記錄每個(gè)朋友組的最后一位，以便下一個(gè)朋友到來時(shí)排到他后面，這個(gè)數(shù)組被稱為“插隊(duì)數(shù)組”。 輸入DEQUEUE命令，則根據(jù)“先進(jìn)先出”，按照各個(gè)元素和它后繼元素的先后順序，每次刪除隊(duì)列重的第一個(gè)。程序結(jié)構(gòu)如圖4.5所示。 While(讀測試文件){ if(輸入”ENQUEUE”) { 讀入名字； 插入散列表； 插入隊(duì)列； } else if(輸入”DEQUEUE”) { 刪除隊(duì)列第一個(gè)名字； 將該名字輸出到文件； } else stop;} 圖4.5入隊(duì)、出隊(duì)操作 測試 5.1 測試方案 按輸入要求輸入正常測試數(shù)據(jù)，測試程序是否能正確解決問題，得到正確答案。應(yīng)注意邊界測試。例如，將n，j分別取為1的用例和n為1000的用例。n，j比較大時(shí)需寫程序生成測試用例。 不按輸入要求輸入數(shù)據(jù)，測試程序能否對(duì)輸入內(nèi)容進(jìn)行數(shù)據(jù)合法性檢測并進(jìn)行相應(yīng)的異常處理。例如，將n或j取為小于1或大于1000的數(shù)，名字超過4個(gè)字母等情況下的測試用例。5.2 測試結(jié)果 小結(jié) 在前面的學(xué)習(xí)過程中我們學(xué)到了很多知識(shí)而這次課程設(shè)計(jì)又是對(duì)我們所學(xué)的 一次總結(jié)，剛開始，可以說是沒有頭緒，于是就去圖書館找資料，找到了一些關(guān)于程序方面的，可這遠(yuǎn)遠(yuǎn)不夠，這只是小小的開始。我們必須掌握很多已學(xué)的知識(shí)才能很好的完成本次的課程設(shè)計(jì)。在這次課程設(shè)計(jì)中，總的感覺是我遇到了很多困難這主要是由于我編寫代碼的經(jīng)驗(yàn)不足，有時(shí)雖然是一個(gè)很小的問題但解決起來卻花費(fèi)了我不少的時(shí)間，值得欣慰的是，當(dāng)自己苦思冥想或者和其它同學(xué)一起探討把問題解決的時(shí)候我還是覺得獲益非淺，這就是在摸索中尋求到的知識(shí)。在設(shè)計(jì)時(shí)也免不了存在著些不足，所以在今后的學(xué)習(xí)中我會(huì)努力取得更大的進(jìn)步。雖然對(duì)著電腦做程序，有些累，可當(dāng)看到勞動(dòng)成果時(shí)，卻有另一番滋味。 參考文獻(xiàn) [1]范策，周世平，胡曉琨.《算法與數(shù)據(jù)結(jié)構(gòu)（C語言版）》[M].北京：機(jī)械工業(yè)出版社，2004 [2]嚴(yán)蔚敏.《數(shù)據(jù)結(jié)構(gòu)（C語言版）》.北京：清華大學(xué)出版社，2004 [3]許卓群，楊冬青，唐世渭，張銘.《數(shù)據(jù)結(jié)構(gòu)與算法》.北京：高等教育出版社，2004 [4]徐孝凱.《數(shù)據(jù)結(jié)構(gòu)實(shí)用教程（第二版）》.北京：清華大學(xué)出版社，2006 附錄 附錄1 源程序清單 #include /*散列表大小TabSize 是大于表最大空間的素?cái)?shù)*/ #define Max 1000001 /*隊(duì)列空間最大值*/ struct hashtab;typedef struct hashtab *PtrToHash;struct hashtab /*散列表數(shù)據(jù)結(jié)構(gòu)*/ { char name[5]; /*名字*/ int group; /*屬于哪個(gè)朋友組*/ char info; /*標(biāo)志位，該單元是否被占用*/ };struct Que;typedef struct Que *PtrToQue;struct Que /*隊(duì)列數(shù)據(jù)結(jié)構(gòu)*/ { long int HashVal; /*散列值*/ long int Index; /*在中的隊(duì)列序號(hào)*/ }; int hashedx=0; /*標(biāo)記元素是否已經(jīng)在散列表里*/ long int Find(PtrToHash hash,char *c)/*查找在散列表中的位置*/ { char *key;long int CurrentPos,CollisionNum; key=c;for(CurrentPos=0;*key;++key) /*散列函數(shù)，計(jì)算散列值*/ CurrentPos=(CurrentPos<<6)+*key;CurrentPos%=TabSize; /*散列值*/ CollisionNum=0;/*如果當(dāng)前單元被占用：單元內(nèi)的元素與當(dāng)前操作的名字不同，使用平方探測法解決沖突；與當(dāng)前操作的名字相同，則直接返回在散列中的位置*/ while((hash[CurrentPos].info)&&(strcmp(hash[CurrentPos].name,c))) { /*平方探測法*/ CurrentPos+=2*(++CollisionNum)-1; if(CurrentPos>=TabSize) CurrentPos-=TabSize;} if((hash[CurrentPos].info)&&(strcmp(hash[CurrentPos].name,c)==0)) /*元素已經(jīng)在散列表里*/ hashedx=1;else /*元素不在散列表里*/ hashedx=0;return CurrentPos;/*返回在散列表中的位置*/ } int main(){ long int Find(PtrToHash hash,char *c); /*查找在散列表中的位置*/ PtrToHash hash; /*散列表*/ PtrToQue queue; /*隊(duì)列*/ int *grouppos; /*記錄每個(gè)朋友組的最后一位，即插隊(duì)數(shù)組*/ int n; /*測試用例數(shù)目*/ int num; /*當(dāng)前測試用例序號(hào)*/ long int i,ii,j,key,temp;long int head,last; /*隊(duì)列的頭和尾*/ char c[8],tempc[8]; /*名字*/ FILE *fpin,*fpout; /*輸入、輸出文件指針*/ if(!(fpin=fopen(“input.txt”,“r”))) /*打開測試文件*/ { printf(“fopen error!”); /*文件打開錯(cuò)誤*/ return-1;} if(!(fpout=fopen(“output.txt”,“w”))) /*打開輸出文件*/ { printf(“fopen error!”); return-1;} hash=(PtrToHash)malloc(sizeof(struct hashtab)*TabSize);/*為散列表申請(qǐng)空間*/ queue=(PtrToQue)malloc(sizeof(struct Que)*Max);/*為隊(duì)列申請(qǐng)空間*/ grouppos=(int *)malloc(sizeof(int)*1000);/*申請(qǐng)空間記錄每個(gè)朋友組的最后一位*/ for(i=0,j=1;i queue[i].Index=j;queue[i-1].Index=0;/*最后一個(gè)單元的后繼單元是第0個(gè)，形成環(huán)*/ num=0;for(fscanf(fpin,“%d”,&n);n;fscanf(fpin,“%d”,&n))/*輸入當(dāng)前測試用例的朋友組數(shù)*/ { if(n<1||n>1000) /*處理異常輸入n*/ { fprintf(fpout,“n is out of rangen”); return-1; } num++; if(num!=1) /*兩個(gè)測試用例間輸入一空行*/ fprintf(fpout,“n”); for(i=0;i hash[i++].info=0; /*初始化散列表，標(biāo)記位置0*/ for(i=0;i /*對(duì)每一組朋友*/ { fscanf(fpin,“%d”,&j); /*當(dāng)前組里的人數(shù)*/ if(j<1||j>1000) /*處理異常輸入j*/ { fprintf(fpout,“j is out of rangen”); return-1; } for(;j;--j) { fscanf(fpin,“%s”,c); /*輸入名字*/ for(ii=0;ii tempc[ii]='
第二篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告