1、數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)任務(wù)書一、設(shè)計(jì)的目的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)是在學(xué)完數(shù)據(jù)結(jié)構(gòu)課程之后的實(shí)踐教學(xué)環(huán)節(jié)。該 實(shí)踐教學(xué)是軟件設(shè)計(jì)的綜合訓(xùn)練， 包括問(wèn)題分析，總體結(jié)構(gòu)設(shè)計(jì)，用戶界 面設(shè)計(jì)，程序設(shè)計(jì)基本技能和技巧。要求學(xué)生在設(shè)計(jì)中逐步提高程序設(shè)計(jì) 能力，培養(yǎng)科學(xué)的軟件工作方法。學(xué)生通過(guò)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)在下述各方 面得到鍛煉：1、能根據(jù)實(shí)際問(wèn)題的具體情況，結(jié)合數(shù)據(jù)結(jié)構(gòu)課程中的基本理論和基 本算法，正確分析出數(shù)據(jù)的邏輯結(jié)構(gòu)，合理地選擇相應(yīng)的存儲(chǔ)結(jié)構(gòu)，并能設(shè)計(jì)出解決問(wèn)題的有效算法。2、提高程序設(shè)計(jì)和調(diào)試能力.學(xué)生通過(guò)上機(jī)實(shí)習(xí)，驗(yàn)證自己設(shè)計(jì)的算 法的正確性。學(xué)會(huì)有效利用基本調(diào)試方法，迅速找出程序代碼中的錯(cuò)誤并 且

2、修改。3、培養(yǎng)算法分析能力。分析所設(shè)計(jì)算法的時(shí)間復(fù)雜度和空間復(fù)雜度， 進(jìn)一步提高程序設(shè)計(jì)水平。二、設(shè)計(jì)的要求、注意事項(xiàng)和進(jìn)程1、要求：每人選作附錄中的一個(gè)題目（特別說(shuō)明：如不想選作指定題目的 可以向老師提出，學(xué)生自行選擇，但是在難度和工作量上必須足 夠題目選擇自行分配，分組后由班長(zhǎng)統(tǒng)一填表發(fā)給教師，不 再變動(dòng)，使用C或C+實(shí)現(xiàn)，不允許使用其他代碼，每個(gè)題目必須給出清晰的數(shù)據(jù)結(jié)構(gòu)，給出詳細(xì)的對(duì)應(yīng)的基本操作 代碼，應(yīng)該有較好的輸入輸出界面，教師只提出基本功能和要求，學(xué)生 應(yīng)該對(duì)其進(jìn)行完善和豐富。學(xué)生必須設(shè)計(jì)出易于理解的輸入輸出 界面，學(xué)生應(yīng)該準(zhǔn)備多組測(cè)試數(shù)據(jù)（不能僅僅只有一組），而且測(cè)試數(shù)據(jù)允許隨

3、時(shí)變動(dòng)。每個(gè)學(xué)生都需要上交一份課程設(shè)計(jì)報(bào)告，該報(bào)告的格式參照模板，使用紙張A4 ,統(tǒng)一為左側(cè)裝訂。源程序和報(bào)告的電子版，由班級(jí)統(tǒng)一刻制光盤，光盤中每個(gè)學(xué)生 一個(gè)文件夾，文件夾命名規(guī)則如下，學(xué)生學(xué)號(hào) 學(xué)生姓名 所選課 程設(shè)計(jì)題目名稱，該文件夾內(nèi)包括兩項(xiàng)內(nèi)容，一個(gè)是該學(xué)生的課 程設(shè)計(jì)報(bào)告電子版，報(bào)告的電子版使用 word文檔，另一個(gè)是該 學(xué)生的課程設(shè)計(jì)源代碼，源代碼不壓縮存入一個(gè)文件夾內(nèi)。 光盤 刻制完畢后，光盤上用記號(hào)筆書寫，班級(jí)名稱，人數(shù)，對(duì)應(yīng)課程 名稱。2、注意事項(xiàng)：1）充分理解題目，給定主要算法及其應(yīng)用組合；2）各種文檔資料要在程序開發(fā)過(guò)程中逐漸形成；3）采用統(tǒng)一課程設(shè)計(jì)報(bào)告模板；4）每位

4、同學(xué)報(bào)告及代碼內(nèi)容不允許重復(fù)、雷同。3、進(jìn)程：1）查閱資料、邏輯設(shè)計(jì)（3月5日3月18日）2）程序設(shè)計(jì)及調(diào)試（3月19日3月25日）3）撰寫報(bào)告及答辯（3月26日一3月30日）三、報(bào)告內(nèi)容及要求實(shí)習(xí)報(bào)告包括以下七個(gè)內(nèi)容：.需求分析描述要求編程解決的問(wèn)題。以無(wú)歧義的陳述說(shuō)明程序 設(shè)計(jì)的任務(wù)，強(qiáng)調(diào)的是程序要做什么？明確規(guī)定：（a）輸入的形式和輸入值的范圍；（b）輸出的形式；（c）程序所能達(dá)到的功能；（d）測(cè)試數(shù)據(jù)：包括正確的輸入及其輸出結(jié)果和含有錯(cuò)誤的輸入及其 輸出結(jié)果。.概要設(shè)計(jì) 給出程序要達(dá)到的具體的要求。描述解決相應(yīng)問(wèn)題算 法的設(shè)計(jì)思想。描述所設(shè)計(jì)程序的各個(gè)模塊（即函數(shù)）功能。說(shuō)明本程序 中

