【正文】 1 計(jì)算機(jī)學(xué)院信息 管理 與信息 系統(tǒng) 專業(yè) 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 題 目： 哈夫曼樹的應(yīng)用 班 級(jí)： 信管 09101班 姓 名： 趙林芬 學(xué) 號(hào)： 202117020214 同組人姓名： 陳立芳 王紅 起 迄 日 期 ： 課程設(shè)計(jì)地點(diǎn) : 系辦公樓 E3A513 指導(dǎo)教師： 孫葉楓 評(píng)閱意見： 成績(jī)?cè)u(píng)定： 評(píng)閱人： 日期： 完成日期： 2021 年 3 月 4 日 2 目錄 設(shè)計(jì)目的 ........................................................................................................................................ 3 需求分析 ........................................................................................................................................ 4 選題的意義及背景 ............................................. 4 輸入 /輸出形式和輸出值的范圍 .................................. 4 概要設(shè)計(jì) ........................................................................................................................................ 4 設(shè)計(jì)思想 .................................................... 4 函數(shù)間的關(guān)系 ................................................ 4 詳細(xì)設(shè)計(jì) ........................................................................................................................................ 5 哈夫曼的主要結(jié)構(gòu) ............................................. 5 結(jié)構(gòu)定義 ................................................. 5 主要函數(shù)聲明及功能描述 ................................... 6 源程序 ...................................................... 7 頭文件 ................................................... 7 源文件 ................................................... 8 程序測(cè)試結(jié)果 及問題分 析 ......................................................................................................... 17 總結(jié) .............................................................................................................................................. 18 參考文獻(xiàn) ...................................................................................................................................... 18 3 數(shù)據(jù)結(jié)構(gòu)作為一門學(xué)科主要研究數(shù)據(jù)的各種邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，以及對(duì)數(shù)據(jù)的各種操作。因此，主要有三個(gè)方面的內(nèi)容：數(shù)據(jù)的邏輯結(jié)構(gòu)；數(shù)據(jù)的物理存儲(chǔ)結(jié)構(gòu)；對(duì)數(shù)據(jù)的操作（或算法）。通常，算法的設(shè)計(jì)取決于數(shù)據(jù)的邏輯結(jié)構(gòu)，算法的實(shí)現(xiàn)取決于數(shù)據(jù)的物理存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是信息的一種組織方式，其目的是為了提高算法的效率，它通常與一組 算法的集合相對(duì)應(yīng)，通過這組算法集合可以對(duì)數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)進(jìn)行某種操作。 在當(dāng)今信息時(shí)代，信息技術(shù)己成為當(dāng)代知識(shí)經(jīng)濟(jì)的核心技術(shù)。我們時(shí)刻都在和數(shù)據(jù)打交道。比如人們?cè)谕獬龉ぷ鲿r(shí)找最短路徑，在銀行查詢存款、通過互聯(lián)網(wǎng)查新聞、以及遠(yuǎn)程教育報(bào)名等，所有這些都在與數(shù)據(jù)發(fā)生關(guān)系。實(shí)際上，現(xiàn)實(shí)世界中的實(shí)體經(jīng)過抽象以后，就可以成為計(jì)算機(jī)上所處理的數(shù)據(jù)。 數(shù)據(jù)結(jié)構(gòu)課程主要是研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中所出現(xiàn)的計(jì)算機(jī)操作對(duì)象以及它們之間的關(guān)系和操作的學(xué)科。 數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)軟件和計(jì)算機(jī)硬件之間的一門計(jì)算 機(jī)專業(yè)的核心課程，它是計(jì)算機(jī)程序設(shè)計(jì)、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ)，廣泛的應(yīng)用于信息學(xué)、系統(tǒng)工程等各種領(lǐng)域。 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)是為了將實(shí)際問題中所涉及的對(duì)象在計(jì)算機(jī)中表示出來并對(duì)它們進(jìn)行處理。通過課程設(shè)計(jì)可以提高學(xué)生的思維能力， 促進(jìn)學(xué)生的綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。通過此次課程設(shè)計(jì)主要達(dá)到以下目的： 一、 了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力； 二、 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等基本方法和技能； 三、 提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析 和解決問題的能力； 四、 訓(xùn)練用系統(tǒng)的觀點(diǎn)和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。 4 2． 需求分析 選題的意義及背景 鍛煉我們的編碼能力，真正理解數(shù)據(jù)結(jié)構(gòu)的編碼思想 ,并且鍛煉我們的動(dòng)手能力和成員間的配合，提高程序編寫能力。 在信息傳遞時(shí)，希望長度能盡可能短，即采用最短碼。赫夫曼編碼的應(yīng)用，就是采用這種有效的數(shù)據(jù)壓縮技術(shù)可以節(jié)省數(shù)據(jù)文件的存儲(chǔ)空間和計(jì)算機(jī)網(wǎng)絡(luò)的傳送時(shí)間。 輸入 /輸出形式和輸出值的范圍 輸入信息以加載存檔的 文件為方式，加載 不成功，提示出錯(cuò)信息，加載成功后，系統(tǒng)對(duì)其編碼，并按照選擇對(duì)各種相關(guān)信息存檔 3． 概要設(shè)計(jì) 設(shè)計(jì)思想 哈夫曼樹用鄰接矩陣作為存儲(chǔ)結(jié)構(gòu)，借助靜態(tài)鏈表來實(shí)現(xiàn)遍歷。 利用多重結(jié)構(gòu)體的形式設(shè)計(jì)出所需的 變量類型， 還有基本的文件讀寫知識(shí)，同時(shí) 借助九大子函數(shù)結(jié)合一個(gè)主函數(shù)設(shè)計(jì)了此課程內(nèi)容，第一部分為信息的讀寫及統(tǒng)計(jì)；第二部分為哈夫曼樹及其編碼的建立，再將編碼信息寫進(jìn)文件；第三部分為給信息加密在寫進(jìn)文件，再在對(duì)其翻譯。最后的主函數(shù)是整個(gè)程序的組織者，利用 switch 選擇循環(huán)將九大子函數(shù)聯(lián)系起來，畫龍點(diǎn) 睛。 這樣整個(gè)程序的基本流出就出來了，再根據(jù)此流出設(shè)計(jì)出源程序。 函數(shù)間的關(guān)系 哈夫曼系統(tǒng)，函數(shù)間的關(guān)系如圖所示： 界面運(yùn)行圖如下： 頭文件及原文件 文件的讀寫 哈夫曼的建立及編碼 文件加密編碼及寫入文件 從文 件中讀取信息 將信息寫進(jìn)文件 構(gòu)建哈夫曼樹 建立哈夫曼編碼 給文件信息加密編碼 將已編碼信息寫進(jìn)文件 將編碼信息翻譯及寫入文 件 將編碼規(guī)則寫進(jìn)文件 件 統(tǒng)計(jì)信息中各字符的出現(xiàn)次數(shù) 5 詳細(xì)設(shè)計(jì) 哈夫曼的主要結(jié)構(gòu) 結(jié)構(gòu)定義 ： define MAXVALUE 1000//定義最大權(quán)值 define MAXBIT 100//定義哈夫曼樹中葉子結(jié)點(diǎn)個(gè)數(shù) typedef struct { char data。//字符值 int num。//某個(gè)值的字符出現(xiàn)的次數(shù) }TotalNode。 //統(tǒng)計(jì)結(jié)點(diǎn)，包括字符種類和出現(xiàn)次數(shù) typedef struct { TotalNode tot[300]。//統(tǒng)計(jì)結(jié)點(diǎn)數(shù)組 int num。//統(tǒng)計(jì)數(shù)組中含有的字符個(gè)數(shù) }Total。 //統(tǒng)計(jì)結(jié)構(gòu)體，包括統(tǒng)計(jì)數(shù)組和字符種類數(shù) typedef struc