《 資料結構與演算法 》課程設計
（2009/2010學年第二學期第20周）
指導教師： 王老師
班級：電腦科學與技術（3）班
學號：姓名：
《資料結構與演算法》課程設計
一、 前言
1．摘要
2．《資料結構與演算法》課程設計任務書
二、實驗目的
三、題目--赫夫曼編碼/解碼器
1．問題描述
2．基本要求
3．測試要求
4．實現提示
四、 需求分析--具體要求
五、 概要設計
六、 程式說明
七、 詳細設計
八、 實驗心得與體會
隨著計算機的普遍應用與日益發展，其應用早已不侷限於簡單的數值運算，而涉及到問題的分析、資料結構框架的設計以及設計最短路線等複雜的非數值處理和操作。演算法與資料結構的學習就是為以後利用計算機資源高效地開發非數值處理的電腦程式打下堅實的理論、方法和技術基礎。
演算法與資料結構旨在分析研究計算機加工的資料物件的特性，以便選擇適當的資料結構和儲存結構，從而使建立在其上的解決問題的演算法達到最優。
資料結構是在整個電腦科學與技術領域上廣泛被使用的術語。它用來反映乙個資料的內部構成，即乙個資料由那些成分資料構成，以什麼方式構成，呈什麼結構。資料結構有邏輯上的資料結構和物理上的資料結構之分。
邏輯上的資料結構反映成分資料之間的邏輯關係，而物理上的資料結構反映成分資料在計算機內部的儲存安排。資料結構是資料存在的形式。
《資料結構》主要介紹一些最常用的資料結構，闡明各種資料結構內在的邏輯關係，討論其在計算機中的儲存表示，以及在其上進行各種運算時的實現演算法，並對演算法的效率進行簡單的分析和討論。資料結構是介於數學、計算機軟體和計算機硬體之間的一門計算機專業的核心課程，它是計算機程式設計、資料庫、作業系統、編譯原理及人工智慧等的重要基礎，廣泛的應用於資訊學、系統工程等各種領域。
學習資料結構是為了將實際問題中所涉及的物件在計算機中表示出來並對它們進行處理。通過課程設計可以提高學生的思維能力，促進學生的綜合應用能力和專業素質的提高。
《資料結構與演算法》是計算機專業重要的核心課程之一，在計算機專業的學習過程中占有非常重要的地位。《資料結構與演算法課程設計》就是要運用本課程以及到目前為止的有關課程中的知識和技術來解決實際問題。特別是面臨非數值計算型別的應用問題時，需要選擇適當的資料結構，設計出滿足一定時間和空間限制的有效演算法。
本課程設計要求同學獨立完成乙個較為完整的應用需求分析。並在設計和編寫具有一定規模程式的過程中，深化對《資料結構與演算法》課程中基本概念、理論和方法的理解；訓練綜合運用所學知識處理實際問題的能力，強化物件導向的程式設計理念；使自己的程式設計與除錯水平有乙個明顯的提高。
資料結構作為一門學科主要研究資料的各種邏輯結構和儲存結構，以及對資料的各種操作。因此，主要有三個方面的內容：資料的邏輯結構；資料的物理儲存結構；對資料的操作（或演算法）。
通常，演算法的設計取決於資料的邏輯結構，演算法的實現取決於資料的物理儲存結構。資料結構是資訊的一種組織方式，其目的是為了提高演算法的效率，它通常與一組演算法的集合相對應，通過這組演算法集合可以對資料結構中的資料進行某種操作。
在當今資訊時代，資訊科技己成為當代知識經濟的核心技術。我們時刻都在和資料打交道。比如人們在外出工作時找最短路徑，在銀行查詢存款、通過網際網路查新聞、以及遠端教育報名等，所有這些都在與資料發生關係。
實際上，現實世界中的實體經過抽象以後，就可以成為計算機上所處理的資料。
。資料結構是介於數學、計算機軟體和計算機硬體之間的一門計算機專業的核心課程，它是計算機程式設計、資料庫、作業系統、編譯原理及人工智慧等的重要基礎，廣泛的應用於資訊學、系統工程等各種領域。
學習資料結構是為了將實際問題中所涉及的物件在計算機中表示出來並對它們進行處理。通過課程設計可以提高學生的思維能力，促進學生的綜合應用能力和專業素質的提高。通過此次課程設計主要達到以下目的：
了解並掌握資料結構與演算法的設計方法，具備初步的獨立分析和設計能力；
初步掌握軟體開發過程的問題分析、系統設計、程式編碼、測試等基本方法和技能；
提高綜合運用所學的理論知識和方法獨立分析和解決問題的能力；
訓練用系統的觀點和軟體開發一般規範進行軟體開發，培養軟體工作者所應具備的科學的工作方法和作風。
1. 問題描述
利用赫夫曼編碼進行通訊可以大大提高通道利用率，縮短資訊傳輸時間，降低傳輸成本。這要求在傳送端通過乙個編碼系統對待傳輸資料預先編碼，在接收端將傳來的資料進行解碼（復原）。對於雙工通道（即可以雙向傳輸資訊的通道），每端都需要乙個完整的編/解碼系統。
試為這樣的資訊收發站編寫乙個赫夫曼碼的編/解碼系統。
2. 基本要求
乙個完整的系統應具有以下功能：
(1) i：初始化（initialization）。從終端讀入字符集大小n，以及n個字元和n個權值，建立赫夫曼樹，並將它存於檔案hfmtree中。
(2) e：編碼（encoding）。利用已建好的赫夫曼樹（如不在記憶體，則從檔案hfmtree中讀入），對檔案tobetran中的正文進行編碼，然後將結果存入檔案codefile中。
(3) d：解碼（decoding）。利用已建好的赫夫曼樹將檔案codefile中的**進行解碼，結果存入檔案textfile中。
以下為選做：
(4) p：印**檔案（print）。將檔案codefile以緊湊格式顯示在終端上，每行50個**。同時將此字元形式的編碼檔案寫入檔案codeprin中。
(5) t：印赫夫曼樹（tree printing）。將已在記憶體中的赫夫曼樹以直觀的方式（比如樹）顯示在終端上，同時將此字元形式的赫夫曼樹寫入檔案treeprint 中。
3. 測試要求
(1) 已知某系統在通訊聯絡中只可能出現八種字元，其頻率分別為0.05,0.29,0.
07,0.08,0.14,0.
23,0.03,0.11，試設計赫夫曼編碼。
(2) 用下表給出的字符集和頻度的實際統計資料建立赫夫曼樹，並實現以下報文的編碼和解碼：「this programe is my f**orite」。
4. 實現提示
(1) 編碼結果以文字方式儲存在檔案codefile中。
(2) 使用者介面可以設計為「選單」方式：顯示上述功能符號，再加上「q」，表示退出執行quit。請使用者鍵入乙個選擇功能符。
此功能執行完畢後再顯示此選單，直至某次使用者選擇了「q」為止。
(3) 在程式的一次執行過程中，第一次執行i，d或c命令之後，赫夫曼樹已經在記憶體了，不必再讀入。每次執行中不一定執行i命令，因為檔案hfmtree可能早已建好。
四、具體要求：
課程設計成果的內容必須由以下四個部分組成，缺一不可。
(1) 上交源程式：學生按照實驗題目的具體要求所開發的所有源程式（應該放到乙個資料夾中）；
(2) 上交程式的說明檔案：（儲存在.txt中）在說明文件中應該寫明上交程式所在的目錄，上交程式的主程式檔名，如果需要安裝，要有程式的安裝使用說明；
(3) 設計報告：（儲存在word 文件中，檔名要求： 按照「姓名_學號_設計題目」起名，如檔名為「 張三_***_赫夫曼編碼 」.doc。列印稿用a4紙）。
其中包括:
題目；實驗目的；
需求分析：在該部分中敘述實現的功能要求；
概要設計：
在此說明每個部分的演算法設計說明（可以是描述演算法的流程圖），每個程式中使用的儲存結構設計說明（如果指定儲存結構請寫出該儲存結構的定義）；
詳細設計
各個演算法實現的源程式，對每個題目要有相應的源程式（可以是一組源程式，每個功能模組採用不同的函式實現）。源程式要按照寫程式的規則來編寫。要結構清晰，重點函式的重點變數、重點功能部分要加上清晰的程式注釋；
除錯分析
測試資料，測試輸出的結果，時間複雜度分析，和每個模組設計和除錯時存在問題的思考（問題是哪些？問題如何解決？），演算法的改進設想；
總結：總結可以包括 : 設計過程的收穫、遇到問題及解決問題過程的思考、程式除錯能力的思考、對資料結構這門課程的思考、在設計過程中對《資料結構》課程的認識等內容。
（4）考核成績評定標準：
本課程設計的評價由三部分組成，包括程式演示（50%），課程設計報告（30%），回答教師提問（20%）。
1．程式演示：
優功能完善，全部測試正確，並且能夠對區域性進行完善。
良功能完善，但測試欠缺。
中功能基本完善，但程式尚有部分錯誤。
及格完成記憶體中赫夫曼編碼/解碼，但不涉及檔案操作。
不及格功能不完善，且程式錯誤較多，無法執行。
2．課程設計報告：
1．優包括設計內容，設計思想，已經完成的任務及達到的目標，設計思路清晰、書寫條理清楚，源程式結構合理、清晰，注釋說明完整，有對本次課程設計的心得體會。
2．良包括設計內容，設計思想，已經完成的任務及達到的目標，設計思路基本清晰、書寫條理基本清楚，源程式結構合理、清晰，注釋說明基本完整，有對本次課程設計的心得體會。
3．中課程設計報告內容基本完整，思路較清晰，書寫基本清楚，源程式結構尚可，有注釋說明但不完整。
4．及格課程設計報告內容基本完整，思路較差，書寫尚清楚。
5．不及格課程設計報告內容不完整，書寫沒有條理。
3．回答教師提問：
1. 優能回答教師提出的所有問題，並完全正確，思路清晰
2. 良基本能回答教師提出的所有問題，有些小錯誤
3. 中基本能回答教師提出的問題，少數問題回答錯誤或不清楚
4. 及格能回答教師提出的問題，但較多問題回答錯誤或不能回答
5. 不及格基本不能回答教師提出的問題
4、概要設計
1) 問題分析哈夫曼樹的定義
1.哈夫曼樹節點的資料型別定義為：
typedef struct赫夫曼樹的結構體
char ch;
int weight權值
資料結構課程設計哈夫曼編碼
淮海工學院電腦科學系 實驗報告書 課程名 資料結構 題目 樹形資料結構實驗 班級 軟體112 學號 姓名樹型資料結構實驗報告要求 1目的與要求 1 熟練掌握huffman樹的建立演算法與程式設計實現 2 熟練掌握huffman編碼演算法的實現與程式設計應用 3 建立較為實用的通訊報文huffman編...
資料結構課程設計報告 哈夫曼編碼
廣東工業大學華立學院 課程設計 課程名稱 資料結構 題目名稱 哈夫曼編碼 學生學部 系 資訊與計算機學部 專業班級 09計算機2班 學號學生姓名 指導教師 2010 年 12 月23 日 廣東工業大學華立學院 課程設計 任務書 一 課程設計 程序安排 二 應收集的資料及主要參考文獻 1 嚴蔚敏，吳偉...
資料結構課程設計總結報告哈夫曼編碼解碼
4.3 流程圖 6 1.問題描述 設計乙個利用哈夫曼演算法的編碼和解碼系統，重複地顯示並處理以下專案，直到選擇退出為止。1 初始化 鍵盤輸入字符集大小n n個字元和n個權值，建立哈夫曼樹 2 編碼 利用建好的哈夫曼樹生成哈夫曼編碼 3 輸出編碼 4 顯示哈夫曼樹 5 介面設計的優化 6 設字符集及頻...