本人大二,最近在写哈夫曼树电文编码
要实现:
已知n个字符在原文中出现的频率,求它们的哈夫曼编码。
1、读入n个字符,以及字符的权值,试建立一棵Huffman树。
2、根据生成的Huffman树,求每个字符的Huffman编码。并对给定的待编码字符序列进行编码,并输出。
现学校要求使用c语言文件输入输出辅助使用
整个程序可以通过编译,但在初始化后,选择2 .Encode 会直接跳出switch,进入3.Decode 但整个程序运行完,是下图效果,并没有实行整个程序,现在还不知道为什么 ,望能够救助一下!
我也试图解决过这个问题,在调试时发现报错program receive signal SIGSEGV Segmentation fault
通过查询有说是无法访问指针的内存 或者声明变量时在函数内 ,但还是无从下手。
下面附完整代码:
#include <conio.h> /* for getch() */
#include <ctype.h> /* for tolower() */
#include <malloc.h> /* for malloc(), calloc(), free() */
#include <string.h> /* for memmove(), strcpy() */
#include <stdlib.h>
/*树结构和全局结构指针*/
#define NODENUM 26
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef char SElemType;
/*----------哈夫曼树结点结构-------------*/
struct node {
char ch;
int weight;
int parent;
int lchild, rchild;
} *ht ; //指向哈夫曼树的存储空间的指针变量
/*----------字符编码结点结构-------------*/
struct HuffmanCoding {
int start;
char coding[NODENUM];
char ch;
int num[NODENUM];
};
/*--------哈夫曼树遍历时栈的结点结构------*/
struct stacknode {
int NodeLevel;
int NodeElem;
};
typedef struct {
struct node *base;
struct node *top;
int stacksize;
} SqStack;
/************************************************************/
/* 释放哈夫曼树数据空间函数 */
/************************************************************/
void free_ht() {
if (ht != NULL) {
free(ht);
ht = NULL;
}
}
int InitStack(SqStack &S) { //建立一个栈
S.base = (struct node *)malloc(STACK_INIT_SIZE * sizeof(struct node));
if (!(S.base))
exit(-1);
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return 0;
}
int Push(SqStack &S, struct node *e) { //将元素e插入栈中
if (S.top - S.base >= S.stacksize) {
if (!(S.base = (struct node *)realloc(S.base, (STACK_INIT_SIZE + STACKINCREMENT) * sizeof(struct node))))
exit(-1);
S.top = S.base + STACKINCREMENT;
S.stacksize += STACKINCREMENT;
}
*S.top++ = *e;
return 0;
}
int Pop(SqStack &S, struct node *&e) { //出栈,将栈顶元素赋值给e返回
if (S.base == S.top)
return false;
e = --S.top;
return 0;
}
int StackEmpty(SqStack &S) { //判定栈是否为空
if (S.base == S.top) {
return true;
} else
return false;
}
/*---------------常量文件名---------------*/
const char *TableFileName = "HfmTbl.txt"; //哈夫曼树数据文件
const char *CodeFileName = "CodeFile.txt"; //字符编码数据文件
const char *SourceFileName = "SrcText.txt"; //需编码的字符串文件
const char *EnCodeFileName = "EnCodeFile.txt"; //编码数据文件
const char *DecodeFileName = "DecodeFile.txt"; //译码字符文件
/************************************************************/
/* 从文件读取哈夫曼树数据函数 */
/************************************************************/
int ReadFromFile() {
int i;
int m;
FILE *fp;
if ((fp = fopen(TableFileName, "rb")) == NULL) {
printf("cannot open %s\n", TableFileName);
getch();
return 0;
}
fread(&m, sizeof(int), 1, fp); //m为数据个数 sizeof(int)=4
free_ht();
ht = (struct node *)malloc(m * sizeof(struct node));
fread(ht, sizeof(struct node), m, fp);
fclose(fp);
return m;
}
/************************************************************/
/* 吃掉无效的垃圾字符函数函数 */
/* 从键盘读字符数据时使用,避免读到无效字符 */
/************************************************************/
void EatCharsUntilNewLine() {
while (getchar() != '\n')
continue;
}
/************************************************************/
/* 选择权值最小的两个根结点函数 */
/************************************************************/
void Select(struct node h[], int n, int *s1, int *s2) {
int i, k, m1, m2, p1, p2;
//(学生完成)
for (i = n + 1; i <= 2 * n - 1; i++) {
m1 = m2 = 32767;
for (k = 1; k < i; k++) {
if (h[k].parent == 0) {
if (h[k].weight < m1) {
m2 = m1;
p2 = p1;
m1 = h[k].weight;
p1 = k; //时m1 p1 得最小值
} else if (h[k].weight < m2) {
m2 = h[k].weight;
p2 = k;
}
}
}
h[p1].parent = i;
h[p2].parent = i;
h[i].weight = m1 + m2;
h[i].lchild = p1;
h[i].rchild = p2;
s1 = &h[i].lchild;
s2 = &h[i].rchild;
}
}
/************************************************************/
/* 创建哈夫曼树和产生字符编码的函数 */
/************************************************************/
int Initialization(node h[], node *ht, HuffmanCoding code[]) {
int i = 0, n, m, m1, m2, p1, p2, start, k;
int f, c;
HuffmanCoding d;
FILE *fp;
printf("输入字符总数 n:");
scanf("%d", &n);
EatCharsUntilNewLine();
m = 2 * n - 1; //一共2n-1个结点
ht = (struct node *)malloc(m * sizeof(struct node)); //树结点
//申请哈夫曼树的存储空间
/********************************************************/
/* 创建哈夫曼树 */
/* 1、输入字符和权值 */
/* 2、初始化哈夫曼树 */
/* 3、建立哈夫曼树 */
/********************************************************/
for (i = 1; i <= n; i++) {
printf("输入第%d个元素的节点值和权重:", i);
getchar();
scanf("%c%d", &h[i].ch, &h[i].weight);
}
for (i = 1; i <= 2 * n - 1; i++) {
h[i].lchild = h[i].parent = h[i].rchild = 0;
}
for (i = n + 1; i <= 2 * n - 1; i++) {
m1 = m2 = 32767;
p1 = p2 = i;
for (k = 1; k < i; k++) {
if (h[k].parent == 0) {
if (h[k].weight < m1) {
m2 = m1;
p2 = p1;
m1 = h[k].weight;
p1 = k; //时m1 p1 得最小值
} else if (h[k].weight < m2) {
m2 = h[k].weight;
p2 = k;
}
}
}
h[p1].parent = i;
h[p2].parent = i;
h[i].weight = m1 + m2;
h[i].lchild = p1;
h[i].rchild = p2; //分配父结点
}
//把哈夫曼树的数据存储到文件中
if ((fp = fopen(TableFileName, "wb")) == NULL) {
printf("cannot open %s\n", TableFileName);
getch();
return 0;
}
fwrite(&m, sizeof(int), 1, fp); //把2 * n - 1以占4个字节的形式输入进去
fwrite(ht, sizeof(struct node), m, fp); //每次输入sizeof(struct node)个字节,共输入2 * n - 1次
// for (i = 1; i <= 2 * n - 1; i++) {
//
// fwrite(&h[i], sizeof(struct node), 1, fp);
// printf("下标:%d\n权值:%d\n父亲:%d\n左孩子:%d\n右孩子:%d\n", i, h[i].weight, h[i].parent, h[i].lchild, h[i].rchild);
// }
fclose(fp);
free_ht();
printf("\nInitial successfule!\n");
getch();
return n;
}
/************************************************************/
/* 哈夫曼编码的函数 */
/************************************************************/
int Encode(node h[], HuffmanCoding code[], int n) {
int i, j, f, m, k;
char Encodestr[256], c;
HuffmanCoding d;
FILE *fp1, *fp2;
for (i = 1; i <= n; i++) {
d.start = n + 1;
c = i;
f = h[i].parent;
while (f != 0) {
if (h[f].lchild == c)
d.coding[--d.start] = '0';
else
d.coding[--d.start] = '1';
c = f;
f = h[f].parent;
}
code[i] = d;
}
if ((fp1 = fopen(CodeFileName, "wb")) == NULL) {
printf("cannot open %s\n", CodeFileName);
getch();
return 0;
}
fwrite(&n, sizeof(int), 1, fp1);
fwrite(&code[1], sizeof(struct HuffmanCoding), n, fp1); //此处 CodeFileName和EnCodeFileName 相似 二合一
fclose(fp1);
printf("222");
}
/************************************************************/
/* 哈夫曼译码的函数 */
/************************************************************/
int Decode(node h[], HuffmanCoding code[], int n) {
FILE *CFP, *TFP;
char DeCodeStr[256];
char ch;
int i, j, f, m, k;
printf("请输出电文(0或1),以‘#’为结束标志:\n");
ch = getchar();
k = 1;
while (ch != '#') {
DeCodeStr[k] = ch;
ch = getchar();
k++;
}
j = k - 1;
m = k;
f = 2 * n - 1;
k = 1;
if (!(CFP = fopen(EnCodeFileName, "wb"))) {
printf("cannot open %s\n", EnCodeFileName);
getch();
return 0;
}
fwrite(&j, sizeof(int), 1, CFP);
fwrite(&DeCodeStr, sizeof(DeCodeStr), k - 1, CFP);
if (!(TFP = fopen(DecodeFileName, "wb"))) {
printf("cannot open %s\n", DecodeFileName);
getch();
return 0;
}
while (k < m) {
while (h[f].lchild != 0) {
if (DeCodeStr[k] == '0')
f = h[f].lchild;
if (DeCodeStr[k] == '1')
f = h[f].rchild;
k++;
}
fwrite(&h[f].ch, sizeof(char), 1, TFP);
f = 2 * n - 1;
}
free_ht();
fclose(CFP);
fclose(TFP);
printf("\n");
getch();
printf("222");
}
/************************************************************/
/* 以凹式形式打印哈夫曼树的函数 */
/************************************************************/
int PrintHuffmanTree(struct node h[], int q) {
// int i, node, child, n, top, width = 4, m;
// struct node stack[NODENUM], *p;
// int level[NODENUM][2];
// char type;
int m = ReadFromFile();
printf("\n%10c Huffman TRee in Level\n", ' ');
printf("%10c--------------------------------------\n", ' ');
//(学生完成)
SqStack S;
InitStack(S);
struct node *p;
p = &h[m];
int n, i, width = 4, c, f;
int level[100], top;
printf("\n");
top = 1;
level[top] = width;
for (i = 1; i < q + 1; i++) {
n = level[top];
c = i;
f = h[i].parent;
if (p) {
Push(S, p);
for (i = 0; i < n; i++)
printf(" ");
printf("%c", p->ch);
top--;
printf("\n");
if (p->rchild != NULL) {
top++;
level[top] = n + width; //输出空格数增加width
if (h[f].rchild == c)
p = &h[h[f].rchild];
}
if (p->lchild != NULL) {
top++;
level[top] = n + width;
//输出空格数增加width
}
} else {
Pop(S, p);
if (h[f].lchild == c)
p = &h[h[f].lchild];
}
}
printf("\n");
return 0;
}
/************************************************************/
/* 打印哈夫曼字符编码的函数 */
/************************************************************/
int PrintCharCoding(HuffmanCoding code[], int n, struct node h[]) {
int i;
FILE *fp;
/********************************************************/
/* 打印字符编码 */
/* 1、读字符编码数据 */
/* 2、打印字符编码数据 */
/* 格式: */
/* character coding */
/* ---------------------- - */
/* charactor coding */
/* */
/* */
/********************************************************/
if (!(fp = fopen(EnCodeFileName, "rb"))) {
printf("cannot open %s\n", EnCodeFileName);
getch();
return 0;
} //打开文
printf("character coding\n");
printf("---------------------- \n");
printf("character \t coding\n");
for (i = 1; i <= n; i++) {
fread(&h[i].ch, sizeof(char), 1, fp);
printf("%c\t", h[i].ch);
fread(&code[i].num[i], sizeof(struct HuffmanCoding), 1, fp);
printf("%d\t", code[i].num[i]);
printf("\n");
}
fclose(fp);
}
/************************************************************/
/* 以表的形式打印哈夫曼树的函数 */
/************************************************************/
int PrintHuffmanTable(struct node h[], int n) {
int i, m = ReadFromFile();;
FILE *fp;
/************************************************************/
/* 打印字符编码 */
/* 1、读哈夫曼树数据 */
/* 2、打印哈夫曼树数据 */
/* 格式: */
/* Huffman Table */
/* ---------------------------------------------------------------------- */
/* Number charactor weight Parent Lchild Rchild */
/* */
/* */
/************************************************************/
printf("Huffman Table\n");
printf("----------------------------------------------------- \n");
printf("Number \tweight \t Parent\t Lchild \t Rchild \n");
if ((fp = fopen(TableFileName, "rb")) == NULL) {
printf("cannot open %s\n", TableFileName);
getch();
return 0;
}
for (int i = 1; i <= m; i++) {
fread(&h[i], sizeof(struct node), m, fp);
printf("%d\t%d\t%d\t%d\t%d\t\n", i, h[i].weight, h[i].parent, h[i].lchild, h[i].rchild);
}
fclose(fp);
free_ht();
}
int nemu() {
int num;
printf("\n ******* huffman arithmetic demonstration *********\n");
printf(" *%15c1---Initial%23c\n", ' ', '*');
printf(" *%15c2---Encode%24c\n", ' ', '*');
printf(" *%15c3---Decode%24c\n", ' ', '*');
printf(" *%15c4---Print huffmantree%13c\n", ' ', '*');
printf(" *%15c5---Print huffman Table%11c\n", ' ', '*');
printf(" *%15c6---Print char Coding%13c\n", ' ', '*');
printf(" *%15c7---Quit%26c\n", ' ', '*');
printf(" **************************************************\n");
printf("%15cSelcet 1,2,3,4,5,6,7: ", ' ');
do {
scanf("%d", &num);
} while (num < 1 || num > 7);
return (num);
}
int main() {
//定义定义
struct HuffmanCoding code[NODENUM]; //字符编码结点结构
struct node h[NODENUM];
int n, s;
node *ht = &h[0];
while (1) {
switch (nemu()) {
case 1:
n = Initialization(h, ht, code);
break;
case 2:
Encode(h, code, n);
break;
case 3:
Decode(h, code, n);
break;
case 4:
PrintHuffmanTree(h, n);
break;
case 5:
PrintHuffmanTable(h, n);
break;
case 6:
PrintCharCoding(code, n, h);
break;
case 7:
return 0;
default:
printf("请输入合法量!\n");
nemu();
}
}
}
```c
```