數(shù)據(jù)結(jié)構(gòu)課程設(shè)計要求

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計指導(dǎo)書 一、 課程設(shè)計的性質(zhì)、任務(wù)和目的課程設(shè)計是學(xué)生對課程所學(xué)知識的綜合運用，它與課堂聽講、上機實驗、課外練習(xí)、自學(xué)研究相輔相成，構(gòu)成一個完整的課程教學(xué)體系。數(shù)據(jù)結(jié)構(gòu)是一門實踐性強的課程，其中對算法設(shè)計和程序編寫的掌握尤為重要。學(xué)生雖然可以通過與課堂教學(xué)同步的上機實驗完成相關(guān)內(nèi)容的練習(xí)，但卻往往局限于一些功能簡單、彼此之間關(guān)系獨立的算法和程序。課程設(shè)計是一種綜合訓(xùn)練，致力于培養(yǎng)學(xué)生全面、靈活的算法設(shè)計思想和較高的編程能力，要求學(xué)生編寫的程序結(jié)構(gòu)清楚和正確易讀，符合軟件工程的規(guī)范，能夠為今后從事計算機開發(fā)與應(yīng)用打下基礎(chǔ)。需要學(xué)生具有豐富科學(xué)知識、獨立解決實際問題、有創(chuàng)造能力，這

2、也是該課程設(shè)計的最終目的。二、課程設(shè)計的方式與基本要求方式：整個課程設(shè)計要求分為四個階段來完成。第一階段為準(zhǔn)備階段，此階段要求將學(xué)生自主進(jìn)行問題分析和相關(guān)資料查詢，并對課程設(shè)計內(nèi)容作初步設(shè)計；第二階段為編程及程序調(diào)試階段，此階段會安排一定數(shù)量的集中上機時間；第三階段為程序測試及檢查階段，此階段由指導(dǎo)老師對每位學(xué)生的設(shè)計結(jié)果作測試和檢查，并根據(jù)測試及檢查結(jié)果評定學(xué)生成績，此成績占課程設(shè)計總成績的70%；第四階段為學(xué)生編寫課程設(shè)計實驗報告階段，每位學(xué)生按照課程設(shè)計實驗報告的內(nèi)容和要求編寫詳細(xì)的課程設(shè)計實驗報告并打印上交給指導(dǎo)老師，由指導(dǎo)老師根據(jù)每位學(xué)生的完成情況評定成績，此成績占課程設(shè)計總成績的3

3、0%。三、課程設(shè)計的基本要求數(shù)據(jù)結(jié)構(gòu)課程設(shè)計要求學(xué)生在規(guī)定的時間內(nèi)（三周內(nèi)）完成所選題目，并根據(jù)所選問題分析設(shè)計思路、選擇數(shù)據(jù)結(jié)構(gòu)描述、確立算法過程、用一種計算機語言（用C語言）編寫出詳細(xì)的實現(xiàn)程序，然后通過上機反復(fù)調(diào)試與修改，直到獲得滿意的結(jié)果為止。對于要解決的同一問題，由于所采用的數(shù)據(jù)結(jié)構(gòu)可能不同、所選擇的算法可能不同、編寫的程序也不盡相同，但只要結(jié)果正確且有效（具有較好的時間復(fù)雜度和空間復(fù)雜度）即可，即不要求編寫的算法和程序完全一致，但力求編寫的算法和程序更優(yōu)秀、綜合指標(biāo)更好。通過本課程的課程設(shè)計，應(yīng)使學(xué)生達(dá)到以下的基本要求 : 1. 能根據(jù)加工數(shù)據(jù)對象的特征，選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)、存儲結(jié)

4、構(gòu)及相應(yīng)算法，基本掌握各種算法在時間和空間的分析技巧。 2. 能夠進(jìn)行算法設(shè)計和程序設(shè)計，并且使所設(shè)計的程序結(jié)構(gòu)清楚，正確易讀，并上機調(diào)試通過。 3初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能；4. 訓(xùn)練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。5. 設(shè)計的題目要求達(dá)到一定工作量，并具有一定的深度和難度。6. 較強的實習(xí)、實踐能力；較強的分析問題、解決問題的能力。設(shè)計要求： 1. 有明確的設(shè)計思路； 2. 有完整的界面； 3. 能夠完整實現(xiàn)算法； 4. 有圖形輔助說明； 5. 有適當(dāng)?shù)膸椭δ埽?6

