数据结构作业,三叉哈夫曼树的实现

这是我用二叉哈夫曼树代码改的,但是无法实现,首先是叶子节点和节点数没法表示,然后就算自己输入固定节点也无法正确实现,请问怎么实现三叉哈夫曼树呢

#include
#include
#include
#include
using namespace std;
typedef struct
{
unsigned int weight; //结点权值
unsigned int parent, lchild, rchild; //结点的父指针,左右孩子指针
}HTNode, HuffmanTree; //动态分配数组存储哈夫曼树
typedef char **HuffmanCode; //动态分配数组存储哈夫曼编码表
HuffmanTree HT; //哈夫曼树HT
HuffmanCode HC; //哈夫曼编码表HC
unsigned int *w; //w存放叶子结点权值

char * source_code;//source_code 存放原始码
void CreateHuffmanTree(HuffmanTree &, unsigned int
, int); //生成一棵哈夫曼树
void HuffmanCoding(HuffmanTree, HuffmanCode &, int); //对哈夫曼树进行编码
void PrintHuffmanCode(HuffmanCode, unsigned int*, int); //显示哈夫曼编码
void Select(HuffmanTree, int, int&, int&); //在数组中寻找权值最小的两个结点
int main()
{
int n, i; //n是哈夫曼树叶子结点数
char choose = 'y'; //用于选择程序是否退出
//程序解说
printf("本程序将演示构造哈夫曼树.\n");
printf("首先输入叶子结点数目.\n例如:2\n");
printf("然后输入原始码以及权值.\n");
printf("第1个原始码及其权值 :");
printf("a 5\n");
printf("第2个原始码及其权值 :");
printf("b 3\n");
printf("程序会构造一棵哈夫曼树并显示哈夫曼编码.\n");
cout << "权值" << " " << "原始码" << " " << "哈夫曼编码" << endl;
printf(" 5 a 1\n");
printf(" 3 b 0\n");
putchar('\n');
putchar('\n');
while (choose != 'N'&&choose != 'n')
{
printf("请输入叶子结点数目:");
scanf("%d", &n); //输入叶子结点数
if (n <= 1)
{
printf("该数不合理!\n"); continue;
}
w = (unsigned int*)malloc(n * sizeof(unsigned int)); //开辟空间存放权值
source_code = (char *)malloc(n * sizeof(char)); //开辟空间存放原始码
//printf("请输入各原始码以及权值 :\n");
for (i = 0; i < n; i++)
{
printf("第%d个原始码及其权值 :", i + 1);
cin >> source_code[i]; //输入原始码
cin >> w[i]; //输入各叶子结点权值
}
CreateHuffmanTree(HT, w, n); //生成哈夫曼树
HuffmanCoding(HT, HC, n); //进行哈夫曼编码
putchar('\n');
PrintHuffmanCode(HC, w, n); //显示哈夫曼编码
printf("哈夫曼树构造完毕,还要继续吗?(Y/N)");
scanf(" %c", &choose);
}
}
void CreateHuffmanTree(HuffmanTree &HT, unsigned int *w, int n)
{//w存放n个结点的权值,将构造一棵哈夫曼树HT
int i, m;
int s1, s2;
HuffmanTree p;
if (n <= 1) return;
m = 2 * n - 1; //n个叶子结点的哈夫曼树,有2*n-1个结点
HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode)); //开辟2*n各结点空间,0号单元不用
for (p = HT + 1, i = 1; i <= n; ++i, ++p, ++w) //进行初始化
{
p->weight = *w;
p->parent = 0;
p->lchild = 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) //建哈夫曼树
{
//从HT[1...i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2
Select(HT, i - 1, s1, s2);
HT[s1].parent = i; HT[s2].parent = i; //修改s1和s2结点的父指针parent
HT[i].lchild = s1; HT[i].rchild = s2; //修改i结点的左右孩子指针
HT[i].weight = HT[s1].weight + HT[s2].weight; //修改权值
}
}
void HuffmanCoding(HuffmanTree HT, HuffmanCode &HC, int n)
{
//将有n个叶子结点的哈夫曼树HT进行编码, 所编的码存放在HC中
//方法是从叶子到根逆向求每个叶子结点的哈夫曼编码
int i, c, f, start;
char *cd;
HC = (HuffmanCode)malloc((n + 1) * sizeof(char *)); //分配n个编码的头指针向量
cd = (char *)malloc(n * sizeof(char)); //开辟一个求编码的工作空间
cd[n - 1] = '\0'; //编码结束符
for (i = 1; i <= n; ++i) //逐个地求哈夫曼编码
{
start = n - 1; //编码结束位置
for (c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent) //从叶子到根逆向求编码
if (HT[f].lchild == c)
cd[--start] = '0'; //若是左孩子编为'0'
else
cd[--start] = '1'; //若是右孩子编为'1'
HC[i] = (char *)malloc((n - start) * sizeof(char)); //为第i个编码分配空间
strcpy(HC[i], &cd[start]); //将编码从cd复制到HC中
}
free(cd); //释放工作空间
}
void PrintHuffmanCode(HuffmanCode HC, unsigned int *w, int n)
{
//显示有n个叶子结点的哈夫曼树的编码表
int i;
printf("哈夫曼编码如下 :\n");
putchar('\n');
cout << "权值" << " " << "原始码" << " " << "哈夫曼编码" << endl;
for (i = 1; i <= n; i++)
{
printf(" %d", w[i - 1]);
printf(" %3c\t ", source_code[i - 1]);
puts(HC[i]);
}
printf("\n");
}
void Select(HuffmanTree HT, int t, int&s1, int&s2)
{
//在HT[1...t]中选择parent不为0且权值最小的两个结点,其序号分别为s1和s2,s1存放最小的,s2存放次小的
int i = 0;
int j = 0;
int k = 0;
int least = 0;
int second = 0;

for (i = 1; i <= t; i++)
{
    if (HT[i].parent == 0)

        break;
}

for (j = i + 1; j <= t; j++)
{
    if (HT[j].parent == 0)

        break;
}

if (HT[i].weight < HT[j].weight)
{
    least = i;
    second = j;
}
else
{
    least = j;
    second = i;
}
for (k = j + 1; k <= t; k++)
{
    if (HT[k].parent == 0)
    {
        if (HT[k].weight < HT[least].weight)
        {
            second = least;
            least = k;
        }
        else if (HT[k].weight >= HT[least].weight && HT[k].weight < HT[second].weight)
            second = k;
    }
}
s1 = least;
s2 = second;

}

