數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告---赫夫曼編碼

1、<p>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) </p><p><b>　　題目：赫夫曼編碼</b></p><p>　　院、 系：計(jì)算機(jī)科學(xué)與工程學(xué)院</p><p>　　學(xué)科專業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù) </p><p>　　學(xué) 生： </p><p>　　學(xué)

2、 號(hào)： </p><p>　　指導(dǎo)教師： </p><p><b>　　2010年12月</b></p><p><b>　　目 錄</b></p><p>　　1課程設(shè)計(jì)的題目----------------------- 0 頁&l

3、t;/p><p>　　2課程設(shè)計(jì)的目的（設(shè)計(jì)要解決的問題）-------2頁</p><p>　　3概要設(shè)計(jì)（函數(shù)劃分、總體設(shè)計(jì)）--------- 2頁</p><p>　　4詳細(xì)設(shè)計(jì)（各函數(shù)算法、流程圖、程序）-----3頁</p><p>　　5調(diào)試結(jié)果--------------------------------23頁</p&g

4、t;<p>　　6課程設(shè)計(jì)總結(jié)----------------------------24頁</p><p>　　7心得體會(huì)------------------------------- 24頁</p><p><b>　　課程設(shè)計(jì)的目的：</b></p><p>　　了解利用赫夫曼樹求解給定權(quán)值的字符串的赫夫曼編碼的算法思想；&

5、lt;/p><p>　　學(xué)習(xí)利用計(jì)算機(jī)程序語言實(shí)現(xiàn)赫夫曼樹構(gòu)造的算法；</p><p>　　利用構(gòu)造好的赫夫曼樹對(duì)任一字符串求解其赫夫曼編碼，以此熟悉赫夫曼編碼的整個(gè)求解過程；</p><p><b>　　概要設(shè)計(jì):</b></p><p>　　函數(shù)劃分：功能模塊總共分為四個(gè)塊，由四個(gè)主要的函數(shù)來實(shí)現(xiàn)，分別為：</p&

6、gt;<p>　　linklist calculation(char temp[],int n)-------統(tǒng)計(jì)字符種類及各個(gè)字符在字符串中出現(xiàn)次數(shù)的函數(shù)：用temp[]接收用戶輸入的字符串，將字符串存入一個(gè)鏈表當(dāng)中，鏈表的每個(gè)結(jié)點(diǎn)存儲(chǔ)字符串的一個(gè)字符，然后用兩個(gè)指針p和t，查找字符串中相同的字符，將相同的字符結(jié)點(diǎn)刪除，只保留一個(gè)，并且在保留的那個(gè)字符結(jié)點(diǎn)中統(tǒng)計(jì)當(dāng)前字符的權(quán)值（即其在字符串中出現(xiàn)的次數(shù)），統(tǒng)計(jì)完成后將鏈表

7、的頭結(jié)點(diǎn)返回；</p><p>　　status auto_calculation(linklist L)-------自動(dòng)統(tǒng)計(jì)權(quán)值的函數(shù)，以每個(gè)字符在字符串中出現(xiàn)的次數(shù)作為其權(quán)值：將calculation()中統(tǒng)計(jì)的各個(gè)字符在字符串中出現(xiàn)的次數(shù)作為權(quán)值存儲(chǔ)到全局?jǐn)?shù)組w中；</p><p>　　status input_weight(linklist L)--------手動(dòng)輸入各個(gè)字符權(quán)

8、值的函數(shù)：對(duì)之前建立好的存儲(chǔ)字符串中每種字符信息的鏈表的結(jié)點(diǎn)進(jìn)行操作，手動(dòng)輸入每個(gè)字符的權(quán)值，并將其對(duì)應(yīng)的存儲(chǔ)在每個(gè)結(jié)點(diǎn)的權(quán)值變量weight中，待鏈表中所有字符權(quán)值手動(dòng)輸入完畢后，再將鏈表中存儲(chǔ)的每種字符的權(quán)值賦給存儲(chǔ)權(quán)值的全局?jǐn)?shù)組w中；</p><p>　　void Creat_HuffmanTree(HuffmanTree &HT,linklist L)------根據(jù)字符串中每個(gè)字符的權(quán)值構(gòu)造赫夫

9、曼樹的函數(shù)：利用之前用于存儲(chǔ)存儲(chǔ)字符串中每種字符信息的鏈表，統(tǒng)計(jì)出字符種類個(gè)數(shù)n（即鏈表的結(jié)點(diǎn)數(shù)），然后開辟長度為2n的存儲(chǔ)空間構(gòu)造赫夫曼樹，這其中還需要調(diào)用選擇權(quán)值最小的兩個(gè)結(jié)點(diǎn)的select()函數(shù)；</p><p>　　void text_code(HuffmanTree HT,linklist head,int n)-------根據(jù)構(gòu)造好的赫夫曼樹求解字符串中每個(gè)字符的編碼的函數(shù)：將之前構(gòu)造好的赫夫曼樹

10、，由葉子結(jié)點(diǎn)向根結(jié)點(diǎn)求每個(gè)字符的赫夫曼編碼，并且將得到的編碼保存與相應(yīng)字符對(duì)應(yīng)的一個(gè)數(shù)組中，這個(gè)數(shù)組是Code這個(gè)結(jié)構(gòu)體的一個(gè)成員，它其中還包括存儲(chǔ)每個(gè)字符及其權(quán)值的變量；</p><p>　　void Calculte_code(char temp[],linklist head)------輸出每個(gè)字符以及整個(gè)字符串的赫夫曼編碼的函數(shù)：將每個(gè)字符輸出，同時(shí)逆序輸出求解得到的編碼，即是其對(duì)應(yīng)的赫夫曼編碼，然后輸