5、. 設(shè)計完成后寫出設(shè)計報告，對整個設(shè)計過程做出總結(jié)。 課程設(shè)計報告要求 : 1. 每一項設(shè)計要求都要用函數(shù)實現(xiàn)，； 2. 有程序流程圖； 3. 有程序清單； 5. 課程設(shè)計中遇到的難點及解決方法； 6. 收獲總結(jié)。 7. 做好設(shè)計期間的記錄。 四、課程設(shè)計的主要任務(wù) 1. 問題分析和任務(wù)定義 根據(jù)設(shè)計題目的要求，充分地分析和理解問題，明確問題要求做什么？（而不是怎么做？）限制條件是什么？2. 邏輯設(shè)計 對問題描述中涉及的操作對象定義相應(yīng)的數(shù)據(jù)類型，并按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊，定義主程序模塊和各抽象數(shù)據(jù)類型。邏輯設(shè)計的結(jié)果應(yīng)寫出每個抽象數(shù)據(jù)類型的定義(包括數(shù)據(jù)結(jié)構(gòu)的描述和每個基本操作的

6、功能說明)，各個主要模塊的算法，并給出模塊之間的調(diào)用關(guān)系。3. 詳細(xì)設(shè)計 定義相應(yīng)的存儲結(jié)構(gòu)并寫出各函數(shù)的偽碼算法。在這個過程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡單和易于調(diào)試，抽象數(shù)據(jù)類型的實現(xiàn)盡可能做到數(shù)據(jù)封裝，基本操作的規(guī)格說明盡可能明確具體。詳細(xì)設(shè)計的結(jié)果是對數(shù)據(jù)結(jié)構(gòu)和基本操作出進(jìn)一步的求精，寫出數(shù)據(jù)存儲結(jié)構(gòu)的類型定義，寫出函數(shù)形式的算法框架。4. 程序編碼 把詳細(xì)設(shè)計的結(jié)果進(jìn)一步求精為程序設(shè)計語言程序。程序要按照寫程序的規(guī)則來編寫。要結(jié)構(gòu)清晰，重點函數(shù)的重點變量，重點功能部分要加上清晰的程序注釋，使程序中邏輯概念清楚。5. 調(diào)試與測試 采用自底向上，分模塊進(jìn)行，即先調(diào)試低

7、層函數(shù)。調(diào)試正確后，認(rèn)真整理源程序及其注釋，形成格式和風(fēng)格良好的源程序清單和結(jié)果；6.編寫課程設(shè)計報告五、課程設(shè)計報告內(nèi)容與要求課程設(shè)計報告要求：(1) 不少于2500字（12-15頁），先交電子稿，由學(xué)委在12月5日前收齊，老師檢查通過后可打印(A4紙)交上來。 (2) 正文部分可以包括：需求分析、概要設(shè)計、詳細(xì)設(shè)計、測試與分析、總結(jié)、源程序清單。 (3) 設(shè)計報告一人一題，嚴(yán)禁抄襲，否則按不及格處理。課程設(shè)計報告內(nèi)容 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計實驗報告要求完成的內(nèi)容包括：1、 引言給出問題分析過程，充分分析和理解問題的設(shè)計要求，寫出本課程設(shè)計的研究內(nèi)容和研究意

8、義；2、 給出數(shù)據(jù)結(jié)構(gòu)描述根據(jù)要解決的問題，考慮各種可能的數(shù)據(jù)結(jié)構(gòu)類型，從中選擇一種較為有效的方法，并寫出采用的數(shù)據(jù)結(jié)構(gòu)描述及其功用。3、 給出相應(yīng)算法設(shè)計根據(jù)問題分析的結(jié)果，并確立好所選的數(shù)據(jù)結(jié)構(gòu)描述，然后寫出合理的算法設(shè)計過程，特別要注意所使用函數(shù)間的調(diào)用與被調(diào)用關(guān)系。4、 給出詳細(xì)程序清單根據(jù)算法的內(nèi)容，用計算機語言（如C語言）編寫完整的程序，并將程序在機器上反復(fù)調(diào)試，直到結(jié)果正確為止，最后將程序清單打印出來，要求附上詳細(xì)注解。特別要注意算法與程序的區(qū)別以及上下層模塊間的接口處理。5、 給出程序運行結(jié)果利用典型的測試用例，將數(shù)據(jù)輸入到程序執(zhí)行過程中去，記下執(zhí)行過程中屏幕顯示情況與相應(yīng)結(jié)果

