課程設(shè)計(jì)哈夫曼編碼編程實(shí)現(xiàn)(存儲(chǔ)版)
【正文】 pointer=pointernext。//把這個(gè)表尾的結(jié)點(diǎn)的指針域賦為NULL，用于以后的判斷。{ char ch。為止。 while((ch=())!=EOF) particular_recording(ch)。}void creat_huffman_tree(int number,int n)//構(gòu)造哈夫曼樹(shù)。定義sec用來(lái)指出pointer2指向的結(jié)點(diǎn)在存儲(chǔ)空間的位置。也就是說(shuō)要pointer1與pointer2都要有指向，前兩個(gè)結(jié)點(diǎn)找出。就第一個(gè)用pointer1來(lái)指向，與min記錄位置。 pointer2=pointer1。 } else { maximum=min。(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)小。 } else { pointer2=pointer。再重復(fù)如上的操作，直到最后的樹(shù)的建成。//既然pointer1指向的結(jié)點(diǎn)的父結(jié)點(diǎn)了，就記錄下來(lái)。只要number1小于2*。程序執(zhí)行結(jié)果界面如下：字符輸入界面，字符輸入完，以字符39。 字符由statistics()輸入。綜合時(shí)間復(fù)雜度分析，該程序的時(shí)間復(fù)雜度為T(N)=Θ(N)。這些都是根據(jù)它們的結(jié)點(diǎn)類型計(jì)算得來(lái)。在這個(gè)程序中，本人認(rèn)為用鍵盤輸入的字符中有一個(gè)字符‘’沒(méi)有納入哈夫曼編碼中，其是還不是完善的。同時(shí)，還有一個(gè)代表?xiàng)５淖兞?。由于，在N很大情況下，這一部分的賦值運(yùn)算總次數(shù)也就是這部分的時(shí)間的復(fù)雜度為T(N)=Θ(N).如果，N不是很大，其時(shí)間復(fù)雜度就為：T(N)=Θ(1)；構(gòu)建哈夫曼樹(shù)部分的函數(shù)與哈夫曼編碼讀取的函數(shù)時(shí)間復(fù)雜度分析。其分別是統(tǒng)計(jì)部分的函數(shù)、構(gòu)建哈夫曼樹(shù)部分的函數(shù)與哈夫曼編碼讀取的函數(shù),這里假如輸入的字符個(gè)數(shù)為N,而其中的總不同字符為n.統(tǒng)計(jì)部分的時(shí)間復(fù)雜度分析及該部分要分析函數(shù)是如下函數(shù)。（如下）：在程序執(zhí)行的第一界面中選擇第二個(gè)選項(xiàng)。到下一個(gè)函數(shù)去判斷。這是指向提貢data數(shù)據(jù)項(xiàng)次之的那個(gè)結(jié)點(diǎn)。因?yàn)楣蚵鼧?gòu)樹(shù)中樹(shù)從葉子結(jié)點(diǎn)開(kāi)始建立。 pointer1=pointer。 if(pointerparent==1amp。 } } } pointer++。 { 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指向data數(shù)據(jù)項(xiàng)是最小的那個(gè)結(jié)點(diǎn)。//定義min用來(lái)指出pointer1指向的結(jié)點(diǎn)在存儲(chǔ)空間的位置。 head0frequency=0。 exit(0)。)//從輸入流中斷獲取字符，直到碰到字符39。//如果在承載字符的鏈表中沒(méi)那個(gè)字符，就向那個(gè)鏈表插入一個(gè)結(jié)點(diǎn)來(lái)記錄那個(gè)字符。//同時(shí)，記錄這個(gè)字符的個(gè)數(shù)以有了一個(gè)。while(pointernext!=NULL)//循環(huán)的方式來(lái)找到承載統(tǒng)計(jì)字符的鏈表的表尾結(jié)點(diǎn)。有就向調(diào)用函數(shù)回答是。//創(chuàng)建一個(gè)同承載字符鏈表的結(jié)點(diǎn)同類型的指針，用于訪問(wèn)那個(gè)鏈表。 { pointerch=39。如果有的話，就是其左子結(jié)點(diǎn)的存儲(chǔ)空間位置。它們的相關(guān)數(shù)據(jù)來(lái)自承載統(tǒng)計(jì)字符鏈表中的相應(yīng)數(shù)據(jù)，一個(gè)葉子結(jié)點(diǎn)，就要讀取一個(gè)承載統(tǒng)計(jì)字符鏈表的一個(gè)結(jié)點(diǎn)的數(shù)據(jù)。//由于哈夫曼樹(shù)中，有n個(gè)葉子結(jié)點(diǎn)，哈夫曼樹(shù)就應(yīng)有2*n1個(gè)結(jié)點(diǎn)。 } reading_code()。while(pointer1parent!=1)//由于輸入結(jié)點(diǎn)數(shù)據(jù)時(shí)，根結(jié)點(diǎn)的parent項(xiàng)記錄為1,這是循環(huán)條件用來(lái)判斷是否訪問(wèn)到根結(jié)點(diǎn) { pointer2=head+(pointer1parent1)。 if((i+1)%2==0) coutendl。 } else cout(line feed)39。)//由于字符中可能會(huì)出現(xiàn)空格與換行符，于它們的ch數(shù)據(jù)項(xiàng)的顯示特殊化處理。ihead0frequency。 case 2:statistics()。 cout from the file reading characters endl。//在上函數(shù)完成葉子結(jié)點(diǎn)的輸入的基礎(chǔ)上創(chuàng)建哈夫曼樹(shù)。//建立一個(gè)棧來(lái)存放huffman codeint main(void){ initialization_of_head()。parent用來(lái)記//錄該結(jié)點(diǎn)的位置，如果其無(wú)父結(jié)點(diǎn)，其值為1，left_child來(lái)記錄其左子結(jié)點(diǎn)的位置，無(wú)左子樹(shù)，就記錄為0。 int data。struct information_node{ char ch。int enter_huffman_values(int n)。bool find_record(char cha)。//哈夫曼樹(shù)葉子結(jié)點(diǎn)的輸入creat_huffman_tree(number,n)。data用來(lái)記錄權(quán)重。在每個(gè)結(jié)點(diǎn)是一個(gè)結(jié)構(gòu)體類型。每次由無(wú)父結(jié)點(diǎn)的結(jié)點(diǎn)中選出兩個(gè)權(quán)重最小的兩結(jié)點(diǎn)，把它們的權(quán)重之和來(lái)構(gòu)建一個(gè)新結(jié)點(diǎn)的權(quán)重，并且用那兩個(gè)結(jié)點(diǎn)要記錄它們的父結(jié)點(diǎn)就是那個(gè)新結(jié)點(diǎn)。while((ch=())!=39。} *head0。實(shí)現(xiàn)思路字符統(tǒng)計(jì)：字符統(tǒng)計(jì)是為了計(jì)算出字符的頻數(shù)，以之構(gòu)成哈夫曼樹(shù)葉子結(jié)點(diǎn)的權(quán)。這三者順序進(jìn)行。 struct information_node *next。void statistics(){ char
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1