62《數(shù)據結構》課程設計任務書

1、1006402 數(shù)據結構課程設計任務書一、設計目的1. 了解并掌握數(shù)據結構與算法的設計方法，具備初步的獨立分析和設計能力；2. 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設計、程序編碼測試等基本方法和技能。3. 提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力。4. 訓練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作者所應具備的 科學的工作方法和作風。數(shù)據結構是一門實踐性較強的軟件基礎課程，為了學好這門 課程，必須在掌握理論知識的同時，加強上機實踐。本課程設計的目的就是要達到理論與 實際應用相結合，使同學們能夠根據數(shù)據對象的特性，學會數(shù)據組織的方法，能把現(xiàn)實世 界中的實際問題在計算

2、機內部表示出來，并培養(yǎng)基本的、良好的程序設計技能。二、設計地點 湖南城市學院實驗樓計算機房 407三、設計時間2018年6月 4日6月8日四、設計分組 （54 人 五、指導教師： 陳強 莫照六、設計課題：1表達式翻譯要求：編寫完整程序 ,將不包含括號的算術中綴表達式翻譯成后綴表達式.輸入 :中綴表達式,80個字符以內 .輸出:轉換后的后綴表達式 .要求:界面友好 ,函數(shù)功能要劃分好 2超市選址問題 設計要求：對于某一學校超市，其他各單位到其的距離不同，同時各單位人員去超市的頻 度也不同。請為超市選址，要求實現(xiàn)總體最優(yōu)。3串的查找和替換輸入或打開一篇英文文章，在該文章中找出所有給定的單詞，然后對

3、所 有給定的單詞替換為另外一個單詞。4地圖著色問題 設計要求：已知中國地圖，對各省進行著色，要求相鄰省所使用的顏色不同，并保證使用 的顏色總數(shù)最少。5二叉排序樹的實現(xiàn) 用順序和二叉鏈表作存儲結構1以回車（n為輸入結束標志，輸入數(shù)列L,生成一棵二叉排序樹T;2對二叉排序樹 T 作中序遍歷，輸出結果；3輸入元素x,查找二叉排序樹 T,若存在含x的結點，則刪除該結點，并作中序遍歷（執(zhí)行操作 2；否則輸出信息 “無 x”；6二叉樹的遍歷問題 二叉樹的中序、前序、后序的遞歸、非遞歸遍歷算法，層次序的非遞歸遍歷算法的實現(xiàn)， 應包含建樹的實現(xiàn)。要求：遍歷的內容應是千姿百態(tài)的。7飛機售票系統(tǒng) 任務：通過此系統(tǒng)

4、可以實現(xiàn)如下功能： 錄入：1 / 12 可以錄入航班情況 數(shù)據可以存儲在一個數(shù)據文件中，數(shù)據結構、具體數(shù)據自定）查詢：可以查詢某個航線的情況 如，輸入航班號，查詢起降時間，起飛抵達城市，航班票價，票 價折扣，確定航班是否滿倉）；可以輸入起飛抵達城市，查詢飛機航班情況；訂票： 訂票情況可以存在一個數(shù)據文件中，結構自己設定）可以訂票，如果該航班已經無票，可以提供相關可選擇航班；退票：可退票，退票后修改相關數(shù)據文件；客戶資料有姓名，證件號，訂票數(shù)量及航班情況，訂單要有編號。修改航班信息：當航班信息改變可以修改航班數(shù)據文件要求：根據以上功能說明，設計航班信息，訂票信息的存儲結構，設計程序完成功能；&敢

5、死隊問題有M個敢死隊員要炸掉敵人的一碉堡，誰都不想去，排長決定用輪回數(shù)數(shù)的辦法來決定哪 個戰(zhàn)士去執(zhí)行任務。如果前一個戰(zhàn)士沒完成任務，則要再派一個戰(zhàn)士上去?，F(xiàn)給每個戰(zhàn)士 編一個號，大家圍坐成一圈，隨便從某一個戰(zhàn)士開始計數(shù)，當數(shù)到5時，對應的戰(zhàn)士就去執(zhí)行任務，且此戰(zhàn)士不再參加下一輪計數(shù)。如果此戰(zhàn)士沒完成任務，再從下一個戰(zhàn)士開始 數(shù)數(shù)，被數(shù)到第5時，此戰(zhàn)士接著去執(zhí)行任務。以此類推，直到任務完成為止。排長是不愿意去的，假設排長為1號，請你設計一程序，求出從第幾號戰(zhàn)士開始計數(shù)才能讓排長最后一個留下來而不去執(zhí)行任務。要求：至少采用兩種不同的數(shù)據結構的方法實現(xiàn)。如果采用三種以上的方法者，可加分。9 哈夫曼編

