哈夫曼树编码数据结构课设

问题遇到的现象和发生背景

哈夫曼树编码运行不出结果

用代码块功能插入代码，请勿粘贴截图

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

#define N 100
#define Max 2N-1//因为N个结点的哈夫曼树总共有2N-1个结点

//定义结构体，包含权重，双亲，左孩子，右孩子；
typedef struct {
double weight;
char s;
int parent, lchild, rchild;
}HTNode,HuffmanTree[Max+1];//0号存储单元未用，所以数组长度加一

//函数声明
void Select(HuffmanTree ht, int x, int* m1, int* m2);
void CreatHuffmanTree(HuffmanTree ht, int n);
void HuffmanTreeCoding(HuffmanTree ht, char** hc, int n);
void printfHuffmanTreecode(HuffmanTree ht, char** hc, int index);
void Huffmanfind(HuffmanTree ht, int n, char* pwd);

找出森林中根得权值最小的两个
基本思想：先初始化min1，min2，然后依次遍历森林集合与min1比较,如果小就把他赋值给min1；min2同理
函数参数解释：ht是哈夫曼树，x是森林中根结点个数，*m1,*m2是为了存储最小和第二小的数；

/
void Select(HuffmanTree ht, int x, int* m1, int* m2) {
//初始化min1,min2来比较，要用一个比较大的数，否则与根结点遍历比较之后得到的是原来的min1,min2的小数
double min1 = 10000;
double min2 = 10000;
int i;
for (i = 1; i <= x; i++)
{

   //找权值最小的值需要满足两个条件：小于min1，而且他的根结点必须是零，才能保证他不是叶子结点。
   if (ht[i].weight < min1 && ht[i].parent == 0) {
       min1 = ht[i].weight;
       *m1 = i;
   }

}
//接下来查找第二个小的数
int j;
for (j = 1; j <= x; j++)
{

   //在已经查找到最小的数的前提下，查找不等于min1的数min2
   //找权值第二小的值需要满足：不是最小的那个，但是可以和最小的数值相等
   if (ht[j].weight < min2 && j != *m1 && ht[j].parent == 0)
   {
       min2 = ht[j].weight;
       *m2 = j;
   }

}

}
/*

构造哈夫曼树
基本思想：在森林中不断选择两个最小的根节点，直到最后只有一颗树为止，这颗树就是哈夫曼树
函数参数意义：n是用户在主函数中输入的字符个数，也就是哈夫曼树的叶子结点个数
/

void CreatHuffmanTree(HuffmanTree ht, int n)
{
int i;
//有n个结点，需要从n+1后开始构造新的根，小于总哈夫曼的结点数2*n-1;
for (i = n + 1; i <= 2 * n - 1; i++)
{
int m1, m2;
//调用Select函数，其中注意i-1，查找两个最小的数，并赋值给m1,m2;
Select(ht, i - 1, &m1, &m2);
//从n+1开始创建新的根结点，是左右结点的和
ht[i].weight = ht[m1].weight + ht[m2].weight;
//左边是最小的数，右边是第二小的数
ht[i].lchild = m1;
ht[i].rchild = m2;
//ht[i]的双亲结点是零
ht[i].parent = 0;
//左孩子、右孩子的双亲结点地址为i;
ht[m1].parent = i;
ht[m2].parent = i;

}

哈夫曼树编码
基本思想：结点是左结点便赋值为0，右便赋值为1，从而得到编码
函数参数意义：hc是哈夫曼编码，n是用户主函数中输入的字符个数

/
void HuffmanTreeCoding(HuffmanTree ht, char** hc, int n)
{
char* cd = (char*)malloc(n * sizeof(char));//分配求编码的工作空间
cd[n - 1] = '\0';//根节点编码为空
int now = 1;//表示正在编码的结点；
int p = 0;//正在编码结点的父亲结点；
int start;//此时编码存在数组中的位置
int i = 0;
/外层循环用于初始化，更换需要编码的结点/
while (i < n)
{

   start = n - 1;//编码在数组中指定位置开始存放；
   now = i + 1;//正在编码的结点加一；
   p = ht[now].parent;//父亲结点初始化为now正在编码的结点位置

   /*内层循环用于获取指定结点的编码*/
   while(p!=0)//当p=0时就是根节点
   {
       start--;
       if (ht[p].lchild == now)//只要结点是其父结点的左子树便赋值为0，右为1；
       {
           cd[start] = '0';
       }
       else
       //if (ht[p].rchild == now)//不同
       {
           cd[start] = '1';
       }
       now = p;//此时结点是原来的父亲结点
       p = ht[now].parent;//更新父亲结点，从下往上
   }
   hc[i + 1] = (char*)malloc((n - start) * sizeof(char));//开辟存储空间存储编码
   strcpy_s(hc[i + 1], &cd[start],20);//赋值编码到新的存储空间里
   i++;

}
}
/*

先序打印

/
void printfHuffmanTreecode(HuffmanTree ht, char** hc, int index) {
if (index >= 1) {//如果是叶子结点就输出他的字符以及编码

   if (ht[index].lchild == 0 && ht[index].rchild == 0)
   {//叶子结点

       printf("字符%c的编码为：%s\n", ht[index].s, hc[index]);
       return;
   }
   printfHuffmanTreecode(ht, hc, ht[index].lchild);//递归
   printfHuffmanTreecode(ht, hc, ht[index].rchild);

}
}
//在生成的哈夫曼树中输入编码查找目标
/*
基本思想：从根结点出发，是0走左子树，是1走右子树
函数参数意义：pwd是用户输入要查找的编码*/
void Huffmanfind(HuffmanTree ht, int n, char* pwd)
{
int len = strlen(pwd);
int i = 0, node = 2 * n - 1;
while (i < len)
{

   if (pwd[i] == '0')//是0走左子树
   {
       node = ht[node].lchild;//更新结点
       i++;
       if (ht[node].lchild == 0 && ht[node].rchild == 0)//如果是叶子结点就输出叶子结点字符
       {
           printf("%c", ht[node].s);
           node = 2 * n - 1;//重新从根结点开始，继续编译
       }
   }
   if (pwd[i] == '1') 
   {
       node = ht[node].rchild;//更新结点
       i++;
       if (ht[node].lchild == 0 && ht[node].rchild == 0)//如果是叶子结点就输出叶子结点字符
       {
           printf("%c", ht[node].s);
           node = 2 * n - 1;//重新从根结点开始，继续编译
       }
   }

}
}
main(void)
{
HuffmanTree ht;
int n;//输入字符个数
printf("请输入字符个数\n");
scanf_s("%d", &n);
getchar();//获取字符串
char* hc[N+1];
/二叉树的初始化/
printf("请输入需要生成哈夫曼树的字符以及对应的频率，如：a2\n");
int i;
for (i = 1; i <= n; i++)
{

   scanf_s("%c%lf", &ht[i].s,10, &ht[i].weight);
   ht[i].lchild = 0;
   ht[i].parent = 0;
   ht[i].rchild = 0;

}

char pwd[9999];
scanf_s("%s",pwd,20);
CreatHuffmanTree(ht,n);
HuffmanTreeCoding(ht,hc,n);
printfHuffmanTreecode(ht,hc, 2*n-1);
Huffmanfind(ht,n, pwd);

}