11、出整個(gè)字符串的赫夫曼編碼；</p><p>　　選擇權(quán)值最小的兩個(gè)結(jié)點(diǎn)的函數(shù)--------void select(HuffmanTree &HT,int nn,int *s11,int *s22)，這是輔助建造赫夫曼樹的函數(shù)。</p><p><b>　　總體設(shè)計(jì)：</b></p><p>　　求解一個(gè)字符串的赫夫曼編碼的算法主要是根

12、據(jù)字符串中各個(gè)字符的權(quán)值構(gòu)造赫夫曼樹來進(jìn)行編碼的，對(duì)于字符的權(quán)值，我采用了自動(dòng)統(tǒng)計(jì)和手動(dòng)輸入兩種方式得到，這樣可以方便用戶的各種需求。</p><p>　　對(duì)于自動(dòng)統(tǒng)計(jì)各個(gè)字符的權(quán)值這一功能，主要是依據(jù)各個(gè)字符在字符串中出現(xiàn)的次數(shù)作為它的權(quán)值。因?yàn)樽址袝?huì)有重復(fù)出現(xiàn)的字符，而它們的權(quán)值是每種字符出現(xiàn)的次數(shù)即可，即只需將統(tǒng)計(jì)得到的權(quán)值存儲(chǔ)在一個(gè)字符的信息中即可，因此，我采用了鏈表這種數(shù)據(jù)結(jié)構(gòu)，將用戶輸入的字符串的

13、每個(gè)字符分別保存在一個(gè)鏈表的每個(gè)結(jié)點(diǎn)中，然后查找鏈表中字符相同的結(jié)點(diǎn)，用一個(gè)指針p從鏈表的第一個(gè)結(jié)點(diǎn)開始，再用一個(gè)查找指針t指向p的下一個(gè)結(jié)點(diǎn)，然后讓指針t從p的下一個(gè)結(jié)點(diǎn)開始，查找p后面的所有結(jié)點(diǎn)，如果找到與p中的字符相同結(jié)點(diǎn)，就將t所指的結(jié)點(diǎn)從鏈表中刪除，p所指的結(jié)點(diǎn)的權(quán)值加1，t繼續(xù)向下查找，直至查找完最后一個(gè)結(jié)點(diǎn)，然后將p指向下一個(gè)待查找的字符，t繼續(xù)從p的下一個(gè)結(jié)點(diǎn)開始，重復(fù)上述過程，直至將鏈表中的所有結(jié)點(diǎn)都查找一遍，最后，鏈

14、表中存儲(chǔ)的就是字符串中不同的字符及它們各自在字符串中的出現(xiàn)次數(shù)。</p><p>　　對(duì)于手動(dòng)輸入各個(gè)字符權(quán)值這一功能模塊，同樣需要先統(tǒng)計(jì)出字符串中不同字符的個(gè)數(shù)，然后給每個(gè)字符手動(dòng)賦上相應(yīng)的權(quán)值，因此，同樣利用統(tǒng)計(jì)各個(gè)字符在字符串中出現(xiàn)次數(shù)的鏈表，手動(dòng)給每個(gè)結(jié)點(diǎn)中的字符賦權(quán)值，覆蓋掉原先的出現(xiàn)次數(shù)即可。</p><p>　　待自動(dòng)統(tǒng)計(jì)或者通過手動(dòng)輸入的方式給每個(gè)字符賦上相應(yīng)的權(quán)值以后，將

15、鏈表中的權(quán)值對(duì)應(yīng)的存儲(chǔ)到一個(gè)全局?jǐn)?shù)組w中，w數(shù)組定義為全局變量的原因是整個(gè)程序運(yùn)行過程中，多個(gè)函數(shù)都會(huì)訪問它，因此定義為全局變量可以方便每個(gè)函數(shù)的訪問。然后，統(tǒng)計(jì)出字符串中不同字符的個(gè)數(shù)n，開辟2n個(gè)連續(xù)的存儲(chǔ)單元來建立赫夫曼樹，其中這段存儲(chǔ)空間中的0號(hào)單元不使用，而作為后面判斷每個(gè)結(jié)點(diǎn)是否存在雙親或者左右孩子使用。開始構(gòu)造赫夫曼樹，先將n個(gè)字符的權(quán)值對(duì)應(yīng)存儲(chǔ)到1～n號(hào)存儲(chǔ)單元中，并且將它們的左右孩子以及雙親都初始化為0號(hào)單元，即沒有雙

16、親和左右孩子，然后從現(xiàn)有的權(quán)值表中選出兩個(gè)雙親為0且權(quán)值最小的相加后，添加到n+1～2n單元中，更新權(quán)值表，重復(fù)上述過程，建立赫夫曼樹。赫夫曼樹構(gòu)造完成后，將此存儲(chǔ)空間的頭指針通過宏引帶回，方便后續(xù)的操作。</p><p>　　調(diào)用一個(gè)text_code()函數(shù)對(duì)建立好的赫夫曼樹有葉子結(jié)點(diǎn)向根結(jié)點(diǎn)逆向求每個(gè)葉子結(jié)點(diǎn)的編碼，并將編碼存儲(chǔ)在一個(gè)結(jié)構(gòu)體成員數(shù)組中，這個(gè)結(jié)構(gòu)體還包含存儲(chǔ)字符的變量，以及存儲(chǔ)字符權(quán)值的變量，

17、這樣就可以將每個(gè)字符與它的權(quán)值和編碼對(duì)應(yīng)起來。</p><p>　　最后，利用之前用于統(tǒng)計(jì)字符種類及其每個(gè)字符出現(xiàn)次數(shù)的鏈表倒序輸出每個(gè)字符的編碼，即得到它的赫夫曼編碼，然后，在輸出整個(gè)字符串的赫夫曼編碼。</p><p><b>　　詳細(xì)設(shè)計(jì)</b></p><p><b>　　各函數(shù)算法：</b></p>

