一 簡單字符串壓縮

編寫一個字符串壓縮程序，將字符串中連續出席的重復字母進行壓縮，並輸出壓縮後的字符串。

壓縮規則：

1、僅壓縮連續重復出現的字符。比如字符串”abcbc”由於無連續重復字符，壓縮後的字符串還是”abcbc”。
2、壓縮字段的格式為”字符重復的次數+字符”。例如：字符串”xxxyyyyyyz”壓縮後就成為”3x6yz”。

#include 
#include 
#include 

int main()
{ 
    char str[100] = {'\0'};
    char res[100] = {'\0'};
    scanf("%s",str);
    int length = strlen(str);
    int i=0, j=0, k=0;
    int count = 0;
    do
    {
        if(i < length && str[i++] == str[j])
            count++;
        if(str[i] != str[j])
        {
            if(count <= 1)
                res[k++] = str[j];
            else
            {
                if(count > 1)
                {
                    char temp[10] = {'\0'};
                    itoa(count,temp,10);
                    strcpy(res+k,temp);
                    k+=strlen(temp);
                    res[k++] = str[j];
                }
            }
            j = i;
            count = 0;
        }
    }while(i

運行情況：

二 哈夫曼編碼

哈夫曼樹─即最優二叉樹，帶權路徑長度最小的二叉樹，經常應用於數據壓縮。 在計算機信息處理中， “哈夫曼編碼”是一種一致性編碼法（又稱“熵編碼法”），用於數據的無損耗壓縮。這一術語是指使用一張特殊的編碼表將源字符（例如某文件中的一個符號）進行編碼。這張編碼表的特殊之處在於，它是根據每一個源字符出現的估算概率而建立起來的（出現概率高的字符使用較短的編碼，反之出現概率低的則使用較長的編碼，這便使編碼之後的字符串的平均期望長度降低，從而達到無損壓縮數據的目的）。這種方法是由David.A.Huffman發展起來的。 例如，在英文中，e的出現概率很高，而z的出現概率則最低。當利用哈夫曼編碼對一篇英文進行壓縮時，e極有可能用一個位 哈弗曼編碼在信息論中應用舉例哈弗曼編碼在信息論中應用舉例 (bit)來表示，而z則可能花去25個位（不是26）。用普通的表示方法時，每個英文字母均占用一個字節（byte），即8個位。二者相比，e使用了一般編碼的1/8的長度，z則使用了3倍多。若能實現對於英文中各個字母出現概率的較准確的估算，就可以大幅度提高無損壓縮的比例。

//用Ｃ語言實現Huffman編碼，並計算本節中塊的編碼
//長度（以位為單位），計算Ｈuffman編碼的壓縮比。
//主程序：
#include
#include

typedef struct HfTreeNode
{
	int weight; //權重
	int parent; //父節點
	int lchild, rchild;   //兩個子節點
}Struct, *HfStruct;

typedef struct{
	char code[10];
	int start;
}HCodeType;

void quanDCT(short(*data)[8], short(*result)[8]);//量化函數
int calWeight(short(*result), int(*Node), int(*Weight));//權重計算
void print_data_screen(short data[8][8]);//數據打印

//待編碼數據
short DctData[8][8] = {
	{ 1149, 38, -43, -10, 25, -83, 10, 40 },
	{ -81, -3, 114, -73, -6, -2, 21, -5 },
	{ 13, -11, 0, -42, 25, -3, 16, -38 },
	{ 1, -61, -13, -12, 35, -23, -18, 4 },
	{ 43, 12, 36, -4, 9, -21, 6, -8 },
	{ 35, -11, -9, -4, 19, -28, -21, 13 },
	{ -19, -7, 20, -6, 2, 2, 11, -21 },
	{ -5, -13, -11, -17, -4, -1, 6, -4 } };

HfStruct create_HuffmanTree(int *WeightPoint, int n);//霍夫曼樹創建函數
void HuffmanCoding(HfStruct HT, HCodeType HuffCode[], int n);//霍夫曼編碼函數

void main()
{
	int i, j;//循環變量
	int Length;//編碼節點數
	int totalbits = 0;//計算編碼後的總的比特數

	int Node[64];//節點數組
	int Weight[64];//權重數組

	short QuanResult[8][8];//量化結果存儲
	quanDCT(DctData, QuanResult);//數據量化
	printf("量化後的數據:\n");//打印量化數據
	print_data_screen(QuanResult);

	Length = calWeight(*QuanResult, Node, Weight);//計算量化數據的節點與權重，並返回節點數

	int *maNode = (int*)malloc(Length*sizeof(int));//按有效節點進行分配
	int *maWeight = (int*)malloc(Length*sizeof(int));//按有效節點進行分配
	for (i = 0; i