騎士巡游數(shù)據(jù)結(jié)構(gòu)課程設計完成版

騎士巡游數(shù)據(jù)結(jié)構(gòu)課程設計完成版目錄一． 課程設計的目的 1二． 功能說明 1三． 詳細設計 23.1. 功能模塊設計 23.1.1. 主函數(shù)main()的執(zhí)行流程 23.1.2. 創(chuàng)建模塊 33.1.3. 操作模塊 33.1.4. 顯示模塊 33.2. 數(shù)據(jù)結(jié)構(gòu)設計 3四． 程序?qū)崿F(xiàn) 74.1. 源碼分析 74.2. 調(diào)試結(jié)果 134.3. 調(diào)試時遇到的問題及解決 134.4. 時間復雜度分析 134.5. 算法的改進設想 14結(jié)束語 16參考文獻 17課程設計的目的騎士巡游的求解是一個經(jīng)典的算法，許多數(shù)學家，程序員在不斷尋早改善求解方法。對騎士巡游問題的研究中可包括貪心算法，回溯算法，窮舉算法。本例是通過窮舉算法，加深對數(shù)據(jù)窮舉的理解。在對已經(jīng)走過的路線里，采用標志矩陣進行記錄。標志矩陣的引入利用了數(shù)據(jù)的線性存儲。利用窮舉算法，標志矩陣實現(xiàn)簡單的騎士巡游算法。功能說明整個實驗完成一個騎士巡游算法，本實驗中騎士巡游的實現(xiàn)通過窮舉舉例和標志矩陣。騎士巡游數(shù)據(jù)結(jié)構(gòu)課程設計完成版全文共8頁，當前為第1頁。創(chuàng)建模塊。根據(jù)輸入騎士巡游數(shù)據(jù)結(jié)構(gòu)課程設計完成版全文共8頁，當前為第1頁。操作模塊。輸入騎士的初始位置，進行騎士巡游操作。顯示模塊。顯示出巡游結(jié)果。創(chuàng)建標志矩陣顯示巡游結(jié)果進行巡游創(chuàng)建標志矩陣顯示巡游結(jié)果進行巡游操作模塊顯示模塊創(chuàng)建模塊操作模塊顯示模塊創(chuàng)建模塊騎士巡游表實驗程序圖1功能模塊圖騎士巡游表實驗程序詳細設計功能模塊設計主函數(shù)main()的執(zhí)行流程在進入main()函數(shù)之后立即執(zhí)行菜單，輸入行列數(shù)，本實驗中，行列最大11。執(zhí)行流程如圖：開始開始Main（）Main（）函數(shù)輸入命令輸入命令是否符合條件條件是是否符合條件條件是否否判斷命令，完成相應功能判斷命令，完成相應功能結(jié)束結(jié)束圖2主函數(shù)main()的流程圖創(chuàng)建模塊本模塊先要求輸入要創(chuàng)建的棋盤的行列數(shù)。程序給出標志矩陣。操作模塊騎士巡游數(shù)據(jù)結(jié)構(gòu)課程設計完成版全文共8頁，當前為第2頁。輸入騎士初始位置，進行巡游。騎士巡游數(shù)據(jù)結(jié)構(gòu)課程設計完成版全文共8頁，當前為第2頁。顯示模塊現(xiàn)實巡游結(jié)果。數(shù)據(jù)結(jié)構(gòu)設計利用標志矩陣，行優(yōu)先，循序存取，對巡游過的方格標志，通過簡單的算法將標志矩陣與棋盤位置進行轉(zhuǎn)換。程序?qū)崿F(xiàn)源碼分析#include<stdio.h>intf[11][11];/*定義一個矩陣來模擬棋盤*/intadjm[121][121];/*標志矩陣，即對于上述棋盤，依次進行編號 1--121(行優(yōu)先）可以從一個棋盤格i跳到棋盤格j時，adjm[i][j]=1*/voidcreatadjm(void);/*創(chuàng)建標志矩陣函數(shù)聲明*/voidmark(int,int,int,int);/*將標志矩陣相應位置置1*/voidtravel(int,int);/*巡游函數(shù)聲明*/intn,m;/*定義矩陣大小及標志矩陣的大小*//******************************主函數(shù)***********************************/intmain(){inti,j,k,l;printf("Pleaseinputsizeofthechessboard:");/*輸入矩陣的大小值*/ scanf("%d",&n);m=n*n;creatadjm();/*創(chuàng)建標志矩陣*/ puts("Thesignmatrixis:");for(i=1;i<=m;i++)/*打印輸出標志矩陣*/{for(j=1;j<=m;j++) printf("%2d",adjm[i][j]);printf("\n");}騎士巡游數(shù)據(jù)結(jié)構(gòu)課程設計完成版全文共8頁，當前為第3頁。printf("Pleaseinputtheknight'sposition(i,j):");/*輸入騎士的初始位置*/騎士巡游數(shù)據(jù)結(jié)構(gòu)課程設計完成版全文共8頁，當前為第3頁。scanf("%d%d",&i,&j);l=(i-1)*n+j;/*騎士當前位置對應的標志矩陣的橫坐標*/while((i>0)||(j>0))/*對騎士位置的判斷*/{for(i=1;i<=n;i++)/*棋盤矩陣初始化*/for(j=1;j<=n;j++)f[i][j]=0;k=0;/*所跳步數(shù)計數(shù)*/travel(l,k);/*從i,j出發(fā)開始巡游*/puts("Thetravelstepsare:");for(i=1;i<=n;i++)/*巡游完成后輸出巡游過程*/ {for(j=1;j<=n;j++) printf("%4d",f[i][j]);printf("\n"); }printf("Pleaseinputtheknight'sposition(i,j):");/*為再次巡游輸入起始位置*/ scanf("%d%d",&i,&j);l=(i-1)*n+j;} puts("\nPressanykeytoquit..."); getchar();return0;}/*****************************創(chuàng)建標志矩陣子函數(shù)*************************/voidcreatadjm(){inti,j;for(i=1;i<=n;i++)/*巡游矩陣初始化*/for(j=1;j<=n;j++)f[i][j]=0;for(i=1;i<=m;i++)/*標志矩陣初始化*/for(j=1;j<=m;j++)adjm[i][j]=0;for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(f[i][j]==0)/*對所有符合條件的標志矩陣種元素置1*/ {f[i][j]=1;騎士巡游數(shù)據(jù)結(jié)構(gòu)課程設計完成版全文共8頁，當前為第4頁。if((i+2<=n)&&(j+1<=n))mark(i,j,i+2,j+1);騎士巡游數(shù)據(jù)結(jié)構(gòu)課程設計完成版全文共8頁，當前為第4頁。if((i+2<=n)&&(j-1>=1))mark(i,j,i+2,j-1);if((i-2>=1)&&(j+1<=n))mark(i,j,i-2,j+1);if((i-2>=1)&&(j-1>=1))mark(i,j,i-2,j-1);if((j+2<=n)&&(i+1<=n))mark(i,j,i+1,j+2);if((j+2<=n)&&(i-1>=1))mark(i,j,i-1,j+2);if((j-2>=1)&&(i+1<=n))mark(i,j,i+1,j-2);if((j-2>=1)&&(i-1>=1))mark(i,j,i-1,j-2); }return;}/*********************************巡游子函數(shù)*******************************/voidtravel(intp,intr){inti,j,q;for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(f[i][j]>r)f[i][j]=0;/*棋盤矩陣的置〉r時，置0*/r=r+1;/*跳步計數(shù)加1*/i=((p-1)/n)+1;/*還原棋盤矩陣的橫坐標*/j=((p-1)%n)+1;/*還原棋盤矩陣的縱坐標*/f[i][j]=r;/*將f[i][j]做為第r跳步的目的地*/for(q=1;q<=m;q++)/*從所有可能的情況出發(fā)，開始進行試探式巡游*/ {i=((q-1)/n)+1;j=((q-1)%n)+1;if((adjm[p][q]==1)&&(f[i][j]==0)) travel(q,r);/*遞歸調(diào)用自身*/}return;}/*************************賦值子函數(shù)***************************************/voidmark(inti1,intj1,inti2,intj2){adjm[(i1-1)*n+j1][(i2-1)*n+j2]=1;adjm[(i2-1)*n+j2][(i1-1)*n+j1]=1;return;}騎士巡游數(shù)據(jù)結(jié)構(gòu)課程設計完成版全文共8頁，當前為第5頁。騎士巡游數(shù)據(jù)結(jié)構(gòu)課程設計完成版全文共8頁，當前為第5頁。調(diào)試結(jié)果使用vc++進行調(diào)試成功，程序的運行如下圖：圖3程序調(diào)試運行圖調(diào)試時遇到的問題及解決在調(diào)試之中，主要遇到了以下問題：由于初次接觸騎士巡游問題，對在窮舉算法中，對巡游過的位置很久找不到一好的個算法，最后參考網(wǎng)上的算法，采用了標志矩陣。輸入，輸出的條件控制沒有寫好，導致可控性不好。后來簡單的加入了一條控制語句輕松實現(xiàn)。時間復雜度分析騎士巡游數(shù)據(jù)結(jié)構(gòu)課程設計完成版全文共8頁，當前為第6頁。創(chuàng)建標志矩陣子函數(shù)算法復雜度O(N)，巡游子函數(shù)時間復雜度O(N)。騎士巡游數(shù)據(jù)結(jié)構(gòu)課程設計完成版全文共8頁，當前為第6頁。算法的改進設想關(guān)于騎士巡游的求解有窮舉，貪心等算法