算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

十十十十十十十十十十十十十十十十十十十*******************實(shí)踐教學(xué)a、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上、上vt>*******************蘭州理工大學(xué)計(jì)算機(jī)與通信學(xué)院2016年秋季學(xué)期算法與數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目：1.跳馬問題2.超市選址問題專業(yè)班級：軟件工程(1)班姓名：學(xué)號：1516270168指導(dǎo)教師：成 TOC\o"1-5"\h\z目錄 1\o"CurrentDocument"摘要 3\o"CurrentDocument"跳馬問題 3\o"CurrentDocument"采用類語言定義相關(guān)的數(shù)據(jù)類型 .4\o"CurrentDocument"算法設(shè)計(jì) 4\o"CurrentDocument"程序流程圖 .6\o"CurrentDocument"調(diào)試分析 6\o"CurrentDocument"測試結(jié)果 6\o"CurrentDocument"源代碼（帶注釋） .7\o"CurrentDocument"學(xué)校超市選址問題 9\o"CurrentDocument"采用類語言定義相關(guān)的數(shù)據(jù)類型 .9\o"CurrentDocument"算法設(shè)計(jì) 10\o"CurrentDocument"函數(shù)的調(diào)用關(guān)系圖 12調(diào)試分析 13\o"CurrentDocument"測試結(jié)果 13源代碼（帶注釋） 16總結(jié) 20參考文獻(xiàn) 21致謝 22摘要國際象棋中的跳馬問題是一個(gè)古老而著名的問題。跳馬問題也稱為騎士周游問題，是算法的設(shè)計(jì)中的經(jīng)典問題。如果有這樣一種走法，則稱所走的這條線為馬的周游路線。在8*8的方格棋盤中馬的行走規(guī)則從棋盤的某一方格出發(fā)，開始在棋盤上周游，如果能不重復(fù)地走遍棋盤上的每一個(gè)方格，這樣的一條周游路線在數(shù)學(xué)上被稱為國際象棋棋盤上馬的哈密爾頓鏈。本程序主要完成找出馬的哈密爾頓鏈并在棋盤上動態(tài)的標(biāo)注其行走的過程。關(guān)鍵詞：馬的遍歷，迭代，最少出口。校園超市選址用鄰接矩陣（或鄰接表）表示，主要功能有：校園平面圖接矩陣（鄰接表）的建立、路徑的查詢、從某一點(diǎn)到另一景的最短路徑查找、按查找出的最短路徑確定超市的地址、顯示輸出等功能。一般情況下，校園的道路是雙向通行的，可設(shè)校園平面圖是一無向網(wǎng)，邊表示路徑，邊上的權(quán)值存放路徑長度等相關(guān)信息。關(guān)鍵詞：弗洛伊德，鄰接矩陣，最短路徑。一.跳馬問題要求在64個(gè)國際象棋格子，任意位置放一個(gè)馬，如何不重復(fù)地把格子走完。采用類語言定義相關(guān)的數(shù)據(jù)類型#include<iostream.h>#include<stdio.h>voidmain(){intMovel[8]=(-2,-1,1,2,2,1,-1,-2):intMovev[8]={l,2,2,1,-1,-2,-2,-1}:intA[8][8];int1,v,11,vl,12,v2,m,n,s,b,d;算法設(shè)計(jì)for(intt=2;t<=64;t++)//開始馬的遍歷{b=8;for(intp=0;p<=7;p++)//判斷馬的路線，找出最短路線{ll=l+Movel[p];vl=v+Movev[p];if(11〉二0&&11〈二7&&v1>=0Mv1<=7&&A[11][vl]==0){d=0;for(intq=0;q<=7:q++){12=ll+Movel[q];v2=vl+Movev[q]:if(12>=0M12<=7Mv2>=0Mv2<=7MA[12][v2]==0)d++;if(b>=d)(b=d;s=p;}}}if(b<=8)(l+=Movel[s];v+=Movev[s];A[l][v]=t;}}〃打印出馬的路線，cout<<endl;printf(" ******************馬的路線********************\n");for(m=0;m<=7;m++)(printf(〃〃)；for(n=0;n<=7;n++)(printf("%6d",A[m][n]);}cout<<endl;}cout<<endl;

