數(shù)據(jù)結(jié)構(gòu)馬踏棋盤

1、實現(xiàn)順序?；蜓h(huán)隊列的存儲一 需求分析1.1理解棧的特性“后進先出” 和隊列的特性“先進先出”。僅僅認(rèn)識到棧和隊列是兩種特殊的線性表是遠遠不夠的，本次實驗的目的在于更深入的了解棧和隊列的特性，以便在實際問題背景下靈活運用他們。在了解他特性的基礎(chǔ)上，還將鞏固對這種結(jié)構(gòu)的構(gòu)造方法的理解。1.2要求：在國際象棋8×8棋盤上面，按照國際象棋規(guī)則中馬的行進規(guī)則，實現(xiàn)從任意初始位置，每個方格只進入一次，走遍棋盤上全部64個方格。編制程序，求出馬的行走路線，并按求出的行走路線，將數(shù)字1，2，64依次填入一個8×8的方陣，并輸出它的行走路線（棋盤如圖所示）。輸入：任意一個起始位置；輸出：無

2、重復(fù)踏遍棋盤的結(jié)果，以數(shù)字1-64表示行走路線。 012345670  8 1   1 7   2  2   H    3 6   3  4  5 4   5        6  

3、      7        二 概要設(shè)計為了實現(xiàn)上述程序功能，可以采用順序棧或者鏈棧來存儲它的數(shù)據(jù)，本實驗所需要的存儲空間不是很大，不需動態(tài)的開辟很多空間，所以采用相對簡單的順序棧來存儲數(shù)據(jù)，既方便有簡單，而用鏈棧在實現(xiàn)上相對比順序棧復(fù)雜的一點。2.1順序棧的抽象數(shù)據(jù)類型定義：ADT Stack數(shù)據(jù)對象：D=ai| ai（0，1，9），i=0,1，2，n，n0數(shù)據(jù)關(guān)系：R=< ai-1, ai >| ai-1, aiD,i=1,2，n ADT

4、 Stack2.2本程序包含三個模塊：1、主程序模塊：void main()定義變量；接受命令；處理命令；退出； 2、起始坐標(biāo)函數(shù)模塊馬兒在棋盤上的起始位置；3、探尋路徑函數(shù)模塊馬兒每個方向進行嘗試，直到試完整個棋盤；4、輸出路徑函數(shù)模塊輸出馬兒行走的路徑； 2.3各模塊之間的調(diào)用關(guān)系：主程序模塊 輸入的初始位置是否正確 否起始坐標(biāo)函數(shù)模塊 是 探尋路徑函數(shù)模塊 輸出路徑函數(shù)模塊塊 結(jié)束 三 詳細(xì)設(shè)計3.1定義頭文件和預(yù)定義#include<stdio.h>#define MAXSIZE 100#define N 83.2數(shù)據(jù)類型定義int board88; /定義棋盤int Ht

5、ry18=1,-1,-2,2,2,1,-1,-2; /*存儲馬各個出口位置相對當(dāng)前位置行下標(biāo)的增量數(shù)組*/int Htry28=2,-2,1,1,-1,-2,2,-1; /*存儲馬各個出口位置相對當(dāng)前位置列下標(biāo)的增量數(shù)組*/struct Stack /定義棧類型 int i; /行坐標(biāo)int j; /列坐標(biāo) int director; /存儲方向stackMAXSIZE; /定義一個棧數(shù)組int top=-1; /棧指針3.3函數(shù)聲明void InitLocation(int xi,int yi); /馬兒在棋盤上的起始位置坐標(biāo)int TryPath(int i,int j); /馬兒每個方向

