實(shí)驗(yàn)實(shí)現(xiàn)順序?；蜓h(huán)隊(duì)列的存儲(chǔ)

1、實(shí)驗(yàn)二實(shí)現(xiàn)順序?；蜓h(huán)隊(duì)列的存儲(chǔ)題目：編制一個(gè)馬踏棋盤(pán)算法實(shí)現(xiàn)的程序班級(jí)：計(jì)科0603姓名：李漢剛學(xué)號(hào)：20064140303完成日期：2008-4-20一、實(shí)驗(yàn)?zāi)康?1) 、理解棧的特性“后進(jìn)先出”和隊(duì)列的特性“先進(jìn)先出”。(2) 、僅僅認(rèn)識(shí)到棧和隊(duì)列是兩種特殊的線(xiàn)性表是遠(yuǎn)遠(yuǎn)不夠的，本次實(shí)驗(yàn)的目的在于更深入的了解棧和隊(duì)列的特性，以便在實(shí)際問(wèn)題背景下靈活運(yùn)用他們。(3) 、在了解他特性的基礎(chǔ)上，還將鞏固對(duì)這種結(jié)構(gòu)的構(gòu)造方法的理解。二、實(shí)驗(yàn)環(huán)境(1) WindowsXP系統(tǒng)下(2) 編程環(huán)境：VC6.0+三、實(shí)驗(yàn)內(nèi)容(1) 、要求：在國(guó)際象棋8X8棋盤(pán)上面，按照國(guó)際象棋規(guī)則中馬的行進(jìn)規(guī)則，實(shí)現(xiàn)從

2、任意初始位置，每個(gè)方格只進(jìn)入一次，走遍棋盤(pán)上全部64個(gè)方格。編制程序，求出馬的行走路線(xiàn)，并按求出的行走路線(xiàn)，將數(shù)字1,2,，64依次填入一個(gè)8X8的方陣，并輸出它的行走路線(xiàn)(棋盤(pán)如圖所示)。、輸入：任意一個(gè)起始位置；輸出：無(wú)重復(fù)踏遍棋盤(pán)的結(jié)果，以數(shù)字1-64表示行走路線(xiàn)。012345670811722H363454567(2) 、數(shù)據(jù)結(jié)構(gòu)要求：采用順序棧或者鏈棧實(shí)現(xiàn)。四、實(shí)驗(yàn)步驟為了實(shí)現(xiàn)上述程序功能，可以采用順序?；蛘哝湕?lái)存儲(chǔ)它的數(shù)據(jù)，本實(shí)驗(yàn)所需要的存儲(chǔ)空間不是很大，不需動(dòng)態(tài)的開(kāi)辟很多空間，所以采用相對(duì)簡(jiǎn)單的順序棧來(lái)存儲(chǔ)數(shù)據(jù)，既方便有簡(jiǎn)單，而用鏈棧在實(shí)現(xiàn)上相對(duì)比順序棧復(fù)雜的一點(diǎn)。(一)、概要

