🎄🎄🎆🎆🎆🎆🎄🎄
🎊🎊🎊🎊🎉🎉🎉🎉
🎄🎄🎄🎄🎄🎄🎄🎄🎄🎄
1.用C或C++语言建立二叉树，并实现二叉树的先根、中根、后根遍历。
2.在此基 础上，实现树与二叉树的相互转换。
3.实现一个简单的哈夫曼编码/译码器，能根据一段电文设计赫夫曼编码，并
能用该编码对一段给定的电文进行译码。
难度 A：建立二叉树，并实现二叉树的先根、中根、后根遍历；个人完成，
评分最高 70 分。
难度 B：在 A 的基础上，实现树与二叉树的相互转换；个人完成，评分最高
至 90 分。
难度 C：实现一个简单的哈夫曼编码/译码器，能根据一段电文设计赫夫曼
编码，并能用该编码对一段给定的电文进行译码。由 2-3 个人的团队完成，评分最高可至 100 分
main.cpp
#include "BiTree.h"#include "HuffmanCode.h"#define MAXSIZE 100#define MAXSIZE_msg 200#define MAXSIZE_Code 50 //定义Visit函数Status print(TElemType e){ printf("%c",e); return OK;} //A难度模块int Apro(void){ BiTree T; //定义二叉树T（二叉链表表示法） printf("按先序次序输入二叉树的结点的值，空格表示空树\n"); CreatBiTree(&T);//建立二叉树 Status (*Visit)(TElemType e)=print; //函数指针Visit指向print printf("生成二叉树的前序输出：\n"); PreOrderTraverse(T,Visit); //前序遍历 printf("\n"); printf("生成二叉树的中序输出：\n"); InOrderTraverse(T,Visit); //中序遍历 printf("\n"); printf("生成二叉树的后序输出：\n"); PostOrderTraverse(T,Visit); //后序遍历 printf("\n"); printf("按下Y返回上一级，按其他任意键退出程序"); char ch=getch(); if(ch==121||ch==89) return 1; //返回上一级 else exit(0); //退出程序} //B难度模块int Bpro(void){ CTree C; //定义树C（孩子链表表示法） BiTree T; //定义二叉树T（二叉链表表示法） InitCTree(&C); //初始化树C CreatCTree(&C); //建立树C printf("请确认您输入的树的信息:\n"); pr(&C); printf("按任意键开始将树转换为二叉树:\n"); fflush(stdin); getch(); CTreeToBiTree(C.r,&C,&T); //将树C转换成二叉树T Status (*Visit)(TElemType e)=print; 函数指针Visit指向print printf("转换中...完成\n"); printf("转换成的二叉树的前序输出：\n"); PreOrderTraverse(T,Visit); //前序输出转换后的树T printf("\n"); printf("转换成的二叉树的中序输出：\n"); InOrderTraverse(T,Visit); //中序输出转换后的树T printf("\n"); printf("转换成的二叉树的后序输出：\n"); PostOrderTraverse(T,Visit); //后序输出转换后的树T printf("\n"); printf("按下Y返回上一级，按其他任意键退出程序"); char ch=getch(); if(ch==121||ch==89) return 1; //返回上一级 else exit(0); //退出程序} int Cpro1(void){ HuffmanTree HT;//定义赫夫曼树 HuffmanCode HC;//定义赫夫曼编码 int n;//字符个数 char select; char* ch;//存放字符 char houzhui1[]="HuffmanCode.txt"; char houzhui2[]="KeyToCode.Key"; int* w;//存放权重 int i,j=0;//循环变量 FILE* fp;//文件流结构体 char e; //存放加密编码时从文件中读出的字符 char* file = (char*)malloc(sizeof(char) * MAXSIZE);//定义存放文件路径的一维数组 printf("请输入您想加密的字符个数：\n"); scanf("%d",&n); ch = (char*)malloc(n * sizeof(char)); //存放用户加密的字符 w = (int*)malloc(n * sizeof(int)); //存放对应字符的权重 fflush(stdin); printf("请输入您想加密的字符及其权重（空格分开），按回车完成一项的输入：\n"); for(i = 0;i <= n-1;i++){ //让用户依次输入加密的字符和权值 scanf("%c %d",&ch[i],&w[i]); fflush(stdin); } printf("生成编码中...完成\n"); printf("生成的各字符的赫夫曼编码如下:\n"); HuffmanCoding(&HT,&HC,w,n); //生成赫夫曼编码 for(i=1;i<=n;i++){ //打印生成的赫夫曼编码 printf("%c:",ch[i-1]); printf("%s",HC[i]); printf("\n"); } printf("是否导出编码信息？Y\\N\n"); select=getch(); fflush(stdin); if(select == 121 || select == 89){ printf("请输入编码信息的保存路径\n"); gets(file); strcat(file,houzhui1); while(!(fp=fopen(file,"w+"))){ //若打开文件失败则提示用户重新输入文件路径 printf("请输入正确路径：\n"); gets(file); strcat(file,houzhui1); } for(i = 0;i <= n-1;i++){ //导出编码到指定文件 fputc(ch[i],fp); fputc(':',fp); while( HC[i+1][j] != '\0'){ fputc(HC[i+1][j],fp); j++; } j = 0; fputc('\n',fp); } fclose(fp); printf("编码信息文件已生成\n"); } j=0; //循环变量重新赋值 printf("请输入生成的密匙路径\n"); gets(file); //得到输入的文件路径 strcat(file,houzhui2); while(!(fp=fopen(file,"w+"))){ //若打开文件失败则提示用户重新输入文件路径 printf("建立密匙失败，请确认密匙路径是否正确\n"); gets(file); strcat(file,houzhui2); } for(i = 0;i <= n-1;i++){ //将ASCII码进行处理后导入密匙，形成加密文件 fputc(ch[i]+168,fp); while( HC[i+1][j] != '\0'){ fputc(HC[i+1][j]+168,fp); j++; } j = 0; fputc('#'+168,fp); } fclose(fp); printf("密匙创建成功，它将是解码的唯一凭证\n"); printf("按下Y返回上一级，按其他任意键退出程序"); char chh=getch(); if(chh==121||chh==89) return 1; //返回上一级 else exit(0); //退出程序} int Cpro2(void){ int i,j=0;//循环变量 char* msg = (char*)malloc(sizeof(char) * MAXSIZE_msg);//存放要解码的信息 printf("请输入您想解码的信息\n"); gets(msg); HuffmanCode HCC; //存放从密匙中读入的信息 HCC = (char**)malloc(MAXSIZE_Code * sizeof(char*)); HCC[0] = (char*)malloc((MAXSIZE_Code*MAXSIZE_Code) * sizeof(char)); //为赫夫曼编码表生成空间 for(i = 1;i <= MAXSIZE_Code - 1;i++) HCC[i]=HCC[i-1] + MAXSIZE_Code; printf("请输入要载入的密匙路径：\n"); char* file2 = (char*)malloc(sizeof(char) * MAXSIZE);//定义存放文件路径的一维数组 FILE* fp2; gets(file2); //得到输入的文件路径 while(!(fp2=fopen(file2,"r"))){ //若打开文件失败则提示用户重新输入文件路径 printf("打开密匙失败，请确认密匙路径:\n"); gets(file2); } char e; e=fgetc(fp2) - 168; //e存放从密匙中读取的一个字符 i=1; //循环变量重新赋值 while(e != EOF){ //导入密匙信息 if(e != '#'){ HCC[i][j] = e; j++; } else{ HCC[i][j] = '\0'; i++; j = 0; } e=fgetc(fp2); if( e != EOF) e = e-168; } int z = i-1;//z代表字符个数 i=0;// 循环变量重新赋值 int b = 1;//指示当前匹配到第几个字符 int d = 1;//指示当前匹配到字串的第d个字符 int n; //指示当前从第几个msg开始比的 printf("解码中...完成\n"); printf("代表信息如下：\n"); while(msg[i] != '\0'){ n = i; while(b <= z){ while((msg[n] == HCC[b][d])&&(!((msg[n] == '\0')&&(HCC[b][d] == '\0')))){ //当前字符匹配则指针前移 n++; d++; } if(HCC[b][d] == '\0'){ // 判断是否匹配 printf("%c",HCC[b][0]); //输出编码 i = n; //变量重新赋值 b = 1; d = 1; break; } else if(n == z){ //如果是最后一个字符完成匹配查询，则主串指针前移一个字符继续匹配 i++; b = 1; d = 1; break; } else{ // 匹配下一个字符的赫夫曼编码 n=i; b++; d=1; } } } printf("\n按下Y返回上一级，按其他任意键退出程序"); char chh=getch(); if(chh==121||chh==89) return 1; //返回上一级 else exit(0); //退出程序} int main(){ begin:system("cls"); int select; //存放用户选择的难度 printf("输入1转入难度A对应程序（建立二叉树并实现二叉树的先根、中根、后根遍历）\n"); printf("输入2转入难度B对应程序（树的建立、树与二叉树的相互转换）\n"); printf("输入3转入难度C对应程序（赫夫曼编码/译码器）\n"); scanf("%d",&select); fflush(stdin); //清空缓存区 switch(select){ case 1:{ if(Apro() == 1) //执行A难度程序 goto begin;}break; case 2:{ if(Bpro() == 1) //执行B难度程序 goto begin;}break; case 3:{ printf("输入1进入编码加密器，输入2进入编码解密器\n"); int select2; scanf("%d",&select2); fflush(stdin); switch(select2){ case 1:{ if(Cpro1() == 1) //执行编码程序 goto begin;} case 2:{ if(Cpro2() == 1) //执行解码程序 goto begin;} }break; } } return 0;}BiTree.h
#include "Public.h"#include "CTree.h"char ch; //二叉树的链式存储结构typedef struct BiTNode{ TElemType data; struct BiTNode* lchild; struct BiTNode* rchild;}BiTNode,*BiTree; //按先序次序输入二叉树的结点的值，空格表示空树Status CreatBiTree(BiTree* T); //先序遍历二叉树T，对每个结点调用Visit函数一次，若Visit失败则操作失败返回ERROR，否则返回OKStatus PreOrderTraverse(BiTree T,Status (*Visit)(TElemType e)); //中序遍历二叉树T，对每个结点调用Visit函数一次，若Visit失败则操作失败返回ERROR，否则返回OKStatus InOrderTraverse(BiTree T,Status (*Visit)(TElemType e)); //后序遍历二叉树T，对每个结点调用Visit函数一次，若Visit失败则操作失败返回ERROR，否则返回OKStatus PostOrderTraverse(BiTree T,Status (*Visit)(TElemType e)); //将带双亲的孩子链表存储表示的树C，转换成二叉链表表示的二叉树T，now代表根节点所在位置C.rStatus CTreeToBiTree(int now,CTree* C,BiTree* T); //CreatBiTree操作的实现Status CreatBiTree(BiTree* T){ scanf("%c",&ch); fflush(stdin); if(ch == ' ') *T = NULL; else{ if(NULL == (*T = (BiTree)malloc(sizeof(BiTNode)))) exit(OVERFLOW); (*T)->data = ch; //创建树或子树的根节点 CreatBiTree(&((*T)->lchild)); //创建坐子树 CreatBiTree(&((*T)->rchild)); //创建右子树 } return OK;} //PreOrderTraverse操作的实现Status PreOrderTraverse(BiTree T,Status (*Visit)(TElemType e)){ if(T != NULL){ if(OK == (*Visit)(T->data)) //访问节点 if(OK == PreOrderTraverse(T->lchild,Visit)) //遍历左子树 if(OK == PreOrderTraverse(T->rchild,Visit)) //遍历右子树 return OK; return ERROR; } else return OK;} //InOrderTraverse操作的实现Status InOrderTraverse(BiTree T,Status (*Visit)(TElemType e)){ if(T != NULL){ if(OK == InOrderTraverse(T->lchild,Visit)) if(OK == (*Visit)(T->data)) if(OK == InOrderTraverse(T->rchild,Visit)) return OK; return ERROR; } else return OK;} //PostOrderTraverse操作的实现Status PostOrderTraverse(BiTree T,Status (*Visit)(TElemType e)){ if(T != NULL){ if(OK == PostOrderTraverse(T->lchild,Visit)) if(OK == PostOrderTraverse(T->rchild,Visit)) if(OK == (*Visit)(T->data)) return OK; return ERROR; } else return OK;} //CTreeToBiTree操作的实现Status CTreeToBiTree(int now,CTree* C,BiTree* T){ (*T)=(BiTree)malloc(sizeof(BiTNode)); //创建二叉树根（子树的根）节点 (*T)->data=C->nodes[now].data; (*T)->rchild=NULL; //首先将节点的rchild置为空，保证转换成的二叉树根节点的右子树为空 ChildPtr p; //p用来暂时存放孩子指针 p=C->nodes[now].firstchild; //将二叉树根（子树的根）节点的第一个孩子指针赋予p if(p!=NULL){ //若二叉树根（子树的根）节点有孩子 CTreeToBiTree(p->child,C,&((*T)->lchild)); //创建二叉树根（子树的根）节点的左孩子为该第一个孩子 BiTree q = (*T)->lchild; //q用来暂时存放兄弟节点的指针 p=p->next; //下一个孩子 while(NULL != p){ //所有孩子 CTreeToBiTree(p->child,C,&(q->rchild)); //创建二叉树根（子树的根）节点的左孩子的右孩子为第一个孩子的兄弟节点 p=p->next; q=q->rchild; } } else{ //若是叶子节点则置左右孩子为空 (*T)->lchild=NULL; (*T)->rchild=NULL; } return OK;}CTree.h
#include "Public.h"#define MAX_TREE_SIZE 100 //树的带双亲的孩子链表存储表示typedef struct CTNode{ int child; struct CTNode* next;}*ChildPtr; //定义一个节点项typedef struct{ int parent; TElemType data; ChildPtr firstchild; //指向第一个孩子}CTBox; typedef struct{ CTBox nodes[MAX_TREE_SIZE]; int n,r; //节点数和根的位置}CTree; //初始化一棵树TStatus InitCTree(CTree* T); //创建一棵树TStatus CreatCTree(CTree* T); //打印树TStatus pr(CTree* T); //InitCTree操作的实现Status InitCTree(CTree* T){ T->n = 0; T->r = 0; for(int i=0;i<=MAX_TREE_SIZE-1;i++) //将所有节点的孩子指针初始化为空 T->nodes[i].firstchild=NULL; return OK;} //CreatCTree操作的实现Status CreatCTree(CTree* T){ char ch=0; //用来存放用户输入的字符 int i=0; int j=0; //i，j为次数变量 char p; //存放双亲 printf("请按任意次序输入所有节点的值,输入空格代表结束\n"); printf("若您想进行二叉树的转换，请按从树根到树底，从最左孩子到最右孩子的次序输入\n"); scanf("%c",&ch); fflush(stdin); //清除缓冲区 while(ch != ' '){ //让用户输入节点的值直到用户输入空格 T->nodes[i].data=ch; i++; scanf("%c",&ch); fflush(stdin); } printf("\n"); T->n=i; for(i=0;i<=T->n-1;i++){ //让用户输入每个节点的双亲 printf("请输入%c节点的双亲,若是根节点则输入空格\n",T->nodes[i].data); scanf("%c",&p); if(' '==p){ //如果是根 T->nodes[i].parent=-1;//根节点双亲的位置置为-1 T->r=i; fflush(stdin); continue; } fflush(stdin); for(j=0;j<=T->n-1;j++){ if(p != T->nodes[j].data) //寻找双亲的位置j continue; T->nodes[i].parent=j; //将节点的双亲置为j ChildPtr q=(ChildPtr)malloc(sizeof(CTNode)); //创建双亲的孩子节点 q->child=i; q->next=NULL; ChildPtr r=T->nodes[j].firstchild; if(NULL == r) T->nodes[j].firstchild=q; else{ while(NULL !=r->next) r=r->next; r->next=q; } } } return OK;} //打印操作的实现Status pr(CTree* T){ int i=0; int j=0; ChildPtr p; for(;i<=T->n-1;i++){ if(T->nodes[i].parent!=-1) printf("节点值：%c 双亲：%c ",T->nodes[i].data,T->nodes[T->nodes[i].parent].data); else printf("节点值：%c 根节点无双亲 ",T->nodes[i].data); p=T->nodes[i].firstchild; while(NULL != p){ printf(" 孩子：%c ",T->nodes[p->child].data); p=p->next; } printf("\n"); } return OK;}public.h
#include <stdio.h>#include <malloc.h>#include <stdlib.h>#include <conio.h> //getch（）#include <string.h>#define TRUE 1#define OK 2#define FALSE 0#define ERROR -1#define OVERFLOW -2typedef int Status; typedef char TElemType;HuffmanCode.h
#include "Public.h" typedef struct{ int weight; int parent,lchild,rchild;}HTNode,*HuffmanTree; //动态分配数组存储赫夫曼树 typedef char **HuffmanCode; //动态分配数组存储赫夫曼编码表 //求赫夫曼编码,w存放n个字符的权值（均>0），构造赫夫曼树HT，并求出n个字符的赫夫曼编码HCvoid HuffmanCoding(HuffmanTree* HT,HuffmanCode* HC,int* w,int n){ int i=1; int j=1; int firstsmall,secondsmall; HuffmanTree p; if(n <= 1) return; int m = 2 * n - 1; (*HT) = (HuffmanTree)malloc(sizeof(HTNode) * (m + 1)); (*HT)[0].weight=9999; for(p = (*HT) + 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最小的两个节点，其序号分别为firstsmall和secondsmall firstsmall = 0; secondsmall = 0; for(j = 1;j <= i-1;j++){ if((*HT)[j].parent != 0) continue; if((*HT)[j].weight <= (*HT)[firstsmall].weight || (*HT)[j].weight <= (*HT)[secondsmall].weight){ if((*HT)[firstsmall].weight <= (*HT)[secondsmall].weight) secondsmall = j; else firstsmall = j; } } //select(HT,i-1, &firstsmall,&secondsmall); (*HT)[firstsmall].parent = i; (*HT)[secondsmall].parent = i; (*HT)[i].lchild = firstsmall; (*HT)[i].rchild=secondsmall; (*HT)[i].weight=(*HT)[firstsmall].weight + (*HT)[secondsmall].weight; } //从叶子到根逆向求每个字符的赫夫曼编码 (*HC) = (HuffmanCode)malloc((n + 1)*sizeof(char*)); //分配n个字符编码的头指针向量 char* cd = (char*)malloc(n*sizeof(char)); //分配求编码的工作空间 cd[n-1]='\0'; //编码结束符 int start; int c; //存放当前节点位置 int f; //存放父节点位置 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)); //为第i个字符编码分配空间 int k; strcpy((*HC)[i],&cd[start]); } free(cd); //释放cd }//HuffanCoding代码文件下载https://github.com/Maximusarthur/Strengthen-Code
声明：文中观点不代表本站立场。本文传送门：https://eyangzhen.com/206916.html
