哈夫曼编、译码器.docVIP

《数据结构－－C++实现》 课程设计报告 题目:哈夫曼编/译码器 【问题描述】利用哈夫曼编码可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对传输数据预先编码，在接收端将传来的数据进行译码。对于双工信道，每端都需要一个完整的编/译码器。试为这样的通信端编写一个哈夫曼编/译码器。 需求分析 运行环境(软、硬件环境) Visual studio 2008 程序实现的功能 初始化：输入一串字符（正文），计算不同字符（包括空格）的数目以及每种字符出现的频率（以该种字符出现的次数作为其出现频率），根据权值建立哈夫曼树，输出每一种字符的哈夫曼编码。 编码：利用求出的哈夫曼编码，对该正文（字符串）进行编码，并输出。 译码：对于得到的一串编码，利用已求得的哈夫曼编码进行译码，将译出的正文输出。 输出哈夫曼树形态：以树的形式输出哈夫曼树。 程序的输入 一串字符(英文)或短文(英文) 程序的输出 根据用户需求不同有相应的输出 测试数据 there are three students 设计说明 算法设计的思想 建立链表类、栈类、队列类、哈夫曼结点类、哈夫曼树类，通过主函数调用的方法来实现程序的功能。 主要的数据结构说明 链表模板类: templateclass Type//模板链表类 class LinkList { private : HuaffmanTreeNodeType *head;//链表的头结点 public: Type List[1000]; LinkList(void); ~LinkList(void); HuaffmanTreeNodeType *GetHead();// void SetHead(HuaffmanTreeNodeType *h);// void Insert(HuaffmanTreeNodeType *p);// HuaffmanTreeNodeType* IsTheSame(HuaffmanTreeNodeType *pa);//判断pa是否有相同的结点，如果有相同返回该结点,否则返回NULL void CreateList();//创建一个哈弗曼结点的链表 int GetLength(); HuaffmanTreeNodeType* Delete(HuaffmanTreeNodeType *p);//删除结点 HuaffmanTreeNodeType*Copy();//复制链表 bool CheckAllTure();//检查是否全部加入哈弗曼树 }; 栈模板类: templatetypename T//模板栈类 class Stack { private : T Data[MAX]; int top; public : StackT();//构造函数 bool push(T num);//进栈操作 T pop();//出栈操作 T Get_top();//得到栈顶的元素 bool Empty();//判断栈是否为空 bool Full();//判断栈是否已满 void Clear();//清空栈 }; 队列模板类: templatetypename T//模板队列类 class Queue { private : T num[MAX];//队列中的数据元素 int front,rear;//队首，队尾的标志 public: Queue(void);//构造函数 ~Queue(void);//析构函数 void EnQueue(T p);//入队操作 T DeQueue();//出队操作 bool IsEmpty();//判断队列是否为空 bool IsFull();//判断队列是否已满 void Clear();//清空队列 }; 哈夫曼结点模板类: templateclass Type//模板哈夫曼结点类 class HuaffmanTreeNode { private : int Key;//该字符出现的次数； Type Data;// 输入的字符元素； HuaffmanTreeNodeType *parent;//双亲结点指针; HuaffmanTreeNodeType *lchild;//左孩子结点指针; HuaffmanTreeNodeType *rchild;//右孩子结点指针; int Tag;//记录该结点是双亲的左右孩子，左孩子为，有孩子为; HuaffmanTreeNodeType *next;//下一个结点，用于链表 bool Flag;//标记该结点是否已经计入哈弗曼树 public: HuaffmanTreeNode(void);//默认构造函数;