數(shù)據(jù)結(jié)構(gòu)綜合設(shè)計(jì)題目列表.ppt

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)時(shí)間安排,每周進(jìn)行檢查，匯報(bào)進(jìn)展,1.每個(gè)題目每個(gè)同學(xué)獨(dú)自完成，同一個(gè)宿舍的同學(xué)不選相同的題目。 2.完成后才用答辯的形式，對(duì)自己所做系統(tǒng)的功能、特色講解，并能正確對(duì)老師指定的代碼做出解釋。同一個(gè)題目的同學(xué)，在同一時(shí)段答辯，以檢查是否有相似性，以及就水平不同進(jìn)行比較。 3.每個(gè)題目的難易不同，對(duì)應(yīng)的成績(jī)會(huì)不同；每個(gè)題目所做的功能及質(zhì)量的不同，會(huì)打出不同的成績(jī)。 4.每個(gè)功能的核心都用C語(yǔ)言實(shí)現(xiàn)，如果純C實(shí)現(xiàn)，所有的東西都自己實(shí)現(xiàn)，除非必要的基本的函數(shù)調(diào)用一些，得分更高。,綜合設(shè)計(jì)要求,綜合設(shè)計(jì)題目列表,1.實(shí)體的描述:根據(jù)提供的數(shù)據(jù),能顯示該實(shí)體,并對(duì)實(shí)體進(jìn)行裁剪等功能。（人數(shù)不限

2、） 該設(shè)計(jì)內(nèi)容主要涉及到面、線、點(diǎn)的表示，主要用線性表鏈?zhǔn)酱鎯?chǔ)方面的知識(shí)，會(huì)采用多級(jí)鏈表，因此要比書(shū)中相應(yīng)的知識(shí)的復(fù)雜很多。 該題目出自教圖形圖像方面的老師，題目所涉及的內(nèi)容會(huì)在大三、大四或畢業(yè)設(shè)計(jì)時(shí)使用。 建議能力強(qiáng)的同學(xué)，選擇此題目。,2.提供手機(jī)號(hào)碼的管理方案。（人數(shù)不限） 由于手機(jī)號(hào)碼的特殊性，將號(hào)碼組織成何種結(jié)構(gòu)是關(guān)鍵。因此從如何組織邏輯結(jié)構(gòu)、物理結(jié)構(gòu)，實(shí)現(xiàn)哪些算法，如何實(shí)現(xiàn)，這些都需要設(shè)計(jì)者分析考慮。 功能主要實(shí)現(xiàn)在現(xiàn)實(shí)生活中真實(shí)的號(hào)碼中查找指定的號(hào)碼，能增加和刪除號(hào)碼，能遍歷所有的號(hào)碼，要求高效，用時(shí)短。 分析過(guò)程需要綜合書(shū)中全部知識(shí)，實(shí)現(xiàn)可能只會(huì)使用書(shū)中部分知識(shí)。 因?yàn)闆](méi)有任何

3、可以參考的方案，全部需要自己分析與考慮，建議能力強(qiáng)的同學(xué)選擇此題目。,3.管理系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)。（4人） 實(shí)現(xiàn)的管理系統(tǒng)要求功能較全，且能與現(xiàn)實(shí)生活接近考慮數(shù)據(jù)量大，如有上百萬(wàn)條的情況。 主要用線性表的知識(shí)（順序與鏈?zhǔn)酱鎯?chǔ)都會(huì)涉及），涉及查找與排序算法，文件的知識(shí)是必須。 這里綜合用到數(shù)據(jù)結(jié)構(gòu)的知識(shí)，都不復(fù)雜，但有些鎖碎，建議想強(qiáng)化基本知識(shí)掌握的同學(xué)選此題目。,游戲中要考慮的因素:可以實(shí)現(xiàn)二維游戲,也可以是三維游戲。 二維游戲要求考慮:碰撞檢測(cè)加截場(chǎng)景聲音加載文件保存與加載鼠標(biāo)拾取與操作地圖之生成。 三維游戲要求考慮:碰撞檢測(cè)骨骼動(dòng)畫(huà)之實(shí)現(xiàn)靈活攝像機(jī)設(shè)置粒子系統(tǒng)之實(shí)現(xiàn)地形生成天空生成動(dòng)態(tài)流體之

4、模擬場(chǎng)景之渲染輸入之交互處理。,4.飛機(jī)游戲的實(shí)現(xiàn)（2人） 該游戲的基本要求：飛機(jī)能飛，有聲音，鼠標(biāo)與鍵盤控制靈活、合理，能發(fā)射子彈，碰雷爆炸。,5.精靈動(dòng)畫(huà)之實(shí)現(xiàn)（2人）。,6.游戲中部分主要功能之模擬，如尋路功能、地圖之生成之模擬。（2人）,游戲可以設(shè)計(jì)的簡(jiǎn)單，也可以復(fù)雜，這取決于你個(gè)人的能力，但界面一定要美觀，操作方便。,7.一元多項(xiàng)式的各種運(yùn)算（10人） 除了考慮書(shū)中已提供的加法功能外，可以實(shí)現(xiàn)更多的運(yùn)算。 該算法主要涉及線性表的鏈?zhǔn)讲僮?，是?shù)據(jù)結(jié)構(gòu)中最基本，也是日后應(yīng)用最常用的操作，也是后續(xù)課程認(rèn)為學(xué)生在這方面編程能力最差的一部分知識(shí)。 沒(méi)有完整控制過(guò)鏈表的同學(xué)只能選擇此題目，因?yàn)檫@

