//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)
{
//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 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");
//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]]++; }
}
//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; }
}
//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) {
}
//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); }
}
//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");
}