數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)總結(jié)報(bào)告

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

一、調(diào)試過(guò)程中碰到哪些問(wèn)題？

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

因?yàn)橐婚_(kāi)頭設(shè)計(jì)的廣義表的字符串表示沒(méi)有思量清楚，處理惟獨(dú)一個(gè)孩子的節(jié)點(diǎn)時(shí)發(fā)生了混亂。調(diào)試之初不以為是設(shè)計(jì)的問(wèn)題，從而在代碼上花了不少時(shí)光調(diào)試。

目前的設(shè)計(jì)是：

Tree=Identifier(Node,Node)

Node=Identifier|()|Tree

Identifier=ASCIICharacter

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

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

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

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

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

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

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

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

解決計(jì)劃：

①在壓縮文件頭部寫入源文件的總長(zhǎng)度（字節(jié)數(shù)）。需要四個(gè)字節(jié)來(lái)存儲(chǔ)這個(gè)信息（假定文件長(zhǎng)度不超過(guò)4GB）。

②增強(qiáng)第257個(gè)字符（在一個(gè)字節(jié)的0~255之外）用于EOF。對(duì)于較長(zhǎng)的文件，

會(huì)造成較大的損耗。

③在壓縮文件頭寫入源文件的總長(zhǎng)度%256的值，需要一個(gè)字節(jié)。因?yàn)樽詈笠粋€(gè)字節(jié)存在或不存在會(huì)影響文件總長(zhǎng)%256的值，因此可以按照這個(gè)值推斷囫圇壓縮文件的最后一字節(jié)末尾的0是否在源文件中存在。

（2）壓縮程序的效率問(wèn)題。

在編寫壓縮解壓程序時(shí)

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

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

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

這樣一來(lái)，每寫一位二進(jìn)制位，就要在內(nèi)部舉行兩次函數(shù)調(diào)用。假如將這些代碼合并起來(lái)，再針對(duì)位運(yùn)算舉行一些優(yōu)化，明顯不利于代碼的可讀性，但對(duì)程序的執(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)研常用的壓縮算法，對(duì)這些算法舉行比較分析

（一）無(wú)損壓縮算法

①RLE

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

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

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

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

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

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

②Huffman

哈夫曼編碼是無(wú)損壓縮當(dāng)中最好的辦法。它使用預(yù)先二進(jìn)制描述來(lái)替換每個(gè)符號(hào)，長(zhǎng)度由特別符號(hào)浮現(xiàn)的頻率打算。常見(jiàn)的符號(hào)需要很少的位來(lái)表示，而不常見(jiàn)的符號(hào)需要無(wú)數(shù)為來(lái)表示。

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

③Rice

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

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

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