运行结果及报错内容

输入：3
a1
s2
d3
直接退出无输入

我的解答思路和尝试过的方法

求求哪位大佬帮忙看看问题把

我想要达到的结果

仅供参考：

#include <iostream>
#include <string>
using namespace std;
struct huffTree {
    int parent;
    int lchild;
    int rchild;
    int weight;
    string flag;
};
struct Lowest_node {
    char ch;
    int ch_num;
};
void coding(int length,huffTree *tree,int n,int &a,int &b) {
    int i;
    int r,s;

    r=s=length;
    for (i=0;i<n;i++) {
        if (tree[i].weight<r
         && tree[i].parent==-1) {
            r=tree[i].weight;
            a=i;
        }
    }
    for (i=0;i<n;i++) {
        if (tree[i].weight<s
         && i!=a
         && tree[i].parent==-1) {
            s=tree[i].weight;
            b=i;
        }
    }
}
void frequency(string str) {
    int i,j;
    int length=str.length();
    Lowest_node *node=new Lowest_node[length];

    for (i=0;i<length;i++) node[i].ch_num=0;

    int char_type_num=0;
    for (i=0;i<length;i++) {
        for (j=0;j<char_type_num;j++)
            if (str[i]==node[j].ch
            || ('a'<=node[j].ch && node[j].ch<='z'
                && str[i]+32==node[j].ch))
                break;//
        if (j<char_type_num) node[j].ch_num++;
        else {
            if ('A'<=str[i] && str[i] <= 'Z') node[j].ch=str[i]+32;
            else node[j].ch=str[i];
            node[j].ch_num++;
            char_type_num++;
        }
    }
    for (i=0;i<char_type_num;i++) {
        for (j=i;j<char_type_num;j++) {
            if (node[j].ch_num<node[j+1].ch_num) {
                int temp;
                char ch_temp;
                temp=node[j].ch_num;
                ch_temp=node[j].ch;
                node[j].ch_num=node[j+1].ch_num;
                node[j].ch=node[j+1].ch;
                node[j+1].ch_num=temp;
                node[j+1].ch=ch_temp;
            }
        }
    }
    for (i=0;i<char_type_num;i++)
        cout<<"字符"<<node[i].ch<<"出现了"<<node[i].ch_num<<"次"<<endl;
    huffTree *huff=new huffTree[2*char_type_num-1];
    huffTree temp;
    string *code=new string[2*char_type_num-1];

    for (i=0;i<2*char_type_num-1;i++) {
        huff[i].lchild=-1;
        huff[i].parent=-1;
        huff[i].rchild=-1;
        huff[i].flag=-1;
    }
    for (j=0;j<char_type_num;j++) huff[j].weight=node[j].ch_num;
    int min1,min2;
    for (int k=char_type_num;k<2*char_type_num-1;k++) {
        coding(length,huff,k,min1,min2);
        huff[min1].parent=k;
        huff[min2].parent=k;
        huff[min1].flag="0";
        huff[min2].flag="1";
        huff[k].lchild=min1;
        huff[k].rchild=min2;
        huff[k].weight=huff[min1].weight+huff[min2].weight;
    }
    for (i=0;i<char_type_num;i++) {
        temp=huff[i];
        while (1) {
            code[i]=temp.flag+code[i];
            temp=huff[temp.parent];
            if (temp.parent==-1) break;//
        }
    }
    cout<<"字符串的每个字符huffman编码为："<<endl;
    for (i=0;i<char_type_num;i++) cout<<node[i].ch<<"  "<<code[i]<<endl;
    cout<<"整个字符串的huffman编码为："<<endl;
    for (i=0;i<length;i++) {                                                                                     //S?
        for (j=0;j<char_type_num;j++) {
            if (str[i]==node[j].ch)
                cout<<code[j];
        }
    }
    delete[] node;
    node=NULL;
    delete[] huff;
    huff=NULL;
    delete[] code;
    code=NULL;
}
int main() {
    int length=0;
    string str;
    cout<<"请输入一个字符串：";
    cin>>str;
    frequency(str);
    return 0;
}
//请输入一个字符串：2333abcde
//字符3出现了3次
//字符2出现了1次
//字符a出现了1次
//字符b出现了1次
//字符c出现了1次
//字符d出现了1次
//字符e出现了1次
//字符串的每个字符huffman编码为：
//3  11
//2  000
//a  001
//b  010
//c  011
//d  100
//e  101
//整个字符串的huffman编码为：
//000111111001010011100101