#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct tree {
	unsigned char letter;
	struct tree * left;
	struct tree * right;
	struct tree * up;
	char direct;
};

struct tree * create_l (char letter) {
	struct tree * cur;
	cur = (struct tree *) malloc (sizeof(struct tree));
	cur->up = NULL;
	cur->left = NULL;
	cur->right = NULL;
	cur->letter = letter;
	cur->direct = '0';
	return cur;
}

struct tree * add (int mas1, int mas2, struct tree * cur1, struct tree * cur2) {
	struct tree * par;
	par = (struct tree *) malloc (sizeof(struct tree));
	if (mas1 < mas2) {
		par->right = cur1;
		par->left = cur2;
		cur1->direct = '1';
		cur2->direct = '0';
	} else {
		par->right = cur2;
		par->left = cur1;
		cur1->direct = '0';
		cur2->direct = '1';
	}
	cur1->up = par;
	cur2->up = par;
	par->up = NULL;
	par->letter = 0;
	return par;
}

int main (void) {
	int n = 256;
	FILE *in, * tabl, *codes, *decode, *in_dec;
	in = fopen ("in.txt", "r");
	tabl = fopen ("in.txt", "r");
	codes = fopen ("codes.txt", "w");
	in_dec = fopen ("codes.txt", "r");
	decode = fopen ("decode.txt", "w");
	if ((in == NULL) || (tabl == NULL) || (codes == NULL) || (decode == NULL) || (in_dec == NULL)) {
		printf ("Файл не найден\n");
		return 0;
	}
	int freq[n];											//создание и заполнение массива частот
	unsigned char freq_l[n];
	for (int i = 0; i < n; i++) {
		freq[i] = 0;
		freq_l[i] = 0;
	}
	unsigned char c;
	while (fscanf (tabl, "%c", &c) != EOF) {
		freq[(int)c]++;
		freq_l[(int)c] = c;
	}														//массив частот создан и заполнен
	struct tree * list[n], * temp[n];						//создание дерева для декодирования + для выбора кодов
	struct tree * root;
	for (int i = 0; i < n; i++) {
		list[i] = NULL;
		temp[i] = NULL;
	}
	int k = 0, flag = 0;
	for (int i = 0; i < n; i++) {
		if (freq[i] != 0) {
			k++;
		}
	}
	if (k == 1) {
		for (int i = 0; i < n; i++) {
			if (freq[i] != 0) {
				list[i] = create_l (freq_l[i]);
				root = list[i];
				flag++;
				c = freq_l[i];
			}
		}
	}
	while (k > 1) {
		int min, m_min, numb1 = 257, numb2 = 257;
		for (int i = 0; i < n; i++) {
			if (freq[i] != 0) {
				if (numb1 >= freq[i]) {
					min = m_min;
					numb2 = numb1;
					m_min = i;
					numb1 = freq[i];
				} else {
					if (numb2 >= freq[i]) {
						min = i;
						numb2 = freq[i];
					}
				}
			}
		}
		if (freq_l[min] != 0) {
			list[min] = create_l (freq_l[min]);
			temp[min] = list[min];
		}
		if (freq_l[m_min] != 0) {
			list[m_min] = create_l (freq_l[m_min]);
			temp[m_min] = list[m_min];
		}
		freq_l[min] = 0;
		freq_l[m_min] = 0;
		list[min] = add (freq[min], freq[m_min], list[min], list[m_min]);
		list[m_min] = list[min];
		freq[min] += freq[m_min];
		freq[m_min] = 0;
		k--;
		if (k == 1) {
			root = list[min];
		}
	}
	char * sh[n];
	for (int i = 0; i < n; i++) {
		sh[i] = (char *) malloc (sizeof(char)*256);
	}
	if (flag == 1) {
		sh[(int)c][0] = '0';
		sh[(int)c][1] = '\0';
	} else {
		for (int i = 0; i < n; i++) {
			if (temp[i] != NULL) {
				int j = 0;
				c = temp[i]->letter;
				while (temp[i]->up != NULL) {
					sh[(int)c][j] = temp[i]->direct;
					temp[i] = temp[i]->up;
					j++;
				}
				sh[(int)c][j] = '\0';
			}
		}
	}
	while (fscanf(in, "%c", &c) != EOF) {				//кодирование
		int j = 0;
		while (sh[(int)c][j] != '\0') {
			j++;
		}
		for (int i = j - 1; i > -1; i--) {
			fprintf (codes, "%c", sh[(int)c][i]);
		}
		//fprintf (codes, "-");
	}
	fclose (in);
	fclose (tabl);
	fclose (codes);
	struct tree * cur = root;									//декодирование
	while (fscanf (in_dec, "%c", &c) != EOF) {
		if (cur->letter == 0) {
			if (c == '0') {
				cur = cur->left;
			} else {
				cur = cur->right;
			}
		} else {
			fprintf (decode, "%c", cur->letter);
			if (c == '0') {
				cur = root->left;
			} else {
				cur = root->right;
			}
		}
	}
	if (cur->letter != 0) {
		fprintf (decode, "%c", cur->letter);
	}
	fclose (in_dec);
	fclose (decode);
	return 0;
}