9、。6、報告格式見附件六、考核方式與評分辦法1、 考核方式：上機測試及編寫課程設(shè)計實驗報告。2、 評分辦法：課程設(shè)計的上機測試結(jié)果占70%，實驗報告成績占30%。七課程設(shè)計 按7-9頁的排版規(guī)范來統(tǒng)一，不符合規(guī)范的將不能及格；（請注意看后面的附注部分）八、課程設(shè)計的參考資料參考資料：1嚴(yán)蔚敏 吳偉民，.數(shù)據(jù)結(jié)構(gòu)(C語言版). 清華大學(xué)出版社；2嚴(yán)蔚敏 吳偉民，.數(shù)據(jù)結(jié)構(gòu)題集(C語言版) 清華大學(xué)出版社；3 李春葆，數(shù)據(jù)結(jié)構(gòu)（C語言篇)習(xí)題與解析，清華大學(xué)出版社 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計題目 （每個同學(xué)可按下面列出的題目選題，如果有自己感興趣的題目可提交給老師，老師審核通過后才能作為課程設(shè)計題目）1. 迷

10、宮求解 （1）.設(shè)計目的 僅僅認(rèn)識到棧是一種特殊的線性表是遠(yuǎn)遠(yuǎn)不夠的，本次實習(xí)的目的在于使學(xué)生深入了解棧的特征，以便在實際問題背景下靈活運用它，同時還將鞏固這種數(shù)據(jù)結(jié)構(gòu)的構(gòu)造方法。 （2） 問題描述 迷宮問題是取自心理學(xué)的一個古典實驗。在該實驗中，把一只老鼠從一個無頂大盒子的門放入，在盒子中設(shè)置了許多墻，對行進(jìn)方向形成了多處阻擋。盒子僅有一個出口，在出口處放置一塊奶酪，吸引老鼠在迷宮中尋找道路以到達(dá)出口。對同一只老鼠重復(fù)進(jìn)行上述實驗，一直到老鼠從入口走到出口，而不走錯一步。老鼠經(jīng)過多次試驗最終學(xué)會走通迷宮的路線。設(shè)計一個計算機程序?qū)θ我庠O(shè)定的矩形迷宮A，求出一條從入口到出口的通路，或得出沒有通

11、路的結(jié)論。 （3）設(shè)計要求(1) 建立一個大小為m×n的任意迷宮（迷宮數(shù)據(jù)可由用戶輸入或由程序自動生成），并在屏幕上顯示出來；（2）找出一條通路的二元組（i,j）數(shù)據(jù)序列，（i,j）表示通路上某一點的坐標(biāo)。（3）用一種標(biāo)志（如數(shù)字8）在迷宮中標(biāo)出該條通路；（4）在屏幕上輸出迷宮和通路； 2. .赫夫曼編碼的應(yīng)用 1、 設(shè)計目的 在當(dāng)今信息爆炸時代，如何采用有效的數(shù)據(jù)壓縮技術(shù)節(jié)省數(shù)據(jù)文件的存儲空間和計算機網(wǎng)絡(luò)的傳送時間已越來越引起人們的重視，赫夫曼編碼正是一種應(yīng)用廣泛且非常有效的數(shù)據(jù)壓縮技術(shù)。 2、 問題描述 赫夫曼編碼的應(yīng)用很廣泛，利用赫夫曼樹求得的用于通信的二進(jìn)制編碼稱為赫夫曼編碼

12、。樹中從根到每個葉子都有一條路徑，對路徑上的各分支約定：指向左子樹的分支表示“0”碼，指向右子樹的分支表示“1”碼，取每條路徑上的“0”或“1”的序列作為和各個葉子對應(yīng)的字符的編碼，這就是赫夫曼編碼。 3、 設(shè)計要求 本設(shè)計要求是對輸入的一串電文字符實現(xiàn)赫夫曼編碼，再對赫夫曼編碼生成的代碼串進(jìn)行譯碼，輸出電文字符串。 4、 相關(guān)知識介紹 通常我們把數(shù)據(jù)壓縮的過程稱為編碼，解壓縮的過程稱為解碼。電報通信是傳遞文字的二進(jìn)制碼形式的字符串。但在信息傳遞時，總希望總長度能盡可能短，即采用最短碼。假設(shè)每種字符在電文中出現(xiàn)的次數(shù)為Wi，編碼長度為Li，電文中有n種字符，則電文編碼總長度為WiLi。若將此對