0

1个回答

2
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
优化的三叉哈夫曼树
1. 背景 在通讯、计算机网络、数据压缩、图像处理中,哈夫曼编码是一项极其重要的技术。哈夫曼编码是建立在二叉哈夫曼树的基础上,如果能够找到比二叉哈夫曼树更好的数据结构,那么对数据压缩等将起到促进作用。本文通过论述二叉哈夫曼树编码算法以及普通的三叉哈夫曼树编码算法,给出一种优化的三叉哈夫曼编码算法。 2. 哈夫曼编码2.1 哈夫曼编码 哈夫曼编码是根据每个字符出现的频率进行编码的,依据字符出现
用C语言实现三叉哈夫曼树
用C语言实现三叉哈夫曼树 用C语言实现三叉哈夫曼树 用C语言实现三叉哈夫曼树
数据结构(15)--哈夫曼树以及哈夫曼编码的实现
参考书籍:数据结构(C语言版)严蔚敏吴伟民编著清华大学出版社 本文中的代码可从这里下载:https://github.com/qingyujean/data-structure 1.哈夫曼树 假设有n个权值{w1, w2, ..., wn},试构造一棵含有n个叶子结点的二叉树,每个叶子节点带权威wi,则其中带权路径长度WPL最小的二叉树叫做最优二叉树或者哈夫曼树。 特点:哈...
三叉链表
#include #include #include using namespace std;enum {ERROR,OK,OVERFLOW = 0};int Nil = ;typedef struct BiTNode{ int data; BiTNode *lchild,*rchild,*parent;}BiTNode,*BiTree;bool
三叉哈夫曼树的分析
要讲解三叉哈夫曼树之前,你得弄懂一下几个问题: 1、什么是二叉哈夫曼树 2、二叉哈夫曼树是什么类型的算法 3、在2中的算法构建出三叉或者N叉哈夫曼树一定是最优的吗? 以上的问题我就不给予具体的answer,其实二叉哈夫曼树就应用了贪心算法,对于该算法不熟悉的同学赶紧去补补书 贪心算法无法保证全局最优,而是提供了局部最优的一种解决方法。(当然证明为最优的贪心策略就可以的,前
数据结构::如何实现哈夫曼树
【哈夫曼树的定义】:     哈夫曼树又称为最优二叉树,它是加权路径最短的二叉树。     不同于普通的二叉树,它的每个节点都有相应的权值,当我们构建的时候最终离根节点远的节点权重小,反之就比较大。 【哈夫曼树的实现】: 1、利用的核心思想:贪心算法      贪心算法:是指在问题进行求解的时候,总是做出当前看起来最好的选择。即就是说贪心算法做出不是整体的最优解,而是某种
数据结构--哈夫曼树建立及打印编码
题目描述 对输入的英文大写字母进行统计概率 然后构建哈夫曼树,输出是按照概率降序排序输出Huffman编码。#include <iostream> #include <queue> #include <cstring> #include <vector> #include <cstdio> #include <algorithm> using namespace std;class Node {
数据结构——哈夫曼树的实现以及编码(C语言实现)
1、问题描述       利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。构造哈夫曼树时,首先将由n个字 符形成的n个叶子结点存放到数组HuffNode的前n个分量中,然后根据哈夫曼方法的基本思想,不断将两个较小的子树合并为一个 较大的子树,每次构成的新子树的根结点顺序放到HuffNode数组中的前n个分量的后面。        通俗的来讲,哈弗曼树就是一种广...
【数据结构】哈夫曼树编码/译码器
前言 参考博客:https://www.cnblogs.com/kangjianwei101/p/5242934.html 原博客是用C语言实现的,笔者改用java实现,原因主要有以下几点: 避免使用复杂的指针,减小错误发生的可能性 对字符串和数组的处理都自带了很多方法,不用在自己实现 java的char类型用来存储Unicode类型的,字节长为2,而Unicode编码是包含中文的,所以可以直接...
二叉树:三叉链表
//三叉链表 #ifndef _PBITREE_H #define _PBITREE_H #incldue "BiTree.h" //包含二叉链表的头文件(见上一篇文章)//结点结构体templatestruct PBiTNode{T data;PBiTNode *lchild,*rchild,*parent;};  //类模板:继承自BiTree template class PBi
数据结构实践课-哈夫曼树-文件的压缩解压(MFC)
数据结构实践课-哈夫曼树-文件的压缩解压(MFC)
链表与哈夫曼树
&amp;lt;!--[if !supportLists]--&amp;gt;一、&amp;lt;!--[endif]--&amp;gt;什么是链表? 链表是使用指针进行连接的一种数据结构,他可以提供比数组更加灵活的数据存储。 认识一下链表之前,先知道节点。 Class Node { Object data;/用于存储数据; Node next;//指向下一个的指针 } 一、哈夫曼编码 以哈夫曼树─即最...
哈夫曼树的实现及其实例分析
定义给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。
c++ 哈夫曼树简便构造(数据结构作业篇)
// 用最小栈方式构建哈弗曼树// 定义一个哈夫曼树的节点struct MinHeapNode {    // One of the input characters    char data;    // Frequency of the character    unsigned freq;    // 哈夫曼的编码值, #号表示无编码    string code_huff = &quot;#&quot;;  ...
北邮数据结构哈夫曼树实验报告
北邮数据结构实验,哈夫曼树,含有报告以及源代码程序
三叉链表实现二叉树基本操作
#include #include #include using namespace std; int head, tail; typedef struct treenode { char data; treenode *lchild; treenode *rchild; treenode *parent; }node, *Tree; node *q[100];
二叉树的三叉链表存储及其Java实现
三叉链表存储的思想是让每个节点持有三个引用parent、left、right,分别指向其父节点、左子节点和右子节点。如下图所示: 因此,三叉链表存储的节点大致如: class Node{         T data;         Node parent;         Node left;         Node right;     }   Ja
数据结构之---C语言实现二叉树的三叉链表存储表示
数据结构之---C语言实现二叉树的三叉链表存储表示
哈夫曼树——————数据结构作业
实现一个哈夫曼编码系统,系统包括以下功能: 字符信息统计:读取待编码的源文件SourceFile.txt,统计出现的字符及其频率。 建立哈夫曼树:根据统计结果建立哈夫曼树。 建立哈夫曼码表:利用得到的哈夫曼树,将各字符对应的编码表保存在文件Code.txt中。 对源文件进行编码:根据哈夫曼码表,将SourceFile.txt中的字符转换成相应的编码文件ResultFile.txt。 Sourc...
哈夫曼编码链表+树实现
/** 输入格式是 输入每个字符的次数 然后依次输出每个字符的编码 样例输入 3 a 10 b 5 c 8 4 a 1 b 1 c 1 d 1 样例输出 a:0 b:10 c:11 a:00 b:01 c:10 d:11 */  #include #include typedef struct tree {     char ch;
c++ 数据结构 *** 哈夫曼树的应用——压缩软件
数据结构的作业,压缩软件用的,具体写的过程中有哪些问题在程序里说吧。 头文件与常量部分: 利用char的8位,来存储文件里的元素。每次取出文件中的8位并记录这八位出现的次数用来进行哈夫曼数的建立。 #include #include #include #include #include using namespace std; //利用char进行8位一取,这样不管是字符类型还是
数据结构之哈夫曼树的实现
1、Huffman(哈夫曼)树的一些基本概念 1、1哈夫曼树的定义 最简哈夫曼树是一种数据结构,是由德国数学家冯·哈夫曼发现的,又称最优二叉树,是一种带权路径长最短的树。所以Huffman树是一种二叉树。 1、2哈夫曼树的经典应用 哈夫曼树最经典的应用时在通信领域的哈夫曼编码上面。经哈夫曼编码的信息消除了冗余的数据,加提高了通信信道的传输效率,目前,Huffman编码计数还是数据压缩的重要...
C语言实现Huffman树并计算带权路径长度
More Code,More progress #include #include typedef int ElemType; typedef struct _BTreeNode { ElemType data; struct _BTreeNode* left; struct _BTreeNode* right; }BTreeNode; //根据数组 a
利用哈夫曼树实现文件压缩
实现原理: 1.按照字符分析要压缩的文件得出结果(有哪些字符,每个字符出现的次数)。 2.根据字符出现的次数构建哈夫曼树(得出字符的哈夫曼编码)。 3.根据字符的哈夫曼编码进行转换、压缩,然后创建压缩文件。 4.读取压缩文件,读出哈夫曼编码和字符的对照表。解压缩。 数据结构的设计: 1.保存字符次数和字符的数据结构 struct _symbol{ char charac
数据结构上机作业3-哈夫曼编码
1.问题描述从键盘接收一串电文字符,输入对应的Huffman编码。同时,能翻译由Huffman编码生成的代码串,输出对应的电文字符串。2.设计要求1) 构造一棵 Huffman树。 2) 实现Huffman编码,并用Huffman编码生成的代码串进行译码。 3) 程序中字符和权值是可变的,实现程序的灵活性。3.代码实现参考文章: http://blog.csdn.net/TW_345/a
JAVA数据结构与算法实现-哈夫曼树
JAVA数据结构与算法实现-哈夫曼树 哈夫曼树,是一种特殊的二叉树,由一个叫做哈夫曼的人实现出来的,由于他的一致性所以数据统一。在这里我使用数组实现二叉树的原理。 在这里我们首先创建一个二叉树节点的类,名为point: /** * Created by jim_D on 2018/10/11. */ public class point { int info;//定义节点的值 point lef...
《C++实现数据结构》:哈夫曼树
首先我们先来明确几个概念。 树的路径长度:从根到树中任意结点的路径长度是指从根结点到该结点的路径上所包括的边的数目,也相当于是该结点的层次-1。 树的内路径长度:除叶子结点外,从根到树中其他所有结点的路径长度之和。 树的外路径长度:从根到树中所有叶子结点的路径长度之和。 叶子结点的加权路径长度:从根到该叶子的路径长度与叶子的权的乘积。 树的加权路径长度:树中所有叶子结点的加权路径长度之和。
哈夫曼编码/译码器数据结构课程设计
设计一个哈夫曼编码/译码系统,对一个文本文件中的字符进行哈夫曼编码,生成编码文件(后缀名.cod);反过来,可将一个编码文件还原为一个文本文件(.txt)。 要求: (1)输入一个待编码的文本文件名,统计文本文件中各字符的个数作为权值,生成哈夫曼树; (2)将文本文件利用哈夫曼树进行编码,生成编码文件(后缀名cod); (3)输入一个待解码的编码文件名称,并利用相应的哈夫曼树将编码文件译码; (4)显示指定的编码文件和文本文件; (5)把哈夫曼编码用二进制位紧缩到一个变量中,利用位运算进行真正的数据压缩,并求压缩比。(此选项选作)
哈夫曼树的构造与哈夫曼编码
#include<stdio.h> #include<string.h> #include<stdlib.h> #define N 20//叶子结点最大值 #define M 2*N-1//所有结点最大值 //静态三叉链表实现哈夫曼树 typedef struct Huffman{ int weight; int parent; int lchild; int r
数据结构-哈夫曼树的实现
数据结构哈夫曼树的实现,数据结构哈夫曼树的实现,数据结构哈夫曼树的实现
哈夫曼树(数据结构)
设二叉树具有n个带权值的叶子节点,从根节点到叶子节点的路径长度与对应叶子节点权值的乘积之和叫做二叉树的“带权路径长度”。
数据结构-----哈夫曼树的构造以及遍历
/* 根据Huffman树的构造原理进行构造 ... 哈夫曼树在编码压缩的领域有很好的应用,利用Huffman进行编码可以保证数据传输 的无二义性 。 但是要注意的是 对于出现频率大的数据我们应该尽量放在离根节点近的地方进行编码 , 出现频率小的数据我们可以放在距离根节点小的地方。 这样可以提高数据的传输效率 。 */ #include "stdio.h" #include "malloc.h
【C++数据结构】哈夫曼树代码实现
HuffeManTree.h#pragma once #include "Stack.h" // 我自己写的栈 #include "Stack.cpp"template<class T> class CTree { public: CTree(void);public: T data = NULL; int weight = 1; CTree* lNode = nu
数据结构之哈夫曼树(c语言)
哈夫曼树 利用静态链表建立赫夫曼树,建树过程中要求左子树权值小于右子树权值,求各结点的编码。要求:叶子结点的个数n及结点值由键盘录入。本题给出程序代码,要求修改以满足测试要求.  #include "stdio.h" #include "malloc.h" #include "string.h" typedef struct{    unsigned int weight;  
数据结构:哈夫曼树和哈夫曼编码
哈夫曼树 哈夫曼树是一种最优二叉树,其定义是:给定n个权值作为n个叶子节点,构造一棵二叉树,若树的带权路径长度达到最小,这样的树就达到最优二叉树,也就是哈夫曼树,示例图如下: 基本概念 深入学习哈夫曼树前,先了解一下基本概念,并以上面的哈夫曼树图为例 路径:树中一个结点到另一个结点之间的分支序列构成两个结点间的路径。 路径长度:路径中分支的数目,从根结点到第L层结点的路径长度为L-1...
【数据结构】哈夫曼树实现编码译码
根据一段字符串中字符的个数 作为该字符的权值生成哈夫曼树。        然后根据生成的哈夫曼编码,对任意字符串实现编码,对任意二进制串实现译码。 程序运行结果: 1.程序主界面: 2.根据字符串 创建哈夫曼树及编码: 3.生成的编码表如下: 4.根据生成的哈夫曼编码对字符串编码: 5.生成的编码保存在文件中: 6.对二进制串译码
【数据结构】二叉树(哈夫曼树)的JAVA代码实现
哈夫曼树的基本概念 二叉树的经典应用就是哈夫曼(Haffman)树,也称最优二叉树,是指对于一组带有确定权值的叶结点、构造的具有最小带权路径长度的二叉树。 二叉树的路径长度是指由根结点到所有的叶结点的路径长度之和。如果二叉树的叶结点都带有一定的权值,则可以将这个概念加以推广。设二叉树具有n个带权值的叶结点,那么从根结点到各个叶结点的路径长度与相应的叶结点权值的乘积之和叫做二叉树的带权路径长度。...
数据结构与算法 哈夫曼树的实现
数据结构与算法课程实验报告,实现哈夫曼树,对文档进行哈夫曼树编码
数据结构之---C语言实现哈夫曼树和编码
数据结构之---C语言实现哈夫曼树和编码
线索二叉树的递归与非递归实现 数据结构作业
(1)递归实现二叉树的中序线索化 (2)非递归实现二叉树的中序线索化 (3)实现中序线索二叉树上遍历二叉树
文章热词 机器学习教程 Objective-C培训 交互设计视频教程 颜色模型 设计制作学习
相关热词 mysql关联查询两次本表 native底部 react extjs glyph 图标 大数据预科班作业 数据库课程设计作业