哈夫曼树代码关于 SIGSEGV, Segmentation fault.“错误

Question

问题在于它会报“Thread 1 received signal SIGSEGV, Segmentation fault.“错误

问题相关代码

//生成编码（左边为0，右边为1）
HuffmanCode *CreatHuffmanCode(HuffmanTree T, int N) 
{
    HuffmanCode *TC = (HuffmanCode *)malloc((N + 1) * sizeof(HuffmanCode));
    //给各元素分配内存空间
    for (int i = 0; i < N + 1; i++) {
        TC[i] = (HuffmanCode)malloc(sizeof(struct HCNode));
    }

    HuffmanTree Temp = T;
    char cd[100];          //临时编码数组
    int cdlen = 0;         //记录编码串的长度

    //哈夫曼树已经建完，权值没有用了，这里将各个结点的权值重新赋值为0，用于记录访问结点的次数
    ErgodicHuffmanTree(Temp);

    //如果树不空
    while (Temp) {
        int i = 0;
        i=Temp->Ori_Position;            //记录Temp的位置，也是编码串应该插入的位置

        //如果当前结点一次没有访问，进入if
        if (Temp->Weight == 0) {
            Temp->Weight = 1;                  //重置访问次数为1

            //如果有左孩子，则访问左孩子，并且一路标记值为0
            if (Temp->Left != NULL) {
                Temp = Temp->Left;
                cd[cdlen++] = '0';
            }
            //当前结点没有左孩子，也没有右孩子，说明为叶子结点，直接记录哈夫曼编码
            else {
                cd[cdlen] = '\0';
                TC[i]->Code = (char *)malloc((cdlen + 1) * sizeof(char));
                TC[i]->Char = Temp->Char;
                strcpy(TC[i]->Code, cd);
                TC[i]->CodeLenth = cdlen;
            }
        }
        //如果Weight为1，说明访问过一次，即是从其左孩子返回的
        else if (Temp->Weight == 1) {
            Temp->Weight = 2;                   //重置访问次数为2

            //如果有右孩子，遍历右孩子，记录标记值为1
            if (Temp->Right != NULL) {
                Temp = Temp->Right;
                cd[cdlen++] = '1';
            }
        }
        //如果访问次数为2，说明左右孩子都遍历完了，返回父结点
        else {
            Temp->Weight = 0;
            Temp = Temp->Parent;
            cdlen--;
        }
    }
    return TC;                //返回最终的编码数组
}

报错内容

我想要达到的结果

希望能最大限度的保留原始代码

总的代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXP 10000           //当生成点与原始字符结点权值相同时，原始字符结点为左子结点 
#define MAX1 100001          //设置输入的01串的最大长度（预留一个位置给‘\0’） 
#define MAX2 40000           //解码字符数组的最大长度，100001/3

//哈夫曼树类型
typedef struct HTNode *HuffmanTree;
//哈夫曼树结点定义
struct HTNode {
    char Char;               //字符
    int Ori_Position;        //字符在原始序列的位置（用下标表示）
    int Weight;              //权值（即字符出现的频率）
    HuffmanTree Left;        //指向左子树
    HuffmanTree Right;       //指向右子树
    HuffmanTree Parent;      //指向父结点
};

//最小堆类型
typedef struct HNode *MinHeap;
//最小堆结点定义
struct HNode {
    HuffmanTree *Data;       //存放数据的数组，元素类型为HuffmanTree
    int Size;                //数组大小
};

//哈夫曼编码类型 
typedef struct HCNode *HuffmanCode;
//哈夫曼编码结点定义
struct HCNode {
    char Char;               //字符
    char *Code;              //哈夫曼编码（动态分配内存）
    int CodeLenth;           //哈夫曼编码长度
};

