數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)

1、數(shù)據(jù)結(jié)構(gòu)與算法分析課程設(shè)計(jì)內(nèi)容體系主要內(nèi)容數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)課程，可使學(xué)生深化理解書本知識，致力于用學(xué)過的理論知識和上機(jī)取得的實(shí)踐經(jīng)驗(yàn)，解決具體、復(fù)雜的實(shí)際問題，培養(yǎng)軟件工作者所需的動(dòng)手能力、獨(dú)立解決問題的能力。該課程設(shè)計(jì)側(cè)重軟件設(shè)計(jì)的綜合訓(xùn)練，包括問題分析、總體結(jié)構(gòu)設(shè)計(jì)、用戶界面設(shè)計(jì)、程序設(shè)計(jì)基本技能和技巧、多人合作，以至一整套軟件工作規(guī)范的訓(xùn)練和科學(xué)作風(fēng)的培養(yǎng)。一、 課程設(shè)計(jì)要求學(xué)生必須仔細(xì)閱讀數(shù)據(jù)結(jié)構(gòu)與算法分析課程設(shè)計(jì)方案，認(rèn)真主動(dòng)完成課程設(shè)計(jì)的要求。有問題及時(shí)主動(dòng)通過各種方式與教師聯(lián)系溝通。學(xué)生要發(fā)揮自主學(xué)習(xí)的能力，充分利用時(shí)間，安排好課程設(shè)計(jì)的時(shí)間計(jì)劃，并在課程設(shè)計(jì)過程中不斷檢測自己的

2、計(jì)劃完成情況，及時(shí)的向教師匯報(bào)。課程設(shè)計(jì)按照教學(xué)要求需要兩周時(shí)間完成，兩周中每天（按每周5天）至少要上3-4小時(shí)的機(jī)來調(diào)試C語言設(shè)計(jì)的程序，總共至少要上機(jī)調(diào)試程序30小時(shí)。二、 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)的具體內(nèi)容本次課程設(shè)計(jì)完成如下模塊（共9個(gè)模塊，學(xué)生可以在其中至少挑選6個(gè)功能塊完成，但有*號的模塊是必須要選擇的）（1） 運(yùn)動(dòng)會(huì)分?jǐn)?shù)統(tǒng)計(jì)* 任務(wù)：參加運(yùn)動(dòng)會(huì)有n個(gè)學(xué)校，學(xué)校編號為1n。比賽分成m個(gè)男子項(xiàng)目，和w個(gè)女子項(xiàng)目。項(xiàng)目編號為男子1m，女子m+1m+w。不同的項(xiàng)目取前五名或前三名積分；取前五名的積分分別為：7、5、3、2、1，前三名的積分分別為：5、3、2；哪些取前五名或前三名由學(xué)生自己設(shè)定。（

3、m<=20,n<=20）功能要求：l 可以輸入各個(gè)項(xiàng)目的前三名或前五名的成績；l 能統(tǒng)計(jì)各學(xué)?？偡?；l 可以按學(xué)校編號、學(xué)?？偡帧⒛信畧F(tuán)體總分排序輸出；l 可以按學(xué)校編號查詢學(xué)校某個(gè)項(xiàng)目的情況；可以按項(xiàng)目編號查詢?nèi)〉们叭蚯拔迕膶W(xué)校。 規(guī)定：輸入數(shù)據(jù)形式和范圍：20以內(nèi)的整數(shù)（如果做得更好可以輸入學(xué)校的名稱，運(yùn)動(dòng)項(xiàng)目的名稱）輸出形式：有中文提示，各學(xué)校分?jǐn)?shù)為整形界面要求：有合理的提示，每個(gè)功能可以設(shè)立菜單，根據(jù)提示，可以完成相關(guān)的功能要求。存儲結(jié)構(gòu)：學(xué)生自己根據(jù)系統(tǒng)功能要求自己設(shè)計(jì)，但是要求運(yùn)動(dòng)會(huì)的相關(guān)數(shù)據(jù)要存儲在數(shù)據(jù)文件中。（數(shù)據(jù)文件的數(shù)據(jù)讀寫方法等相關(guān)內(nèi)容在c語言程序設(shè)計(jì)的書

4、上，請自學(xué)解決）請?jiān)谧詈蟮纳辖毁Y料中指明你用到的存儲結(jié)構(gòu)；測試數(shù)據(jù)：要求使用1、全部合法數(shù)據(jù)；2、整體非法數(shù)據(jù)；3、局部非法數(shù)據(jù)。進(jìn)行程序測試，以保證程序的穩(wěn)定。測試數(shù)據(jù)及測試結(jié)果請?jiān)谏辖坏馁Y料中寫明；（2）訂票系統(tǒng) 任務(wù)：通過此系統(tǒng)可以實(shí)現(xiàn)如下功能：錄入：可以錄入航班情況（數(shù)據(jù)可以存儲在一個(gè)數(shù)據(jù)文件中，數(shù)據(jù)結(jié)構(gòu)、具體數(shù)據(jù)自定）查詢：可以查詢某個(gè)航線的情況（如，輸入航班號，查詢起降時(shí)間，起飛抵達(dá)城市，航班票價(jià)，票價(jià)折扣，確定航班是否滿倉）；可以輸入起飛抵達(dá)城市，查詢飛機(jī)航班情況；訂票：可以訂票（訂票情況可以存在一個(gè)數(shù)據(jù)文件中，結(jié)構(gòu)自己設(shè)定），如果該航班已經(jīng)無票，可以提供相關(guān)可選擇航班；退票：可

