【正文】 滿足條件的解，或者無(wú)解。由于回溯求解的規(guī)則規(guī)則是“后進(jìn)先出”因此自然要用到棧。訂票系統(tǒng)（1）問(wèn)題描述通過(guò)此系統(tǒng)可以實(shí)現(xiàn)如下功能： 1）錄入：可以錄入航班情況（數(shù)據(jù)可以存儲(chǔ)在一個(gè)數(shù)據(jù)文件中，數(shù)據(jù)結(jié)構(gòu)、具體數(shù)據(jù)自定）2）查詢： 可以查詢某個(gè)航線的情況（如，輸入航班號(hào)，查詢起降時(shí)間，起飛抵達(dá)城市，航班票價(jià)，票價(jià)折扣，確定航班是否滿倉(cāng)）；可以輸入起飛抵達(dá)城市，查詢飛機(jī)航班情況；3）訂票：（訂票情況可以存在一個(gè)數(shù)據(jù)文件中，結(jié)構(gòu)自己設(shè)定）可以訂票，如果該航班已經(jīng)無(wú)票，可以提供相關(guān)可選擇航班；4）退票： 可退票，退票后修改相關(guān)數(shù)據(jù)文件；客戶資料有姓名，證件號(hào)，訂票數(shù)量及航班情況，訂單要有編號(hào)。5）修改航班信息：當(dāng)航班信息改變可以修改航班數(shù)據(jù)文件（2）要求根據(jù)以上功能說(shuō)明，設(shè)計(jì)航班信息，訂票信息的存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)程序完成功能；迷宮求解（1）問(wèn)題描述可以輸入一個(gè)任意大小的迷宮數(shù)據(jù)，用非遞歸的方法求出一條走出迷宮的路徑，并將路徑輸出；（2）要求在上交資料中請(qǐng)寫明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；dijkstra算法求最短路徑問(wèn)題描述：從鍵盤上輸入一個(gè)圖的基本信息（圖用鄰矩陣表示）1)首先輸入圖的結(jié)點(diǎn)數(shù)num 2)依次輸入圖的各條邊3）程序所能達(dá)到的功能：輸出用dijkstra算法求出的一條最短路徑。joseph環(huán)（1）問(wèn)題描述編號(hào)是1，2，??,n的n個(gè)人按照順時(shí)針?lè)较驀蝗?，每個(gè)人只有一個(gè)密碼（正整數(shù)）。一開始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m,從第一個(gè)仍開始順時(shí)針?lè)较蜃?開始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針?lè)较虻南乱粋€(gè)人開始重新從1報(bào)數(shù)，如此下去，直到所有人全部出列為止。設(shè)計(jì)一個(gè)程序來(lái)求出出列順序。（2）要求 利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過(guò)程，按照出列的順序輸出各個(gè)人的編號(hào)。（3）測(cè)試數(shù)據(jù)：m的初值為20，n=7 ,7個(gè)人的密碼依次為3，1，7，2，4，7，4，首先m=6,則正確的輸出是什么？（4）輸入數(shù)據(jù)：建立輸入處理輸入數(shù)據(jù)，輸入m的初值，n，輸入每個(gè)人的密碼，建立單循環(huán)鏈表。（5）輸出形式：建立一個(gè)輸出函數(shù)，將正確的輸出序列建立二叉樹，層序、先序遍歷（用遞歸或非遞歸的方法都可以）（1）問(wèn)題描述：建立二叉樹，并實(shí)行層序、先序遍歷等算法（2）要求：能夠輸入樹的各個(gè)結(jié)點(diǎn)，并能夠輸出用不同方法遍歷的遍歷序列；分別建立建立二叉樹存儲(chǔ)結(jié)構(gòu)的的輸入函數(shù)、輸出層序遍歷序列的函數(shù)、輸出先序遍歷序列的函數(shù)；赫夫曼樹的建立（1）問(wèn)題描述：建立建立最優(yōu)二叉樹函數(shù)（2）要求：可以建立函數(shù)輸入二叉樹，并輸出其赫夫曼樹在上交資料中請(qǐng)寫明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、輸入輸出、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；圖的建立及輸出（1）問(wèn)題描述：建立圖的存儲(chǔ)結(jié)構(gòu)（圖的類型可以是有向圖、無(wú)向圖、有向網(wǎng)、無(wú)向網(wǎng)，學(xué)生可以任選兩種類型）（2）要求：能夠輸入圖的頂點(diǎn)和邊的信息，并存儲(chǔ)到相應(yīng)存儲(chǔ)結(jié)構(gòu)中，而后輸出圖的鄰接矩陣。拓?fù)渑判颍?）問(wèn)題描述：編寫函數(shù)實(shí)現(xiàn)圖的拓?fù)渑判颉＃?）要求：能夠以一定的方式輸入數(shù)據(jù)結(jié)點(diǎn)各種排序（1）問(wèn)題描述：對(duì)30000個(gè)隨機(jī)整數(shù)，利用插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序等排序方法進(jìn)行排序，并統(tǒng)計(jì)每一種排序上機(jī)所花費(fèi)的時(shí)間。（2）要求：輸入的數(shù)據(jù)形式為任何一個(gè)正整數(shù)，大小不限。輸出的形式：數(shù)字大小逐個(gè)遞增的數(shù)列1圖的遍歷 對(duì)任意給定的圖（頂點(diǎn)數(shù)和邊數(shù)自定），建立它的鄰接表并輸出，然后利用隊(duì)列的五種基本運(yùn)算（置空隊(duì)列、進(jìn)隊(duì)、出隊(duì)、取隊(duì)頭元素、判隊(duì)空）實(shí)現(xiàn)圖的廣度優(yōu)先搜索周游。1線性表的操作利用鏈表的插入運(yùn)算建立線性鏈表，然后利用鏈表的查找、刪除、計(jì)數(shù)、輸出等運(yùn)算反復(fù)實(shí)現(xiàn)鏈表的這些操作（插入、刪除、查找、計(jì)數(shù)、輸出單獨(dú)寫成函數(shù)的形式），并能在屏幕上輸出操作前后的結(jié)果。1長(zhǎng)整數(shù)四則運(yùn)算*問(wèn)題描述：設(shè)計(jì)一個(gè)實(shí)現(xiàn)任意長(zhǎng)的整數(shù)進(jìn)行加法運(yùn)算的演示程序。*基本要求：利用雙向循環(huán)鏈表實(shí)現(xiàn)長(zhǎng)整數(shù)的存儲(chǔ)，每個(gè)結(jié)點(diǎn)含一個(gè)整形變量。任何整形變量的范圍是(2^151)。輸入和輸出形式：按中國(guó)對(duì)于長(zhǎng)整數(shù)的表示習(xí)慣，每四位一組，組間用逗號(hào)隔開。*測(cè)試數(shù)據(jù)：（1）0；0；應(yīng)輸出“0”。（2）2345,6789；7654,3211；應(yīng)輸出“1,0000,0000”。（3）9999,9999；1,0000,0000,0000；應(yīng)輸出“999（4）1,0001,0001；1,0001,0001；應(yīng)輸出“0”。（5）1,0001,0001；1,0001,0000；應(yīng)輸出“1”。（6）9999,9999,9999；9999,9999,9999；應(yīng)輸出“1,9999,9999,9998”。（7）1,0000,9999,9999；1；應(yīng)輸出“1,0001,0000,0000”。*實(shí)現(xiàn)提示：（1）每個(gè)結(jié)點(diǎn)中可以存放的最大整數(shù)為32767，才能保證兩數(shù)相加不會(huì)溢出，但若這樣存放，即相當(dāng)于按32768進(jìn)制存放，在十進(jìn)制與32768進(jìn)制數(shù)之間的轉(zhuǎn)換十分不方便，故可以在每個(gè)結(jié)點(diǎn)中僅存十進(jìn)制的4位，即不超過(guò)9999的非負(fù)整數(shù)，整個(gè)鏈表表示為萬(wàn)進(jìn)制。（2）可以利用頭結(jié)點(diǎn)數(shù)據(jù)域的符號(hào)代表長(zhǎng)整數(shù)的符號(hào)。用其絕對(duì)值表示元素結(jié)點(diǎn)數(shù)目。相加過(guò)程中不要破壞兩個(gè)操作數(shù)鏈表。兩操作數(shù)的頭指針存于指針數(shù)組中是簡(jiǎn)化程序結(jié)構(gòu)的一種方法。不能給長(zhǎng)整數(shù)位數(shù)規(guī)定上限。1克魯斯?fàn)査惴ㄇ笞钚∩蓸鋯?wèn)題描述：從鍵盤上輸入一個(gè)圖的基本信息（圖用鄰矩陣表示）1)首先輸入圖的結(jié)點(diǎn)數(shù)num 2)依次輸入圖的各條邊3)程序所能達(dá)到的功能：能夠輸出這個(gè)圖的一棵最小生成樹1算術(shù)表達(dá)式求值演示（1）問(wèn)題描述：表達(dá)式求值是實(shí)現(xiàn)程序設(shè)計(jì)語(yǔ)言的基本問(wèn)題之一，也是棧的應(yīng)用的一個(gè)典型例子。設(shè)計(jì)一個(gè)程序，演示用算符優(yōu)先法對(duì)算術(shù)表達(dá)式求值的過(guò)程。（2）基本要求：以字符序列的形式從終端上輸入語(yǔ)法正確的、不含變量的整數(shù)表達(dá)式。利用教材中給出的算符優(yōu)先關(guān)系，實(shí)現(xiàn)對(duì)算術(shù)四則混合運(yùn)算表達(dá)式的求值，并仿照教材例31演示在求值中運(yùn)算符棧、運(yùn)算數(shù)棧、輸入字符和主要操作的變化過(guò)程。16．稀疏矩陣運(yùn)算器*問(wèn)題描述：稀疏矩陣是指那些多數(shù)元素為0的矩陣。利用“稀疏”特點(diǎn)進(jìn)行存儲(chǔ)和計(jì)算可以大大節(jié)省存儲(chǔ)空間，提高計(jì)算效率。實(shí)現(xiàn)一個(gè)能進(jìn)行稀疏矩陣基本原酸的運(yùn)算器。*基本要求：以“帶行邏輯鏈接信息”的三元組順序表示稀疏矩陣，實(shí)現(xiàn)兩個(gè)矩陣相加、相減和相乘的運(yùn)算。稀疏矩陣的輸入形式采用三元組表示，而運(yùn)算結(jié)構(gòu)的矩陣則以通常的陣列形式列出。*實(shí)現(xiàn)提示：（1）首先應(yīng)輸入矩陣的行數(shù)和列數(shù)，并判別給出的兩個(gè)矩陣的行、列數(shù)對(duì)于所要求作的運(yùn)算是否匹配。可設(shè)矩陣的行數(shù)和列數(shù)均不超過(guò)20。（2）程序可以對(duì)三元組的輸入順序加以限制，例如，按行優(yōu)先。注意研究教科書中的算法，以便提高計(jì)算效率。（3）在用三元組表示稀疏矩陣時(shí)，相加或相減所得結(jié)果矩陣應(yīng)該另生成，乘積矩陣也可以用二維數(shù)組存放。四、時(shí)間安排《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》安排在第三學(xué)期進(jìn)行，時(shí)間2周（1718周）。五、組織管理1．由院、系指派經(jīng)驗(yàn)豐富的專業(yè)教師擔(dān)任指導(dǎo)教師。2．課程設(shè)計(jì)實(shí)行指導(dǎo)教師負(fù)責(zé)制，由指導(dǎo)教師全面負(fù)責(zé)課程設(shè)計(jì)的指導(dǎo)與管理工作。六、成績(jī)考核與評(píng)定學(xué)生課程設(shè)計(jì)結(jié)束后寫出總結(jié)報(bào)告，對(duì)設(shè)計(jì)的內(nèi)容和效果進(jìn)行總結(jié)，按照學(xué)生在設(shè)計(jì)期間的表現(xiàn)，指導(dǎo)老師對(duì)每位學(xué)生寫出評(píng)語(yǔ)和鑒定，系課程設(shè)計(jì)領(lǐng)導(dǎo)小組組織答辯，最后確定每位學(xué)生課程設(shè)計(jì)成績(jī)，課程設(shè)計(jì)成績(jī)分為優(yōu)、良、中、及格和不及格五個(gè)等級(jí)。課程設(shè)計(jì)成績(jī)?yōu)槠綍r(shí)表現(xiàn)30%、設(shè)計(jì)報(bào)告50%、答辯20%。評(píng)分標(biāo)準(zhǔn)：① 優(yōu)秀：目的明確，態(tài)度端正，模范遵守學(xué)校的各項(xiàng)紀(jì)律。工作認(rèn)真，積極 主動(dòng)，吃苦耐勞，能出色的完成設(shè)計(jì)任務(wù)。撰寫了高質(zhì)量的總結(jié)報(bào)告。答辯準(zhǔn)確流利。② 良好：目的明確，態(tài)度端正，能遵守學(xué)校的各項(xiàng)紀(jì)律，工作比較積極主動(dòng)。能較好地完成設(shè)計(jì)任務(wù)，成績(jī)較突出，表現(xiàn)良好；撰寫了質(zhì)量比較高的實(shí)習(xí)報(bào)告。答辯較準(zhǔn)確流利。③ 及格：目的明確，態(tài)度基本端正，能遵守學(xué)校紀(jì)律，在督促下能開展工作 并完成一定的設(shè)計(jì)任務(wù)，無(wú)大的違紀(jì)違規(guī)現(xiàn)象；撰寫了實(shí)習(xí)報(bào)告。通過(guò)了答辯。④ 不及格：實(shí)習(xí)態(tài)度端正，不能遵守實(shí)習(xí)單位的紀(jì)律，不服從領(lǐng)導(dǎo)，自由散漫，工作消極被動(dòng)，不能完成實(shí)習(xí)任務(wù)，實(shí)習(xí)期間有失職、曠工、打架、酗酒等大的過(guò)失?；驘o(wú)實(shí)習(xí)報(bào)告，沒(méi)有通過(guò)答辯。2．成績(jī)?cè)u(píng)定依據(jù)上述考核內(nèi)容，最后采用優(yōu)（90分）、良（80～89分）、中（70～79分）及格（60～69分）、不及格（七、主要參考資料《數(shù)據(jù)結(jié)構(gòu) C語(yǔ)言》 嚴(yán)蔚敏 清華大學(xué)出版社 《c語(yǔ)言程序設(shè)計(jì)》 譚浩強(qiáng) 清華大學(xué)出版社 《數(shù)據(jù)結(jié)構(gòu)習(xí)題》 李春保 清華大學(xué)出版社 《數(shù)據(jù)結(jié)構(gòu)習(xí)題》 嚴(yán)蔚敏 清華大學(xué)出版社 《c語(yǔ)言與數(shù)據(jù)結(jié)構(gòu)》 王立柱 清華大學(xué)出版社 《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言篇）習(xí)題與解析》李春葆 第五篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)課程設(shè)計(jì)教學(xué)大綱《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》課程設(shè)計(jì)教學(xué)大綱Course Design of Data Structure課程代碼：適用專業(yè)：信息計(jì)算、信息安全 總學(xué)時(shí)數(shù)：1周編寫年月：2004年7月執(zhí) 筆：劉科峰、李小英、高學(xué)軍課程性質(zhì)：設(shè)計(jì)（論文）/必修 開課學(xué)期：5 總學(xué)分?jǐn)?shù)：1 修訂年月：2007年7月一、課程設(shè)計(jì)的性質(zhì)和目的《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》是本學(xué)院本科專業(yè)的集中實(shí)踐性環(huán)節(jié)之一，是學(xué)習(xí)完《數(shù)據(jù)結(jié)構(gòu)》課程后進(jìn)行的一次全面的綜合應(yīng)用練習(xí)。其目的就是要達(dá)到理論與實(shí)際相結(jié)合，使學(xué)生能夠根據(jù)數(shù)據(jù)對(duì)象的特性，學(xué)會(huì)數(shù)據(jù)組織的方法，能把現(xiàn)實(shí)世界中的實(shí)際問(wèn)題在計(jì)算機(jī)內(nèi)部表示出來(lái)，并培養(yǎng)良好的程序設(shè)計(jì)技能。二、課程設(shè)計(jì)內(nèi)容及學(xué)時(shí)分配寫出不少于3000字的課程設(shè)計(jì)說(shuō)明書。說(shuō)明書中除了在封面中應(yīng)有題目、班級(jí)、姓名、學(xué)號(hào)和課程設(shè)計(jì)日期以外，其正文一般有如下幾個(gè)方面的內(nèi)容： 三、課程設(shè)計(jì)教學(xué)基本要求四、課程設(shè)計(jì)選題根據(jù)教材《數(shù)據(jù)結(jié)構(gòu)題集（C語(yǔ)言版）》（嚴(yán)蔚敏、吳偉民主編）選擇課程設(shè)計(jì)題目，或選擇下列與實(shí)際應(yīng)用緊密結(jié)合的較綜合性的題目，要求通過(guò)設(shè)計(jì)，在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇應(yīng)用、算法的設(shè)計(jì)及其實(shí)現(xiàn)等方面加深對(duì)課程基本內(nèi)容的理解和綜合運(yùn)用。1． 運(yùn)動(dòng)會(huì)分?jǐn)?shù)統(tǒng)計(jì)系統(tǒng)； 2． 停車場(chǎng)管理系統(tǒng)； 3． 民航售票系統(tǒng)； 4． 有理數(shù)四則運(yùn)算器； 5． 文本格式化器； 6． 哈夫曼編/譯碼器； 7． 教學(xué)計(jì)劃編制； 8． 計(jì)算機(jī)輔助考核系統(tǒng)；9． 學(xué)籍管理系統(tǒng)； 10． 圖書管理系統(tǒng)。五、本課程與其它課程的聯(lián)系與分工本課程是《數(shù)據(jù)結(jié)構(gòu)》的配套課程，學(xué)完《數(shù)據(jù)結(jié)構(gòu)》后進(jìn)行的綜合性課程設(shè)計(jì)。六、成績(jī)?cè)u(píng)定由指導(dǎo)教師根據(jù)學(xué)生完成任務(wù)的情況、課程設(shè)計(jì)說(shuō)明書的質(zhì)量和課程設(shè)計(jì)過(guò)程中的工作態(tài)度等綜合打分。課程設(shè)計(jì)結(jié)束時(shí)，要求學(xué)生寫出課程設(shè)計(jì)報(bào)告，可運(yùn)行的軟件系統(tǒng)（包括源程序）。課程設(shè)計(jì)成績(jī)：上機(jī)情況（20%）包括出勤情況、調(diào)試表現(xiàn)。設(shè)計(jì)報(bào)告占40％，設(shè)計(jì)作品占40％。成績(jī)?cè)u(píng)定實(shí)行優(yōu)、良、中、及格和不及格五個(gè)等級(jí)。優(yōu)秀者人數(shù)一般不得超過(guò)總?cè)藬?shù)的20%。不及格者不能得到相應(yīng)的學(xué)分，需重新做課程設(shè)計(jì)，經(jīng)指導(dǎo)教師考核及格后，方可取得相應(yīng)學(xué)分。有關(guān)的考查相關(guān)材料（文字材料以及磁盤或光盤）統(tǒng)一妥善保管。七、建議教材與教學(xué)參考書[1] 《數(shù)據(jù)結(jié)構(gòu)》，嚴(yán)蔚敏 吳偉民 編著，清華大學(xué)出版社[2] 《數(shù)據(jù)結(jié)構(gòu)題集》嚴(yán)蔚敏 吳偉民 米寧 編著，清華大學(xué)出版社