迷宮求解數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)

頁(yè)需求分析以二維數(shù)組maze[n+2][m+2]表示迷宮，其中：maze[0][j]和maze[n+1][j](0<=j<=m+1)及maze[i][0]和maze[i][m+1](0<=i<=j+1)為添加的一圈障礙。數(shù)組中以元素值為0的表示通路，1表示障礙，限定迷宮的大小，m，n<=0。迷宮的入口位置和出口位置可由用戶自行設(shè)定。如設(shè)定的迷宮處在通路，則值輸出迷宮中的通路，即0，現(xiàn)實(shí)的0連起來(lái)就是一個(gè)迷宮通路路徑；如設(shè)定的迷宮中不出在通路，則輸出“該迷宮找不到通路!”；測(cè)試樣例：輸入迷宮的長(zhǎng)寬為5和6，輸入迷宮為：100111001111100011010111110000當(dāng)入口位置為（1,2），出口位置為（5,6）時(shí)，則輸出數(shù)據(jù)為：#########0##0##00##0##0000#########程序執(zhí)行的命令為：輸入迷宮的尺寸；2、創(chuàng)建迷宮；3、輸入迷宮的的出入口位置；4、求解迷宮；輸出迷宮的解。概要設(shè)計(jì)2.1.數(shù)據(jù)結(jié)構(gòu)2.1.1、邏輯結(jié)構(gòu)1）棧的定義：限定僅在表尾進(jìn)行插入或刪除操作的線性表；2）操作特性：后進(jìn)先出;3)ADT定義：ADTStack{數(shù)據(jù)對(duì)象：D={ai|ai∈CharSet,i=1,2,…,n,n>=0}數(shù)據(jù)關(guān)系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,…,n}基本操作：InitStack(&S)操作結(jié)果：構(gòu)造一個(gè)空棧S。DestroyStack（&S）初始條件：棧S已存在。操作結(jié)果：銷毀棧S。ClearStack(&S)初始條件：棧S已存在。操作結(jié)果：將S清為空棧。StackLength(&S)初始條件：棧S已存在。操作結(jié)果：返回棧S的長(zhǎng)度。StackEmpty(&S)初始條件：棧S已存在。操作結(jié)果：若S為空棧，則返回TRUE，否則返回FALSE。GetTop(S,&e)初始條件：棧S已存在。操作結(jié)果：若棧S不空，則以e返回棧頂元素。Push(&S,e)初始條件：棧S已存在。操作結(jié)果：在棧S的棧頂插入新的棧頂元素e。Pop(&S,&e)初始條件：棧S已存在。操作結(jié)果：刪除S的棧頂元素，并以e返回其值。StackTraverse(S,visit())初始條件：棧S已存在。操作結(jié)果：從棧底到棧頂依次對(duì)S中的每個(gè)元素調(diào)用函數(shù)visit()。}ADTStack2.1.2、存儲(chǔ)結(jié)構(gòu)1）順序存儲(chǔ)結(jié)構(gòu)：順序棧：是利用一塊地址連續(xù)的存儲(chǔ)單元來(lái)存放棧中的元素，同時(shí)要利用一個(gè)指針top來(lái)指示棧頂元素的位置。注：在本迷宮求解程序設(shè)計(jì)中用到的就是棧的順序存儲(chǔ)結(jié)構(gòu)。//棧的順序存儲(chǔ)表示#defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)綏＃烘湕Ｊ侵覆捎面準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)的棧。鏈棧是一種特殊的單鏈表，即限定僅在表頭進(jìn)行插入和刪除操作的單鏈表，因此鏈棧的結(jié)點(diǎn)結(jié)構(gòu)與單鏈表的結(jié)點(diǎn)結(jié)構(gòu)相同。2.2、基本操作2.2.1、迷宮中棧的基本操作：基本操作：InitStack(&S)操作結(jié)果：構(gòu)造一個(gè)空棧S。StackEmpty(&S)初始條件：棧S已存在。操作結(jié)果：若S為空棧，則返回TRUE，否則返回FALSE。GetTop(S,&e)初始條件：棧S已存在。操作結(jié)果：若棧S不空，則以e返回棧頂元素。Push(&S,e)初始條件：棧S已存在。操作結(jié)果：在棧S的棧頂插入新的棧頂元素e。Pop(&S,&e)初始條件：棧S已存在。操作結(jié)果：刪除S的棧頂元素，并以e返回其值。2.2.2、迷宮的抽象數(shù)據(jù)類型ADTMazeType{數(shù)據(jù)對(duì)象:D={ai,j|ai,j∈{‘’,‘#’、‘@’、‘*’}，0<=i<=n+1,0<=j<=m+1,m,n<=20} 數(shù)據(jù)關(guān)系:R={ROW,LINE}ROW={<ai-1,j,ai,j>|ai-1,j,ai,j∈D,i=1,…,m+1,j=0,…,n+1}LINE={<ai-1,j,ai,j>|ai-1,j,ai,j∈D,i=1,…,m+1,j=0,…,n+1} 基本操作:StatusPass(MazeType&maze,PosTypecurpos) 初始條件:maze存在迷宮,curpos保存了當(dāng)前位置的坐標(biāo) 操作結(jié)果:如果可通,返回真,否則為假voidFootPrint(MazeType&maze,PosTypecurpos) 初始條件:maze存在迷宮,curpos保存了當(dāng)前位置的坐標(biāo) 操作結(jié)果:將當(dāng)前坐標(biāo)curpos處的maze[][]值記為足跡PosTypeNextPos(PosTypeCurPos,intdi) 初始條件:各參數(shù)值已經(jīng)定義操作結(jié)果:求得以當(dāng)前位置為棧頂?shù)南乱粋€(gè)方向的元素的坐標(biāo)StatusMazePath(SqStack&S,PosTypestart,PosTypeend) 初始條件:maze存在迷宮地圖操作結(jié)果:為建立的迷宮找到一條路徑}ADTmaze;2.2.3、本程序包含三個(gè)模塊1）主函數(shù)模塊：intmain（）{初始化迷宮；求解迷宮；輸出迷宮的解；return0；}2）棧實(shí)現(xiàn)模塊—實(shí)現(xiàn)棧的抽象殊絕類型3）迷宮實(shí)現(xiàn)模塊—實(shí)現(xiàn)迷宮的抽象數(shù)據(jù)類型各模塊的調(diào)用關(guān)系如下：主函數(shù)模塊——>迷宮模塊——>棧模塊4）求解迷宮中一條通路的偽碼算法：設(shè)定當(dāng)前位置的初值為入口位置；do{ 若當(dāng)前位置可通， 則{將當(dāng)前位置插入棧頂；//納入路徑 若該位置是出口位置，則結(jié)束；//求得路徑存放在棧中 否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置；}否則{若棧不空且棧位置尚有其他方向未被探索，則設(shè)定新的當(dāng)前位置為沿順時(shí)針方向旋轉(zhuǎn)找到的棧頂位置的下一相鄰塊；若棧不空但棧頂位置的四周均不可通，則{刪去棧頂位置；//后退一步，從路徑中刪去該通道塊；若棧不空，則重新測(cè)試新的棧頂位置；直到找到一個(gè)可通的相鄰塊或出棧至?？眨粆}}while(棧不空)；{棧空說(shuō)明沒有路徑存在}詳細(xì)設(shè)計(jì)坐標(biāo)位置類型typedefstruct{ introw; intline;}PosType;迷宮類型StatusPass(PosTypeCurPos)//判定當(dāng)前位置是否可以通過(guò)，即是未曾走到過(guò)的通道塊voidFootPrint(PosTypeCurPos)//給當(dāng)前可通過(guò)的位置標(biāo)記PosTypeNextPos(PosTypeCurPos,intdi)//探尋下一個(gè)位置，并標(biāo)記方向StatusMazePath(SqStack&S,PosTypestart,PosTypeend)//求解迷宮maze中，從入口start到出口end的一條路徑，//如存在，返回OK，否則返回ERROR棧類型typedefstruct{ intord;//通道塊在路徑上的“序號(hào)” intdi;//通道塊在迷宮中的“坐標(biāo)位置” PosTypeseat;//從此通道塊走向下一通道塊的“方向”}SElemType;//棧的元素類型typedefstruct{ SElemType*base;//在構(gòu)造棧之前和銷毀之后，base的值為NULL SElemType*top;//棧頂指針 intstacksize;//當(dāng)前已分配的存儲(chǔ)空間，以元素為單位}SqStack;//棧定義棧的基本操作如下：voidInitStack(SqStack&S)//初始化棧，設(shè)棧S為空棧（S.top=NULL）voidPush(SqStack&S,SElemTypee)//若分配空間成功，則在S的棧頂插入新的棧頂元素e//否則增加棧棧的存儲(chǔ)空間，再插入新的元素intGetTop(SqStack&S,SElemTypee)//若棧S不空，則以e帶回棧頂元素并返回TRUE，否則返回FALSEintPop(SqStack&S,SElemType&e)//若棧不空，則刪除S的棧頂元素并以e帶回其值，且返回TRUE//否則返回FALSEintStackEmpty(SqStackS)//若S為空棧（S.top==NULL），則返回TRUE；否則返回FALSE具體部分操作的算法如下：voidInitStack(SqStack&S){//初始化棧S為空棧（S.top=NULL） S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base)exit(OVERFLOW); S.top=S.base; S.stacksize=STACK_INIT_SIZE;}//InitstackvoidPush(SqStack&S,SElemTypee){//若分配空間成功，則在S的棧頂插入新的棧頂元素e//否則增加棧棧的存儲(chǔ)空間，再插入新的元素 if(S.top-S.base>=S.stacksize) { S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!S.base)exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e;}//Push求解迷宮的偽碼算法：StatusMazePath(SqStack&S,PosTypestart,PosTypeend){//若迷宮maze中存在從入口start到出口end的通道，則//一條存放在棧中(從棧底到棧頂為從入口到出口的路徑)，并返//回OK，否則返回ERROR PosTypecurpos; intcurstep; SElemTypee; InitStack(S); curpos=start;//設(shè)定“當(dāng)前位置”為“初始位置” curstep=1;//探索第一步 do{ if(Pass(curpos)) {//當(dāng)前位置可以通過(guò)，即是未曾走到過(guò)的的通道塊//留下足跡 FootPrint(curpos); e.di=1; e.ord=curstep; e.seat=curpos; Push(S,e);//加入路徑 if(curpos.row==end.row&&curpos.line==end.line)returnOK;//到達(dá)出口位置 curpos=NextPos(curpos,1); curstep++;//探索下一步 } else//當(dāng)前位置不能通過(guò) { if(!StackEmpty(S)) { Pop(S,e); while(e.di==4&&!StackEmpty(S)) { FootPrint(e.seat); Pop(S,e);curstep--； } if(e.di<4) { e.di++; Push(S,e); curpos=NextPos(e.seat,e.di); }//if }//if } }while(!StackEmpty(S)); returnERROR;}//MazePath主函數(shù)和其它函數(shù)的偽碼算法voidprintpath(SqStackS,intn,intm){//打印路徑 printf("\n\n通路路徑為:\n"); //PosTypestart,end;SElemType*p=S.base;//定義一個(gè)指針p指向棧中的元素，設(shè)//定初值為p=S.base while(p!=S.top) { maze[p->seat.row][p->seat.line]=2; p++;//將有效路徑的通道塊全部標(biāo)記為2或其他不為1或0的//值 } inti,flag=0;//打印出路徑，周圍用“#”圍成一圈作圍墻 for(i=0;i<m+2;i++)printf("%c",'#');printf("\n"); for(i=1;i<n+1;i++) { printf("%c",'#'); for(intj=1;j<m+1;j++) { if(maze[i][j]==2)printf("%c",'0'); elseprintf(""); } printf("%c",'#'); printf("\n"); } for(i=0;i<m+2;i++)printf("%c",'#');printf("\n\n");}//printpathintmain(){//主函數(shù) SqStackS; intr,l; while(true) { printf("創(chuàng)建一個(gè)迷宮，請(qǐng)輸入迷宮長(zhǎng)和寬(不得大于20):\n"); scanf("%d%d",&r,&l);if(r<1||r>20||l<1||l>20){printf("輸入錯(cuò)誤!");} inti; printf("按行輸入%d*%d數(shù)據(jù)(0代表可通,1代表不可通):\n",r,l); for(i=0;i<l+2;i++)maze[0][i]=1; for(i=1;i<r+1;i++) { maze[i][0]=1; for(intj=1;j<l+1;j++) scanf("%d",&maze[i][j]); maze[i][l+1]=1; } for(i=0;i<l+2;i++)maze[r+1][i]=1; PosTypestart,end; printf("輸入入口行坐標(biāo)和列坐標(biāo):");scanf("%d",&start.row);scanf("%d",&start.line); printf("輸入出口行坐標(biāo)和列坐標(biāo):");scanf("%d",&end.row);scanf("%d",&end.line); if(MazePath(S,start,end)) printpath(S,r,l); elseprintf("該迷宮找不到通路!\n\n"); } return0;}//main調(diào)試分析1、在本次的程序設(shè)計(jì)中，最核心的算法就是MazePath()函數(shù)，其他的算法并沒有出現(xiàn)什么問(wèn)題。不過(guò)在最后輸出的時(shí)候本來(lái)想輸出路徑的先后順序，即maze[1][2]>maze[2][2]>maze[3][2]>maze[3][3]>maze[4][3]>maze[5][3]>maze[5][4]>maze[5][5]>maze[5][6]，但是最后發(fā)現(xiàn)這樣只有在入口在左上角，出口在右下角時(shí)，才可以正確輸出。但是入口和出口是隨機(jī)的，若是入口在右下角，出口在左上角，則也同樣輸出maze[1][2]>maze[2][2]>maze[3][2]>maze[3][3]>maze[4][3]>maze[5][3]>maze[5][4]>maze[5][5]>maze[5][6]，雖然這兩個(gè)路徑是一樣的，但是有先后順序，故最后沒有輸出這種形式，將這段代碼注釋了（源程序中有注釋的代碼）；2、本來(lái)是想設(shè)計(jì)成既可以手動(dòng)輸入迷宮又可以自動(dòng)生成迷宮，但是感覺沒有太大的用處，所以最后省略了，只保留了手動(dòng)輸入。3、在整個(gè)編寫的過(guò)程中，出現(xiàn)過(guò)很多錯(cuò)誤，包括一些標(biāo)點(diǎn)符號(hào)的小錯(cuò)誤，但是借助DEBUG調(diào)試器和數(shù)據(jù)觀察窗口，很快找出來(lái)問(wèn)題的所在。用戶手冊(cè)本程序的運(yùn)行環(huán)境為DOS操作系統(tǒng),執(zhí)行文件為：迷宮求解.exe.進(jìn)入演示程序后,即顯示文本方式的用戶界面:根據(jù)提示輸入迷宮大小及迷宮后,輸入迷宮的行和列,回車后即可得到所輸入迷宮的解或者是顯示“該迷宮找不到通路!”字樣。測(cè)試結(jié)果輸入長(zhǎng)寬為5，6，入口為（1,2），出口為（5,6）的迷宮100111001111100011010111110000求解結(jié)果：輸入長(zhǎng)寬為4，5，入口為（1,1），出口為（4,5）的迷宮01011001101011110000輸出結(jié)果為：輸入長(zhǎng)寬為4，5，入口為（1,1），出口為（4,5）的迷宮110111010101100011010111110000輸出結(jié)果為：附錄源程序文件名清單：主函數(shù).cpp迷宮的實(shí)現(xiàn).h棧的實(shí)現(xiàn).h參考文獻(xiàn)1、嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)[M].北京：清華大學(xué)出版社，2012.2、嚴(yán)蔚敏，吳偉民，米寧.數(shù)據(jù)結(jié)構(gòu)題集(C語(yǔ)言版)[M].北京：清華大學(xué)出版社，2012.3、蘇仕華，魏韋巍，王敬生，劉燕君.數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)[M].北京：機(jī)械工業(yè)出版社，2010.心得體會(huì)做了這次程序設(shè)計(jì)，我們發(fā)現(xiàn)利用數(shù)據(jù)結(jié)構(gòu)進(jìn)行程序設(shè)計(jì)并不像想像中的那么高深，像我們現(xiàn)在所做的，只是一些最基本的程序。經(jīng)過(guò)一個(gè)學(xué)期的學(xué)習(xí)，對(duì)數(shù)據(jù)結(jié)構(gòu)有了一個(gè)初步的認(rèn)識(shí)，但沒有進(jìn)行實(shí)際應(yīng)用。這次程序設(shè)計(jì)，就相當(dāng)于對(duì)一個(gè)學(xué)期的所學(xué)做一個(gè)總結(jié)，再進(jìn)行一次綜合運(yùn)用，更是學(xué)到了很多新的東西，無(wú)意中也提升了自己的程序設(shè)計(jì)水平；在程序設(shè)計(jì)過(guò)程中碰到了很多問(wèn)題，通過(guò)上網(wǎng)查資料等各種手段，我們的解決實(shí)際問(wèn)題的能力也得到了提高。這次的程序設(shè)計(jì)，讓我們對(duì)程序設(shè)計(jì)有了一個(gè)更全面的認(rèn)識(shí)，如果我們以后能在編程領(lǐng)域深入發(fā)展，這一次也算是我們邁出的重要一步吧。小組成員工作分配程序、文檔的編寫；程序校對(duì)及查找資料；文檔的勘誤及字體的調(diào)整。