18、<p>　　Linklist calculation(char temp[],int n)：字符數(shù)組temp接收用戶輸入的 字符串，整型變量n為字符串中字符的個(gè)數(shù)。若接收到的字符串不為空，則創(chuàng)建一個(gè)存儲(chǔ)字符串的鏈表head，用一個(gè)for循環(huán)將字符串中的每個(gè)字符及其權(quán)值等相關(guān)信息存儲(chǔ)在鏈表中的每個(gè)結(jié)點(diǎn)中，并且初始化每個(gè)字符的權(quán)值為1。鏈表建立完畢后，用一個(gè)指針p指向鏈表的第一個(gè)結(jié)點(diǎn)，同時(shí)用一個(gè)指針t指向p的下一個(gè)結(jié)點(diǎn)，然后讓指

19、針t從p的下一個(gè)結(jié)點(diǎn)開始，查找p后面的所有結(jié)點(diǎn)，如果找到與p中的字符相同結(jié)點(diǎn)，就將t所指的結(jié)點(diǎn)從鏈表中刪除，同時(shí)p所指的結(jié)點(diǎn)的權(quán)值加1，t繼續(xù)向下查找，直至查找完最后一個(gè)結(jié)點(diǎn)，然后將p指向下一個(gè)待查找的字符，t繼續(xù)從p的下一個(gè)結(jié)點(diǎn)開始，重復(fù)上述過程，直至將鏈表中的所有結(jié)點(diǎn)都查找一遍，最后，鏈表中存儲(chǔ)的就是字符串中不同的字符及它們各自在字符串中的出現(xiàn)次數(shù)，以上操作完成后，將鏈表的頭指針返回，算法結(jié)束；</p><p&g

20、t;　　status auto_calculation(linklist L）：L為之前建立好的鏈表的頭結(jié)點(diǎn)指針，如果鏈表不為空，則用p指向頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，然后用一個(gè)for循環(huán)輸出鏈表中各個(gè)結(jié)點(diǎn)中的字符及其對(duì)應(yīng)的權(quán)值（這里為字符在字符串中的出現(xiàn)次數(shù)為其權(quán)值），同時(shí)用一個(gè)變量n統(tǒng)計(jì)出不同字符的個(gè)數(shù)，然后給一個(gè)指向整型變量的全局指針w開辟n個(gè)連續(xù)的存儲(chǔ)整型數(shù)據(jù)的內(nèi)存單元，將開辟好的存儲(chǔ)空間的首地址返回給w，然后用一個(gè)指針p從鏈表的第一個(gè)

21、結(jié)點(diǎn)開始，循環(huán)的將各個(gè)結(jié)點(diǎn)中的權(quán)值賦到w的每個(gè)存儲(chǔ)單元中。如果鏈表為空，輸出“統(tǒng)計(jì)錯(cuò)誤”的提示信息。最后返回一個(gè)狀態(tài)值；</p><p>　　status input_weight(linklist L)：L為之前建立好的鏈表的頭結(jié)點(diǎn)指針，將指針p指向鏈表頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)（即第一個(gè)結(jié)點(diǎn)），如果鏈表不為空，p從第一個(gè)結(jié)點(diǎn)開始直至最后一個(gè)，循環(huán)的得到用戶給當(dāng)前結(jié)點(diǎn)中字符賦的權(quán)值，同時(shí)用一個(gè)整型變量n統(tǒng)計(jì)鏈表的結(jié)點(diǎn)數(shù)

22、，根據(jù)n的大小開辟一段存儲(chǔ)整型數(shù)據(jù)的連續(xù)存儲(chǔ)單元，并將此段存儲(chǔ)空間的首地址返回給全局指針變量w，然后將鏈表中每個(gè)結(jié)點(diǎn)的權(quán)值賦到w這個(gè)數(shù)組的每個(gè)存儲(chǔ)單元中。如果鏈表為空，則輸出相應(yīng)的提示信息，最后返回一個(gè)狀態(tài)值;</p><p>　　void Creat_HuffmanTree(HuffmanTree &HT,linklist L)：L為之前建立好的鏈表的頭結(jié)點(diǎn)的指針，HT用來返回構(gòu)造好的赫夫曼樹的頭指針。

23、首先，用一個(gè)指針temp_p指向L的下一個(gè)結(jié)點(diǎn)（即鏈表的第一個(gè)結(jié)點(diǎn)），然后用一個(gè)n統(tǒng)計(jì)出鏈表的結(jié)點(diǎn)數(shù)，即得到字符串中不同字符的個(gè)數(shù)，如果n<=1，則算法結(jié)束，因?yàn)橐粋€(gè)字符無法構(gòu)造赫夫曼樹，否則，開辟一段2n個(gè)連續(xù)的存儲(chǔ)HTnode這個(gè)結(jié)構(gòu)體的內(nèi)存單元，并且把首地址返回給HT，這段存儲(chǔ)空間的0號(hào)存儲(chǔ)單元不用，其中這段存儲(chǔ)空間中的0號(hào)單元不使用，而作為后面判斷每個(gè)結(jié)點(diǎn)是否存在雙親或者左右孩子使用，HTnode這個(gè)結(jié)構(gòu)體包含三個(gè)成員，分