3.程序流程圖圖1.1程序流程圖調(diào)試分析在選課問題中，我自己寫的數(shù)組結(jié)果調(diào)試的時(shí)候，錯(cuò)誤很多，才明白計(jì)算機(jī)語言有自己特定的格式，數(shù)據(jù)結(jié)構(gòu)也有其特殊性；如果考慮不到的話那就無法通過編譯。所以我找了大量的資料和參考程序幫助我修改自己的錯(cuò)誤。測試結(jié)果輸入坐標(biāo)：（2,5），結(jié)果如下:請輸入馬在棋盤上的起始位置,中間用穿格隔尸］注意兩個(gè)數(shù)字均小于&）：25率字字牛牛津***********牛馬的路線字字牛牛******：**字字字**牛**26522375432045233S2542115526273653說44193524393247635828iS45162184313103；4033596482912155042171114930匕4960■■■ZGAYE■輸入起始位置（4,6），結(jié)果如下:二二_=跳馬|司題(64^)= = = = =_=清新入馬在棋盅上的起始位置,中間用空格隔開！注意兩個(gè)數(shù)字均小于力；46牢學(xué)常腳器品肆宰律牢翡描用**牛牢牢馬的路線斯稀用*零牢牢學(xué)常需*肆牛律學(xué)需翡稀用*&3342912工16211430116255281352173564335059541526103.15S615625IS53473545324960124694857442：40193746743942232853S432232041■ZGAMEera:源代碼(帶注釋)for(intt=2;t<=64;t++)//開始馬的遍歷(b=8;for(intp=0;p<=7;p++) //判斷馬的路線，找出最短路線(l1=l+Movel[p];v1=v+Movev[p];if(l1>=0&&l1<=7&&v1>=0&&v1<=7&&A[l1][v1]==0)(d=0;for(intq=0;q<=7;q++)(l2=l1+Movel[q];v2=v1+Movev[q];if(l2>=0&&l2<=7&&v2>=0&&v2<=7&&A[l2][v2]==0)d++;}if(b>=d)(b=d;s=p;}}}if(b<=8)(l+=Movel[s];v+=Movev[s];}}//打印出馬的路線，cout<<endl;printf(" ******************馬的路線********************\n")；for(m=0;m<=7;m++)(printf(〃〃)；for(n=0;n<=7;n++)(printf("%6d",A[m][n]);}cout<<endl;}cout<<endl;printf(〃==================GAMEOVER======================\n");}二.學(xué)校超市選址問題校園平面圖采用鄰接矩陣（或鄰接表）表示，主要功能有：校園平面圖鄰接矩陣（或鄰接表）的建立、路徑的查詢、從某一點(diǎn)到另一景的最短路徑查找、按查找出的最短路徑確定超市的地址、顯示輸出等功能。一般情況下，校園的道路是雙向通行的，可設(shè)校園平面圖是一無向網(wǎng)，邊表示路徑，邊上的權(quán)值存放路徑長度等相關(guān)信息。1.采用類語言定義相關(guān)的數(shù)據(jù)類型#include<string.h>#include<stdio.h>#include<time.h>#include"malloc.h"#include<iostream.h>#defineTURE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-1#defineINF32767constintMAXVEX=100;typedefcharVextype;typedefstruct（Vextypevexs[MAXVEX][MAXVEX];//單位名稱（頂點(diǎn)信息）；intadj[MAXVEX][MAXVEX];//單位之間的相通情況（是否有邊）；intdis[MAXVEX][MAXVEX]; //單位間距離（邊的長度）；intf[MAXVEX]; //各單位去超市的頻率；intn; //頂點(diǎn)數(shù)和邊數(shù)；inte;

}Mgraph;數(shù)據(jù)模型（邏輯結(jié)構(gòu)）：帶權(quán)無向圖。算法設(shè)計(jì)Floyd算法表述:第一步，讓所有路徑加上中間頂點(diǎn)1,取A[i][j]與A[i][1]+A[1][j]中較小的值作A[i][j]的新值，完成后得到A（1）,如此進(jìn)行下去，當(dāng)?shù)趉步完成后，A（k）[i][j]表示從i到就且路徑上的中間頂點(diǎn)的路徑的序號小于或等于k的最短路徑長度。當(dāng)?shù)趎-1步完成后，得到A（n-1），A（n-1）即所求結(jié)果。A（n-1）[i][j]表示從i到j(luò)且路徑上的中點(diǎn)頂點(diǎn)的序號小于或等于n-1的最短路徑長度，即A（n-1）[i][j]表示從i到j(luò)的最短路徑長度。代碼如下：voidFloyed（Mgraph*G） //帶權(quán)有向圖求最短路徑floyd算法（intA[MAXVEX][MAXVEX],path[MAXVEX][MAXVEX];inti,j,k,pre;intcount[MAXVEX];//初始化A[][//初始化A[][]和path口口數(shù)組〃置初值；//k代表運(yùn)算步驟for(j=0;j<G->n;j++)(A[i][j]=G->dis[i][j];path[i][j]=-1;count[i]=0;}for(k=0;k<G->n;k++)(for(i=0;i<G->n;i++)for(j=0;j<G->n;j++)if(A[i][j]>(A[i][k]+A[k][j])//從i經(jīng)j到k的一條路徑更短(A[i][j]=A[i][k]+A[k][j];path[i][j]=k;}}cout<<endl<<"Floyed算法求解如下:"<<endl;for(i=0;i<G->n;i++)for(j=0;j<G->n;j++)(if(i!=j)(cout<<〃〃<<i<<〃->〃<<j<<〃；〃；if(A[i][j]==INF)(if(i!=j)cout<<"不存在路徑〃<<〃\n〃<<endl;}else(cout<<"路徑長度為：〃<<A[i][j]<<〃\n〃;cout<<〃路徑為：〃<<i<<〃〃；pre=path[i][j];while(pre!=-1)(cout<<pre<<〃\n〃；pre=path[pre][j];}cout<<j<<endl;}〃以下為選擇總體最優(yōu)過程，然后確址；for(i=0;i<G->n;i++)for(j=0;j<G->n;j++)(if(A[i][j]==INF)count[i]=0;elsecount[i]=1;}for(i=0;i<G->n;i++)if(count[i])(for(j=0;j<G->n;j++)A[i][0]+=A[i][j];}for(i=0;i<G->n;i++)(k=0;if(count[i])if(A[k][0]>A[i][0])k=i;}cout<<"超市的最佳地址為:"<<G->vexs[k]<<endl;}函數(shù)的調(diào)用關(guān)系圖圖2.1函數(shù)調(diào)用關(guān)系圖調(diào)試中遇到的問題及對問題的解決方法在調(diào)試中因?yàn)檫壿嬇袛鄺l件的混亂導(dǎo)致結(jié)果輸出的錯(cuò)誤，編寫代碼時(shí)的不規(guī)范也遇到了很多的小問題，但經(jīng)過多次的思考和調(diào)試，把順序思路思考清楚，才得出正確結(jié)果。算法的時(shí)間、空間復(fù)雜度時(shí)間復(fù)雜度為O（『3）空間復(fù)雜度為O（n）5.測試結(jié)果測試數(shù)據(jù)：輸入：單位個(gè)數(shù)、單位間的路徑數(shù)、單位名稱、相通兩單位以及之間的距離、和各單位去超市的頻率。請輸入單位個(gè)數(shù)：請輸入單位間的路徑數(shù)：6請輸入單位名稱：請輸入第0個(gè)單位名稱：北村請輸入第1個(gè)單位名禰：南村請輸入第2個(gè)單位名禰：田徑場請輸入第3個(gè)單位名稱：一喜教亨樓請輸入第4個(gè)單位名稱：二號教學(xué)樓請盛入而值的兩單位（輸入格式：1,j）：0,1請輸入相逋兩個(gè)單位間的距離（格式：dis）,5請輸入相通的兩單位（輸入格式：i,j）：L2請輸入相通兩個(gè)單位間的距離（格式：dis）：5請輸入相通的兩單位（輸入格式:J）:23諸輸入相通兩個(gè)單?位間的距離（格式：dis）：—請輸入相通的兩單位（輸入格式:,J）:3U 圖2.2測試頁面請輸入相通的兩單位（輸入格式:i,j）：3,4請輸入相通兩個(gè)單位間的距離（格式：dis）；4請輸入相通的兩單位（輸入格式:i,j）：1,3請輸入相通兩個(gè)單位間的距離（格式；dis）：10請輸入相通的兩單位（輸入格式：i.j）：0,4清輸.入相通兩個(gè)單位間的距離（格式：dis）：10請輸入第0個(gè)單位去超市的相對頻率：1請輸入第1個(gè)單位去超市的相對頻率：1請輸入第2個(gè)單位?去超市的相對頻率：1請輸入第3個(gè)單位去超市的相對頻率：1請輸入第4個(gè)單位去超市的相對頻率：1Ployed算法求解如下：0->1:路徑長度為：5路徑為：D10->2:路徑長度為:10路徑為：D120->3;路徑長度為:14路徑為：0430->4:路徑長度為：10路徑為：04?0;路徑長度為路徑為：10>2;路徑長度為:j路徑為:12>3;路徑長度為:10路徑為:13>4:路徑長度為:14路徑為:134>0;路徑長度為:10路徑為:210>1;路徑長度為:5路徑為:21圖2.4測試頁面>1;路徑長度為：5路徑為：21>3;路徑長度為:7路徑為3>4;路徑長度為:11路徑為:234>G;路徑長度為:14路徑為：34C〉1;路徑長度為:1。路徑為：31乂;路徑長度為:了路徑為:32>4;路徑長度為:4路徑為:34路徑長度為:10路徑為0刀；路徑長度為:14路徑為：431>2;路徑長度為:11路徑為:432>3;路徑長度為:4路徑為:43超市的夏隹地址為:北村