5、用到的所有抽象數(shù)據(jù)類型的定義、主程序的流程以及各程序模塊之間的 層次（調(diào)用）關(guān)系。.詳細(xì)設(shè)計(jì) 實(shí)現(xiàn)概要設(shè)計(jì)中定義的所有數(shù)據(jù)類型，對(duì)每個(gè)操作只 需要寫出流程或偽碼算法；對(duì)主程序和其他模塊也都需要寫出流程或偽碼 算法（偽碼算法達(dá)到的詳細(xì)程度建議為：按照偽碼算法可以在計(jì)算機(jī)鍵盤 直接輸入高級(jí)程序設(shè)計(jì)語(yǔ)言程序）；畫出函數(shù)的調(diào)用關(guān)系圖。給出所使用的基本抽象數(shù)據(jù)類型，所定義的具體問(wèn)題的數(shù)據(jù)類型，以及新定義的抽象數(shù) 據(jù)類型。設(shè)計(jì)出良好的輸入輸出界面（清晰易懂）。4,調(diào)試分析內(nèi)容包括：（a）調(diào)試過(guò)程中遇到的問(wèn)題是如何解決的以及對(duì)設(shè)計(jì)與實(shí)現(xiàn)的回顧討 論和分所；（b）算法的時(shí)空分析（包括基本操作和其他算法的時(shí)間復(fù)

6、雜度和空間復(fù) 雜度的分析）和改進(jìn)設(shè)想；（c）經(jīng)驗(yàn)和體會(huì)等。.用戶使用說(shuō)明 說(shuō)明如何使用你編寫的程序，詳細(xì)列出每一步的 操作步驟。.測(cè)試結(jié)果 設(shè)計(jì)測(cè)試數(shù)據(jù)，或具體給出測(cè)試數(shù)據(jù)。要求測(cè)試數(shù)據(jù) 能全面地測(cè)試所設(shè)計(jì)程序的功能。列出你的測(cè)試結(jié)果，包括輸入和輸出。 這里的測(cè)試數(shù)據(jù)應(yīng)該完整和嚴(yán)格，最好多于需求分析中所列。.測(cè)試情況：給出程序的測(cè)試情況，并分析運(yùn)行結(jié)果附錄（非必須，按照需要添加）帶注釋的源程序?？梢灾涣谐龀绦蛭募那鍐巍Ｋ?、成績(jī)?cè)u(píng)定考核采用五級(jí)評(píng)分制（優(yōu)秀、良好、中等、及格、不及格）。主要依 據(jù)是選擇題目的難易程度、解決問(wèn)題的思路和方法、程序運(yùn)行情況、程序 的結(jié)構(gòu)合理與否、算法說(shuō)明的清晰程度

7、、報(bào)告的規(guī)范程度、總結(jié)的深刻程 度以及選做情況和獨(dú)立完成情況。附錄：可選題目飛機(jī)訂票系統(tǒng)（限1人完成）任務(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)。修改航班信息：當(dāng)航班信息

8、改變可以修改航班數(shù)據(jù)文件要求：根據(jù)以上功能說(shuō)明，設(shè)計(jì)航班信息，訂票信息的存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì) 程序完成功能；宿舍管理查詢軟件（限1人完成）任務(wù)：為宿舍管理人員編寫一個(gè)宿舍管理查詢軟件，程序設(shè)計(jì) 要求：采用交互工作方式建立數(shù)據(jù)文件，數(shù)據(jù)文件按關(guān)鍵字（姓名、學(xué)號(hào)、房號(hào)）進(jìn)行排序（冒泡、選擇、插入排序等任選一種）查詢菜單：（用二分查找實(shí)現(xiàn)以下操作）按姓名查詢按學(xué)號(hào)查詢按房號(hào)查詢3.校園導(dǎo)航問(wèn)題(限1人完成)設(shè)計(jì)要求：設(shè)計(jì)你的學(xué)校的平面圖，至少包括 10個(gè)以上的場(chǎng)所，每 兩個(gè)場(chǎng)所間可以有不同的路，且路長(zhǎng)也可能不同，找出從任意場(chǎng)所到達(dá)另 一場(chǎng)所的最佳路徑(最短路徑).圖書借閱管理系統(tǒng)(限1人完成)主要分為兩大

9、功能：圖書管理(增加圖書、查詢圖書、刪除圖書、圖書借閱、還書);會(huì)員管理(增加會(huì)員、查詢會(huì)員、刪除會(huì)員、借書信息)；學(xué)生成績(jī)管理(限1人完成)實(shí)現(xiàn)功能：輸入、輸出、插入、刪除、查找、追加、讀入、顯示、 保存、拷貝、排序、索引、分類合計(jì)、退出?；钇趦?chǔ)蓄帳目管理(限1人完成)活期儲(chǔ)蓄處理中，儲(chǔ)戶開戶、銷戶、存入、支出活動(dòng)頻繁，系統(tǒng) 設(shè)計(jì)要求：能比較迅速地找到儲(chǔ)戶的帳戶，以實(shí)現(xiàn)存款、取款記賬；能比較簡(jiǎn)單，迅速地實(shí)現(xiàn)插入和刪除，以實(shí)現(xiàn)開戶和銷戶的需要。通訊錄的制作(限1人完成)設(shè)計(jì)目的：用數(shù)據(jù)結(jié)構(gòu)中的雙向鏈表作數(shù)據(jù)結(jié)構(gòu)，編寫一個(gè) 通訊錄管理系統(tǒng)。以把所學(xué)數(shù)據(jù)結(jié)構(gòu)知識(shí)應(yīng)用到實(shí)際軟件開發(fā)中去。設(shè)計(jì)內(nèi)容：本

