數(shù)據(jù)結(jié)構(gòu)課程設(shè)計題目及要求(2015-2016-2)

1、一 課程設(shè)計題目每位同學(xué)在本次課程設(shè)計期間須選擇兩道題目（1,2任選一題，3,4任選一題）并按照要求完成。1 考試報名管理系統(tǒng)1.1 題目簡介考試報名工作給各高校報名工作帶來了新的挑戰(zhàn)，給教務(wù)管理部門增加了很大的工作量，報名數(shù)據(jù)手工錄入既費時又會不可避免地出現(xiàn)錯誤，同時也給不少學(xué)生以可乘之機。本項目是對考試報名管理的簡單模擬，用菜單選擇方式完成下列功能：輸入考生信息；輸出考生信息；查詢考生信息；添加考生信息；修改考生信息；刪除考生信息。1.2 設(shè)計思路本項目的實質(zhì)是完成對考生信息的建立、查找、插入、修改、刪除等功能，可以首先定義項目的數(shù)據(jù)結(jié)構(gòu)，然后將每個功能寫成一個函數(shù)來完成對數(shù)據(jù)的操作，最后

2、完成主函數(shù)以驗證各個函數(shù)功能并得出運行結(jié)果。1.3 數(shù)據(jù)結(jié)構(gòu)本項目的數(shù)據(jù)是一組考生信息，每條考生信息由準(zhǔn)考證號、姓名、性別、年齡、報考類別等信息組成，這組考生信息具有相同特性，屬于同一數(shù)據(jù)對象，相鄰數(shù)據(jù)元素之間存在序偶關(guān)系。由此可以看出，這些數(shù)據(jù)也具有線性表中數(shù)據(jù)元素的性質(zhì)，所以該系統(tǒng)的數(shù)據(jù)可以采用線性表來存儲。我們知道，線性表的順序存儲結(jié)構(gòu)的特點是邏輯關(guān)系相鄰的兩個元素在物理位置上也相鄰，因此可以隨機存儲表中任一元素，它的存儲位置可用一個簡單、直觀的公式來表示。然而，從另一個方面來看，這個特點也鑄成了這種存儲結(jié)構(gòu)的弱點：在做插入或刪除操作時，需要移動大量元素。為克服這一缺點，我們引入另一種存

3、儲形式鏈?zhǔn)酱鎯?。鏈?zhǔn)酱鎯κ蔷€性表的另一種表示方法，由于它不要求邏輯上相鄰的元素在物理位置上也相鄰，因此它沒有順序存儲結(jié)構(gòu)的弱點，但同時也失去了順序表可隨機存取的特點。鏈?zhǔn)酱鎯Φ膬?yōu)點是插入或刪除元素時很方便，使用靈活。缺點是存儲密度小，存儲空間利用率低。事實上，鏈表插入、刪除運算的快捷是以空間代價來換取時間。順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動態(tài)操作。若線性表的長度變化不大，且其主要操作是查找，則采用順序表；若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。本項目對考生數(shù)據(jù)主要進(jìn)行插入、刪除、修改等操作，所以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)比較適合。用結(jié)構(gòu)體類型定義每個

4、考生信息，故該單鏈表中的每個結(jié)點的結(jié)構(gòu)可描述為：typedef struct examineechar examno10;/準(zhǔn)考證號 char name10; /姓名char sex;float age;char examtype5;/成績 ElemType;2 家譜管理系統(tǒng)2.1 題目簡介家譜（或稱族譜）是一種以表譜形式，記載一個以血緣關(guān)系為主體的家族世系繁衍和重要人物事跡的特殊圖書體裁。家譜是中國特有的文化遺產(chǎn)，是中華民族的三大文獻(xiàn)（國史，地志，族譜）之一，屬珍貴的人文資料，對于歷史學(xué)、民俗學(xué)、人口學(xué)、社會學(xué)和經(jīng)濟學(xué)的深入研究，均有其不可替代的獨特功能。本項目對家譜管理進(jìn)行簡單的模擬，以實

5、現(xiàn)查看祖先和子孫個人信息、插入家族成員、刪除家族成員等功能。2.2 設(shè)計思路本項目的實質(zhì)是完成對家譜成員信息的建立、查找、插入、修改、刪除等功能，可以首先定義家族成員的數(shù)據(jù)結(jié)構(gòu)，然后將每個功能寫成一個函數(shù)來完成對數(shù)據(jù)的操作，最后完成主函數(shù)以驗證各個函數(shù)功能并得出運行結(jié)果。2.3 數(shù)據(jù)結(jié)構(gòu)因為家族中的成員之間存在一個對多個的層次結(jié)構(gòu)關(guān)系，所以不能用上面講的線性表來表示。家譜從形狀上看像一顆倒長的樹，所以用樹結(jié)構(gòu)來表示家譜比較適合。樹型結(jié)構(gòu)是一類非常重要的非線性數(shù)據(jù)結(jié)構(gòu)，直觀看來，樹是以分支關(guān)系定義的層次結(jié)構(gòu)?？梢远骀湵碜鳛闃涞拇鎯Y(jié)構(gòu)，鏈表中的兩個鏈域分別指向該結(jié)點的第一個孩子結(jié)點和下一個兄弟

