數(shù)據(jù)結構集中上機試驗報告

1、XX大學信息與計算科學專業(yè)2008級數(shù)據(jù)結構集中上機設計題目：迷宮求解（非遞歸求解）設計時間：2010-2011學年第一學期姓名班級學號成績目錄一、實驗內容2.二、需求分析2.三、總體設計2.（一）存儲結構2.（二）流程圖3.四、詳細設計3.（一）基本算法解析3.（二）為實現(xiàn)算法，需要的象的數(shù)據(jù)類型 4.（三）函數(shù)的調用關系5.（四）算法時間、空間復雜度 5.五、代碼 5六、運行結果分析1.0.（一）迷宮路徑探索成功1.0（二）迷宮路徑未找到的情況1.3（三）程序的優(yōu)缺點與改進1.3七、參考文獻1.4.八、心得體會1.4.任務：可以輸入一個任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷 宮的

2、路徑，并將路徑輸出。:、需求分析1、可以輸入一個任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出；要求使用非遞歸算法。2、用戶可以根據(jù)自己的需求進行輸入所需的迷宮，其中1 表示迷宮的墻壁，0表示迷宮的通路，從而建立迷宮。3、可以自行輸入迷宮的入口和出口坐標。4、程序執(zhí)行的命令包括：（1）構造棧函數(shù)。其中包括了構造空棧InitStack;壓入新數(shù)據(jù)元素Push；棧頂元素出棧Pop。（ 2）構造求迷宮路徑函數(shù)。其中定義了二維數(shù)組mazeMN 存取迷宮數(shù)據(jù)；輸出找到的通路MazePath。（3）建立一個迷宮initmaze。其中包括輸入迷宮行數(shù)列數(shù)以及各行各列；加一圈圍墻并輸出

3、迷宮。三、總體設計（一）存儲結構首先用二維數(shù)組存儲迷宮數(shù)據(jù)，迷宮數(shù)據(jù)由用戶輸入。一個以鏈表結構作存儲結構的棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組（i,j,d）形式輸出，其中（i,j）指示迷宮中的一個坐標，d表示走到下一坐標的方向（東南西北所用代表數(shù)字，自行定義）。1從入口出發(fā)，順著某一個方向進行探索，若能走通，繼續(xù)往前走，否則沿原路退回，換一個方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到但沒能到達出口，則所設置的迷宮沒有通路。迷宮的入口點的下標（a,b） ，出口點的下標（m,n） 。為方便，可在迷宮周圍加一周障礙。對于迷宮的任意位置，均可約定有東西

4、南北4 個方向可以走通。經過的位置把0 變成 -1，輸出迷宮路徑。2 本程序有三個模塊;（1） 主程序模塊（2） 三個模塊即其對象，實現(xiàn)棧鏈表抽象數(shù)據(jù)類型（3） 迷宮存儲迷宮，尋路徑，輸出迷宮。（二）流程圖四、詳細設計（一）基本算法解析：首先用二維數(shù)組存儲迷宮數(shù)據(jù)，迷宮數(shù)據(jù)由用戶輸入。一個以鏈表結構作存儲結構的棧類型， 然后編寫一個求解迷宮的非遞歸程序。 求 得的通路以三元組（i,j,d）形式輸出，其中（i,j）指示迷宮中的一個坐標，d表示走到下一坐標的方向（東南西北所用代表數(shù)字，自行定義）迷宮的過程可以模擬成一個搜索的過程。每到一處，總讓它按東西南北四個方向順序試探下一個位置，如果某方向可以

5、通過，并且不曾到達，則前進一步，在新的位置上繼續(xù)進行探索。如果 4 個方向都走不通或者曾經到達過，則退回一步，在原來的位置上繼續(xù)試探下一位置。每前進一步或后退一步，都要進行判斷，若前進到了出口處，則說明找到了一條通路，若退回到了入口處，則說明不存在通路。用一個二維指針數(shù)組迷宮表示迷宮，數(shù)組中每個元素取值“0”（表示通路）或“1”（表示墻壁）。迷宮的入口點在位置（a,b）處，出口點在位置（m,n）處。設計一個模擬走迷宮的算法，為期尋找一條從入口點到出口點的通路。二維數(shù)組的0 行 m+1 列元素全置成“1”，表示迷宮的外墻，第一行第一列元素和第 m 行 m 列元素置成“0”，表示迷宮的入口和出口。

6、假設當前所在位置是（x,y） 。延某個方向前進一步，它可能到達的位置最多有 4。如果用結構體Element elem記錄4方向上行下標增量和列下標增量，則沿第i個方向前進一步，可能到達的新位置坐標可利用結構體Element elem確定while（!StackEmpty（S1） /棧不為空有路徑可走Pop（S1,elem）;i=elem.x;j=elem.y;d=elem.d+1;從迷宮的入口位置開始，沿圖示方向順序依次進行搜索。定義一個棧，按從入口到出口存取路徑，在搜索過程中，每前進一步，如果有新位置入棧，則把上一個探索的位置存入棧中，當前位置“-1”（表示這個位置在通路上），并將該位置的坐

