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

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

2、一實(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á)最小，其單4獨(dú)的每一條路徑都必須具有最小長度。2) 算法按照路徑長度的非降次序生成這些路徑。首先，生成一條到最近結(jié)點(diǎn)的最短路徑，然后，生成一條到第二近結(jié)點(diǎn)的最短路徑，等等。即只用求出從路徑 v0開始到 G 中其他所有結(jié)點(diǎn)的最短路徑長度

3、。假定 G中 n 個(gè)結(jié)點(diǎn)被標(biāo)記上 1 到 n,集合 S 作為一個(gè)數(shù)組存放，如果結(jié)點(diǎn) i 不在 S 中，那么 Si=0，如果在 S 中，那么 Si=1，假設(shè) COSTi,j是i,j的權(quán)，那么在邊i，j不在本錢鄰接矩陣時(shí)，就被置某個(gè)大數(shù)，這里用 N 表示，當(dāng) i=j 時(shí)，COSTi,j被置以 0。3 3程序源代碼程序源代碼#include #include #define N 1000void shortestPaths(int v,int *COST,int *DIST,int n);/最短路徑生成函數(shù)void output2(int *arr,int row,int col);/輸出本錢的鄰接

4、矩陣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; /* printf(本錢鄰接矩陣：n); output2(&COST00,7,7); */ /生成 0 號結(jié)點(diǎn)到

5、 1 至 6 號結(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;5 int pren;/pw記錄起始結(jié)點(diǎn)到結(jié)點(diǎn) w 的最短路徑中的 w 前一結(jié)點(diǎn) int u,num,i,w; int tv,td=0; /初始化：結(jié)點(diǎn) v 以外的結(jié)點(diǎn)未被選中，并更新路徑長度為 v 到

6、其它結(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; /更新路徑 for(w=1;w(DISTu+*(COST+u*n+w)6 DISTw=(DISTu+*(COST+u*n+w); prew=u;/更

7、新結(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 output2(int *a,int row,int col) int i,j; for(i=0;irow;i+) for(j=0;jcol;j+) if

8、(*(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+)7 if(*(arr+i)=N) printf( Nt); else printf(%3dt,*(arr+i); 4 4運(yùn)行演示運(yùn)行演示我用了書上的一個(gè)例子，它的本錢鄰接矩陣已直接存入程序中，它的帶權(quán)有向圖如下：V0V1V2V3V5V6V4207025503040555025105070 圖 2 帶權(quán)有向圖運(yùn)行結(jié)果如下所示：8圖 3 運(yùn)行結(jié)果圖二實(shí)驗(yàn)二二

9、實(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 所示。9圖 1 歸并文件流程圖2、設(shè)計(jì)方法貪心算法3、度量標(biāo)準(zhǔn)每次選出 k 個(gè)最小的文件歸并，將歸并后的結(jié)果作為新的文件參加待歸并的文件序列中，直到歸并完成。值得注意的是，由于所有的內(nèi)部點(diǎn)的度數(shù)必須為 k，因此，對于 n 取某些值，就不和 k 元?dú)w并樹相對應(yīng)。所以有必要引進(jìn)一定量的虛結(jié)點(diǎn)，每個(gè)虛結(jié)點(diǎn)賦值 0，這個(gè)虛結(jié)點(diǎn)的虛值，不會(huì)影響所產(chǎn)生度數(shù)為 k 的帶權(quán)外部路徑長度。3 3程序源代碼程序源代碼#include#include10#include#include

10、#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(sizeof(T); head-elem=0; /獲取文件數(shù) do printf(請輸入文件的個(gè)數(shù)(1):); scanf(%d,&num); while(num1,=%d):,num); scanf(%d,

11、&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=(rand()%MAX+1); head-elem+; printf(隨機(jī)生成的文件序列為：);11 outTable(head); /補(bǔ)充虛結(jié)點(diǎn) r=(k-1)-(num-1)%(k-1)%(k-1); while(he

12、ad-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 *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è)最小的文件歸并

13、if(kelem) i=-1; /取 k 個(gè)最小的文件 while(+inext; j=0; while(jelem) if(mini-elemcur-elem) mpre=cpre; mini=cur; 12 cpre=cur; cur=cur-next; j+; mpre-next=mini-next; head-elem-; /輸出歸并的 K 個(gè)文件的大小 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 *he