數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 哈弗曼編碼

數(shù)據(jù)結(jié)構(gòu)——哈夫曼編碼/譯碼器PAGE20數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)院系：班級(jí)：組別：指導(dǎo)教師：摘要隨著計(jì)算機(jī)的普遍應(yīng)用與日益發(fā)展，其應(yīng)用早已不局限于簡(jiǎn)單的數(shù)值運(yùn)算，而涉及到問題的分析、數(shù)據(jù)結(jié)構(gòu)框架的設(shè)計(jì)以及設(shè)計(jì)最短路線等復(fù)雜的非數(shù)值處理和操作。算法與數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)就是為以后利用計(jì)算機(jī)資源高效地開發(fā)非數(shù)值處理的計(jì)算機(jī)程序打下堅(jiān)實(shí)的理論、方法和技術(shù)基礎(chǔ)。算法與數(shù)據(jù)結(jié)構(gòu)旨在分析研究計(jì)算機(jī)加工的數(shù)據(jù)對(duì)象的特性，以便選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，從而使建立在其上的解決問題的算法達(dá)到最優(yōu)。數(shù)據(jù)結(jié)構(gòu)是在整個(gè)計(jì)算機(jī)科學(xué)與技術(shù)領(lǐng)域上廣泛被使用的術(shù)語。它用來反映一個(gè)數(shù)據(jù)的內(nèi)部構(gòu)成，即一個(gè)數(shù)據(jù)由那些成分?jǐn)?shù)據(jù)構(gòu)成，以什么方式構(gòu)成，呈什么結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)有邏輯上的數(shù)據(jù)結(jié)構(gòu)和物理上的數(shù)據(jù)結(jié)構(gòu)之分。邏輯上的數(shù)據(jù)結(jié)構(gòu)反映成分?jǐn)?shù)據(jù)之間的邏輯關(guān)系，而物理上的數(shù)據(jù)結(jié)構(gòu)反映成分?jǐn)?shù)據(jù)在計(jì)算機(jī)內(nèi)部的存儲(chǔ)安排。數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)存在的形式?！稊?shù)據(jù)結(jié)構(gòu)》主要介紹一些最常用的數(shù)據(jù)結(jié)構(gòu)，闡明各種數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系，討論其在計(jì)算機(jī)中的存儲(chǔ)表示，以及在其上進(jìn)行各種運(yùn)算時(shí)的實(shí)現(xiàn)算法，并對(duì)算法的效率進(jìn)行簡(jiǎn)單的分析和討論。數(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ì)目的數(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)。二.需求分析摘要 1目錄 1一.設(shè)計(jì)目的 2二.需求分析 32.1哈夫曼編碼/譯碼器簡(jiǎn)介 32.2需求分析 32.2.1程序的基本功能 32.2.2輸入/輸出形式 32.2.3測(cè)試數(shù)據(jù)要求 32.3基本要求 3a.編/譯碼系統(tǒng)應(yīng)具有以下功能： 3b.測(cè)試數(shù)據(jù) 4三.概要設(shè)計(jì) 43.1問題分析哈夫曼樹的定義 43.2系統(tǒng)結(jié)構(gòu)圖（功能模塊圖） 5四.詳細(xì)設(shè)計(jì) 54.1編碼與譯碼 54.2源代碼 84.3運(yùn)行結(jié)果 12五.調(diào)試分析 12在我自己課程設(shè)計(jì)中，就在編寫好源代碼后的調(diào)試中出現(xiàn)了不少的錯(cuò)誤，遇到了很多麻煩及困難，我的調(diào)試及其中的錯(cuò)誤和我最終找出錯(cuò)誤，修改為正確的能夠執(zhí)行的程序中，通過分析，我學(xué)到了： 12六.小結(jié) 142.1哈夫曼編碼/譯碼器簡(jiǎn)介舉例說明，先前快速遠(yuǎn)距離通信的主要手段是電報(bào)，即將需傳送的文字轉(zhuǎn)換成由二進(jìn)制的字符組成的字符串。在傳送電文時(shí)，希望總長(zhǎng)盡可能地短，如果對(duì)每個(gè)字符設(shè)計(jì)長(zhǎng)度不等的編碼，且讓電文中出現(xiàn)次數(shù)較多的字符采用盡可能短的編碼，以減少經(jīng)費(fèi)。哈夫曼樹就是根據(jù)此原理設(shè)計(jì)出來的一種存儲(chǔ)結(jié)構(gòu)。本次要做的哈夫曼編碼/譯碼器的主要功能是：運(yùn)用二叉樹來設(shè)計(jì)二進(jìn)制的前綴編碼。若給一個(gè)文件，先統(tǒng)計(jì)文件中每個(gè)字符出現(xiàn)的頻數(shù)，即作為此字符的權(quán)值，然后將里面的字符編碼成相應(yīng)的哈夫曼編碼；反之，根據(jù)哈夫曼譯碼原理把所給二進(jìn)制數(shù)編譯成對(duì)應(yīng)的字符串。2.2需求分析2.2.1程序的基本功能本程序可以對(duì)任何大小的字符型文件進(jìn)行Huffman編碼，生成一個(gè)編碼文件。并可以在程序運(yùn)行結(jié)束后的任意時(shí)間對(duì)它解碼還原生成字符文件。即：先對(duì)一條電文進(jìn)行輸入，并實(shí)現(xiàn)Huffman編碼，然后對(duì)Huffman編碼生成的代碼串進(jìn)行譯碼，最后輸出電文數(shù)字2.2.2輸入/輸出形式當(dāng)進(jìn)行編碼時(shí)輸入為原字符文件文件名，當(dāng)程序運(yùn)行編碼完成之后輸入編碼文件名（默認(rèn)名為code.dll）。當(dāng)進(jìn)行譯碼時(shí)輸入為編碼文件名（默認(rèn)名為code.dll），從文件中讀取Huffman編碼樹后輸入字符文件的文件名。2.2.3測(cè)試數(shù)據(jù)要求本程序中測(cè)試數(shù)據(jù)主要為字符型文件。2.3基本要求a.編/譯碼系統(tǒng)應(yīng)具有以下功能：（1）I：初始化（Initialization）。從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹，并將它存于文件hfmTree中。（2）E：編碼（Encoding）。利用已建好的哈夫曼樹（如不在內(nèi)存，則從文件hfmTree中讀入），對(duì)文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。（3）D：譯碼（Decoding）。利用已建好的哈夫曼樹將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中。（4）P：印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個(gè)代碼。同時(shí)將此字符形式的編碼文件寫入文件CodePrin中。（5）T：印哈夫曼樹（Treeprinting）。將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹入表形式或廣義表）顯示在終端上，同時(shí)將此字符形式的哈夫曼樹寫入文件TreePrint中。b.測(cè)試數(shù)據(jù)（1）利用下面這道題中的數(shù)據(jù)調(diào)試程序。某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)八種字符，其概率分別為0.25，0.29，0.07，0.08，0.14，0.23，0.03，0.11，試設(shè)計(jì)哈夫曼編碼。（2）用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立哈夫曼樹，并實(shí)現(xiàn)以下報(bào)文的編碼和譯碼：“THISPROGRAMISMYFAVORITE”。字符空格