6、碼轉碼器利用哈夫曼編碼進行信息通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成 本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據預先編碼，在接收端將傳來的數(shù) 據進行譯碼 復原）。對于雙工信道 即可以雙向傳輸信息的信道），每端都需要一個完整 的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個哈夫曼編/譯碼系統(tǒng)?；疽笠粋€完整的系統(tǒng)應具有以下功能：1） I:初始化1 nitialization ）。從終端讀入字符集大小n,以及n個字符和n個權值，建立哈夫曼樹，并將它存于文件hfmTree中。2） E：編碼Encoding ）。利用已建好的哈夫曼樹 如不在內存，則從文件htmTree中讀入），對

7、文件ToBeTran中的正文進行編碼，然后將結果存入文件CodeFile中。宇符ACDEFGHIJ氏L頻度186641322M210321154767153320N0FQPSTUVWXYZ頻度57631514861eo2281811513） D：譯碼Decoding ）。利用已建好的哈夫曼樹將文件CodeFile中的代碼進行譯碼，結果存入文件TextFile中。4） P:印代碼文件Print ）。將文件 CodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼寫入文件CodePrint中。5） T：印哈夫曼樹TreePrinting ）。將已在內存中的哈夫曼樹以直觀的方式

8、樹或凹入表2 / 12TreePrint 中。形式）顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件 測試數(shù)據 1）數(shù)據一：已知某系統(tǒng)在通信聯(lián)絡中只可能出現(xiàn)8 種字符，其概率分別為0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11, 以此設計哈夫曼編碼。利用此數(shù)據對程序進行調試。 2）用下表給出的字符集和頻度的實際統(tǒng)計數(shù)據建立哈夫曼樹，并實現(xiàn)以下報文的編碼和 譯碼： “THIS PROGRAM IS MY FAVORITE” 。 實現(xiàn)提示 1）文件 CodeFile 的基類型可以設為子界型 bit=0.1 。2）用戶界面可以設計為菜單”方式：顯示上述功能符號，再加上

9、“Q表示運行Quit。請用戶鍵入一個先把功能符，些功能執(zhí)行完畢后再經菜單，直至某次用戶先把了“ E為止。能比較迅速地找到儲戶的帳戶，以實現(xiàn)存款、取款記賬； 2能比較簡單，迅速地實現(xiàn)插入和刪除，以實現(xiàn)開戶和銷戶的需要。12簡單的職工管理系統(tǒng)1. 問題描述對單位的職工進行管理，包括插入、刪除、查找、排序等功能。2. 要求職工對象包括姓名、性別、出生年月、工作年月、學歷、職務、住址、電話等信息。1）新增一名職工：將新增職工對象按姓名以字典方式職工管理文件中。 2）刪除一名職工：從職工管理文件中刪除一名職工對象。 3）查詢：從職工管理文件中查詢符合某些條件的職工。 4）修改：檢索某個職工對象，對其某些

10、屬性進行修改。5）排序：按某種需要對職工對象文件進行排序。3. 實現(xiàn)提示職工對象數(shù)不必很多，便于一次讀入內存，所有操作不經過內外存交換。1）由鍵盤輸入職工對象，以文件方式保存。程序執(zhí)行時先將文件讀入內存。 2）對職工對象中的 姓名 按字典順序進行排序。具有圖形菜單界面； 2查找，替換 等長，不等長） ，插入 插串，文本塊的插入）、塊移動 可正確存盤、取盤； 4正確顯示總行數(shù)。14教案計劃編制問題 大學的每個專業(yè)都要制定教案計劃。假設任何專業(yè)都有固定的學習年限，每學年含兩學3 / 12 期，每學期的時間長度和學分上限值均相等，每個專業(yè)開設的課程都是確定的，而且課程 在開設時間的安排必須滿足先修關

