數(shù)據(jù)結(jié)構實驗總結(jié)報告

千里之行，始于足下讓知識帶有溫度。第2頁/共2頁精品文檔推薦數(shù)據(jù)結(jié)構實驗總結(jié)報告數(shù)據(jù)結(jié)構試驗總結(jié)報告

一、調(diào)試過程中碰到哪些問題？

（1）在二叉樹的調(diào)試中，從廣義表生成二叉樹的模塊花了較多時光調(diào)試。

因為一開頭設計的廣義表的字符串表示沒有思量清楚，處理惟獨一個孩子的節(jié)點時發(fā)生了混亂。調(diào)試之初不以為是設計的問題，從而在代碼上花了不少時光調(diào)試。

目前的設計是：

Tree=Identifier(Node,Node)

Node=Identifier|()|Tree

Identifier=ASCIICharacter

例子：a(b((),f),c(d,e))

這樣便消退了歧義，保證惟獨一個孩子的節(jié)點和葉節(jié)點的處理中不存在問題。

（2）Huffman樹的調(diào)試花了較長時光。Huffman編碼本身并不難處理，棘手的是輸入輸出。①Huffman編碼后的文件是按位存儲的，因此需要位運算。

②文件結(jié)尾要刷新緩沖區(qū)，這里簡單引發(fā)邊界錯誤。

在實際編程時，首先編寫了屏幕輸入輸出（用0、1表示二進制位）的版本，然后再加入二進制文件的讀寫模塊。主要調(diào)試時光在后者。

二、要讓演示版壓縮程序具有有用性，哪些地方有待改進？

（1）壓縮文件的最后一字節(jié)問題。

壓縮文件的最后一字節(jié)不一定對齊到字節(jié)邊界，因此可能有幾個多余的0，而這些多余的0可能恰好構成一個Huffman編碼。解碼程序無法獲知這個編碼是否屬于源文件的一部分。因此有的文件解壓后末尾可能浮現(xiàn)一個多余的字節(jié)。

解決計劃：

①在壓縮文件頭部寫入源文件的總長度（字節(jié)數(shù)）。需要四個字節(jié)來存儲這個信息（假定文件長度不超過4GB）。

②增強第257個字符（在一個字節(jié)的0~255之外）用于EOF。對于較長的文件，

會造成較大的損耗。

③在壓縮文件頭寫入源文件的總長度%256的值，需要一個字節(jié)。因為最后一個字節(jié)存在或不存在會影響文件總長%256的值，因此可以按照這個值推斷囫圇壓縮文件的最后一字節(jié)末尾的0是否在源文件中存在。

（2）壓縮程序的效率問題。

在編寫壓縮解壓程序時

①編寫了屏幕輸入輸出的版本

②將輸入輸出語句用位運算封裝成一次一個字節(jié)的文件輸入輸出版本

③為提高輸入輸出效率，削減系統(tǒng)調(diào)用次數(shù)，增強了8KB的輸入輸出緩存窗口

這樣一來，每寫一位二進制位，就要在內(nèi)部舉行兩次函數(shù)調(diào)用。假如將這些代碼合并起來，再針對位運算舉行一些優(yōu)化，明顯不利于代碼的可讀性，但對程序的執(zhí)行速度將有一定提高。

（3）程序界面越發(fā)人性化。

HuffmanTreeDemo(C)2022-12-16boj

Usage:huffman[-cfile][-ufile]output_file

-cCompressfile.e.g.huffman-ctest.txttest.huff

-uUncompressfile.e.g.huffman-utest.hufftest.txt

目前的程序提醒如上所示。假如要求有用性，可以考慮加入其他人性化的功能。

三、調(diào)研常用的壓縮算法，對這些算法舉行比較分析

（一）無損壓縮算法

①RLE

RLE又叫RunLengthEncoding，是一個針對無損壓縮的十分容易的算法。它用重復字節(jié)和重復的次數(shù)來容易描述來代替重復的字節(jié)。盡管容易并且對于通常的壓縮十分低效，但它有的時候卻十分實用（例如，JPEG就使用它）。

變體1：重復次數(shù)+字符

文本字符串：AAABBBCCCCDDDD，編碼后得到：3A3B4C4D。

變體2：特別字符+重復次數(shù)+字符

文本字符串：AAAAABCCCCBCCC，編碼后得到：BB5ABB4CBB3C。編碼串的最開頭說明特別字符B，以后B后面跟著的數(shù)字就表示出重復的次數(shù)。

變體3：把文本每個字節(jié)分組成塊，每個字符最多重復127次。每個塊以一個特別字節(jié)開始。那個特別字節(jié)的第7位假如被置位，那么剩下的7位數(shù)值就是后面的字符的重復次數(shù)。假如第7位沒有被置位，那么剩下7位就是后面沒有被壓縮的字符的數(shù)量。例如：文本字符串：AAAAABCDEFFF。編碼后得到：85A4BCDE83F（85H=10000101B、4H=00000100B、83H=10000011B）

②Huffman

哈夫曼編碼是無損壓縮當中最好的辦法。它使用預先二進制描述來替換每個符號，長度由特別符號浮現(xiàn)的頻率打算。常見的符號需要很少的位來表示，而不常見的符號需要無數(shù)為來表示。

哈夫曼算法在轉(zhuǎn)變?nèi)魏畏柖M制編碼引起少量密集表現(xiàn)方面是最佳的。然而，它并不處理符號的挨次和重復或序號的序列。

③Rice

Rice編碼背后的基本思想是盡可能的用較少的位來存儲多個字（正像使用哈夫曼編碼一樣）。實際上，Rice類似靜態(tài)的哈夫曼編碼（例如，編碼不是由實際數(shù)據(jù)內(nèi)容的統(tǒng)計信息打算，而是由小的值比高的值常見的假定打算）。編碼十分容易：將值X用X個‘1’位之后跟一個0位來表示。

對于由大word（例如：16或32位）組成的數(shù)據(jù)和教低的數(shù)據(jù)值，Rice編碼能夠獲得較好的壓縮比。音頻和高動態(tài)變化的圖像都是這種類型的數(shù)據(jù)，它們被預處理過（例如delta相鄰的采樣）。

盡管哈夫曼編碼處理這種數(shù)據(jù)是最優(yōu)的，卻因為幾個緣由而不適合處理這種數(shù)據(jù)（例如：32位大小要求16GB的柱狀圖緩沖