/*
 * 程序功能：對文本文件success.dat進行霍夫曼編碼，用文本文件coding.dat保存編碼
 * 編程思路：
   第一步：
       首先打開掃描文件success.dat，統計出每個字符出現的次數，作為各個字符的權，
   在這里我假設文本文件里面的字符只包含a~z這26個小寫字母，用CharCount函數掃描文件，統計
   出各個字符在文件中出現的次數(注意，如果某個字符一個都沒出現，那就設它的權為1，因為權
   是0的話將不能正確編碼，血的教訓) CharCount函數的原型如下：
   void CharCount(FILE *fp, int *Count, int length);
   其中fp是要掃描的文件的指針，數組Count的每個元素分別用來統計a,b..z在文件中出現的次數，
   length是數組的長度。

   第二步：
       根據給定的字符集(這里設字符集為a~z這26個小寫字母)， 和各字符的權(用CharCount函數得到的)，
   創建哈夫曼樹，函數原型如下：
   void createHTree(HuffmanTree HT, char *c, int *w, int n);
   其中數組c[0..n-1]就是要編碼的字符集，w[0..n-1]就是Count函數得到的各字符的權，構造霍夫曼樹HT

   第三步：
       對霍夫曼樹中的n個葉子結點進行編碼，第i個葉子結點的編碼存放在HC[i]中(1 <= i <= n)
	函數原型如下：
	void HuffmanCoding(HuffmanTree HT, HuffmanCode HC, int n);
	若中HT是構造的一棵霍夫曼樹，HC是一個字符串數組，n是霍夫曼樹葉子結點的數目

   第四步：
       對文本文件success.dat進行霍夫曼編碼，用文本文件coding.dat保存編碼，函數原型如下：
       void Coding(HuffmanTree HT, HuffmanCode HC, int n);
    其中HT是構造好的一棵霍夫曼樹，HC是保存著霍夫曼樹各葉子結點編碼的字符串數組，n是葉子結點
	的數目。
	    這個函數以讀方式打開success.dat和寫方式打開coding.dat，然后從success.dat里面讀一個字符，
	在字符串數組HC中找出該字符的編碼，寫入coding.dat文件，直到success.dat讀完為止。 

 * Copyright (c) 2006 All rights reserved.
 * 文件名：HuffmanCoding.c
 *
 * 文件標識：霍夫曼編碼
 * 摘要：對文本文件success.dat進行霍夫曼編碼，用文本文件coding.dat保存編碼
 * 輸入：無
 * 輸出：輸出一個霍夫曼編碼文件(文件內容是0或1的字符序)
 *
 * 當前版本 0.01
 * 作者：羅
 * 完成日期：2006年4月4日
 */


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXLEAFNUM 50    /* 葉子結點的最大數目 */

/* 定義一個霍夫曼樹的結構 */
typedef struct node
{
    char ch;                   /* 當前結點表示的字符，對于非葉子結點，此域不用 */
	int weight;                /* 當前結點的權值 */
    int parent;                /* 當前結點的父結點下標，為0表示無父結點 */
    int lchild, rchild;        /* 當前結點左右孩子結點的下標，都為0時表示無孩子結點 */
} HuffmanTree[2*MAXLEAFNUM];
typedef char* HuffmanCode[MAXLEAFNUM+1];

/* 在HT[1~n]中選擇weigth最小的且parent為0的結點，用p1,p2帶回 */
void select(HuffmanTree HT, int n, int *p1, int *p2);

/* 根據給定的字符集創建哈夫曼樹 */
void createHTree(HuffmanTree HT, char *c, int *w, int n);

/* n個葉子結點在霍夫曼樹HT中的下標為1~n，第i(i<=i<=n)個葉子的編碼存放HC[i]中 */
void HuffmanCoding(HuffmanTree HT, HuffmanCode HC, int n);

/* 利用具有n個字符的霍夫曼編碼的編碼集（1~n）對字符逐個進行編碼 */
/* 最后把編碼存儲在buff 所指向的字符指針中 */
void Coding(HuffmanTree HT, HuffmanCode HC, int n);


/* 統計字符在文件中出現的次數，并作為該字符的權進行霍夫曼編碼 */
void CharCount(FILE *fp, int *Count, int length);

//函數功能：在HT[1~n]中選擇weigth最小的且parent為0的結點，用p1,p2帶回
//參數：HT為n棵霍夫曼樹，p1和p2用來帶回weight最小的且parent為0的兩個結點
//返回值：無
void select(HuffmanTree HT, int n, int *p1, int *p2)
{
	static int first = 1;
	int k, i;
	while (HT[first].parent != 0)
		first++;
	k = first;
	for (i = first+1; i <= n; i++)
	if ((HT[i].parent == 0) && (HT[i].weight < HT[k].weight))
	{
		k = i;
	}
	if (k = first)
	{
		first++;
		while (HT[first].parent != 0)
			first++;
	}
	*p1 = k;

	k = first;
	for (i = first+1; i <= n; i++)
	if ((HT[i].parent == 0) && (HT[i].weight < HT[k].weight) &&(i != *p1))
	{
		k = i;
	}
	if (k == first)
	{
		first++;
		while (HT[first].parent != 0)
			first++;
	}
	*p2 = k;
}


