没有合适的资源?快使用搜索试试~ 我知道了~
数据结构课程设计-哈夫曼树及编码.doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 139 浏览量
2021-10-10
19:43:36
上传
评论
收藏 283KB DOC 举报
温馨提示
试读
20页
数据结构课程设计-哈夫曼树及编码.doc
资源推荐
资源详情
资源评论
HUFFMAN 树及编码
1. 需求分析
随机输入一篇英文文章〔或读一个 TXT 文件〕,生成并显示 HUFFMAN 树,
输出每个字母的 HUFFMAN 编码,判断 ASCII 编码与 HUFFMAN 编码对本篇报
文长度节省效果。
(a) 输入的形式为键盘随机输入,输入的字符串长度在 10000 以内;
(b) 输出 HUFFMAN 树的存储结构;
(c) 程序功能为 输 入英文 文章中每 个字母 的 HUFFMAN 编码 , 以及与
ASCLL 码编码长度的比较结果;
(d) 测试数据:正确的输入一篇英文文章,会输出各个字母的 HUFFMAN
编码。错误的输入即其输出输入错误。
2. 概要设计
首先统计英文文章中各个字母的个数作为权值,再统计出现的字母的个数,
以决定所构造赫夫曼树的节点个数,之后便开始构造赫夫曼树,再构造每个节
点的哈夫曼编码。
所设计的抽象数据类型如下:
typedef struct
{
unsigned int weight; //权值
unsigned int parent, lchild, rchild; //双亲,左孩子,右孩子
} HTNode, * HuffmanTree;
typedef char * * HuffmanCode;
所设计的函数如下:
int min(HuffmanTree HT, int i) 找出所有权值中最小的那个。
void Select(HuffmanTree HT, int i, int &s1, int &s2) 找出每次最小的两个权值
最小的权值。
Status HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)
构造赫夫曼树并构造每个字母的赫夫曼编码。
void PrintHT(HuffmanTree HT, int n)
输出赫夫曼树的存储结构。
3. 详细设计
int min(HuffmanTree HT, int i)
{int j, flag = 1;
unsigned int k = 10000;
for(j = 1; j <= i; j++)
{
if(HT[j].weight < k && HT[j].parent == 0)
{
k = HT[j].weight, flag = j;
}//if
}
HT[flag].parent = 1;
return flag;
}
void Select(HuffmanTree HT, int i, int &s1, int &s2)
{
int j;
s1 = min(HT, i);
s2 = min(HT, i);
if(s1 > s2)
{
j = s1;
s1 = s2;
s2 = j;
}
}
Status HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)
{
int s1, s2, i, start, f;
char *cd;
HuffmanTree p = NULL;//p 是工作指针,指向赫夫曼树中的结点
if(n <= 1)
{
return ERROR;
}
int m = 2 * n - 1; //n 个字符构造的赫夫曼树共有 m = 2*n-1 个结点
printf("->待构造的赫夫曼树共有 2 ×%d - 1 = %d 个结点\n", n, m);
if(!(HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode))))//申请赫夫曼树
结点占用的内存空间,0 号单元不用
{
exit(OVERFLOW);
}//if
printf("->赫夫曼树共分配了%d 个结点空间,其中包含一个不用的 0 号单
元\n", m + 1);
//printf("->初始化所有叶子节点的权值,父亲和孩子:\n");
for(p = HT + 1, i = 1; i <= n; ++i, ++p, ++w)
{
p->weight = *w;
p->parent = 0;//双亲初始值为 0,表示此结点还没有被选择最小的算法
选择过
p->lchild = 0;//左右孩子初始化为 0,表示空
p->rchild = 0;
}
for(; i <= m; i++, p++)
{
p->weight = 0;
p->parent = 0;
p->lchild = 0;
p->rchild = 0;
}
for(i = n + 1; i <= m; ++i)
{
Select(HT, i - 1, s1, s2);
HT[s1].parent = i;//选出的两个权值最小的结点的双亲就是即将生成的
结点
HT[s2].parent = i;
HT[i].lchild = s1;//即将生成的结点左孩子是 s1,右孩子是 s2,
HT[i].rchild = s2;//因为 s1 比 s2 先选,所以 s1 总是小于等于 s2
HT[i].weight = HT[s1].weight + HT[s2].weight;//即将生成结点的权值就
是两个权值最小的结点的权值之和
}
if(!(HC = (HuffmanCode)malloc((n + 1) * sizeof(char *))))
{
exit(OVERFLOW);
}//if
if(!(cd = (char *)malloc(n * sizeof(char))))
{
exit(OVERFLOW);
}
cd[n-1] = '\0';
for(int i = 1; i <= n; ++i)
{
start = n - 1;
for(int c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent)
{
if(HT[f].lchild == c)
{
cd[--start] = '0';
}//if
else //叶子结点根结点的右孩子
{
cd[--start] = '1';
}//else
}
if(!(HC[i] = (char *)malloc((n - start) * sizeof(char))))
{
exit(OVERFLOW);
}
strcpy(HC[i], &cd[start]);
//printf("->叶子节点%d 的赫夫曼编码为:%s\n", i, HC[i]);
}
free(cd);
return OK;
}//HuffmanCoding
void PrintHT(HuffmanTree HT, int n)
{
int m = 2 * n - 1;
printf("\n+-------------------------------------------------------------+\n");
printf("| 赫夫曼树 HT 的存储结构 |\n");
printf("+----------+----------+----------+--------------+-------------+\n");
printf("| 结点编号 | weight | parent | leftchild | rightchild |\n");
printf("+----------+----------+----------+--------------+-------------+\n");
for(int i = 1; i <= m; i++)
{
printf("| %4d | %4d | %4d | %4d | %4d |\n",
i, HT[i].weight, HT[i].parent, HT[i].lchild, HT[i].rchild);
printf("+----------+----------+----------+--------------+-------------+\n");
}
}
for(int i = 0; i < len; i++)
{
if(str[i] == 'A')
a[65]++;
else if(str[i] == 'B')
a[66]++;
else if(str[i] == 'C')
a[67]++;
else if(str[i] == 'D')
a[68]++;
else if(str[i] == 'E')
a[69]++;
else if(str[i] == 'F')
a[70]++;
else if(str[i] == 'G')
a[71]++;
else if(str[i] == 'H')
a[72]++;
else if(str[i] == 'I')
a[73]++;
else if(str[i] == 'J')
a[74]++;
else if(str[i] == 'K')
a[75]++;
else if(str[i] == 'L')
a[76]++;
else if(str[i] == 'M')
a[77]++;
else if(str[i] == 'N')
a[78]++//部分统计字母代码
主 程 序 首 先 随 机 输 入 一 篇 英 文 文 章 , 再 统 计 各 字 母 个 数 , 再 调 用
HuffmanCoding(HT, HC, w, n) 函数 ,此函数又会调用 void Select(HuffmanTree
HT, int i, int &s1, int &s2)函数,而此函数又会调用 int min(HuffmanTree HT, int i)
函数,构造完成后便调用 PrintHT(HT,n)函数输出赫夫曼树的存储结构。
剩余19页未读,继续阅读
资源评论
学习使人快乐张
- 粉丝: 14
- 资源: 6万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功