实验ios |
实验三 Huffman编码的实现算法 |
学院编程 |
|
专业(班级)函数 |
|
姓名学习 |
|
学号编码 |
|
教师spa |
|
1. 掌握二叉树的存储结构。设计
2. 掌握二叉树的遍历操做的实现方法。3d
3. 掌握创建Huffman树及求Huffman编码的操做,加深对二叉树应用的理解。指针
1. 二叉树采用二叉链表存储结构
2. 二叉树的遍历操做能够用递归算法实现
硬件平台:计算机CPU 主频2.0G以上;内存128兆以上;
软件平台:Windows2003或以上版本,Visual C++6.0。
1. 设计一棵二叉树,输入彻底二叉树的先序序列,用#表明虚结点(空指针),如ABD###CE##F##,创建二叉树。
2. 实现二叉树的前序、中序和后序遍历。
3. 设计一个哈夫曼编码系统, 根据字符频率构造哈夫曼树,并给出每一个字符的哈夫曼编码。
2.需求分析:
(1)初始化:从键盘输入n个字符的权值,创建哈夫曼树。
(2)创建哈夫曼树。
(3)编码:利用建好的哈夫曼树对各权值进行编码,输出各权值的哈夫曼编码。
(4)初始化二叉树:输入彻底二叉树的先序序列,用#表明虚结点(空指针),如ABD###CE##F##,创建二叉树。
(5)先序,中序,后序遍历二叉树。
(6)输出遍历字符串。
3.概要设计:
//---------赫夫曼树的存储结构----------
typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;
Void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
//求赫夫曼编码
//-------------二叉树存储结构
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
Status CreateBiTree(BiTree &T)
//创建二叉树
void PreOrderTraverse(BiTree T)
//先序遍历二叉树
void InOrderTraverse(BiTree T)
//中序遍历二叉树
void PostOrderTraverse(BiTree T)
//后序遍历二叉树
void Select(HuffmanTree &HT, int n, int &s1, int &s2)
//选出权值最小的两个权值
4.功能结构图
//哈夫曼树构造原则: 权值小的在前,相等的单节点在前;
#include <stdio.h> #include <stdlib.h> #include <string.h> #include<iostream> #include<stack> #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 using namespace std; typedef char TElemType ; typedef int Status ; typedef struct{ unsigned int weight; unsigned int parent,lchild,rchild; }HTNode,*HuffmanTree; typedef char **HuffmanCode; typedef struct BiTNode{ TElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; Status CreateBiTree(BiTree &T){ char ch; scanf("%c",&ch); if('#'==ch) T=NULL; else{ T=new BiTNode; T->data=ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } } Status Visit(TElemType e){ printf("%c ",e); return OK; } void PreOrderTraverse(BiTree T){ if(T) { printf("%c ",T->data); PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } } void InOrderTraverse(BiTree T){ if(T) { InOrderTraverse(T->lchild); printf("%c ",T->data); InOrderTraverse(T->rchild); } } void PostOrderTraverse(BiTree T){ if(T) { PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); printf("%c ",T->data); } } void Select(HuffmanTree &HT, int n, int &s1, int &s2) { //在HT[1..n]中选择parent为0且weight最小的两个结点, // 其序号分别为s1和s2。 int i; s1=-1;s2=-1; for(i=1; i<=n; i++) if(HT[i].parent == 0) { if(s1 == -1) s1 = i; else if(HT[i].weight < HT[s1].weight) { s2 = s1; s1 = i; } else if(s2 == -1 || HT[i].weight < HT[s2].weight) s2 = i; } } void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) { // 并求出n个字符的哈夫曼编码HC int i, m, s1, s2, start; char *cd; unsigned int c, f; if (n<=1) return; m = 2 * n - 1; HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0号单元未用 for (i=1; i<=n; i++) { //初始化 HT[i].weight=w[i-1]; HT[i].parent=0; HT[i].lchild=0; HT[i].rchild=0; } for (i=n+1; i<=m; i++) { //初始化 HT[i].weight=0; HT[i].parent=0; HT[i].lchild=0; HT[i].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; HT[i].lchild = s1; HT[i].rchild = s2; HT[i].weight = HT[s1].weight + HT[s2].weight; } //--- 从叶子到根逆向求每一个字符的哈夫曼编码 --- cd = (char *)malloc(n*sizeof(char)); // 分配求编码的工做空间 cd[n-1] = '\0'; // 编码结束符。 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个字符编码分配空间 strcpy(HC[i], &cd[start]); // 从cd复制编码(串)到HC } free(cd); //释放工做空间 } //HuffmanCoding void mainview_user( ) //界面函数 { BiTree T; int c; while(1) { system("CLS"); //清除屏幕函数 printf(" ------------------------------------\n"); printf(" |**********二叉树的应用*********|\n"); printf(" |********1 哈夫曼编码*********|\n"); printf(" |********2 输入二叉树*********|\n"); printf(" |********3 前序遍历***********|\n"); printf(" |********4 中序遍历***********|\n"); printf(" |********5 后序遍历***********|\n"); printf(" |********0 退出系统***********|\n"); printf(" ------------------------------------\n"); printf("\n"); printf("请选择:"); scanf("%d",&c); switch(c) { case 1: { int i,n; int *w; HuffmanTree HT; HuffmanCode HC; printf("请输入要输入权值的数量:"); scanf("%d",&n); //权值个数 w=(int *)malloc(n*sizeof(int)); printf("Input weights:"); for ( i=0;i<n;i++) //录入权值 scanf("%d",&w[i]); HC=(char **)malloc((n+1)*sizeof(char*)); //0空间未用 HT=(HuffmanTree)malloc((2*n+1+1)*sizeof(HTNode));//0空间未用 HuffmanCoding(HT, HC, w, n); printf("\n"); for (i = 1; i<n+1; i++){ printf("权值%d的哈夫曼编码为:",w[i-1]) ; printf("%s\n", HC[i]); //输出哈夫曼编码 free(HC[i]); //释放空间 } free(HC); free(HT); break; } case 2: { printf("按先序读入字符串:"); getchar(); CreateBiTree(T); break; } case 3: { PreOrderTraverse(T); break; } case 4: { InOrderTraverse(T); break; } case 5: { PostOrderTraverse(T); break; } case 0: { return; } default:printf("输入错误,请从新输入!\n");fflush(stdin); } printf("\n\n"); system("PAUSE"); } } int main() { mainview_user( ); return 0; }