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

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

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

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

5、現查看祖先和子孫個人信息、插入家族成員、刪除家族成員等功能。2.2 設計思路本項目的實質是完成對家譜成員信息的建立、查找、插入、修改、刪除等功能，可以首先定義家族成員的數據結構，然后將每個功能寫成一個函數來完成對數據的操作，最后完成主函數以驗證各個函數功能并得出運行結果。2.3 數據結構因為家族中的成員之間存在一個對多個的層次結構關系，所以不能用上面講的線性表來表示。家譜從形狀上看像一顆倒長的樹，所以用樹結構來表示家譜比較適合。樹型結構是一類非常重要的非線性數據結構，直觀看來，樹是以分支關系定義的層次結構。可以二叉鏈表作為樹的存儲結構，鏈表中的兩個鏈域分別指向該結點的第一個孩子結點和下一個兄弟

6、結點，固該表示法又稱二叉樹表示法，或孩子兄弟表示法。孩子兄弟表示法是一種鏈式存儲結構，它通過描述每個結點的一個孩子和兄弟信息來反映結點之間的層次關系，其具體的結點結構為：firstChilddatanextSibling其中，firstchild為指向該結點第一個孩子的指針，nextsibling為指向該結點下一個兄弟，elem是數據元素內容，舉例如下：其存儲形式定義如下：typedef struct CSLinklist    Elemtype data;    struct CSLinklist *firstchild,*next

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

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

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

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

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

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

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

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