A

B

C

D

E

F

G

H

I

J

K

L

M頻度186

64

13

22

32103

21

15

47

57

1

5

32

20字符

N

O

P

Q

R

S

T

U

V

W

X

Y

Z頻度

57

63

15

1

48

51

80

23

8

18

1

16

1三.概要設(shè)計(jì)3.1問題分析哈夫曼樹的定義1、哈夫曼樹節(jié)點(diǎn)的數(shù)據(jù)類型定義為：typedefstruct{HuffmanTreeHT;//引用上一個(gè)數(shù)據(jù)類型char*c;//存放將要建立哈夫曼樹的字符intlongth;//字符的大小，即開始第一步輸入的一個(gè)整數(shù)HuffmanCodeHC;//存放對(duì)應(yīng)的哈夫編碼即對(duì)應(yīng)的01代碼}Huffman;2、所實(shí)現(xiàn)的功能函數(shù)如下（1）intmin(HuffmanTreet,inti)接收原始數(shù)據(jù)：從終端讀入字符集大小n，n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹，存于文件hfmtree.dat中。供InitHuffman（）函數(shù)調(diào)用（2）voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn)初始化哈夫曼樹，處理InputHuffman(HuffmanHfm)函數(shù)得到的數(shù)據(jù)，按照哈夫曼規(guī)則建立2叉樹。此函數(shù)塊調(diào)用了Select（）函數(shù)。（3）voidSelect(HuffmanTreeHT,intend,int*s1,int*s2)把輸入的字符按權(quán)值從小到大排序，挑出最小權(quán)值供HuffmanCoding()調(diào)用并且根節(jié)點(diǎn)的權(quán)值等于他的左右孩子的權(quán)值和（4）voidDecoding()編碼功能函數(shù)：利用已建好的哈夫曼樹（如不在內(nèi)存，則從文件hfmtree.dat中讀入）對(duì)文件中的正文進(jìn)行編碼，然后將結(jié)果存入文件codefile.dat中。如果正文中沒有要編碼的字符，則鍵盤讀入并存儲(chǔ)到ToBeTran文件中。讀入ToBeTran中將要編碼的內(nèi)容，將編碼好的哈夫曼編碼存儲(chǔ)到CodeFile中。（5）voidDecoding(HuffmanHfm)譯碼功能函數(shù)：利用已建好的哈夫曼樹將文件codefile.dat中的代碼進(jìn)行譯碼，結(jié)果存入文件textfile.dat中。（6）voidCode_printing()打印功能函數(shù)：輸出哈夫曼樹，字符，權(quán)值，以及它對(duì)應(yīng)的編碼。（7）主函數(shù)的簡(jiǎn)要說明，主函數(shù)主要設(shè)計(jì)的是一個(gè)分支語句，讓用戶挑選所實(shí)現(xiàn)的功能。使用鏈樹存儲(chǔ)，然后分別調(diào)用統(tǒng)計(jì)頻數(shù)函數(shù)，排序函數(shù)，建立哈夫曼函數(shù)，編碼函數(shù)，譯碼函數(shù)來實(shí)現(xiàn)功能。3.2系統(tǒng)結(jié)構(gòu)圖（功能模塊圖）哈夫曼編碼哈夫曼編碼/譯碼器初始化赫夫曼樹編碼譯碼打印編碼打印赫曼樹打印哈夫曼樹四.詳細(xì)設(shè)計(jì)4.1編碼與譯碼創(chuàng)建哈弗曼樹開始開始初始化哈夫曼鏈表且有2n-1個(gè)節(jié)點(diǎn)i=1i<np->weight=*w;p->parent=0;p->lchild=0;p->rchild=0;for(i=n+1;i<=m;++i)HT[s1].parent=HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;結(jié)束編碼開始開始將字符存入哈夫曼編碼結(jié)構(gòu)體數(shù)組的字符單元中if(q==q->Parent->LChild)HC[i].code[--HC[i].start]='0'HC[i].code[--HC[i].start]='1'p=p->nextI=n時(shí)結(jié)束譯碼開始開始Root指向根節(jié)點(diǎn)P!=rootcode[i]=='0'p=p->LChildp=p->Rchildp->LChild==NULL&&p->RChild==NULLs[k++]=str[j]p=root結(jié)束4.2源代碼#include"stdafx.h"#include<iomanip.h>#include<stdio.h>#include<string.h>#defineMAX99charcha[MAX];charhc[MAX-1][MAX];ints1,s2;//設(shè)置全局變量，以便在方法(函數(shù))select中返回兩個(gè)變量typedefstruct//huffman樹存儲(chǔ)結(jié)構(gòu){unsignedintweight;//權(quán)值intlchild,rchild,parent;}huftree;voidselect(huftreetree[],intk)//找尋parent為0,權(quán)最小的兩個(gè)節(jié)點(diǎn){inti;for(i=1;i<=k&&tree[i].parent!=0;i++);s1=i;//初始化s1for(i=1;i<=k;i++)if(tree[i].parent==0&&tree[i].weight<tree[s1].weight)s1=i;//把最小值賦給s1for(i=1;i<=k;i++)if(tree[i].parent==0&&i!=s1)break;s2=i;//初始化s2for(i=1;i<=k;i++)if(tree[i].parent==0&&i!=s1&&tree[i].weight<tree[s2].weight)s2=i;//把最小值賦給s2}voidhuffman(huftreetree[],int*w,intn)//生成huffman樹{intm,i;if(n<=1)return;m=2*n-1;for(i=1;i<=n;i++)//給tree中每個(gè)結(jié)點(diǎn)權(quán)值賦值，且分別給左右孩子及雙親初始化{tree[i].weight=w[i];tree[i].parent=0;tree[i].lchild=0;tree[i].rchild=0;}for(i=n+1;i<=m;i++)//給除了葉子結(jié)點(diǎn)下的其它結(jié)點(diǎn)初始化{tree[i].weight=0;tree[i].parent=0;tree[i].lchild=0;tree[i].rchild=0;}for(i=n+1;i<=m;i++)//最終結(jié)果{select(tree,i-1);tree[s1].parent=i;tree[s2].parent=i;tree[i].lchild=s1;tree[i].rchild=s2;tree[i].weight=tree[s1].weight+tree[s2].weight;}}voidhuffmancode(huftreetree[],charcode[],intn)//輸出huffman編碼{intstart,c,i,f;printf("哈夫曼樹：");//輸出hufftreefor(i=1;i<=2*n-1;i++)printf("5d%",i);printf("5d%",tree[i].weight);printf("5d%",tree[i].parent);printf("5d%",tree[i].lchild);printf("5d%",tree[i].rchild);printf("\n");code[n-1]='\0';//printf("哈夫曼編碼:\n");for(i=1;i<=n;i++){start=n-1;for(c=i,f=tree[i].parent;f!=0;c=f,f=tree[f].parent)//輸出huffman編碼{if(tree[f].lchild==c)code[--start]='0';//把編碼存入codeelsecode[--start]='1';}strcpy(hc[i],&code[start]);//把code分別復(fù)制給hcprintf("%s",cha[i]);printf("-->");printf("%s",hc[i]);printf("\n");//分別輸出編碼for是滿足條件進(jìn)入}}voidtohuffmancode(intn)//編碼部分{inti=0,j;charanychar[9999];printf("請(qǐng)輸入你要編碼的字符串:\n");printf(">>>");gets(anychar);printf("編碼為:");for(;anychar[i]!='\0';i++){j=0;for(;anychar[i]!=cha[j]&&j<=n;)j++;if(j<=n)printf("%d",hc[j]);}printf("\n");}voiddecode(charch[],huftreetree[],intn)//譯碼{inti,j,m;charb;m=2*n-1;i=m;printf("請(qǐng)輸入編碼:\n");printf(">>>");scanf("%d",b);printf("譯碼為:");while(b!=10)//遇到回車時(shí)，結(jié)束{if(b=='0')i=tree[i].lchild;elsei=tree[i].rchild;if(tree[i].lchild==0){printf("%d",ch[i]);j=i,i=m;}cin.get(b);}if(tree[j].lchild!=0)printf("\nERROR\n");}voidmain(){inti=0,n=0;int*w,weight[MAX];charcode[MAX];huftreetree[MAX];w=weight;charin;while(in!='5'){printf("哈夫曼編碼\n");printf("1建立初始化哈夫曼樹2輸出哈夫曼編碼3編碼4譯碼5退出\n");printf("請(qǐng)輸入(1--5):");scanf("%d",in);printf("\n");switch(in){case'1':printf("請(qǐng)輸入待編碼字符個(gè)數(shù):");scanf("%d",&n);printf("請(qǐng)輸入字符及對(duì)應(yīng)權(quán)值:");for(i=1;i<=n;i++){printf(">>>");scanf