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

by admin on 2020年1月22日

void HuffmanCoding(HuffmanTree &HT,HuffmanCode&HC,int *w,int n)
{
 int m,i,s1,s2,start,c,f;
    HuffmanTree p;
   if(n<=1)
     return;
   m=2*n-1;//由得到的叶子数而计算结点总数
   HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//分配存储空间
   for(p=HT+1,i=1;i<=n;++i,++p,++w)
     { p->weight=*w;//为结点初始化权值
      
//cout<<endl<<“HT[“<<i<<“].weight=”<<p->weight<<”
“; 
    printf(“nHT[%d].weight=%d “,i,p->weight);
       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;
     }//初始化双亲和左右孩子,使他们成为孤立的
  // cout<<endl<<endl<<“哈弗曼树创建的顺序如下:”;
   printf(“nn赫夫曼树创建的顺序如下:”);
   for(i=n+1;i<=m;++i)
   {
   Select(HT,i-1,s1,s2); //调用select函数
      HT[s1].parent=i;
      HT[s2].parent=i;
      HT[i].lchild=s1;
      HT[i].rchild=s2;
     
HT[i].weight=HT[s1].weight+HT[s2].weight;//新结点的权值是s1和s2权值的和
     // cout<<endl<<“HT[“<<s1<<“] and
HT[“<<s2<<“] create”;
   printf(“nHT[%d] and HT[%d] create”,s1,s2);
    //  cout<<”
HT[“<<i<<“].weight=”<<HT[i].weight;
   printf(“tHT[%d].weight=%d”,i,HT[i].weight);
 
  
}//每次选择最小的两个结点做左右孩子,权值和为新的结点的权值和,删去连个小的结点
   //*********哈夫曼编码*****************
   HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
   char *cd;
   cd=(char *)malloc(n*sizeof(char));
   cd[n-1]=’’;
  
//cout<<endl<<endl<<“HuffmanTree编码是:”<<endl;
    printf(“nnHuffmanTree编码是:n”);
   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′;
         else
          cd[–start]=’1′;
      HC[i]=(char*)malloc((n-start)*sizeof(char));
      strcpy(HC[i],&cd[start]);
      printf(“nHT[%d] node’s Huffman code is: %s”,i,HC[i]);
   }
   free(cd);
}
//****************主函数部分********************
void main()             
{  HuffmanTree HT;
   HuffmanCode HC;
   int n,i;
   int *w,W[MAX_LENGTH];
  //
cout<<“***********本实验实现的是哈夫曼树的建立以及编码*********”;//交互信息
  
printf(“***********本实验实现的是赫夫曼树的建立以及编码**********”);
  // cout<<endl<<“请输入哈弗曼树元素的个数: “;
   printf(“n请输入赫夫曼树元素的个数:”);
  // cin>>n;
   scanf(“%d”,&n);
   for(i=0;i<n;++i)
   {
    //cout<<“请输入第
“<<i+1<<“个元素的权值(0~255的整数): “;
    printf(“请输入第%d个元素的权值(0~255的整数):”,i+1);
      // cin>>W[i];
    scanf(“%d”,&W[i]);
   }
   w=W;
   HuffmanCoding(HT,HC,w,n);
   getch();
}