10、系統(tǒng)應(yīng)完成一下幾方面的功能：輸入信息enter();顯示信息 display();查找以姓名作為關(guān)鍵字search();刪除信息delete();在盤save ();裝入load();設(shè)計(jì)要求：每條信息至包含：姓名(NAME )街道(STREET)城市(CITY)郵編(EIP)國(guó)家(STATE)幾項(xiàng)作為一個(gè)完整的系統(tǒng)，應(yīng)具有友好的界面和較強(qiáng)的容錯(cuò)能力哈夫曼編碼/譯碼器(限1人完成)【問(wèn)題描述】設(shè)計(jì)一個(gè)利用哈夫曼算法的編碼和譯碼系統(tǒng)， 重復(fù)地顯 示并處理以下項(xiàng)目，直到選擇退出為止?！净疽蟆繉?quán)值數(shù)據(jù)存放在數(shù)據(jù)文件(文件名為data.txt ,位于執(zhí)行程序的當(dāng)前目錄中)初始化：鍵盤輸入字符集大

11、小 n、n個(gè)字符和n個(gè)權(quán)值，建立 哈夫曼樹；編碼：利用建好的哈夫曼樹生成哈夫曼編碼；輸出編碼；設(shè)字符集及頻度如下表：字符空格 A B C D E F G H I J K L M頻度 186 64 13 22 32 103 21 15 47 57 1 5 32 20字符 NOPQ RST UVWXYZ頻度 57 63 15 1 48 51 80 23 8 18 1 16 1電話號(hào)碼查找系統(tǒng)(限1人完成)【問(wèn)題描述】利用散列表的設(shè)計(jì)與實(shí)現(xiàn)電話號(hào)碼查找系統(tǒng)。【基本要求】設(shè)每個(gè)記錄有下列數(shù)據(jù)項(xiàng)：電話號(hào)碼、用戶名、地址；從鍵盤輸入各記錄，分別以電話號(hào)碼和用戶名為關(guān)鍵字建立散列表；采用一定的方法解決沖突；

12、查找并顯示給定電話號(hào)碼的記錄；查找并顯示給定用戶名的記錄。學(xué)生成績(jī)管理系統(tǒng)(限1人完成)現(xiàn)有學(xué)生成績(jī)信息文件1 (1.txt),內(nèi)容如下姓名學(xué)號(hào)語(yǔ)文數(shù)學(xué)英語(yǔ)張明明01677882李成友02789188張輝燦03688256王露04564577除爾明05673847.學(xué)生成2.費(fèi)信息.文件2 (2.tx：t),內(nèi)容如下姓名學(xué)號(hào)語(yǔ)文數(shù)學(xué)英語(yǔ)陳果31576882李華明32889068張明東33484256李明國(guó)34504587除追鳧35475877試編寫一管理系統(tǒng)，要求如下：實(shí)現(xiàn)對(duì)兩個(gè)文件數(shù)據(jù)進(jìn)行合并，生成新文件3.txt抽取出三科成績(jī)中有補(bǔ)考的學(xué)生并保存在一個(gè)新文件4.txt對(duì)合并后的文件3.tx

13、t中的數(shù)據(jù)按總分降序排序(至少采用兩種排序方法實(shí)現(xiàn))輸入一個(gè)學(xué)生姓名后，能查找到此學(xué)生的信息并輸出結(jié)果(至少采用兩種查找方法實(shí)現(xiàn))要求使用結(jié)構(gòu)體，鏈或數(shù)組等實(shí)現(xiàn)上述要求.圖的遍歷和生成樹求解實(shí)現(xiàn)(限 1人完成)要求：先任意創(chuàng)建一個(gè)圖；圖的DFS,BFS的遞歸和非遞歸算法的實(shí)現(xiàn)最小生成樹(兩個(gè)算法)的實(shí)現(xiàn)，求連通分量的實(shí)現(xiàn)要求用鄰接矩陣、鄰接表結(jié)構(gòu)存儲(chǔ)實(shí)現(xiàn)排序綜合（限1人完成）利用隨機(jī)函數(shù)產(chǎn)生N個(gè)隨機(jī)整數(shù)（20000以上），對(duì)這些數(shù)進(jìn)行 多種方法進(jìn)行排序。要求：至少采用五種方法實(shí)現(xiàn)上述問(wèn)題求解 （提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排 序）0并把排序

14、后的結(jié)果保存在不同的文件中。統(tǒng)計(jì)每一種排序方法的性能（以上機(jī)運(yùn)行程序所花費(fèi)的時(shí)間為準(zhǔn)進(jìn)行對(duì)比），找出其中兩種較快的方法。josephs 環(huán) （限1人完成）任務(wù)：編號(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ì)一個(gè) 程序來(lái)求出出列順序。要求：利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過(guò)程， 按照出列的順序輸出 各個(gè)人的編號(hào)。測(cè)試數(shù)據(jù)：m的初值為20,