11、系。每門課程有哪些先修課程是確定的，可以有任意多 門，也可以沒有。每門課恰好占一個學期。試在這樣的前提下設計一個教案計劃編制程 序?；疽蟆W分和直接先修課的課程號。2 ）允許用戶指定下列兩種編排策略之一：一是使學生在各學期中的學習負擔盡量均勻；二是使課程盡可能地集中在前幾個學期中。老鼠形象可辨認，可用鍵盤操縱老鼠上下左右移動； 2迷宮的墻足夠結實，老鼠不能穿墻而過； 3正確檢測結果，若老鼠在規(guī)定時間內走到糧倉處，提示成功，否則提示失敗； 4添加編輯迷宮功能，可修改當前迷宮，修改內容：墻變路、路變墻； 5找出走出迷宮的所有路徑，以及最短路徑。 利用序列化功能實現(xiàn)迷宮地圖文件的存盤和讀出等功能

12、 17利用棧求表達式的值編寫程序實現(xiàn)表達式求值，即驗證某算術表達式的正確性，若正 確，則計算該算術表達式的值。主要功能描述如下：1、從鍵盤上輸入表達式。2、分析該表達式是否合法： 1)是數(shù)字，則判斷該數(shù)字的合法性。若合法，則壓入數(shù)據到堆棧中。 2)是規(guī)定的運算符，則根據規(guī)則進行處理。在處理過程中，將計算該表達式的值。 ：初始化堆棧 intMake_str( ：語法檢查并計算 intpush_operate(intoperate ：將操作碼壓入堆棧 intpush_num(doublenum ：將操作數(shù)壓入堆棧 intprocede(intoperate ：處理操作碼 intchange_opn

13、d(intoperate ：將字符型操作碼轉換成優(yōu)先級 intpush_opnd(intoperate ：將操作碼壓入堆棧 intpop_opnd( ：將操作碼彈出堆棧 intcaculate(intcur_opnd ：簡單計算 +，-，*， / doublepop_num( ：彈出操作數(shù) 18利用棧求表達式的值隨機產生n個題目，題目涉及加減乘除和帶括號的混合運算。要求：有交互菜單；指 定鍵隨時終止練習；將所有的練習題和答案及對錯評價輸出到文件備查；按對錯的比 例，給出“優(yōu)”、“良”、“中”、“還需努力”的評價。19排序綜合利用隨機函數(shù)產生 N 個隨機整數(shù) 至少采用三種方法實現(xiàn)上述問題求解 統(tǒng)

14、計每一種排序方法的性能 如果采用 4種或 4 種以上的方法者，可適當加分。 20任意長的整數(shù)加法設計一個程序實現(xiàn)兩個任意長的整數(shù)的求和運算。要求：利用雙向 循環(huán)鏈表，設計一個實現(xiàn)任意長的整數(shù)進行加法運算的程序，要求輸入和輸出每四位一 組，組間用逗號隔開。如 1,0000,0000,0000,0000 。21散列表的設計與實現(xiàn)5 / 12 設計散列表實現(xiàn)電話號碼查找系統(tǒng)。【基本要求】1設每個記錄有下列數(shù)據項：電話號碼、用戶名、地址； 2從鍵盤輸入各記錄，分別以電話號碼和用戶名為關鍵字建立散列表； 3采用一定的方法解決沖突；4查找并顯示給定電話號碼的記錄； 5查找并顯示給定用戶名的記錄。【進一步完

15、成內容】1系統(tǒng)功能的完善； 2設計不同的散列函數(shù)，比較沖突率； 3在散列函數(shù)確定的前提下，嘗試各種不同類型處理沖突的方法，考察平均查找長度的變 化。22散列法的實驗研究 散列法中，散列函數(shù)構造方法多種多樣，同時對于同一散列函數(shù)解決沖突的方法也可以不 同。兩者是影響查詢算法性能的關鍵因素。對于幾種典型的散列函數(shù)構造方法，做實驗觀 察，不同的解決沖突方法對查詢性能的影響。23樹的應用 實現(xiàn)樹與二叉樹的轉換的實現(xiàn)。以及樹的前序、后序的遞歸、非遞歸算法，層次序的非遞 歸算法的實現(xiàn)，應包含建樹的實現(xiàn)。24樹與二叉樹的轉換的實現(xiàn)樹與二叉樹的轉換的實現(xiàn)，以及樹的前序、后序的遞歸、非 遞歸遍歷算法，層次序的非

16、遞歸遍歷算法的實現(xiàn)，應包含建樹的實現(xiàn)。(多種遍歷可以只實現(xiàn)一個 。25數(shù)制轉換問題任意給定一個 M進制的數(shù)x,請實現(xiàn)如下要求1求出此數(shù)x的10進制值 用MD表示)2實現(xiàn)對x向任意的一個非M進制的數(shù)的轉換。3至少用兩種或兩種以上的方法實現(xiàn)上述要求用棧解決,用數(shù)組解決,其它方法解決)。26順序結構, ,動態(tài)鏈表結構下的一元多項式的加、減、乘法的實現(xiàn) 設有一元多項式 Am(x 和 Bn(x.Am(x=A0+A1x1+A2x2+A3x3+ +AmxmBn (x=B0+B1x1+B2x2+B3x3+ +Bnxn請實現(xiàn)求 M(x=Am(x+Bn(x 、M(x=Am(x-Bn(x 和 M(x=Am(xX B

17、n(x。 要求：1 首先判定多項式是否稀疏 2分別采用順序和動態(tài)存儲結構實現(xiàn)； 3結果 M(x 中無重復階項和無零系數(shù)項； 4要求輸出結果的升冪和降冪兩種排列情況27宿舍管理查詢軟1 任務：為宿舍管理人員編寫一個宿舍管理查詢軟件,程序設計要求：A. 采用交互工作方式B. 建立數(shù)據文件，數(shù)據文件按關鍵字 姓名、學號、房號)進行排序(冒泡、選擇、插入排序等任選一種 6 / 122查詢菜單 :（ 用二分查找實現(xiàn)以下操作 A. 按姓名查詢B.按學號查詢C .按房號查詢3打印任一查詢結果 可以連續(xù)操作） 28宿舍管理查詢軟件 為宿舍管理人員編寫一個宿舍管理查詢軟件，程序要求采用交互工作方式，并建立相應的

18、 數(shù)據文件。要求：實現(xiàn)按關鍵字（姓名、學號、房號 排序的功能，并分別用冒泡、選擇、插入排序實現(xiàn)；實現(xiàn)查找（按姓名、學號、房號 ，采用二分查找算法實現(xiàn)；有交互菜單，用戶不選擇退出時可以連續(xù)操作。29通訊錄的制作模塊要求：第一個模塊一一主函數(shù)ma in （的功能是：根據選單的選項調用各函數(shù)，并完成相應的功 能。第二個模塊 Menu（ 的功能是：顯示英文提示選單。 第三個模塊 Quit（ 的功能是：退出選單。第四個模塊Create（的功能是：創(chuàng)建新的通訊錄。第五個模塊 Add（ 的功能是：在通訊錄的末尾，寫入新的信息，并返回選單。第六個模塊一一Find（的功能是：查詢某人的信息，如果找到了，則顯示該

19、人的信 息，如果未找到，則提示通訊錄中沒有此人的信息，并返回選單。第七個模塊 Alter（ 的功能是：修改某人的信息，如果未找到要修改的人，則提示 通訊錄中沒有此人的信息，并返回選單。第八個模塊一一Delete（的功能是：刪除某人的信息，如果未找到要刪除的人，則提示 通訊錄中沒有此人的信息，并返回選單。第九個模塊 List（ 的功能是：顯示通訊錄中的所有記錄。設計要求：1每條信息至包含：姓名 NAME ）、性別（GENDER、電話TEL ）、城市CITY ）郵編 EIP ）幾項。2作為一個完整的系統(tǒng)，應具有友好的界面和較強的容錯能力 30圖的遍歷和最小生成樹求解實現(xiàn)要求：1先任意創(chuàng)建一個圖；2

20、圖的 DFS,BFS 的遞歸和非遞歸算法的實現(xiàn) 3最小生成樹 兩個算法）的實現(xiàn)，求連通分量的實現(xiàn) 4要求用鄰接矩陣、鄰接表、十字鏈表多種結構存儲實現(xiàn)31 圖書管理系統(tǒng) 設計一個計算機管理系統(tǒng)完成圖書管理基本業(yè)務。【基本要求】 1每種書的登記內容包括書號、書名、著作者、現(xiàn)存量和庫存量； 2對書號建立索引表 線性表）以提高查找效率；3系統(tǒng)主要功能如下：7 / 12*采編入庫：新購一種書，確定書號后，登記到圖書帳目表中，如果表中已有，則只將庫存 量增加；*借閱：如果一種書的現(xiàn)存量大于0，則借出一本，登記借閱者的書證號和歸還期限，改變現(xiàn)存量；*歸還：注銷對借閱者的登記，改變該書的現(xiàn)存量。【進一步完成內

21、容】1系統(tǒng)功能的進一步完善；2索引表采用樹表。3設計內容4程序流程圖5源程序6軟件測試報告 包括所用到的數(shù)據及結果）32. 圖書借閱管理系統(tǒng) 主要分為兩大功能：1圖書管理（增加圖書、查詢圖書、刪除圖書、圖書借閱、還書;2會員管理（增加會員、查詢會員、刪除會員、借書信息 ;33. 文章編輯功能：輸入一頁文字，程序可以統(tǒng)計出文字、數(shù)字、空格的個數(shù)。靜態(tài)存儲一頁文章，每行最多不超過80個字符，共N行；要求1）分別統(tǒng)計出其中英文字母數(shù)和空格數(shù)及整篇文章總字數(shù)；2）統(tǒng)計某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；3）刪除某一子串，并將后面的字符前移。存儲結構使用線性表，分別用幾個子函數(shù)實現(xiàn)相應的功能；輸

22、入數(shù)據的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標點符號。輸出形式：1）分行輸出用戶輸入的各行字符；2 ）分4行輸出全部字母數(shù)、”數(shù)字個數(shù)、空格個數(shù)、”文章總字數(shù)3 ）輸出刪除某一字符串后的文章；34. 稀疏矩陣的實現(xiàn)和應用基本功能要求：稀疏矩陣采用三元組表示，求兩個具有相同行列數(shù)的稀疏矩陣 A和B的相加矩陣C,并輸出C。求出A的轉置矩陣D，輸出D。測試數(shù)據:35. 稀疏矩陣實現(xiàn)與應用要求：實現(xiàn)三元組、十字鏈表下的稀疏矩陣的加、轉、乘的實現(xiàn)。36. 線索二叉樹的應用要求實現(xiàn)線索樹建立、插入、刪除、恢復線索的實現(xiàn)。37校園導航問題設計要求：設計你的學校的平面圖，至少包括10個以上的場

23、所，每兩個場所間可以有不同的路，且路長也可能不同，找出從任意場所到達另一場所的最佳路徑最短路徑）。1、基本要求：1）設計校園平面圖，在校園景點選10個左右景點。以圖中頂點表示校園內各景點，存放8 / 12 景點名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等有關信息。2) 為來訪客人提供圖中任意景點相關信息的查詢。3) 為來訪客人提供任意景點的問路查詢，即查詢任意兩個景點之間的一條最短路徑。 2、實現(xiàn)提示：一般情況下，校園的道路是雙向通行的，可設計校園平面圖是一個無向網。 頂點和邊均含有相關信息。38學生成績管理 實現(xiàn)功能：輸入、輸出、插入、刪除、查找、追加、讀入、顯示、保存、拷貝、排序、

24、索 引、分類合計、退出。39學生搭配問題一班有 m 個女生 ,有 n 個男生 (m 不等于 n, 現(xiàn)要開一個舞會 .男女生分別編號坐在舞池的兩邊 的椅子上 .每曲開始時 ,依次從男生和女生中各出一人配對跳舞,本曲沒成功配對者坐著等待下一曲找舞伴 .請設計一系統(tǒng)模擬動態(tài)地顯示出上述過程,要求如下 :1輸出每曲配對情況2計算出任何一個男生(編號為X和任意女生(編號為Y,在第K曲配對跳舞的情況至少求 出 K 的兩個值 .3盡量設計出多種算法及程序 ,可視情況適當加分提示 :用隊列來解決比較方便40學校超市選址問題 設計要求：對于某一學校超市，其他各單位到其的距離不同，同時各單位人員去超市的頻 度也不同。請為超市選址，要求實現(xiàn)總體最優(yōu)。41一元多項式的四則運算的實現(xiàn) 順序結構、動態(tài)鏈表結構下的一元多項式的加法、減法、乘法的實現(xiàn)。設有一元多項式 Am(x和Bn(x.A