【文章內(nèi)容簡介】 對它們進(jìn)行處理。通過課程設(shè)計可以提高學(xué)生的思維能力，促進(jìn)學(xué)生的綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。通過此次課程設(shè)計主要達(dá)到以下目的：n 了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨(dú)立分析和設(shè)計能力； n 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能； n 提高綜合運(yùn)用所學(xué)的理論知識和方法獨(dú)立分析和解決問題的能力；n 訓(xùn)練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。二、課程設(shè)計的基本要求獨(dú)立思考，獨(dú)立完成：每人任選一題，在課程設(shè)計中各任務(wù)要求獨(dú)立完成，遇到問題大家可以相互討論，互相調(diào)試檢查，但不可以拷貝。按照課程設(shè)計的具體要求建立的功能模塊，每個模塊要求按照如下幾個內(nèi)容認(rèn)真完成；其中包括：a）需求分析：在該部分中敘述，每個模塊的功能要求b）概要設(shè)計在此說明每個部分的算法設(shè)計說明（可以是描述算法的流程圖），每個程序中使用的存儲結(jié)構(gòu)設(shè)計說明（如果指定存儲結(jié)構(gòu)請寫出該存儲結(jié)構(gòu)的定義。c）詳細(xì)設(shè)計各個算法實現(xiàn)的源程序（可放在附錄中），對每個題目要有相應(yīng)的源程序（可以是一組源程序，每個功能模塊采用不同的函數(shù)實現(xiàn)）源程序要按照寫程序的規(guī)則來編寫。要結(jié)構(gòu)清晰，重點函數(shù)的重點變量，重點功能部分要加上清晰的程序注釋。d）調(diào)試分析測試數(shù)據(jù)，測試輸出的結(jié)果，時間復(fù)雜度分析，和每個模塊設(shè)計和調(diào)試時存在問題的思考（問題是哪些？問題如何解決？），算法的改進(jìn)設(shè)想等。每人實現(xiàn)的結(jié)果必須進(jìn)行檢查和演示；程序源代碼和程序的說明文件必須上交，作為考核內(nèi)容的一部分；（上交時每人交一份，文件夾的取名規(guī)則為：“學(xué)號 姓名”，如“11207210188 張麗”。該文件夾下至少包括：“源代碼”和“課程設(shè)計報告”，統(tǒng)一放在服務(wù)器的文件夾“d： / 3數(shù)據(jù)結(jié)構(gòu)課程設(shè)計任務(wù)書/11級專升本數(shù)據(jù)結(jié)構(gòu)課程設(shè)計”中）。課程設(shè)計報告要對重點函數(shù)及結(jié)構(gòu)進(jìn)行說明。報告格式參照（報告示例）。報告提交時間：第16周星期五之前，遲交無成績。形式：課程設(shè)計報告(要求書寫課程設(shè)計報告）和電子文檔。三、課程設(shè)計內(nèi)容：例如：輸入第一個數(shù)為：***172586，輸入第二個數(shù)為：***7則程序運(yùn)行后輸出***172586****7=正確答案。2．矩陣的運(yùn)算采用十字鏈表表示稀疏矩陣，并實現(xiàn)矩陣的加減法和乘法運(yùn)算, 要求：要檢查有關(guān)運(yùn)算的條件，并對錯誤的條件產(chǎn)生報警。3． 訂票系統(tǒng)設(shè)計航班信息，訂票信息的存儲結(jié)構(gòu)，設(shè)計程序完成如下功能：錄入：可以錄入航班情況(數(shù)據(jù)可以存儲在一個數(shù)據(jù)文件中，數(shù)據(jù)結(jié)構(gòu)、具體數(shù)據(jù)自定)查詢：可以查詢某個航線的情況(如，輸入航班號，查詢起降時間，起飛抵達(dá)城市，航班票價，票價折扣，確定航班是否滿倉)；可以輸入起飛抵達(dá)城市，查詢飛機(jī)航班情況；訂票：(訂票情況可以存在一個數(shù)據(jù)文件中，結(jié)構(gòu)自己設(shè)定)可以訂票，如果該航班已經(jīng)無票，可以提供相關(guān)可選擇航班；退票： 可退票，退票后修改相關(guān)數(shù)據(jù)文件；客戶資料有姓名，證件號，訂票數(shù)量及航班情況，訂單要有編號。修改航班信息：當(dāng)航班信息改變可以修改航班數(shù)據(jù)文件 6． 賓館訂房和退房系統(tǒng)假設(shè)一個賓館有n個標(biāo)準(zhǔn)的客房，每個標(biāo)準(zhǔn)客房有m個標(biāo)準(zhǔn)間，利用鏈表、?；蛘哧犃械葦?shù)據(jù)結(jié)構(gòu)設(shè)計出具有訂房和退房等功能的管理系統(tǒng)。7． 建立二叉樹和線索二叉樹分別用以下方法建立二叉樹： 1）用先序遍歷的輸入序列 2）用層次遍歷的輸入序列 3）用先序和中序遍歷的結(jié)果最后對所建立的二叉樹進(jìn)行中序線索化，并對此線索樹進(jìn)行中序遍歷(不使用棧)。8．校園導(dǎo)航問題設(shè)計要求：設(shè)計你的學(xué)校的平面圖，至少包括10個以上的場所，每兩個場所間可以有不同的路，且路長也可能不同，找出從任意場所到達(dá)另一場所的最佳路徑（最短路徑）。9．馬的遍歷問題設(shè)計程序完成如下要求：在中國象棋棋盤上，對任一位置上放置的一個馬，均能選擇一個合適的路線，使得該棋子能按象棋的規(guī)則不重復(fù)地走過棋盤上的每一位置。要求：依次輸出所走過的各位置的坐標(biāo)。/ 3數(shù)據(jù)結(jié)構(gòu)課程設(shè)計任務(wù)書要求對包含加、減、乘、除、括號運(yùn)算符的任意整型表達(dá)式進(jìn)行求解，操作數(shù)可以是多位數(shù)。設(shè)計程序完成如下要求：在88的國際象樣棋盤上，放置8個皇后，使得這8個棋子不能互相被對方吃掉。要求：依次輸出各種成功的放置方法。設(shè)計程序完成如下功能：對給定的圖結(jié)構(gòu)和起點，產(chǎn)生深度優(yōu)先遍歷和廣度優(yōu)先遍歷序列，并給出求解過程的動態(tài)演示。14．構(gòu)造n個城市連接的最小生成樹一個地區(qū)的n個城市間的距離網(wǎng)，用prim算法或kruskal算法建立最小生成樹，并計算得到的最小生成樹的代價?；疽螅?)城市間的距離網(wǎng)采用鄰接矩陣表示，鄰接矩陣的存儲結(jié)構(gòu)定義采用課本中給出的定義，若兩個城市之間不存在道路，則將相應(yīng)邊的權(quán)值設(shè)為自己定義的無窮大值。要求在屏幕上顯示得到的最小生成樹中包括了哪些城市間的道路，并顯示得到的最小生成樹的代價。2)表示城市間距離網(wǎng)的鄰接矩陣(要求至少6個城市，10條邊)15． 藥店的藥品銷售統(tǒng)計系統(tǒng)設(shè)計一系統(tǒng)，實現(xiàn)醫(yī)藥公司定期對銷售各藥品的記錄進(jìn)行統(tǒng)計，可按藥品的編號、單價、銷售量或銷售額做出排名。基本要求：在本設(shè)計中，首先從數(shù)據(jù)文件中讀出各藥品的信息記錄，存儲在順序表中。各藥品的信息包括：藥品編號、藥名、藥品單價、銷出數(shù)量、銷售額。對各藥品的藥名、單價、銷售量或銷售額進(jìn)行排序時，可采用多種排序方法，如直接插入排序、冒泡排序、快速排序，直接選擇排序、堆排等方法。四、上交作業(yè)及成績評定上交要求上交設(shè)計報告和源程序。其中設(shè)計報告要以手寫報告的形式上交；電子版內(nèi)容包括程序源碼和設(shè)計報告的電子文檔。整個班級的設(shè)計均放在一個文件夾中。課程設(shè)計報告注意事項：1）運(yùn)行結(jié)果請截圖（alt + prtsc）；2)系統(tǒng)功能模塊介紹請請采用流程圖形式； 3）課程設(shè)計總結(jié)可以從以下幾個方面書寫 : 課程設(shè)計的收獲、遇到問題及其解決過程、程序調(diào)試技巧、在課程設(shè)計過程中對《數(shù)據(jù)結(jié)構(gòu)》課程的認(rèn)識等內(nèi)容。評分標(biāo)準(zhǔn)根據(jù)完成任務(wù)的情況、課程設(shè)計報告書的質(zhì)量和課程設(shè)計過程中的工作態(tài)度等按照30%、50%、20%加權(quán)綜合打分。成績評定實行百分制。上機(jī)程序檢查未通過者、無設(shè)計報告者以及嚴(yán)重抄襲他人設(shè)計者，成績?yōu)椴患案瘛? 3數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計摘要篇五2014/2015學(xué)年第一學(xué)期《數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計》任務(wù)書一、課程設(shè)計目的數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計是《數(shù)據(jù)結(jié)構(gòu)與算法》課程教學(xué)必不可缺的一個重要環(huán)節(jié)，它可加深學(xué)生對該課程所學(xué)內(nèi)容的進(jìn)一步的理解與鞏固，是將計算機(jī)課程與實際問題相聯(lián)接的關(guān)鍵步驟。通過課程設(shè)計，能夠提高學(xué)生分析問題、解決問題，從而運(yùn)用所學(xué)知識解決實際問題的能力，因而必須給予足夠的重視。2二、課程設(shè)計題目 棋盤覆蓋【間題描述】在一個2k2k 個方格組成的棋盤中，恰有一個方格與其它方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中，要用圖示的4種不同形態(tài)的l型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個l型骨牌不得重疊覆蓋?！净疽蟆浚?）輸入k以及特殊方格所在的行號dr和特殊方格的列號dc。1（2）要求輸出每一步用什么形態(tài)l型骨牌覆蓋，覆蓋后得到的棋盤圖形。（3）如果輸出的結(jié)果只是用矩陣表示則為良好，用圖形表示則為優(yōu)?！緶y試數(shù)據(jù)】 【實現(xiàn)提示】使用分治策略，把棋盤劃分成4個小棋盤，然后用一個l型骨牌覆蓋將這4個小棋盤變?yōu)槎季哂刑厥夥礁竦钠灞P。 hanoi塔問題（*）【問題描述】設(shè)a，b，c是三個塔座。開始時，在塔座a上有一疊共n個圓盤，這些圓盤自下而上，由大到小地疊放在一起，各圓盤從小到大編號為1,2,?,n，要求將塔座a上的這一疊圓盤移到塔座b上，并仍按同樣順序疊置。在移動圓盤時應(yīng)遵守以下移動規(guī)則：規(guī)則（1）每次只能移動一個圓盤；規(guī)則（2）任何時刻都部允許將較大的圓盤壓在較小的圓盤之上；規(guī)則（3）在滿足移動規(guī)則（1）和（2）的前提下，可將圓盤移至a，b，c中任一塔座上?！净疽蟆浚?）設(shè)計出hannoi塔游戲，供用戶玩；（2）提供正確的搬運(yùn)方法?！緦崿F(xiàn)說明】正確的搬運(yùn)方法使用遞歸方法實現(xiàn)?！緶y試數(shù)據(jù)】 矩陣連乘問題【問題描述】給定n個矩陣{a1,a2,...,an},其中ai和ai+1是可乘的，i＝1,2,?,n1。考察這n個矩陣的連乘積a1a2,...,an，通過加括號方式，找出矩陣乘積所需的最少計算量的方法?！净疽蟆枯斎朊總€矩陣的行和列，要求輸出最少計算量的矩陣乘積方法，如(a1(a2(a3a4)))?！緦崿F(xiàn)說明】 使用動態(tài)規(guī)劃方法。 多邊形游戲（*）【問題描述】多邊形游戲是一個單人玩的游戲，開始時有一個由n個頂點構(gòu)成的多邊形。每個頂點被賦予一個整數(shù)值，每條邊被賦予一個運(yùn)算符“＋”或“*”。所有邊依次用整數(shù)從1到n編號。游戲第1步，將一條邊刪除。隨后n1步按以下方式操作：選擇一條邊e及由e連接著的2個頂點v1和v2；用一個新的頂點取代邊e及用e連接著的2個頂點v1和v2，將由頂點v1和v2的整數(shù)值通過邊e上的運(yùn)算得到的結(jié)果賦予新頂點。最后，所有邊都被刪除，游戲結(jié)束。游戲的得分就是所剩頂點上的整數(shù)值。【基本要求】設(shè)計該游戲供用戶玩；對于給定的多邊形，給出最高得分計算。【實現(xiàn)說明】 使用動態(tài)規(guī)劃方法。 01背包問題【問題描述】給定n種物品和一背包。物品i的重量是wi，其價值為vi，背包的容量為c。問應(yīng)如何選擇裝入背包種的物品，使得裝入背包種物品的總價值最大?！净疽蟆渴褂脛討B(tài)規(guī)劃、回溯法以及分支界限三種方法實現(xiàn)?！緶y試數(shù)據(jù)】 【實現(xiàn)提示】 排序方法【問