15、n=7 ,7個(gè)人的密碼依次為3, 1, 7, 2, 4, 7, 4,首先m=6,則正確的輸出是什么？要求：輸入數(shù)據(jù)：建立輸入處理輸入數(shù)據(jù)，輸入 m的初值，n ,輸 入每個(gè)人的密碼，建立單循環(huán)鏈表。輸出形式：建立一個(gè)輸出函數(shù)，將正確的輸出序列HUFFMAN 樹及編碼（限1人完成）隨機(jī)輸入一篇英文文章（或讀一個(gè) TXT文件），生成并顯示HUFFMAN樹，輸出每個(gè)字母的 HUFFMAN編碼，判斷ASCII編碼與HUFFMAN編碼對(duì)本篇報(bào)文長(zhǎng)度節(jié)省效果。拓?fù)渑判颍ㄏ?人完成）問(wèn)題描述建立圖的存儲(chǔ)結(jié)構(gòu)，能夠輸入圖的頂點(diǎn)和邊的信息，并 存儲(chǔ)到相應(yīng)存儲(chǔ)結(jié)構(gòu)中，再編寫函數(shù)實(shí)現(xiàn)圖的拓?fù)渑判??；疽筮x擇鄰接表作

16、為有向圖的存儲(chǔ)結(jié)構(gòu)模擬整個(gè)過(guò)程，并輸 出拓卜排序的頂點(diǎn)序列。測(cè)試數(shù)據(jù)利用下圖中的數(shù)據(jù)調(diào)試程序簡(jiǎn)單的職工管理系統(tǒng)(限1人完成).問(wèn)題描述對(duì)單位的職工進(jìn)行管理，包括插入、刪除、查找、排序等功能。.要求職工對(duì)象包括姓名、性別、出生年月、工作年月、學(xué)歷、職務(wù)、 住址、電話等信息。(1)新增一名職工：將新增職工對(duì)象按姓名以字典方式職工管理文 件中。(2)刪除一名職工：從職工管理文件中刪除一名職工對(duì)象。(3)查詢：從職工管理文件中查詢符合某些條件的職工。(4)修改：檢索某個(gè)職工對(duì)象，對(duì)其某些屬性進(jìn)行修改。(5)排序：按某種需要對(duì)職工對(duì)象文件進(jìn)行排序。3.實(shí)現(xiàn)提示職工對(duì)象數(shù)不必很多，便于一次讀入內(nèi)存，所有操

17、作不經(jīng)過(guò)內(nèi)外 存交換。(1)由鍵盤輸入職工對(duì)象，以文件方式保存。程序執(zhí)行時(shí)先將文件 讀入內(nèi)存。(2)對(duì)職工對(duì)象中的姓名按字典順序進(jìn)行排序。(3)對(duì)排序后的職工對(duì)象進(jìn)行增、刪、查詢、修改等操作。.哈希表設(shè)計(jì)(限1人完成)問(wèn)題描述:針對(duì)自己的班集體中的 人名”設(shè)計(jì)一個(gè)哈希表，使得平 均查找長(zhǎng)度不超過(guò)R,完成相應(yīng)的建表和查表程序?；疽?假設(shè)人名為中國(guó)姓名的漢語(yǔ)拼音形式。待填入哈希表的 人名共有30個(gè)，取平均查找長(zhǎng)度的上限為2。哈希函數(shù)用除留余數(shù)法構(gòu) 照，用鏈表法處理沖突。測(cè)試數(shù)據(jù):讀取熟悉的30個(gè)人的姓名。.學(xué)生信息管理(限1人完成)要求每條學(xué)生信息至包含學(xué)號(hào)(xh)、姓名(xm)、性別(xb)

18、、年齡(nl)、 專業(yè)(zy)等，完成如下功能：(1)輸入學(xué)生基本信息記錄enter()(2)增加一名學(xué)生記錄(可和功能1合并)一一insert()(3)刪除指定(按姓名)學(xué)生的信息 一一delete()(4)修改指定(按姓名)學(xué)生的信息)一一modify()(5)查詢符合條件的學(xué)生(按專業(yè))一一search()(6)顯示學(xué)生管理庫(kù)中的信息 一一display。.計(jì)算一元稀疏多項(xiàng)式(限1人完成)要求完成如下功能：輸入并建立多項(xiàng)式creatpolyn()輸出多項(xiàng)式，輸出形式為整數(shù)序列，序列按指數(shù)升序排列一一 printpolyn()多項(xiàng)式a和b相加，建立多項(xiàng)式a+b,輸出相加的多項(xiàng)式一一 add

19、polyn()多項(xiàng)式a和b相減，建立多項(xiàng)式a-b,輸出相減的多項(xiàng)式一一 subpolyn()用帶表頭結(jié)點(diǎn)的單鏈表存儲(chǔ)多項(xiàng)式。測(cè)試數(shù)據(jù)：(2x+5x8-3.1x11)+(7-5x8+11x9)(6-3x+4.4x2-1.2x9)-(-6-3x+5.4x2+7.8x15)(x+x2+x3)+0(4 ) (x+x3)-(-x-x-3).通訊錄的制作(限1人完成)要求每條信息至包含姓名(name )城市(dty)電話(tel) QQ號(hào) (qq),完成如下功能：輸入信息enter();顯示信息-display();查找以姓名作為關(guān)鍵字 一一search();刪除信息delete();(5)存盤(將數(shù)據(jù)保

20、存在文件中，此功能選做)save ();.運(yùn)動(dòng)會(huì)分?jǐn)?shù)統(tǒng)計(jì)(1人完成)任務(wù)：參加運(yùn)動(dòng)會(huì)有n個(gè)學(xué)校，學(xué)校編號(hào)為1n。比賽分成 m個(gè)男子項(xiàng)目，和w個(gè)女子項(xiàng)目。項(xiàng)目編號(hào)為男子1m ,女子m+1m+w o不同的項(xiàng)目取前五名或前三名積分；取前五名的積分分 別為：7、5、3、2、1,前三名的積分分別為：5、3、2;哪些取前五名 或前三名由學(xué)生自己設(shè)定。(m=20,n=20 )功能要求：可以輸入各個(gè)項(xiàng)目的前三名或前五名的成績(jī)；能統(tǒng)計(jì)各學(xué)?？偡?，可以按學(xué)校編號(hào)或名稱、學(xué)?？偡帧⒛信畧F(tuán)體總分排序輸出；可以按學(xué)校編號(hào)查詢學(xué)校某個(gè)項(xiàng)目的情況； 可以按項(xiàng)目編號(hào)查詢?nèi)〉们叭蚯拔迕膶W(xué)校。數(shù)據(jù)存入文件并能隨時(shí)查詢規(guī)定：輸