24、別為weight(權(quán)值）、lchild(左孩子）、rchild(右孩子）以及parent(雙親）。然后開始構(gòu)造赫曼樹，首先將n個(gè)字符的權(quán)值對(duì)應(yīng)存儲(chǔ)到1～n號(hào)存儲(chǔ)單元中，并且將它們的左右孩子以及雙親都初始化為0號(hào)單元，即沒有雙親和左右孩子，然后調(diào)用select()函數(shù)從現(xiàn)有的權(quán)值表中選出兩個(gè)雙親為0且權(quán)值最小的相加后的權(quán)值，添加到n+1～2n單元中，并且將這兩個(gè)權(quán)值最小的單元的序號(hào)s1和s</p><p>　　vo

25、id select(HuffmanTree &HT,int nn,int *s11,int *s22)：HT為建立好的赫夫曼樹的首地址，nn為搜索的權(quán)值表中存儲(chǔ)單元的最大序號(hào)，s11和s22分別帶回搜索到的權(quán)值最小的兩個(gè)結(jié)點(diǎn)所在表中的序號(hào)，定義一個(gè)臨時(shí)變量temp=0，然后，將表中第一個(gè)雙親為0的結(jié)點(diǎn)的權(quán)值賦給temp，然后再用一個(gè)for循環(huán)從1～nn號(hào)單元中找到雙親為0，且比temp小的結(jié)點(diǎn)，把它的權(quán)值賦給temp，直至找完n

26、n個(gè)存儲(chǔ)單元后，temp中存儲(chǔ)的就是最小的權(quán)值，同時(shí)將此權(quán)值所在存儲(chǔ)單元的序號(hào)k賦給指針s11所指的存儲(chǔ)單元，由s11帶回這個(gè)序號(hào)，同理，查找另一個(gè)權(quán)值最小的結(jié)點(diǎn)也采用相同方法，只是查找時(shí)附加一個(gè)條件是，找到的序號(hào)不能等于*s11，最后，同樣賦給*s22，有s22帶回第二小的權(quán)值所在的存儲(chǔ)單元的序號(hào)；</p><p>　　void text_code(HuffmanTree HT,linklist head,in

27、t n)：HT為赫夫曼樹的首地址，head為之前建立好的鏈表的頭結(jié)點(diǎn)的指針，n為鏈表的結(jié)點(diǎn)數(shù)。從葉子結(jié)點(diǎn)向根結(jié)點(diǎn)逆向求其編碼,從雙親不為0的葉子結(jié)點(diǎn)開始，一直查找到雙親為0的根結(jié)點(diǎn)為止，在由葉子結(jié)點(diǎn)向根結(jié)點(diǎn)逆向求編碼的過程中，先判斷當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)是否為0，如果不為0，則在判斷當(dāng)前結(jié)點(diǎn)是其雙親結(jié)點(diǎn)的左孩子還是右孩子，如果是左孩子，就將字符0賦到鏈表中對(duì)應(yīng)的結(jié)點(diǎn)的存儲(chǔ)編碼的字符數(shù)組中，若是右孩子就將字符1賦值到存儲(chǔ)編碼的數(shù)組中，然后，再

28、向上查找，再次按照上述步驟判斷，直到查找到根結(jié)點(diǎn)（雙親為0的結(jié)點(diǎn)），這樣就完成了一個(gè)葉子結(jié)點(diǎn)的編碼過程，再對(duì)下一個(gè)葉子結(jié)點(diǎn)重復(fù)上述步驟進(jìn)行編碼即可。最后，鏈表的每個(gè)結(jié)點(diǎn)中的字符數(shù)組存儲(chǔ)的就是赫夫曼編碼的倒序。</p><p>　　void Calculate_Code(char temp[],linklist head)：字符數(shù)組temp存儲(chǔ)的是用戶輸入的字符串，在主函數(shù)中調(diào)用此函數(shù)時(shí)，通過主函數(shù)中定義的字符數(shù)組

29、s傳遞數(shù)組首地址給它，head為之前建立的鏈表的頭結(jié)點(diǎn)指針。將指針p指向頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，然后用p循環(huán)將鏈表中每個(gè)結(jié)點(diǎn)中字符及其對(duì)應(yīng)的編碼輸出，由于開始求解每個(gè)字符赫夫曼編碼的時(shí)候是由葉子結(jié)點(diǎn)向根結(jié)點(diǎn)逆向求的編碼，因此，存儲(chǔ)編碼的數(shù)組c中存儲(chǔ)的是赫夫曼編碼的倒序，因此輸出的時(shí)候采用逆序輸出，就可得到赫夫曼編碼了。然后，再從鏈表的頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)開始，將字符串中的第一個(gè)字符到第n個(gè)字符，依次與鏈表中每個(gè)結(jié)點(diǎn)中的字符相比較，如果找到相同

30、字符的結(jié)點(diǎn)，就將結(jié)點(diǎn)中的編碼輸出，依此循環(huán)，直至字符串中的每個(gè)字符的編碼都輸出，這樣就得到了整個(gè)字符串的編碼。</p><p><b>　　流程圖：</b></p><p>　　Linklist calculation(char temp[],int n)：統(tǒng)計(jì)字符種類及各個(gè)字符在字符串中出現(xiàn)的次數(shù)的函數(shù)</p><p>　　status au

31、to_calculation(linklist L)：自動(dòng)統(tǒng)計(jì)權(quán)值的函數(shù)，以每個(gè)字符在字符串中出現(xiàn)的次數(shù)為權(quán)值</p><p>　　status input_weight(linklist L)：手動(dòng)輸入各個(gè)字符權(quán)值的函數(shù)</p><p>　　void select(HuffmanTree &HT,int nn,int *s11,int *s22):在構(gòu)造赫夫曼樹的順序表中選出雙親

32、為0，且權(quán)值最小的兩個(gè)結(jié)點(diǎn)，并用s11和s22返回這兩個(gè)結(jié)點(diǎn)所在順序表中的序號(hào)</p><p>　　void Creat_HuffmanTree(HuffmanTree &HT,linklist L)：建立赫夫曼樹的函數(shù)</p><p>　　void text_code(HuffmanTree HT,linklist head,int n):從葉子結(jié)點(diǎn)向根結(jié)點(diǎn)逆向求編碼</p

33、><p>　　void Calculte_Code(char temp[],linklist head)：輸出各個(gè)字符及整個(gè)字符串編碼的函數(shù)</p><p>　　源程序：(由于采用了C++中的引用形參，因此必須采用.cpp為擴(kuò)展名的源文件編譯）</p><p>　　//HuffmanCoding.cpp</p><p>　　#include<

34、;stdio.h></p><p>　　#include<string.h></p><p>　　#include<stdlib.h></p><p>　　#define length 100;</p><p>　　#define OK 1;</p><p>　　#define error

35、 0;</p><p>　　typedef int status;</p><p>　　typedef struct</p><p><b>　　{</b></p><p>　　unsigned int weight;</p><p>　　unsigned int lchild ,rchild ,

36、parent;</p><p>　　}HTnode,*HuffmanTree;</p><p>　　typedef struct</p><p><b>　　{</b></p><p>　　char code;</p><p>　　unsigned int weight;</p>&

37、lt;p>　　char c[10];</p><p>　　}Code,*Code_p;</p><p>　　typedef struct Lnode</p><p><b>　　{</b></p><p><b>　　Code a;</b></p><p>　　stru

38、ct Lnode *next;</p><p>　　}Node,*linklist;</p><p>　　typedef char **HuffmanCode;</p><p>　　int *w; //w存放n個(gè)字符的相應(yīng)權(quán)值</p><p>　　linklist calculation(char temp[],int n) //統(tǒng)計(jì)字符種

39、類及各個(gè)字符在字符串中出現(xiàn)次數(shù)的函數(shù)，n表示字符串的個(gè)數(shù)</p><p><b>　　{</b></p><p><b>　　int i=0;</b></p><p>　　linklist p;</p><p>　　linklist t;</p><p>　　linklist

40、 head;</p><p>　　//創(chuàng)建一個(gè)字符串鏈表</p><p>　　head=(linklist)malloc(sizeof(Node)); //創(chuàng)建一個(gè)帶頭結(jié)點(diǎn)的鏈表</p><p>　　head->next=NULL;</p><p><b>　　p=head;</b></p><

41、p><b>　　if(n!=0)</b></p><p><b>　　{</b></p><p>　　//將字符串存儲(chǔ)到一個(gè)鏈表中，每個(gè)結(jié)點(diǎn)存儲(chǔ)一個(gè)字符，方便后續(xù)統(tǒng)計(jì)字符的種類個(gè)數(shù)及其各個(gè)字符的權(quán)值</p><p>　　for(i=0;i<n;i++)</p><p><b>

42、　　{</b></p><p>　　t=(linklist)malloc(sizeof(Node));</p><p>　　t->a.code=temp[i];</p><p>　　t->a.weight=1; //權(quán)值先初始化為1</p><p>　　p->next=t;</p><p>

43、;　　t->next=NULL;</p><p>　　p=p->next;</p><p><b>　　}</b></p><p>　　/***對(duì)鏈表進(jìn)行處理，字符串中的每種字符只保留一個(gè)，同時(shí)統(tǒng)計(jì)每種字符在字符串中出現(xiàn)的次數(shù)，如果采用自動(dòng)統(tǒng)計(jì)權(quán)值的話，</p><p>　　就以每個(gè)字符在字符串中出現(xiàn)的次數(shù)作

44、為其權(quán)值***/</p><p>　　linklist p1;</p><p>　　p=head->next;</p><p>　　linklist temp_p;</p><p>　　while(p!=NULL)</p><p><b>　　{</b></p><p&g

45、t;　　t=p->next;</p><p><b>　　p1=p;</b></p><p>　　while(t!=NULL)</p><p><b>　　{</b></p><p>　　if(p->a.code==t->a.code)</p><p>&l

46、t;b>　　{</b></p><p>　　p->a.weight++;</p><p>　　p1->next=t->next;</p><p><b>　　temp_p=t;</b></p><p>　　t=t->next;</p><p>　　free

47、(temp_p);</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p><b>　　p1=t;</b></p><p>　　t=t->n

48、ext;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　p=p->next;</p><p><b>　　}</b></p><p><b>　　}</b></p&g

49、t;<p><b>　　else</b></p><p>　　printf("沒有字符！");</p><p>　　return head;</p><p><b>　　}</b></p><p>　　status auto_calculation(linklist

50、 L) //自動(dòng)統(tǒng)計(jì)權(quán)值的函數(shù)，以每個(gè)字符在字符串中出現(xiàn)的次數(shù)作為其權(quán)值</p><p><b>　　{</b></p><p>　　printf("各字符權(quán)值統(tǒng)計(jì)如下：\n");</p><p>　　linklist p=L->next;</p><p><b>　　if(p)&

51、lt;/b></p><p><b>　　{</b></p><p><b>　　int n=0;</b></p><p>　　for(;p!=NULL;p=p->next)</p><p><b>　　{</b></p><p>　　pri

52、ntf("%c : %d",p->a.code,p->a.weight);</p><p>　　printf("\n");</p><p><b>　　n++;</b></p><p><b>　　}</b></p><p>　　w=(int *)

53、malloc(n*sizeof(int));</p><p>　　p=L->next;</p><p><b>　　int i;</b></p><p>　　for(i=0;i<n&&p!=NULL;i++,p=p->next)</p><p>　　w[i]=p->a.weight

54、;</p><p>　　return OK;</p><p><b>　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　printf("統(tǒng)計(jì)錯(cuò)誤，沒有字符！\n"

55、);</p><p>　　return error;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　status input_weight(linklist L) //手動(dòng)輸入各個(gè)字符權(quán)值的函數(shù)</p><p><

56、b>　　{</b></p><p>　　linklist p=L->next;</p><p>　　if(p!=NULL)</p><p><b>　　{</b></p><p><b>　　int n=0;</b></p><p>　　printf(

57、"請(qǐng)輸入各個(gè)字符的權(quán)值：\n");</p><p>　　for(p=L->next;p!=NULL;p=p->next)</p><p><b>　　{</b></p><p>　　printf("%c:",p->a.code);</p><p>　　scanf(

58、"%d",&p->a.weight);</p><p><b>　　n++;</b></p><p><b>　　}</b></p><p>　　w=(int *)malloc(n*sizeof(int));</p><p>　　p=L->next;</

59、p><p><b>　　int i=0;</b></p><p>　　for(i=0;i<n&&p!=NULL;i++,p=p->next)</p><p>　　w[i]=p->a.weight;</p><p>　　return OK;</p><p><b&

60、gt;　　}</b></p><p><b>　　else</b></p><p><b>　　{</b></p><p>　　printf("沒有字符！\n");</p><p>　　return error;</p><p><b&g

61、t;　　}</b></p><p><b>　　}</b></p><p>　　void select(HuffmanTree &HT,int nn,int *s11,int *s22)</p><p><b>　　{</b></p><p>　　int temp=0;</

62、p><p>　　HuffmanTree p=HT;</p><p><b>　　int k;</b></p><p>　　for(k=1;k<=nn;k++)</p><p><b>　　{</b></p><p>　　if(!p[k].parent)</p>

63、<p><b>　　{</b></p><p>　　temp=p[k].weight;</p><p><b>　　*s11=k;</b></p><p><b>　　break;</b></p><p><b>　　}</b></p&g

64、t;<p><b>　　}</b></p><p>　　for(k=1;k<=nn;k++)</p><p><b>　　{</b></p><p>　　if(!p[k].parent)</p><p><b>　　{</b></p><

65、p>　　if(p[k].weight<temp)</p><p><b>　　{</b></p><p>　　temp=p[k].weight;</p><p><b>　　*s11=k;</b></p><p><b>　　}</b></p><

66、;p><b>　　}</b></p><p><b>　　}</b></p><p>　　for(k=1;k<=nn;k++)</p><p><b>　　{</b></p><p>　　if(!p[k].parent&&k!=*s11)</p

67、><p><b>　　{</b></p><p>　　temp=p[k].weight;</p><p><b>　　*s22=k;</b></p><p><b>　　break;</b></p><p><b>　　}</b><

68、;/p><p><b>　　}</b></p><p>　　for(k=1;k<=nn;k++)</p><p><b>　　{</b></p><p>　　if(!p[k].parent&&k!=*s11)</p><p><b>　　{<

69、/b></p><p>　　if(p[k].weight<temp)</p><p><b>　　{</b></p><p>　　temp=p[k].weight;</p><p><b>　　*s22=k;</b></p><p><b>　　}<

70、;/b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　if(*s11>*s22)</p><p><b>　　{</b></p><p>　　temp=*s11;</p>

71、<p>　　*s11=*s22;</p><p>　　*s22=temp;</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　//建立赫夫曼樹</b></p><p>　　void Cr

72、eat_HuffmanTree(HuffmanTree &HT,linklist L)</p><p><b>　　{</b></p><p><b>　　int n=0;</b></p><p>　　linklist temp_p=L->next;</p><p>　　for(;te

73、mp_p!=NULL;temp_p=temp_p->next) //統(tǒng)計(jì)字符串中不同字符的個(gè)數(shù)</p><p><b>　　n++;</b></p><p><b>　　if(n<=1)</b></p><p><b>　　return;</b></p><p>　

74、　int m=2*n-1;</p><p><b>　　int i;</b></p><p>　　HuffmanTree p;</p><p>　　HT=(HuffmanTree)malloc((m+1)*sizeof(HTnode)); //零號(hào)單元未用</p><p>　　for(p=HT,i=1;i<=n;i

75、++) //給它賦上相應(yīng)的權(quán)值</p><p><b>　　{</b></p><p>　　p[i].weight=w[i-1];</p><p>　　p[i].lchild=0;</p><p>　　p[i].rchild=0;</p><p>　　p[i].parent=0;</p>

76、;<p><b>　　}</b></p><p>　　for(;i<=m;i++)</p><p><b>　　{</b></p><p>　　p[i].weight=0;</p><p>　　p[i].parent=0;</p><p>　　p[i].l

77、child=0;</p><p>　　p[i].rchild=0;</p><p><b>　　}</b></p><p>　　int s1,s2;</p><p>　　//建立huffman樹</p><p>　　for(i=n+1;i<=m;i++)</p><p&g

78、t;<b>　　{</b></p><p><b>　　s1=0;</b></p><p><b>　　s2=0;</b></p><p>　　select(HT,i-1,&s1,&s2);</p><p>　　HT[s1].parent=i;</p>

79、;<p>　　HT[s2].parent=i;</p><p>　　HT[i].lchild=s1;</p><p>　　HT[i].rchild=s2;</p><p>　　HT[i].weight=HT[s1].weight+HT[s2].weight;</p><p><b>　　}</b></

80、p><p><b>　　int j;</b></p><p>　　for(j=1;j<m;j++)</p><p><b>　　{</b></p><p>　　printf("%d weight=%d,parent=%d,lchild=%d,rchild=%d",j,HT[j]

81、.weight,HT[j].parent,HT[j].lchild,HT[j].rchild);</p><p>　　printf("\n");</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　//---從葉子向根節(jié)點(diǎn)逆向求赫夫

82、曼編碼----</p><p>　　void text_code(HuffmanTree HT,linklist head,int n)</p><p><b>　　{</b></p><p>　　HuffmanTree p=HT;</p><p>　　linklist tp;</p><p>　

83、　tp=head->next;</p><p><b>　　int m;</b></p><p><b>　　int k;</b></p><p><b>　　int j;</b></p><p><b>　　int i;</b></p>

84、<p>　　for(i=1;i<=n&&tp!=NULL;i++,tp=tp->next)</p><p><b>　　{</b></p><p><b>　　k=i;</b></p><p>　　for(j=1,m=p[k].parent; m!=0; k=m,m=p[k].pa

85、rent,j++)</p><p><b>　　{</b></p><p>　　if(p[m].lchild==k)</p><p>　　tp->a.c[j-1]='0';</p><p><b>　　else</b></p><p>　　tp->

86、a.c[j-1]='1';</p><p><b>　　}</b></p><p>　　for(;j-1<10;j++)</p><p>　　tp->a.c[j-1]='\0';</p><p><b>　　}</b></p><p&g

87、t;<b>　　}</b></p><p>　　void Calculte_Code(char temp[],linklist head)</p><p><b>　　{</b></p><p><b>　　int n;</b></p><p>　　linklist p=hea

88、d->next;</p><p>　　printf("各個(gè)字符的編碼如下：\n");</p><p>　　for(;p!=NULL;p=p->next)</p><p><b>　　{</b></p><p>　　printf("%c:",p->a.code);&

89、lt;/p><p><b>　　n=0;</b></p><p>　　for(int i=0;p->a.c[i]!='\0';i++)</p><p><b>　　n++;</b></p><p>　　for(int i=n-1;i>=0;i--)</p>&l

90、t;p>　　printf("%c",p->a.c[i]);</p><p>　　printf("\n");</p><p><b>　　}</b></p><p>　　printf("電文的編碼：");</p><p><b>　　int

91、m=0;</b></p><p>　　for(int k=0;temp[k]!='\0';k++)</p><p><b>　　m++;</b></p><p><b>　　int i,j;</b></p><p>　　for(i=0;i<m;i++)</p&

92、gt;<p><b>　　{</b></p><p>　　for(p=head->next;p!=NULL;p=p->next)</p><p><b>　　{</b></p><p>　　if(p->a.code==temp[i])</p><p><b>

93、;　　{</b></p><p><b>　　n=0;</b></p><p>　　for(j=0;p->a.c[j]!='\0';j++)</p><p><b>　　n++;</b></p><p>　　for(j=n-1;j>=0;j--)</p&

94、gt;<p>　　printf("%c",p->a.c[j]);</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　printf("\n&

95、quot;);</p><p><b>　　}</b></p><p>　　void main()</p><p><b>　　{</b></p><p>　　char s[100];</p><p><b>　　int n=0;</b></p&g

96、t;<p>　　HuffmanTree HT=NULL;</p><p>　　linklist L;</p><p>　　printf("請(qǐng)輸入一串電文：");</p><p>　　scanf("%s",&s);</p><p>　　for(int i=0;s[i]!='\

97、0';i++)</p><p><b>　　n++;</b></p><p>　　if(n!=1) //一個(gè)結(jié)點(diǎn)無法構(gòu)造赫夫曼樹，無赫夫曼編碼</p><p><b>　　{</b></p><p>　　L=calculation(s,n);</p><p>　　i

98、nt num=0;</p><p>　　char choice;</p><p><b>　　do</b></p><p><b>　　{</b></p><p>　　choice='n';</p><p>　　printf("\t1.自動(dòng)統(tǒng)計(jì)字符權(quán)

99、值（以每個(gè)字符在字符串中出現(xiàn)的次數(shù)作為其權(quán)值）\n\t2.手動(dòng)輸入字符的權(quán)值\n)");</p><p>　　printf("\t\t請(qǐng)選擇：");</p><p>　　scanf("%d",&num);</p><p>　　switch(num)</p><p><b>　

100、　{</b></p><p><b>　　case 1:</b></p><p>　　auto_calculation(L);</p><p><b>　　break;</b></p><p><b>　　case 2:</b></p><p&g

101、t;　　input_weight(L);</p><p><b>　　break;</b></p><p><b>　　default:</b></p><p>　　printf("選項(xiàng)輸入錯(cuò)誤，重新選擇(Y/N)？\n");</p><p>　　scanf("%c&q

102、uot;,&choice);</p><p><b>　　}</b></p><p>　　}while(choice=='y'||choice=='Y');</p><p>　　Creat_HuffmanTree(HT,L);</p><p>　　text_code(HT,L,n)

103、;</p><p>　　Calculte_Code(s,L);</p><p><b>　　}</b></p><p><b>　　else</b></p><p>　　printf("只有一個(gè)字符，無法構(gòu)造赫夫曼樹,無赫夫曼編碼！\n");</p><p&g

104、t;<b>　　}</b></p><p><b>　　調(diào)試結(jié)果</b></p><p>　　自動(dòng)統(tǒng)計(jì)的調(diào)試結(jié)果（截圖）：</p><p>　　手動(dòng)輸入權(quán)值的調(diào)試結(jié)果（截圖）：</p><p><b>　　課程設(shè)計(jì)總結(jié)：</b></p><p>　　赫夫

105、曼樹作為一種最優(yōu)二叉樹，它的特點(diǎn)就是樹的n個(gè)葉子結(jié)點(diǎn)的帶權(quán)路徑長度最短，樹的帶權(quán)路徑長度也是最短的，因此，赫夫曼樹在解決最佳判定問題以及最短編碼問題等領(lǐng)域有著重要的應(yīng)用。</p><p>　　本次課程設(shè)計(jì)就是利用赫夫曼樹對(duì)一段已知權(quán)值的字符串進(jìn)行赫夫曼編碼的應(yīng)用，赫夫曼編碼的特點(diǎn)是編碼最短，且在譯碼過程中不會(huì)產(chǎn)生歧義，當(dāng)用戶輸入一段字符串以后，我們可以根據(jù)用戶對(duì)每個(gè)字符賦的權(quán)值，或者可以根據(jù)統(tǒng)計(jì)出的每個(gè)字符在字符

106、串中出現(xiàn)的次數(shù)作為權(quán)值對(duì)每個(gè)字符求解赫夫曼編碼。</p><p>　　在整個(gè)程序設(shè)計(jì)中，我設(shè)計(jì)了兩個(gè)功能模塊供用戶選擇：一個(gè)是利用每個(gè)字符在字符串中出現(xiàn)的次數(shù)作為其權(quán)值對(duì)其進(jìn)行編碼；另一個(gè)就是根據(jù)用戶對(duì)每個(gè)字符自定義的權(quán)值對(duì)其進(jìn)行編碼。在程序設(shè)計(jì)中，我利用到了鏈表這種數(shù)據(jù)結(jié)構(gòu)對(duì)字符串中的字符種類個(gè)數(shù)進(jìn)行統(tǒng)計(jì)，同時(shí)通過查找鏈表結(jié)點(diǎn)，得到每個(gè)字符在字符串中出現(xiàn)的次數(shù)，這個(gè)次數(shù)可以作為自動(dòng)統(tǒng)計(jì)權(quán)值這一功能模塊的權(quán)值，如

107、果用戶選擇自定義每個(gè)字符的權(quán)值，直接對(duì)鏈表中每個(gè)結(jié)點(diǎn)中的權(quán)值重新賦值即可，因此，這個(gè)作為統(tǒng)計(jì)使用的鏈表在整個(gè)程序設(shè)計(jì)中起到了至關(guān)重要的作用，包括后續(xù)根據(jù)構(gòu)造好的赫夫曼樹對(duì)每個(gè)字符進(jìn)行編碼以及最后輸出編碼都使用到了這個(gè)鏈表。</p><p>　　通過本次課程設(shè)計(jì)，我對(duì)構(gòu)造赫夫曼樹的整個(gè)過程以及利用赫夫曼樹求解赫夫曼編碼的原理也有了一個(gè)完整和全面的掌握，對(duì)于以后相關(guān)編碼原理的學(xué)習(xí)也打下了堅(jiān)實(shí)的基礎(chǔ)，更重要的是在課程設(shè)

108、計(jì)中，我享受到了把自己腦袋中的想法變成現(xiàn)實(shí)以后的欣喜。</p><p><b>　　心得體會(huì)</b></p><p>　　通過這次課程設(shè)計(jì)，我的編程能力不僅得到了一個(gè)較大的提升，再一次鍛煉了我分析問題和解決問題的能力，因?yàn)槲易孕∽鍪卤阆矚g追求完美，對(duì)于老師提出的只是手動(dòng)對(duì)每個(gè)字符賦權(quán)值的這一要求，我感覺并不是很完美，因此，我想到增加一個(gè)讓字符串自動(dòng)獲得權(quán)值這一功能，并

109、且用戶可以自己選擇一種權(quán)值獲得方法。心中有了想法和思路以后，我便開始動(dòng)手設(shè)計(jì)，我先設(shè)計(jì)了程序的大體框架，然后將每個(gè)功能實(shí)現(xiàn)細(xì)分到每個(gè)函數(shù)上以后，我便開始動(dòng)手編寫程序，由于對(duì)赫夫曼樹的構(gòu)造以及編碼的算法還算比較了解，加上編程能力還算不錯(cuò)，因此整個(gè)算法的實(shí)現(xiàn)上幾乎沒有遇到什么困難，在較短的時(shí)間內(nèi)就把它做完了。</p><p>　　但是，這次課程設(shè)計(jì)花費(fèi)我大量精力和時(shí)間的環(huán)節(jié)是最后的課程設(shè)計(jì)報(bào)告，由于平時(shí)很少動(dòng)手畫流程

110、圖，而課程設(shè)計(jì)報(bào)告要求提供算法流程圖，為了畫出一個(gè)清晰明了的算法流程圖，我花了很多精力和時(shí)間，總共有七個(gè)流程圖，起初畫前兩個(gè)的時(shí)候，總是感覺畫得不夠好，別人有可能看不懂，而且又花了很多很多時(shí)間，便有點(diǎn)耐不住心了，但又為了做好整個(gè)課程設(shè)計(jì)，又強(qiáng)迫自己耐心繼續(xù)畫，在畫圖的過程中，我慢慢摸索出了一些簡便且效果很好的制圖方法，就是利用word中提供的制表功能可以快速簡潔地制作出清晰明了的N-S流程圖，這是我以前沒有發(fā)現(xiàn)的，因?yàn)橐郧白稣n程設(shè)計(jì)報(bào)告

111、畫N-S流程圖時(shí)，使用的總是通過一些矩形框和直線構(gòu)造一個(gè)N-S流程圖，這樣畫出來的效果不僅不美觀，而且為了對(duì)其線條，會(huì)花去大量的時(shí)間，而發(fā)現(xiàn)利用制表功能可以快速畫出美觀的N-S流程圖后，以前對(duì)N-S流程圖的恐懼感一下就沒了，在短短幾小時(shí)中，就完成了整個(gè)程序流程圖的繪制，并且效果比起原來的要好出了很多，感覺心里充滿著成就感和喜悅之情，相信在以后工作中，需要在項(xiàng)目設(shè)計(jì)報(bào)告中添加流程圖時(shí)，我也可以快速準(zhǔn)確的寫出讓老板和客戶滿意的報(bào)告，這應(yīng)該算