双向循环列表和霍夫曼编码.doc

山东建筑大学计算机科学与技术学院课程设计说明书题  目: 双向循环链表、霍夫曼编码课  程:  数据结构、算法与应用院(部):  计算机科学与技术学院专  业:   计算机科学与技术班  级:      计科111学生姓名:      刘鑫学  号:     2011111028指导教师:      李盛恩完成日期:    2013年7月2日目录课程设计任务书  I双向循环链表、霍夫曼编码及相关操作的实现  1一、问题描述  1二、数据结构  1三、逻辑设计  2四、编码  3五、测试数据  12六、测试情况  13结论  16参考文献  17课程设计指导教师评语  18山东建筑大学计算机科学与技术学院课程设计任务书设计题目双向循环链表、霍夫曼编码及相关操作的实现已知技术参数和设计要求霍夫曼编码(HuffmanCoding)是一种编码方式,哈夫曼编码是可变字长编码(VLC),该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,根据输入的字符和相应的频率,实现如下功能:1、根据输入的权重构造霍夫曼树2、根据构造的霍夫曼树对字符进行编码3、根据输入的编码能进行译码双向循环链表是表中最后一个结点的指针域指向头结点,其作用是方便定义一个节点的前驱节点和后继节点。本次课题要求实现双向循环列表,实现如下功能:1、插入节点2、根据输入节点查找节点地址3、根据输入的节点地址查找节点4、删除节点设计内容与步骤1、设计存储结构2、设计算法3、编写程序,进行调试4、总结并进行演示、:40-17:05地点::40-17:05地点::40-17:05地点::40-12:05地点:实验室看程序资料准备下午答辩设计考核要求1、考勤20%2、课程设计说明书50%3、成果展示30%   指导教师(签字):      教研室主任(签字)霍夫曼编码、双向链表及相关操作的实现一、,实现对输入字符串和频率构造一棵霍夫曼树并对其编码。,实现chain类的所有功能,实现对链表的插入、查询字节、查询字节地点和删除节点的功能。2、,最小两个权值先连接成为左右孩,编码时向左编码0, Huffman树 、:voidselect(huffTreearray[],intn,int&a,int&b)//用来选择array中权重最小的两棵树huffTreehuff[max];//假设节点数不超过max的huffman树stringstr[max];//用来保存节点对应的字符intarray[max];//用来保存节点的权重开始其流程图如下:进行相应的操作程序结束退出对编码串进行译码对字符串进行编码构造霍夫曼树进行相应的操作(主要是输出):Chain<T>::Chain()//构造chain类intChain<T>::Length()const//求链表长度Chain<T>::~Chain()//chain类析构boolChain<T>::Find(intk,T&x)const//查找节点地址intChain<T>::Search(constT&x)const//搜索节点Chain<T>&Chain<T>::Delete(intk,T&x)//删除节点Chain<T>&Chain<T>::Insert(intk,constT&x)//插入节点voidChain<T>::Output(ostream&out)const//输出链开始根据输入的节点调用insert插入到链表中程序退出调用Serch实现搜索调用Find实现查询构造双向循环链表输出所要的信息和链表结束四、编码霍夫曼编码:#include<iostream>#include<string>usingnamespacestd;constintmax=100;classhuffTree{public:intparent,lchild,rchild,weight;stringflag;};//用来选择array中权重最小的两棵树voidselect(huffTreearray[],intn,in