数据结构作业(3)

1、第九章检索作业9.6假设值A到H存储在自组织线性表中，开始以升序存储。对于第9.2节中建议的三个自组织启发式规则，请按以下顺序访问线性表，并给出结果线性表和所需的比较总数。d H H G H G G H G H E C 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 :D A B C E F2G: H D G A B C E F 8H :D G A B C E f1英：英国航空公司，英国航空公司，F 7G: H G D E A B C F 3H :G D E A B C f1

2、G: H G D E A B C F 2H :G D E A B C f1E: 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 :G E D C A B f1G: 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 :D A B C E F G8H :D A B C E F G1G: G H D A B C E F 8H :G D A B C E F2英：英国航空航天局，英国航空公司，F 7G: G E H D

3、 A B C F 3H :G E D A B C F 3G: G H E D A B C F 2H :G E D A B C F2E: 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 C E H F G 7G: A B D C E H G F 8H: A B D C

4、H E G F 6英：英国航空公司，英国航空公司，英国航空公司，英国航空公司，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 C H G F5C: A B D C E H G F 5E : A B D C H G F5H: A B D E H C G F 6G: A B D E H G C F 7比较总数=959.8假设线性表由数组实现，编写一个算法实现频率计数自组织线性表的启发式规则。特别是，写一个函数FreqCount，它把要检索的值作为输入，并相应地调

5、整线性表。如果该值不在线性表中，将其添加到线性表的末尾，其频率计数为1。算法思想：按顺序访问记录。对于每个被访问的记录，该记录的访问次数增加1。如果该记录的访问号大于前一记录的访问号，则该记录与线性表中的前一记录交换。伪代码：模板无效频率计数(Elem A，整数计数)int n=0；同时(int val=GETNEXT()！=完成)对于(I=0；i 0)(计数i计数i-1)交换(Ai，AI-1)；交换(计数i，计数I-1)；9.9编写一个算法来实现移动到前端自组织线性表的启发式规则，假设线性表由数组实现。特别是，编写一个函数MoveToFront，它接受要检索的值作为输入，并相应地调整线性表。

6、如果该值不在线性表格中，请将其添加到线性表格的开头。算法思想：按顺序访问记录。当你找到一个记录，把它放在线性表格的前面，把其他记录放回一个位置。伪代码：模板虚空移动到前方(Elem A)int n=0；同时(int val=GETNEXT()！=完成)对于(I=0；i 0)交换(Ai，A0)；9.10假设线性表由数组实现，编写一个算法来实现转置自组织线性表的启发式规则。特别是，写一个转置函数，它把要检索的值作为输入，并相应地调整线性表。如果该值不在线性表格中，请将其添加到线性表格的末尾。算法思想：按顺序访问记录，并将找到的记录的位置与线性表中的前一个记录交换。伪代码：模板虚空传送(Elem A

7、)int n=0；同时(int val=GETNEXT()！=完成)对于(I=0；i 2(10) - 4(20) - 6(2) - 2 - 1(10) - 3(3) - 4(5) - 3 - 2(3) - 5(15) - 4 - 1(20) - 2(5) - 5(11) - 6(10) - 5 - 3(15) - 4(11) - 6(3) - 6 - 1(2) - 4(10) - 5(3) - 11.4对于图11.26所示的图，给出了从顶点1开始的DFS树。42163511.5对于图11.26所示的图表，给出从顶点1开始的BFS树42163511.8对于图11.26中的图，给出了使用Dijks

8、tra最短路径算法从顶点4生成的最短路径表。如图11.18所示，在处理每个顶点时给出相应的d值。123456最初的333033治疗4205301110治疗2155801110治疗3155801110治疗5155801110治疗6155801110治疗1155801110从顶点4到顶点1的最短路径是15；从顶点4到顶点2的最短路径是5；从顶点4到顶点3的最短路径是8；从顶点4到顶点4的最短路径是0；从顶点4到顶点5的最短路径是11；从顶点4到顶点6的最短路径是10。11.12编写一个算法来确定具有|V|个顶点的有向图是否包含循环。算法的时间开销应为 (| v | | e |)。算法思想：采用广度

9、优先拓扑排序方法，首先访问所有边，计算指向每个顶点的边数，将所有无条件顶点放入队列，然后处理队列。当从队列中删除一个顶点时，将打印该顶点，并且所有相邻顶点的前提条件计数减少1。当相邻顶点的计数为0时，它被放入队列。如果仍有未打印的顶点，并且队列为空，则图形包含循环。伪代码：空顶部(图形*G，队列)整数G-n()；int v，w；对于(v=0；VN()；v)计数v=0；对于(v=0；VN()；(v)对于(w=G-第一(v)；wn；w=G-下一个(v，w)计数w；对于(v=0；VN()；(v)如果(计数v=0；)q-入队(v)；同时(Q长度()！=0)q-出列(v)；打印输出(v)；对于(w=G-第一(v)；wn()；w=G-下一个(v，w)计数w-；如果(计数