MinHeap AdjustHeap(MinHeap H);                             //调整为最小堆
MinHeap CreatMinHeap(char a[], int b[], int N);            //建立最小堆
HuffmanTree DeleteHeap(MinHeap H);                         //删除堆顶元素
void InsertHeap(MinHeap H, HuffmanTree T);                 //插入堆中
void AdjustChild(HuffmanTree T);                           //调整左右结点
HuffmanTree CreatHuffmanTree(char a[], int b[], int N);    //建立哈夫曼树
void PrintfHuffmanTree(HuffmanTree T);                     //打印哈夫曼树 
HuffmanTree ErgodicHuffmanTree(HuffmanTree T);             //递归将权值重新赋值
HuffmanCode *CreatHuffmanCode(HuffmanTree T, int N);       //生成编码（左边为0，右边为1）
void PrintfHuffmanCode(HuffmanCode *TC, int N);            //打印出所有字符及其对应的哈夫曼编码结果
int MessageTransmissionLength(HuffmanCode *TC, char Message[]);            //计算报文传输长度
int Decode(HuffmanTree T, char EncodingString[], char DecodeString[]);     //解码，如果失败显示“解码失败”

int main() 
{
    //原始字符序列
    char a[27] = {' ', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};
    //相应的权值
    int b[27] = {186, 64, 13, 22, 32, 103, 21, 15, 47, 57, 1, 5, 32, 20, 57, 63, 15, 1, 48, 51, 80, 23, 8, 18, 1, 16, 1};
    int N = 27, tag;

    char Message[] = "THIS PROGRAM IS MY FAVORITE";        //报文
    char EncodingString[MAX1];                             //输入的01串
    char DecodeString[MAX2];                               //解码结果

    //建立哈夫曼树
    HuffmanTree T = CreatHuffmanTree(a, b, N);
    //打印哈夫曼树
    PrintfHuffmanTree(T);
    
    //生成哈夫曼编码
    HuffmanCode *TC = CreatHuffmanCode(T, N);
    //打印哈夫曼编码
    PrintfHuffmanCode(TC, N);

    //打印“THIS PROGRAM IS MY FAVORITE”总的报文传输长度
    printf("“%s”总的报文传输长度为：%d\n\n", Message, MessageTransmissionLength(TC, Message));
    printf("*******************************************************************************************************************************************\n\n");

    //对用户输入的01串进行解码
    printf("请用户输入编码形式的字符串（仅由0和1组成）：");
    gets(EncodingString);
    tag = Decode(T, EncodingString, DecodeString);

    //打印解码结果
    if (tag == 1) {
        printf("译文为：%s\n\n", DecodeString);
        printf("*******************************************************************************************************************************************\n\n");
    } 
    else {
        printf("编码失败\n\n");
        printf("*******************************************************************************************************************************************\n\n");
    }
    return 0;
}

//调整为最小堆
MinHeap AdjustHeap(MinHeap H) 
{
    int i, Parent, Child;
    HuffmanTree Temp;
    
    //从最后一个有孩子的结点开始往前调整 
    for (i = H->Size / 2; i >= 1; i--) {
        for (Parent = i; 2 * Parent <= H->Size; Parent = Child) {
            Child = 2 * Parent;

            //Child指向最小的孩子结点
            if (Child != H->Size && (H->Data[Child]->Weight > H->Data[Child + 1]->Weight)) {
                Child++;
            }
            
            //找到相应的位置了 
            if (H->Data[Parent]->Weight > H->Data[Child]->Weight) {
                Temp = H->Data[Parent];
                H->Data[Parent] = H->Data[Child];
                H->Data[Child] = Temp;
            }
        }
    }
    return H;
}

//建立最小堆
MinHeap CreatMinHeap(char a[], int b[], int N) 
{
    MinHeap H = (MinHeap)malloc(sizeof(struct HNode));
    H->Size = N;

    //为Data数组分配内存，0不放元素
    H->Data = (HuffmanTree *)malloc((H->Size + 1) * sizeof(HuffmanTree));
    H->Data[0] = NULL;
    
    //一一填入结点信息 
    for (int i = 1; i <= H->Size; i++) {
        H->Data[i] = (HuffmanTree)malloc(sizeof(struct HTNode));
        H->Data[i]->Char = a[i - 1];
        H->Data[i]->Weight = b[i - 1];
        H->Data[i]->Ori_Position = i - 1;        //存放字符在原始序列中的位置（存下标，从0开始）
        H->Data[i]->Left = H->Data[i]->Right = H->Data[i]->Parent = NULL;
    }

    //调整为最小堆
    return AdjustHeap(H);
}