5、退票，退票后修改相關(guān)數(shù)據(jù)文件；客戶資料有姓名，證件號，訂票數(shù)量及航班情況，訂單要有編號。修改航班信息：當(dāng)航班信息改變可以修改航班數(shù)據(jù)文件要求：根據(jù)以上功能說明，設(shè)計(jì)航班信息，訂票信息的存儲結(jié)構(gòu)，設(shè)計(jì)程序完成功能； （3）文章編輯* 功能：輸入一頁文字，程序可以統(tǒng)計(jì)出文字、數(shù)字、空格的個(gè)數(shù)。靜態(tài)存儲一頁文章，每行最多不超過80個(gè)字符，共N行；要求：（1）分別統(tǒng)計(jì)出其中英文字母數(shù)和空格數(shù)及整篇文章總字?jǐn)?shù)；（2）統(tǒng)計(jì)某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；（3）刪除某一子串，并將后面的字符前移。（4）存儲結(jié)構(gòu)使用線性表，分別用幾個(gè)子函數(shù)實(shí)現(xiàn)相應(yīng)的功能；輸入數(shù)據(jù)的形式和范圍：可以輸入大寫、小寫的英

6、文字母、任何數(shù)字及標(biāo)點(diǎn)符號。輸出形式：（1）分行輸出用戶輸入的各行字符；（2）分4行輸出"全部字母數(shù)"、"數(shù)字個(gè)數(shù)"、"空格個(gè)數(shù)"、"文章總字?jǐn)?shù)"（3）輸出刪除某一字符串后的文章；（4）約瑟夫環(huán)（Joseph）任務(wù)：編號是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ì)一個(gè)程

7、序來求出出列順序。要求：利用單向循環(huán)鏈表存儲結(jié)構(gòu)模擬此過程，按照出列的順序輸出各個(gè)人的編號。測試數(shù)據(jù)：m的初值為20，n=7 ,7個(gè)人的密碼依次為3，1，7，2，4，7，4，首先m=6,則正確的輸出是什么？輸入數(shù)據(jù)：建立輸入處理輸入數(shù)據(jù)，輸入m的初值，n ，輸入每個(gè)人的密碼，建立單循環(huán)鏈表。輸出形式：建立一個(gè)輸出函數(shù)，將正確的輸出序列（5）猴子選大王* 任務(wù)：一堆猴子都有編號，編號是1，2，3 .m ,這群猴子（m個(gè)）按照1-m的順序圍坐一圈，從第1開始數(shù)，每數(shù)到第N個(gè)，該猴子就要離開此圈，這樣依次下來，直到圈中只剩下最后一只猴子，則該猴子為大王。輸入數(shù)據(jù)：輸入m,n m,n 為整數(shù)，n<

8、;m輸出形式：中文提示按照m個(gè)猴子，數(shù)n 個(gè)數(shù)的方法，輸出為大王的猴子是幾號 ，建立一個(gè)函數(shù)來實(shí)現(xiàn)此功能 （6）建立二叉樹，層序、先序遍歷（ 用遞歸或非遞歸的方法都可以）* 任務(wù)：要求能夠輸入樹的各個(gè)結(jié)點(diǎn)，并能夠輸出用不同方法遍歷的遍歷序列；分別建立建立二叉樹存儲結(jié)構(gòu)的的輸入函數(shù)、輸出層序遍歷序列的函數(shù)、輸出先序遍歷序列的函數(shù)； （7）赫夫曼樹的建立任務(wù) ：建立建立最優(yōu)二叉樹函數(shù) 要求：可以建立函數(shù)輸入二叉樹，并輸出其赫夫曼樹在上交資料中請寫明：存儲結(jié)構(gòu)、 基本算法（可以使用程序流程圖） 、輸入輸出、源程序、測試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；（8）紙牌游戲* 任務(wù)：

9、編號為1-52張牌，正面向上，從第2張開始，以2為基數(shù)，是2的倍數(shù)的牌翻一次，直到最后一張牌；然后，從第3張開始，以3為基數(shù)，是3的倍數(shù)的牌翻一次，直到最后一張牌；然后從第4張開始，以4為基數(shù)，是4的倍數(shù)的牌翻一次， 直到最后一張牌；.再依次5的倍數(shù)的牌翻一次，6的，7的 直到 以52為基數(shù)的 翻過，輸出：這時(shí)正面向上的牌有哪些？ （9）圖的建立及輸出任務(wù)：建立圖的存儲結(jié)構(gòu)（圖的類型可以是有向圖、無向圖、有向網(wǎng)、無向網(wǎng)，學(xué)生可以任選兩種類型），能夠輸入圖的頂點(diǎn)和邊的信息，并存儲到相應(yīng)存儲結(jié)構(gòu)中，而后輸出圖的鄰接矩陣。 要求：給出圖的深度優(yōu)先和廣度優(yōu)先遍歷算法，并給出遍歷過程的動(dòng)態(tài)演示效果三、