3、設(shè)計(jì)(1) 、順序棧的抽象數(shù)據(jù)類(lèi)型定義：ADTStack(數(shù)據(jù)對(duì)象：D=(ai|ai(0,1,，9),i=0,1,2,，n,n>0數(shù)據(jù)關(guān)系：R=<a.,a>1a.,aiCD,i=1,2nADTStack(2) 本程序包含三個(gè)模塊：1、主程序模塊：voidmain()定義變量；接受命令；處理命令；退出；2、起始坐標(biāo)函數(shù)模塊一一馬兒在棋盤(pán)上的起始位置；3、探尋路徑函數(shù)模塊一一馬兒每個(gè)方向進(jìn)行嘗試，直到試完整個(gè)棋盤(pán);4、輸出路徑函數(shù)模塊一一輸出馬兒行走的路徑；各模塊之間的調(diào)用關(guān)系:主程序模塊起始坐標(biāo)函數(shù)模探尋路徑函數(shù)模輸出路徑函數(shù)模I結(jié)束;II(二)、詳細(xì)設(shè)計(jì)(1)、定義頭文件和預(yù)

4、定義#include<stdio.h>#defineMAXSIZE100#defineN8(2)、數(shù)據(jù)類(lèi)型定義intboard88;/定義棋盤(pán)intHtry18=1,-1,-2,2,2,1,-1,-2;/*存儲(chǔ)馬各個(gè)出口位置相對(duì)當(dāng)前位置行下標(biāo)的增量數(shù)組*/intHtry28=2,-2,1,1,-1,-2,2,-1;/*存儲(chǔ)馬各個(gè)出口位置相對(duì)當(dāng)前位置列下標(biāo)的增量數(shù)組*/structStack/定義棧類(lèi)型inti;/行坐標(biāo)intj;/列坐標(biāo)intdirector;/存儲(chǔ)方向stackMAXSIZE;/定義一個(gè)棧數(shù)組inttop=-1;/棧指針馬兒在棋盤(pán)上的起始位置坐標(biāo)馬兒每個(gè)方向進(jìn)行嘗

5、試，直到試完整個(gè)棋盤(pán)輸出馬兒行走的路徑、函數(shù)聲明voidInitLocation(intxi,intyi);/intTryPath(inti,intj);/voidDisplay();/(4)、起始坐標(biāo)函數(shù)模塊voidInitLocation(intxi,intyi)intx,y;/定義棋盤(pán)的橫縱坐標(biāo)變量top+;/棧指針指向第一個(gè)棧首stacktop.i=xi;/將起始位置的橫坐標(biāo)進(jìn)棧stacktop.j=yi;/將起始位置的縱坐標(biāo)進(jìn)棧stacktop.director=-1;/將起始位置的嘗試方向賦初值boardxiyi=top+1;/標(biāo)記棋盤(pán)x=stacktop.i;/將起始位置的橫坐標(biāo)

6、賦給棋盤(pán)的橫坐標(biāo)y=stacktop.j;/將起始位置的縱坐標(biāo)賦給棋盤(pán)的縱坐標(biāo)if(TryPath(x,y)/調(diào)用馬兒探尋函數(shù)，如果馬兒探尋整個(gè)棋盤(pán)返回1否則返回0Display();/輸出馬兒的行走路徑elseprintf("無(wú)解");(5)、探尋路徑函數(shù)模塊intTryPath(inti,intj)(intfind,director,number,min;/定義幾個(gè)臨時(shí)變量inti1,j1,h,k,s;/定義幾個(gè)臨時(shí)變量inta8,b18,b28,d8;/定義幾個(gè)臨時(shí)數(shù)組while(top>-1)/棧不空時(shí)循環(huán)(for(h=0;h<8;h+)/用數(shù)組a8記錄

7、當(dāng)前位置的下一個(gè)位置的可行路徑的條數(shù)(number=0;i=stacktop.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

8、)/如果找到下一位置number+;/記錄條數(shù)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)/如果走完整個(gè)棋盤(pán)返回1return(1);find=0;/表示沒(méi)有找到下一個(gè)位置for(h=director+1;h<8;h+)/向八個(gè)方向進(jìn)行探尋(i=stacktop.i+Htry1dh;j=

9、stacktop.j+Htry2dh;if(boardij=0&&i>=0&&i<8&&j>=0&&j<8)/如果找到下一位置(find=1;/表示找到下一個(gè)位置break;if(find=1)/如果找到下一個(gè)位置進(jìn)棧(stacktop.director=director;/top+;/stacktop.i=i;stacktop.j=j;stacktop.director=-1;/boardij=top+1;/else/(boardstacktop.istacktop.j=0;top-;/return(0)

10、;(6)輸出路徑函數(shù)模塊voidDisplay()(inti,j;for(i=0;i<N;i+)(for(j=0;j<N;j+)printf("t%d",boardij);/printf("nn");printf("n");存儲(chǔ)棧結(jié)點(diǎn)的方向棧指針前移進(jìn)棧重新初始化下一棧結(jié)點(diǎn)的嘗試方向標(biāo)記棋盤(pán)否則退棧/清除棋盤(pán)的標(biāo)記棧指針前移退棧輸出馬兒在棋盤(pán)上走過(guò)的路徑(5)主程序模塊voidmain()(inti,j;intx,y;for(i=0;i<N;i+)/初始化棋盤(pán)for(j=0;j<N;j+)boardij=0;f

11、or(;)(printf("Pleaseinputimportpoint(1<=x<=8and1<=y<=8)n");printf("Inputx=");scanf("%d”,&x);/輸入起始位置的橫坐標(biāo)printf("Inputy=");scanf("%d",&y);/輸入起始位置的縱坐標(biāo)if(x>=1&&x<=8&&y>=1&&y<=8)break;printf("Yourinp

12、utisworng!n");printf("beginwith%dboard:nn",8*(x-1)+y);InitLocation(x-1,y-1);/調(diào)用起始坐標(biāo)函數(shù)五、調(diào)試分析(1) 、本次實(shí)驗(yàn)的主要目的是在于掌握和理解棧的特性和它的應(yīng)用。在編制該程序中遇到了很多問(wèn)題。首先，在開(kāi)始剛編制程序的時(shí)候遇到的問(wèn)題是，程序編譯都通不過(guò)，主要在一些細(xì)節(jié)的問(wèn)題上，還有在程序的返回值在剛開(kāi)始時(shí)也沒(méi)有正確返回。經(jīng)過(guò)編譯慢慢調(diào)試，編譯都能通過(guò)，沒(méi)有錯(cuò)誤和警告。(2) 、雖然編譯都能通過(guò)，但是運(yùn)行時(shí)卻出錯(cuò)，程序不能終止，只有通過(guò)人工方式結(jié)束程序，可能是在某些地方出現(xiàn)了無(wú)限死循環(huán)

13、了，然后在仔細(xì)檢查代碼，發(fā)現(xiàn)沒(méi)有標(biāo)記馬兒嘗試的方向director,這樣的話(huà)，馬兒回溯的時(shí)候，下一次又有可能走那個(gè)方向，這樣就出現(xiàn)了死循環(huán)。、標(biāo)記好馬兒嘗試的方向后，編譯運(yùn)行，但是運(yùn)行結(jié)果卻不符合程序所要求的結(jié)果，說(shuō)明在算法上肯定有錯(cuò)誤，檢查發(fā)現(xiàn)，馬兒走的坐標(biāo)沒(méi)有控制后，它的橫縱坐標(biāo)必須控制0到7之間,否則的話(huà)?cǎi)R兒就會(huì)踏出棋盤(pán)以外，這樣輸出的結(jié)果就不對(duì)。還有就是棋盤(pán)走過(guò)的位置要標(biāo)記一下，以便下次走不重復(fù)走，當(dāng)回溯的時(shí)候的記得把標(biāo)記給清掉，這個(gè)地方有時(shí)候也很容易混淆。、還有一點(diǎn)就是，該程序運(yùn)算量大，算法復(fù)雜度高，所以運(yùn)行的時(shí)候很慢，特別占內(nèi)存，CPU的使用也很高，幾乎都在70喉IJ90沱間，配置

14、低了可能還運(yùn)行不了。六、運(yùn)行結(jié)果結(jié)果1：PieriseInptit±n1:SAnd-fi>IliHJUtjc41npuTiftQin29*361538433-11727394635IS512833181437444?-42312&294b心F1E3NG2134041Gd532257iRAl5ft22ss明1257R5E572<3yG11E>042156ain寫(xiě)Jko七口cor>：d_nu>c結(jié)果2:PJ.o-Ei.aoimpi.mpoi.'tpo土ntCl<Xndl1nputIiikju.1bolnx=3j/92442Jb>o

15、e55T251621223s264332417&42?&222135G634457ZB6116ES3非59G41229V344與b2!3VGid直g!>H4G3?32946£301133R473R311PI”14anjpkRytrocontzJviui#七、實(shí)驗(yàn)體會(huì)通過(guò)本次實(shí)驗(yàn)的編寫(xiě)，能夠掌握棧的性質(zhì)以及它的應(yīng)用。這次實(shí)驗(yàn)花了很多時(shí)間才完成，其實(shí)本應(yīng)該早完成的，在檢查的過(guò)程中有多多少少修改完美了一下，不過(guò)算法思想?yún)s沒(méi)有改變。這個(gè)程序也讓我頭疼了幾次，就是運(yùn)行速度很慢，要等很久才能輸出結(jié)果，這樣的話(huà)很占內(nèi)存資源，而且CPU的使用記錄也很高，主要是它需要的運(yùn)算太多，所以CPU使用記錄也是很高的。雖然我也參考了一些優(yōu)化的算法，可以找到最優(yōu)路進(jìn)走，但是這些最優(yōu)算法都和棧的應(yīng)用