大數(shù)據(jù)結(jié)構(gòu)哈夫曼實(shí)驗(yàn)C語言

實(shí)用標(biāo)準(zhǔn)文案《用哈夫曼編碼實(shí)現(xiàn)文件壓縮》實(shí) 驗(yàn) 報(bào) 告課程名稱 數(shù)據(jù)結(jié)構(gòu)B實(shí)驗(yàn)學(xué)期 2012 至2013 學(xué)年 第 一 學(xué)期學(xué)生所在系部 計(jì)算機(jī)學(xué)院年級(jí) 2011 專業(yè)班級(jí) 信管B11-2學(xué)生姓名 學(xué)號(hào)精彩文檔實(shí)用標(biāo)準(zhǔn)文案任課教師 蘭蕓實(shí)驗(yàn)成績(jī)精彩文檔實(shí)用標(biāo)準(zhǔn)文案一、實(shí)驗(yàn)題目：用哈夫曼編碼實(shí)現(xiàn)文件壓縮二、實(shí)驗(yàn)?zāi)康模?、了解文件的概念。2、掌握線性鏈表的插入、刪除等算法。3、掌握Huffman 樹的概念及構(gòu)造方法。4、掌握二叉樹的存儲(chǔ)結(jié)構(gòu)及遍歷算法。5、利用Huffman 樹及Huffman 編碼，掌握實(shí)現(xiàn)文件壓縮的一般原理。三、實(shí)驗(yàn)設(shè)備與環(huán)境：微型計(jì)算機(jī)、Windows 系列操作系統(tǒng) 、VisualC++6.0 軟件四、實(shí)驗(yàn)內(nèi)容：輸入一些字符，即赫夫曼樹結(jié)點(diǎn)的權(quán)值，創(chuàng)建 Haffman 樹，再將各字符對(duì)應(yīng)的哈夫曼編碼寫入文件中。五、概要設(shè)計(jì)：1）構(gòu)造Hufffman樹—Hufffman算法2）Huffman編碼：數(shù)據(jù)通信用的二進(jìn)制編碼編碼：根據(jù)字符出現(xiàn)頻率構(gòu)造 Huffman 樹，然后將樹中結(jié)點(diǎn)引向其左孩子的分支標(biāo)“0”，引向其右孩子的分支標(biāo)“ 1”；每個(gè)字符的編碼即為從根到每個(gè)葉子的路徑上得到的 0、1序列。3）二叉樹的存儲(chǔ)結(jié)構(gòu)typedefstructnode{datatypedata;精彩文檔實(shí)用標(biāo)準(zhǔn)文案structnode*lchild,*rchild;}BinTree;六、詳細(xì)設(shè)計(jì)：1、構(gòu)造Huffman 樹步驟：Ⅰ、根據(jù)給定的 n個(gè)權(quán)值{w1,w2,??wn}，構(gòu)造n棵只有根結(jié)點(diǎn)的二叉樹，令起權(quán)值為wj。Ⅱ、在森林中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作左右子樹，構(gòu)造一棵新的二叉樹，置新二叉樹根結(jié)點(diǎn)權(quán)值為其左右子樹根結(jié)點(diǎn)權(quán)值之和。Ⅲ、在森林中刪除這兩棵樹，同時(shí)將新得到的二叉樹加入森林中。Ⅳ、重復(fù)上述兩步，直到只含一棵樹為止，這棵樹即哈夫曼樹。2、利用Select函數(shù)選出權(quán)值最小的兩個(gè)結(jié)點(diǎn)。3、利用CreatHT函數(shù)構(gòu)的建赫夫曼樹先將所有的葉子結(jié)點(diǎn)的父結(jié)點(diǎn)和左右孩子結(jié)點(diǎn)均賦值為 0，并將輸入的權(quán)值依次賦給葉子結(jié)點(diǎn)的 weight 域。從樹的最底部開始循環(huán) Select函數(shù)共n-1次，將最小權(quán)的結(jié)點(diǎn)賦給中間結(jié)點(diǎn)的左孩子，將次小權(quán)的結(jié)點(diǎn)賦給中間結(jié)點(diǎn)的右孩子。4、從葉子到根逆向求每個(gè)字符的赫夫曼編碼，開辟字符串空間，從葉子結(jié)點(diǎn)開始逆向?qū)ふ颐總€(gè)中間結(jié)點(diǎn)的左右孩子，開辟字符空間為左孩子賦值為字符 0，為右孩子賦值為字符 1，運(yùn)用strcpy 函數(shù)將所得字符依次從右到左連接于所開辟的字符串空間，所得字符串即為赫夫曼編碼。#include<stdio.h>#include<string.h>精彩文檔實(shí)用標(biāo)準(zhǔn)文案#include<stdlib.h>#include<conio.h>#include<time.h>structnode{longweight;//權(quán)值unsignedcharch;//字符intparent,lchild,rchild;charcode[256];//編碼的位數(shù)最多為256位intCodeLength;//編碼長(zhǎng)度}hfmnode[512];voidcompress();//主函數(shù)voidmain(){intchoice;printf("歡迎使用赫夫曼編碼壓縮文件！請(qǐng)選擇 1 or 2：\n");printf("1. 壓縮文件\n");printf("2. 退出！\n");scanf("%d",&choice);if(choice==1)compress();精彩文檔實(shí)用標(biāo)準(zhǔn)文案elseif(choice==2)return;elseprintf(" 輸入錯(cuò)誤！");}壓縮函數(shù)voidcompress(){inti,j;charinfile[20],outfile[20];FILE *ifp,*ofp;unsignedcharc;//longFileLength,filelength=0;intn,m;// 葉子數(shù)和結(jié)點(diǎn)數(shù)ints1,s2;// 權(quán)值最小的兩個(gè)結(jié)點(diǎn)的標(biāo)號(hào)charcodes[256];longsumlength=0;floatrate,speed;intcount=0;clock_tstart1,start2,finish1,finish2;double duration1,duration2;voide