《數(shù)據(jù)結(jié)構(gòu)》課程設計總結(jié)

《數(shù)據(jù)結(jié)構(gòu)》課程設計報告題目：老鼠走迷宮班級：姓名：學號：指導教師：__日期：2010年7月一、課程設計目標1、問題描述本程序是利用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出。首先由用戶輸入一組二維數(shù)組來組成迷宮，確認后程序自動運行，當迷宮有完整路徑可以通過時，以0和1所組成的迷宮形式輸出，標記所走過的路徑結(jié)束程序；當迷宮無路徑時，提示輸入錯誤結(jié)束程序。2、問題分析1.抽象數(shù)據(jù)類型定義：ADTFind{數(shù)據(jù)對象：D={ai?ai∈ElemSet,i=1,2,…,n,n≥0}數(shù)據(jù)關系：R1={<ai-1,ai>?ai-1,ai∈D}基本操作：

find(&S)初始條件：已初始化棧S，且棧為空操作結(jié)果：從棧Ｓ中找出相對應的數(shù)據(jù)關系，并輸出結(jié)果}ADTFind2.主程序的流程以及各程序模塊之間的調(diào)用關系：(1).定義變量i、j、w、z為整形變量(2).輸入迷宮二維數(shù)組maze(0:m,0:n)(3).調(diào)用子程序find()(4).結(jié)束程序二、概要設計1、方案確定多個函數(shù)進行組合，有顯示圖形函數(shù)、方向函數(shù)、自動創(chuàng)建迷宮函數(shù)、手動創(chuàng)建迷宮函數(shù)，迷宮的大小創(chuàng)建！2、程序設計模塊設計連接圖界面顯示模塊界面顯示模塊路徑顯示模塊判斷路徑模塊自動創(chuàng)建模塊手動創(chuàng)建模塊尺寸設計模塊3、模塊功能描述1、尺寸設計模塊：確定界面大??；2、自動創(chuàng)建模塊：自動創(chuàng)建游戲界面；3、手動創(chuàng)建模塊：手動創(chuàng)建游戲界面；4、打印游戲界面（基于DOS）;5、判斷路徑模塊：判斷是否為通路；6、路徑顯示模塊：打印通路；三、詳細設計1、方法設計本程序主要用到了堆棧的出棧與入棧算法，在走迷宮的時候用到查找的相關知識，來判斷路徑問題，通過人機對話街界面，實現(xiàn)手動與隨機兩種方式生成迷宮界面，讓程序更加人性化，增強了程序的可操行，通過功能函數(shù)的調(diào)用，將各個模塊聯(lián)系起來，實現(xiàn)整體的功能結(jié)合，以實現(xiàn)最終的整體效果。2、程序流程圖圖2輸入矩陣尺寸圖2輸入矩陣尺寸判斷尺寸創(chuàng)建方式主程序（判斷路徑）打印路徑>10或<0<=10和>=1隨即創(chuàng)建手動創(chuàng)建路徑不通提示錯誤四、程序清單#include<stdio.h>#include<stdlib.h>typedefenum{ERROR,OK}Status;//枚舉類型的創(chuàng)立typedefstruct{introw,line;//定義行列}PosType;typedefstruct{intdi,ord;PosTypeseat;}SElemType;typedefstruct{SElemType*base;//定義基部SElemType*top;//定義頭部intstacksize;}SqStack;StatusInitStack(SqStack&S);StatusPush(SqStack&S,SElemType&a);//數(shù)據(jù)入棧StatusPop(SqStack&S,SElemType&a);//數(shù)據(jù)出棧StatusStackEmpty(SqStackS);StatusMazePath(intmaze[12][12],SqStack&S,PosTypestart,PosTypeend);//創(chuàng)建一個棧voidInitmaze(intmaze[12][12],intsize);voidprintmaze(intmaze[12][12],intsize);StatusvoidMarkfoot(intmaze[12][12],PosTypeCurPos);PosTypeNextPos(PosTypeCurPos,intDir);voidprintpath(intmaze[12][12],SqStackS,intsize);//迷宮的建立voidmain(){SqStackS;intsize,maze[12][12];for(intn=0;n<10;n++){printf("創(chuàng)建一個正方形迷宮，請輸入迷宮尺寸(注意不要大于10):\n");scanf("%d",&size);if(size<1||size>10){printf("輸入錯誤!");return;}Initmaze(maze,size);printmaze(maze,size);PosTypestart,end;printf("輸入入口行坐標和列坐標:");scanf("%d",&start.row);scanf("%d",&start.line);printf("輸入出口行坐標和列坐標:");scanf("%d",&end.row);scanf("%d",&end.line);if(MazePath(maze,S,start,end))printpath(maze,S,size);elseprintf("找不到通路!\n\n");}}StatusMazePath(intmaze[12][12],SqStack&S,PosTypestart,PosTypeend){PosTypecurpos;intcurstep;SElemTypee;InitStack(S);curpos=start;curstep=1;//定義初始化do{if(Pass(maze,curpos)){Markfoot(maze,curpos);e.di=1;e.ord=curstep;e.seat=curpos;Push(S,e);if(curpos.row==end.row&&curpos.line==end.line)returnOK;curpos=NextPos(curpos,1);curstep++;}//查找成功，繼續(xù)找下一個通路else{if(!StackEmpty(S)){Pop(S,e);while(e.di==4&&!StackEmpty(S)){Markfoot(maze,e.seat);Pop(S,e);}if(e.di<4){e.di++;Push(S,e);curpos=NextPos(e.seat,e.di);}}}}while(!StackEmpty(S));returnERROR;//查找不成功，退回上一個通路位置}voidInitmaze(intmaze[12][12],intsize)<我所負責>{charselect;printf("選擇創(chuàng)建方式A:自動生成B:手動創(chuàng)建\n");label:scanf("%c",&select);if(select=='a'||select=='A'){for(inti=0;i<size+2;i++)maze[0][i]=1;for(i=1;i<size+1;i++){maze[i][0]=1;for(intj=1;j<size+1;j++)maze[i][j]=rand()%2;maze[i][size+1]=1;}for(i=0;i<size+2;i++)maze[size+1][i]=1;}//自動創(chuàng)建迷宮的算法elseif(select=='b'||select=='B'){printf("按行輸入%d*%d數(shù)據(jù),0代表可通,1代表不可通(每行以Enter結(jié)束):\n",size,size);for(inti=0;i<size+2;i++)maze[0][i]=1;for(i=1;i<size+1;i++){maze[i][0]=1;for(intj=1;j<size+1;j++)scanf("%d",&maze[i][j]);maze[i][size+1]=1;}for(i=0;i<size+2;i++)maze[size+1][i]=1;}elseif(select=='\n')gotolabel;elseprintf("輸入錯誤!");}//手動創(chuàng)建迷宮過程voidprintmaze(intmaze[12][12],intsize){printf("\n\n");printf("顯示所建的迷宮(#表示外面的墻):\n");for(inti=0;i<size+2;i++)printf("%c",'#');printf("\n");for(i=1;i<size+1;i++){printf("%c",'#');for(intj=1;j<size+1;j++){printf("%d",maze[i][j]);}printf("%c",'#');printf("\n");}for(i=0;i<size+2;i++)printf("%c",'#');printf("\n");}//顯示外面墻的算法voidprintpath(intmaze[12][12],SqStackS,intsize){printf("\n\n通路路徑為:\n");SElemType*p=S.base;while(p!=S.top){maze[p->seat.row][p->seat.line]=2;p++;}for(inti=0;i<size+2;i++)printf("%c",'#');printf("\n");for(i=1;i<size+1;i++){printf("%c",'#');for(intj=1;j<size+1;j++){if(maze[i][j]==2)printf("%c",'0');elseprintf("");}printf("%c",'#');printf("\n");}for(i=0;i<size+2;i++)printf("%c",'#');printf("\n\n");}//創(chuàng)建邊線，便于操作</我所負責>Status{if(maze[CurPos.row][CurPos.line]==0)returnOK;elsereturnERROR;}voidMarkfoot(intmaze[12][12],PosTypeCurPos){maze[CurPos.row][CurPos.line]=1;}PosTypeNextPos(PosTypeCurPos,intDir){PosTypeReturnPos;switch(Dir)//定義四個方向{case1:ReturnPos.row=CurPos.row;ReturnPos.line=CurPos.line+1;break;//判斷老鼠是否能向右走case2:ReturnPos.row=CurPos.row+1;ReturnPos.line=CurPos.line;break;//判斷老鼠是否能向下走case3:ReturnPos.row=CurPos.row;ReturnPos.line=CurPos.line-1;break;//判斷老鼠是否能向左走case4:ReturnPos.row=CurPos.row-1;ReturnPos.line=CurPos.line;break;//判斷老鼠是否能向上走}returnReturnPos;}StatusInitStack(SqStack&S){S.base=(SElemType*)malloc(100*sizeof(SElemType));if(!S.base)returnERROR;S.top=S.base;S.stacksize=100;returnOK;}StatusPush(SqStack&S,SElemType&a){*S.top++=a;returnOK;}StatusPop(SqStack&S,SElemType&a){if(S.top==S.base)returnERROR;a=*--S.top;returnOK;}StatusStackEmpty(SqStackS){if(S.top==S.base)returnOK;returnERROR;}//顯示