猪脚说第十二期

不知道大家做完第五次作业有什么感受。其实说句实在话，第五次作业是整个七套作业中最简单的一次，猪脚两小时做完所有必做题，因为对于树的前、中、后序遍历以及BFS、DFS操作全部都可以直接套用模版或者封装成函数，只需要在一道题之内写出正确的代码片段，其它题目直接Ctrl+c、Ctrl+v就行，并且词频统计和表达式计算都是之前做过的题目所以整体来讲不会太花时间。

另外，大家也可以针对词频统计和表达式计算这两道题，综合对比一下各种数据结构解题的优劣与可拓展性。

树叶节点遍历（树-基础题）

这道题几乎没有坑点，考察大家对于树的相关概念和基本操作。最好的方式是按部就班地将每一个重要操作封装成函数，在main函数里直接按照逻辑进行调用，这样也可以为后续题目节省时间。

#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
    int num;
    int height;
    struct Node *left, *right;
}Basic_tree;
Basic_tree *insert(Basic_tree *root, int x, int high){
    high++;
    if(root == NULL){
        root = (Basic_tree*)malloc(sizeof(Basic_tree)); // 一定要记得malloc
        root->num = x;
        root->left = NULL;
        root->right = NULL; // 因为递归涉及非空判断，所以这个地方一定要初始化！
        root->height = high;
    }
    else if(x < root->num)
        root->left = insert(root->left, x, high);
    else
        root->right = insert(root->right, x, high); // 递归调用即可
    return root;
} // 插入操作，可直接当作模版使用
void trade(Basic_tree *a){
    if(a == NULL)
        return ;
    else if(a->left == NULL && a->right == NULL)
        printf("%d %d\n", a->num, a->height); // 前序遍历即可实现输出从左到右的叶节点
    trade(a->left);
    trade(a->right);
}
int main(){
    int i, n, x;
    Basic_tree *root = NULL;
    scanf("%d", &n);
    for(i=0;i<n;i++){
        scanf("%d", &x);
        root = insert(root, x, 0); // 每输入一个数就添加到树中
    }
    trade(root);
    return 0;
}

词频统计（树实现）

这道题的插入操作可以直接套用第一题写好的insert函数，再对建立好的树进行中序遍历即可符合题意要求输出，而中序遍历代码块只需要在第一题的前序遍历代码块上稍作顺序上的修改即可。

另外，不要以为这道题和之前的题目一样，它多了一个操作。程序应首先输出二叉排序树中根节点、根节点的右节点及根节点的右节点的右节点上的单词（个数不足则按实际个数输出），这一步如果在代码里没有判断的模块，很容易访问到空指针哦～

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAXSIZE 101
typedef struct Node{
    int count;
    char word[MAXSIZE];
    struct Node *left, *right;
}Basic_tree;
Basic_tree *insert(Basic_tree *root, char x[]){
    if(root == NULL){
        root = (Basic_tree*)malloc(sizeof(Basic_tree));
        strcpy(root->word,x);
        root->left = NULL;
        root->right = NULL;
        root->count = 1;
    }
    else if(strcmp(x,root->word) < 0)
        root->left = insert(root->left, x);
    else if(strcmp(x,root->word) > 0)
        root->right = insert(root->right, x);
    else
        root->count++; // 利用递归操作插入到合适位置
    return root;
}
int get(FILE *fp, char w[]){
    int i=0;
    char c;
    while(!(isalpha(c=fgetc(fp)))){
        if(c==EOF)
            return c;
        else
            continue;
    } // 跳过文件最开始的非字母字符
    do{
        w[i++] = tolower(c);
    }while(isalpha(c=fgetc(fp)));
    w[i]='\0';
    return 1;
}
void trade(Basic_tree *a){
    if(a == NULL)
        return ;
    trade(a->left);
    printf("%s %d\n", a->word, a->count);
    trade(a->right);
} // 中序遍历输出即可实现按照字典序输出
int main() {
    char wordtemp[MAXSIZE]={0};
    Basic_tree *root=NULL;
    FILE *in = fopen("article.txt","r");
    while(get(in,wordtemp) != EOF)
        root = insert(root,wordtemp); // 建树
    if(root == NULL);
    else if(root->right == NULL)
        printf("%s\n", root->word);
    else if(root->right->right == NULL)
        printf("%s %s\n", root->word, root->right->word);
    else
        printf("%s %s %s\n", root->word, root->right->word, root->right->right->word);
    trade(root);
    return 0;
}