21、入數(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語(yǔ)言程序設(shè)計(jì)的書上，請(qǐng)自學(xué)解決)請(qǐng)?jiān)谧詈蟮纳辖毁Y料中指明你 用到的存儲(chǔ)結(jié)構(gòu)；測(cè)試數(shù)據(jù)：要求使用1、全部合法數(shù)據(jù)；2、整體非法數(shù)據(jù)；3、局部 非法數(shù)據(jù)。進(jìn)行程序測(cè)試，以保證程序的穩(wěn)定。測(cè)試數(shù)據(jù)及測(cè)試結(jié)果請(qǐng)?jiān)?上交的資料中寫明；.最小生成樹問(wèn)題（限1人完成）問(wèn)題描述： 在n個(gè)城市之間建設(shè)網(wǎng)絡(luò)，只需

22、保證連通即可，求最經(jīng) 濟(jì)的架設(shè)方法。對(duì)于圖，其生成樹中的邊也帶權(quán)，將生成樹各邊的權(quán)值總和稱為生成樹的權(quán)，并將權(quán)值最小的生成樹稱為最小生成樹，簡(jiǎn)稱為 MST。有兩種非常典型的算法：Prim算法和kruskal算法。任務(wù)要求：設(shè)計(jì)程序完成如下功能：對(duì)給定的網(wǎng)和起點(diǎn)，用PRIM算 法和kruskal算法的基本思想求解出所有的最小生成樹。存儲(chǔ)結(jié)構(gòu)可自行 選擇。測(cè)試數(shù)據(jù)：自行設(shè)定，注意邊界等特殊情況。要求：如何用多種數(shù)據(jù)結(jié)構(gòu)來(lái)求解問(wèn)題。同時(shí)要求實(shí)現(xiàn)對(duì)應(yīng)數(shù)據(jù)結(jié)構(gòu) 的所有基本操作。.敢死隊(duì)問(wèn)題（限1人完成）有M個(gè)敢死隊(duì)員要炸掉敵人的一碉堡，誰(shuí)都不想去，排長(zhǎng)決定用輪 回?cái)?shù)數(shù)的辦法來(lái)決定哪個(gè)戰(zhàn)士去執(zhí)行任務(wù)。如果

23、前一個(gè)戰(zhàn)士沒完成任務(wù)， 則要再派一個(gè)戰(zhàn)士上去?，F(xiàn)給每個(gè)戰(zhàn)士編一個(gè)號(hào)，大家圍坐成一圈，隨便 從某一個(gè)戰(zhàn)士開始計(jì)數(shù)，當(dāng)數(shù)到 5時(shí)，對(duì)應(yīng)的戰(zhàn)士就去執(zhí)行任務(wù)，且此 戰(zhàn)士不再參加下一輪計(jì)數(shù)。如果此戰(zhàn)士沒完成任務(wù)，再?gòu)南乱粋€(gè)戰(zhàn)士開始 數(shù)數(shù)，被數(shù)到第5時(shí)，此戰(zhàn)士接著去執(zhí)行任務(wù)。以此類推，直到任務(wù)完 成為止。排長(zhǎng)是不愿意去的，假設(shè)排長(zhǎng)為1號(hào)，請(qǐng)你設(shè)計(jì)一程序，求出從第 幾號(hào)戰(zhàn)士開始計(jì)數(shù)才能讓排長(zhǎng)最后一個(gè)留下來(lái)而不去執(zhí)行任務(wù)。要求：至少采用兩種不同的數(shù)據(jù)結(jié)構(gòu)的方法實(shí)現(xiàn)。.最短路徑實(shí)現(xiàn)圖的輸入，選擇合適的結(jié)構(gòu)表示圖，在此基礎(chǔ)上實(shí)現(xiàn)求解最短路 徑的算法，可以從任意一點(diǎn)求最短路徑，學(xué)生必須準(zhǔn)備多組測(cè)試數(shù)據(jù)，并 設(shè)計(jì)清晰

