課程設(shè)計(jì)哈夫曼編碼編程實(shí)現(xiàn)(參考版)
2025-06-21 00:07本頁(yè)面
【正文】 在這個(gè)程序中，本人認(rèn)為用鍵盤(pán)輸入的字符中有一個(gè)字符‘’沒(méi)有納入哈夫曼編碼中，其是還不是完善的。所以，程序的存儲(chǔ)空間最大是（n+1)*9+（2*n1)*17+4*(1+n)+28.編程總結(jié) 該程序能完成從文件中已存字符或從鍵盤(pán)要求輸入的所有字符的統(tǒng)計(jì)，最后完成哈夫曼編碼。每一個(gè)函數(shù)中，調(diào)用局部變量用的存儲(chǔ)空間不會(huì)超出28個(gè)字節(jié)。這些都是根據(jù)它們的結(jié)點(diǎn)類(lèi)型計(jì)算得來(lái)。同時(shí)，還有一個(gè)代表?xiàng)５淖兞?。如輸入n個(gè)字符，對(duì)于承載統(tǒng)計(jì)字符鏈表就要(n+1）*9 個(gè)字節(jié)的存儲(chǔ)空間。用它們分別指向承載統(tǒng)計(jì)字符鏈表與哈夫曼樹(shù)結(jié)點(diǎn)存儲(chǔ)空間。綜合時(shí)間復(fù)雜度分析，該程序的時(shí)間復(fù)雜度為T(mén)(N)=Θ(N)。由于，在N很大情況下，這一部分的賦值運(yùn)算總次數(shù)也就是這部分的時(shí)間的復(fù)雜度為T(mén)(N)=Θ(N).如果，N不是很大，其時(shí)間復(fù)雜度就為：T(N)=Θ(1)；構(gòu)建哈夫曼樹(shù)部分的函數(shù)與哈夫曼編碼讀取的函數(shù)時(shí)間復(fù)雜度分析。在find_record()函數(shù)中要進(jìn)行查找進(jìn)行而進(jìn)行的賦值，這里查找平均的次數(shù)要小于(n1)/2,也就是在find_record函數(shù)中進(jìn)行的賦值的平均次數(shù)要小于N*((n1)/2)。這N個(gè)函數(shù)還要進(jìn)入find_record()函數(shù)中進(jìn)行判斷。 字符由statistics()輸入。其分別是統(tǒng)計(jì)部分的函數(shù)、構(gòu)建哈夫曼樹(shù)部分的函數(shù)與哈夫曼編碼讀取的函數(shù),這里假如輸入的字符個(gè)數(shù)為N,而其中的總不同字符為n.統(tǒng)計(jì)部分的時(shí)間復(fù)雜度分析及該部分要分析函數(shù)是如下函數(shù)。由字符統(tǒng)計(jì)部分的輸入規(guī)模決定。結(jié)束。程序執(zhí)行結(jié)果界面如下：字符輸入界面，字符輸入完，以字符39。（如下）：在程序執(zhí)行的第一界面中選擇第二個(gè)選項(xiàng)。本人認(rèn)為那樣可以使信息在傳輸時(shí)能完整的保存信息開(kāi)始的風(fēng)格。就進(jìn)入結(jié)果界面中，每一個(gè)字符與它的哈夫編碼行等于號(hào)連起來(lái)，指明它的相應(yīng)的哈夫曼編碼。只要number1小于2*。到下一個(gè)函數(shù)去判斷。//如果還有兩個(gè)或兩個(gè)以上結(jié)點(diǎn)無(wú)父結(jié)點(diǎn)記錄，這就說(shuō)明了還要繼續(xù)構(gòu)樹(shù)。//既然pointer2指向的結(jié)點(diǎn)的父結(jié)點(diǎn)了，就記錄下為。//既然pointer1指向的結(jié)點(diǎn)的父結(jié)點(diǎn)了，就記錄下來(lái)。這是指向提貢data數(shù)據(jù)項(xiàng)次之的那個(gè)結(jié)點(diǎn)。pointerright_child=sec。//指出樹(shù)的新結(jié)點(diǎn)的左子結(jié)點(diǎn)所在的位置。再重復(fù)如上的操作，直到最后的樹(shù)的建成。因?yàn)楣蚵鼧?gòu)樹(shù)中樹(shù)從葉子結(jié)點(diǎn)開(kāi)始建立。//在這里pointer是出了查找范圍的，在范圍外其指向的結(jié)點(diǎn)是待錄入數(shù)據(jù)的結(jié)點(diǎn)于是向這個(gè)結(jié)點(diǎn)錄入數(shù)據(jù)。 } } pointer++。 } else { pointer2=pointer。 pointer1=pointer。 { if(pointerdatapointer1data) { sec=min。否則，就用pointer2來(lái)指向它。(pointerdatapointer2data))//如果訪問(wèn)的結(jié)點(diǎn)無(wú)父結(jié)點(diǎn)記錄，又結(jié)點(diǎn)的data數(shù)據(jù)比pointer2指向的結(jié)點(diǎn)的data數(shù)據(jù)項(xiàng)小。 if(pointerparent==1amp。 { m=pointerhead+1。inumbermaximum。 } else { maximum=min。 } } } pointer++。 { sec=pointerhead+1。 min=pointerhead+1。 pointer2=pointer1。 { if(pointer1datapointerdata)//如果這個(gè)結(jié)點(diǎn)的data數(shù)據(jù)項(xiàng)與第一個(gè)結(jié)點(diǎn)的data數(shù)據(jù)項(xiàng)要小，就用pointer1指向這個(gè)數(shù)據(jù)項(xiàng)，而pointer2指向第一個(gè)。amp。 pointer1=pointer。就第一個(gè)用pointer1來(lái)指向，與min記錄位置。amp。39。它們的數(shù)據(jù)項(xiàng)ch。也就是說(shuō)要pointer1與pointer2都要有指向，前兩個(gè)結(jié)點(diǎn)找出。其中pointer1指向data數(shù)據(jù)項(xiàng)是最小的那個(gè)結(jié)點(diǎn)。amp。申明maximun,是為的存min與sec中的最大的值。定義sec用來(lái)指出pointer2指向的結(jié)點(diǎn)在存儲(chǔ)空間的位置。//定義min用來(lái)指出pointer1指向的結(jié)點(diǎn)在存儲(chǔ)空間的位置。data是記錄字符的權(quán)重，也就是由統(tǒng)計(jì)部分統(tǒng)計(jì)出的相應(yīng)字符在輸入的字符集中的頻數(shù)。struct huffman_number_node *pointer=head,*pointer1,*pointer2。}void creat_huffman_tree(int number,int n)//構(gòu)造哈夫曼樹(shù)。 head0frequency=0。 head0ch=39。}void initialization_of_head(void)//初始化一個(gè)以后用于字符輸入的鏈表頭結(jié)點(diǎn),給它空間。 while((ch=())!=EOF) particular_recording(ch)。 exit(0)。{ ifstream infile(,ios::in)。//深入進(jìn)入統(tǒng)計(jì)。為止。)//從輸入流中斷獲取字符，直到碰到字符39。 while((ch=())!=39。39。{ char ch。//如果在承載字符的鏈表中沒(méi)那個(gè)字符，就向那個(gè)鏈表插入一個(gè)結(jié)點(diǎn)來(lái)記錄那個(gè)字符。退回調(diào)用函數(shù)。{if(find_record(ch)==true)。//把這個(gè)表尾的結(jié)點(diǎn)的指針域賦為NULL，用于以后的判斷。//同時(shí)，記錄這個(gè)字符的個(gè)數(shù)以有了一個(gè)。
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1