6、結(jié)點，固該表示法又稱二叉樹表示法，或孩子兄弟表示法。孩子兄弟表示法是一種鏈?zhǔn)酱鎯Y(jié)構(gòu)，它通過描述每個結(jié)點的一個孩子和兄弟信息來反映結(jié)點之間的層次關(guān)系，其具體的結(jié)點結(jié)構(gòu)為：firstChilddatanextSibling其中，firstchild為指向該結(jié)點第一個孩子的指針，nextsibling為指向該結(jié)點下一個兄弟，elem是數(shù)據(jù)元素內(nèi)容，舉例如下：其存儲形式定義如下：typedef struct CSLinklist    Elemtype data;    struct CSLinklist *firstchild,*next

7、sibling; CSLinklist,*CSTree;3 哈夫曼優(yōu)化編碼3.1 題目簡介信息時代，人們對使用計算機獲取信息、處理信息的依賴性越來越高。計算機系統(tǒng)面臨的是數(shù)值、文字、語言、音樂、圖形、動畫、靜圖像、電視視頻圖像等多種媒體。數(shù)字化的視頻和音頻信號的數(shù)量之大是驚人的，對于電視畫面的分辨率640×480的彩色圖像，30幀/s，則一秒鐘的數(shù)據(jù)量為：640×480×24×3022112M，所以播放時，需要221Mbps的通信回路。存儲時，1張CD可存640M，則僅可以存放289s的數(shù)據(jù)。多媒體信息中，視頻信息是一種比較特殊的媒體，數(shù)據(jù)量極大，信息豐

8、富，并以與時間密切相關(guān)的流的形式存在。因此，視頻數(shù)據(jù)的表達(dá)、組織、存儲和傳輸都有很大難度。解決的基礎(chǔ)在于對視頻數(shù)據(jù)進(jìn)行壓縮。自1948年Oliver提出了PCM編碼理論，編碼技術(shù)日趨成熟，已經(jīng)設(shè)計和應(yīng)用了許多壓縮算法和技術(shù)，如在H.261、JPEG和MPEG編碼標(biāo)準(zhǔn)中的應(yīng)用等。數(shù)據(jù)壓縮目前的主要目標(biāo)是較大的壓縮比、較快的壓縮解壓速度以及盡可能好的圖象還原質(zhì)量，而對于壓縮數(shù)據(jù)的處理如數(shù)據(jù)組織、檢索、重構(gòu)等還并沒有較好的考慮，也沒有一個比較完整的解決方案，因此在這方面仍有許多工作要做。哈夫曼編碼就是一種優(yōu)化編碼方法。本項目要求從鍵盤接收任意一個字符串，以#結(jié)尾。以字符串中某字符出現(xiàn)的次數(shù)，作為該字

9、符的權(quán)值。利用得到的權(quán)值構(gòu)建huffman樹、并輸出每個字符對應(yīng)的huffman編碼。另外，要求利用圖形庫函數(shù)，畫出這顆哈夫曼樹或動態(tài)演示該哈夫曼樹的生成過程。3.2 設(shè)計思路假設(shè)一個文件中出現(xiàn)了8種符號S0，SQ，S2，S3，S4，S5，S6，S7，那么每種符號要編碼，至少需要3bit。假設(shè)編碼成000，001，010，011，100，101，110，111。那么符號序列S0S1S7S0S1S6S2S2S3S4S5S0S0S1編碼后變成00000111100000111001001001110010100 0000001，共用了42bit。我們發(fā)現(xiàn)S0，S1，S2這3個符號出現(xiàn)的頻率比較大，

10、其它符號出現(xiàn)的頻率比較小，我們采用這樣的編碼方案：S0到S7的碼遼分別01，11，101，0000，0001，0010，0011，100，那么上述符號序列變成011110001110011101101000000010010010111，共用了39bit。盡管有些碼字如S3，S4，S5，S6變長了(由3位變成4位)，但使用頻繁的幾個碼字如S0，S1變短了，所以實現(xiàn)了壓縮。對于上述的編碼可能導(dǎo)致解碼出現(xiàn)非單值性：比如說，如果S0的碼字為01，S2的碼字為011，那么當(dāng)序列中出現(xiàn)011時，你不知道是S0的碼字后面跟了個1，還是完整的一個S2的碼字。因此，編碼必須保證較短的編碼決不能是較長編碼的前綴

