Huffman full

[Minhquy2003iothust]

//Khai bao thu vien trong Dev C

include

include

include

include /

//Khai báo biến cục bộ

define doLonCayHuffman 100

//Ham xu li input void input(char c[1000], char kiTu[1000], int tanSuat[1000]){ //Dem so lan xuat hien moi ki tu trong xau int cnt[256]={0}; for(int i = 0; i < strlen(c); ++i){ cnt[(int)c[i]]++; }

//Tao 2 mang moi luu ki tu va tan suat tuong ung
int kiTu_cnt = 0, tanSuat_cnt = 0;
for (int i = 0; i < 256; ++i){
    if (cnt[i] != 0) {
        kiTu[kiTu_cnt]=i;
        tanSuat[tanSuat_cnt]=cnt[i];
        ++ kiTu_cnt;
        ++ tanSuat_cnt;
    }
}

}

//Ham dem so luong ki tu trong xau int soLuongKiTu(char c[1000]){ int cnt[256]={0}; for(int i = 0; i < strlen(c); ++i){ cnt[(int)c[i]]++; } int count = 0; for (int i = 0; i < 256; ++i){ if (cnt[i] != 0) count++; } return count; }

//Ham shannon void shannon(char kiTu[1000], int tanSuat[1000], int doDaiXau, int kichThuoc){ //Mang chua xac suat cua cac ki tu float xacSuat[1000];
//Bien tam float temp_1, temp_2; //Sap xep cac ki tu theo chieu xac suat giam dan for(int i = 0; i < kichThuoc; ++i){ for(int j = i + 1; j < kichThuoc; ++j){ if(tanSuat[i] < tanSuat[j]){ temp_1 = tanSuat[i]; tanSuat[i] = tanSuat[j]; tanSuat[j] = temp_1;
temp_2 = kiTu[i]; kiTu[i] = kiTu[j]; kiTu[j] = temp_2;
} } } for(int i = 0; i < kichThuoc; ++i){ xacSuat[i] = (double) tanSuat[i] / doDaiXau; }

//Mang luu do dai tu ma
int l[100];
for(int i = 0; i < kichThuoc; ++i){
    double x = - (log(xacSuat[i]) / log(2)) + 1;
    l[i] = (int)x; 
}

// Tinh gia tri Pi
float p[100]; 
for(int i = 0; i < kichThuoc; ++i){
    p[i+1] = xacSuat[i] + p[i];
}

// In ra tu ma
for(int i = 0; i < kichThuoc; ++i){
    printf("%c: ", kiTu[i]);
    for(int j = 0; j < l[i]; ++j){
        if((p[i] - pow(2,-j-1)) >= 0){
            printf("1");
            p[i] = p[i] - pow(2,-j-1);
        }
        else 
            printf("0");
    }
    printf("\n");
}

}

//Nút cây Huffman struct huffmanNode { //Kí tự đầu vào char kiTu; //Tần suất của kí tự unsigned tanSuat; //Hai nút con struct huffmanNode left, right; };

//Tập hợp các nút cây struct huffmanTree { //kích thước cây unsigned kichThuoc; //sức chứa của cây unsigned sucChua; //Mảng con trỏ vào nút struct huffmanNode **array; };

//hàm tạo ra nút với các thông số của kí tự đầu vào struct huffmanNode *node (char kiTu, unsigned tanSuat) {

//temp là 1 biến tạm lưu nút
struct huffmanNode *temp = (struct huffmanNode*)malloc(sizeof(struct huffmanNode));
temp->left = temp->right = NULL;
temp->kiTu = kiTu;
temp->tanSuat = tanSuat;
return temp;

}

//Hàm tạo cây với sức chứa đã cho struct huffmanTree createTree(unsigned sucChua) { struct huffmanTree tree = (struct huffmanTree*)malloc(sizeof(struct huffmanTree)); //ban đầu để kích thước là 0 tree->kichThuoc = 0; tree->sucChua = sucChua; tree->array = (struct huffmanNode*)malloc(tree->sucChua sizeof(struct huffmanNode*)); return tree; }

//Hàm tráo hai nút void swapNode(struct huffmanNode a, struct huffmanNode b) { struct huffmanNode temp = a; a = b; *b = temp; }

//Hàm tạo cấu trúc minheap cho cây Huffman void minHeap (struct huffmanTree tree, int i) { int min = i; int left = 2i; int right = 2*i + 1; if (left < tree->kichThuoc && tree->array[left]->tanSuat < tree->array[min]->tanSuat) min = left; if (right < tree->kichThuoc && tree->array[right]->tanSuat < tree->array[min]->tanSuat) min = right; if (min != i) { swapNode(&tree->array[min], &tree->array[i]); minHeap(tree, min); } }

//Hàm kiểm tra kích thước cây có bằng 1 không int kichThuocBang1(struct huffmanTree* tree) { return (tree->kichThuoc == 1); }

