#include<stdio.h>
#include<conio.h>
#include<string.h>
/*
哈夫曼編碼示例程序
哈夫曼建樹算法描述：
1. 將所有權(quán)值分別構(gòu)造一個(gè)只有一個(gè)結(jié)點(diǎn)的二叉樹結(jié)點(diǎn)，將這些結(jié)點(diǎn)加入集合A（哈夫曼森林）
2. 檢查集合A成員的個(gè)數(shù)，如果為1，則算法結(jié)束，集合A中唯一的結(jié)點(diǎn)為哈夫曼樹的根。
3. 從集合A中取出根結(jié)點(diǎn)權(quán)值最小的兩棵樹a, b，集合中不再保留這兩棵樹。
4. 由a和b分別為左、右子樹構(gòu)造一個(gè)新的二叉樹r, 令r的權(quán)值等于a的權(quán)值與b的權(quán)值之和。
5. 將r加入到集合A中，返回第 2 步。
*/

struct HuffmanNode /*哈夫曼樹結(jié)點(diǎn)類型*/
{
    char data;               /*結(jié)點(diǎn)上的數(shù)據(jù)*/
    int power;               /*結(jié)點(diǎn)的權(quán)值*/
    HuffmanNode *lchild;     /*左分支(作為二叉樹結(jié)點(diǎn)時(shí)用)*/
    HuffmanNode *rchild;     /*右分支(作為二叉樹結(jié)點(diǎn)時(shí)用)*/
    HuffmanNode *next;       /*后繼指針(作為單鏈表結(jié)點(diǎn)時(shí)用)*/
};

/*給Huffman森林（按各樹根結(jié)點(diǎn)的值升序排列的帶頭結(jié)點(diǎn)的鏈表）添加一棵Huffman樹使得鏈表仍然有序  */
void AddNode(HuffmanNode *headNode, HuffmanNode *pNode)
{
    HuffmanNode *p = headNode;
    /*  找到第一個(gè)權(quán)值小于給定結(jié)點(diǎn)的結(jié)點(diǎn)，p指定該結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)  */
    while (p->next && p->next->power < pNode->power) p = p->next;
    pNode->next = p->next;
    p->next = pNode;
}
/*    功能：構(gòu)造哈夫曼樹  */
/*    參數(shù)說明  */
/*    n: 字符的個(gè)數(shù)  */
/*    datas: 要統(tǒng)計(jì)的字符  */
/*    powers: 字符對(duì)應(yīng)的權(quán)值(出現(xiàn)的次數(shù))   */
HuffmanNode* CreateHuffmanTree(int n, char datas[], int powers[])
{
    HuffmanNode head;
    head.next = NULL; //初始化森林
    for (int i = 0; i < n; i++)
    {
        HuffmanNode *pNode = new HuffmanNode;
        pNode->data = datas[i];
        pNode->power = powers[i];
        pNode->lchild = pNode->rchild = pNode->next = NULL;
        AddNode(&head, pNode);
    }
    /*開始構(gòu)造      */
    while (head.next)
    {
        if (!head.next->next) /*只剩最后一個(gè)結(jié)點(diǎn)，這就是根 */
        {
            return head.next;
        }
        /* 取前兩個(gè)出來構(gòu)造一棵新樹（因?yàn)殒湵硪呀?jīng)按權(quán)值升序排列了，前兩個(gè)就是最小的兩個(gè)）    */
        HuffmanNode *pN1, *pN2, *pRoot;
        pN1 = head.next;              /*第一個(gè)結(jié)點(diǎn)     */
        pN2 = pN1->next;              /*第二個(gè)結(jié)點(diǎn)     */
        head.next = pN2->next;        /*將這兩個(gè)結(jié)點(diǎn)從鏈表中刪除     */
        pRoot = new HuffmanNode;    /*為這兩個(gè)結(jié)點(diǎn)建立根結(jié)點(diǎn) */
        pRoot->power = pN1->power + pN2->power; /*權(quán)值相加  */
        pRoot->lchild = pN1;          /*左分支為第一個(gè)結(jié)點(diǎn)  */
        pRoot->rchild = pN2;          /*右分支為第二個(gè)結(jié)點(diǎn)  */
        /* 將新的根加入哈夫曼森林   */
        AddNode(&head, pRoot);
    }
    return NULL;
}

/*     計(jì)算哈夫曼樹的帶權(quán)路徑長度PWL       */
/*     node: 樹結(jié)點(diǎn)        */
/*     level: 當(dāng)前層數(shù)        */
int GetPWL(HuffmanNode *node, int level)
{
    if (!node) return 0;
    if (!node->lchild && !node->rchild) return node->power * level;       /*     是葉結(jié)點(diǎn)        */
    return GetPWL(node->lchild, level + 1) + GetPWL(node->rchild, level+1);
}

/*    獲取所有葉點(diǎn)的哈夫曼編碼    */
/*    node: 樹結(jié)點(diǎn)                */
/*    code: 上層前綴              */
void GetCodes(HuffmanNode *node, const char *code)
{
    if (!node->lchild && !node->rchild)
    {
        /*是葉結(jié)點(diǎn)，打印編碼    */
	printf("%c %d %s\n",node->data,node->power,code);
        /*cout << node->data << " " << node->power << " " << code << endl;       */
        return;
    }

    int len = strlen(code);
    char *newcode = new char[len+2];
    strcpy(newcode, code);
    newcode[len+1] = '\0';
    if (node->lchild)          /*左分支分配'1'        */
    {
        newcode[len] = '1';
        GetCodes(node->lchild, newcode);
    }
    if (node->rchild)         /*右分支分配'0'        */
    {
        newcode[len] = '0';
        GetCodes(node->rchild, newcode);
    }
    delete[] newcode;
}

/*     釋放所有結(jié)點(diǎn),要按二叉樹的方式        */
void FreeNodes(HuffmanNode *node)
{
    if (!node) return;
    FreeNodes(node->lchild);
    FreeNodes(node->rchild);
    delete node;
}
/*請(qǐng)嘗試改變主函數(shù)，使之能統(tǒng)計(jì)指定文本文件中的各字母出現(xiàn)的次數(shù)，然后給這些字母編碼，并將文本文件的內(nèi)容編碼后輸出到out.txt中      */

int main()
{
    int n, pow,i=0;
    char ch, *datas = new char[n];
    float total=0;
    do
    {
        printf("請(qǐng)輸入字母個(gè)數(shù):\t: ");
        scanf("%d",&n);
    } while (n < 1);
    int *pows = new int[n];
	for(i=0;i< n;i++)
	{
		printf("請(qǐng)輸入符號(hào) %d ---> ",i+1);
		scanf("%s",&ch);
		datas[i]=ch;
	}
	for(i=0;i< n;i++)
	{
		printf("\n\t請(qǐng)輸入次數(shù) %c ---> ",datas[i]);
		scanf("%d",&pow);
		pows[i]=pow;
		total=total+pows[i];
	}

    HuffmanNode *root = CreateHuffmanTree(n, datas, pows);
    printf("構(gòu)造出哈夫曼樹的權(quán)值為：%d\n",GetPWL(root, 0));
    printf("所有字母的哈夫曼編碼如下：\n");
    GetCodes(root, "");
    FreeNodes(root);
    delete[] datas;
    delete[] pows;
    return 1;
}