數(shù)據(jù)結(jié)構(gòu)課程設(shè)計2012

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計題目題目一大數(shù)算術(shù)表達(dá)式求值題目二求解馬踏棋盤問題題目三校園導(dǎo)游題目一大數(shù)算術(shù)表達(dá)式求值問題描述表達(dá)式求值是實(shí)現(xiàn)程序設(shè)計語言的基本問題之一，也是棧的應(yīng)用的一個典型例子。設(shè)計一個程序，演示用算符優(yōu)先法對算術(shù)表達(dá)式求值的過程。以字符序列的形式從終端上輸入語法正確的、不含變量的整數(shù)（大數(shù)）表達(dá)式。實(shí)現(xiàn)對算術(shù)四則混合運(yùn)算表達(dá)式的求值，顯示在求值中運(yùn)算符棧、運(yùn)算數(shù)棧、輸入字符和主要操作的變化過程。輸出格式要求要求分步驟輸出，每一步輸出格式：STEP XOP Stack pop： XXXX （或 OP Stack push： XXXX ）NUM Stack pop：XXXX （或 NUM

2、Stack push： XXXX ）NUM Stack push： XXXX這里要求打印出該步具體的出棧入棧順序，OP stack表示運(yùn)算符棧、 NUM stack表示運(yùn)算數(shù)棧。每步最后打印兩個棧的狀態(tài)，格式：OP Stack ：0 XXX 1XXXNUM Stack：0 XXX 1XXX 2XXX題目二求解馬踏棋盤問題問題描述將馬隨機(jī)放在國際象棋8*8的棋盤的某個方格中，馬按走棋規(guī)則進(jìn)行移動。要求每個方格上只進(jìn)入一次，走遍棋盤上全部64個方格。試求出馬的行走路線。要求：編制非遞歸程序；打印求出的行走路線；將數(shù)字1，2，64依次填入的8*8方陣，輸出之。問題分析每次在多個可走位置中隨機(jī)選擇一個

3、，用適當(dāng)結(jié)構(gòu)妥善管理位置，試探失敗時回溯。問題分析77775555添加策略：為每一個位置設(shè)置一個權(quán)值，表示該位置可以到達(dá)的位置數(shù)；移動時向權(quán)值大的位置移動輸出格式要求ABCDEFGH12345678馬位置表示：（D4）馬移動輸出格式：1STEPFROMTO1（D4）（C6）2（C6）（A7）64（XX）（XX）23輸出格式要求棋盤輸出格式：12345678AXXXXXXXXBXXXXXXXXCXXXXXXXXDXXXXXXXXEXXXXXXXXFXXXXXXXXGXXXXXXXXHXXXXXXXX題目三校園導(dǎo)游問題描述設(shè)計校園平面圖，所含景點(diǎn)不少于10個。以圖中頂點(diǎn)表示學(xué)校各景點(diǎn)，存放景點(diǎn)名稱

4、、代號、簡介等信息；以邊表示路徑，存放路徑長度等相關(guān)信息。要求：為來訪客人提供圖中任意景點(diǎn)的問路查詢，即查詢?nèi)我鈨蓚€景點(diǎn)之間的一條最短的簡單路徑；為來訪客人提供圖中景點(diǎn)間的推薦路線（遍歷各節(jié)點(diǎn)的最短路線）和各景點(diǎn)之間的介紹。圖信息1. 南大門廣場2. 光谷體育館3. 眼鏡湖4.紫松5.青年園6.集貿(mào)市場7.光電實(shí)驗(yàn)室8.東九孔子像9.瑜園10.珞珈山11.韻苑12.愛因斯坦廣場圖信息各景點(diǎn)簡介自己填寫503230402040404026252039100101020301. 南大門廣場2. 光谷體育館3. 眼鏡湖4.紫松8.東九9.瑜園10.珞珈山11.韻苑12.愛因斯7.光電5.青年園6.集貿(mào)市場問題分析節(jié)點(diǎn)組成無向圖，則可用最短路徑求解：Dijkstra 算法Floyd算法 輸出格式要求順序打印景點(diǎn)和介紹，格式要求：STEP1：景點(diǎn)名景點(diǎn)介紹兩