//Hàm lấy ra nút nhỏ nhất struct huffmanNode getMin(struct huffmanTree tree) { struct huffmanNode* temp = tree->array[0]; tree->array[0] = tree->array[tree->kichThuoc-1]; --tree->kichThuoc; minHeap(tree,0); return temp; }

//Hàm chèn thêm nút void chenNode (struct huffmanTree tree, struct huffmanNode treeNode) { ++tree->kichThuoc; int i = tree->kichThuoc-1; while (i && treeNode->tanSuat < tree->array[(i-1)/2]->tanSuat) { tree->array[i] = tree->array[(i-1)/2]; i = (i-1)/2; } tree->array[i] = treeNode; }

//Hàm xây dựng minheap void buildMinheap(struct huffmanTree* tree) { int n = tree->kichThuoc - 1; int i; for (i = (n-1) / 2; i>=0; --i) minHeap(tree,i); }

//Hàm in ra mảng có kích thước n void printArray (int arr[], int n) { int i; for(i = 0;i < n; ++i) printf ("%d", arr[i]); printf("\n"); }

//Hàm kiểm tra xem nút có phải lá không int leafTree(struct huffmanNode* root) { return !(root->left) && !(root->right); }

//Hàm tạo 1 cây với sức chứa bằng kích thước //Chèn toàn bộ kí tự vào cây struct huffmanTree createAndBuildHuffmanTree (char kiTu[], int tanSuat[], int kichThuoc) { struct huffmanTree tree = createTree(kichThuoc); for (int i = 0;i < kichThuoc; ++i) tree->array[i] = node(kiTu[i], tanSuat[i]); tree->kichThuoc = kichThuoc; buildMinheap(tree); return tree; }

//Hàm chính để cây dựng cây Huffman struct huffmanNode buildHuffmanTree(char kiTu[], int tanSuat[], int kichThuoc) { struct huffmanNode left, right, top; //B1: Tạo cây có sức chứa bằng với kích thước struct huffmanTree* tree = createAndBuildHuffmanTree(kiTu, tanSuat, kichThuoc); //lặp lại cho đến khi kích thước không bằng 1 while(!kichThuocBang1(tree)){ //B2: Lấy ra 2 tần suất nhỏ nhất left = getMin(tree); right = getMin(tree); //B3: Tạo nút mới có giá trị bằng tổng 2 nút vừa lấy //2 nút vừa lấy sẽ là 2 nút con của nút mới //Chèn nút mới vào Cây top = node('#', left->tanSuat + right->tanSuat); top->left = left; top->right = right; chenNode(tree, top); } //B4:Còn lại 1 mình nút rễ và cây hoàn thành return getMin(tree); }

//Hàm in ra từ mã từ rễ của cây Huffman dùng arr[] void inTuMa(struct huffmanNode* root, int arr[], int top) { //Quy ước 0 là bên trái if (root->left){ arr[top] = 0; inTuMa (root->left, arr, top + 1); }

//Quy ước 1 là bên phải
if (root->right){
    arr[top] = 1;
    inTuMa (root->right, arr, top + 1);
}
//Nếu nó là nút lá
//In ra kí tự và từ mã của nó từ arr[]
if(leafTree(root)){
    printf("%c: ", root->kiTu);
    printArray(arr, top);
}

}

//Hàm tạo cây Huffman và in ra từ mã void huffmanTuMa (char kiTu[], int tanSuat[], int kichThuoc) { //tạo cây Huffman struct huffmanNode* re = buildHuffmanTree(kiTu, tanSuat, kichThuoc); //in từ mã từ cây đã tạo int arr[doLonCayHuffman], top = 0; inTuMa(re,arr,top); } //Ham main int main() {
char c[1000], kiTu[1000], tanSuat[1000]; printf("Hay nhap xau ki tu dau vao:"); gets(c); input(c,kiTu,tanSuat); int soKiTu = soLuongKiTu(c); int option; printf("Ban muon ma hoa bang phuong phap nao:\n"); printf("Shannon nhan phim \"1\"\n"); printf("Huffman nhan phim \"2\"\n"); printf("Ca hai nhan phim \"3\"\n"); scanf("%d", &option); while (option != 1 && option != 2 && option != 3) { printf("Lua chon khong ton tai, yeu can ban chon lai!\n"); scanf("%d", &option); } if (option == 1){ printf("Bang ma hoa Shannon:\n"); shannon(c, tanSuat, strlen(c), soKiTu); } else if(option == 2){ printf("Bang ma hoa Huffman:\n"); huffmanTuMa(kiTu, tanSuat, soKiTu); } else { printf("Bang ma hoa Shannon:\n"); shannon(c, tanSuat, strlen(c), soKiTu); printf("Bang ma hoa Huffman:\n"); huffmanTuMa(kiTu, tanSuat, soKiTu); } return 0; }

[Minhquy2003iothust]