计算器（表达式计算-表达式树实现）

该题的实现思路与具体步骤已经在题面中告诉大家了。其中中缀转后缀表达式的操作可以直接使用第四次作业题解中给出的Change(char s[])函数，而建立树的过程可以直接跟着题面描述走，最后对树进行后续遍历即可得到表达式的值，后续遍历操作直接在第一题的前序遍历代码块上稍作顺序上的修改即可，所以做起来其实是很快的。

一定要看题目是浮点数运算还是整型运算！！！

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
int num[201], ans[201], top=-1, top1=-1;
char op[201]={0};
typedef struct Node{
    int num;
    char op;
    struct Node *left, *right;
}Tree;
Tree savetree[1000];
Tree *treestack[1000]; // 树的指针栈
void Change(char s[]){
    int i, j=0, stacktop=-1;
    char stack[201]={0};
    for(i=0;s[i]!='\0';){
        while(isdigit(s[i])){
            num[j] = num[j]*10 + s[i++] - '0';
            if(!isdigit(s[i]))
                j++;
        }
        if(s[i]=='\0')
            break;
        if(s[i]=='(')
            stack[++stacktop]=s[i];
        else if(s[i]=='+'||s[i]=='-'){
            while(stacktop>-1){
                if(stack[stacktop]=='(')
                    break;
                else
                    op[j++]=stack[stacktop--];
            }
            stack[++stacktop]=s[i];
        }
        else if(s[i]=='*'||s[i]=='/'){
            while(stacktop>-1){
                if(stack[stacktop]=='('||stack[stacktop]=='+'||stack[stacktop]=='-')
                    break;
                else
                    op[j++]=stack[stacktop--];
            }
            stack[++stacktop]=s[i];
        }
        else if(s[i]==')'){
            while(stack[stacktop]!='(')
                op[j++]=stack[stacktop--];
            stacktop--;
        }
        i++;
    }
    while(stacktop>-1)
        op[j++]=stack[stacktop--];
} // 中缀转后缀表达式的即用模版
void trade(Tree *a){
    if(a == NULL)
        return ;
    trade(a->left);
    trade(a->right);
    if(a->op != '\0'){
        switch(a->op){
            case '+':
                a->num = a->left->num + a->right->num;
                break;
            case '-':
                a->num = a->left->num - a->right->num;
                break;
            case '*':
                a->num = a->left->num * a->right->num;
                break;
            case '/':
                a->num = a->left->num / a->right->num;
                break;
        }
    } // 在运算符的节点存储当前运算的值，最后根节点所存储的值即为表达式结果
} // 对表达式树进行后续遍历
int main(int argc, const char * argv[]) {
    int i, j=0;
    char x[201], s[201];
    gets(x);
    for(i=0;x[i]!='\0';i++){
        if(x[i]!=' '&&x[i]!='=')
            s[j++]=x[i];
    } // 删除空格
    s[j]='\0';
    Change(s);
    for(i=0;;i++){
        if(num[i]!=0){
            top++;
            top1++;
            savetree[top1].num=num[i];
            savetree[top1].left=savetree[top1].right=NULL;
            treestack[top]=&savetree[top1];
        }
        else if(op[i]!='\0'){
            top1++;
            savetree[top1].op=op[i];
            savetree[top1].left=treestack[top-1];
            savetree[top1].right=treestack[top];
            top--;
            treestack[top]=&savetree[top1];
        }
        if(num[i]==0&&op[i]=='\0')
            break;
    } // 按照题面描述建立表达式树
    if(treestack[0]!=NULL){
        if(treestack[0]->op!='\0')
            printf("%c ", treestack[0]->op);
        else
            printf("%d ", treestack[0]->num);
    }
    if(treestack[0]->left!=NULL){
        if(treestack[0]->left->op!='\0')
            printf("%c ", treestack[0]->left->op);
        else
            printf("%d ", treestack[0]->left->num);
    }
    if(treestack[0]->right!=NULL){
        if(treestack[0]->right->op!='\0')
            printf("%c ", treestack[0]->right->op);
        else
            printf("%d ", treestack[0]->right->num);
    }
    printf("\n");
    trade(treestack[0]);
    printf("%d\n", treestack[0]->num); // 根节点所储存的值就是最终运算结果
    return 0;
}

