数据结构课程设计报告
《数据结构－－C++实现》
课程设计报告
院：计算机学院
1
学专业班级：软件工程 数据结构课程设计报告
题目:哈夫曼编/译码器
【问题描述】利用哈夫曼编码可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对传输数据预先编码，在接收端将传来的数据进行译码。对于双工信道，每端都需要一个完整的编/译码器。试为这样的通信端编写一个哈夫曼编/译码器。 一.需求分析
1.运行环境(软、硬件环境)
Visual studio 2008 2.程序实现的功能
初始化：输入一串字符（正文），计算不同字符（包括空格）的数目以及每种字符出现的频率（以该种字符出现的次数作为其出现频率），根据权值建立哈夫曼树，输出每一种字符的哈夫曼编码。
编码：利用求出的哈夫曼编码，对该正文（字符串）进行编码，并输出。
译码：对于得到的一串编码，利用已求得的哈夫曼编码进行译码，将译出的正文输出。
输出哈夫曼树形态：以树的形式输出哈夫曼树。 3.程序的输入
一串字符(英文)或短文(英文) 4.程序的输出
根据用户需求不同有相应的输出
1
数据结构课程设计报告
5.测试数据
there are three students 二.设计说明 1.算法设计的思想
建立链表类、栈类、队列类、哈夫曼结点类、哈夫曼树类，通过主函数调用的方法来实现程序的功能。 2.主要的数据结构说明 链表模板类:
template//模板链表类 class LinkList { private : };
HuaffmanTreeNode *head;//链表的头结点 Type List[1000]; LinkList(void); ~LinkList(void);
HuaffmanTreeNode *GetHead();// void SetHead(HuaffmanTreeNode *h);// void Insert(HuaffmanTreeNode *p);//
HuaffmanTreeNode* IsTheSame(HuaffmanTreeNode *pa);//判断pa是否有相同的结点，如void CreateList();//创建一个哈弗曼结点的链表 int GetLength();
HuaffmanTreeNode* Delete(HuaffmanTreeNode *p);//删除结点 HuaffmanTreeNode*Copy();//复制链表 bool CheckAllTure();//检查是否全部加入哈弗曼树 public:
果有相同返回该结点,否则返回NULL
栈模板类:
template//模板栈类 class Stack { private :
T Data[MAX];
2
数据结构课程设计报告
int top;
public :
Stack();//构造函数 bool push(T num);//进栈操作 T pop();//出栈操作
T Get_top();//得到栈顶的元素 bool Empty();//判断栈是否为空 bool Full();//判断栈是否已满 void Clear();//清空栈
};
队列模板类:
template//模板队列类 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();//清空队列
};
哈夫曼结点模板类:
template//模板哈夫曼结点类 class HuaffmanTreeNode { private : int Key;//该字符出现的次数； Type Data;// 输入的字符元素；
HuaffmanTreeNode *parent;//双亲结点指针; HuaffmanTreeNode *lchild;//左孩子结点指针; HuaffmanTreeNode *rchild;//右孩子结点指针;
int Tag;//记录该结点是双亲的左右孩子，左孩子为，有孩子为; HuaffmanTreeNode *next;//下一个结点，用于链表
bool Flag;//标记该结点是否已经计入哈弗曼树
public:
3
数据结构课程设计报告
};
HuaffmanTreeNode(void);//默认构造函数; HuaffmanTreeNode(int
k,Type
d,int
t,HuaffmanTreeNode
*p=NULL,HuaffmanTreeNode*l=NULL,HuaffmanTreeNode *r=NULL);//构造函数
~HuaffmanTreeNode(void);//默认析构函数; int GetKey();//得到该结点在正文中出现的次数 void SetKey(int key);//设置关键字的次数 Type GetData();//得到该结点对应的文字编码 void SetData(Type data);//设置结点的文字编码
HuaffmanTreeNode *GetParent();//得到该结点的双亲结点 void SetParent(HuaffmanTreeNode *p);//设置双亲结点 HuaffmanTreeNode *GetLchild();//得到左孩子结点 void SetLchild(HuaffmanTreeNode *p);//设置左孩子结点 HuaffmanTreeNode *GetRchild();//得到右孩子结点 void SetRchild(HuaffmanTreeNode *p);//设置右孩子结点 int GetTag();//得到标记 void SetTag(int t);//设置标记
HuaffmanTreeNode *GetNext();//得到下一个结点 void SetNext(HuaffmanTreeNode *p);//设置下一个结点 bool GetFlag(){ return Flag;} void SetFlag(bool tag){Flag=tag;}
哈夫曼树模板类:
template//模板哈夫曼树类 class HuaffmanTree {
HuaffmanTreeNode *Root;//树根结点 Queue qu;//存放密码 HuaffmanTree(void); ~HuaffmanTree(void);
void SetRoot(HuaffmanTreeNode *p){this->Root=p;} HuaffmanTreeNode *GetRoot(){return Root;}
HuaffmanTreeNode *Merge(HuaffmanTreeNode* pa,HuaffmanTreeNode* pb);//合void CreateTree(LinkList L1);//创建哈夫曼树 int * GetCode(Type data,LinkList L);//得到编码 void Coding(LinkList L);//编码 void DeCode(LinkList L);//译码函数
void Display(HuaffmanTreeNode*p,int n);//遍历哈夫曼树 HuaffmanTreeNode *Find(Type data,LinkList L); void GetCharFrenquency(LinkList L);//得到每种字符出现的次数 void ShowPriorText(LinkList L);
public:
并两个结点
4