華科算法實(shí)驗(yàn)報(bào)告

1、 . .頁腳. 課課 程程 實(shí)實(shí) 驗(yàn)驗(yàn) 報(bào)報(bào) 告告 課程名稱：課程名稱： 算法設(shè)計(jì)與分析算法設(shè)計(jì)與分析 專業(yè)班級(jí)：專業(yè)班級(jí)：計(jì)算機(jī)科學(xué)與技術(shù)計(jì)算機(jī)科學(xué)與技術(shù) 13xx13xx 班班學(xué)學(xué) 號(hào)：號(hào)： 姓姓 名：名： 指導(dǎo)老師：指導(dǎo)老師： 報(bào)告日期：報(bào)告日期： 2015-11-292015-11-29 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 . .頁腳. 目錄目錄一實(shí)驗(yàn)一一實(shí)驗(yàn)一 .3 31 1實(shí)驗(yàn)題目實(shí)驗(yàn)題目.3 32 2設(shè)計(jì)思路設(shè)計(jì)思路.3 33 3程序源代碼程序源代碼.4 44 4運(yùn)行演示運(yùn)行演示.7 7二實(shí)驗(yàn)二二實(shí)驗(yàn)二 .8 81 1實(shí)驗(yàn)題目實(shí)驗(yàn)題目.8 82 2設(shè)計(jì)思路設(shè)計(jì)思路.8 83

2、 3程序源代碼程序源代碼.9 94 4運(yùn)行演示運(yùn)行演示.1212 . .頁腳. 一實(shí)驗(yàn)一實(shí)驗(yàn)一一1 1實(shí)驗(yàn)題目實(shí)驗(yàn)題目單源最短路徑問題： 已知一個(gè) n 結(jié)點(diǎn)有向圖 G=(V,E)和邊的權(quán)函數(shù) c(e)，求由 G 中某指定結(jié)點(diǎn) v0 到其它各結(jié)點(diǎn)的最短路徑。假定邊的權(quán)值為正。2 2設(shè)計(jì)思路設(shè)計(jì)思路 貪心算法流程圖如圖 1：圖 1 生成最短路徑算法流程設(shè)計(jì)總方法：使用貪心算法求解。貪心方法：1) 度量標(biāo)準(zhǔn)生成的所有路徑長度之和作為度量標(biāo)準(zhǔn)。為了使這一量度達(dá)到最小，其單 . .頁腳. 獨(dú)的每一條路徑都必須具有最小長度。2) 算法按照路徑長度的非降次序生成這些路徑。首先，生成一條到最近結(jié)點(diǎn)的最短路徑，

3、然后，生成一條到第二近結(jié)點(diǎn)的最短路徑，等等。即只用求出從路徑 v0開始到 G 中其他所有結(jié)點(diǎn)的最短路徑長度。假定 G 中n 個(gè)結(jié)點(diǎn)被標(biāo)記上 1 到 n,集合 S 作為一個(gè)數(shù)組存放，如果結(jié)點(diǎn) i 不在 S 中，則Si=0，如果在 S 中，則 Si=1，若 COST（i,j）是（i,j）的權(quán)，則在邊（i，j）不在成本鄰接矩陣時(shí)，就被置某個(gè)大數(shù)，這里用 N 表示，當(dāng) i=j 時(shí)，COST（i,j）被置以 0。3 3程序源代碼程序源代碼#include #include #define N 1000void shortestPaths(int v,int *COST,int *DIST,int n);

4、/最短路徑生成函數(shù)void output2(int *arr,int row,int col);/輸出成本的鄰接矩陣void outArray1(int *arr,int n);/輸出更新后其它結(jié)點(diǎn)到起始結(jié)點(diǎn)的路徑長度int main() int COST77= 0,20,50,30, N, N, N, N, 0,25, N, N,70, N, N, N, 0,40,25,50, N, N, N, N, 0,55, N, N, N, N, N, N, 0,10,70, N, N, N, N, N, 0,50, N, N, N, N, N, N, 0 ; int DIST7; int v=0;

5、/* printf(成本鄰接矩陣：n); output2(&COST00,7,7); */ /生成 0 號(hào)結(jié)點(diǎn)到 1 至 6 號(hào)結(jié)點(diǎn)的最短路徑 shortestPaths(v,&COST00,DIST,7); return 0;void shortestPaths(int v,int *COST,int *DIST,int n)/G 是一個(gè) n 結(jié)點(diǎn)有向圖，它由其成本鄰接矩陣 COSTnn表示，DISTj被置以結(jié)點(diǎn) v到 /結(jié)點(diǎn) j 的最短路徑長度，這里 1=j=n;DISTv被置成 0 int Sn; . .頁腳. int pren;/pw記錄起始結(jié)點(diǎn)到結(jié)點(diǎn) w 的最短路徑中

6、的 w 前一結(jié)點(diǎn) int u,num,i,w; int tv,td=0; /初始化：結(jié)點(diǎn) v 以外的結(jié)點(diǎn)未被選中，并更新路徑長度為 v 到其它結(jié)點(diǎn)的初始成本 for(i=0;in;i+) Si=0; *(DIST+i)=*(COST+v*n+i); prei=0; Sv=1; DISTv=0; /更新路徑長度 for(num=1;numn;num+) /選擇距離結(jié)點(diǎn) v 最近的結(jié)點(diǎn) w for(w=1;wn;w+) if(Sw=0) td=DISTw; tv=w; break; for(w+;wDISTw) td=DISTw; tv=w; u=tv; Su=1; DISTu=td; /更新路徑

