一 簡單字符串壓縮

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

壓縮規則：

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

#include <stdio.h> #include <string.h> #include <stdlib.h>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<length);res[k] = '\0';printf("The result is : %s\n",res);return 0; }

運行情況：

二 哈夫曼編碼

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

//用Ｃ語言實現Huffman編碼，并計算本節中塊的編碼 //長度（以位為單位），計算Ｈuffman編碼的壓縮比。 //主程序： #include<stdio.h> #include<stdlib.h>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<Length; i++){*(maNode + i) = Node[i];//拷貝有效節點*(maWeight + i) = Weight[i];//拷貝有效權重}//根據權重與有效節點數創建霍夫曼樹HfStruct p = create_HuffmanTree(maWeight, Length);//打印霍夫曼樹printf("霍夫曼樹:\n");for (i = 0; i<2 * Length - 1; i++)printf("父節點:%3d,左子節點:%3d,右子節點:%3d,權重:%3d\n", p[i].parent, p[i].lchild, p[i].rchild, p[i].weight);HCodeType code[9];//依據霍夫曼樹進行編碼HuffmanCoding(p, code, Length);//霍夫曼編碼//打印出編碼結果printf("\n編碼結果:\n");for (i = 0; i<Length; i++){printf("節點:%3d,權重:%3d,編碼:", *(maNode + i), *(maWeight + i));for (j = code[i].start + 1; j < Length; j++)printf("%c", code[i].code[j]);printf("\n");}//計算編碼后的總的比特數,計算壓縮比for (i = 0; i<Length; i++){j = Length - 1 - code[i].start;totalbits = totalbits + maWeight[i] * j;}printf("\n編碼后的總位數為:%d,壓縮比為:%4.2f\n", totalbits, (double)(64 * 8) / totalbits);while (1); }short QuanTable[8][8] = {{ 16, 11, 10, 16, 24, 40, 51, 61 },{ 12, 12, 14, 19, 26, 58, 60, 55 },{ 14, 13, 16, 24, 40, 57, 69, 56 },{ 14, 17, 22, 29, 51, 87, 80, 62 },{ 18, 22, 37, 56, 68, 109, 103, 77 },{ 24, 35, 55, 64, 81, 104, 113, 92 },{ 49, 64, 78, 87, 103, 121, 120, 101 },{ 72, 92, 95, 98, 112, 100, 103, 99 } };//量化表void print_data_screen(short data[8][8])//數據打印 {int x, y;for (x = 0; x<8; x++)for (y = 0; y<8; y++){printf("%d", data[x][y]);if (y == 7){if (x == 7)printf("\n\n");elseprintf("\n");}else{printf(",");}}}void quanDCT(short(*data)[8], short(*result)[8])//數據量化 {int x, y;for (x = 0; x<8; x++){for (y = 0; y<8; y++){*(*(result + x) + y) = (short)(double(*(*(data + x) + y)) / QuanTable[x][y] + 0.5);}} }int calWeight(short(*result), int *Node, int *Weigh)//計算權重 {int x, y, i, find = 0;for (x = 0; x<64; x++){Node[x] = 0;Weigh[x] = 0;}Node[0] = (*result);Weigh[0] = 1;i = 0;for (x = 1; x<64; x++){for (y = 0; y <= i; y++){if (*(x + result) == Node[y]){Weigh[y]++;find = 1;break;}}if (find){find = 0;continue;}else{i++;Node[y] = *(x + result);Weigh[y]++;}}return i + 1;}/* 從HtStruct選出權重最小，并且沒有父節點的節點 */ int WeightMinNode(HfStruct HtStruct, int Mum) {int i = 0; //序號, 循環用int min; //最小權重序號int MinWeight; //最小權重//首先選擇一個節點，用于比較出最小的一個while (HtStruct[i].parent != -1)i++;MinWeight = HtStruct[i].weight;min = i;//選出weight最小且parent為-1的元素，并將其序號賦給min for (; i<Mum; i++){if (HtStruct[i].weight<MinWeight&&HtStruct[i].parent == -1){MinWeight = HtStruct[i].weight;min = i;}}//選出weight最小的元素后，將其parent置1，使得下一次比較時將其排除在外。HtStruct[min].parent = 1;return min; }/* 從HtStruct數組的前k個元素中選出weight最小且parent為-1的兩個，分別將其序號保存在min1和min2中 */ void ChoseMinium2(HfStruct HtStruct, int Mum, int *min1, int *min2) {*min1 = WeightMinNode(HtStruct, Mum);*min2 = WeightMinNode(HtStruct, Mum); }/* 根據給定的n個權值構造一棵赫夫曼樹 */ HfStruct create_HuffmanTree(int *WeightPoint, int n) {//一棵有n個葉子節點的赫夫曼樹共有2n-1個節點int AllNodeNum = 2 * n - 1;HfStruct HT = (HfStruct)malloc(AllNodeNum*sizeof(Struct));int i;//葉子節點初始化,將傳入的數據加載到葉子節點上for (i = 0; i<n; i++){HT[i].parent = -1;HT[i].lchild = -1;HT[i].rchild = -1;HT[i].weight = *WeightPoint;WeightPoint++;}//HT[n],HT[n+1]...HT[2n-2]中存放的是中間構造出的每棵二叉樹的根節點for (; i<AllNodeNum; i++){HT[i].parent = -1; //父節點初始化HT[i].lchild = -1; //左子節點初始化HT[i].rchild = -1; //右子節點初始化HT[i].weight = 0; //權重初始化}int min1, min2;int *ad_min1 = &min1;//用于傳遞最小權重的節點int *ad_min2 = &min2; //用于傳遞最小權重的節點//每一輪比較后選擇出min1和min2構成一課二叉樹,最后構成一棵赫夫曼樹for (i = n; i<AllNodeNum; i++){ChoseMinium2(HT, i, ad_min1, ad_min2); //選出權重最小的兩個節點HT[min1].parent = i; //父節點賦值HT[min2].parent = i; //父節點賦值HT[i].lchild = min1; //左子節點賦值HT[i].rchild = min2; //右子節點賦值HT[i].weight = HT[min1].weight + HT[min2].weight; //權重為兩個子節點權重之和}return HT; } /* 從葉子節點到根節點逆向求赫夫曼樹HT中n個葉子節點的赫夫曼編碼，并保存在code中 */ void HuffmanCoding(HfStruct HT, HCodeType HuffCode[], int n) {HCodeType cd;int i,j,current,father;for (i = 0; i<n; i++){cd.start = n - 1;current = i; //定義當前訪問的節點father = HT[i].parent; //當前節點的父節點//從葉子節點向上搜索while (father != -1){if (HT[father].lchild == current) //如果是左子節點，則編碼為0 cd.code[cd.start--] = '0';else//如果是右子節點，則編碼為1 cd.code[cd.start--] = '1';current = father;father = HT[father].parent;}for (j = cd.start + 1; j <n; j++)HuffCode[i].code[j] = cd.code[j];HuffCode[i].start = cd.start;} }

總結

以上是生活随笔為你收集整理的C语言实现压缩二例的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。