服务优化

这道题为2020级期末考试真题，并且是最后一题

该题一种简单做法是：某节点的编号直接对应到结构体树的数组下标里去，机场流量再另外开一个结构体存储，最后输出的时候建立映射关系即可。从上到下、从左到右的顺序可以利用BFS遍历实现，老师上课也讲过了，用队列实现即可。

需要注意的一点是，根节点的分支也不一定就是3个，一些同学会在这个细节上出错。

#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
    int name;
    struct Node *latter[3];
}Tree, *Treeptr;
Tree airport_branch[5000];
struct AirNode{
    int name;
    int flow;
}airport_record[5000];
int after[5000], gatenumber=0; // after数组存储原本从上到下、从左到右顺序所得节点的编号
int comp(const void * a, const void * b){
    struct AirNode *e1 = (struct AirNode*)a;
    struct AirNode *e2 = (struct AirNode*)b;
    if(e1->flow != e2->flow)
        return e2->flow - e1->flow;
    else
        return e1->name - e2->name;
}
void order(Treeptr t){
    Treeptr queue[5000], p;
    int front=0, rear=0;
    queue[0] = t;
    while(front<=rear){
        p=queue[front++];
        if(p->latter[0]==NULL&&p->latter[1]==NULL&&p->latter[2]==NULL){
            after[gatenumber++] = p->name;
        }
        if(p->latter[0]!=NULL)
            queue[++rear]=p->latter[0];
        if(p->latter[1]!=NULL)
            queue[++rear]=p->latter[1];
        if(p->latter[2]!=NULL)
            queue[++rear]=p->latter[2];
    }
} // 根据题意，此题需采取BFS遍历
int main() {
    int i, r, s;
    while(1){
        scanf("%d", &r);
        if(r==-1)
            break;
        else{
            airport_branch[r].name=r;
            i=0;
            while(1){
                scanf("%d", &s);
                if(s==-1)
                    break;
                else{
                    airport_branch[r].latter[i]=(Tree*)malloc(sizeof(Tree));
                    airport_branch[s].name=s;
                    airport_branch[r].latter[i++]=&airport_branch[s];
                }
            }
        }
    } // 至此，登机口节点树已全部建立好
    order(&airport_branch[100]); // 树根节点编号为100，则直接从该位置开始BFS遍历
    for(i=0;i<gatenumber;i++)
        scanf("%d %d", &airport_record[i].name, &airport_record[i].flow);
    qsort(airport_record,gatenumber,sizeof(struct AirNode),comp);
    for(i=0;i<gatenumber;i++)
        printf("%d->%d\n", airport_record[i].name, after[i]);
    return 0;
}

实验：树的构造与遍历

这道题没什么好说的，其实是一道比较无聊（指题面太长了，但真正需要大家实现的功能比较少）但又有点有趣（指可以通过这道题学习一种文本文件压缩方法）的题，具体步骤和功能题面上说的很清楚了，这里就不作赘述，直接上代码。

