匿名使用者2007.01.28 回答

去年做的課程設計，有什麼不合要求的自己改改 #include

#include

#include

int m，s1，s2； typedef struct { unsigned int weight； unsigned int parent，lchild，rchild； }HTNode，*HuffmanTree； //動態分配陣列儲存哈夫曼樹 typedef char *HuffmanCode； //動態分配陣列儲存哈夫曼編碼表 void Select（HuffmanTree HT，int n） { int i，j； for（i = 1；i <= n；i++） if（！HT［i］。parent）{s1 = i；break；} for（j = i+1；j <= n；j++） if（！HT［j］。parent）{s2 = j；break；} for（i = 1；i <= n；i++） if（（HT［s1］。weight>HT［i］。weight）&&（！HT［i］。parent）&&（s2！=i））s1=i； for（j = 1；j <= n；j++） if（（HT［s2］。weight>HT［j］。weight）&&（！HT［j］。parent）&&（s1！=j））s2=j； } void HuffmanCoding（HuffmanTree &HT， HuffmanCode HC［］， int *w， int n） { // 演算法6。13 // w存放n個字元的權值（均>0），構造哈夫曼樹HT， // 並求出n個字元的哈夫曼編碼HC int i， j； char *cd； int p； int cdlen； if （n<=1） return； m = 2 * n - 1； HT = （HuffmanTree）malloc（（m+1） * sizeof（HTNode））； // 0號單元未用 for （i=1； i<=n； i++） { //初始化 HT［i］。weight=w［i-1］； HT［i］。parent=0； HT［i］。lchild=0； HT［i］。rchild=0； } for （i=n+1； i<=m； i++） { //初始化 HT［i］。weight=0； HT［i］。parent=0； HT［i］。lchild=0； HT［i］。rchild=0； } puts（“\n哈夫曼樹的構造過程如下所示：”）； printf（“HT初態：\n 結點 weight parent lchild rchild”）； for （i=1； i<=m； i++） printf（“\n%4d%8d%8d%8d%8d”，i，HT［i］。weight， HT［i］。parent，HT［i］。lchild， HT［i］。rchild）； printf（“ 按任意鍵，繼續 。。。”）； getchar（）； for （i=n+1； i<=m； i++） { // 建哈夫曼樹 // 在HT［1。。i-1］中選擇parent為0且weight最小的兩個結點， // 其序號分別為s1和s2。 Select（HT， i-1）； HT［s1］。parent = i； HT［s2］。parent = i； HT［i］。lchild = s1； HT［i］。rchild = s2； HT［i］。weight = HT［s1］。weight + HT［s2］。weight； printf（“\nselect： s1=%d s2=%d\n”， s1， s2）； printf（“ 結點 weight parent lchild rchild”）； for （j=1； j<=i； j++） printf（“\n%4d%8d%8d%8d%8d”，j，HT［j］。weight， HT［j］。parent，HT［j］。lchild， HT［j］。rchild）； printf（“ 按任意鍵，繼續 。。。”）； getchar（）； } //————無棧非遞迴遍歷哈夫曼樹，求哈夫曼編碼 cd = （char *）malloc（n*sizeof（char））； // 分配求編碼的工作空間 p = m； cdlen = 0； for （i=1； i<=m； ++i） // 遍歷哈夫曼樹時用作結點狀態標誌 HT［i］。weight = 0； while （p） { if （HT［p］。weight==0） { // 向左 HT［p］。weight = 1； if （HT［p］。lchild ！= 0） { p = HT［p］。lchild； cd［cdlen++］ =‘0’； } else if （HT［p］。rchild == 0） { // 登記葉子結點的字元的編碼 HC［p］ = （char *）malloc（（cdlen+1） * sizeof（char））； cd［cdlen］ =‘\0’； strcpy（HC［p］， cd）； // 複製編碼（串） } } else if （HT［p］。weight==1） { // 向右 HT［p］。weight = 2； if （HT［p］。rchild ！= 0） { p = HT［p］。rchild； cd［cdlen++］ =‘1’； } } else { // HT［p］。weight==2，退回退到父結點，編碼長度減1 HT［p］。weight = 0； p = HT［p］。parent； ——cdlen； } } } // HuffmanCoding void main（） { HuffmanTree HT；HuffmanCode *HC；int *w，n，i； puts（“輸入結點數：”）； scanf（“%d”，&n）； HC = （HuffmanCode *）malloc（n*sizeof（HuffmanCode））； w = （int *）malloc（n*sizeof（int））； printf（“輸入%d個結點的權值\n”，n）； for（i = 0；i < n；i++） scanf（“%d”，&w［i］）； HuffmanCoding（HT，HC，w，n）； puts（“\n各結點的哈夫曼編碼：”）； for（i = 1；i <= n；i++） printf（“%2d（%4d）：%s\n”，i，w［i-1］，HC［i］）； getchar（）； }