6.源代碼（帶注釋6.源代碼（帶注釋voidCreatMgraph(Mgraph*G){inti,j,k;printf("請輸入單位個(gè)數(shù):\n");scanf("%d",&(G->n));printf(-請輸入單位間的路徑數(shù):\n");scanf("%d”,&(G->e));printf("請輸入單位名稱:\n");for(i=0;i<G->n;i++){printf("請輸入第％d個(gè)單位名稱:\n",i);scanf("%s”,&G->vexs[i]);}for(i=0;i<G->n;i++) 〃結(jié)構(gòu)體的初始化;for(j=0;j<G->n;j++){G->adj[i][j]=0;G->dis[i][j]=0;G->f[i]=0;}for(k=0;k<G->e;k++){printf("請輸入相通的兩單位(輸入格式:i,j):\n");scanf("%d,%d",&i,&j);//在距離上體現(xiàn)為無向；printf("請輸入相通兩個(gè)單位間的距離(格式：dis)：\n");scanf("%d”,&(G->dis[i][j]));G->adj[i][j]=1;G->adj[j][i]=1;G->dis[j][i]=G->dis[i][j];}for(k=0;k<G->n;k++){printf("請輸入第％d個(gè)單位去超市的相對頻率:\n",k);scanf("%d",&(G->f[k]));}for(i=0;i<G->n;i++) 〃以距離和頻率之積作為權(quán)值;for(j=0;j<G->n;j++){G->dis[i][j]*=G->f[i]; 〃最終權(quán)值非完全無向；if(G->adj[i][j]=0&&i!=j)G->dis[i][j]=INF;}}voidFloyed(Mgraph*G) 〃帶權(quán)有向圖求最短路徑floyd算法{intA[MAXVEX][MAXVEX],path[MAXVEX][MAXVEX];inti,j,k,pre;intcount[MAXVEX];for(i=0;i<G->n;i++) //初始化A[][]和path[][]數(shù)組for(j=0;j<G->n;j++) 〃置初值；{A[i][j]=G->dis[i][j];path[i][j]=-1;count[i]=0;

for(k=0;k<G->n;k++){//kfor(k=0;k<G->n;k++){//k代表運(yùn)算步驟for(i=0;i<G->n;i++)for(j=0;j<G->n;j++)if(A[i][j]>(A[i][k]+A[k][j])) 〃從i經(jīng)j到k的一條路徑更短{A[i][j]=A[i][k]+A[k][j];path[i][j]=k;}}cout<<endl<<"Floyed算法求解如下:"<<endl;for(i=0;i<G->n;i++)for(j=0;j<G->n;j++){if(i!=j){cout<<""<<i<<"->"<<j<<";";if(A[i][j]=INF){if(i!=j)cout<<"不存在路徑"<<"\n"<<endl;}else{cout<<"路徑長度為:"<<A[i][j]<<"\n";cout<<"路徑為:"<<i<<"";pre=path[i][j];while(pre!=-1){cout<<pre<<"\n";pre=path[pre][j];}cout<<j<<endl;}}}〃以下為選擇總體最優(yōu)過程，然后確址；for(i=0;i<G->n;i++)for(j=0;j<G->n;j++){if(A[i][j]==INF)count[i]=0;elsecount[i]=1;}for(i=0;i<G->n;i++)if(count[i]){for(j=0;j<G->n;j++)A[i][0]+=A[i][j];}for(i=0;i<G->n;i++){k=0;if(count[i])if(A[k][0]>A[i][0])k=i;}cout<<"超市的最佳地址為:"<<G->vexs[k]<<endl;總結(jié)通過對數(shù)據(jù)結(jié)構(gòu)這門課的學(xué)習(xí)，我了解到：“數(shù)據(jù)結(jié)構(gòu)”在計(jì)算機(jī)科學(xué)中是一門綜合性的專業(yè)基礎(chǔ)課。而我們現(xiàn)在所學(xué)的數(shù)據(jù)結(jié)構(gòu)是C語言版的，是建立在C語言基礎(chǔ)之上的，若是C語言基礎(chǔ)知識不牢固，要想學(xué)好數(shù)據(jù)結(jié)構(gòu)這門課程是有一定的困難的。所以在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)這門課程的時(shí)候，也順便復(fù)習(xí)了C語言的相關(guān)內(nèi)容，加深了我對C語言的理解和應(yīng)用，并且也深深體會到了數(shù)據(jù)結(jié)構(gòu)這門課程的重要性。在本次課程設(shè)計(jì)過程中，我體會到自己所學(xué)的東西太少了，很多都不知道