【正文】 if(pointerparent==1amp。amp。(pointerdatapointer2data))//如果訪問的結(jié)點(diǎn)無(wú)父結(jié)點(diǎn)記錄，又結(jié)點(diǎn)的data數(shù)據(jù)比pointer2指向的結(jié)點(diǎn)的data數(shù)據(jù)項(xiàng)小。就用pointer1與pointer2中的其中一個(gè)指向它，如果它的data數(shù)據(jù)比pointer1的data數(shù)據(jù)項(xiàng)還小，就用pointer1來指向它，pointer2指向pointer1以前指向的結(jié)點(diǎn)。否則，就用pointer2來指向它。同時(shí)，min與sec也要相應(yīng)的改變記錄。 { if(pointerdatapointer1data) { sec=min。 pointer2=pointer1。 pointer1=pointer。 min=m。 } else { pointer2=pointer。 sec=m。 } } pointer++。 }pointerdata=pointer1data+pointer2data。//在這里pointer是出了查找范圍的，在范圍外其指向的結(jié)點(diǎn)是待錄入數(shù)據(jù)的結(jié)點(diǎn)于是向這個(gè)結(jié)點(diǎn)錄入數(shù)據(jù)。其data項(xiàng)是pointer1與pointer2的data項(xiàng)的和這是哈夫曼構(gòu)樹的方法。因?yàn)楣蚵鼧?gòu)樹中樹從葉子結(jié)點(diǎn)開始建立。每次由無(wú)父結(jié)點(diǎn)的結(jié)點(diǎn)中選出兩個(gè)權(quán)重最小的兩結(jié)點(diǎn)，把它們的權(quán)重之和來構(gòu)建一個(gè)新結(jié)點(diǎn)的權(quán)重，并且那兩個(gè)結(jié)點(diǎn)要記錄它們的父結(jié)點(diǎn)就是那個(gè)新結(jié)點(diǎn)。再重復(fù)如上的操作，直到最后的樹的建成。pointerleft_child=min。//指出樹的新結(jié)點(diǎn)的左子結(jié)點(diǎn)所在的位置。這里指向提貢data數(shù)據(jù)項(xiàng)最小的那個(gè)結(jié)點(diǎn)。pointerright_child=sec。//指出樹的新結(jié)點(diǎn)的右子結(jié)點(diǎn)所在的位置。這是指向提貢data數(shù)據(jù)項(xiàng)次之的那個(gè)結(jié)點(diǎn)。 pointer1parent=number+1。//既然pointer1指向的結(jié)點(diǎn)的父結(jié)點(diǎn)了，就記錄下來。 pointer2parent=number+1。//既然pointer2指向的結(jié)點(diǎn)的父結(jié)點(diǎn)了，就記錄下為。creat_huffman_tree(number+1,n)。//如果還有兩個(gè)或兩個(gè)以上結(jié)點(diǎn)無(wú)父結(jié)點(diǎn)記錄，這就說明了還要繼續(xù)構(gòu)樹。于是遞歸調(diào)用。到下一個(gè)函數(shù)去判斷。這里的number+1說明的是，2*n1中結(jié)點(diǎn)中有number+1個(gè)結(jié)點(diǎn)以錄入數(shù)據(jù)。只要number1小于2*。 }}程序執(zhí)行 程序執(zhí)行的第一界面：有兩個(gè)選項(xiàng)，現(xiàn)在選1就會(huì)把一個(gè)文件中的字符進(jìn)行哈夫曼編碼。就進(jìn)入結(jié)果界面中，每一個(gè)字符與它的哈夫編碼行等于號(hào)連起來，指明它的相應(yīng)的哈夫曼編碼。這里，也把文件中的空格與換行符也統(tǒng)計(jì)進(jìn)來了，這是本人的想法。本人認(rèn)為那樣可以使信息在傳輸時(shí)能完整的保存信息開始的風(fēng)格。但本人也認(rèn)識(shí)到，它也會(huì)議帶來信息的多余。（如下）：在程序執(zhí)行的第一界面中選擇第二個(gè)選項(xiàng)。于是進(jìn)入了用戶自己輸入字符，再統(tǒng)計(jì)，再哈夫曼編碼的輸出。程序執(zhí)行結(jié)果界面如下：字符輸入界面，字符輸入完，以字符39。39。結(jié)束。繼上的結(jié)果界面時(shí)間復(fù)雜度分析 該程序中，影響程序執(zhí)行時(shí)間的基本運(yùn)算是賦值運(yùn)算。由字符統(tǒng)計(jì)部分的輸入規(guī)模決定。主要從三個(gè)部分的函數(shù)進(jìn)行時(shí)間的復(fù)雜度分析。其分別是統(tǒng)計(jì)部分的函數(shù)、構(gòu)建哈夫曼樹部分的函數(shù)與哈夫曼編碼讀取的函數(shù),這里假如輸入的字符個(gè)數(shù)為N,而其中的總不同字符為n.統(tǒng)計(jì)部分的時(shí)間復(fù)雜度分析及該部分要分析函數(shù)是如下函數(shù)。 bool find_record(char cha)//找出已存入的字符 void recording(char ch)//插入新字符 void statistics()//字符頻數(shù)統(tǒng)計(jì)的入口函數(shù)。 字符由statistics()輸入。進(jìn)行了N次賦值。這N個(gè)函數(shù)還要進(jìn)入find_record()函數(shù)中進(jìn)行判斷。最后會(huì)有n個(gè)字符進(jìn)入record()函數(shù)中插入鏈表。在find_record()函數(shù)中要進(jìn)行查找進(jìn)行而進(jìn)行的賦值，這里查找平均的次數(shù)要小于(n1)/2,也就是在find_record函數(shù)中進(jìn)行的賦值的平均次數(shù)要小于N*((n1)/2)。,在recording（）函數(shù)中，經(jīng)計(jì)算會(huì)有(n1)*n/2+5*n 次賦值運(yùn)算。由于，在N很大情況下，這一部分的賦值運(yùn)算總次數(shù)也就是這部分的時(shí)間的復(fù)雜度為T(N)=Θ(N).如果，N不是很大，其時(shí)間復(fù)雜度就為：T(N)=Θ(1)；構(gòu)建哈夫曼樹部分的函數(shù)與哈夫曼編碼讀取的函數(shù)時(shí)間復(fù)雜度分析。由于，不同的字符是有限可數(shù)，那么這里的時(shí)間復(fù)雜度變?yōu)椋篢(N)=Θ(1)。綜合時(shí)間復(fù)雜度分析，該程序的時(shí)間復(fù)雜度為T(N)=Θ(N)?？臻g復(fù)雜度分析 程序中主要用到兩個(gè)全局變量指針。用它們分別指向承載統(tǒng)計(jì)字符鏈表與哈夫曼樹結(jié)點(diǎn)存儲(chǔ)空間。它們的大小是隨輸入字符的不同總數(shù)決定的。如輸入n個(gè)字符，對(duì)于承載統(tǒng)計(jì)字符鏈表就要(n+1）*9 個(gè)字節(jié)的存儲(chǔ)空間。對(duì)于哈夫曼樹的結(jié)點(diǎn)的存儲(chǔ)空間來說，其需要（2*n1)*17個(gè)字節(jié)的空間。同時(shí)，還有一個(gè)代表?xiàng)５淖兞?。這個(gè)變量要的存儲(chǔ)空間是小于或等于4*（1+n)個(gè)字節(jié)。這些都是根據(jù)它們的結(jié)點(diǎn)類型計(jì)算得來。而其它的變量都是局部變量。每一個(gè)函數(shù)中，調(diào)用局部變量用的存儲(chǔ)空間不會(huì)超出28個(gè)字節(jié)。其中在函數(shù)creat_huffman_tree(int number,int n)/中用的局部變量存儲(chǔ)空間最大，其為28字節(jié)。所以，程序的存儲(chǔ)空間最大是（n+1)*9+（2*n1)*17+4*(1+n)+28.編程總結(jié) 該程序能完成從文件中已存字符或從鍵盤要求輸入的所有字符的統(tǒng)計(jì)，最后完成哈夫曼編碼。并打印出來。在這個(gè)程序中，本人認(rèn)為用鍵盤輸入的字符中有一個(gè)字符‘’沒有納入哈夫曼編碼中，其是還不是完善的。資料參考⑴ 嚴(yán)蔚敏, 吳偉民. 數(shù)據(jù)結(jié)構(gòu). 清華大學(xué)出版社, ⑵ 錢能. C++程序設(shè)計(jì)教程（第二版）. 清華大學(xué)