10、上交相關(guān)內(nèi)容要求上交的成果的內(nèi)容必須由以下四個(gè)部分組成，缺一不可1 上交源程序：學(xué)生按照課程設(shè)計(jì)的具體要求所開發(fā)的所有源程序（應(yīng)該放到一個(gè)文件夾中）；2 上交程序的說明文件：（保存在.txt中）在說明文檔中應(yīng)該寫明上交程序所在的目錄，上交程序的主程序文件名，如果需要安裝，要有程序的安裝使用說明；3 課程設(shè)計(jì)報(bào)告：（保存在word 文檔中，文件名要求 按照"姓名-學(xué)號-課程設(shè)計(jì)報(bào)告"起名，如文件名為"張三-001-課程設(shè)計(jì)報(bào)告".doc ）按照課程設(shè)計(jì)的具體要求建立的功能模塊，每個(gè)模塊要求按照如下幾個(gè)內(nèi)容認(rèn)真完成；其中包括:l 需求分析：在該部分中敘述，每

11、個(gè)模塊的功能要求l 概要設(shè)計(jì)：在此說明每個(gè)部分的算法設(shè)計(jì)說明（可以是描述算法的流程圖），每個(gè)程序中使用的存儲結(jié)構(gòu)設(shè)計(jì)說明（如果指定存儲結(jié)構(gòu)請寫出該存儲結(jié)構(gòu)的定義。l 詳細(xì)設(shè)計(jì)：各個(gè)算法實(shí)現(xiàn)的源程序，對每個(gè)題目要有相應(yīng)的源程序（可以是一組源程序，每個(gè)功能模塊采用不同的函數(shù)實(shí)現(xiàn)）源程序要按照寫程序的規(guī)則來編寫。要結(jié)構(gòu)清晰，重點(diǎn)函數(shù)的重點(diǎn)變量，重點(diǎn)功能部分要加上清晰的程序注釋。l 調(diào)試分析：測試數(shù)據(jù)，測試輸出的結(jié)果，時(shí)間復(fù)雜度分析，和每個(gè)模塊設(shè)計(jì)和調(diào)試時(shí)存在問題的思考（問題是哪些？問題如何解決？），算法的改進(jìn)設(shè)想。4. 課設(shè)總結(jié)： （保存在word 文檔中）總結(jié)可以包括 : 課程設(shè)計(jì) 過程的收獲、遇

12、到問題、遇到問題解決問題過程的思考、程序調(diào)試能力的思考、對數(shù)據(jù)結(jié)構(gòu)這門課程的思考、在課程設(shè)計(jì)過程中對數(shù)據(jù)結(jié)構(gòu)課程的認(rèn)識等內(nèi)容數(shù)據(jù)結(jié)構(gòu)與算法分析課程內(nèi)容體系主要內(nèi)容教學(xué)單元模塊具體教學(xué)內(nèi)容緒論緒論部分是全書的預(yù)備知識，主要對ADL語言、數(shù)據(jù)結(jié)構(gòu)與算法、算法分析基礎(chǔ)、OOP、和C+做了簡單介紹基本數(shù)據(jù)結(jié)構(gòu)基本數(shù)據(jù)結(jié)構(gòu)部分包括線性表、堆棧與隊(duì)列、數(shù)組、字符串、整數(shù)集合類、樹（包括AVL樹、伸展樹等）、圖（包括網(wǎng)絡(luò)流等問題的討論）、散列（Hash）等典型算法典型算法部分主要介紹了若干典型算法的實(shí)現(xiàn)，并給出必要的復(fù)雜性分析和比較過程，具體包括遞歸、排序、查找和內(nèi)存管理等復(fù)雜數(shù)據(jù)結(jié)構(gòu)復(fù)雜數(shù)據(jù)結(jié)構(gòu)部分主要包

13、括優(yōu)先級隊(duì)列、不相交集合類和文件結(jié)構(gòu)等算法設(shè)計(jì)技巧典型算法設(shè)計(jì)技巧的介紹，主要包括貪婪算法、分治算法、動(dòng)態(tài)規(guī)劃、回溯算法和隨機(jī)化算法等應(yīng)用應(yīng)用部分是上述數(shù)據(jù)結(jié)構(gòu)和典型算法的一些應(yīng)用示例，具體包括事件驅(qū)動(dòng)模擬、等價(jià)類、殘缺棋盤和圖象壓縮等問題的討論，在課時(shí)允許的情況下還會(huì)介紹攤還分析、紅黑樹等數(shù)據(jù)結(jié)構(gòu)與算法分析課程實(shí)踐內(nèi)容體系主要內(nèi)容實(shí)踐教學(xué)單元模塊實(shí)踐教學(xué)基本要求實(shí)踐教學(xué)具體內(nèi)容趣味程序設(shè)計(jì)實(shí)踐1.熟悉編程環(huán)境2.復(fù)習(xí)C語言程序設(shè)計(jì)的基本內(nèi)容1.開學(xué)第一、二周布置若干趣味程序設(shè)計(jì)題目，如奇數(shù)階幻陣算法、萬年歷算法、迷宮算法等。并完成：2.隨機(jī)產(chǎn)生n個(gè)整數(shù)，然后用一種排序算法將它們從小到大排序。