本科生學(xué)位論文論多媒體技術(shù)在教學(xué)中的應(yīng)用姓名：指導(dǎo)教師：專業(yè)：教育管理專業(yè)年級(jí)：完成時(shí)間：

論多媒體技術(shù)在教學(xué)中的應(yīng)用[摘要]多媒體不再是傳統(tǒng)的輔助教學(xué)工具，而是為構(gòu)造一種新的網(wǎng)絡(luò)教學(xué)環(huán)境創(chuàng)造了條件，特別是對(duì)于教育社會(huì)化來(lái)說(shuō)，多媒體網(wǎng)絡(luò)是一種更理想的傳播工具。多媒體本身具有：融合性、非線性化，無(wú)結(jié)構(gòu)性、相互交涉性、可編輯性、實(shí)時(shí)性等特點(diǎn)；同時(shí)運(yùn)用在教育教學(xué)上又有其特長(zhǎng)：利于信息的存儲(chǔ)利用、是培養(yǎng)發(fā)散性思維的工具、促使學(xué)習(xí)個(gè)別化的實(shí)現(xiàn)。多媒體在教學(xué)中的應(yīng)用有著多種的形式，它在提高學(xué)生學(xué)習(xí)興趣上有著積極的作用，同時(shí)它還能促進(jìn)學(xué)生知識(shí)的獲取與保持、對(duì)教學(xué)信息進(jìn)行有效的組織與管理、建構(gòu)理想的學(xué)習(xí)環(huán)境，促進(jìn)學(xué)生自主學(xué)習(xí)等多方面的效果。立足未來(lái)發(fā)展，利用多媒體網(wǎng)絡(luò)技術(shù)，開展教學(xué)試驗(yàn)。[關(guān)鍵詞]多媒體網(wǎng)絡(luò)教學(xué)系統(tǒng)資源共享多媒體技術(shù)主要指多媒體計(jì)算機(jī)技術(shù)，加工、控制、編輯、變換，還可以查詢、檢索。人們借助于多媒體技術(shù)可以自然貼切地表達(dá)、傳播、處理各種視聽信息，并具有更多的參與性和創(chuàng)造性。當(dāng)今多媒體已成為廣泛流傳的名詞，但人們對(duì)于它的認(rèn)識(shí)，特別是對(duì)于它在教育教學(xué)方面如何更好應(yīng)用，未知的因素還很多。