13、應(yīng)到二叉樹上，Wi為葉結(jié)點的權(quán)，Li為根結(jié)點到葉結(jié)點的路徑長度。那么，WiLi恰好為二叉樹上帶權(quán)路徑長度。因此 ，設(shè)計電文總長最短的二進(jìn)制前綴編碼，就是以n種字符出現(xiàn)的頻率作權(quán)，構(gòu)造一棵赫夫曼樹，此構(gòu)造過程稱為赫夫曼編碼。根據(jù)設(shè)計要求和分析，要實現(xiàn)本設(shè)計，必須實現(xiàn)以下幾個方面的功能： (1) 赫夫曼樹的建立； (2) 赫夫曼編碼的生成； (3) 編碼文件的譯碼。 3. .綜合排序 （1）設(shè)計目的 對于數(shù)據(jù)處理工作，排序是其最基本的運算之一。在當(dāng)今的計算機系統(tǒng)中，花費在排序上的時間占系統(tǒng)CPU運行時間的很大比重（約20%60%）。為了提高計算機的工作效率，人們提出了各種各樣的排序算法，這些算法充

14、分地展示了算法設(shè)計的某些重要原則和高超技巧。本設(shè)計旨在對一些常用的內(nèi)部排序算法作深入地探討和理解，通過比較，評價各算法的優(yōu)劣。 （2）問題描述 各種內(nèi)部排序算法的時間復(fù)雜度分析結(jié)果只給出了算法執(zhí)行時間的階，或大概執(zhí)行時間。試通過隨機的數(shù)據(jù)比較各算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動次數(shù)，以取得直觀感受。 （3）設(shè)計要求 (1) 實現(xiàn)基本排序方法：直接插入排序、希爾排序、冒泡、快速排序、直接選擇、堆排序；（要求至少實現(xiàn)四種算法） (2) 利用隨機函數(shù)產(chǎn)生不少于100個隨機整數(shù)，利用直接插入排序、希爾排序、冒泡、快速排序、直接選擇、堆排序等排序方法進(jìn)行遞增排序，統(tǒng)計各算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動次數(shù)

15、； (3) 可以用菜單的形式組織程序各功能； (4) 至少要用5組不同的輸入數(shù)據(jù)作比較，比較的指標(biāo)為有關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字移動次數(shù)（關(guān)鍵字交換計為3次移動）；(5 ) 觀察所有實驗結(jié)果并匯集成表格加以總結(jié)。 4 .學(xué)生信息管理 (1) 問題描述 為學(xué)生管理人員編寫一個學(xué)生信息管理的軟件；可用順序存儲或鏈?zhǔn)酱鎯Ψ绞綄崿F(xiàn)。 （2）設(shè)計要求要求每條學(xué)生信息至包含學(xué)號(xh)、姓名(xm)、性別(xb)、年齡(nl)、專業(yè)(zy)等，完成如下功能：a) 輸入學(xué)生基本信息記錄input( ) b) 增加一名學(xué)生記錄（可和功能1合并）insert( ) c) 刪除指定（按姓名）學(xué)生的信息delet

16、e( ) d) 修改指定（按姓名）學(xué)生的信息）modify( ) e) 查詢符合條件的學(xué)生（按專業(yè)）search( ) f) 顯示學(xué)生管理庫中的信息display( )5 集合的并、交和差運算（1）. 問題描述 編制一個能演示執(zhí)行集合的并、交和差運算的程序。（2） 基本要求 (1) 集合的元素限定為小寫字母字符 a.z 。(2) 演示程序以用戶和計算機的對話方式執(zhí)行。（3）測試數(shù)據(jù) (1)Set1="magazine"，Set2="paper"，Set1Set2="aegimnprz"，Setl Set2="ae"