14、3.試編一程序，用貪心法求解一般的著色問題。鏈表應(yīng)用實(shí)驗(yàn)1.熟悉鏈表結(jié)構(gòu)2.掌握鏈表結(jié)構(gòu)上的各種操作3.學(xué)會(huì)運(yùn)用鏈表結(jié)構(gòu)求解問題1.試將本章介紹的兩種Josephus問題的求解過程在計(jì)算機(jī)中實(shí)現(xiàn)，實(shí)現(xiàn)時(shí)要求輸出的不是整數(shù)，而是實(shí)際的人名。2.設(shè)A與B分別為兩個(gè)帶有頭結(jié)點(diǎn)的有序循環(huán)鏈表（所謂有序是指鏈接點(diǎn)按數(shù)據(jù)域值大小鏈接，本題不妨設(shè)按數(shù)據(jù)域值從小到大排列），list1和list2分別為指向兩個(gè)鏈表的指針。請寫出并在計(jì)算機(jī)上實(shí)現(xiàn)將這兩個(gè)鏈表合并為一個(gè)帶頭結(jié)點(diǎn)的有序循環(huán)鏈表的算法。棧與隊(duì)列應(yīng)用實(shí)驗(yàn)1.熟悉棧和隊(duì)列結(jié)構(gòu)2.掌握棧和隊(duì)列結(jié)構(gòu)上的各種操作3.學(xué)會(huì)運(yùn)用棧和隊(duì)列結(jié)構(gòu)求解問題1. 設(shè)計(jì)實(shí)現(xiàn)一個(gè)

15、求解n階Hanoi塔問題的算法提示：將n個(gè)圓盤由A依次移到C，B作為輔助塔座。當(dāng)n=1時(shí)，可以直接完成。否則，將塔座A頂上的n-1個(gè)圓盤移動(dòng)到塔座B上，用塔座C作為輔助塔座；然后移第n個(gè)圓盤；最后將塔座B上的n-1個(gè)圓盤移到塔座C上，并用塔座A作為輔助塔座。2. 根據(jù)書中介紹的思想，設(shè)計(jì)并實(shí)現(xiàn)一個(gè)對簡化表達(dá)式求值的系統(tǒng)。3. 在計(jì)算機(jī)上模擬實(shí)現(xiàn)農(nóng)夫過河問題的解。文本文件檢索實(shí)驗(yàn)1.熟悉字符串的操作2.學(xué)會(huì)運(yùn)用字符串的操作進(jìn)行文本檢索和查詢。1. 根據(jù)課堂介紹設(shè)計(jì)實(shí)現(xiàn)KMP算法2. 試設(shè)計(jì)一個(gè)簡單的文本編輯器，使之具有對字符串的輸入、輸出、插入、刪除、查找和替換等功能3. 設(shè)計(jì)實(shí)現(xiàn)一個(gè)通用的判定

16、回文個(gè)數(shù)問題的算法程序 稀疏矩陣和廣義表實(shí)驗(yàn)1熟悉稀疏矩陣和廣義表結(jié)構(gòu)2掌握稀疏矩陣和廣義表結(jié)構(gòu)上的各種操作3學(xué)會(huì)運(yùn)用稀疏矩陣和廣義表結(jié)構(gòu)求解問題1. 設(shè)計(jì)實(shí)現(xiàn)兩個(gè)普通矩陣相乘的算法2. 實(shí)現(xiàn)用三元組表示法實(shí)現(xiàn)稀疏矩陣相加及轉(zhuǎn)置算法3. 設(shè)計(jì)實(shí)現(xiàn)兩個(gè)N次一元多項(xiàng)式相加的算法程序 樹結(jié)構(gòu)實(shí)驗(yàn)1.熟悉樹和二叉樹結(jié)構(gòu)2.掌握樹和二叉樹結(jié)構(gòu)上的各種操作3.學(xué)會(huì)運(yùn)用樹和二叉樹結(jié)構(gòu)求解問題1. 設(shè)計(jì)一個(gè)程序，根據(jù)二叉樹的先根序列和對稱序序列創(chuàng)建一棵用左右指針表示的二叉樹2. 根據(jù)哈夫曼算法創(chuàng)建哈夫曼樹，并求樹中每個(gè)外部結(jié)點(diǎn)的編碼3. 設(shè)計(jì)一個(gè)程序，把中綴表達(dá)式轉(zhuǎn)換成一棵二叉樹，然后通過后序遍歷計(jì)算表達(dá)式的