6、進行嘗試，直到試完整個棋盤void Display(); /輸出馬兒行走的路徑3.4起始坐標(biāo)函數(shù)模塊void InitLocation(int xi,int yi)int x,y; /定義棋盤的橫縱坐標(biāo)變量top+; /棧指針指向第一個棧首stacktop.i=xi; /將起始位置的橫坐標(biāo)進棧stacktop.j=yi; /將起始位置的縱坐標(biāo)進棧stacktop.director=-1; /將起始位置的嘗試方向賦初值boardxiyi=top+1; /標(biāo)記棋盤x=stacktop.i; /將起始位置的橫坐標(biāo)賦給棋盤的橫坐標(biāo)y=stacktop.j; /將起始位置的縱坐標(biāo)賦給棋盤的縱坐標(biāo)if(T

7、ryPath(x,y) /調(diào)用馬兒探尋函數(shù)，如果馬兒探尋整個棋盤返回1否則返回0Display(); /輸出馬兒的行走路徑else printf("無解"); 3.5探尋路徑函數(shù)模塊int TryPath(int i,int j)int find,director,number,min; /定義幾個臨時變量int i1,j1,h,k,s; /定義幾個臨時變量int a8,b18,b28,d8; /定義幾個臨時數(shù)組while(top>-1) /棧不空時循環(huán)for(h=0;h<8;h+) /用數(shù)組a8記錄當(dāng)前位置的下一個位置的可行路徑的條數(shù)number=0; i=s

8、tacktop.i+Htry1h; j=stacktop.j+Htry2h; b1h=i; b2h=j; if(boardij=0&&i>=0&&i<8&&j>=0&&j<8) /如果找到下一位置for(k=0;k<8;k+)i1=b1h+Htry1k; j1=b2h+Htry2k; if(boardi1j1=0&&i1>=0&&i1<8&&j1>=0&&j1<8) /如果找到下一位置 number+; /記錄條數(shù)

9、 ah=number; /將條數(shù)存入數(shù)組a8中 for(h=0;h<8;h+) /根據(jù)可行路徑條數(shù)小到大按下表排序放入數(shù)組d8中min=9; for(k=0;k<8;k+)if(min>ak) min=ak; dh=k; /將下表存入數(shù)組d8中 s=k; as=9; director=stacktop.director; if(top>=63) /如果走完整個棋盤返回1return (1);find=0; /表示沒有找到下一個位置for(h=director+1;h<8;h+) /向八個方向進行探尋i=stacktop.i+Htry1dh; j=stacktop.

10、j+Htry2dh;if(boardij=0&&i>=0&&i<8&&j>=0&&j<8) /如果找到下一位置find=1; /表示找到下一個位置break;if(find=1) /如果找到下一個位置進棧stacktop.director=director; /存儲棧結(jié)點的方向 top+; /棧指針前移進棧stacktop.i=i;stacktop.j=j;stacktop.director=-1; /重新初始化下一棧結(jié)點的嘗試方向boardij=top+1; /標(biāo)記棋盤else /否則退棧boardsta

11、cktop.istacktop.j=0; /清除棋盤的標(biāo)記top-; /棧指針前移退棧return (0); 3.6輸出路徑函數(shù)模塊void Display() int i,j; for(i=0;i<N;i+)for(j=0;j<N;j+)printf("t%d ",boardij); /輸出馬兒在棋盤上走過的路徑printf("nn");printf("n");3.7主程序模塊void main()int i,j;int x,y;for(i=0;i<N;i+) /初始化棋盤 for(j=0;j<N;j+) b

12、oardij=0;for(;)printf("Please input importpoint(1<=x<=8 and 1<=y<=8)n");printf("Input x = ");scanf("%d",&x); /輸入起始位置的橫坐標(biāo)printf("Input y = ");scanf("%d",&y); /輸入起始位置的縱坐標(biāo)if(x>=1&&x<=8&&y>=1&&y<=8)

13、break;printf("Your input is worng!n");printf("begin with %d board:nn", 8*(x-1)+y);InitLocation(x-1,y-1); /調(diào)用起始坐標(biāo)函數(shù)四 調(diào)試分析（1）本次實驗的主要目的是在于掌握和理解棧的特性和它的應(yīng)用。在編制該程序中遇到了很多問題。首先，在開始剛編制程序的時候遇到的問題是，程序編譯都通不過，主要在一些細(xì)節(jié)的問題上，還有在程序的返回值在剛開始時也沒有正確返回。經(jīng)過編譯慢慢調(diào)試，編譯都能通過，沒有錯誤和警告。（2）雖然編譯都能通過，但是運行時卻出錯，程序不能終止

14、，只有通過人工方式結(jié)束程序，可能是在某些地方出現(xiàn)了無限死循環(huán)了，然后在仔細(xì)檢查代碼，發(fā)現(xiàn)沒有標(biāo)記馬兒嘗試的方向director，這樣的話，馬兒回溯的時候，下一次又有可能走那個方向，這樣就出現(xiàn)了死循環(huán)。（3）標(biāo)記好馬兒嘗試的方向后，編譯運行，但是運行結(jié)果卻不符合程序所要求的結(jié)果，說明在算法上肯定有錯誤，檢查發(fā)現(xiàn)，馬兒走的坐標(biāo)沒有控制后，它的橫縱坐標(biāo)必須控制0到7之間，否則的話馬兒就會踏出棋盤以外，這樣輸出的結(jié)果就不對。還有就是棋盤走過的位置要標(biāo)記一下，以便下次走不重復(fù)走，當(dāng)回溯的時候的記得把標(biāo)記給清掉，這個地方有時候也很容易混淆。（4）還有一點就是，該程序運算量大，算法復(fù)雜度高，所以運行的時候很慢，特別占內(nèi)存，CPU的使用也很高，幾乎都在70%到90%之間，配置低了可能還運行不了。五 測試結(jié)果結(jié)果1：結(jié)果2：六 實驗體會通過本次實驗的編寫，能夠掌握棧的性質(zhì)以及它的應(yīng)用。這次實驗花了很多時間才完成，其實本應(yīng)該早完成的，在檢查的過程中有多多少少修改完美了一下，不過算法思想?yún)s沒有改變。這個程序也讓我頭疼了幾次，就是運行速度很慢，要等很久才能輸出結(jié)果，這樣的話很占內(nèi)存資源，而且CPU的使用記錄也很高，主要是它需要的運算太多，所以CPU 使用記錄也是很高的。雖然我也參考了一些優(yōu)化的算法，可以找到最優(yōu)路進走，但是這些最優(yōu)算法都和棧的應(yīng)用失去了聯(lián)系，