【文章內(nèi)容簡(jiǎn)介】 的編號(hào)一次為 1， 2， 3，?， n。設(shè)計(jì)一個(gè)程序，求出所有可能由此輸出的長(zhǎng)度為 n 的車廂序列。 測(cè)試數(shù)據(jù)自己輸入。 20. 算術(shù)表達(dá)式的求值演示 問題描述：（需求分析和背景意義） 表達(dá)式計(jì)算是實(shí)現(xiàn)程序設(shè)計(jì)語言的基本問題之一，也是棧的應(yīng)用的一個(gè)典型的例子。設(shè)計(jì)一個(gè)程序，演示用算符優(yōu)先法對(duì)算術(shù)表達(dá)式求值的過程。 基本要求：（設(shè) 計(jì)階段，概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)） 以字符序列的形式從終端輸入語法正確的、不含變量的整數(shù)表達(dá)式。利用教科書表 給出的算符優(yōu)先關(guān)系，實(shí)現(xiàn)對(duì)算術(shù)四則混合運(yùn)算表達(dá)式的求值，并仿照教科書上的例 31 演示在求值中運(yùn)算符棧、運(yùn)算數(shù)棧、輸入字符和主要操作的變化過程。 測(cè)試數(shù)據(jù)： 教科書例 31的算術(shù)表達(dá)式 3*（ 72），以及下列表達(dá)式 8； 1+2+3+4； 881*5；1024/4*8； 1024/（ 4*8）； （ 20+2） *（ 6/2）； 333； 8/（ 99）； 2*（ 6+2*（ 3+6*（ 6+6）））；（（（ 6+6） *6+3） *2+6） *2； 實(shí)現(xiàn)提示： （ 1） 設(shè)置運(yùn)算符棧和運(yùn)算數(shù)棧輔助分析算符優(yōu)先關(guān)系。 （ 2） 在讀入表達(dá)式的字符序列的同時(shí)，完成運(yùn)算符和運(yùn)算數(shù)（整數(shù)）的識(shí)別處理，以及相應(yīng)的運(yùn)算。（ 3）在識(shí)別出運(yùn)算數(shù)的同時(shí)，要將其字符序列形式轉(zhuǎn)化成整數(shù)形式。 （ 4）在程序的適當(dāng)位置輸出運(yùn)算符棧、運(yùn)算數(shù)棧、輸入字符和主要操作的內(nèi)容。 選做內(nèi)容 ： （ 1）擴(kuò)充運(yùn)算符集，如增加乘方、單目減、賦值等運(yùn)算。 （ 2）運(yùn)算量可以是變量。 （ 3）運(yùn)算量可以是實(shí)數(shù)類型。 （ 4）計(jì)算器的功能 和仿真界面。 21. 校園導(dǎo)游咨詢 問題描述：（需求分析和背景意義） 設(shè)計(jì)一個(gè)校園導(dǎo)游程序，為來訪的客人提供各種信息查詢服務(wù)。 基本要求：（設(shè)計(jì)階段，概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)） （ 1）設(shè)計(jì)你所在學(xué)校的校園平面圖，所含景點(diǎn)不少于 10個(gè)。以圖中頂點(diǎn)表示校內(nèi)各景點(diǎn)，存放景點(diǎn)名稱、代號(hào)、簡(jiǎn)介等信息；以邊表示路徑，存放路徑長(zhǎng)度的相關(guān)信息。 （ 2）為來訪客人提供圖中任意景點(diǎn)的相關(guān)信息查詢。 （ 3）為來訪客人提供圖中任意景點(diǎn)的問路查詢，即查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間的一條最短路徑。 測(cè)試數(shù)據(jù)： 由讀者根據(jù) 實(shí)際情況指定。 實(shí)現(xiàn)提示： 一般情況下，校園的道路是雙向通行的，可設(shè)校園平面圖是一個(gè)無向網(wǎng)。頂點(diǎn)和邊均含有相關(guān)信息。 選做內(nèi)容 ： （ 1）求校園的關(guān)節(jié)點(diǎn)。 （ 2）提供圖中任意景點(diǎn)問路查詢，即求任意兩個(gè)景點(diǎn)之間的所有路徑。 （ 3） 提供校園圖中多個(gè)景點(diǎn)的最佳訪問路線查詢，即求途經(jīng)這個(gè)景點(diǎn)的最佳（短）路徑。 （ 4）校園導(dǎo)游圖的景點(diǎn)和道路的修改擴(kuò)充功能。 （ 5）擴(kuò)充道路信息，如道路類別（車道、人行道等）、沿途景色等級(jí)，以至可按客人所需分別查詢?nèi)诵新窂交蜍囆新窂交蛴^景路徑等。 （ 6）擴(kuò)充每個(gè)景點(diǎn)的 鄰接景點(diǎn)的方向等信息，使得路徑查詢結(jié)果能提供詳導(dǎo)向信息。 （ 7）實(shí)現(xiàn)校園導(dǎo)游圖的仿真界面。 22. 約瑟夫環(huán)的求解及演示 問題描述：（需求分析和背景意義） 約瑟夫問題的一種描述是 :編號(hào)為 1,2,? ,n 的 n 個(gè)人按順時(shí)針方向圍坐一圈 ,每個(gè)人持有一個(gè)密碼 (正整數(shù) ).一開始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值 m,從第一個(gè)人開始按順時(shí)針方向自 1 開始順序報(bào)數(shù) ,報(bào)到 m 時(shí)停止報(bào)數(shù) .報(bào) m 的人將出列 ,將他的密碼作為新的 m 值 ,從他在順時(shí)針方向上的下一個(gè)人開始重新從 1 報(bào)數(shù) ,如此下去 ,直至所有人全部出列為止 .設(shè)計(jì)一程序求出出列順序 . 基本要求：（設(shè)計(jì)階段，概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)） 利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬次過程 ,按照出列的順序印出個(gè)人的編號(hào) . 測(cè)試數(shù)據(jù)： m 的初值為 20。n=7,7 個(gè)人的密碼依次為 :3,1,7,2,4,8,4,首先 m 值為 6(正確的出列順序應(yīng)為 6,1,4,7,2,3,5). 實(shí)現(xiàn)提示： 程序運(yùn)行后 ,首先要求用戶指定初始報(bào)數(shù)上限 ,然后讀取個(gè)人的密碼 .可設(shè) n≤“頭結(jié)點(diǎn)” ,請(qǐng)注意空表和非空表的界限 . 選做內(nèi)容 ： 向上述程序中添加在順序結(jié)構(gòu)上實(shí)現(xiàn)的部分 . 衡二叉樹操作的演示 問題描述：（需求分析和背景意義） 利用平衡二叉樹實(shí)現(xiàn)一個(gè)動(dòng)態(tài)查找表。 基本要求：（設(shè)計(jì)階段，概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)） 實(shí)現(xiàn)動(dòng)態(tài)查找表的三種功能：查找、插入、刪除。 測(cè)試數(shù)據(jù)：自行設(shè)定。 實(shí)現(xiàn)提示： （ 1）初始，平衡二叉樹為空樹，操作界面給出查找、插入和刪除三種操作供選擇。每種操作均要提示輸入關(guān)鍵字。每次插入或刪除一個(gè)結(jié)點(diǎn)后，應(yīng)更新平衡二叉樹的顯示。 （ 2）平衡二叉樹的顯示可采用凹入表現(xiàn)形式，也可以采用圖形界面畫出樹行。 （ 3）、教科書已給出查找和 插入算法，本題重點(diǎn)在于對(duì)刪除算法的設(shè)計(jì)和實(shí)現(xiàn)。假設(shè)要?jiǎng)h除關(guān)鍵字為 x 的結(jié)點(diǎn)。如果 x不在葉子結(jié)點(diǎn)上，則用它的左子樹中最大值或右子樹中的最小值取代 x。如此反復(fù)取代，直到刪除動(dòng)作傳遞到某個(gè)葉子結(jié)點(diǎn)。刪除葉子結(jié)點(diǎn)時(shí)，若需要進(jìn)行平衡交換，可采用插入的平衡變換的反變換（如，左子樹變矮對(duì)應(yīng)右子樹長(zhǎng)高）。 選做內(nèi)容 ： （ 1）合并兩棵平衡二叉樹。 （ 2）把一棵二叉樹分裂為兩棵平衡二叉樹，使得在一棵樹中的所有關(guān)鍵字都小于或等于 x，另一棵樹中的任一關(guān)鍵字都大于 x。 24. 最小生成樹問題 問題描述：（需求分析 和背景意義） 若要在 n 個(gè)城市之間建設(shè)通信網(wǎng)絡(luò)，只需要假設(shè) n1 條線路即可。如何以最低的經(jīng)濟(jì)代價(jià)建設(shè)這個(gè)通信網(wǎng)，是一個(gè)網(wǎng)的最小生成樹問題。 基本要求： （設(shè)計(jì)階段，概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)） （ 1）利用克魯斯卡爾算法求網(wǎng)的最小生成樹。 （ 2）實(shí)現(xiàn)教材 節(jié)中定義的抽象數(shù)據(jù)類型 MFSet。以此表示構(gòu)造生成樹過程中的連通分量。（ （ 3）以文本的形式輸出生成樹中各條邊以及他們的權(quán)值。（ a c 3） 提示： 通信線路一旦建立，必然是雙向的。因此，構(gòu)造最小生成樹的網(wǎng)一定是無向網(wǎng)。 設(shè)圖的頂點(diǎn)數(shù)不超 過 30 個(gè)，并為簡(jiǎn)單起見，網(wǎng)中的權(quán)值設(shè)成小于 100 的整數(shù)，可利用 C 語言提供的隨機(jī)函數(shù)產(chǎn)生。 圖的存儲(chǔ)結(jié)構(gòu)的選取和所作操作相適應(yīng)。為了便于選擇權(quán)值最小的邊，此題的存儲(chǔ)結(jié)構(gòu)既不選用鄰接矩陣的數(shù)組表示法也不選用鄰接表， 而是以存儲(chǔ)邊（帶權(quán)）的數(shù)組表示圖。 選做內(nèi)容： 利用堆排序（參見教科書 節(jié)）實(shí)現(xiàn)選擇權(quán)值最小的邊。 （八皇后） 問題描述：（需求分析和背景意義） 設(shè)計(jì)一個(gè)國(guó)際象棋的馬踏遍棋盤的演示程序 . 基本要求： （設(shè)計(jì)階段：概要設(shè)計(jì)和詳細(xì)設(shè)計(jì)） 將馬隨機(jī)放在國(guó)際象棋的 8 8 棋盤 Board[8][8]的某個(gè)方格中 ,馬按走棋規(guī)則進(jìn)行移動(dòng) .要求每個(gè)方格只進(jìn)入一次 ,走遍棋盤上全部 64 個(gè)方格 .編制非遞歸程序 ,求出馬的行走路線 ,并按求出的馬的行走路線 ,將路線 1,2,? ,64 依次填入一個(gè) 8 8 的方陣 ,輸出之 . 測(cè)試數(shù)據(jù)： 由讀者指定 .可自行指定一個(gè)馬的初始位置 (i,j),0≤ i,j≤ 7. 實(shí)現(xiàn)提示 :下頁圖顯示了馬位于方格 (2,3)時(shí) ,8 個(gè)可能的移動(dòng)位置 .一般來說 ,當(dāng)馬位于位置 (i,j)時(shí) ,可以走到下列 8 個(gè)位置之一 (i2,j+1),(i1,j+2),(i+1,j+2),(i+2,j+1),(i+2,j1),(i+1,j2),(i1,j2),(i2,j1) 0 1 2 3 4 5 6 7 0 8 1 1 7 2 2 H 3 6 3 4 5 4 5 6 7 但是 ,如果 (i,j)靠近棋盤的邊緣 ,上述有些位置可能超出棋盤范圍 ,成為不允許的位置 .8 個(gè)可能位置可以用兩個(gè)一維數(shù)組 HTry1[0..7]和 HTry2[0..7]來表示 : HTry1 0 1 2 3 4 5 6 7 2 1 1 2 2 1 1 2 HTry2 0 1 2 3 4 5 6 7 1 2 2 1 1 2 2 1 位于 (i,j)的馬可以走到的新位置是棋盤范圍內(nèi)的 (i+HTry1[h],j=HTry2[h]),其中 h=0,1,? ,7. 每次在多個(gè)可走位置中選擇其中一個(gè)進(jìn)行試探 ,其余未曾試探過的可走位置必須用適當(dāng)結(jié)構(gòu)妥善管理 ,以備失敗時(shí)的“回溯” (悔棋 )使用 . 選做內(nèi)容： (1) 求出從某一起點(diǎn)出發(fā)的多條以至全部行走路線 . (2)探討每次選擇位置的“最佳策略” ,以減少回溯的次數(shù) . (3)演示尋找 行走路線的回溯過程 . 任務(wù)：參加運(yùn)動(dòng)會(huì)有 n 個(gè)學(xué)校，學(xué)校編號(hào)為 1?? n。比賽分成 m 個(gè)男子項(xiàng)目，和 w 個(gè)女子項(xiàng)目。項(xiàng)目編號(hào)為男子 1?? m，女子 m+1?? m+w。不同的項(xiàng)目取前五名或前三名積分；取前五名的積分分別為： 1，前三名的積分分別為： 2；哪些取前五名或前三名由學(xué)生自己設(shè)定。（ m=20,n=20） 功能要求： 1) 可以輸入各個(gè)項(xiàng)目的前三名或前五名的成績(jī)； 2) 能統(tǒng)計(jì)各學(xué)?？偡?， 3) 可以按學(xué)校編號(hào)或名稱、學(xué)?？偡?、男女團(tuán)體總分排序輸出； 4) 可以按學(xué)校編號(hào)查詢學(xué)校某個(gè)項(xiàng)目的情況；可以按項(xiàng)目編號(hào)查詢?nèi)〉们叭蚯拔迕膶W(xué)校。 5) 數(shù)據(jù)存入文件并能隨時(shí)查詢 6) 規(guī)定：輸入數(shù)據(jù)形式和范圍：可以輸入學(xué)校的名稱，運(yùn)動(dòng)項(xiàng)目的名稱 輸出形式：有中文提示，各學(xué)校分?jǐn)?shù)為整形 界面要求：有合理的提示，每個(gè)功能可以設(shè)立菜單，根據(jù)提示，可以完成相關(guān)的功能要求。 存儲(chǔ)結(jié)構(gòu)：學(xué)生自己根據(jù)系統(tǒng)功能要求自己設(shè)計(jì)，但是要求運(yùn)動(dòng)會(huì)的相關(guān)數(shù)據(jù)要存儲(chǔ)在數(shù)據(jù)文件中。（數(shù)據(jù)文件的數(shù)據(jù)讀寫方法等相關(guān)內(nèi)容在 c 語言程序設(shè)計(jì)的書上，請(qǐng)自學(xué)解決）請(qǐng)?jiān)谧詈蟮纳辖毁Y料中指明你用到的存儲(chǔ) 結(jié)構(gòu)； 測(cè)試數(shù)據(jù)：要求使用 全部合法數(shù)據(jù)； 整體非法數(shù)據(jù)； 局部非法數(shù)據(jù)。進(jìn)行程序測(cè)試，以保證程序的穩(wěn)定。測(cè)試數(shù)據(jù)及測(cè)試結(jié)果請(qǐng)?jiān)谏辖坏馁Y料中寫明； 27. 飛機(jī)訂票系統(tǒng) 任務(wù)：通過此系統(tǒng)可以實(shí)現(xiàn)如下功能： 錄入： 可以錄入航班情況（數(shù)據(jù)可以存儲(chǔ)在一個(gè)數(shù)據(jù)文件中，數(shù)據(jù)結(jié)構(gòu)、具體數(shù)據(jù)自定） 查詢： 可以查詢某個(gè)航線的情況（如，輸入航班號(hào)，查詢起降時(shí)間，起飛抵達(dá)城市，航班票價(jià)，票價(jià)折扣，確定航班是否滿倉(cāng)）； 可以輸入起飛抵達(dá)城市，查詢飛機(jī)航班情況； 訂票：（訂票情況可以存在一個(gè)數(shù) 據(jù)文件中，結(jié)構(gòu)自己設(shè)定） 可以訂票，如果該航班已經(jīng)無票，可以提供相關(guān)可選擇航班； 退票： 可退票，退票后修改相關(guān)數(shù)據(jù)文件； 客戶資料有姓名，證件號(hào)，訂票數(shù)量及航班情況，訂單要有編號(hào)。 修改航班信息： 當(dāng)航班信息改變可以修改航班數(shù)據(jù)文件 要求： 根據(jù)以上功能說明，設(shè)計(jì)航班信息，訂票信息的存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)程序完成功能； 28. 文章編輯 功能：輸入一頁文字，程序可以統(tǒng)計(jì)出文字、數(shù)字、空格的個(gè)數(shù)。 靜態(tài)存儲(chǔ)一頁文章，每行最多不超過 80 個(gè)字符，共 N 行；要求（ 1）分別統(tǒng)計(jì)出其中英文字 母數(shù)和空格數(shù)及整篇文章總字?jǐn)?shù)；（ 2）統(tǒng)計(jì)某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；（ 3）刪除某一子串，并將后面的字符前移。 存儲(chǔ)結(jié)構(gòu)使用線性表，分別用幾個(gè)子函數(shù)實(shí)現(xiàn)相應(yīng)的功能； 輸入數(shù)據(jù)的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標(biāo)點(diǎn)符號(hào)。 輸出形式：（ 1）分行輸出用戶輸入的各行字符；（ 2）分 4 行輸出 全部字母數(shù) 、 數(shù)字個(gè)數(shù)、 空格個(gè)數(shù) 、 文章總字?jǐn)?shù) （ 3）輸出刪除某一字符串后的文章； 29. 紙牌游戲 任務(wù)：編號(hào)為 152 張牌，正面向上，從第 2張開始，以 2 為基數(shù)，是 2 的倍 數(shù)的牌翻一次，直到最后一張牌；然后，從第 3 張開始，以 3 為基數(shù)，是 3 的倍數(shù)的牌翻一次，直到最后一張牌；然后?從第 4 張開始，以 4 為基數(shù)，是 4的倍數(shù)的牌翻一次， 直到最后一張牌； ...再依次5 的倍數(shù)的牌翻一次， 6的， 7