【正文】 寫出并在計(jì)算機(jī)上實(shí)現(xiàn)將這兩個(gè)鏈表合并為一個(gè)帶頭結(jié)點(diǎn)的有序循環(huán)鏈表的算法。鏈表應(yīng)用實(shí)驗(yàn)，實(shí)現(xiàn)時(shí)要求輸出的不是整數(shù)，而是實(shí)際的人名。并完成：，然后用一種排序算法將它們從小到大排序。l 調(diào)試分析：測(cè)試數(shù)據(jù)，測(cè)試輸出的結(jié)果，時(shí)間復(fù)雜度分析，和每個(gè)模塊設(shè)計(jì)和調(diào)試時(shí)存在問(wèn)題的思考（問(wèn)題是哪些？問(wèn)題如何解決？），算法的改進(jìn)設(shè)想。l 詳細(xì)設(shè)計(jì)：各個(gè)算法實(shí)現(xiàn)的源程序，對(duì)每個(gè)題目要有相應(yīng)的源程序（可以是一組源程序，每個(gè)功能模塊采用不同的函數(shù)實(shí)現(xiàn)）源程序要按照寫程序的規(guī)則來(lái)編寫。輸入數(shù)據(jù)：輸入m,n m,n 為整數(shù)，nm輸出形式：中文提示按照m個(gè)猴子，數(shù)n 個(gè)數(shù)的方法，輸出為大王的猴子是幾號(hào) ，建立一個(gè)函數(shù)來(lái)實(shí)現(xiàn)此功能 （6）建立二叉樹(shù)，層序、先序遍歷（ 用遞歸或非遞歸的方法都可以）** 任務(wù)：要求能夠輸入樹(shù)的各個(gè)結(jié)點(diǎn)，并能夠輸出用不同方法遍歷的遍歷序列；分別建立建立二叉樹(shù)存儲(chǔ)結(jié)構(gòu)的的輸入函數(shù)、輸出層序遍歷序列的函數(shù)、輸出先序遍歷序列的函數(shù)； （7）赫夫曼樹(shù)的建立任務(wù) ：建立建立最優(yōu)二叉樹(shù)函數(shù) 要求：可以建立函數(shù)輸入二叉樹(shù)，并輸出其赫夫曼樹(shù)在上交資料中請(qǐng)寫明：存儲(chǔ)結(jié)構(gòu)、 基本算法（可以使用程序流程圖） 、輸入輸出、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；（8）紙牌游戲** 任務(wù)：編號(hào)為152張牌，正面向上，從第2張開(kāi)始，以2為基數(shù)，是2的倍數(shù)的牌翻一次，直到最后一張牌；然后，從第3張開(kāi)始，以3為基數(shù)，是3的倍數(shù)的牌翻一次，直到最后一張牌；然后…從第4張開(kāi)始，以4為基數(shù)，是4的倍數(shù)的牌翻一次， 直到最后一張牌；...再依次5的倍數(shù)的牌翻一次，6的，7的 直到 以52為基數(shù)的 翻過(guò)，輸出：這時(shí)正面向上的牌有哪些？ （9）圖的建立及輸出任務(wù)：建立圖的存儲(chǔ)結(jié)構(gòu)（圖的類型可以是有向圖、無(wú)向圖、有向網(wǎng)、無(wú)向網(wǎng)，學(xué)生可以任選兩種類型），能夠輸入圖的頂點(diǎn)和邊的信息，并存儲(chǔ)到相應(yīng)存儲(chǔ)結(jié)構(gòu)中，而后輸出圖的鄰接矩陣。測(cè)試數(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)鏈表。設(shè)計(jì)一個(gè)程序來(lái)求出出列順序。一開(kāi)始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m,從第一個(gè)仍開(kāi)始順時(shí)針?lè)较蜃?開(kāi)始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。（4）存儲(chǔ)結(jié)構(gòu)使用線性表，分別用幾個(gè)子函數(shù)實(shí)現(xiàn)相應(yīng)的功能；輸入數(shù)據(jù)的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標(biāo)點(diǎn)符號(hào)。修改航班信息：當(dāng)航班信息改變可以修改航班數(shù)據(jù)文件要求：根據(jù)以上功能說(shuō)明，設(shè)計(jì)航班信息，訂票信息的存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)程序完成功能； （3）文章編輯** 功能：輸入一頁(yè)文字，程序可以統(tǒng)計(jì)出文字、數(shù)字、空格的個(gè)數(shù)。進(jìn)行程序測(cè)試，以保證程序的穩(wěn)定。存儲(chǔ)結(jié)構(gòu)：學(xué)生自己根據(jù)系統(tǒng)功能要求自己設(shè)計(jì)，但是要求運(yùn)動(dòng)會(huì)的相關(guān)數(shù)據(jù)要存儲(chǔ)在數(shù)據(jù)文件中。（m=20,n=20）功能要求：l 可以輸入各個(gè)項(xiàng)目的前三名或前五名的成績(jī)；l 能統(tǒng)計(jì)各學(xué)校總分；l 可以按學(xué)校編號(hào)、學(xué)?？偡?、男女團(tuán)體總分排序輸出；l 可以按學(xué)校編號(hào)查詢學(xué)校某個(gè)項(xiàng)目的情況；可以按項(xiàng)目編號(hào)查詢?nèi)〉们叭蚯拔迕膶W(xué)校。項(xiàng)目編號(hào)為男子1……m，女子m+1……m+w。二、 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)的具體內(nèi)容本次課程設(shè)計(jì)完成如下模塊（共9個(gè)模塊，學(xué)生可以在其中至少挑選6個(gè)功能塊完成，但有**號(hào)的模塊是必須要選擇的）（1） 運(yùn)動(dòng)會(huì)分?jǐn)?shù)統(tǒng)計(jì)** 任務(wù)：參加運(yùn)動(dòng)會(huì)有n個(gè)學(xué)校，學(xué)校編號(hào)為1……n。學(xué)生要發(fā)揮自主學(xué)習(xí)的能力，充分利用時(shí)間，安排好課程設(shè)計(jì)的時(shí)間計(jì)劃，并在課程設(shè)計(jì)過(guò)程中不斷檢測(cè)自己的計(jì)劃完成情況，及時(shí)的向教師匯報(bào)。一、 課程設(shè)計(jì)要求學(xué)生必須仔細(xì)閱讀《數(shù)據(jù)結(jié)構(gòu)與算法分析》課程設(shè)計(jì)方案，認(rèn)真主動(dòng)完成課程設(shè)計(jì)的要求。.. . . ..《數(shù)據(jù)結(jié)構(gòu)與算法分析》課程設(shè)計(jì)內(nèi)容體系主要內(nèi)容《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》課程，可使學(xué)生深化理解書本知識(shí)，致力于用學(xué)過(guò)的理論知識(shí)和上機(jī)取得的實(shí)踐經(jīng)驗(yàn)，解決具體、復(fù)雜的實(shí)際問(wèn)題，培養(yǎng)軟件工作者所需的動(dòng)手能力、獨(dú)立解決問(wèn)題的能力。該課程設(shè)計(jì)側(cè)重軟件設(shè)計(jì)的綜合訓(xùn)練，包括問(wèn)題分析、總體結(jié)構(gòu)設(shè)計(jì)、用戶界面設(shè)計(jì)、程序設(shè)計(jì)基本技能和技巧、多人合作，以至一整套軟件工作規(guī)范的訓(xùn)練和科學(xué)作風(fēng)的培養(yǎng)。有問(wèn)題及時(shí)主動(dòng)通過(guò)各種方式與教師聯(lián)系溝通。課程設(shè)計(jì)按照教學(xué)要求需要兩周時(shí)間完成，兩周中每天（按每周5天）至少要上34小時(shí)的機(jī)來(lái)調(diào)試C語(yǔ)言設(shè)計(jì)的程序，總共至少要上機(jī)調(diào)試程序30小時(shí)。比賽分成m個(gè)男子項(xiàng)目，和w個(gè)女子項(xiàng)目。不同的項(xiàng)目取前五名或前三名積分；取前五名的積分分別為：1，前三名的積分分別為：2；哪些取前五名或前三名由學(xué)生自己設(shè)定。 規(guī)定：輸入數(shù)據(jù)形式和范圍：20以內(nèi)的整數(shù)（如果做得更好可以輸入學(xué)校的名稱，運(yùn)動(dòng)項(xiàng)目的名稱）輸出形式：有中文提示，各學(xué)校分?jǐn)?shù)為整形界面要求：有合理的提示，每個(gè)功能可以設(shè)立菜單，根據(jù)提示，可以完成相關(guān)的功能要求。（數(shù)據(jù)文件的數(shù)據(jù)讀寫方法等相關(guān)內(nèi)容在c語(yǔ)言程序設(shè)計(jì)的書上，請(qǐng)自學(xué)解決）請(qǐng)?jiān)谧詈蟮纳辖毁Y料中指明你用到的存儲(chǔ)結(jié)構(gòu)；測(cè)試數(shù)據(jù)：要求使用全部合法數(shù)據(jù)；整體非法數(shù)據(jù)；局部非法數(shù)據(jù)。測(cè)試數(shù)據(jù)及測(cè)試結(jié)果請(qǐng)?jiān)谏辖坏馁Y料中寫明；（2）訂票系統(tǒng) 任務(wù)：通過(guò)此系統(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)無(wú)票，可以提供相關(guān)可選擇航班；退票：可退票，退票后修改相關(guān)數(shù)據(jù)文件；客戶資料有姓名，證件號(hào)，訂票數(shù)量及航班情況，訂單要有編號(hào)。靜態(tài)存儲(chǔ)一頁(yè)文章，每行最多不超過(guò)80個(gè)字符，共N行；要求：（1）分別統(tǒng)計(jì)出其中英文字母數(shù)和空格數(shù)及整篇文章總字?jǐn)?shù)；（2）統(tǒng)計(jì)某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；（3）刪除某一子串，并將后面的字符前移。輸出形式：（1）分行輸出用戶輸入的各行字符；（2）分4行輸出全部字母數(shù)、數(shù)字個(gè)數(shù)、空格個(gè)數(shù)、文章總字?jǐn)?shù)（3）輸出刪除某一字符串后的文章；（4）約瑟夫環(huán)（Joseph）任務(wù)：編號(hào)是1，2，……,n的n個(gè)人按照順時(shí)針?lè)较驀蝗?，每個(gè)人只有一個(gè)密碼（正整數(shù)）。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針?lè)较虻南乱粋€(gè)人開(kāi)始重新從1報(bào)數(shù)，如此下去，直到所有人全部出列為止。要求：利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過(guò)程，按照出列的順序輸出各個(gè)人的編號(hào)。輸出形式：建立一個(gè)輸出函數(shù)，將正確的輸出序列（5）猴子選大王** 任務(wù)：一堆猴子都有編號(hào)，編號(hào)是1，2，3 ...m ,這群猴子（m個(gè)）按照1m的順序圍坐一圈，從第1開(kāi)始數(shù)，每數(shù)到第N個(gè)，該猴子就要離開(kāi)此圈，這樣依次下來(lái)，直到圈中只剩下最后一只猴子，則該猴子為大王。 要求：給出圖的深度優(yōu)先和廣度優(yōu)先遍歷算法，并給出遍歷過(guò)程的動(dòng)態(tài)演示效果三、 上交相關(guān)內(nèi)容要求上交的成果的內(nèi)容必須由以下四個(gè)部分組成，缺一不可1． 上交源程序：學(xué)生按照課程設(shè)計(jì)的具體要求所開(kāi)發(fā)的所有源程序（應(yīng)該放到一個(gè)文件夾中）；2． 上交程序的說(shuō)明文件：（）在說(shuō)明文檔中應(yīng)該寫明上交程序所在的目錄，上交程序的主程序文件名，如果需要安裝，要有程序的安裝使用說(shuō)明；3． 課程設(shè)計(jì)報(bào)告：（保存在word 文檔中，文件名要求 按照姓名學(xué)號(hào)課程設(shè)計(jì)報(bào)告起名，如文件名為張三001課程設(shè)計(jì)報(bào)告.doc ）按照課程設(shè)計(jì)的具體要求建立的功能模塊，每個(gè)模塊要求按照如下幾個(gè)內(nèi)容認(rèn)真完成；其中包括:l 需求分析：在該部分中敘述，每個(gè)模塊的功能要求l 概要設(shè)計(jì)：在此說(shuō)明每個(gè)部分的算法設(shè)計(jì)說(shuō)明（可以是描述算法的流程圖），每個(gè)程序中使用的存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)說(shuō)明（如果指定存儲(chǔ)結(jié)構(gòu)請(qǐng)寫出該存儲(chǔ)結(jié)構(gòu)的定義。要結(jié)構(gòu)清晰，重點(diǎn)函數(shù)的重點(diǎn)變量，重點(diǎn)功能部分要加上清晰的程序注釋。4. 課設(shè)總結(jié)： （保存在word 文檔中）總結(jié)可以包括 : 課程設(shè)計(jì) 過(guò)程的收獲、遇到問(wèn)題、遇到問(wèn)題解決問(wèn)題過(guò)程的思考、程序調(diào)試能力的思考、對(duì)數(shù)據(jù)結(jié)構(gòu)這門課程的思考、在課程設(shè)計(jì)過(guò)程中對(duì)《數(shù)據(jù)結(jié)構(gòu)》課程的認(rèn)識(shí)等內(nèi)容《數(shù)據(jù)結(jié)構(gòu)與算法分析》――課程內(nèi)容體系主要內(nèi)容教學(xué)單元模塊具體教學(xué)內(nèi)容緒論緒論部分是全書的預(yù)備知識(shí)，主要對(duì)ADL語(yǔ)言、數(shù)據(jù)結(jié)構(gòu)與算法、算法分析基礎(chǔ)、OOP、和C++做了簡(jiǎn)單介紹基本數(shù)據(jù)結(jié)構(gòu)基本數(shù)據(jù)結(jié)構(gòu)部分包括線性表、堆棧與隊(duì)列、數(shù)組、字符串、整數(shù)集合類、樹(shù)（包括AVL樹(shù)、伸展樹(shù)等）、圖（包括網(wǎng)絡(luò)流等問(wèn)題的討論）、散列（Hash）等典型算法典型算法部分主要介紹了若干典型算法的實(shí)現(xiàn)，并給出必要的復(fù)雜性分析和比較過(guò)程，具體包括遞歸、排序、查找和內(nèi)存管理等復(fù)雜數(shù)據(jù)結(jié)構(gòu)復(fù)雜數(shù)據(jù)結(jié)構(gòu)部分主要包括優(yōu)先級(jí)隊(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à)類、殘缺棋盤和圖象壓縮等問(wèn)題的討論，在課時(shí)允許的情況下還會(huì)介紹攤還分析、紅黑樹(shù)等《數(shù)據(jù)結(jié)構(gòu)與算法分析》課程實(shí)踐內(nèi)容體系主要內(nèi)容實(shí)踐教學(xué)單元模塊實(shí)踐教學(xué)基本要求實(shí)踐教學(xué)具體內(nèi)容趣味程序設(shè)計(jì)實(shí)踐、二周布置若干趣味程序設(shè)計(jì)題目，如奇數(shù)階幻陣算法、萬(wàn)年歷算法、迷宮算法等。，用貪心法求解一般的著色問(wèn)題。（所謂有序是指鏈接點(diǎn)按數(shù)據(jù)域值大小鏈接，本題不妨設(shè)按數(shù)據(jù)域值從小到大排列），list1和list2分別為指向兩個(gè)鏈表的指針。棧與隊(duì)列應(yīng)用實(shí)驗(yàn)1. 設(shè)計(jì)實(shí)現(xiàn)一個(gè)求解n階Hanoi塔問(wèn)題的算法提示：將n個(gè)圓盤由A依次移到C，B作為輔助塔座。否則，將塔座A頂上的n1個(gè)圓盤移動(dòng)到塔座B上，用塔座C作為輔助塔座；然后移第n個(gè)圓盤；最后將塔座B上的n1個(gè)圓盤移到塔座C上，并用塔座A作為輔助塔座。3. 在計(jì)算機(jī)上模擬實(shí)現(xiàn)農(nóng)夫過(guò)河問(wèn)題的解。1. 根據(jù)課堂介紹設(shè)計(jì)實(shí)現(xiàn)KMP算法2. 試設(shè)計(jì)一個(gè)簡(jiǎn)單的文本編輯器，使之具有對(duì)字符串的輸入、輸出、插入、刪除、查找和替換等功能3. 設(shè)計(jì)實(shí)現(xiàn)一個(gè)通用的判定回文個(gè)數(shù)問(wèn)題的算法程序 稀疏矩陣和廣義表實(shí)驗(yàn)1．熟悉稀疏矩陣和廣義表結(jié)構(gòu)2．掌握稀疏矩陣和廣義表結(jié)構(gòu)上的各種操作3．學(xué)會(huì)運(yùn)用稀疏矩陣和廣義表結(jié)構(gòu)求解問(wèn)題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)式相加的算法程序 樹(shù)結(jié)構(gòu)實(shí)驗(yàn)1. 設(shè)計(jì)一個(gè)程序，根據(jù)二叉樹(shù)的先根序列和對(duì)稱序序列創(chuàng)建一棵用左右指針表示的二叉樹(shù)2. 根據(jù)哈夫曼算法創(chuàng)建哈夫曼樹(shù)，并求樹(shù)中每個(gè)外部結(jié)點(diǎn)的編碼3. 設(shè)計(jì)一個(gè)程序，把中綴表達(dá)式轉(zhuǎn)換成一棵二叉樹(shù)，然后通過(guò)后序遍歷計(jì)算表達(dá)式的值4. 設(shè)計(jì)實(shí)現(xiàn)一個(gè)完成對(duì)BST樹(shù)進(jìn)行插入、刪除、查找操作的算法，并希望有部分同學(xué)能進(jìn)一步把該算法改寫為針對(duì)AVL樹(shù)的相關(guān)算法圖結(jié)構(gòu)實(shí)驗(yàn)采用兩種不同的圖的表示方法，實(shí)現(xiàn)拓?fù)渑判蚝完P(guān)鍵路徑的求解過(guò)程。輸出整個(gè)工程的最短完成時(shí)間是多少? 哪些活動(dòng)是關(guān)鍵活動(dòng)? 說(shuō)明哪項(xiàng)活動(dòng)提高速度后能導(dǎo)致整個(gè)工程提前完成?分析不同存儲(chǔ)結(jié)構(gòu)對(duì)于算法效率的影響。（用拉鏈法解決碰撞時(shí)負(fù)載因子取2，用開(kāi)地址法時(shí)取1/2）航班信息查詢與檢索實(shí)驗(yàn)設(shè)計(jì)對(duì)于直接插入排序、直接選擇排序、起泡排序、Shell排序、快速排序和堆排序等六種算法進(jìn)行上機(jī)實(shí)習(xí)。2. 算法中增加比較次數(shù)和移動(dòng)次數(shù)的統(tǒng)計(jì)功能。4. 設(shè)計(jì)實(shí)現(xiàn)一個(gè)航班信息查詢與檢索系統(tǒng)課程實(shí)驗(yàn)參考教材：l 魏開(kāi)平等編著. 數(shù)據(jù)結(jié)構(gòu)輔導(dǎo)與實(shí)驗(yàn). 清華大學(xué)出版社，2006年第1版l 瞿有甜，《數(shù)據(jù)結(jié)構(gòu)與算法分析》實(shí)驗(yàn)指導(dǎo)書， 實(shí)驗(yàn)1 猴子選大王任務(wù)：一堆猴子都有編號(hào)，編號(hào)是1，2，3 ...m ,這群猴子（m個(gè)）按照1m的順序圍坐一圈，從第1開(kāi)始數(shù)，每數(shù)到第N個(gè)，該猴子就要離開(kāi)此圈，這樣依次下來(lái)，直到圈中只剩下最后一只猴子，則該猴子為大王。實(shí)驗(yàn)內(nèi)容：源程序：include include typedef struct node{ int data。}ListNode。/*建立單循環(huán)鏈表函數(shù)*/LinkList InitRing(int n,LinkList R){ ListNode *p,*q。 R=q=(ListNode *)malloc(sizeof(ListNode))。in。 qdata=i。q=p。 pnext=R。 return R。 ListNode *p,*q。 for(i=1。i++) { for(j=1。j++) p=pnext。 pnext=qnext。 if(i%10==0)printf(\n)。 } R=p。}/*輸出函數(shù)*/void OutRing(int n,LinkList R){ int i。 p=R。i=n/2。 if(i%10==0) printf(\n)。 printf(猴大王的號(hào)碼：\n)。 }/*主函數(shù)*/void main(){ LinkList R。 LinkList InitRing(int n,LinkList R )。 scanf(%d,amp。 printf(報(bào)到要被淘汰數(shù)字 K:)。k)。 R=InitRing(n,R)。 printf(