- 1、本文档共25页,可阅读全部内容。
- 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
计算机算法设计与分析实验的报告
华北电力大学
实 验 报 告
|
|
实验名称 算法设计实验
课程名称 算法设计与分析
|
|
专业班级:信安1301 学生姓名:
学 号: 成 绩:
指导教师:胡朝举 实验日期: 2015年11月
实验一、归并排序(Merging Sort)
?实验内容
归并排序是一个非常优秀的排序方法,也是典型的分治策略的典型应用。实验要求:
(1)编写一个模板函数:
template typename T
MergeSort(T *a, int n);
以及相应的一系列函数,采用分治策略,对任意具有:
bool operator(const Tx,const Ty);
比较运算符的类型进行排序。
与STL库中的函数std::sort(..)进行运行时间上的比较,给出比较结果,如:动态生成100万个随机生成的附点数序列的排序列问题, 给出所用的时间比较。
归并排序就是将两个或两个以上的有序表合并成一个有序表的过程。将两个有序表合并成一个有序表的过程称为2-路归并。
假设初始序列含有n个记录,则可看成n个有序的子序列,每个字序列的长度为1,然后两两归并,得到[n/2]个长度为2或1的有序子序列;再两两归并,...,如此重复,直到一个长度为n的有序序列为止。
例 已知待排序记录的关键字序列为{49,38,65,97,76,13,27},给出2-路归并排序法进行排序的过程
2-路归并排序中的核心操作是,将待排序序列中前后相邻的两个有序序列归并为一个有序序列。相邻两个有序子序列的归并
设两个有序表存放在同一数组中相邻的位置上:R[low..mid]和R[mid+1..high],每次分被从两个表中取出一个记录进行关键字的比较,将较小者放入T[low..high]中,重复此过程,直至其中一个表为空,最后将另一非空表中余下的部分直接复制到T中。
1)时间复杂度当有n个记录时,需进行[log2n]趟归并排序,每一趟归并,其关键字比较次数不超过n,元素移动次数都是n,因此,归并排序的时间复杂度为O(nlog2n)。2)空间复杂度用顺序表实现归并排序时,需要和待排序记录个数相等的辅助存储空间,所以空间复杂度为O(n);—Huffman树及Huffman编码
实验内容
一个记录字符及出现频率的文件如下所示:
huffman.haf
7
a,45
b,13
c,12
d,16
e,9
f,5
试编写一个读取此种格式文件类CHuffman, 内部机制采用优先队列,用于建立Huffman树及进行Huffman编码输出,其用法可以如下所示:
CHuffman hm(huffman.dat);
hm.CreateTree();
hm.OutputTree();
hm.OutputCode(); //二进制形式的字符串
对于输出树的形式可自行决定(如图形界面或字符界面)。
二、?主要思想
该程序已封装为类在HuffmanCode.cpp中,该代码读取E:\h.dat路径下的数据文件,可以更改为用户输入的指定路径,但鉴于算法核心功能已经实现,不再加强此功能。另一点,此程序在建立完哈夫曼树后,不是使用遍历二叉树求解的方法而是使用直接从叶子节点出发,直接沿路径返回至根节点进行哈夫曼编码确定,不足之处是,结构体中多加了存储字段,消耗了更多内存。此外,向量已经给出了类似栈的操作,直接利用这一点,模仿优先队列进行操作,具体说明及实现在注释中已给出。
这个霍夫曼编码本身用到了贪心的思想,所以也在这里列举了出来。这个问题本身在计算机系的很多教材上都出现过。这里权且记录下来。霍夫曼的编码是这样的。假设我有一组带压缩的文本,里面各个字符出现的频率不同,现在需要对他们进行压缩。比如
假设我们有100,000个字符的文本.最直观的压缩办法就是原来每个字符要8个bits。现在我一共只有6个字符,那我就把每个字符用3个二进制 位来表示,这样所有100,000个字符用300,000个bit就可以表示了。这种是最直观的方案。但是霍夫曼提出的方案更精妙一些。他提出,基于每个 字符出现的频率不同,可以让出现次数多的字符用更少的二进制位来描述,出现次数少的字符用多一些二进制来描述。比如上图显示的这个Variable-length codeword里面。a出现的频率最高,所以用一个二进制位0来表示。而f出现的频率很小,所以用4个
您可能关注的文档
- 管理信息系统实验的报告.docx
- 篮球馆工程岩土工程详细勘察的报告.doc
- 箱包皮具加工新增生产设备建设项目环境影响的报告表.doc
- 类MIPS单周期微处理器设计实验的报告.docx
- 粮食现代物流项目资金申请的报告.doc
- 管理运筹学实验的报告.doc
- 粘土矿地质灾害危险性评估的报告.doc
- 精制牛血清白蛋白项目项目可行性研究的报告.doc
- 精密制粉有限公司高炉水渣处理与加工项目申请的报告.doc
- 粮油购销储运公司社会实践的报告(论文).doc
- 新的一年工作展望.docx
- 医生年终个人工作的述职报告(3篇).docx
- 2023年消防设施操作员之消防设备中级技能考前冲刺练习题附答案详解.docx
- 2022-2023年环境影响评价工程师之环评技术导则与标准通关练习题包括详细解答.docx
- 2023年中级注册安全工程师之安全生产管理考前冲刺检测卷和答案.docx
- 2023年中级银行从业资格之中级银行管理考前冲刺测试卷提供答案解析.docx
- 2023年公共营养师之二级营养师通关模拟考试试卷附带答案.docx
- 证券分析师之发布证券研究报告业务考前冲刺模拟题库.docx
- 2022-2023年二级建造师之二建建设工程法规及相关知识综合提升测试卷附答案.docx
- 2023年二级建造师之二建机电工程实务通关模拟考试试卷提供答案解析.docx
文档评论(0)