17、，Set1-Set2="gimnz"。(2)Set1= " 012oper4a6tion89"，Set2="error data"，Set1Set2="adeinoprt"，Setl Set2="aeort"，Set1-Set2="inp"。（4） 實現(xiàn)提示以有序鏈表表示集合。（5） 選作內(nèi)容(1) 集合的元素判定和子集判定運算。(2) 求集合的補集。(3) 集合的混合運算表達(dá)式求值。(4) 集合的元素類型推廣到其他類型 ， 甚至任意類型。6 . 稀疏矩陣運算器(1) 問題描

18、述稀疏矩陣是指那些多數(shù)元素為零的矩陣。利用 " 稀疏 " 特點進(jìn)行存儲和計算可以大大 節(jié)省存儲空間 , 提高計算效率。實現(xiàn)一個能進(jìn)行稀疏矩陣基本運算的運算器。（2） 基本要求以三元組順序表表示稀疏矩陣,實現(xiàn)兩個矩陣相加、相減和相乘、及矩陣的轉(zhuǎn)置的運算。稀疏矩陣的輸入形式采用三元組表示 , 而運算結(jié)果的矩陣則以通常的陣列形式列出。（3） 實現(xiàn)提示 首先應(yīng)輸入矩陣的行數(shù)和列數(shù) , 并判別給出的兩個矩陣的行、列數(shù)對于所要求作的運算是否相匹配。可設(shè)矩陣的行數(shù)和列數(shù)均不超過 20 。 程序可以對三元組的輸入順序加以限制 , 例如 , 按行優(yōu)先。 在用三元組表示稀疏矩陣時 , 相加或相

19、減所得結(jié)果矩陣應(yīng)該另生成 , 乘積矩陣也可用二維數(shù)組存放。7. 算術(shù)表達(dá)式求值(1) 問題描述一個算術(shù)表達(dá)式是由操作數(shù)(operand)、運算符(operator)和界限符(delimiter)組成的。假設(shè)操作數(shù)是正整數(shù)，運算符只含加減乘除等四種運算符，界限符有左右括號和表達(dá)式起始、結(jié)束符“#”， 如：#（7+15）*（23-28/4）#。引入表達(dá)式起始、結(jié)束符是為了方便。（2） 基本要求 首先利用用棧 將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式：用棧對后綴表達(dá)式求值；從鍵盤讀入一個合法的算術(shù)表達(dá)式，輸出正確的結(jié)果。顯示輸入序列和棧的變化過程。 （3）實現(xiàn)提示為實現(xiàn)運算符優(yōu)先，可以使用兩個操作棧，操作數(shù)棧s

20、t ,用于存放操作數(shù)及運算結(jié)果；操作符棧op，用于存放操作符。 濱江學(xué)院數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計題 目 院 系 計算機系 從此開始橫線對齊。年級班級 2012級軟工工程（3） 學(xué)生姓名 學(xué) 號 學(xué) 期 2014-2015（一） 任課教師 黃 群 二一四年 十二月 十 日9論壇系統(tǒng)題目1 引言主要寫課題的研究背景和研究意義 在現(xiàn)在信息化的時代，網(wǎng)上論壇是最常見的網(wǎng)上交流的載體，是電子布告欄系統(tǒng)。網(wǎng)上論壇相當(dāng)于一個網(wǎng)上社區(qū)，人們在這個虛擬社區(qū)中能夠進(jìn)行各種交流活動。本課程就是關(guān)于網(wǎng)上論壇的一個系統(tǒng)，在本系統(tǒng)中用戶可以自由的發(fā)表意見、討論問題、瀏覽信息、相互交換信息與幫助等。論文及參考文獻(xiàn)全部用1.25倍行距，正文，正文中文一律采用宋體五號宋體字，英文為Times New Roman，中文標(biāo)點一律采用全角。 系統(tǒng)用戶主要有普通用戶、論壇管理員、分類討論區(qū)版主。其中普通用戶主要有：注冊、登錄、瀏覽論壇、查詢與修改、發(fā)表帖子、回復(fù)帖子、刪除自己發(fā)表的帖子等。論壇管理員具有最高的權(quán)限，除了具有可以使用版主的功能外，還具有進(jìn)行論壇用戶管理，并對討論區(qū)的所有帖子進(jìn)行管理。分類討論區(qū)版主除了使用普通用戶的功能