7、標壓入棧中。如果沒有新位置入棧，則返回到上一個位置。一直到達出口。總之，入口出發(fā)，順著某一個方向進行探索，若能走通，則繼續(xù)往前進，否則沿著原路返回，換一個方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達出口，則所設定的迷宮沒有通路。迷宮的入口點在位置（1,1） ，出口點在位置（m,n） 。為處理方便，可在迷宮的四周加一周障礙。對于迷宮的任一位置，均可定為東南西北四個方向可通。（二）為實現(xiàn)算法，需要的象的數(shù)據(jù)類型InitStack（）構造空棧StackEmpty（）判斷棧是否為空Push（） 壓入新數(shù)據(jù)元素Pop（） 棧頂元素出棧m 迷宮的行數(shù)n 迷宮的列數(shù)d 0=

8、東 1=南2=西3=北typedef struct Lstack 鏈棧Element elem;struct LStack *next;*PLStack;（三）函數(shù)的調用關系mainmazePathInitStack Push Popinitmaze（四）算法時間、空間復雜度1）本算法在空間上主要開辟了一個二維數(shù)組， 規(guī)模都是迷宮（m+2） * （n+2）。 一個是棧，一個是迷宮路徑記錄，輸入時候調用棧。2）在時間上為簡單的鏈表棧的存儲結構，二維指針initmaze函數(shù)算法時間復雜度為 O （m+2） * （n+2）, Mazepath為 O （1）, （m 為行數(shù) n 為列數(shù)）。五、代碼/*

9、以一個m*n的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙，設計一 個程序對任意設定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結 論。首先實現(xiàn)一個以鏈表結構作存儲結構的棧類型，然后編寫一個求解迷宮的非 遞歸程序。求得的通路以三元組（i,j,d）形式輸出，其中（i,j）指示迷宮中的一 個坐標，d表示走到下一坐標的方向。*/#include<stdio.h>#include<stdlib.h>#define M 15#define N 15struct mark /定義迷宮內點的坐標類型 int x;int y;struct Element /棧元素 int