11、。符合這種要求的編碼稱之為前綴編碼。3.3 數(shù)據(jù)結(jié)構(gòu)要構(gòu)造符合這樣的二進(jìn)制編碼體系，可以通過二叉樹來實現(xiàn)。1)首先統(tǒng)計出每個符合出現(xiàn)的頻率，上例SO到S7的出現(xiàn)頻率分別為4/14，3/14，2/14，1/14，1/14，1/14，1/14，1/14。2)從左到右把上述頻率按從小到大的順序排列。3)每一次選出最小的兩個值，作為二叉樹的兩個葉子節(jié)點，將和作為它們的根節(jié)點，這兩個葉子節(jié)點不再參與比較，新的根節(jié)點參與比較。4)重復(fù)(3)，直到最后得到和為1的根節(jié)點。將形成的二叉樹的左節(jié)點標(biāo)0，右節(jié)點標(biāo)1。把從最上面的根節(jié)點到最下面的葉子節(jié)點路徑中遇到的0，1序列串起來，得到各個符號的編碼?？梢钥吹?，符

12、號只能出現(xiàn)在樹葉上，任何一個字符的路徑都不會是另一字符路徑的前綴路徑，這樣，前綴編碼也就構(gòu)造成功了。這樣一棵二叉樹稱之為Huffman樹，常用于最佳判定，它是最優(yōu)二叉樹，是一種帶權(quán)路徑長度最短的二叉樹。所謂樹的帶權(quán)路徑長度，就是樹中所有的葉結(jié)點的權(quán)值乘上其到根結(jié)點的路徑長度(若根結(jié)點為0層，葉結(jié)點到根結(jié)點的路徑長度為葉結(jié)點的層數(shù))。樹的帶權(quán)路徑長度記為：WPL(W1*L1W2*L2W3*L3Wn*Ln)，N個權(quán)值Wi(i1，2，n)構(gòu)成一棵有N個葉結(jié)點的二叉樹，相應(yīng)的葉結(jié)點的路徑長度為Li(i1，2，n)。Huffman樹得出的WPL值最小。4 綜合排序4.1 題目簡介（1）至少采用四種排序方

13、法實現(xiàn)隨機生成100個數(shù)值的排序（可采用的排序方法有插入排序、希爾排序、冒泡排序、快速排序、選擇排序、堆排序、歸并排序）。并把排序后的結(jié)果保存在不同的文件中。（2）統(tǒng)計每一種排序方法的性能（以上機運行程序所花費的時間為準(zhǔn)進(jìn)行對比），找出其中兩種較快的方法。4.2 設(shè)計思路4.3 數(shù)據(jù)結(jié)構(gòu)略二 相關(guān)要求1. 程序設(shè)計規(guī)范性要求1）要求利用結(jié)構(gòu)化程序設(shè)計語言C語言來完成上述題目。2）對于有數(shù)據(jù)輸入的課題，要求輸入數(shù)據(jù)必須具有規(guī)范化的格式，并預(yù)先輸入10條以上規(guī)范化數(shù)據(jù)，便于檢查和演示。3）模塊化程序設(shè)計：要求在設(shè)計的過程中，按功能定義函數(shù)或書寫多個文件，進(jìn)行模塊化設(shè)計，各個功能模塊用函數(shù)的形式來實

14、現(xiàn)。4）所選課題必須上機通過，并獲得滿意的結(jié)果。5）注意程序書寫風(fēng)格：鋸齒型書寫格式，并適當(dāng)加入注釋語句。2. 程序設(shè)計考核要求2.1考核方法Ø 第一部分（50%）：程序演示演示程序，并正確回答老師的問題。Ø 第二部分（25%）：程序設(shè)計報告（電子及紙質(zhì)版）程序設(shè)計報告，內(nèi)容包括實驗?zāi)康?、課題任務(wù)要求、方案設(shè)計、主要程序清單(附注釋)、調(diào)試記錄（碰到的問題和解決方案）、程序設(shè)計心得及主要參考文獻(xiàn)。Ø 第三部分（25%）：出勤及表現(xiàn)情況2.2考核要求Ø 每位同學(xué)必須獨立完成所分配程序設(shè)計題目，同學(xué)之間可以相互討論，但不得抄襲，如發(fā)現(xiàn)代碼雷同，按抄襲處理。Ø 課程設(shè)計報告用A4紙正反打印，左側(cè)裝訂，報告內(nèi)容不得少于12頁。Ø 第八周周一前提交課程設(shè)計相關(guān)材料，包括程序設(shè)計報告的紙質(zhì)版本及電子文檔、源程序文件電子版、編譯鏈接后得到的可執(zhí)行文件電子版，電子稿、紙質(zhì)版由班長統(tǒng)一收齊后上交。每位同