數(shù)據(jù)結(jié)構(gòu)課程設計-馬踏棋盤

PAGEPAGE7目錄TOC\o"1-2"\h\z\u1前言 12需求分析 12.1任務和要求 12.2運行環(huán)境 12.3開發(fā)工具 13分析和設計 13.1系統(tǒng)分析及設計思路 13.2主要數(shù)據(jù)結(jié)構(gòu)及算法 23.3函數(shù)流程圖 24具體代碼實現(xiàn) 95課程設計總結(jié) 165.1程序運行結(jié)果 165.2設計結(jié)論 16參考文獻 18致謝 18

1前言編寫一個C語言程序，作為國際象棋中的馬踏遍棋盤的演示程序。在這里，我們用一個main函數(shù)通過調(diào)用其他一些分功能函數(shù)來實現(xiàn)求并且輸出馬踏遍棋盤的行走路線。2需求分析2.1任務和要求將馬隨機放在國際象棋的8×8棋盤的某個方格中，馬按照走棋的規(guī)則進行移動。每個方格只進入一次，走遍棋盤的全部64個方格。編寫算法，求出馬的行走路線，并按求出的行走路線，將1,2,…,64依次填入一個8×8的方陣，并輸出。要求：畫出算法的流程圖，分析算法的時間復雜度。2.2運行環(huán)境（1）WINDOWS2000/XP系統(tǒng)（2）VisualC++6.0編譯環(huán)境或TC編譯環(huán)境2.3開發(fā)工具C語言3分析和設計3.1系統(tǒng)分析及設計思路根據(jù)需求分析可知，我們所設計的程序要達到讓馬從任意一起點出發(fā)都不重復地遍歷所有的8×8棋格的功能。按照需求，并考慮到程序的可讀性，我們按順序共設計了以下六大模塊：定義頭文件和宏定義模塊：這是C程序必不可少的一個部分，通過頭文件來調(diào)用程序所需庫函數(shù)，而通過宏定義進行宏替換。(2)數(shù)據(jù)類型定義模塊：該模塊定義了全局數(shù)據(jù)結(jié)構(gòu)，它們的作用域為從定義開始到本源文件結(jié)束，以便于讓后面很多函數(shù)都可以用到它們，而不必再重新定義。(3)探尋路徑函數(shù)模塊：按照馬的行走規(guī)則對棋盤進行遍歷，尋找馬的行走路徑，每次僅訪問一個棋格，保證每個棋格都訪問到且每個棋格僅訪問一次。(4)輸出路徑函數(shù)模塊：對探尋路徑函數(shù)模塊中保存下來的順序進行輸出，輸出格式按照棋盤8×8的方陣格式。(5)起始坐標函數(shù)模塊：將馬的起始位置坐標與棋盤坐標聯(lián)系起來，通過調(diào)用探尋路徑函數(shù)和輸出路徑函數(shù)達到預期效果。(6)主程序模塊：主要是完成棋盤初始化，輸入，調(diào)用等任務進而來完成馬踏棋盤問題。另外，一般來說，當馬位于（i,j）時，可以走下列8個位置之一：（i-2,j+1)(i-1,j+2)(i+1,j+2)(i+2,j+1)(i+2,j-1)(i+1,j-2)(i-1,j-2)(i-2,j-1)這8個可能的位置可以用兩個一維數(shù)組存放，利用一維數(shù)組表示馬在棋盤內(nèi)新位置。但是，如果(x,y)靠近棋盤的邊緣，上述位置可能超出棋盤范圍，成為不允許的位置。3.2主要數(shù)據(jù)結(jié)構(gòu)及算法（1)定義頭文件和宏定義#include<stdio.h> #defineMAXSIZE100 #defineN8（2）數(shù)據(jù)類型定義intboard[8][8];定義棋盤；intHtry1[8]={1,-1,-2,2,2,1,-1,-2}；intHtry2[8]={2,-2,1,1,-1,-2,2,-1};Htry1[8]和Htry2[8]分別表示馬各個出口位置相對當前位置的橫坐標和縱坐標的增量數(shù)組；structStack { inti; intj; intdirector; }stack[MAXSIZE]; inttop=-1;這里是定義棧類型，其中i是橫坐標，j是縱坐標，director是存儲方向，stack[MAXSIZE]表示定義一個棧數(shù)組，top=-1表示棧指針，可以存儲棋盤上的信息以及棧中元素移動情況。(3)探尋路徑函數(shù)定義一個TryPath(inti,intj)函數(shù)來探尋馬的行走路徑，此函數(shù)通過while（top>-1）語句將程序控制在棧不為空的情況下進行循環(huán)，在while循環(huán)中，首先通過一個雙重for循環(huán)記錄下當前位置的下一個位置的可行路徑條數(shù)，在通過一個雙重for循環(huán)將前面可行路徑條數(shù)從小到大排序存儲在數(shù)組中，最后通過一個for循環(huán)來向8個方向進行探尋。(4)輸出路徑函數(shù)定義一個Display()函數(shù)來按照棋盤格式輸出馬的探尋路徑，此函數(shù)通過一個雙重for循環(huán)來實現(xiàn)的，外循環(huán)控制橫坐標的增加，內(nèi)循環(huán)控制縱坐標的增加。（5）起始坐標函數(shù)定義一個InitLocation(intxi,intyi)函數(shù)將馬的行走路徑與棋盤坐標聯(lián)系起來達到預期效果，此函數(shù)是通過棧將馬的起始位置與棋盤坐標聯(lián)系起來的，并且調(diào)用了TryPath(inti,intj)函數(shù)和Display()函數(shù)。(6)主函數(shù)在main()函數(shù)中，我們通過一個雙重for循環(huán)控制棋盤的橫縱坐標完成了對棋盤的初始化，在通過一個三個表達式都為空的for循環(huán)來控制輸入正確的橫縱坐標，直到輸入正確才跳出循環(huán)在執(zhí)行下面的語句，最后通過調(diào)用InitLocation(intxi,intyi)函數(shù)完整了整個馬踏棋盤問題。時間復雜度分析：在main()函數(shù)中，棋盤初始化的時間復雜度為O（N^2)，接著經(jīng)過一個for循環(huán)，其時間復雜度為O（1），再往下調(diào)用InitLocation(x-1,y-1)函數(shù)時，要經(jīng)過一個while(top>-1)，在while循環(huán)中還有雙重for循環(huán)，因此時間復雜度比較大，故總的時間復雜度也比較大。3.3函數(shù)流程圖（1）主函數(shù)流程圖開始開始inti,j;inti,j;printf("******printf("***********馬踏棋盤***********\n\n");i<Ni<NNJ<NJ<NNi++Yi++board[i][j]=0;j++printf("Pleaseprintf("Pleaseinputimportpoint(1<=x<=8and1<=y<=8)\n\n");printf("請輸入起始位置的橫坐標x=");printf("請輸入起始位置的橫坐標x=");123123scanf("%d",&x);printf("\n");scanf("%d",&x);printf("\n");printf("輸入起始位置的縱坐標y=");printf("輸入起始位置的縱坐標y=");scanf("%d",&scanf("%d",&y);printf("\n")x>=1&&x<=8&&y>=1&&y<=8x>=1&&x<=8&&y>=1&&y<=8Yprintf("Yourinputisworng!!!\n");Nprintf("Yourinputisworng!!!\n");printf("beginwith%dboard:\n\n",8*(x-1)+y);printf("beginwith%dboard:\n\n",8*(x-1)+y);InitLocation(x-1,y-1);InitLocation(x-1,y-1);return0;return0;結(jié)束結(jié)束圖3.1main函數(shù)流程圖（2）探尋路徑函數(shù)流程圖661 h=0h=0h<8Nh<8Y min=9; min=9;k=0k=0k<8k<8NYmin>a[k]min>a[k]Ymin=a[k];d[h]=k;s=k;min=a[k];d[h]=k;s=k;k++a[s]=9;h++a[s]=9;h++director=stack[top].director;director=stack[top].director;top>=63top>=63return(1);find=0;h=director+1h=director+1h<8Nh<8i=stack[top].i+Htry1[d[h]];Yi=stack[top].i+Htry1[d[h]];54235423h++j=stack[top].j+Htry2[d[h]];h++j=stack[top].j+Htry2[d[h]];(board[i][j]==0&&i>=0&&i<8&&j>=0&&j<8(board[i][j]==0&&i>=0&&i<8&&j>=0&&j<8NNNfind=1; break;find=1; break;find=1Nstack[top].director=director;top++;Ystack[top].director=director;top++;stack[top].i=i; stack[top].j=j; stack[top].j=j;stack[top].i=i; stack[top].j=j; stack[top].j=j;stack[top].director=-1;board[i][j]=top+1;stack[top].director=-1;board[i][j]=top+1;board[stack[top].i][stack[top].j]=0board[stack[top].i][stack[top].j]=0;top--;圖3.2探尋路徑函數(shù)流程圖（3）輸出路徑函數(shù)流程圖inti,j;inti,j;i=0i=0i<Ni<NNYI++j=0I++j=0j<Nj<NNprintf("\t%d",board[i][j]);printf("\t%d",board[i][j]);j++j++printf("\n\n");printf("\n\n");圖3.3輸出路徑函數(shù)流程圖（4）坐標函數(shù)流程圖inti，j;inti，j;TryPath(x,y)TryPath(x,y) NYPrintf("無解"）；Dispaly();Printf("無解"）；Dispaly();圖3.4坐標函數(shù)流程圖4具體代碼實現(xiàn) //定義頭文件和宏定義 #include<stdio.h> #defineMAXSIZE100 #defineN8 //數(shù)據(jù)類型定義 intboard[8][8];//定義棋盤 intHtry1[8]={1,-1,-2,2,2,1,-1,-2}; //存儲馬各個出口位置相對當前位置行下標的增量數(shù)組 intHtry2[8]={2,-2,1,1,-1,-2,2,-1}; //存儲馬各個出口位置相對當前位置列下標的增量數(shù)組 structStack//定義棧類型 { inti;//橫坐標 intj;//縱坐標 intdirector;//存儲方向 }stack[MAXSIZE];//定義一個棧數(shù)組 inttop=-1;//棧指針 //探尋路徑函數(shù)模塊 intTryPath(inti,intj) { intfind,director,number,min;//定義幾個臨時變量 inti1,j1,h,k,s;//定義幾個臨時變量 inta[8],b1[8],b2[8],d[8];//定義幾個臨時數(shù)組 while(top>-1)//棧不空時循環(huán) { for(h=0;h<8;h++)//用數(shù)組a[8]記錄當前位置的下一個位置的可行路徑的條數(shù) { number=0; i=stack[top].i+Htry1[h]; j=stack[top].j+Htry2[h]; b1[h]=i; b2[h]=j; if(board[i][j]==0&&i>=0&&i<8&&j>=0&&j<8)//如果找到下一位置 { for(k=0;k<8;k++) { i1=b1[h]+Htry1[k]; j1=b2[h]+Htry2[k]; if(board[i1][j1]==0&&i1>=0&&i1<8&&j1>=0&&j1<8) //如果找到下一位置 number++;//記錄條數(shù) } a[h]=number;//將條數(shù)存入數(shù)組a[8]中 } } for(h=0;h<8;h++)//根據(jù)可行路徑條數(shù)小到大按下表排序放入數(shù)組d[8]中 { min=9; for(k=0;k<8;k++) if(min>a[k]) { min=a[k]; d[h]=k;//將下表存入數(shù)組d[8]中 s=k; } a[s]=9; } director=stack[top].director; if(top>=63)//如果走完整個棋盤返回1 return(1); find=0;//表示沒有找到下一個位置 for(h=director+1;h<8;h++)//向八個方向進行探尋 { i=stack[top].i+Htry1[d[h]]; j=stack[top].j+Htry2[d[h]]; if(board[i][j]==0&&i>=0&&i<8&&j>=0&&j<8)//如果找到下一位置 { find=1;//表示找到下一個位置 break; } } if(find==1)//如果找到下一個位置進棧 { stack[top].director=director;//存儲棧結(jié)點的方向 top++;//棧指針前移進棧 stack[top].i=i; stack[top].j=j; stack[top].director=-1;//重新初始化下一棧結(jié)點的嘗試方向 board[i][j]=top+1;//標記棋盤 } else//否則退棧 { board[stack[top].i][stack[top].j]=0;//清除棋盤的標記 top--;//棧指針前移退棧 } } return(0); }//輸出路徑函數(shù)模塊 voidDisplay() { inti,j; for(i=0;i<N;i++) { for(j=0;j<N;j++) printf("\t%d",board[i][j]);//輸出馬兒在棋盤上走過的路徑 printf("\n\n"); } printf("\n"); } //起始坐標函數(shù)模塊 voidInitLocation(intxi,intyi) { intx,y;//定義棋盤的橫縱坐標變量 top++;//棧指針指向第一個棧首 stack[top].i=xi;//將起始位置的橫坐標進棧 stack[top].j=yi;//將起始位置的縱坐標進棧 stack[top].director=-1;//將起始位置的嘗試方向賦初值 board[xi][yi]=top+1;//標記棋盤 x=stack[top].i;//將起始位置的橫坐標賦給棋盤的橫坐標 y=stack[top].j;//將起始位置的縱坐標賦給棋盤的縱坐標 if(TryPath(x,y))//調(diào)用馬兒探尋函數(shù)，如果馬兒探尋整個棋盤返回1否則返回0 Display();//輸出馬兒的行走路徑 else printf("無解"); } //主程序模塊 intmain() { intx,y; inti,j; printf("**************馬踏棋盤**************\n\n");for(i=0;i<N;i++)//初始化棋盤 for(j=0;j<N;j++) board[i][j]=0; for(;;) { printf("Pleaseinputimportpoint(1<=x<=8and1<=y<=8)\n\n"); printf("請輸入起始位置的橫坐標x="); scanf("%d",&x);//輸入起始位置的橫坐標 printf("\n"); printf("輸入起始位置的縱坐標y="); scanf("%d",&y);//輸入起始位置的縱坐標 printf("\n"); if(x>=1&&x<=8&&y>=1&&y<=8)break; printf("Yourinputisworng!!!\n"); } printf("beginwith