数据结构作业(3)知识讲解

据结构作业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