据结构作业3)
数(
精品资料
第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 4 H: D H A B C E F G 8 H: H D A B C E F G 2 G: H D G A B C E F 8 H: H D G A B C E F 1 E：H D G E A B C F 7 G: H G D E A B C F 3 H: H G D E A B C F 1 G: H G D E A B C F 2 H: H G D E A B C F 1 E: H G E D A B C F 4 C: H G E D C A B F 7 E: H G E D C A B F 3 H: H G E D C A B F 1 G: 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 4 H: H D A B C E F G 8 H: H D A B C E F G 1 G: G H D A B C E F 8 H: H G D A B C E F 2 E：E H G D A B C F 7
仅供学习与交流，如有侵权请联系网站删除 谢谢2
精品资料
G: G E H D A B C F 3 H: H G E D A B C F 3 G: G H E D A B C F 2 H: H G E D A B C F 2 E: E H G D A B C F 3 C: C E H G D A B F 7 E: E C H G D A B F 2 H: H E C G D A B F 3 G: 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 4 H: A B D C E F H G 8 H: A B D C E H F G 7 G: A B D C E H G F 8 H: A B D C H E G F 6 E：A B D C E H G F 6 G: A B D C E G H F 7 H: A B D C E H G F 7 G: A B D C E G H F 7 H: A B D C E H G F 7 E: A B D E C H G F 5 C: A B D C E H G F 5 E: A B D E C H G F 5 H: A B D E H C G F 6 G: A B D E H G C F 7 比较总数=95
9.8 编写一个算法，实现频率计数自组织线性表启发式规则，假定线性表使用数组实现。特别是编写一个函数FreqCount，它把要检索的值作为输入，并且相应地调整线性表。如果值不在线性表中，就把它添加到线性表的最后，其频率计数是1。
仅供学习与交流，如有侵权请联系网站删除 谢谢3
精品资料
算法思想：
按顺序访问记录，每访问一条记录，该记录的访问数加1，如果该记录的访问数已经大于它前面记录的访问数，这条记录就在线性表中与前面的记录交换。
伪代码：
template
void FreqCount(Elem A[], int count[]) {
int n = 0;
while ((int val = GETNEXT()) != DONE) {
for (i=0; i if (A[i] == val) break; else if (i == n) { A[n] = val; count[n++] = 1; } else { count[i]++; while ((i > 0) && (count[i] > count[i-1])) { swap(A[i], A[i-1]); swap(count[i], count[i-1]); } } } } 9.9 编写一个算法，实现移至前端自组织线性表启发式规则，假定线性表使用数组实现。特别是编写一个函数MoveToFront，它把要检索的值作为输入，并且相应地调整线性表。如果值不在线性表中，就把它添加到线性表的开始位置。 仅供学习与交流，如有侵权请联系网站删除 谢谢4
数据结构作业(3)知识讲解
