精华内容
下载资源
问答
  • 2021-05-23 09:19:27

    /**

    *    实验题目:

    *        求折半查找成功时的平均查找长度

    *    实验目的:

    *        深入掌握折半查找过程和折半查找算法分析

    *    实验内容:

    *        设计程序,建立有序序列R[0...n-1]进行二分查找产生的判断树,

    *    在此基础上完成如下功能:

    *    1、输出n=11时的判定树并求成功情况下的平均查找长度ASL。

    *    2、通过构造判定树可以求得成功情况下的平均查找长度ASL1;当将

    *    含有n个结点的判定树看成是一颗满二叉树时,其成功情况下的平均

    *    查找长度的理论值ASL2约为log2(n+1)-1。对于n=10、100、1000、

    *    10000、100000和1000000,求出其ASL1和ASL2和两者的差值。

    */

    #include #include #include

    typedef struct node

    {

    long index;                             //  当前结点对应的记录下标

    int level;                              //  当前结点的层次->树的高度

    struct node *lchild;                    //  左孩子指针

    struct node *rchild;                    //  右孩子指针

    }dec_node;                                  //  判定树结点类型

    /**

    *   功能:

    *       由create_dec_tree调用以建立判定树。由R[low...high]创建根结点

    *   的判定树,height为树的高度,初始时,由R[0...n-1]创建判定树,height

    *   的初始值为1。

    *

    */

    static void create_dec_tree1(dec_node *&b, long low, long high, int height)     //  指针的引用

    {

    int mid;

    if(low <= high)

    {

    mid = (low + high) / 2;

    b = (dec_node *)malloc(sizeof(dec_node));                               //  动态分配存储空间

    b->index = mid;

    b->level = height;                                                      //  树的高度

    create_dec_tree1(b->lchild, low, mid - 1, height + 1);

    create_dec_tree1(b->rchild, mid + 1, high, height + 1);

    }

    else

    b = NULL;

    }

    /*------------------建立判定树b------------------*/

    static void create_dec_tree(dec_node *&b, long n)

    {

    create_dec_tree1(b, 0, n - 1, 1);

    }

    /*-----------------销毁判定树b------------------*/

    static void destroy_dec_tree(dec_node *&b)

    {

    if(b != NULL)

    {

    destroy_dec_tree(b->lchild);

    destroy_dec_tree(b->rchild);

    free(b);

    }

    }

    /*----------------以括号表示法输出判定树b------------------*/

    static void disp_dec_tree(dec_node *b)

    {

    if(b != NULL)

    {

    printf("%d[%d]", b->index, b->level);

    if(b->lchild != NULL || b->rchild != NULL)

    {

    printf("(");                    //  有孩子结点时才输出(

    disp_dec_tree(b->lchild);       //  递归处理左子树

    if(b->rchild != NULL)

    printf(",");                //  有右孩子结点时才输出,

    disp_dec_tree(b->rchild);       //  递归处理右子树

    printf(")");                    //  有孩子结点时才输出)

    }

    }

    }

    /*----------------求判定树b中比较的总次数------------------*/

    static int sum(dec_node *b)

    {

    if(b != NULL)

    {

    if(b->lchild == NULL && b->rchild == NULL)

    return b->level;

    else

    return sum(b->lchild) + sum(b->rchild) + b->level;

    }

    else

    return 0;

    }

    /*----------------求成功情况下的平均查找长度------------------*/

    static double asl_succ(dec_node *b, long n)

    {

    return 1.0 * sum(b) / n;

    }

    int main(int argc, char *argv[])

    {

    dec_node *b;

    long n = 11;

    double d, asl1, asl2;

    create_dec_tree(b, n);                  //  建立判定树b

    printf("R[0...%d]判定树:\n\t", n - 1);

    disp_dec_tree(b);

    printf("\n\tASL = %g\n", asl_succ(b, n));

    destroy_dec_tree(b);

    printf("成功平均查找长度分析:\n");

    printf("\tn\t\tASL1\t\tASL2\t\t差值\n");

    for(n = 10; n <= 1000000; n *= 10)

    {

    create_dec_tree(b, n);

    asl1 = asl_succ(b, n);

    asl2 = log(n + 1) - 1;

    d = asl1 - asl2;

    printf("%10d\t\t%g\t\t%g\t\t%g\n", n, asl1, asl2, d);

    destroy_dec_tree(b);

    }

    return 0;

    }

    运算结果:

    R[0...10]判定树:

    5[1](2[2](0[3](,1[4]),3[3](,4[4])),8[2](6[3](,7[4]),9[3](,10[4])))

    ASL = 3

    成功平均查找长度分析:

    n               ASL1            ASL2            差值

    10              2.9             1.3979          1.5021

    100              5.8             3.61512         2.18488

    1000              8.987           5.90875         3.07825

    10000              12.3631         8.21044         4.15266

    100000              15.6895         10.5129         5.17652

    1000000              18.9514         12.8155         6.13593

    更多相关内容
  • 折半查找平均查找长度

    千次阅读 2019-12-23 18:15:08
    建完全二叉树 例如长度为12的有序线性表,构建完全二叉树,如下图: 平均查找长度为:3.1

    建完全二叉树

    例如长度为12的有序线性表,构建完全二叉树,如下图:
    在这里插入图片描述
    平均查找长度为:3.1

    展开全文
  • 顺序查找 折半查找平均查找长度分析 ASL:平均查找长度 其中n为查找表中元素个数,Pi为查找第i个元素的概率,通常假设每个元素查找概率相同,Pi=1/n,Ci是找到第i个元素的比较次数。 ASL=∑i=1npici ASL=\sum_{i=1...

    顺序查找 折半查找的平均查找长度分析

    ASL:平均查找长度

    其中n为查找表中元素个数,Pi为查找第i个元素的概率,通常假设每个元素查找概率相同,Pi=1/n,Ci是找到第i个元素的比较次数。
    A S L = ∑ i = 1 n p i c i ASL=\sum_{i=1}^{n} p_ic_i ASL=i=1npici

    一般顺序查找的平均查找长度:

    • 因为顺序查找就是顺序存储 一个一个比较,所以如果查找成功的话说明就和之前不相等的元素已经比较过了。
    • 所以第 n 个元素就是比较了 n 次
    • 每个元素都比较了其所在位序的次数
    • 每个元素被查找的概率都是1/n 所以

    A S L 成 功 = 1 n ( 1 + 2 + 3 + … + n ) = n + 1 2 ASL_{成功}=\frac{1}{n}(1+2+3+…+n)=\frac{n+1}{2} ASL=n1(1+2+3++n)=2n+1

    $ASL_{成功}=n+1 $

    有序顺序表的平均查找长度:

    • 查找成功的 ASL 不影响

    • 如果查找不成功的话,因为顺序表有序,所以可以提前结束,从而缩短查找失败的比较次数,需要画个简单【判定树】

    • 举个例子,在[10 20 30 40 50 60]中查找

    image-20210924175755222
    • 失败的一共有 n+1个结点,所以每个结点的概率就是 1 n + 1 \frac{1}{n+1} n+11
    • 比较次数是 每个失败结点上一层的层数

    A S L 失 败 = 1 n + 1 [ 1 + 2 + 3 + … + n + n ] = n 2 + n n + 1 ASL_{失败} = \frac{1}{n+1}[1+2+3+…+n+n]=\frac{n}{2}+\frac{n}{n+1} ASL=n+11[1+2+3++n+n]=2n+n+1n

    折半查找的平均查找长度:

    • 要涉及到判定树:n 个元素就有n 个【内部结点】 n+1个【外部结点】

    • 【判定树】一定是【满二叉树】

    • 根据折半算法画出初级判定树(只有内部结点),其他空位用【查找失败的方框代替】

    • 算 ASL 直接就是算 [每层结点的个数*层数]➗结点个数

    image-20210924180742717

    • 不成功要具体例子具体计算。
    展开全文
  • 如何计算折半查找平均查找长度?

    万次阅读 多人点赞 2019-04-12 20:52:32
    首先,折半查找可以借助于一个二叉树来描述。 为了简化讨论,则把这棵树近似看成满二叉树,设二叉树的高度为h(h>1) 则,根据二叉树的性质,它有最大节点数...那么平均查找长度为 1/n*(1*2^0+2*2^1+3*2^2+……+j...

    首先,折半查找可以借助于一个二叉树来描述。
    为了简化讨论,则把这棵树近似看成满二叉树,设二叉树的高度为h(h>1)
    则,根据二叉树的性质,它有最大节点数n=2^{h}-1
    h=\log_2(n+1) (2是底数)。那么二叉树的第j层节点数为:2^(j-1),当最后一层也就是j=h
    假定每个元素的查找概率相等,则,pi=1/n (pi为第i个节点的查找概率)
    那么平均查找长度为 1/n*(1*2^0+2*2^1+3*2^2+……+j*2^(j-1))
    则经过化简计算,得平均查找长度为:((n+1)/n ) *log2(n+1)-1 (其中对数中的2为底数:即log以2为底(n+1)的对数)
    注 : 当n很大时 ,可近似为 log2(n+1)-1
    其中 1*2^0+2*2^1+3*2^2+……+j*2^(j-1)的求法如下:
    设 S = 1*2^0 + 2*2^1+3*2^2 +……+ j*2^(j-1) ,
    则 2S = 1*2^1+2*2^2 +……+ (j-1)*2^(j-1) + j*2^j
    则 2S - S = -( 2^0 + 2^1 + 2 ^2 + …… + 2 ^(j-1)) + j *2^j
    即 S = - (2^j-1)+j*2^j           (注这里的相当于h)
    带入化简即可。

    然后将j用n表示

    展开全文
  • 【哈尔滨工业大学2005 四、1(8分)】画出对长度为18的有序的顺序表进行折半查找时的判定树,并指出在等概率时查找成功的平均查找长度,以及查找失败时所需的最多的关键字比较次数。 判定树如下: 图1-1判定树 ...
  • 折半查找判定数及平均查找长度

    万次阅读 多人点赞 2016-07-06 13:28:31
    折半查找判定数及平均查找长度 折半查找的过程看,可用二叉树来描述,二叉树中的每个结点对应有序表中的一个记录,结点中的值为该记录在表中的位置。通常称这个描述折半查找二叉树的过程称为折半查找判定树。 ...
  • 来源:<<数据结构>> 邓俊辉 上述C(k)的递推公式看了好久都没看懂(深刻受到清华的降维打击,差点放弃学习)。 ...期间主要参考了如下帖子: ...对于C(k)来说,我的理解、或者大家有误的理解是:C(k)=C(k-1)+...
  • 折半查找判定数及平均查找长度 折半查找的过程看,可用二叉树来描述,二叉树中的每个结点对应有序表中的一个记录,结点中的值为该记录在表中的位置。通常称这个描述折半查找二叉树的过程称为折半查找判定树。 ...
  • 折半查找平均长度公式推导

    千次阅读 2020-12-01 17:29:35
  • 将12个数画成完全二叉树,第一层有1个、第二次2个、第三层4个,第四层只有5个。 二分查找时: 第一层需要比较1次 ...则平均查找长度即为:(1+2*2+3*4+4*5)/12 = 37/12 = 3.0833 即为 A、3.1 ...
  • 折半查找平均查找次数分析

    万次阅读 多人点赞 2016-10-24 16:41:40
    这里查找成功的平均次数和失败的平均次数分析方法与有序顺序表相同:看结点身处的深度,根结点深度是1。红色线条是查找失败路径,深度计数是边连接的圆形结点。看图中查找成功的平均次数计算。总的查找次数是
  • 查找,就是根据给定的某个值在一组记录集合中确定某个“特定的”数据元素(记录)或者找到属性值符合特定条件的某些记录。 查找表是由同一类型的数据元素(或记录)构成的集合。 关键字:是数据元素(或记录)中某个...
  • 一、前言 上一篇博客讲了有关于查找的概念及顺序查找算法,这次我们再讲解一种新...上次我们说适合静态查找的有顺序查找和折半查找等,今天就给大家讲述一下折半查找。 细心的小伙伴们发现了,我在讲顺序查找的博...
  • 折半查找的过程看,以有序表的中间记录作为比较对象,并以中间记录将表分割为两个子表,对子表...长度为n的折半查找判定树的构造方法为: ⑴ 当n=0时,折半查找判定树为空; ⑵ 当n>0时,折半查找判定树的根...
  • 顺序查找、折半查找基础概念顺序查找一般线性表的顺序查找平均查找次数优缺点:有序表的顺序查找思路失败结点平均查找长度折半查找平均查找长度时间复杂度分块查找(索引顺序查找)思路步骤平均查找长度 基础概念 在...
  • 折半查找的概念及实现代码

    千次阅读 2021-11-23 17:09:25
    文章目录折半查找的概念折半查找的算法实现折半查找平均查找长度 折半查找的概念 折半查找又称二分查找,它仅适用有序的顺序表,即线性表必须按关键字有序、且必须采用顺序存储。 折半查找的算法思路: 将n个...
  • 包括常见的排序算法,以及折半查找,首先对要查找的数据排好序,然后用递归调用的方式实现折半查找(包括了两种实现方式)。指定一个排好序的数组和要查找的值,同时指定要查找的左边界和有边界。左右边界要位于数组...
  • 折半查找判定树及平均查找长度

    万次阅读 2016-12-17 12:49:13
    折半查找的过程看,以有序表的中间记录作为比较对象,并以中间记录将表分割为两个子表,...长度为n的折半查找判定树的构造方法为:⑴ 当n=0时,折半查找判定树为空;⑵ 当n>0时,折半查找判定树的根结点是有序表中
  • 使用范围: 数量少+有序 时间复杂度:O(logn)对数阶
  • 1.顺序查找 2.折半查找 3.分块查找 4.王道课后题
  • 文章目录查找查找的概念顺序查找顺序查找-算法原理顺序查找-算法实现顺序查找-性能分析折半查找折半查找-算法原理折半查找-算法实现折半查找-性能分析分块查找分块查找-算法原理分块查找-算法实现分块查找-性能分析 ...
  • 详解折半查找

    千次阅读 2022-02-01 20:38:06
    1.顺序查找 顺序查找是从线性表的一端,依次对比 每个元素,直到找到要查找的元素,或者没有找到。 代码实现: int SqSearch(int arr[],int length,int x) { ...折半查找又称二分查找,它仅适用于有序的顺序表。
  • 折半查找

    千次阅读 2019-08-08 11:15:22
    **重点:**要使用折半查找,首先数组必须是要已经排好序的。 步骤: 1.取数组中间值,比较中间值与要查找的数的大小 2.若中间值大于查找值,high-1;若中间值小于查找值,low+1 3.重复1,2步,直至中间值小于或等于...
  • 【数据结构】顺序查找和折半查找

    千次阅读 多人点赞 2021-04-03 08:07:36
    数据结构之查找算法 摘要:在本篇文章中,主要讲述了在数据结构中所涉及的几大查找算法,包括:顺序查找、折半查找、分块查找和散列表查找。...在查找算法中,最为重要的便是算法的平均查找长度, ...
  • 为什么分块查找中索引表折半查找平均查找长度不减1
  • 具有12个关键字的有序表,折半查找平均查找长度为( )。【山大学1998二、10(2分)】 【烟台大学2007一、17 (2分)】A.3.1 B.4 C.2.5 D.5 做这个题之前,建议你先看一下《折半查找判定树 二叉排序树 查找成功平均...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 19,223
精华内容 7,689
关键字:

折半查找平均查找长度