/*
8
5 29 7 8 14 23 3 11
*/
int main()
{
    HuffmanTree HT;
    HuffmanCode HC;
    int *w,n,i;

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

 

//
s1为最小的两个值中序号小的那个
void select(HuffmanTree
t,int i,int &s1,int &s2)
{
    int j;
    s1=min(t,i);
    s2=min(t,i);//不可能出现s1>s2
    //printf(“s1:%d s2:%dn”,s1,s2);
    if(t[s1].weight>t[s2].weight)//其实这里完全没有必要
    {
        j=s1;
        s1=s2;
        s2=j;
    }
    //printf(“s1:%d s2:%dn”,s1,s2);
}

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;

# include <stdio.h>     
# include <stdlib.h>
# include <conio.h>
# include <string.h>
# define MAX_LENGTH 100
typedef char **HuffmanCode;
//**********数据结构*************
typedef struct  
{   int weight; //权值
    int parent,lchild,rchild; //双亲,左右孩子
}HTNode,*HuffmanTree;   //结点和指针
//**********select函数**************
void Select(HuffmanTree HT,int i,int &s1,int &s2)
{ //在建立哈夫曼树的所有结点中选择权值最小的两个结点存放在s1,s2中
   int j,k=1;               
   while(HT[k].parent!=0)
       k++;
   s1=k;
   for(j=1;j<=i;++j)
      if(HT[j].parent==0&&HT[j].weight<HT[s1].weight)
   s1=j;
   k=1;
   while(HT[k].parent!=0||k==s1)
      k++;
   s2=k;
   for(j=1;j<=i;++j)
      if(HT[j].parent==0&&HT[j].weight<HT[s2].weight&&j!=s1)
   s2=j;
}
//**********构建哈夫曼树***********************

    if(n<=1)   return;
    m=2*n-1;//huffman编码字符都在二叉树的叶子上,全树的节点为叶子节点的2倍-1;
    HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //
0号单元未用
    for(p=HT+1,i=1;
i<=n; ++i,++p,++w)
    {
        (*p).weight=*w;
        //printf(“%dt%dn”,*w,(*p).weight);
        (*p).parent=0;
        (*p).lchild=0;
        (*p).rchild=0;
    }
    for(; i<=m;
++i,++p)  (*p).parent=0;
    //
在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2
    for(i=n+1; i<=m; ++i)   //
建哈夫曼树
    {
        select(HT,i-1,s1,s2);//在i之前挑选最小的和次小的
        HT[s1].parent=HT[s2].parent=i;
        HT[i].lchild=s1;
        HT[i].rchild=s2;
        HT[i].weight=HT[s1].weight+HT[s2].weight;
    }
    //顺序输出哈夫曼树
    PrintHuffmanTree(HT, HC, n);
}

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例如:2n”);
printf(“然后输入原始码以及权值.n”);
printf(“第1个原始码及其权值 :”);
printf;
printf(“第2个原始码及其权值 :”);
printf;
printf(“程序会构造一棵哈夫曼树并显示哈夫曼编码.n”);
cout << “权值” << ” ” << “原始码” << ” ”
<< “哈夫曼编码” << endl;
printf(” 5 a 1n”);
printf(” 3 b 0n”);
putchar;
putchar;
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 = malloc(n * sizeof; //开辟空间存放原始码
//printf(“请输入各原始码以及权值 :n”);
for (i = 0; i < n; i++)
{
printf(“第%d个原始码及其权值 :”, i + 1);
cin >> source_code[i]; //输入原始码
cin >> w[i]; //输入各叶子结点权值
}
CreateHuffmanTree; //生成哈夫曼树
HuffmanCoding(HT, HC, n); //进行哈夫曼编码
putchar;
PrintHuffmanCode; //显示哈夫曼编码
printf(“哈夫曼树构造完毕,还要继续吗?;
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 * sizeof; //开辟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 * sizeof; //分配n个编码的头指针向量
cd = malloc(n * sizeof; //开辟一个求编码的工作空间
cd[n – 1] = ‘’; //编码结束符
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] = malloc((n – start) * sizeof; //为第i个编码分配空间
strcpy(HC[i], &cd[start]); //将编码从cd复制到HC中
}
free; //释放工作空间
}
void PrintHuffmanCode(HuffmanCode HC, unsigned int *w, int n)
{
//显示有n个叶子结点的哈夫曼树的编码表
int i;
printf(“哈夫曼编码如下 :n”);
putchar;
cout << “权值” << ” ” << “原始码” << ” ”
<< “哈夫曼编码” << endl;
for (i = 1; i <= n; i++)
{
printf(” %d”, w[i – 1]);
printf(” %3ct “, source_code[i – 1]);
puts;
}
printf;
}
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;

void PrintHuffmanTree(HuffmanTree
&HT,HuffmanCode &HC, int n)
{
    int i, c, cdlen;
    char *cd;
    HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//
分配n个字符编码的头指针向量([0]不用)
    cd=(char*)malloc(n*sizeof(char)); //
分配求编码的工作空间
    c=2*n-1;
    cdlen=0;
    for(i=1; i<=c; ++i) HT[i].weight=0; //
遍历赫夫曼树时用作结点状态标志
    while(c)//c是树根所在点,从树根开始遍历,若是叶子则将编码放在数组HC[叶子]
    {
        if(HT[c].weight==0)   //
向左
        {
            HT[c].weight=1;
            if(HT[c].lchild==0 && HT[c].rchild==0)  //
登记叶子结点字符编码
            {
                HC[c]=(char
*)malloc((cdlen+1)*sizeof(char));
                cd[cdlen]=’’;
                strcpy(HC[c],cd); //
复制编码(串)
            }
            if(HT[c].lchild!=0)//想左,给0编码;
            {
                c=HT[c].lchild;
                cd[cdlen++]=’0′;
            }
        }
        else if(HT[c].weight==1)   //
向右
        {
            HT[c].weight=2;
            if(HT[c].rchild!=0) //初始化是叶子节点的左右孩子为空(0),若有孩子不为空,向右编码1;
            {
                c=HT[c].rchild;
                cd[cdlen++]=’1′;
            }
        }
        else
        {

}

    printf(“Number of weights:”);
    scanf(“%d”,&n);

#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存放叶子结点权值

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

#define MAX_INT 99999
//哈夫曼树和哈夫曼编码的存储表示
typedef struct
{
    int weight;
    int parent,lchild,rchild;
} HTNode,*HuffmanTree; // 动态分配数组存储哈夫曼树

    w=(int*)malloc(n*sizeof(int));
    printf(“Weights: n”);
    for(i=0; i<n; i++)
        scanf(“%d”,w+i);

//
w存放n个字符的权值(均>0),构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC
void
HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{
    int m,i,s1,s2;

}

            //HT[c].weight=0;//从左向右退,相当于中序遍历,不会再遍历到哪里了,所以这里没有必要
            c=HT[c].parent;
            –cdlen; // 退到父结点,编码长度减1
        }
    }
    free(cd);
}

int min(HuffmanTree t,int i)
{
    int j,flag;
    int k=MAX_INT; //
取k为不小于可能的值
    for(j=1; j<=i; j++)
        if(t[j].weight<k&&t[j].parent==0)
            k=t[j].weight,flag=j;
    t[flag].parent=1;//保证下一次min()函数选不到它
    //printf(“%d “,flag);
    return flag;
}

    HuffmanCoding(HT,HC,w,n);
    printf(“Huffman code:n”);
    for(i=1; i<=n; i++)
    {
        printf(“权为%d的编码是: “,*(w+i-1));
        printf(“%sn”,HC[i]);
    }

typedef char **HuffmanCode; //
动态分配数组存储哈夫曼编码表

    HuffmanTree p;

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图