17、值4. 設(shè)計(jì)實(shí)現(xiàn)一個(gè)完成對BST樹進(jìn)行插入、刪除、查找操作的算法，并希望有部分同學(xué)能進(jìn)一步把該算法改寫為針對AVL樹的相關(guān)算法圖結(jié)構(gòu)實(shí)驗(yàn)1.熟悉圖結(jié)構(gòu)2.掌握圖結(jié)構(gòu)上的各種操作3.學(xué)會(huì)運(yùn)用圖結(jié)構(gòu)求解問題采用兩種不同的圖的表示方法，實(shí)現(xiàn)拓?fù)渑判蚝完P(guān)鍵路徑的求解過程。使用實(shí)現(xiàn)的算法對于下圖所示的AOE網(wǎng)，求出各活動(dòng)的可能的最早開始時(shí)間和最晚開始時(shí)間。輸出整個(gè)工程的最短完成時(shí)間是多少? 哪些活動(dòng)是關(guān)鍵活動(dòng)? 說明哪項(xiàng)活動(dòng)提高速度后能導(dǎo)致整個(gè)工程提前完成?分析不同存儲結(jié)構(gòu)對于算法效率的影響。散列表實(shí)驗(yàn)1.熟悉散列表結(jié)構(gòu)2.掌握散列函數(shù)的生成方法,掌握常規(guī)沖突處理辦法3. 學(xué)會(huì)運(yùn)用散列結(jié)構(gòu)求解問題試根據(jù)

18、全年級學(xué)生的姓名，構(gòu)造一個(gè)散列表，選擇適當(dāng)?shù)纳⒘泻瘮?shù)和解決碰撞方法，設(shè)計(jì)并實(shí)現(xiàn)插入、刪除和查找算法，統(tǒng)計(jì)碰撞發(fā)生的次數(shù)。（用拉鏈法解決碰撞時(shí)負(fù)載因子取2，用開地址法時(shí)取1/2）航班信息查詢與檢索實(shí)驗(yàn)設(shè)計(jì)1.掌握查找與排序的各種算法2.學(xué)會(huì)選用和設(shè)計(jì)實(shí)際問題所需的查找與排序算法對于直接插入排序、直接選擇排序、起泡排序、Shell排序、快速排序和堆排序等六種算法進(jìn)行上機(jī)實(shí)習(xí)。要求：1. 被排序的對象由計(jì)算機(jī)隨機(jī)生成，長度分別取20，100，500三種。2. 算法中增加比較次數(shù)和移動(dòng)次數(shù)的統(tǒng)計(jì)功能。3. 對實(shí)習(xí)的結(jié)果做比較分析。4. 設(shè)計(jì)實(shí)現(xiàn)一個(gè)航班信息查詢與檢索系統(tǒng)課程實(shí)驗(yàn)參考教材：l 魏開平等編

19、著. 數(shù)據(jù)結(jié)構(gòu)輔導(dǎo)與實(shí)驗(yàn). 清華大學(xué)出版社，2006年第1版l 瞿有甜，數(shù)據(jù)結(jié)構(gòu)與算法分析實(shí)驗(yàn)指導(dǎo)書，2004.9 實(shí)驗(yàn)1 猴子選大王任務(wù)：一堆猴子都有編號，編號是1，2，3 .m ,這群猴子（m個(gè)）按照1-m的順序圍坐一圈，從第1開始數(shù)，每數(shù)到第N個(gè)，該猴子就要離開此圈，這樣依次下來，直到圈中只剩下最后一只猴子，則該猴子為大王。輸入數(shù)據(jù)：輸入m,n m,n 為整數(shù)，n<m輸出形式：中文提示按照m個(gè)猴子，數(shù)n 個(gè)數(shù)的方法，輸出為大王的猴子是幾號 ，建立一個(gè)函數(shù)來實(shí)現(xiàn)此功能 。實(shí)驗(yàn)內(nèi)容：源程序：#include <stdio.h>#include <stdlib.h>

