-
-
Save yasar11732/30d2fc9c1c404d776218424e5e3ca795 to your computer and use it in GitHub Desktop.
#include <stddef.h> // NULL | |
#include <stdint.h> | |
#include <stdlib.h> // calloc | |
#include <string.h> // memset | |
#include <stdio.h> | |
/* | |
* Bir kodun en fazla 15 bit olmasına izin vereceğiz. | |
* Bu nedenle code için 16 bit veri yapısı yeterli. | |
*/ | |
#ifdef _MSC_VER | |
__pragma(pack(push, 1)) | |
struct huffmancode { | |
uint16_t code; | |
uint8_t len; | |
}; | |
__pragma(pack(pop)) | |
#elif defined(__GNUC__) | |
struct __attribute__((packed)) huffmancode { | |
uint16_t code; | |
uint8_t len; | |
}; | |
#endif | |
// her bir code için uzunluk ve kod değerlerini | |
// tuttuğumuz array | |
struct huffmancode tree[0X100]; | |
// her uzunlukta kaç adet kod | |
// olduğunu saymak için | |
uint8_t bl_count[0x10]; | |
// her uzunluktaki kodlama için | |
// atanacak kodu tutar | |
uint16_t next_code[0x10]; | |
typedef struct _huffman | |
{ | |
char c; | |
int freq; | |
struct _huffman *left; | |
struct _huffman *right; | |
} HUFFMANTREE; | |
typedef struct _huffman_array { | |
int cap; | |
int size; | |
HUFFMANTREE **items; | |
} HUFFMANARRAY; | |
HUFFMANTREE *huffmantree_new(char c, int freq) | |
{ | |
HUFFMANTREE *t = malloc(sizeof(HUFFMANTREE)); | |
t->c = c; | |
t->freq = freq; | |
t->left = NULL; | |
t->right = NULL; | |
return t; | |
} | |
/* | |
* Selection sort, büyükten küçüğe | |
*/ | |
void huffman_array_sort(HUFFMANARRAY *arr) | |
{ | |
int i, k; | |
int max_index, max_value; | |
for (i = 0; i < arr->size - 1; i++) | |
{ | |
max_index = i; | |
max_value = arr->items[i]->freq; | |
for (k = i + 1; k < arr->size; k++) | |
{ | |
if (arr->items[k]->freq > max_value) | |
{ | |
max_value = arr->items[k]->freq; | |
max_index = k; | |
} | |
} | |
if (i != max_index) | |
{ | |
HUFFMANTREE *_tmp = arr->items[i]; | |
arr->items[i] = arr->items[max_index]; | |
arr->items[max_index] = _tmp; | |
} | |
} | |
} | |
HUFFMANTREE *huffman_array_pop(HUFFMANARRAY *arr) | |
{ | |
return arr->items[--arr->size]; | |
} | |
void *huffman_array_add(HUFFMANARRAY *arr, HUFFMANTREE *t) | |
{ | |
if (arr->size + 1 == arr->cap) | |
{ | |
arr->cap *= 2; | |
arr->items = realloc(arr->items, arr->cap * sizeof(HUFFMANTREE *)); | |
} | |
arr->items[arr->size++] = t; | |
} | |
HUFFMANARRAY *huffman_array_new() | |
{ | |
HUFFMANARRAY *arr = malloc(sizeof(HUFFMANARRAY)); | |
arr->cap = 8; | |
arr->size = 0; | |
arr->items = malloc(arr->cap * sizeof(HUFFMANTREE *)); | |
return arr; | |
} | |
void huffmantree_print(HUFFMANTREE *t, char *prefix, int size_prefix) | |
{ | |
if (t->left == NULL && t->right == NULL) | |
{ | |
prefix[size_prefix] = 0; | |
printf("%c: %s\n", t->c, prefix); | |
return; | |
} | |
if (t->left) | |
{ | |
prefix[size_prefix++] = '0'; | |
huffmantree_print(t->left, prefix, size_prefix); | |
size_prefix--; | |
} | |
if (t->right) | |
{ | |
prefix[size_prefix++] = '1'; | |
huffmantree_print(t->right, prefix, size_prefix); | |
size_prefix--; | |
} | |
} | |
void load_canonical_codes_from_tree(HUFFMANTREE *t, int length) | |
{ | |
if (!t) | |
return; | |
if (t->c != 0) | |
{ | |
tree[t->c].len = length; | |
} | |
load_canonical_codes_from_tree(t->left, length + 1); | |
load_canonical_codes_from_tree(t->right, length + 1); | |
} | |
char *code_to_binary(struct huffmancode code) | |
{ | |
char *b = malloc(code.len + 1); // +1 null | |
int i; | |
for (i = 0; i < code.len; i++) | |
{ | |
b[i] = code.code & (1 << (code.len - i - 1)) ? '1' : '0'; | |
} | |
b[code.len] = 0; | |
return b; | |
} | |
int main(void) | |
{ | |
unsigned long frequencies[0xFF]; | |
char metin[] = "bu oylesine uzun, oylesine girift bir metin ki, muhakkak gereksiz bitlerini temizlemek gerekir."; | |
char *pcTemp; | |
int i; | |
HUFFMANARRAY *arr = huffman_array_new(); | |
memset(&frequencies[0], 0, sizeof(frequencies)); | |
for (pcTemp = &metin[0]; *pcTemp != 0; pcTemp++) | |
{ | |
frequencies[(int)*pcTemp]++; | |
} | |
for (i = 0; i < 255; i++) | |
{ | |
if (frequencies[i] > 0) | |
{ | |
huffman_array_add(arr, huffmantree_new(i, frequencies[i])); | |
} | |
} | |
while (arr->size > 1) | |
{ | |
huffman_array_sort(arr); | |
HUFFMANTREE *t1 = huffman_array_pop(arr); | |
HUFFMANTREE *t2 = huffman_array_pop(arr); | |
HUFFMANTREE *t3 = calloc(1, sizeof(HUFFMANTREE)); | |
t3->left = t1; | |
t3->right = t2; | |
t3->freq = t1->freq + t2->freq; | |
huffman_array_add(arr, t3); | |
} | |
memset(tree, 0, sizeof(tree)); | |
memset(bl_count, 0, sizeof(bl_count)); | |
memset(next_code, 0, sizeof(next_code)); | |
load_canonical_codes_from_tree(huffman_array_pop(arr), 0); | |
for (i = 0; i < 256; i++) | |
{ | |
bl_count[tree[i].len]++; | |
} | |
int code = 0; | |
bl_count[0] = 0; | |
for (i = 1; i < 0x10; i++) | |
{ | |
code = (code + bl_count[i - 1]) << 1; | |
next_code[i] = code; | |
} | |
for (i = 0; i < 0x100; i++) | |
{ | |
int len = tree[i].len; | |
if (len) | |
{ | |
tree[i].code = next_code[len]; | |
next_code[len]++; | |
} | |
} | |
for (i = 0; i < 0x100; i++) | |
{ | |
int len = tree[i].len; | |
if (len) | |
{ | |
printf("%c: %s\n", i, code_to_binary(tree[i])); | |
} | |
} | |
return 0; | |
} |
(unsigned long)arr->items[i] ^= (unsigned long)arr->items[max_index];
(unsigned long)arr->items[max_index] ^= (unsigned long)arr->items[i];
(unsigned long)arr->items[i] ^= (unsigned long)arr->items[max_index];Bu üç satır "error: lvalue required as left operand of assignment" hatası veriyor.
gcc ile derleyip test etmiştim. c++ derleyicisi ile deniyor olabilir misiniz? Syntax açısından bazı farklılıkları olabiliyor.
Ben de gcc kullandım. Tam olarak "gcc code.c -o output". Gcc version 7.4.0
code.c: In function ‘huffman_array_sort’:
code.c:86:33: error: lvalue required as left operand of assignment
(unsigned long)arr->items[i] ^= (unsigned long)arr->items[max_index];
^~
Kodda ^= ifadesini ^~ ile değiştirince derleniyor ama çıktı yanlış gibi.
^=
solundaki kısmı tamamen parantez içine alarak deneyebilir misiniz?
Eğer o şekilde de derlenmezse, sorun çıkaran kısmı güncelledim.
Denedim ama sorun değişmedi. Bu cevabı uyguladım. Çalıştı. Typecasting ile alakalı bir sıkıntı.
Bu üç satır "error: lvalue required as left operand of assignment" hatası veriyor.