1、精選優(yōu)質(zhì)文檔-傾情為你奉上成績課程設(shè)計(jì)說明書(論文)題 目 課 程 名 稱 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 院（系、部、中心） 計(jì)算機(jī)工程學(xué)院 專 業(yè) 班 級 學(xué) 生 姓 名 學(xué) 號 設(shè) 計(jì) 地 點(diǎn) 設(shè)計(jì)起止時(shí)間：2016年12月25日至 2016年12月31日 專心-專注-專業(yè)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目（例如表達(dá)式求值問題求解）一、課程設(shè)計(jì)目的和要求目的：深入理解數(shù)據(jù)結(jié)構(gòu)的基本理論，掌握數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)的設(shè)計(jì)方法，掌握基于數(shù)據(jù)結(jié)構(gòu)的各種操作的實(shí)現(xiàn)方法，訓(xùn)練對基礎(chǔ)知識和基本方法的綜合運(yùn)用能力，增強(qiáng)對算法的理解能力，提高軟件設(shè)計(jì)能力。在實(shí)踐中培養(yǎng)獨(dú)立分析問題和解決問題的作風(fēng)和能力。要求：熟練運(yùn)用C+語言、基本數(shù)據(jù)結(jié)構(gòu)和

2、算法的基礎(chǔ)知識，獨(dú)立編制一個(gè)具有中等難度的、解決實(shí)際應(yīng)用問題的應(yīng)用程序。通過題意分析、選擇數(shù)據(jù)結(jié)構(gòu)、算法設(shè)計(jì)、編制程序、調(diào)試程序、軟件測試、結(jié)果分析、撰寫課程設(shè)計(jì)報(bào)告等環(huán)節(jié)完成軟件設(shè)計(jì)的全過程，不斷地完善程序以提高程序的性能。二、題意說明及分析一個(gè)迷宮如圖所示，它有一個(gè)入口和出口，其中白色單元表示通路，黑色單元表示路不通。尋找一條從入口到出口的路徑，每步只能從一個(gè)白色單元走到相鄰的白色單元，直至出口。使用棧實(shí)現(xiàn)走迷宮的功能，演示走迷宮的過程?？勺叩陌咨珕卧?表示，不可走的黑色單元用1表示，使用棧，棧頂元素temp標(biāo)記位置，走出迷宮。輸出迷宮和走出路徑。入口三、算法設(shè)計(jì)與分析用ArrayLis

3、t<coordition> 作為棧的數(shù)據(jù)結(jié)。ArrayList是java中Collection集合中線性表，可以通過add.remove操作添加刪除元素，coordition是定義的內(nèi)部類，用來存放一個(gè)節(jié)點(diǎn)的橫縱坐標(biāo)。這樣，棧中的每個(gè)元素就是迷宮中一個(gè)位置的坐標(biāo)。尋路算法(若存在路徑，返回true；若不存在，返回false)：while 棧非空獲取棧頂元素temp = stack.getTopif temp是出口位置跳出循環(huán)else 繼續(xù)向下執(zhí)行if temp上邊可走 and temp上邊未遍歷把temp所在位置標(biāo)記為已遍歷，將temp 上邊的位置加入棧頂進(jìn)入下一次循環(huán)if tem

4、p右邊可走 and temp右邊未遍歷把temp所在位置標(biāo)記為已遍歷，將temp 右邊的位置加入棧頂進(jìn)入下一次循環(huán)if temp下邊可走 and temp下邊未遍歷把temp所在位置標(biāo)記為已遍歷，將temp 下邊的位置加入棧頂進(jìn)入下一次循環(huán)if temp左邊可走 and temp左邊未遍歷把temp所在位置標(biāo)記為已遍歷，將temp 左邊的位置加入棧頂進(jìn)入下一次循環(huán)上下左右都不可走，標(biāo)記temp為已讀，并從棧中移出，進(jìn)入下次循環(huán)最后退出while循環(huán)有兩種情況：1）找到出口位置，那棧中保留的就是從入口到出口的路徑2）棧為空，說明沒有路徑能從入口到出口四、源程序package com.test;i

5、mport java.util.ArrayList;import java.util.List;public class Maprinth private int map;/存放迷宮矩陣，0表示可走，1表示不可走 private coordinate start;/記錄起點(diǎn)坐標(biāo) private coordinate end;/記錄終點(diǎn)坐標(biāo) private List<coordinate> stack;/棧 /* * 坐標(biāo) * */ class coordinate public int x; public int y; public coordinate(int x,int y)