坑点包括第二个步骤不能一味的使用qsort函数，因为算法提示的第二个排序步骤并不是按照节点的字符大小排序的，而是“加入到其后”，而如果不处理字符大小的话，qsort函数对于权重相同的节点，其处理完后的顺序是完全随机的。部分同学在这个地方没有注意到细节。

另外，步骤四中关于char和unsigned char已在猪脚说中阐述。

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

#define MAXSIZE 32

struct tnode {                    //Huffman树结构
    char c;
    int weight;                    //树节点权重，叶节点为字符和它的出现次数
    struct tnode *left,*right;
} ;
int Ccount[128]={0};        //存放每个字符的出现次数，如Ccount[i]表示ASCII值为i的字符出现次数
struct tnode *Root=NULL;         //Huffman树的根节点
char HCode[128][MAXSIZE]={{0}}; //字符的Huffman编码
                                //如HCode['a']为字符a的Huffman编码（字符串形式）
int Step=0;                        //实验步骤
FILE *Src, *Obj;
    
void statCount();             //步骤1：统计文件中字符频率
void createHTree();           //步骤2：创建一个Huffman树，根节点为Root
void makeHCode();             //步骤3：根据Huffman树生成Huffman编码
void atoHZIP();               //步骤4：根据Huffman编码将指定ASCII码文本文件转换成Huffman码文件

void print1();                    //输出步骤1的结果
void print2(struct tnode *p);     //输出步骤2的结果
void print3();                    //输出步骤3的结果
void print4();                    //输出步骤4的结果


int main()
{
    if((Src=fopen("input.txt","r"))==NULL) {
        fprintf(stderr, "%s open failed!\n", "input.txt");
        return 1;
    }
    if((Obj=fopen("output.txt","w"))==NULL) {
        fprintf(stderr, "%s open failed!\n", "output.txt");
        return 1;
    }
    scanf("%d",&Step);                    //输入当前实验步骤
    
    statCount();                        //实验步骤1：统计文件中字符出现次数（频率）
    (Step==1) ? print1(): 1;             //输出实验步骤1结果
    createHTree();                        //实验步骤2：依据字符频率生成相应的Huffman树
    (Step==2) ? print2(Root): 2;         //输出实验步骤2结果
    makeHCode();                 //实验步骤3：依据Root为树的根的Huffman树生成相应Huffman编码
    (Step==3) ? print3(): 3;             //输出实验步骤3结果
    (Step>=4) ? atoHZIP(),print4(): 4;//实验步骤4：据Huffman编码生成压缩文件并输出实验步骤4结果

    fclose(Src);
    fclose(Obj);

    return 0;
}

//【实验步骤1】开始

void statCount()
{
    char c;
    while((c=fgetc(Src))!= EOF)
        Ccount[c]++;
}

//【实验步骤1】结束

//【实验步骤2】开始

void createHTree()
{
    struct tnode *p;
    struct tnode *tmp;
    struct tnode *treestack[1001];
    int top=-1;
    int i, j;
    Ccount[0]=1;
    for(i=0;i<128;i++){
        if(Ccount[i]>0){
            top++;
            p = (struct tnode *)malloc(sizeof(struct tnode));
            p->c = i;
            p->weight = Ccount[i];
            p->left = p->right = NULL;
            treestack[top]=p;
        }
    }
    for(i=0;i<top;i++){
        for(j=0;j<top-i;j++){
            if(treestack[j]->weight < treestack[j+1]->weight){
                tmp = treestack[j];
                treestack[j]=treestack[j+1];
                treestack[j+1]=tmp;
            }
            else if(treestack[j]->weight == treestack[j+1]->weight){
                if(treestack[j]->c < treestack[j+1]->c){
                    tmp = treestack[j];
                    treestack[j]=treestack[j+1];
                    treestack[j+1]=tmp;
                }
            }
        }
    }
    while(top){
        p = (struct tnode *)malloc(sizeof(struct tnode));
        p->weight = treestack[top]->weight + treestack[top-1]->weight;
        p->left = treestack[top];
        p->right = treestack[top-1];
        top--;
        treestack[top] = p;
        tmp = treestack[top];
        for(i=top-1;treestack[i]->weight<=treestack[top]->weight&&i>=0;i--);
        for(j=top-1;j>i;j--)
            treestack[j+1]=treestack[j];
        treestack[i+1]=tmp;
    }
    Root = treestack[top];
}