24、易懂的輸入輸出界面，要求：如何用多種數(shù)據(jù)結(jié)構(gòu)來(lái)求解問(wèn)題。同時(shí)要求實(shí)現(xiàn)對(duì)應(yīng)數(shù)據(jù)結(jié)構(gòu) 的所有基本操作。.圖的基本操作與實(shí)現(xiàn)(限1人完成)(1)自選存儲(chǔ)結(jié)構(gòu)，輸入含n個(gè)頂點(diǎn)(用字符表示頂點(diǎn))和e條邊的圖G;(2)求每個(gè)頂點(diǎn)的度，輸出結(jié)果；(3)指定任意頂點(diǎn)x為初始頂點(diǎn)，對(duì)圖G作DFS遍歷，輸出DFS頂點(diǎn)序列 (提示:使用一個(gè)棧實(shí)現(xiàn)DFS);(4)指定任意頂點(diǎn)x為初始頂點(diǎn)，對(duì)圖G作BFS遍歷，輸出BFS頂點(diǎn)序列(提 示:使用一個(gè)隊(duì)列實(shí)現(xiàn)BFS);(5)輸入頂點(diǎn)x,查找圖G:若存在含x的頂點(diǎn)，則刪除該結(jié)點(diǎn)及與之相關(guān)連的邊，并作DFS遍歷(執(zhí)行操作3);否則輸出信息“無(wú)x”；(6)判斷圖G是否是連通圖，輸

25、出信息“ YES” / “NO” ；.長(zhǎng)的整數(shù)加法問(wèn)題描述：設(shè)計(jì)一個(gè)程序?qū)崿F(xiàn)兩個(gè)任意長(zhǎng)的整數(shù)的求和運(yùn)算?；疽螅豪秒p向循環(huán)鏈表，設(shè)計(jì)一個(gè)實(shí)現(xiàn)任意長(zhǎng)的整數(shù)進(jìn)行加法運(yùn)算的演示程序。要求輸入和輸出每四位一組，組間用逗號(hào)隔開。如： 1,0000, 0000, 0000, 0000。.學(xué)生搭配問(wèn)題。一班有m個(gè)女生，有n個(gè)男生(m不等于n),現(xiàn)要開一個(gè)舞會(huì)。男女 生分別編號(hào)坐在舞池的兩邊的椅子上。 每曲開始時(shí)，依次從男生和女生中 各出一人配對(duì)跳舞，本曲沒成功配對(duì)者坐著等待下一曲找舞伴。請(qǐng)?jiān)O(shè)計(jì)一系統(tǒng)模擬動(dòng)態(tài)地顯示出上述過(guò)程，要求如下：(1)輸出每曲配對(duì)情況；(2)計(jì)算出任何一個(gè)男生(編號(hào)為X)和任意女生

26、(編號(hào)為Y),在 第K曲配對(duì)跳舞的情況.至少求出K的兩個(gè)值；(3)盡量設(shè)計(jì)出多種算法及程序。要求：如何用多種數(shù)據(jù)結(jié)構(gòu)來(lái)求解問(wèn)題。同時(shí)要求實(shí)現(xiàn)對(duì)應(yīng)數(shù)據(jù)結(jié)構(gòu) 的所有基本操作。.車廂調(diào)度問(wèn)題描述：假設(shè)停在鐵路調(diào)度站入口處白車廂序列的編號(hào)一次為 1, 2, 3, n。設(shè)計(jì)一個(gè)程序，求出所有可能由此輸出的長(zhǎng)度為n的車廂序列。 29串的查找和替換問(wèn)題描述：打開一篇英文文章，在該文章中找出所有給定的單詞， 然后 對(duì)所有給定的單詞替換為另外一個(gè)單詞，再存盤。.構(gòu)造可以使n個(gè)城市連接的最小生成樹問(wèn)題描述：給定一個(gè)地區(qū)的n個(gè)城市間的距離網(wǎng)，用Prim算法或Kruskal 算法建立最小生成樹，并計(jì)算得到的最小生成樹

27、的代價(jià)?；疽螅?、城市間的距離網(wǎng)采用鄰接矩陣表示，鄰接矩陣的存儲(chǔ)結(jié)構(gòu)定義采用 課本中給出的定義，若兩個(gè)城市之間不存在道路，則將相應(yīng)邊的權(quán)值設(shè)為 自己定義的無(wú)窮大值。要求在屏幕上顯示得到的最小生成樹中包括了哪些 城市間的道路，并顯示得到的最小生成樹的代價(jià)。2、表示城市間距離網(wǎng)的鄰接矩陣（要求至少 6個(gè)城市，10條邊）3、最小生成樹中包括的邊及其權(quán)值，并顯示得到的最小生成樹的代價(jià)。.設(shè)計(jì)哈希表實(shí)現(xiàn)電話號(hào)碼查詢系統(tǒng)。基本要求：1、設(shè)每個(gè)記錄有下列數(shù)據(jù)項(xiàng)：電話號(hào)碼、用戶名、地址；2、從鍵盤輸入各記錄，分別以電話號(hào)碼和用戶名為關(guān)鍵字建立哈希表；3、采用再哈希法解決沖突；4、查找并顯示給定電話號(hào)碼的記

28、錄；5、查找并顯示給定用戶名的記錄。6、在哈希函數(shù)確定的前提下，嘗試各種不同類型處理沖突的方法（至 少兩種），考察平均查找長(zhǎng)度的變化。.括號(hào)匹配問(wèn)題從預(yù)先存儲(chǔ)的文件中讀出多個(gè)表達(dá)式， 每一個(gè)表達(dá)式有英文字母(小 寫)、運(yùn)算符和左右大()()中小三種括號(hào)構(gòu)成，請(qǐng)編寫一個(gè)程序檢查每個(gè) 表達(dá)式中的左右括號(hào)是否匹配，若匹配，則返回“YES”；否則返回“NO”， 同時(shí)顯示出括號(hào)不匹配的大致位置。 表達(dá)式長(zhǎng)度小于500,括號(hào)不少于20 個(gè)。要求：如何用多種數(shù)據(jù)結(jié)構(gòu)來(lái)求解問(wèn)題。同時(shí)要求實(shí)現(xiàn)對(duì)應(yīng)數(shù)據(jù)結(jié)構(gòu) 的所有基本操作。.迷宮問(wèn)題求解迷宮問(wèn)題，迷宮大小，不小于10乘以10,迷宮的存儲(chǔ)方式應(yīng)該 容易修改，迷宮只