6、this.x = x; this.y = y; /* * 入棧 * */ public void push(coordinate co) if(this.stack!=null) this.stack.add(co); else this.stack = new ArrayList<>(); stack.add(co); /* * 獲取棧頂元素 * */ public coordinate getTop() if(!stack.isEmpty() return stack.get(stack.size()-1); else return null; /* * 出棧操作 * */ p

7、ublic coordinate pop() if(!stack.isEmpty() return stack.remove(stack.size()-1); else return null; /* * 產(chǎn)生例題的迷宮矩陣 * */ public void generatemap2() map = new int66; map00 = 0;map01 = 1;map02 = 0;map03 = 0;map04 = 0;map05 = 1; map10 = 0;map11 = 0;map12 = 0;map13 = 1;map14 = 0;map15 = 1; map20 = 1;map21

8、= 0;map22 = 1;map23 = 0;map24 = 0;map25 = 1; map30 = 0;map31 = 0;map32 = 0;map33 = 1;map34 = 1;map35 = 1; map40 = 0;map41 = 1;map42 = 1;map43 = 0;map44 = 0;map45 = 0; map50 = 0;map51 = 0;map52 = 0;map53 = 0;map54 = 1;map55 = 1; start = new coordinate(0,0); end = new coordinate(4,5); /打印迷宮矩陣 printmap

9、(); public void printmap() if(this.map!=null) for(int i=0;i<map.length;i+) for(int j=0;j<map.length;j+) System.out.print(mapij+" "); System.out.println(); /* * 尋路函數(shù) * return true: 存在路徑 * return false：不存在路徑 * */ public boolean search() /記錄遍歷情況數(shù)組 0 表示未遍歷 ，1 表示遍歷 int flag = new intmap.l

10、engthmap.length; /棧 this.stack = new ArrayList<>(); coordinate start = this.start; coordinate end = this.end; stack.add(start); int i=0; /棧非空 while(!stack.isEmpty()&&(i<10) /按照上 右 下 左的順序遍歷 /取棧頂 coordinate temp = getTop(); /終點(diǎn)則停止 if(temp.x = this.end.x)&&(temp.y=this.end.y) b

11、reak; /向上 if(temp.x>0) /上可走且未遍歷 if(maptemp.x-1temp.y!=1)&&(flagtemp.x-1temp.y=0) /標(biāo)記已遍歷 flagtemp.xtemp.y = 1; /入棧 push(new coordinate(temp.x-1,temp.y); continue; /向右 if(temp.y<map.length-1) /右可走且未遍歷 if(maptemp.xtemp.y+1!=1)&&(flagtemp.xtemp.y+1=0) flagtemp.xtemp.y = 1; /stack.a

12、dd(new coordinate(temp.x,temp.y+1); /入棧 push(new coordinate(temp.x,temp.y+1); continue; /向下 if(temp.x<map.length-1) /下可走且未遍歷 if(maptemp.x+1temp.y!=1)&&(flagtemp.x+1temp.y=0) flagtemp.xtemp.y = 1; /stack.add(new coordinate(temp.x+1,temp.y); /入棧 push(new coordinate(temp.x+1,temp.y); continu

13、e; /向左 if(temp.y>0) /左可走且未遍歷 if(maptemp.xtemp.y-1!=1)&&(flagtemp.xtemp.y-1=0) flagtemp.xtemp.y = 1; /stack.add(new coordinate(temp.x,temp.y-1); /入棧 push(new coordinate(temp.x,temp.y-1); continue; /上下左右都不能走,標(biāo)記已遍歷并移出 flagtemp.xtemp.y = 1; /stack.remove(stack.size()-1); /出棧 pop(); /出入口沒有路徑 i

14、f(stack.size()=0) return false; /找到路徑 else return true; /* * 打印路徑 * */ public void printPath() if(!stack.isEmpty() for(int i=0;i<stack.size()-1;i+) System.out.print("("+stack.get(i).x+","+stack.get(i).y+")"+"->"); System.out.println("("+stack.g

15、et(stack.size()-1).x+","+stack.get(stack.size()-1).y+")"); public static void main(String args) Maprinth Maprinth = new Maprinth(); Maprinth.generatemap2(); if(Maprinth.search() /打印路徑 Maprinth.printPath(); else System.out.println("無可用路徑！"); 五、結(jié)果及分析輸出了這個(gè)迷宮和所走的最短路徑六、總結(jié)與思考通過本次課程設(shè)計(jì)，我對棧的了解更深了一個(gè)層次。棧是一種特殊的線性表，特殊之處在于插入和刪除操作的位置受到限制，棧的插入和刪除操作只允許在線性表的一端進(jìn)行，特點(diǎn)是先