数据结构作业任务.doc
《数据结构作业任务.doc》由会员分享,可在线阅读,更多相关《数据结构作业任务.doc(14页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、,第9章 检索的作业9.6 假定值A到H存储在一个自组织线性表中,开始按照升序存放。对于9.2小节建议的三种自组织启发式规则,按照下面顺序访问线性表,给出结果线性表和需要的比较总数。 D H H G H E G H G H E C E H G(1) 频率计数自组织线性表启发式规则: A B C D E F G H 比较次数D: D A B C E F G H 4H: D H A B C E F G 8H: H D A B C E F G 2G: H D G A B C E F 8H: H D G A B C E F 1E:H D G E A B C F 7G: H G D E A B C F
2、3H: H G D E A B C F 1G: H G D E A B C F 2H: H G D E A B C F 1E: H G E D A B C F 4C: H G E D C A B F 7E: H G E D C A B F 3H: H G E D C A B F 1G: H G E D C A B F 2比较总数=54(2)移至前端自组织线性表启发式规则: A B C D E F G H 比较次数D: D A B C E F G H 4H: H D A B C E F G 8H: H D A B C E F G 1G: G H D A B C E F 8H: H G D A B
3、 C E F 2E:E H G D A B C F 7G: G E H D A B C F 3H: H G E D A B C F 3G: G H E D A B C F 2H: H G E D A B C F 2E: E H G D A B C F 3C: C E H G D A B F 7E: E C H G D A B F 2H: H E C G D A B F 3G: G H E C D A B F 4比较总数=59(3)转置自组织线性表启发式规则: A B C D E F G H 比较次数D: A B D C E F G H 4H: A B D C E F H G 8H: A B D
4、 C E H F G 7G: A B D C E H G F 8H: A B D C H E G F 6E:A B D C E H G F 6G: A B D C E G H F 7H: A B D C E H G F 7G: A B D C E G H F 7H: A B D C E H G F 7E: A B D E C H G F 5C: A B D C E H G F 5E: A B D E C H G F 5H: A B D E H C G F 6G: A B D E H G C F 7比较总数=959.8 编写一个算法,实现频率计数自组织线性表启发式规则,假定线性表使用数组实现。特
5、别是编写一个函数FreqCount,它把要检索的值作为输入,并且相应地调整线性表。如果值不在线性表中,就把它添加到线性表的最后,其频率计数是1。算法思想: 按顺序访问记录,每访问一条记录,该记录的访问数加1,如果该记录的访问数已经大于它前面记录的访问数,这条记录就在线性表中与前面的记录交换。 伪代码: template void FreqCount(Elem A, int count) int n = 0; while (int val = GETNEXT() != DONE) for (i=0; i 0) & (counti counti-1) swap(Ai, Ai-1); swap(co
6、unti, counti-1); 9.9 编写一个算法,实现移至前端自组织线性表启发式规则,假定线性表使用数组实现。特别是编写一个函数MoveToFront,它把要检索的值作为输入,并且相应地调整线性表。如果值不在线性表中,就把它添加到线性表的开始位置。算法思想: 按顺序访问记录,每找到一个记录就把它放到线性表的最前面,而把其他记录后退一个位置。伪代码:template void MoveToFront(Elem A) int n = 0; while (int val = GETNEXT() != DONE) for (i=0; i 0) swap(Ai, A0); 9.10 编写一个算法,
7、实现转置自组织线性表启发式规则,假定线性表使用数组实现。特别是编写一个函数transpose,它把要检索的值作为输入,并且相应地调整线性表。如果值不在线性表中,就把它添加到线性表的最后。算法思想:按顺序访问记录,把找到的记录与它在线性表中的前一条记录交换位置。伪代码:template void tanspose(Elem A) int n = 0; while (int val = GETNEXT() != DONE) for (i=0; i 2(10) - 4(20) - 6(2) - 2 - 1(10) - 3(3) - 4(5) - 3 - 2(3) - 5(15) - 4 - 1(20
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 作业 任务
限制150内