huffman实验报告5

一、对问题的描述1.实验主题：霍夫曼编解码器2.基本要求：初始化。从终端读取字符集大小n、n个字符和n个权重，建立一个哈夫曼树并存储在高频树中。编码。使用构建的哈夫曼树(如果它不在内存中，应该从文件hfmTree中读取)，对文件ToBeTran中的文本进行编码，然后将结果存储在文件CodeFile中。解码。建立的哈夫曼树用于解码文件代码文件中的代码，并将结果存储在文本文件中。打印代码文件。文件代码文件以紧凑的格式显示在终端上，每行50个代码。同时，这种字符形式的编码文件被写入文件代码打印。打印霍夫曼树。已经在存储器中的霍夫曼树以直观的形式(树或凹形式)显示在终端上，并且该字符形式的霍夫曼树被写入文件TreePrint。3.测试数据：霍夫曼树是用下表中给出的字符集和频率的实际统计数据建立的，下面的消息被编码和解码：“这个程序是我最喜欢的”。字符ABCDEFGHiJKLM频率1866413223210321154757153220字符NOPQrSTUVWXYZ频率5763151485180238181161输入/输出：字符集大小n、n个字符和n个权重值都从终端读取。初始化的霍夫曼树存储在hfmTree文件中。要编码的文件是要传输的。编码结果以文本形式存储在文件代码文件中。解码后的文件存储在文本文件中。打印的编码和赫夫曼树分别存储在代码打印和树打印文件中。用户界面可设计为“菜单”模式：显示上述功能符号，并添加退出功能“Q”以指示退出(退出)。用户输入一个选择功能字符，该功能执行后菜单将显示，直到用户选择q。二。需求分析1.该程序可以根据输入的字符集和频率建立哈夫曼树，并对给定的文本进行编码和解码。它还可以直接读取已建立的哈夫曼树，对给定的文本进行编码和解码，打印编码、解码结果、表格和树形哈夫曼树。2.程序运行后，将显示提示消息，提示用户选择要执行的操作。输入提示的字符总数，后跟每个字符及其权重(输入时用逗号分隔)。字符为字符类型，权重为整数类型。输入字符总数。d:不需要输入。p:不需要输入。t:不需要输入。问：结束程序。3.用户输入后，输出结果如下：I:已建立的霍夫曼树以列表的形式存储在hfmtree.txt中。从左到右，每行的数据是存储在节点中的字符、节点的左子序列号、节点的父序列号、节点的右子序列号以及节点的权重值。编码结果存储在文件中解码结果存储在文件中在终端上以紧凑的格式显示编码结果，每行50个代码。同时，这种字符形式的编码文件被写入文件CodePrint.txt哈夫曼树以树的形式显示在终端上，哈夫曼树以这个字符的形式被写入文件树问：节目结束了。三。轮廓设计为了实现上述功能，需要四种抽象数据类型：链表、栈、队列和二叉树。1.链表抽象数据类型定义：2。堆栈抽象数据类型定义ADT SqStack数据对象：D=ai|aiSqStack，i=1，2.n，n0数据关系：r=| AI-1，AI d，AI-1 AI，I=2，n基本操作：/初始化堆栈bool InitStack_sq(SqStack S，int msize)；/判断堆栈是否为空bool StacKempty _ sq(SqStack S)；/查找堆栈长度整型堆栈长度(SqStack S)；/元素堆叠布尔Push_sq(SqStack S，选择类型e)；/元素超出堆栈布尔Pop_sq(SqStack S，选择类型e)； ADTSqStack3.队列抽象数据类型定义ADT链接队列数据对象：D=ai|aiLinkQueue，i=1，2.n，n0数据关系：r=| AI-1，AI d，AI-1 AI，I=2，n基本操作：/初始化队列bool InitQueue_L(链接队列Q)；/判断队列是否为空bool StackFull _ sq(SqStack S)；布尔队列空队列；/求队列长度布尔GetHead_L(链接队列问，队列类型(e)；/元素入队列bool EnQueue_L(链接队列问，队列类型(e)；/元素出队列布尔出列_L(链接队列问，队列类型(e)； ADT链接队列4.二叉树抽象数据类型定义ADT HTNode数据对象：D=ai|aiHTNode，i=1，2.n，n0数据关系：R=|ai-1，aiD，ai-1ai，i=2，n基本操作：/求每个节点层次空隙等级（赫芬顿高中，国际，国际)，国际水平)；/中序遍历打印树形赫芬顿里无效订单（赫芬顿工厂，文件*fp，int k，int a)；/选择权值最小的两个节点无效选择(赫芬顿邮报，2010年，2011年，2011年，Q2)；/初始化霍夫曼树void HuffmanTree(HuffTree HT，char *code，int *w，int n)；/霍夫曼编码无效编码（赫芬顿树，内部根，字符* *人道主义协调员，堆栈s)； ADT HTNode5.本程序保护模块：主程序模块霍夫曼单元模块：实现二叉树的抽象数据类型堆单元模块：实现链表、栈、队列抽象数据类型调用关系：主程序模块-霍夫曼单元模块-堆栈单元模块四、详细设计1.结点类型和结点指针类型：链表：typedef结构LNode收费数据；结构下一个节点*LNode，*个链接表；栈：typedef结构SElemType * elem .int stacksizeint top SqStack队列：typedef链接表队列typedef结构排队前沿；队列后部；链接队列；二叉树：typedef结构内部重量；收费数据；内部父级，lChild，rChildHTNode .typedef HTNode * HuffTree2.链表的实现本实验只用到链表节点类型的定义，用来定义Queueptr，没有用到实现链表操作的函数。3.栈的实现/元素入栈布尔Push_sq(堆栈，选择类型e)如果(StackFull_sq(S)返回错误的；返回真；其余略4.队列的实现布尔出列_L(链接队列问，队列类型e)如果（前=后)返回假；队列p=前-后；q . front-next=p-next；e=p-数据；如果（后部=前部)后部=前部；删除p；返回真；其余略5.二叉树的实现/选择权值最小的两个节点空的选择(赫芬顿树HT，int t，int q1，int q2)int i，j；对于(I=1；I=t * 2-1。如果(一中).parent=0) Q1=我；休息；对于(I=1；I=t * 2-1。如果(一中).重量第一季度.重量)Q2=j；/初始化霍夫曼树void HuffmanTree(HuffTree HT，char *code，int *w，int n)整数m=n*2-1，I，s1，S2；对于(I=1；I=m。一世.1 .大街1号.parent=0；一世.重量=i=n？西一世:0；一世.data=i=n？代码一号: #；对于(I=n1I=m。选择(S2，北部，S1)；一世.lChild=s1 .一世.rChild=s2一世.重量=1 .重量2 .重量；1 .父母2 .父母=我；/霍夫曼编码无效编码(赫芬顿树)超线程，内部根，字符* *人道主义协调员，堆栈s)char ch，e；如果(根！=0)如果(根).lChild=0)推送_sq(S， 0)；根=新字符堆栈长度_平方(S)；根；Pop_sq(S，ch)；推送_sq(南，0)；编码(根).ild、HC、S)；Pop_sq(南、东)；Push_sq(S，1)；编码(根).建筑、住宅、住宅)；Pop_sq(南、东)；/求节点深度空隙等级（赫芬顿高中，国际，