7、 for(w=1;w(DISTu+*(COST+u*n+w) . .頁腳. DISTw=(DISTu+*(COST+u*n+w); prew=u;/更新結(jié)點(diǎn) w 最短路徑并記錄 w 結(jié)點(diǎn)的上一結(jié)點(diǎn) /輸出第 num 次更新后的路徑長度 printf(n 第%d 次路徑:,num); output1(DIST,n); printf(nn); /輸出路徑 for(i=1;in;i+) printf(從 0 到%d,最短的路徑是：n,i); w=i; printf(%d-,w); while(prew!=v) w=prew; printf(%d-,w); printf(%dn,v); void ou

8、tput2(int *a,int row,int col) int i,j; for(i=0;irow;i+) for(j=0;jcol;j+) if(*(a+i*row)+j)=N) printf( Nt); else printf(%3dt,*(a+i*row)+j); puts(n); void output1(int *arr,int n) int i; for(i=0;in;i+) . .頁腳. if(*(arr+i)=N) printf( Nt); else printf(%3dt,*(arr+i); 4 4運(yùn)行演示運(yùn)行演示我用了書上的一個(gè)例子，它的成本鄰接矩陣已直接存入程序中，它

9、的帶權(quán)有向圖如下： 圖 2 帶權(quán)有向圖運(yùn)行結(jié)果如下所示：V0V1V2V3V5V6V4207025503040555025105070 . .頁腳. 圖 3 運(yùn)行結(jié)果圖二實(shí)驗(yàn)二二實(shí)驗(yàn)二1 1實(shí)驗(yàn)題目實(shí)驗(yàn)題目k 路歸并：每次同時(shí)歸并 k 個(gè)文件且使移動(dòng)次數(shù)最少。2 2設(shè)計(jì)思路設(shè)計(jì)思路1、流程圖總流程圖如圖 1 所示。 . .頁腳. 圖 1 歸并文件流程圖2、設(shè)計(jì)方法貪心算法3、度量標(biāo)準(zhǔn)每次選出 k 個(gè)最小的文件歸并，將歸并后的結(jié)果作為新的文件加入待歸并的文件序列中，直到歸并完成。值得注意的是，由于所有的內(nèi)部點(diǎn)的度數(shù)必須為 k，因此，對(duì)于 n 取某些值，就不和 k 元?dú)w并樹相對(duì)應(yīng)。所以有必要引進(jìn)一定

10、量的虛結(jié)點(diǎn)，每個(gè)虛結(jié)點(diǎn)賦值 0，這個(gè)虛結(jié)點(diǎn)的虛值，不會(huì)影響所產(chǎn)生度數(shù)為 k 的帶權(quán)外部路徑長度。3 3程序源代碼程序源代碼#include#include . .頁腳. #include#include#define MAX 100typedef int ElemType;typedef struct Table ElemType elem; struct Table *next;T;void outTable(T *head);void func(T *head,int k);int main() int num,k,r; T *head,*cur; head=(T *)malloc(siz

11、eof(T); head-elem=0; /獲取文件數(shù) do printf(請輸入文件的個(gè)數(shù)(1):); scanf(%d,&num); while(num1,=%d):,num); scanf(%d,&k); while(knum); /生成隨機(jī)序列 srand(time(NULL); cur=(T *)malloc(sizeof(T); head-next=cur; head-elem+; cur-elem=(rand()%MAX+1); while(head-elemnext=(T *)malloc(sizeof(T); cur=cur-next; cur-elem=(r

12、and()%MAX+1); head-elem+; printf(隨機(jī)生成的文件序列為：); . .頁腳. outTable(head); /補(bǔ)充虛結(jié)點(diǎn) r=(k-1)-(num-1)%(k-1)%(k-1); while(head-elemelem=0; cur-next=head-next; head-next=cur; head-elem+; if(r=0) printf(不用補(bǔ)充虛結(jié)點(diǎn)n); else printf(補(bǔ)充%d 個(gè)虛結(jié)點(diǎn):,r); outTable(head); /歸并 func(head,k); return 0;void func(T *head,int k) T *

13、mink,*mpre,*cur,*cpre; int i=0,j=1,times=(head-elem-1)/(k-1),t=times; while(times-0)/當(dāng) K 小于等于待歸并文件數(shù)時(shí)，取 K 個(gè)最小的文件歸并 if(kelem) i=-1; /取 k 個(gè)最小的文件 while(+inext; j=0; while(jelem) if(mini-elemcur-elem) mpre=cpre; mini=cur; . .頁腳. cpre=cur; cur=cur-next; j+; mpre-next=mini-next; head-elem-; /輸出歸并的 K 個(gè)文件的大小

14、 printf(第%d 次歸并:,t-times); i=0; while(ielem); i+; i=1; /歸并 K 個(gè)文件 while(ielem+=mini-elem; free(minj); i+; /將歸并 K 個(gè)文件得到的新文件加入節(jié)點(diǎn)中 min0-next=head-next; head-next=min0; head-elem+; /輸出歸并后的文件 printf(t 歸并后的文件為：); cur=head-next; i=head-elem; while(i-0) printf(%4d,cur-elem); cur=cur-next; printf(n); void outTable(T *h