29、有一個(gè)入口，可以有一個(gè)或多個(gè)出口，按上下左右四方 向行走，或八方向行走，求解可以同行的路徑，要求：如何用多種數(shù)據(jù)結(jié)構(gòu)來(lái)求解問(wèn)題。同時(shí)要求實(shí)現(xiàn)對(duì)應(yīng)數(shù)據(jù)結(jié)構(gòu) 的所有基本操作。.模擬售票大廳考慮去銀行辦業(yè)務(wù)：一般來(lái)說(shuō)，服務(wù)窗口越多，隊(duì)走的越快，銀行經(jīng) 理希望顧客滿意，但又不希望雇傭過(guò)多的員工。我們模擬的服務(wù)窗口有如下假設(shè)：a.只排一隊(duì)，并且先到的人先得到服務(wù)b.平均每隔15秒就會(huì)來(lái)一位顧客c.如果有空閑的窗口，在顧客抵達(dá)之時(shí)就會(huì)馬上處理d.從顧客來(lái)到窗口到處理完顧客請(qǐng)求，這個(gè)平均需要 120秒以下就來(lái)模擬高峰期銀行開多少個(gè)窗口最為合適：(利用平均等待時(shí)問(wèn))給出詳細(xì)的結(jié)果對(duì)比分析，最好有中間的過(guò)程演示

30、，要求：如何用多種數(shù)據(jù)結(jié)構(gòu)來(lái)求解問(wèn)題。同時(shí)要求實(shí)現(xiàn)對(duì)應(yīng)數(shù)據(jù)結(jié)構(gòu) 的所有基本操作。.文件的壓縮和恢復(fù)功能,從文本文件中讀入原始數(shù)據(jù)，該原始數(shù)據(jù)只包含英文字母，對(duì)原始數(shù) 據(jù)進(jìn)行分析后，想辦法對(duì)其進(jìn)行壓縮，壓縮后，保存到新的文件之內(nèi)，并 提供壓縮前后的占用空間之比。要求：(a)原始文件和新產(chǎn)生的文件，利用文本文件來(lái)模仿二進(jìn)制文件。(b)運(yùn)行時(shí)的壓縮原文件的規(guī)模應(yīng)不小于 1K。(c)提供恢復(fù)文件與原文件的相同性對(duì)比功能。(d)提供詳細(xì)的對(duì)比界面，并且有詳細(xì)的中間過(guò)程演示，要求：如何用多種數(shù)據(jù)結(jié)構(gòu)來(lái)求解問(wèn)題。同時(shí)要求實(shí)現(xiàn)對(duì)應(yīng)數(shù)據(jù)結(jié)構(gòu) 的所有基本操作。.集合運(yùn)算常用集合運(yùn)算符號(hào)名稱：和集&符號(hào)解釋：兩個(gè)或

31、兩個(gè)以上的集合的所有元素組成一個(gè)新的集合 稱為和集使用示例：雙目運(yùn)算符(1,2,3)&(1,3,4)=1 2 3 1 3 4符號(hào)名稱：并集+符號(hào)解釋：兩個(gè)或兩個(gè)以上集合并在一起并去除其中重復(fù)元素的 集合，稱為并集使用示例：雙目運(yùn)算符(1,2,3,5,9)+(1,3,4)=1 2 3 5 9 4符號(hào)名稱：差集-符號(hào)解釋：第一個(gè)集合減去第二個(gè)集合所包含的元素，稱為差集使用示例：.雙目運(yùn)算符(1,2,3,5,9)-(1,3,4)=2 5 9.單目運(yùn)算符(去除數(shù)集中重復(fù)的元素)(1,2,3,1,4,2,5)-=1 2 3 4 5符號(hào)名稱：交集*符號(hào)解釋：兩個(gè)集合中都含有的元素使用示例：(1,2,3)*

32、(1,3,4)=1 3符號(hào)名稱：補(bǔ)集/符號(hào)解釋：兩個(gè)集中非共同元素組成的集合(也叫反交集)使用示例：(1,2,3)/(1,3,4)=2 4符號(hào)名稱：逆集符號(hào)解釋：第二個(gè)集合減去第一個(gè)集合所包含的元素，稱為逆集(也叫反差集)使用示例：(1,2,3)(1,3,4)=4符號(hào)名稱：平集!符號(hào)解釋：兩個(gè)集合的和集中，只出現(xiàn)一次的元素組成的集合稱 為平集使用示例：(1,2,3,2,5,6,2,1,4,3,2)!(4,5,9,2,3,5,1,7)=6 9 7要求：允許三個(gè)集合，同時(shí)參與計(jì)算，如何用多種數(shù)據(jù)結(jié)構(gòu)來(lái)求解問(wèn) 題。同時(shí)要求實(shí)現(xiàn)對(duì)應(yīng)數(shù)據(jù)結(jié)構(gòu)的所有基本操作。.特殊矩陣運(yùn)算對(duì)特殊矩陣能夠保存到文件之內(nèi)，而