5、是最基本的知識(shí)，必須掌握。,8.迷宮求解。（2人） 主要利用棧實(shí)現(xiàn)，要求能動(dòng)態(tài)生成迷宮，顯示有幾條路徑，用圖形界面顯示最合適的路徑。,9.離散事件模擬。（2人） 主要利用隊(duì)列實(shí)現(xiàn)。要求能用圖形界面顯示狀態(tài)。,10.計(jì)算器的實(shí)現(xiàn)。（4人） 主要利用棧實(shí)現(xiàn)表達(dá)式求值，要求功能與界面模擬WINDOWS計(jì)算器，支持鼠標(biāo)。,11.記事本之文本編輯的實(shí)現(xiàn)。（3人） 要求功能與界面模擬WINDOWS記事本，支持鼠標(biāo)，因?yàn)橛浭卤竟δ茌^多，可以根據(jù)自己的能力模擬出部分功能，文本編輯這部分功能必須實(shí)現(xiàn)，主要利用串的知識(shí)。,12.建立索引詞表。（2人） 主要利用串的知識(shí)實(shí)現(xiàn)。,13.所有矩陣的壓縮存儲(chǔ)實(shí)現(xiàn)。（2人）

6、 包括特殊矩陣與稀疏矩陣的壓縮存儲(chǔ)，并在上面實(shí)現(xiàn)一定的應(yīng)用，比如顯示與轉(zhuǎn)置等。,14.二叉樹(shù)遍歷算法。 （3人） 要求實(shí)現(xiàn)前、中、后序、層序遍歷的遞歸與非遞歸算法，及存儲(chǔ)加索引的算法和在索引上的遍歷算法。,15.樹(shù)的遍歷和樹(shù)的計(jì)數(shù)（2人）。,16.對(duì)一西文文本提供最優(yōu)的編、解碼方案，并給出編碼與解碼結(jié)果。（3人） 建議已掌握并實(shí)現(xiàn)線性表操作的同學(xué)，但編程能力仍不算高的同學(xué)可選擇此題目，畢竟書(shū)中已提供了主要源碼，自己可發(fā)揮的余地較小。,17.給定一圖，在遍歷的基礎(chǔ)上確定其是否是連通。（4人） 已掌握并實(shí)現(xiàn)線性表操作、編程有一定能力的同學(xué)，可選此題目。書(shū)中雖然有源碼，但離實(shí)現(xiàn)有一些距離，加上老師沒(méi)

7、有講解，考驗(yàn)分析代碼之能力。,18.給定一圖，用兩種方法求其最小生成樹(shù)，確定其結(jié)果是否一致。（4人） 已掌握并實(shí)現(xiàn)線性表操作、編程有一定能力的同學(xué)，可選此題目。 書(shū)中提到的一個(gè)方法有源碼，關(guān)于算法的講解也很詳細(xì)；另一個(gè)方法只有思想，完全沒(méi)有代碼，實(shí)現(xiàn)它考驗(yàn)有算法的基礎(chǔ)上，如何表示與實(shí)現(xiàn)算法之能力。,19.給定一圖，求其拓樸排序。（3人） 要求存儲(chǔ)采用鄰接矩陣與鄰接鏈表兩種方法，其入度為零的點(diǎn)可以采用進(jìn)棧和進(jìn)隊(duì)列兩種方法。尤其是書(shū)中未提到的方法必須實(shí)現(xiàn)。已掌握并實(shí)現(xiàn)線性表操作、編程有一定能力的同學(xué)，可選此題目。 要求以圖形界面呈現(xiàn)結(jié)果。,20.給定一圖，在其拓樸排序的基礎(chǔ)上，求最關(guān)鍵路徑。（4人

8、） 該算法雖然較復(fù)雜，涉及到的知識(shí)也比較多，但書(shū)中畢竟有源碼，而且講解也較為詳細(xì)。已掌握并實(shí)現(xiàn)線性表操作、編程有一定能力的同學(xué)，可選此題目。 要求以圖形界面呈現(xiàn)結(jié)果。,21.給定一圖，求任意兩點(diǎn)間的最短路徑。（4人） 該算法有一定的復(fù)雜性，老師的講解盡管不詳細(xì)，但書(shū)中畢竟有源碼。建議已掌握并實(shí)現(xiàn)線性表操作、編程有一定能力的同學(xué)，選此題目。 要求以圖形界面呈現(xiàn)結(jié)果。,22.實(shí)現(xiàn)所有的靜態(tài)查找表。（3人） 該部分算法較好理解，不太復(fù)雜，已掌握并實(shí)現(xiàn)線性表操作的同學(xué)，可選此題目。 要求最后關(guān)于各種靜態(tài)查找表的性能比較得出一個(gè)結(jié)論。,23.實(shí)現(xiàn)所有的動(dòng)態(tài)查找表。（4人） 該部分算法有一定的難度，尤其二叉排序樹(shù)與平衡二叉樹(shù)，涉及樹(shù)的插入與刪除等復(fù)雜操作。實(shí)現(xiàn)不易，盡管書(shū)中給出的代碼較為詳細(xì) 建議能力強(qiáng)的同學(xué)選擇此題目。,24.實(shí)現(xiàn)所有的哈希函數(shù)構(gòu)造法。（3人） 書(shū)中算法只有思想，沒(méi)有代碼，實(shí)現(xiàn)不易。 已掌握并實(shí)現(xiàn)線性表操作的同學(xué)，可選此題目。,25.實(shí)現(xiàn)所有哈希表的解決沖突的方法。（3人） 書(shū)中算法只有思想，沒(méi)有代碼，實(shí)現(xiàn)不易。 已掌握并實(shí)現(xiàn)線性表操作的同學(xué)，可選此