一、多媒體的教育特長(zhǎng)任何一種媒體不管其怎樣先進(jìn)，它只能是作為一種工具被應(yīng)用到教育領(lǐng)域，能不能促進(jìn)教育的改革，。。。。。。應(yīng)當(dāng)吸取教訓(xùn)，加強(qiáng)理論研究，充分認(rèn)識(shí)多媒體的特性及其教育特長(zhǎng)，以便更好地在教育領(lǐng)域開發(fā)應(yīng)用多媒體。

1、多媒體的特性

（1）融合性多種符號(hào)系統(tǒng)的融合是多媒體的特性之一，多媒體的這一特性區(qū)別于過(guò)去媒體符號(hào)系統(tǒng)的單一性或復(fù)合性。也就是說(shuō)多媒體技術(shù)不是將符號(hào)系統(tǒng)疊加，而是具有整體性的融合。

（2）非線性化，無(wú)結(jié)構(gòu)性因?yàn)槎嗝襟w是在超文本、，其組合結(jié)構(gòu)是固定的、不變的。

（5）實(shí)時(shí)性多媒體信息中的聲音、活動(dòng)視瀕、動(dòng)畫于時(shí)間有密切聯(lián)系，對(duì)它們進(jìn)行呈現(xiàn)、交互等集成處理是實(shí)時(shí)的。在顯示某一主體內(nèi)容時(shí)，其視聽信息具有同步性。

2、多媒體的教育特長(zhǎng)

（1）信息的存儲(chǔ)利用便利多媒體特別是多媒體WWW網(wǎng)絡(luò)信息的存儲(chǔ)、提取、雙向傳輸非常便利，它應(yīng)用于教育，更利于教學(xué)信息傳播機(jī)制的建立。

（2）發(fā)散性思維的工具在培養(yǎng)學(xué)習(xí)者發(fā)散性思維方面…………或創(chuàng)造性思維的基礎(chǔ)。

（3）促使學(xué)習(xí)個(gè)別化的實(shí)現(xiàn)多媒體WWW網(wǎng)絡(luò)有利于個(gè)別化的實(shí)現(xiàn)。因?yàn)閷W(xué)習(xí)者各人需求、學(xué)習(xí)經(jīng)驗(yàn)、認(rèn)知程度等不同，學(xué)習(xí)方法也有差異，由于多媒體教學(xué)信息的多角度多層次性，不具有固定的學(xué)習(xí)