20、;typedef struct nodeint data;struct node * next;ListNode;typedef ListNode * LinkList;/*建立單循環(huán)鏈表函數(shù)*/LinkList InitRing(int n,LinkList R)ListNode *p,*q;int i;R=q=(ListNode *)malloc(sizeof(ListNode);for(i=1;i<n;i+)p=(ListNode *)malloc(sizeof(ListNode);q->data=i;q->next=p;q=p;p->data=n;p->n

21、ext=R;R=p;return R;/*選擇函數(shù)*/LinkList DeleteDeath(int n,int k,LinkList R)int i,j;ListNode *p,*q;p=R;for(i=1;i<=n/2;i+)for(j=1;j<=k-1;j+)p=p->next;q=p->next;p->next=q->next;printf("%4d",q->data);if(i%10=0)printf("n");free(q);R=p;return R;/*輸出函數(shù)*/void OutRing(int

22、 n,LinkList R)int i;ListNode *p;p=R;for(i=1;i<=n/2;i+,p=p->next) printf("%4d",p->data); if(i%10=0) printf("n");printf("n"); printf("猴大王的號碼：n"); printf("4%d",p->next);/*主函數(shù)*/void main()LinkList R;int n,k;LinkList InitRing(int n,LinkList R

23、);printf("猴子的總數(shù)N:");scanf("%d",&n);printf("報(bào)到要被淘汰數(shù)字 K:");scanf("%d",&k);printf("被淘汰的猴子：n");R=InitRing(n,R);R=DeleteDeath(n,k,R); printf("n"); OutRing(n,R);實(shí)驗(yàn)結(jié)果：實(shí)驗(yàn)2 訂票系統(tǒng)任務(wù)：通過此系統(tǒng)可以實(shí)現(xiàn)如下功能：錄入：可以錄入航班情況（數(shù)據(jù)可以存儲在一個(gè)數(shù)據(jù)文件中，數(shù)據(jù)結(jié)構(gòu)、具體數(shù)據(jù)自定）查詢：可以查詢某

24、個(gè)航線的情況（如，輸入航班號，查詢起降時(shí)間，起飛抵達(dá)城市，航班票價(jià)，票價(jià)折扣，確定航班是否滿倉）；可以輸入起飛抵達(dá)城市，查詢飛機(jī)航班情況；訂票：可以訂票（訂票情況可以存在一個(gè)數(shù)據(jù)文件中，結(jié)構(gòu)自己設(shè)定），如果該航班已經(jīng)無票，可以提供相關(guān)可選擇航班；退票：可退票，退票后修改相關(guān)數(shù)據(jù)文件；客戶資料有姓名，證件號，訂票數(shù)量及航班情況，訂單要有編號。修改航班信息：當(dāng)航班信息改變可以修改航班數(shù)據(jù)文件要求：根據(jù)以上功能說明，設(shè)計(jì)航班信息，訂票信息的存儲結(jié)構(gòu)，設(shè)計(jì)程序完成功能； 實(shí)驗(yàn)內(nèi)容：源程序：#include <stdio.h>#include <stdlib.h>#include

25、<conio.h>#include <io.h>#include <math.h>#include <string.h>#include <ctype.h>#define TRUE 1#define FALSE 0typedef int BOOL;#define NEW(type, size) (type*)malloc(sizeof(type) * size)typedef struct _date /* 日期 */ int m_year; int m_month; int m_day; DATE;typedef struct _t

26、ime /* 時(shí)間 */ int m_hour; int m_min; TIME;typedef struct _flight /* 航班數(shù)據(jù) */ int m_fltno; /* 航班號，若此成員為-1，則表示此航班未使用 */ char m_szFrom30; /* 起飛港 */ char m_szPass30; /* 途經(jīng)港 */ char m_szTo30; /* 到達(dá)港 */ TIME m_start; /* 起飛時(shí)間 */ TIME m_arrive; /* 到達(dá)時(shí)間 */ TIME m_fly; /* 飛行固定時(shí)間 */ int m_people; /* 乘客限額 */ FLIG

27、HT, *PFLIGHT;typedef struct _passengernode /* 乘客數(shù)據(jù) */ char m_szName20; /* 姓名 */ char m_szCorp30; /* 單位 */ char m_szNumber19; /* 身份證號，考慮到字母的情況，故使用字符串 */ DATE m_Date; /* 訂票日期 */ int m_fltno; /* 航班號 */ int m_seatno; /* 座位號 */ PASSENGER, *PPASSENGER;typedef struct _psgnode /* 乘客結(jié)點(diǎn) */ PASSENGER m_psg; st

28、ruct _psgnode *next; NODE, *PNODE;/* 清空鍵盤緩沖區(qū) */void ClearBuffer(void);/* 讀取航班數(shù)據(jù) */void ReadFlight(FLIGHT fltlist);/* 讀取乘客數(shù)據(jù) */void ReadPassenger(PNODE psglist);/* 添加航班 */BOOL AddFlight(FLIGHT fltlist, PFLIGHT fltdata);/* 刪除航班 */void DelFlight(FLIGHT fltlist, int index);/* 添加乘客 */void AddPassenger(PN

29、ODE psglist, PPASSENGER psgdata);/* 刪除乘客 */BOOL DelPassenger(PNODE psglist, int index);/* 清空乘客鏈表 */void ClearPsgList(PNODE psglist);/* 取得乘客總數(shù) */unsigned int GetPsgCount(PNODE psglist);BOOL datecmp(DATE* date1, DATE* date2);void Book(FLIGHT fltlist, PNODE psglist);void query(FLIGHT fltlist, PNODE psg

30、list);void fltnumber(FLIGHT fltlist);void psgname (PNODE psglist);void fromto (FLIGHT fltlist);void fltdat(FLIGHT fltlist, PNODE psglist);/* 保存航班數(shù)據(jù) */void SaveFlight(FLIGHT fltlist);/* 保存乘客數(shù)據(jù) */void SavePassenger(PNODE psglist);/* 退出 */void Quit(FLIGHT fltlist, PNODE psglist);BOOL datecmp(DATE* date

31、1, DATE* date2) return (date1->m_year = date2->m_year && date1->m_month = date2->m_month && date1->m_day = date2->m_day);BOOL timecmp(TIME* time1, TIME* time2) return (time1->m_hour = time2->m_hour && time1->m_min = time2->m_min);void ClearBuffer

32、(void) getchar();void ReadFlight(FLIGHT fltlist) FILE *fp; if (fp = fopen("flight.dat", "rb") != NULL) fread(fltlist, sizeof(FLIGHT), 40, fp); else int i; for (i = 0; i < 40; i+) fltlisti.m_fltno = -1; fclose(fp);void ReadPassenger(PNODE psglist) FILE *fp; if (fp = fopen("

33、;psg.dat", "rb") = NULL) psglist->next = NULL; else int i, n; fread(&n, sizeof(int), 1, fp); for (i = 0; i < n; i+) PASSENGER psg; fread(&psg, sizeof(PASSENGER), 1, fp); AddPassenger(psglist, &psg); BOOL AddFlight(FLIGHT fltlist, PFLIGHT fltdata) int i; BOOL bResult

34、= FALSE; for (i = 0; i < 40; i+) if (fltlisti.m_fltno = -1) memcpy(&fltlisti, fltdata, sizeof(FLIGHT); bResult = TRUE; break; return bResult;void DelFlight(FLIGHT fltlist, int index) fltlistindex.m_fltno = -1;void AddPassenger(PNODE psglist, PPASSENGER psgdata) PNODE p, q; for (p = psglist; p

35、->next != NULL; p = p->next) ; q = NEW(NODE, 1); memcpy(&q->m_psg, psgdata, sizeof(PASSENGER); q->next = NULL; p->next = q;BOOL DelPassenger(PNODE psglist, int index) int i = 0; PNODE p, q; for (p = psglist->next; p->next != NULL; p = p->next) i+; if (p != NULL &&

36、 i = index - 1) q = p->next; p->next = q->next; free(q); return TRUE; else return FALSE;void ClearPsgList(PNODE psglist) PNODE p = psglist->next, q; while (p != NULL && p->next != NULL) q = p; p = p->next; free(q); unsigned int GetPsgCount(PNODE psglist) PNODE p; unsigned i

37、nt s = 0; for (p = psglist->next; p != NULL; p = p->next) s+; return s;void Book(FLIGHT fltlist, PNODE psglist) char c = 'y' BOOL b; while (c = 'y' | c = 'Y') int i; PASSENGER psg; printf("請輸入航班號："); scanf("%d", &psg.m_fltno); while (psg.m_fltno

38、>= 10000 | psg.m_fltno < 0) printf("請重新輸入："); scanf("%d", &psg.m_fltno); for(i = 0; i < 40; i+) if(fltlisti.m_fltno = psg.m_fltno) PNODE p;BOOL *q;int j;printf("請輸入訂票日期：(yyyy,mm,dd)");q = NEW(int, fltlisti.m_people);for (j = 0; j < fltlisti.m_people; j+)

39、 qj = FALSE;for (p = psglist->next; p != NULL; p = p->next) if(datecmp(&p->m_psg.m_Date, &psg.m_Date) && psg.m_fltno = p->m_psg.m_fltno) qp->m_psg.m_seatno - 1 = TRUE;printf("以下座位尚未有人訂：");for (j=0; j < fltlisti.m_people; j+) if (!qj) printf("%d "

40、, j + 1);printf("n請輸入訂票座位號：");scanf("%d", &psg.m_seatno);b = FALSE;do int k; if (psg.m_seatno > 0 && psg.m_seatno <= fltlisti.m_people + 1) if (!qpsg.m_seatno - 1) b = TRUE; break; else printf("這個(gè)座位有人了！"); else printf("數(shù)據(jù)非法！"); scanf("%d

41、", &psg.m_seatno); while (!b);printf("請輸入乘客姓名：") ; scanf("%s", psg.m_szName); printf("請輸入乘客單位：");scanf("%s", psg.m_szCorp); printf("請輸入乘客身份證號：");scanf("%s", psg.m_szNumber); AddPassenger(psglist, &psg);printf("您的訂票已成功。&quo

42、t;);free(q); c = getchar(); void query(FLIGHT fltlist, PNODE psglist) for (;) char c; system("cls"); printf("航班查詢n"); printf("n"); printf("1.按航班號查詢n"); printf("2.按姓名查詢乘客n"); printf("3.按起飛、到達(dá)港查詢n"); printf("4.按日期查詢航班情況n"); printf(&

43、quot;5.返回n"); printf("n請選擇1-5："); c = getchar(); switch (c) case '1':fltnumber(fltlist);break; case '2':psgname(psglist);break; case '3':fromto(fltlist);break; case '4':fltdat(fltlist, psglist);break; case '5':break; default:continue; if (c = &#

44、39;5') break; void fltnumber(FLIGHT fltlist) char c = 'y' while (c = 'y' | c = 'Y') BOOL b = FALSE; int fltno, i; printf("可以查詢的航班號："); for (i = 0; i < 40; i+) if (fltlisti.m_fltno != -1) b = TRUE;printf("%d ", fltlisti.m_fltno); if (!b) printf("

45、;無n按任意鍵返回。"); getch(); return; printf("n請輸入要查詢的航班號："); scanf("%d", &fltno); for(i = 0; i < 40; i+) if (fltlisti.m_fltno = fltno) printf("%s-%s-%sn", fltlisti.m_szFrom, fltlisti.m_szPass, fltlisti.m_szTo);printf("起飛時(shí)間：%2d:%02d 到達(dá)時(shí)間：%2d:%02d 飛行固定時(shí)間：%2d:%0

46、2dn", fltlisti.m_start.m_hour, fltlisti.m_start.m_min, fltlisti.m_arrive.m_hour, fltlisti.m_arrive.m_min, fltlisti.m_fly.m_hour, fltlisti.m_fly.m_min);printf("乘客限額：%dn", fltlisti.m_people);break; printf("繼續(xù)查詢嗎？(y/n)"); ClearBuffer(); c = getchar(); void psgname(PNODE psglist

47、) char c = 'y' while (c = 'y' | c = 'Y') char name20; PNODE p; BOOL b = FALSE; printf("請輸入乘客姓名："); scanf("%s",name); for (p = psglist->next; p != NULL; p = p->next) if(strcmp(p->m_psg.m_szName, name) = 0) b = TRUE;printf("姓名：%s 單位：%s 身份證號：%sn

48、", p->m_psg.m_szName, p->m_psg.m_szCorp, p->m_psg.m_szNumber);printf("訂票日期：printf("航班號：%d 座位號：%d", p->m_psg.m_fltno, p->m_psg.m_seatno); break; if (!b) printf("查無此人，按任意鍵退出"); getch(); return; printf("是否繼續(xù)查詢？(y/n)"); ClearBuffer(); c = getchar();

49、 void fromto (FLIGHT fltlist) char c = 'y' while (c = 'y' | c = 'Y') BOOL b = FALSE; char from30, to30; int i; printf("請輸入起飛港："); scanf("%s", from); printf("請輸入到達(dá)港："); scanf("%s", to); for(i = 0; i < 40; i+) if(strcmp(fltlisti.m_szFr

50、om,from)=0) if(strcmp(fltlisti.m_szTo,to)=0) b=TRUE; break; if(b) printf("%s-%s-%sn",fltlisti.m_szFrom,fltlisti.m_szPass,fltlisti.m_szTo); printf("起飛時(shí)間：%2d:%02d 到達(dá)時(shí)間：%2d:%02d 飛行固定時(shí)間：%2d:%02dn",fltlisti.m_start.m_hour,fltlisti.m_start.m_min,fltlisti.m_arrive.m_hour,fltlisti.m_arri

51、ve.m_min,fltlisti.m_fly.m_hour,fltlisti.m_fly.m_min); printf("乘客限額：%d",fltlisti.m_people); else printf("無此飛機(jī)"); getch(); printf("是否繼續(xù)查詢？"); ClearBuffer(); c = getchar(); void fltdat(FLIGHT fltlist, PNODE psglist) int people40, i; DATE date; PNODE p; for (i = 0; i < 4

52、0; i+) peoplei = 0; printf("請輸入您要查詢的日期(yyyy,mm,dd)："); scanf("%d,%d,%d", &date.m_year, &date.m_month, &date.m_day); for (p = psglist->next; p != NULL; p=p->next) if (datecmp(&date, &p->m_psg.m_Date) for(i=0;i<40;i+) if(fltlisti.m_fltno=p->m_psg.

53、m_fltno)peoplei+; for (i = 0; i < 40; i+) if (peoplei > 0) printf("%d %s-%s-%s 人數(shù)：%d", fltlisti.m_fltno, fltlisti.m_szFrom, fltlisti.m_szPass, fltlisti.m_szTo, peoplei); getch();void Add(FLIGHT fltlist) char c = 'y' while (c = 'y' | c = 'Y') FLIGHT flt; BOOL b

54、; printf("請輸入航班號(1 - 10000)："); scanf("%d", &flt.m_fltno); printf("請輸入起飛港："); scanf("%s", flt.m_szFrom); printf("請輸入途經(jīng)港："); scanf("%s", flt.m_szPass); printf("請輸入到達(dá)港："); scanf("%s", flt.m_szTo); printf("請輸入起飛時(shí)間(hh:mm)："); printf("請輸入到達(dá)時(shí)間(hh:mm)："); printf("請輸入飛行固定時(shí)間(hh:mm)："); printf("請輸入乘客限額："); scanf("%d", &flt.m_people); ClearBuffer(); if (AddFlight(fltlist, &flt) printf("添加成功，"); else printf("添加失敗，"); printf("繼續(xù)添加航班嗎(Y/N)？&q