//删除堆顶元素
HuffmanTree DeleteHeap(MinHeap H)
{
    HuffmanTree Temp;

    Temp = H->Data[1];                    //将堆顶元素存起来
    H->Data[1] = H->Data[H->Size--];      //将最后一个元素赋给堆顶，并且堆的元素个数-1
    H = AdjustHeap(H);                    //重新调整为最小堆

    return Temp;                          //返回堆顶元素
}

//插入堆中
void InsertHeap(MinHeap H, HuffmanTree T) 
{
    H->Data[++H->Size] = T;               //将堆的元素个数+1，再将元素放在最后面
    H = AdjustHeap(H);                    //重新调整为最小堆
}

//调整左右结点
void AdjustChild(HuffmanTree T) 
{
    //如果左子结点的权值比右子结点的权值大
    if (T->Left->Weight > T->Right->Weight) {
        HuffmanTree Temp = T->Left;
        T->Left = T->Right;
        T->Right = Temp;
    }
    //如果左子结点的权值与右子结点的权值相等
    else if (T->Left->Weight == T->Right->Weight) {
        //如果原序列中T->Left在T->Right后面
        if (T->Left->Ori_Position > T->Right->Ori_Position) {
            HuffmanTree Temp = T->Left;
            T->Left = T->Right;
            T->Right = Temp;
        }
    }
}

//建立哈夫曼树
HuffmanTree CreatHuffmanTree(char a[], int b[], int N) 
{
    HuffmanTree T;
    MinHeap H = CreatMinHeap(a, b, N);            //建立最小堆
    int i;

    //进行N-1次合并
    for (i = 1; i < N; i++) {
        T = (HuffmanTree)malloc(sizeof(struct HTNode));
        T->Left = DeleteHeap(H);                  //从最小堆中删除一个结点，作为新T的左子结点
        T->Right = DeleteHeap(H);                 //从最小堆中删除一个结点，作为新T的右子结点
        AdjustChild(T);                           //调整左右结点，保证左子结点的权值小于等于右子结点的权值，
                                                  //并且权值相同时以原序列先出现的为左子结点
        T->Weight = T->Left->Weight + T->Right->Weight;       //计算新权值
        T->Char = '#';                                        //生成点的字符随便设置
        T->Ori_Position = MAXP;                               //当生成点与原始字符结点权值相同时，原始字符结点为左子结点
        T->Left->Parent = T->Right->Parent = T;               //设新T为父结点
        InsertHeap(H, T);                                     //将新T插入最小堆
    }

    T = DeleteHeap(H);
    return T;                  //返回指向哈夫曼树的根结点的指针T 
}

//打印哈夫曼树 
void PrintfHuffmanTree(HuffmanTree T)
{
    printf("*******************************************************************************************************************************************\n\n");
    printf("该哈夫曼树为：\n");
    printf("\t\t\t\t\t\t\t         #\t\t\t\t\t\t\t\t\n");
    printf("\t\t\t\t ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n");
    printf("\t\t\t\t#\t\t\t\t\t\t\t\t     #\t\t\t\t\n");
    printf("\t\t   ┏━━━━━━━━━━━┛━━━━━━━━━━━┓\t\t\t\t\t         ┏━━━━━━━━━━━┛━━━━━━━━━━━━━━━┓\n");
    printf("\t            #                       #\t\t\t\t\t    \t  #                          #\n");
    printf("\t  ┏━━━━━━━━┛━━━━━━━━┓\t  ┏━━━━━━━━┛━━━━━━━━┓\t\t\t\t┏━━━━━━━━┛━━━━━━┓    \t    ┏━━━━━━━━┛━━━━━━━━┓\n");
    printf("\t  #                 #\t  E                 #\t\t\t\t#                # \t     #                空格\n");
    printf("     ┏━━━┛━━━┓         ┏━━━┛━━━┓                ┏━━━┛━━━┓     \t\t     ┏━━┛━━┓         ┏━━┛━━┓     ┏━━┛━━┓               \n");
    printf("     #       H         R       S                I       N    \t\t      #     O         A    #      #     T                  \n");
    printf("  ┏━━┛━━┓                                                                 ┏━━┛━━┓         ┏━━┛━━┓     ┏━━┛━━┓            \n");
    printf("  C     U                                                                 #     #         D     L     #     #            \n");
    printf("                                                                        ┏━┛━┓ ┏━┛━┓                 ┏━┛━┓ ┏━┛━┓        \n");
    printf("                                                                        B   P G   Y                 #   W M   F        \n");
    printf("                                                                                                 ┏━━┛━━┓                    \n");
    printf("                                                                                                 V     #                    \n");
    printf("                                                                                                    ┏━━┛━━┓                 \n");
    printf("                                                                                                    #     K                 \n");
    printf("                                                                                                 ┏━━┛━━┓                    \n");
    printf("                                                                                                 #     #                    \n");
    printf("                                                                                               ┏━┛━┓ ┏━┛━┓               \n");
    printf("                                                                                               X   Z J   Q               \n\n");
    printf("*******************************************************************************************************************************************\n\n");
}