33、且可以從文件讀取，在界面上， 以人們熟悉的方式顯示，可以對(duì)特殊矩陣進(jìn)行加法運(yùn)算和減法運(yùn)算， 矩陣 轉(zhuǎn)置，要求：如何用多種數(shù)據(jù)結(jié)構(gòu)來(lái)求解問(wèn)題。同時(shí)要求實(shí)現(xiàn)對(duì)應(yīng)數(shù)據(jù)結(jié)構(gòu) 的所有基本操作。.模擬計(jì)算器的程序(仿照win7計(jì)算器)要求能對(duì)包含加、減、乘、除、括號(hào)運(yùn)算符及 n次方和ABS函數(shù)等 函數(shù)的任意整型表達(dá)式進(jìn)行求解。要求：要檢查有關(guān)運(yùn)算的條件，并對(duì)錯(cuò)誤的條件產(chǎn)生報(bào)警。要求：如何用多種數(shù)據(jù)結(jié)構(gòu)來(lái)求解問(wèn)題。同時(shí)要求實(shí)現(xiàn)對(duì)應(yīng)數(shù)據(jù)結(jié)構(gòu) 的所有基本操作。.查找算法比較問(wèn)題描述：設(shè)計(jì)一個(gè)實(shí)現(xiàn)順序查找、二分查找(折半查找)、二叉排序樹、平衡 二叉樹、哈希查找算法的程序，并具有人機(jī)交互界面?；疽螅?1)設(shè)計(jì)

34、一個(gè)菜單將實(shí)現(xiàn)的查找算法的名字顯示出來(lái)，并提示用戶對(duì)查找算法進(jìn)行選擇；(2)分別實(shí)現(xiàn)順序查找、二分查找(折半查找)、二叉排序樹、哈希 查找；(3)哈希函數(shù)采用除留余數(shù)發(fā)，解決沖突的方法大家任選擇一種；(4)二叉排序樹必須實(shí)現(xiàn)構(gòu)建、查找、插入、刪除四個(gè)基本操作；(5)輸出各種排序的結(jié)果并進(jìn)行比較。要求：如何用多種數(shù)據(jù)結(jié)構(gòu)來(lái)求解問(wèn)題。同時(shí)要求實(shí)現(xiàn)對(duì)應(yīng)數(shù)據(jù)結(jié)構(gòu) 的所有基本操作。.文章編輯功能：輸入一頁(yè)文字，程序可以統(tǒng)計(jì)出文字、數(shù)字、空格的個(gè)數(shù)。 靜 態(tài)存儲(chǔ)一頁(yè)文章，每行最多不超過(guò) 80個(gè)字符，共N行；要求(1)分別統(tǒng)計(jì)出其中英文字母數(shù)和空格數(shù)及整篇文章總字?jǐn)?shù)；(2)統(tǒng)計(jì)某一字符串在文章中出現(xiàn)的次數(shù)，

35、并輸出該次數(shù)；(3)刪除某一子用，并將后面的字符前移。(4)查找，替換(等長(zhǎng)，不等長(zhǎng))，插入(插用，文本塊的插入)、 塊移動(dòng)(行塊，列塊移動(dòng))，刪除；(5)可正確存盤、取盤；(6)正確顯示總行數(shù)。存儲(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)輸出刪除某一 字符串后的文章；要求：如何用多種數(shù)據(jù)結(jié)構(gòu)來(lái)求解問(wèn)題。同時(shí)要求實(shí)現(xiàn)對(duì)應(yīng)數(shù)據(jù)結(jié)構(gòu) 的所有基本操作。.藥店的藥品銷售統(tǒng)計(jì)系統(tǒng)(排序應(yīng)用)【問(wèn)題描述】 設(shè)計(jì)一系

36、統(tǒng)，實(shí)現(xiàn)醫(yī)藥公司定期對(duì)銷售各藥品的記錄 進(jìn)行統(tǒng)計(jì)，可按藥品的編號(hào)、單價(jià)、銷售量或銷售額做出排名。【實(shí)現(xiàn)提示】在本設(shè)計(jì)中，首先從數(shù)據(jù)文件中讀出各藥品的信息記錄，存儲(chǔ)在 順序表中。各藥品的信息包括：藥品編號(hào)、藥名、藥品單價(jià)、銷出數(shù)量、 銷售額。藥品編號(hào)共4位，采用字母和數(shù)4字混合編號(hào)，如：A125,前一位為大寫字母，后三位為數(shù)字， 按藥品編號(hào)進(jìn)行排序時(shí)，可采用基數(shù)排序法。對(duì)各藥品的單價(jià)、銷售量或 銷售額進(jìn)行排序時(shí)，可采用多種排序方法，如直接插入排序、冒泡排序、 快速排序，直接選擇排序等方法。在本設(shè)計(jì)中，對(duì)單價(jià)的排序采用冒泡排 序法，對(duì)銷售量的排序采用快速排序法，對(duì)銷售額的排序采用堆排序法。.停車場(chǎng)管理問(wèn)題描述設(shè)停車場(chǎng)內(nèi)只有一個(gè)可停放n輛汽車的狹長(zhǎng)通道，且只 有一個(gè)大門可供汽車進(jìn)出。汽車在停車場(chǎng)內(nèi)按車輛到達(dá)時(shí)間的先后順序， 依次由北向南排列(大門在最南端