//【实验步骤2】结束

//【实验步骤3】开始
void visitHtree(struct tnode *p, char code, int level, char Huffman[]);
void visitHtree(struct tnode *p, char code, int level, char Huffman[]){
    if(level!=0)
        Huffman[level-1] = code;
    if(p->left==NULL&&p->right==NULL){
        Huffman[level] = '\0';
        strcpy(HCode[p->c], Huffman);
    }
    else{
        visitHtree(p->left, '0', level+1, Huffman);
        visitHtree(p->right, '1', level+1, Huffman);
    }
}
void makeHCode()
{
    char Huffman[MAXSIZE]={0};
    visitHtree(Root, '0', 0, Huffman);
}

//【实验步骤3】结束

//【实验步骤4】开始

void atoHZIP()
{
    unsigned char *pc,hc=0;
    int c=0,i=0;
    fseek(Src,0, SEEK_SET);
    do{
        c=fgetc(Src);
        if(c==EOF)
            c=0;
        for(pc=HCode[c];*pc!='\0';pc++){
            hc = (hc << 1) | (*pc - '0');
            i++;
            if(i==8){
                fputc(hc,Obj);
                printf("%x",hc);
                i=0;
            }
        }
        if(c==0&&i!=0){
            while(i++<8)
                hc = (hc << 1);
            fputc(hc,Obj);
            printf("%x",hc);
            }
         }while(c);
}

//【实验步骤4】结束

void print1()
{
    int i;
    printf("NUL:1\n");
    for(i=1; i<128; i++)
        if(Ccount[i] > 0)
            printf("%c:%d\n", i, Ccount[i]);
}

void print2(struct tnode *p)
{
    if(p != NULL){
        if((p->left==NULL)&&(p->right==NULL))
            switch(p->c){
                case 0: printf("NUL ");break;
                case ' ':  printf("SP ");break;
                case '\t': printf("TAB ");break;
                case '\n':  printf("CR ");break;
                default: printf("%c ",p->c); break;
            }
        print2(p->left);
        print2(p->right);
    }
}

void print3()
{
    int i;
    
    for(i=0; i<128; i++){
        if(HCode[i][0] != 0){
            switch(i){
                case 0: printf("NUL:");break;
                case ' ':  printf("SP:");break;
                case '\t': printf("TAB:");break;
                case '\n':  printf("CR:");break;
                default: printf("%c:",i); break;
            }
            printf("%s\n",HCode[i]);
        }
    }
}

void print4()
{
    long int in_size, out_size;
    
    fseek(Src,0,SEEK_END);
    fseek(Obj,0,SEEK_END);
    in_size = ftell(Src);
    out_size = ftell(Obj);
    
    printf("\n原文件大小：%ldB\n",in_size);
    printf("压缩后文件大小：%ldB\n",out_size);
    printf("压缩率：%.2f%%\n",(float)(in_size-out_size)*100/in_size);
}

非常感谢这位小伙伴看到了这里，那么就不吝啬地给出一道补充思考题吧！（有好的方法可以和猪脚探讨探讨，猪脚v你50😍）

在本次作业中，同学们学习了利用树结构将中缀表达式转化为后缀表达式，很明显，后缀表达式树的节点中是不包含左、右括号的。那么如果给你一个后缀表达式，你能把它转化成包含最少括号的中缀表达式（即若删除任意一对括号，都不能再转化为原来的后缀表达式）吗？

Author: diandian, Riccardo