//递归将权值重新赋值
HuffmanTree ErgodicHuffmanTree(HuffmanTree T) 
{
    if(T){
        T->Weight = 0;
        ErgodicHuffmanTree(T->Left);
        ErgodicHuffmanTree(T->Right);
    }
    return T;
}

//生成编码（左边为0，右边为1）
HuffmanCode *CreatHuffmanCode(HuffmanTree T, int N) 
{
    HuffmanCode *TC = (HuffmanCode *)malloc((N + 1) * sizeof(HuffmanCode));
    //给各元素分配内存空间
    for (int i = 0; i < N + 1; i++) {
        TC[i] = (HuffmanCode)malloc(sizeof(struct HCNode));
    }

    HuffmanTree Temp = T;
    char cd[100];          //临时编码数组
    int cdlen = 0;         //记录编码串的长度

    //哈夫曼树已经建完，权值没有用了，这里将各个结点的权值重新赋值为0，用于记录访问结点的次数
    ErgodicHuffmanTree(Temp);

    //如果树不空
    while (Temp) {
        int i = 0;
        i=Temp->Ori_Position;            //记录Temp的位置，也是编码串应该插入的位置

        //如果当前结点一次没有访问，进入if
        if (Temp->Weight == 0) {
            Temp->Weight = 1;                  //重置访问次数为1

            //如果有左孩子，则访问左孩子，并且一路标记值为0
            if (Temp->Left != NULL) {
                Temp = Temp->Left;
                cd[cdlen++] = '0';
            }
            //当前结点没有左孩子，也没有右孩子，说明为叶子结点，直接记录哈夫曼编码
            else {
                cd[cdlen] = '\0';
                TC[i]->Code = (char *)malloc((cdlen + 1) * sizeof(char));
                TC[i]->Char = Temp->Char;
                strcpy(TC[i]->Code, cd);
                TC[i]->CodeLenth = cdlen;
            }
        }
        //如果Weight为1，说明访问过一次，即是从其左孩子返回的
        else if (Temp->Weight == 1) {
            Temp->Weight = 2;                   //重置访问次数为2

            //如果有右孩子，遍历右孩子，记录标记值为1
            if (Temp->Right != NULL) {
                Temp = Temp->Right;
                cd[cdlen++] = '1';
            }
        }
        //如果访问次数为2，说明左右孩子都遍历完了，返回父结点
        else {
            Temp->Weight = 0;
            Temp = Temp->Parent;
            cdlen--;
        }
    }
    return TC;                //返回最终的编码数组
}

//打印出所有字符及其对应的哈夫曼编码结果
void PrintfHuffmanCode(HuffmanCode *TC, int N) 
{
    printf("各字符的哈夫曼编码及其长度信息如下：\n");
    for (int i = 0; i < N; i++) {
        printf("%c的哈夫曼编码为：%-11s%,哈夫曼编码长度为：%d\n", TC[i]->Char, TC[i]->Code, TC[i]->CodeLenth);
    }
    printf("\n");
    printf("*******************************************************************************************************************************************\n\n");
}

