呜呜呜我是不用高抽象程度的语言就会不知所措的笨蛋
太底层了太底层了太底层了
怎么都是指针都是指针都是指针
啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊
C好难C好难C好难
一上午才调通的Huffman编解码程序 被自己蠢晕了
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
typedef struct Element
{
int weight;
char ch;
} Element;
int compare(Element lhs, Element rhs)
{
if (lhs.weight < rhs.weight)
{
return -1;
}
if (rhs.weight < lhs.weight)
{
return 1;
}
return 0;
}
enum Subtree
{
LEFT = '0',
RIGHT = '1'
};
struct HuffmanTree
{
struct HuffmanTree *left;
struct HuffmanTree *right;
Element element;
};
typedef struct HuffmanTree HuffmanTree;
HuffmanTree *newHuffmanTree(int weight, char ch)
{
HuffmanTree *tree = (HuffmanTree *)malloc(sizeof(HuffmanTree));
tree->left = tree->right = NULL;
tree->element.weight = weight;
tree->element.ch = ch;
return tree;
}
void deleteHuffmanTree(HuffmanTree *this)
{
if (this->left != NULL)
{
deleteHuffmanTree(this->left);
}
if (this->right != NULL)
{
deleteHuffmanTree(this->right);
}
free(this);
}
typedef struct LinkedList
{
HuffmanTree *object;
struct LinkedList *next;
} LinkedList;
LinkedList *newLinkedList(HuffmanTree *tree)
{
LinkedList *list = (LinkedList *)malloc(sizeof(LinkedList));
list->object = tree;
list->next = NULL;
return list;
}
void deleteLinkedList(LinkedList *this)
{
if (this->next != NULL)
{
deleteLinkedList(this->next);
}
free(this);
}
LinkedList *insertIntoList(LinkedList *this, LinkedList *position, LinkedList *newnode)
{
newnode->next = position->next;
position->next = newnode;
return this;
}
LinkedList *removeFromList(LinkedList *this, LinkedList *position)
{
if (position->next == NULL)
{
return NULL;
}
LinkedList *result = position->next;
position->next = result->next;
result->next = NULL;
return result;
}
LinkedList *treeInsert(LinkedList *this, HuffmanTree *tree)
{
if (tree == NULL)
{
return this;
}
LinkedList *p = this;
while (p->next != NULL && compare(p->next->object->element, tree->element) < 0)
{
p = p->next;
}
insertIntoList(this, p, newLinkedList(tree));
return this;
}
HuffmanTree *treeTakeFirst(LinkedList *this)
{
LinkedList *tree_holder = removeFromList(this, this);
if (tree_holder == NULL)
{
return NULL;
}
HuffmanTree *result = tree_holder->object;
deleteLinkedList(tree_holder);
return result;
}
typedef struct Stack
{
int size;
int top;
int *array;
} Stack;
Stack *newStack(int size)
{
if (size < 1)
{
size = 1;
}
Stack *stack = (Stack *)malloc(sizeof(Stack));
stack->size = size;
stack->top = -1;
stack->array = (int *)malloc(size * sizeof(int));
return stack;
}
void deleteStack(Stack *this)
{
if (this == NULL || this->array == NULL)
{
return;
}
free(this->array);
this->array = NULL;
free(this);
this = NULL;
}
void resizeStack(Stack *this, int size)
{
if (size < 1)
{
size = 1;
}
int *new_array = (int *)malloc(size * sizeof(int));
memcpy(new_array, this->array, sizeof(int));
free(this->array);
this->array = new_array;
this->size = size;
}
void stackPush(Stack *this, int value)
{
if (this->top + 1 == this->size)
{
resizeStack(this, this->size * 2);
}
this->array[++this->top] = value;
}
int stackTop(Stack *this)
{
return this->array[this->top];
}
int stackPop(Stack *this)
{
return this->array[this->top--];
}
int stackEmpty(Stack *this)
{
return this->top < 0;
}
char *stack2String(Stack *this)
{
char *result = (char *)malloc((this->top + 2) * sizeof(char)); // +1 +'\0' = +2
for (int i = 0; i <= this->top; ++i)
{
result[i] = this->array[i];
}
result[this->top + 1] = '\0';
return result;
}
HuffmanTree *construct(LinkedList *trees)
{
HuffmanTree *left_subtree = treeTakeFirst(trees);
HuffmanTree *right_subtree = treeTakeFirst(trees);
if (left_subtree != NULL && right_subtree == NULL)
{
return left_subtree;
}
HuffmanTree *new_tree = newHuffmanTree(
left_subtree->element.weight + right_subtree->element.weight,
'\0');
new_tree->left = left_subtree;
new_tree->right = right_subtree;
treeInsert(trees, new_tree);
return construct(trees);
}
void traversal(HuffmanTree *tree, Stack *stack, char *map[])
{
if (tree == NULL)
{
return;
}
if (tree->element.ch != '\0')
{
map[(int)(tree->element.ch)] = stack2String(stack);
}
stackPush(stack, LEFT);
traversal(tree->left, stack, map);
stackPop(stack);
stackPush(stack, RIGHT);
traversal(tree->right, stack, map);
stackPop(stack);
}
HuffmanTree *makeEncoder(LinkedList *trees, char *map[])
{
HuffmanTree *tree = construct(trees);
Stack *stack = newStack(8);
traversal(tree, stack, map);
deleteStack(stack);
return tree;
}
char decodeChar(HuffmanTree *tree, const char *string, size_t *begin)
{
HuffmanTree *p = tree;
while (p->element.ch == '\0')
{
if (string[*begin] == LEFT)
{
p = p->left;
}
else if (string[*begin] == RIGHT)
{
p = p->right;
}
else
{
break;
}
++(*begin);
}
return p->element.ch;
}
void encode(char *src, char *dst, char *map[])
{
for (char *psrc = src, *pdst = dst; *psrc != '\0'; ++psrc)
{
for (char *p = map[(int)(*psrc)]; *p != '\0'; *pdst++ = *p++)
;
}
}
void decode(const char *src, char *dst, HuffmanTree *huffman_tree)
{
char *pdst = dst;
for (size_t i = 0; i < strlen(src);)
{
*pdst++ = decodeChar(huffman_tree, src, &i);
}
}
int main()
{
int n;
scanf("%d", &n);
int weights[102];
char chars[102];
for (int i = 0; i < n; ++i)
{
char str[8];
scanf("%s", str);
chars[i] = str[0];
}
for (int i = 0; i < n; ++i)
{
scanf("%d", &weights[i]);
}
LinkedList *trees = newLinkedList(NULL);
for (int i = 0; i < n; ++i)
{
HuffmanTree *tree = newHuffmanTree(weights[i], chars[i]);
treeInsert(trees, tree);
}
char *encode_map[128];
memset(encode_map, 0, sizeof(encode_map));
HuffmanTree *huffman = makeEncoder(trees, encode_map);
// for (char i = 0; i >= 0; ++i)
// {
// printf("%c %s\n", i, encode_map[i]);
// }
char code[102];
scanf("%s", code);
char encoded[1000];
memset(encoded, 0, sizeof(encoded));
encode(code, encoded, encode_map);
printf("%s\n", encoded);
char decoded[102];
memset(decoded, 0, sizeof(decoded));
decode(encoded, decoded, huffman);
printf("%s\n", decoded);
deleteHuffmanTree(huffman);
deleteLinkedList(trees);
return 0;
}
（水一贴。。但是C真的好难
感觉我这写的还是有内存泄露；；架构也是依托
泯轲
