大数据结构作业(3).doc

大数据结构作业(3).doc

ID:56523689

大小:2.32 MB

页数:12页

时间:2020-06-27

大数据结构作业(3).doc_第1页
大数据结构作业(3).doc_第2页
大数据结构作业(3).doc_第3页
大数据结构作业(3).doc_第4页
大数据结构作业(3).doc_第5页
资源描述:

《大数据结构作业(3).doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、第9章检索的作业9.6假定值A到H存储在一个自组织线性表中,开始按照升序存放。对于9.2小节建议的三种自组织启发式规则,按照下面顺序访问线性表,给出结果线性表和需要的比较总数。DHHGHEGHGHECEHG(1)频率计数自组织线性表启发式规则:ABCDEFGH比较次数D:DABCEFGH4H:DHABCEFG8H:HDABCEFG2G:HDGABCEF8H:HDGABCEF1E:HDGEABCF7G:HGDEABCF3H:HGDEABCF1G:HGDEABCF2H:HGDEABCF1E:HGEDABCF4C:HGEDCABF7E:HGEDCA

2、BF3H:HGEDCABF1G:HGEDCABF2比较总数=54(2)移至前端自组织线性表启发式规则:ABCDEFGH比较次数D:DABCEFGH4H:HDABCEFG8H:HDABCEFG1G:GHDABCEF8H:HGDABCEF2E:EHGDABCF7G:GEHDABCF3H:HGEDABCF3G:GHEDABCF2H:HGEDABCF2E:EHGDABCF3C:CEHGDABF7E:ECHGDABF2H:HECGDABF3G:GHECDABF4比较总数=59(3)转置自组织线性表启发式规则:ABCDEFGH比较次数D:ABDCEFGH

3、4H:ABDCEFHG8H:ABDCEHFG7G:ABDCEHGF8H:ABDCHEGF6E:ABDCEHGF6G:ABDCEGHF7H:ABDCEHGF7G:ABDCEGHF7H:ABDCEHGF7E:ABDECHGF5C:ABDCEHGF5E:ABDECHGF5H:ABDEHCGF6G:ABDEHGCF7比较总数=959.8编写一个算法,实现频率计数自组织线性表启发式规则,假定线性表使用数组实现。特别是编写一个函数FreqCount,它把要检索的值作为输入,并且相应地调整线性表。如果值不在线性表中,就把它添加到线性表的最后,其频率计数是1

4、。算法思想:按顺序访问记录,每访问一条记录,该记录的访问数加1,如果该记录的访问数已经大于它前面记录的访问数,这条记录就在线性表中与前面的记录交换。伪代码:templatevoidFreqCount(ElemA[],intcount[]){intn=0;while((intval=GETNEXT())!=DONE){for(i=0;i0)&&(cou

5、nt[i]>count[i-1])){swap(A[i],A[i-1]);swap(count[i],count[i-1]);}}}}9.9编写一个算法,实现移至前端自组织线性表启发式规则,假定线性表使用数组实现。特别是编写一个函数MoveToFront,它把要检索的值作为输入,并且相应地调整线性表。如果值不在线性表中,就把它添加到线性表的开始位置。算法思想:按顺序访问记录,每找到一个记录就把它放到线性表的最前面,而把其他记录后退一个位置。伪代码:templatevoidMoveToFront(ElemA[]){intn

6、=0;while((intval=GETNEXT())!=DONE){for(i=0;i0)swap(A[i],A[0]);}}9.10编写一个算法,实现转置自组织线性表启发式规则,假定线性表使用数组实现。特别是编写一个函数transpose,它把要检索的值作为输入,并且相应地调整线性表。如果值不在线性表中,就把它添加到线性表的最后。算法思想:按顺序访问记录,把找到的记录与它在线性表中的前一条记录交换位置。伪代码:template

7、Elem>voidtanspose(ElemA[]){intn=0;while((intval=GETNEXT())!=DONE){for(i=0;i

8、=5h(18)=401411822339430512669.16使用闭散列,利用双散列方法解决冲突,把下面的关键码插入到一个有13个槽的散列表中(槽从0到12编号)

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。