10、x,y; /x 行 ,y 列int d; /d 下一步的方向;typedef struct LStack /鏈棧 Element elem;struct LStack *next;*PLStack;/*棧函數(shù) */int InitStack(PLStack &S)構造空棧S=NULL;return 1;int StackEmpty(PLStack S)/R 斷棧是否為空if(S=NULL)return 1;elsereturn 0;int Push(PLStack &S, Element e)/£E 入新數(shù)據(jù)元素PLStack p;p=(PLStack)malloc(

11、sizeof(LStack);p->elem=e;p->next=S;S=p;return 1;int Pop(PLStack &S,Element &e) /棧頂元素出棧 PLStack p;if(!StackEmpty(S)e=S->elem;p=S;S=S->next;free(p);return 1;elsereturn 0;/* 求迷宮路徑函數(shù)*/void MazePath(struct mark start,struct mark end,int mazeMN,int diradd42) int i,j,d;int a,b;Element e

12、lem,e;PLStack S1, S2;InitStack(S1);InitStack(S2);mazestart.xstart.y=2; /入口點作上標記 elem.x=start.x; elem.y=start.y;elem.d=-1; /開始為-1Push(S1,elem);while(!StackEmpty(S1) /棧不為空有路徑可走 Pop(S1,elem); i=elem.x; j=elem.y; d=elem.d+1; /下一個方向 while(d<4) /試探東南西北各個方向 a=i+diraddd0; b=j+diraddd1;if(a=end.x &&am

13、p; b=end.y && mazeab=0) / 如果到了出口 elem.x=i;elem.y=j; elem.d=d; Push(S1,elem);elem.x=a;elem.y=b;elem.d=886; /方向輸出為-1 判斷是否到了出口Push(S1,elem);printf("n0=東1=南2=西3二北886為則走出迷宮nn通路為:(行坐標，列坐標，方 向 )n");while(S1) /逆置序列并輸出迷宮路徑序列 Pop(S1,e); Push(S2,e); while(S2) Pop(S2,e); printf("->(%d,

14、%d,%d)",e.x,e.y,e.d); return; /跳出循環(huán) if(mazeab=0) /找到可以前進的非出口的點mazeab=2; /標記走過此點 elem.x=i; elem.y=j; elem.d=d;Push(S1,elem); /當前位置入棧/ i=a; /下一點轉化為當前點 j=b; d=-1; d+; printf(" 沒有找到可以走出此迷宮的路徑n");/* 建立迷宮*/void initmaze(int mazeMN)int i,j;int m,n; /迷宮行,列 /Mprintf(" 請輸入迷宮的行數(shù)m=");sc

15、anf("%d",&m);printf(" 請輸入迷宮的列數(shù)n=");scanf("%d",&n);printf("n 請輸入迷宮的各行各列:n 用空格隔開,0代表路 ,1 代表墻 n",m,n);for(i=1;i<=m;i+)for(j=1;j<=n;j+)scanf("%d",&mazeij);printf(" 你建立的迷宮為(最外圈為墻).n");for(i=0;i<=m+1;i+) / 加一圈圍墻mazei0=1;mazei

16、n+1=1;for(j=0;j<=n+1;j+)maze0j=1;mazem+1j=1;for(i=0;i<=m+1;i+) / 輸出迷宮for(j=0;j<=n+1;j+)printf("%d ",mazeij);printf("n");void main()int stoMN;struct mark start,end; start,en隊口 和出口 的坐標int add42=0,1,1,0,0,-1,-1,0;/ 行增量和列增量方向依次為東西南北/Minitmaze(sto);/建立迷宮printf(" 輸入入口的橫坐標

17、,縱坐標逗號隔開n");scanf("%d,%d",&start.x,&start.y);printf(" 輸入出口的橫坐標,縱坐標逗號隔開n");scanf("%d,%d",&end.x,&end.y);MazePath(start,end,sto,add); /find path system("PAUSE");六、運行結果分析（一）迷宮路徑探索成功初始界面武七、工語言程序L3Debu叭134k 清輸;'迷官的行數(shù)門.測試數(shù)據(jù)迷宮6行（輸入“6”點擊Enter得

18、到下一界面）測試數(shù)據(jù)迷宮8列（輸入“ 8”點擊Enter得到下一界面）測試數(shù)據(jù)6 行 8 列迷宮0 1 0 1 1 0 1 10 0 1 1 1 0 1 01 0 1 1 0 1 0 01 0 0 0 1 0 1 10 0 0 1 1 1 1 01 1 0 0 1 0 1 1（輸入上述迷宮，點擊Enter得到下一界面）測試數(shù)據(jù)迷宮入口（1,1）（輸入“ 1, 1”點擊Enter得到下一界面）測試數(shù)據(jù)迷宮出口（ 6,3（輸入“6, 3”點擊Enter得到下一界面）如上圖，我們可以得到：當迷宮為0 1 0 1 1 0 1 10 0 1 1 1 0 1 01 0 1 1 0 1 0 01 0 0 0

19、 1 0 1 10 0 0 1 1 1 1 01 1 0 0 1 0 1 1迷宮入口為（1,1）出口為（6,3）時迷宮路徑為，（括號內的內容分別表示為（行坐標，列坐標，數(shù)字化方向（0=東1=南2=西3=北）< <1,1,1> *<2,1,0> * <2,2,1> * <3,2,1> < <4,2,0> -k<4,3,1<5,3,1> <6,3,886>迷宮路徑探索成功！（二）迷宮路徑未找到的情況在上述測試的數(shù)據(jù)當中，我們把迷宮出口改為（6,5）得到的運行結果如下圖:（三）程序的優(yōu)缺點與改進1、

20、該程序在輸出上顯得有些繁瑣。更改方向可以考慮用一個二維數(shù)組來記錄4方向上行下標增量和列下標增量，則沿第i個方向前進一步，可能到達的新位置 坐標可以利用該數(shù)組確定；2、輸出時可以考慮編寫一個輸出函數(shù)，到時直接調用這個輸出函數(shù)就好。假如恢復迷宮函數(shù)，輸出迷宮路徑后再恢復迷宮原始位置；3、對于手動輸入，如果迷宮數(shù)據(jù)太大時，就很麻煩，而且很費時間，可以用隨 機產生函數(shù)，自動生成迷宮。七、參考文獻1、 數(shù)據(jù)結構C 語言 嚴蔚敏 清華大學出版社20022、 C 語言程序設計譚浩強 清華大學出版社20053、 C 語言通用范例開發(fā)金典柳盛2008八、心得體會為期大半學期的數(shù)據(jù)結構的集中上機接近尾聲，在這大半

21、學期里，雖然最后只做了一道題，但真的學到很多。通過兩年來的學習，我覺得這樣的集中上機是非常有意義的。數(shù)據(jù)結構是學習計算機的必學課程，是信息與計算科學專業(yè)的一門主要專業(yè)基礎課程，通過這次實驗上機我們學會在VC 的環(huán)境下去實現(xiàn)數(shù)據(jù)結構中的算法。在學習了理論知識之后，如何去具體的處理數(shù)據(jù)結構中編程的問題，如何把我們的理論運用到實踐中去，這樣的集中上機為我們提供了這樣一個實踐平臺。通過這次實驗，我收獲頗多。首先是對C 語言的認識有了進一步的提升。過這次上機實驗對數(shù)據(jù)結構有了更進一步的鞏固。其次， 通過這次上機實驗，我對非遞歸算法有了更深一層的理解。 在做本次課程設計的過程中我感觸最深的當屬查閱書籍，為了讓自己的設計更加完善，更加符合標準一次次的翻閱相關書籍瀏覽網(wǎng)頁是十分必要的。要很要的掌握編程不能僅僅通過幾個簡單的程序編寫，更需要大量積累和深入才可能。求迷宮路徑需要使用鏈表的棧，靠進棧和出棧來存取路徑數(shù)據(jù)，在編寫程序時，帶著問題去反