//计算报文传输长度
int MessageTransmissionLength(HuffmanCode *TC, char Message[]) 
{
    int i = 0, sum = 0;
    char temp = Message[0];

    while (temp != '\0') {
        switch (temp) {
            case ' ':
                sum += TC[1]->CodeLenth;
                break;
            case 'A':
                sum += TC[2]->CodeLenth;
                break;
            case 'B':
                sum += TC[3]->CodeLenth;
                break;
            case 'C':
                sum += TC[4]->CodeLenth;
                break;
            case 'D':
                sum += TC[5]->CodeLenth;
                break;
            case 'E':
                sum += TC[6]->CodeLenth;
                break;
            case 'F':
                sum += TC[7]->CodeLenth;
                break;
            case 'G':
                sum += TC[8]->CodeLenth;
                break;
            case 'H':
                sum += TC[9]->CodeLenth;
                break;
            case 'I':
                sum += TC[10]->CodeLenth;
                break;
            case 'J':
                sum += TC[11]->CodeLenth;
                break;
            case 'K':
                sum += TC[12]->CodeLenth;
                break;
            case 'L':
                sum += TC[13]->CodeLenth;
                break;
            case 'M':
                sum += TC[14]->CodeLenth;
                break;
            case 'N':
                sum += TC[15]->CodeLenth;
                break;
            case 'O':
                sum += TC[16]->CodeLenth;
                break;
            case 'P':
                sum += TC[17]->CodeLenth;
                break;
            case 'Q':
                sum += TC[18]->CodeLenth;
                break;
            case 'R':
                sum += TC[19]->CodeLenth;
                break;
            case 'S':
                sum += TC[20]->CodeLenth;
                break;
            case 'T':
                sum += TC[21]->CodeLenth;
                break;
            case 'U':
                sum += TC[22]->CodeLenth;
                break;
            case 'V':
                sum += TC[23]->CodeLenth;
                break;
            case 'W':
                sum += TC[24]->CodeLenth;
                break;
            case 'X':
                sum += TC[25]->CodeLenth;
                break;
            case 'Y':
                sum += TC[26]->CodeLenth;
                break;
            case 'Z':
                sum += TC[27]->CodeLenth;
                break;
            default :
                printf("存在非法字符\n");
        }
        temp = Message[++i];
    }
    return sum;                //返回最终的传输长度
}

//解码，如果失败显示“解码失败”
int Decode(HuffmanTree T, char EncodingString[], char DecodeString[]) 
{
    HuffmanTree Temp = T;
    int i = 0, j = 0, tag;              //tag用来判断是否有无法对应找到字符的01字串被忽略
    char ch = EncodingString[0];

    while (ch != '\0') {
        tag = 1;

        //如果读取的字符为0，转向左子树
        if (ch == '0') {
            Temp = Temp->Left;
        }
        //如果读取的字符为1，转向右子树
        else if (ch == '1') {
            Temp = Temp->Right;
        }
        //否则就是非法字符
        else {
            printf("出现非法字符\n");
            return 0;
        }

        //Temp的左右孩子都为空，说明是叶结点了，将相应的字符存入，并且重新开始
        if (!Temp->Left && !Temp->Right) {
            tag = 0;                    //如果是找到字符了，赋值为0
            DecodeString[j++] = Temp->Char;
            Temp = T;
        }

        ch = EncodingString[++i];
    }
    DecodeString[j] = '\0';             //设置字符串结束标志

    //tag为1，说明后面的一串01串都没办法找到对应的字符
    if (tag == 1) {
        return 0;
    }
    return 1;
}

Answer 1

崩溃的时候在弹出的对话框按相应按钮进入调试，按Alt+7键查看Call Stack即“调用堆栈”里面从上到下列出的对应从里层到外层的函数调用历史。双击某一行可将光标定位到此次调用的源代码或汇编指令处，看不懂时双击下一行，直到能看懂为止。

在异常的语句前面，逐个输出各变量的当前值，看是否如预期。