/* 
 * 函數功能：創建霍夫曼樹
 * 參數：數組c[0..n-1]和w[0..n-1]存放了n個字符，以及其概率，構造霍夫曼樹HT
 * 返回值：無
*/
void createHTree(HuffmanTree HT, char *c, int *w, int n)
{
	int i, s1, s2;
	if (n <= 1)
		return;
	/* 根據n個權值構造n棵只有根結點的二叉樹 */
	for (i = 1; i <= n; i++)
	{
		HT[i].ch = c[i-1];
		HT[i].weight = w[i-1];
		HT[i].parent = HT[i].lchild = HT[i].rchild = 0;
	}

	for (; i < 2*n; i++)
	{
		HT[i].parent = HT[i].lchild = HT[i].rchild = 0;
	}

	/* 構造霍夫曼樹，從HT[1.. i-1]中選擇parent 為0,且weight最小的兩棵樹，其序號為s1和s2 */
    for (i = n+1; i < 2*n; i++)
	{
		select(HT, i-1, &s1, &s2);
		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;
	}
}

/* 
 * 函數功能：對霍夫曼樹中的葉子結點進行編碼，第i個結點的編碼放在HC[i]中(1 <= i <= n)
 * 參數：HT為一棵霍夫曼樹，HC為一個存放霍夫曼編碼的字符串數組，n為葉子的個數
 * 返回值：無
*/
void HuffmanCoding(HuffmanTree HT, HuffmanCode HC, int n)
{
    /*n個葉子結點在霍夫曼樹HT中的下標為1~n，第i(i<=i<=n)個葉子的編碼存放HC[i]中*/
    char *cd;
    int i, start, c, f;
    if (n <= 1)
        return;
    cd = (char *)malloc(n);
    cd[n-1] = '\0';
    i = 1;
    while (i <= n)
    {
        start = n-1;
        for (c=i, f=HT[c].parent; f!=0; c=f, f=HT[c].parent)
        {
            if (HT[f].lchild == c)
               cd[--start] = '1';
            else
               cd[--start] = '0';
        }
        HC[i] = (char *)malloc(n - start);
        strcpy(HC[i], &cd[start]);
        i++;
    } 
}


/*
 * 函數功能： 利用具有n個字符的霍夫曼編碼的編碼集（1~n）對字符逐個進行編碼
 * 最后把編碼存儲在buff 所指向的字符指針中
 * 參數：一棵霍夫曼樹，字符集
*/
void Coding(HuffmanTree HT, HuffmanCode HC, int n)
{
	char ch;
	int i;
	FILE *IN, *OUT;

	if ((IN = fopen("success.dat", "r")) == NULL)
	{
		printf("File Open Error!\n");
		exit(1);
	}

	if ((OUT = fopen("coding.dat", "w+")) == NULL)
	{
		printf("File Open Error!\n");
		exit(1);
	}

	while (!feof(IN))
	{
		ch = fgetc(IN);
		i = 1;
		while ((HT[i].ch != ch) && (i <= n))
		{
			i++;
			if (i > n)
				return;
		}

		/* 將ch代表的字符的編碼寫入到輸出文件 */
		fputs(HC[i], OUT);
	}

	fclose(IN);
	fclose(OUT);
}


/*
 * 函數名：CharCount
 * 參數：一個指向文件的指針，以及一個整型數組
 * 函數功能：統計文件中每個字符出現的次數，由Count數組帶回字符出現的次數
 * 返回值：無
*/
void CharCount(FILE *fp, int *Count, int length)
{
	char ch;
	int i;
	/* 如果某個字符在文件中沒有出現，則它的權為1 */
	for (i = 0; i < length; i++)
	{
		Count[i]=1;
	}

	/* 碰到一個出現的字符，就將它的權增1 */
	while (!feof(fp))
	{
		ch = fgetc(fp);
		Count[(ch) - 97]++;
	}
}

int main(int argc, char* argv[])
{
	/* 要進行霍夫曼編碼的字符集 */
    char CharSet[] = "abcdefghijklmnopqrstuvwxyz";

    /* 字符的權 */
    static int weight[26];

	/* 字符集字符個數 */
	int size, i;
    
	/* 霍夫曼樹變量 */

    HuffmanTree HT;
	/* 霍夫曼編碼集 */
	HuffmanCode HC;

	FILE *IN;

	if ((IN = fopen("success.dat", "r")) == NULL)
	{
		printf("File Open Error!\n");
		exit(1);
	}


	size = strlen(CharSet); 
	/* 統計各個字符在文件中出現的次數 */
    CharCount(IN, weight, size);

	/* 輸出各字符在文件中出現的次數，次數為1表示在文件中沒有出現該字符 */
	printf("各個字符的權為：\n");
	for (i = 0; i < size; i++)
	{
		printf("%3d", weight[i]);
		if ((i+1) % 10 == 0)
			printf("\n");
	}
	printf("\n");
	fclose(IN);

	/* 根據字符集和權值創建霍夫曼樹 */
	createHTree(HT, CharSet, weight, size);

	/* 對哈夫曼樹中的葉子結點進行編碼 */
	HuffmanCoding(HT, HC, size);
	/* 輸出各個字符對應的編碼 */
	printf("各個字符的編碼分別為：\n");
	for (i = 1; i <= size; i++)
	{
		printf("%c = %s\n", HT[i].ch, HC[i]);
	}

	/* 對文件進行編碼，執行完后看看你的當前工作目錄下的coding.dat文件，是不是有字符編碼了 */
	Coding(HT, HC, size);

	return 0;
}