1、數(shù)據(jù)結(jié)構(gòu)與算法分析課程設(shè)計(jì)報(bào)告課題名稱：壓縮器/解壓器課題負(fù)責(zé)人名（學(xué)號）:王明星（E10714050）指導(dǎo)教師：王愛平成績：意見：目錄第一章 需求分析*3第二章 概要設(shè)計(jì)*35第三章 詳細(xì)設(shè)計(jì)*516第四章 運(yùn)行結(jié)果及其分析*1618第五章 用戶手冊*18第六章 程序附錄*18第七章 課程設(shè)計(jì)總結(jié)*18參考文獻(xiàn)*18壓縮器/解壓器學(xué)生：王明星 指導(dǎo)老師：王愛平【摘要】：在現(xiàn)代信息社會(huì)發(fā)展到今天這種程度的時(shí)候，網(wǎng)絡(luò)的出現(xiàn)帶給人們生活中極大的方便，但隨之而來的是信息量的增大，這就要對之進(jìn)行處理，使之能夠便于存儲，這就要壓縮器和解壓器的幫忙了，用壓縮器獎(jiǎng)大的文件壓縮為較小的文件后，存儲起來，要用的

2、時(shí)候，用解壓器將之還原，就可以使用了。這就是壓縮器和解壓器的作用了。【題目】 為了節(jié)省存儲空間,常常需要把文本文件采用壓縮編碼方式存儲。例如: 一個(gè)包含 1000個(gè)X的字符串和2000個(gè)Y的字符串的文本文件在不壓縮時(shí)占用的空間為3002字節(jié)(每個(gè)X或每個(gè)Y占用一個(gè)字節(jié),兩個(gè)字節(jié)代表文件用來表示字符串的結(jié)尾.同樣是這個(gè)文件,采用游程長度編碼,可以存儲為字符串1000X2000Y,僅為10個(gè)字符.占用12個(gè)字節(jié),若采用2進(jìn)制表示,則更加節(jié)省空間,上例中的字符串用8個(gè)字節(jié)來存儲,當(dāng)要讀取編碼文件時(shí),需要對其解碼,由壓縮器對其編碼,解壓器對其解碼.要求:用游程-長度編碼+LZW編碼實(shí)現(xiàn)第一章 需求分析

3、1、 本演示程序中，文本集合元素限定為a,b,c,z,0,1,2,9時(shí)，用實(shí)例檢測壓縮器和解壓器的運(yùn)作，輸入的為本文文件（.txt），輸出的為一種自定義的文件（.nz），測試壓縮器解壓器會(huì)不會(huì)出現(xiàn)抖動(dòng)，如果出現(xiàn)，需選取合適的集合來適應(yīng)一般的情況。2、 演示程序以用戶和計(jì)算機(jī)對話得以實(shí)現(xiàn)，即在計(jì)算機(jī)終端顯示“提示信息”后，新建個(gè)相應(yīng)要壓縮的.TXT文件，輸入該文件的文件名，程序就會(huì)將改文件壓縮為.nz的文件，后解壓為.txt文件。3、 測試數(shù)據(jù)測試數(shù)據(jù)為文本字符集合a,b,c,z,0,1,2,9，來測試壓縮器和解壓器。第二章 概要設(shè)計(jì)要實(shí)現(xiàn)上述功能，了解游程長度編碼和LZW編碼的基本原理及基本算

4、法。(1、游程長度編碼游程長度編碼是柵格數(shù)據(jù)壓縮的重要編碼方法，它的基本思路是：對于一幅柵格圖像，常常有行(或列方向上相鄰的若干點(diǎn)具有相同的屬性代碼，因而可采取某種方法壓縮那些重復(fù)的記錄內(nèi)容。其編碼方案是，只在各行(或列數(shù)據(jù)的代碼發(fā)生變化時(shí)依次記錄該代碼以及相同代碼重復(fù)的個(gè)數(shù)，從而實(shí)現(xiàn)數(shù)據(jù)的壓縮。例如對圖1所示的柵格數(shù)據(jù)，可沿行方向進(jìn)行如下游程長度編碼：(9,4,(0,4,(9,3,(0,5,(0,1(9,2,(0,1,(7,2,(0,2,(0,4,(7,2,(0,2,(0,4,(7,4,(0,4,(7,4 ,(0,4,(7,4 ,(0,4,(7,4游程長度編碼對圖3-6(a只用了40個(gè)整數(shù)就

5、可以表示，而如果用前述的直接編碼卻需要64個(gè)整數(shù)表示，可見游程長度編碼壓縮數(shù)據(jù)是十分有效又簡便的。事實(shí)上，壓縮比的大小是與圖的復(fù)雜程度成反比的，在變化多的部分，游程數(shù)就多，變化少的部分游程數(shù)就少，圖件越簡單，壓縮效率就越高。游程長度編碼在柵格加密時(shí)，數(shù)據(jù)量沒有明顯增加，壓縮效率較高，且易于檢索，疊加合并等操作，運(yùn)算簡單，適用于機(jī)器存貯容量小，數(shù)據(jù)需大量壓縮，而又要避免復(fù)雜的編碼解碼運(yùn)算增加處理和操作時(shí)間的情況。font id="zoom" class="zoom"游程長度RL (RunLength，簡稱游程或游長，指的是由字符(或信號取樣值構(gòu)成的數(shù)據(jù)流中

6、各個(gè)字符重復(fù)出現(xiàn)而形成的字符的長度如果給出了形成申的字符，申的長度及申的位置，就能恢復(fù)出原來的數(shù)據(jù)流，游程長度編碼(RLC就是用二進(jìn)制碼字給出這些信息的一類方法。游程長度編碼的主要思想是將一個(gè)相同值的連續(xù)申用其值和申長(重復(fù)的個(gè)數(shù)的數(shù)對二元組來替代例如，在圖像編碼中，可以定義沿特定方向上具有相同灰度值的相鄰像素為一輪，其延續(xù)的長度稱之為延續(xù)的行程，即游程游程終點(diǎn)位置由前一游程終點(diǎn)的相對距離確定，這樣就可以由灰度游程串來表示圖像數(shù)據(jù)例如，若沿水平方向有一申M 個(gè)像素具有相同的灰度N，則按游程長度編碼后，只傳遞兩個(gè)值(N，M 就可以代替這M個(gè)像素的M個(gè)灰度值N。簡單來說，游程長度編碼的主要任務(wù)是統(tǒng)

7、計(jì)連續(xù)相同字符的個(gè)數(shù)，解碼時(shí)要根據(jù)字符及連續(xù)相同字符的個(gè)數(shù)，恢復(fù)原來的數(shù)據(jù)在多媒體信息量激增、網(wǎng)絡(luò)特性和速度都飛速提高的今天，游程長度編碼是一種十分簡單的壓縮方法，編碼解碼的速度也非常快，可廣泛應(yīng)用于多媒體信息的存儲，傳輸。 圖1（2）、LZW壓縮/解壓算法由Lempel、Ziv和Welch這三位科學(xué)家所開發(fā)的技術(shù)。該方法把文本的字符串映射為編碼，首先，為該文本中所有可能出現(xiàn)的字母分別分配一個(gè)代碼。例如：要壓縮的對象是aaabbbbbbbaabaaba，由a和b組成。為a分配代碼0,為b分配代碼1。字符串和編碼的關(guān)系被存儲在字典中。 字典如下： Key 0 1 2 3 4 5 6 7 Code

8、 A b Aa aab bb bbb bbba aaba LZW壓縮器不斷的在輸入文件中尋找在字典中出現(xiàn)的最長的前綴p,并輸出其相應(yīng)的代碼。若輸入文件的下一個(gè)字符為c，則為pc分配下一個(gè)代碼，并插入字典，這種策略稱為LZW規(guī)則。相反，在解壓時(shí)，編碼表由壓縮文件重新構(gòu)造，LZW原則使這種重建成為可能。 如上例子，壓縮時(shí)，文件中第一個(gè)在字典中出現(xiàn)的最長前綴是a, 輸出其編碼0,然后為字符串a(chǎn)a分配代碼2，并插入到字典中。余下的字符串在字典中出現(xiàn)的最長前綴是aa,輸出aa的對應(yīng)代碼2，同時(shí)為字符串a(chǎn)ab分配代碼3并將其插入到字典中。依次類推，由此，輸出0214537 解壓時(shí)，要輸入代碼，然后用代碼所

9、表示的文本來替換這些代碼。代碼到文本的映射可按下面的方法重建：首先把分配給單一字母的代碼插入到字典中。象前面一樣，字典的入口為key-code對。然而此時(shí)是根據(jù)給定的代碼（key）去尋找相應(yīng)的入口（而不是根據(jù)文本Code）。壓縮文件中的第一個(gè)代碼對應(yīng)于單一的字母，因此可以由該字母代替。對于壓縮文件中的其他代碼p,要考慮兩種情況：1）在字典中；2）不在字典中。 在1）情況下，找到p對應(yīng)的文本text(p輸出。并且，根據(jù)壓縮原理可知，若在壓縮文件中代碼q寫在p之前且text(q是與q對應(yīng)的文本，則壓縮器會(huì)為文本text(q（其后緊跟fc(p，text(p的第一個(gè)字符）分配一新代碼。因此在字典中插入

10、序偶（下一個(gè)代碼，text(qfc(p）。 情況2）時(shí)，只有在當(dāng)前文本段形如text(qtext(qfc(q且text(p=text(qfc(q時(shí)才會(huì)發(fā)生。相應(yīng)的壓縮文件段是qp。在壓縮過程中，為text(qfc(q分配的代碼為p。在解壓過程中，在用text(q代替q后，又遇到代碼p。然而，此時(shí)字典中沒有與p對應(yīng)的文本。因?yàn)檫@種情況只在解壓文本段為text(ptext(qfc(q時(shí)才發(fā)生，因此可以對p解碼。當(dāng)遇到一個(gè)沒有定義代碼文本對的代碼p時(shí)，p對應(yīng)的文本為text(qfc(q，其中q為p前面的代碼。 如上例子：首先，初始化字典，在其中插入(0,a,(1,b。壓縮的第一個(gè)代碼為0,則用a代替

11、之。下一個(gè)代碼2未定義，因?yàn)榍耙粋€(gè)代碼為0，且text(0=a,fc(0=a,則text(2=text(0fc(0=aa。因此用aa代替2,并把(2,aa插入字典中。下個(gè)代碼1由b來替換，并把(3,text(2fc(1=(3,aab插入字典中。依次類推，得解壓結(jié)果。第三章 詳細(xì)設(shè)計(jì)（一）、游程長度編碼一）、壓縮程序數(shù)據(jù)結(jié)構(gòu)如下：int count,i;char com,cum;char strs100,str10; FILE *fp,*fp1;代碼如下：#include #include main( int count,i;char com,cum;char strs100,str10; FI

12、LE *fp,*fp1;printf("請輸入源數(shù)據(jù)文件地址(如: D:wmx.txt : "scanf("%s",strs;fp = fopen(strs,"r"printf("請輸入壓縮數(shù)據(jù)文件名(如: D:wmx.txt : "scanf("%s",strs;fp1 = fopen(strs,"w" printf("n 壓縮中"printf("n"com = '?'cum = ''while(!fe

13、of(fp strs0 = fgetc(fp;count = 1;while(1 strs1 = fgetc(fp;if(strs1 = strs0count+;elseif(count > 3fputc(com,fp1;fputc(cum,fp1;fputc(strs0,fp1;itoa(count,str,10;fwrite(str,sizeof(str-1,1,fp1;elsefor(i = 0;i < count;i+fputc(strs0,fp1;fputc(strs1,fp1;if(feof(fp|(strs1 != strs0break;fclose(fp;fclos

14、e(fp1;printf("n 壓縮完成n"return 0;二）、解壓部分?jǐn)?shù)據(jù)結(jié)構(gòu)：int count,i,j;/*計(jì)數(shù)器*/FILE *fp,*fp1;char ch;char strsM,strM; 具體代碼如下：#include #include #include #define M 100main( int count,i,j;/*計(jì)數(shù)器*/FILE *fp,*fp1;char ch;char strsM,strM; printf("請輸入源數(shù)據(jù)文件地址(如: D:wmx.r : "scanf("%s",strs;fp =

15、fopen(strs,"r"printf("請輸入解壓壓數(shù)據(jù)文件名(如: D:wmx.txt : "scanf("%s",strs;fp1 = fopen(strs,"w"printf("n 解壓中"printf("n"while(!feof(fp strs0 = 0;strs1 = 0;strs0 = fgetc(fp;if(strs0 = '?'strs1 = fgetc(fp;if(strs1 = ''strs2 = fgetc(fp;i

16、 = 0;ch = fgetc(fp;while(ch != '0'stri = ch;ch = fgetc(fp;i+;stri = '0'j = strlen(str;count = 0;for(i = 0;i < j;i+count += (stri - '0'*pow(10,j-i-1;for(i = 0;i < count;i+fputc(strs2,fp1;elsefputc(strs0,fp1;fputc(strs1,fp1;elsefputc(strs0,fp1; fclose(fp;fclose(fp1;printf

17、("n解壓完成!"return 0;（二）、LZW編碼一）、本程序主要包含3個(gè)模塊：1）、主程序模塊Main函數(shù)，主要實(shí)現(xiàn)數(shù)據(jù)的輸入，壓縮和解壓的功能。2）、壓縮程序模塊這個(gè)模塊主要是壓縮函數(shù)的代碼，實(shí)現(xiàn)壓縮功能。3）、解壓程序模塊 同理，這個(gè)模塊主要是解壓程序的代碼，來實(shí)現(xiàn)解壓功能。二）、詳細(xì)程序如下#include #include #define BITS 12 /* 定義字節(jié)數(shù)為12*/#define HASHING_SHIFT BITS-8 /* 或者13，14，看輸入的文本情況. */#define MAX_VALUE (1 << BITS - 1

18、/*、如果字節(jié)數(shù)為14，DOS系統(tǒng)需要編輯代碼在大點(diǎn)的模塊 */#define MAX_CODE MAX_VALUE - 1 #if BITS = 14#define TABLE_SIZE 18041 /* 編碼表要比2的位數(shù)次方要大點(diǎn) */#endif #if BITS = 13 #define TABLE_SIZE 9029#endif#if BITS <= 12#define TABLE_SIZE 5021#endif/void *malloc(;int *code_value; /* 定義代碼值數(shù)組 */unsigned int *prefix_code; /* 這個(gè)數(shù)組存放前綴

19、的代碼 */unsigned char *append_character; /*這個(gè)數(shù)組存放附加代碼 */unsigned char decode_stack4000; /* 這個(gè)數(shù)組存放已編碼的字符串 */* 這個(gè)程序從命令行輸入文件名. 然后進(jìn)行壓縮，* 然后壓縮為test.lzw的文件. ，然后再解壓為test.txt,這個(gè)文件是起始文件的副本。*/void strcpy(char *s,char *twhile(*s+=*t+;void compress(FILE *input,FILE *output;int find_match(int hash_prefix,unsigned

20、int hash_character;void expand(FILE *input,FILE *output;unsigned char *decode_string(unsigned char *buffer,unsigned int code;void output_code(FILE *output,unsigned int code;unsigned int input_code(FILE *input;int main(int argc, char *argv/*程序入口，主程序*/FILE *input_file;FILE *output_file;FILE *nz_file;c

21、har input_file_name81;/* 壓縮階段需要3塊緩沖區(qū)*/code_value=(int*malloc(TABLE_SIZE*sizeof(unsigned int;prefix_code=(unsigned int*malloc(TABLE_SIZE*sizeof(unsigned int;append_character=(unsigned char*malloc(TABLE_SIZE*sizeof(unsigned char;if (code_value=NULL | prefix_code=NULL | append_character=NULLprintf(&quo

22、t;Fatal error allocating table space!n"return 0;/exit(;/* 輸入文件名，打開，或者打開已經(jīng)過LZW壓縮的文件*/if (argc>1strcpy(input_file_name,argv1;elseprintf("輸入文件名? "scanf("%s",input_file_name;input_file=fopen(input_file_name,"rb"nz_file=fopen("test.nz","wb"if (inp

23、ut_file=NULL | nz_file=NULLprintf("無法打開文件.n"/exit(;return 0;/* 壓縮文件*/compress(input_file,nz_file;fclose(input_file;fclose(nz_file;free(code_value;/* 解壓的時(shí)候打開壓縮文件*/nz_file=fopen("test.nz","rb"output_file=fopen("test.txt","wb"if (nz_file=NULL | output_f

24、ile=NULLprintf("無法打開文件.n"/exit(;return 0;/* 解壓文件*/ expand(nz_file,output_file;fclose(nz_file;fclose(output_file;free(prefix_code;free(append_character;return 0;/* 這是壓縮程序代碼段*/void compress(FILE *input,FILE *outputunsigned int next_code;unsigned int character;unsigned int string_code;unsigne

25、d int index;int i;next_code=256; /* 下個(gè)代碼就是下個(gè)可用的字符串代碼*/for (i=0;i 壓縮前清除代碼表 */ code_valuei=-1;i=0;printf("壓縮成功 .n"string_code=getc(input; /* 得到首個(gè)代碼值 */* 這是主循環(huán)，這個(gè)循環(huán)執(zhí)行直到所有的可能的代碼都被定義了*/while (character=getc(input != (unsignedEOFif(+i=1000 i=0; printf("*"index=find_match(string_code,ch

26、aracter;/* 如果輸入的字符在代碼表里，取出代碼，如果不在，將這個(gè)字符添加新的代碼*/if(code_valueindex!=-1 string_code=code_valueindex; else if (next_code <= MAX_CODEcode_valueindex=next_code+;prefix_codeindex=string_code;append_characterindex=character;output_code(output,string_code; /* 當(dāng)一個(gè)字符串不在代碼表里的時(shí)候，添加了新的代碼后，輸出最后的一個(gè)字符 */string_c

27、ode=character; /* 結(jié)束主循環(huán).*/output_code(output,string_code; /* 輸出最后一個(gè)代碼 */output_code(output,MAX_VALUE; /* 輸出最后一個(gè)緩沖區(qū)代碼 */output_code(output,0; /* 清除輸出緩沖*/printf("n"/*這是例行的散列。它試圖找到一個(gè)匹配的前綴+字符字符串的字符串表。如果它認(rèn)為，該指數(shù)是回來了。如果字符串沒有發(fā)現(xiàn)，第一個(gè)可用的索引是字符串表返回代替。*/int find_match(int hash_prefix,unsigned int hash_c

28、haracterint index;int offset;index = (hash_character << HASHING_SHIFT hash_prefix;if (index = 0offset = 1;elseoffset = TABLE_SIZE - index;while (1if (code_valueindex = -1return(index;if (prefix_codeindex = hash_prefix && append_characterindex = hash_characterreturn(index;index -= offse

29、t;if (index < 0index += TABLE_SIZE;/*這是例行的擴(kuò)大。它的nz格式文件，并擴(kuò)大  它的輸出文件。代碼應(yīng)該是一個(gè)相當(dāng)接近的匹配，以該算法在隨附的代碼段。*/void expand(FILE *input,FILE *outputunsigned int next_code;unsigned int new_code;unsigned int old_code;int character;int counter;unsigned char *string;/char *decode_string(unsigned char *buffe

30、r,unsigned int code;next_code=256; /* 這是下一個(gè)可用的代碼*/counter=0; printf("解壓成功.n"old_code=input_code(input; /* 讀取其中的第一個(gè)代碼，初始化 */character=old_code; /* 字符變量，并把第一 */putc(old_code,output; /* 代碼輸出*/*這是主要的解壓循環(huán)。其內(nèi)容的字符從nz文件  直到看到了特殊代碼用來表明最后一個(gè)數(shù)據(jù)。*/while (new_code=input_code(input != (MAX_VALU

31、Eif (+counter=1000 /* 本節(jié)的代碼打印出*/ counter=0; printf("*"/*此代碼檢查特別管柱+字符+字符串+特征+字符串案件產(chǎn)生一個(gè)未定義的代碼。它處理它的解碼最后的代碼，并增加了單個(gè)字符的結(jié)尾解碼字符串。*/if (new_code>=next_code*decode_stack=character;string=decode_string(decode_stack+1,old_code;/* Otherwise we do a straight decode of the new code.*/elsestring=decod

32、e_string(decode_stack,new_code;/* 解碼輸出字符串順序相反。*/character=*string;while (string >= decode_stackputc(*string-,output;/*如果可能的話，添加一個(gè)新的代碼字符串表。*/if (next_code <= MAX_CODEprefix_codenext_code=old_code;append_characternext_code=character;next_code+;old_code=new_code;printf("n"/* 這只是字符串解碼的字符

33、串表，儲存它在一個(gè)緩沖區(qū)。緩沖區(qū)可以輸出順序相反的解壓文件。*/unsigned char *decode_string(unsigned char *buffer,unsigned int codeint i;i=0;while (code > 255*buffer+ = append_charactercode;code=prefix_codecode;if (i+>=4094printf("Fatal error during code expansion.n"/ exit(;return NULL;*buffer=code;return(buffer;/

34、* 以下兩個(gè)函數(shù)用于輸出變長守則。它們是嚴(yán)格的書面明確，而不是特別是有效的。*/unsigned int input_code(FILE *inputunsigned int return_value;static int input_bit_count=0;static unsigned long input_bit_buffer=0L;while (input_bit_count <= 24input_bit_buffer |= (unsigned long getc(input << (24-input_bit_count;input_bit_count += 8;return_value=input_bit_buffer >&