資源描述：
《實(shí)驗(yàn)13 快速排序11》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、實(shí)驗(yàn)13快速排序姓名：江婷班級(jí)：計(jì)科三班學(xué)號(hào)：09完成日期：2010/12/01一、需求分析1．本程序需要將n件任務(wù)按用時(shí)去從小到大排序，就可以得到任務(wù)依次的處理順序。當(dāng)有n件任務(wù)同時(shí)來臨時(shí)，每件任務(wù)需要用時(shí)ni，求讓所有任務(wù)等待的時(shí)間和最小的任務(wù)處理順序。2．從文件中讀入圖的信息。3．利用克魯斯卡爾算法求網(wǎng)的最小生成樹。4．以文本形式生成樹中各條邊以及他們的權(quán)值。5．構(gòu)造生成樹的網(wǎng)一定是無向網(wǎng)。并設(shè)頂點(diǎn)數(shù)不超過30個(gè)，邊權(quán)值為小于100的整數(shù)。6．根據(jù)克魯斯卡爾算法的特點(diǎn)，為便于選擇選擇權(quán)值小的邊，存儲(chǔ)結(jié)構(gòu)不選用鄰接矩陣和鄰接表，而是可以用存儲(chǔ)邊（帶權(quán)）的數(shù)組表示圖。二、概要
2、設(shè)計(jì)抽象數(shù)據(jù)類型最小生成樹的初始狀態(tài)為只有n個(gè)頂點(diǎn)而無邊的非連通圖，圖中每個(gè)頂點(diǎn)自成一個(gè)連通分量，所以要定義一個(gè)圖的抽象數(shù)據(jù)類型。ADTGraph{數(shù)據(jù)對(duì)象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。數(shù)據(jù)關(guān)系R：R={VR}VR={
3、v,wV且P(v,w),表示從v到w的弧，謂詞P(v,w)定義了弧的信息}基本操作P：StatusCreateDGraph(ALGraph&G，V,VR);//采用鄰接表存儲(chǔ)表示，構(gòu)造有向圖G（G.kind=DG）。intFirstAdjVex(G,v);//若G中存在頂點(diǎn)v,則返回該頂點(diǎn)在圖中位置;//否則返回
4、-1.StatusDeleteArc(&G,v,w);//在G中刪除弧。intFindInDegree(G,ndegree[]);//求頂點(diǎn)的入度。}ADTGraph生成樹T的每個(gè)連通分量可看成是一個(gè)等價(jià)類，則構(gòu)造T加入新的邊的過程類似于求等價(jià)類的過程，由此可以用MFSet類型來描述T，使構(gòu)造T的過程僅需O（eloge）的時(shí)間。ADTMFSet{數(shù)據(jù)對(duì)象：若設(shè)S是MFSet型的集合，則它由n(n>0)個(gè)子集S（i=1,2，…，n）構(gòu)成，每個(gè)子集的成員都是子界[-maxnumber,maxnumber]內(nèi)的整數(shù)；數(shù)據(jù)關(guān)系：=S基本操作：VoidInitial(&S,n,
5、)；操作結(jié)果：初始化操作。構(gòu)造一個(gè)由n個(gè)子集（每個(gè)子集只含單個(gè)成員x）構(gòu)成的集合S。Intfix_mfset(S,x);初始條件：S是已存在的集合，x是S中某個(gè)子集的成員。操作結(jié)果：查找函數(shù)。確定S中x所屬子集S。Statusmix_mfset(&S,i,j);初始條件：S和S是S中的兩個(gè)互不相交的非空集合。操作結(jié)果：歸并操作。將S和S中的一個(gè)并入另一個(gè)中。}ADTMFSet;算法的基本思想最小生成樹的MST性質(zhì)：假設(shè)N=（V，{E}）是一個(gè)連通網(wǎng)，U是頂點(diǎn)集V的一個(gè)非空子集。若（u,v）是一條具有最小權(quán)值（代價(jià)）的邊，其中uU,vV-U，則必存在一棵包含邊（u,v）的最小生成
6、樹。克魯斯卡爾算法思想：假設(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中所有頂點(diǎn)都在同一連通分量上為止。程序的流程程序由三個(gè)模塊組成：（1）輸入模塊：完成圖中邊數(shù)和頂點(diǎn)的輸入。（2）構(gòu)造最小生成樹并輸出模塊：實(shí)現(xiàn)最小生成樹的構(gòu)建，并將結(jié)果輸出到屏幕。三、詳細(xì)設(shè)計(jì)物理數(shù)據(jù)類型為便于實(shí)現(xiàn)查找和歸并操作，則ADTMFSet的樹應(yīng)采用雙親表示法存儲(chǔ)結(jié)構(gòu)，如下所示：
7、typedefPTreeMFSet;intfix_mfset(MFSetS,inti){//確定集合S中i所在子集，并將從i至根路徑上所有結(jié)點(diǎn)都變成根的孩子結(jié)點(diǎn)。if(i<1
8、
9、i>S.n)return-1;//i不屬于S中任一子集for(j=i;S.nodes[j].parent>0;j=S.nodes[j].parent);for(k=i;k!=j;k=t){t=S.nodes[k].parent;S.nodes[k].parent=j;}returnj;}//fix_mfsetStatusmix_mfset(MFSet&S,inti,intj){//S.nodes[i]和
10、S.nodes[j]分別為S的互不相交的兩個(gè)子集Si和Sj的根結(jié)點(diǎn)。//并求集Si并Sj.if(i<1
11、
12、i>S.n
13、
14、j<1
15、
16、j>S.n)returnERROR;if(S.nodes[i].parent>S.nodes[j].parent){//Si所含成員數(shù)比Sj少S.nodes[j].parent+=S.nodes[i].parent;S.nodes[i].parent=j;}else{S.nodes[i].parent+=S.nodes[j].parent;S.nodes[j].p
