精华内容
下载资源
问答
  • 本文主要介绍了顺序文件的基本概念及其查找操作,主要包括连续顺序文件的顺序查找和二分查找,以及链接顺序文件查找

    基本概念

    在物理结构中记录排列的先后次序与在逻辑结构中记录排列的先后次序一致的文件称为顺序文件

    记录的排列按关键字值有序的顺序文件称为排序顺序文件,否则,称为一般顺序文件;(该划分是在逻辑上的划分)

    在存储介质上采用连续组织方式的顺序文件称为连续顺序文件;采用链接组织方式的顺序文件称为链接顺序文件;(该划分是在物理上的划分)

    若排序顺序文件在存储介质上采用连续组织方式,称之为排序连续顺序文件

    连续顺序文件的查找

    顺序查找法

    基本思想:

    从文件的第一个记录开始,将用户给出的关键字值与当前被查找记录的关键字值进行比较,若匹配,则查找成功,给出被查到的记录在文件中的位置,查找结束。若所有n 个记录的关键字值都已比较,不存在与用户要查的关键字值匹配的记录,则查找失败,给出信息0。

    非递归算法C语言实现:
    int SEQSEARCH1(keytype key[ ],int n,keytype k)
    {
        int i;
        for(i=1;i<=n; i++)              //位置从1开始
            if(key[i]==k)
               return i;
        return 0;
    }
    
    递归算法C语言实现:
    int SEQSEARCH2(keytype key[ ],int n,keytype k,int i)
    {
        if(i>n)
           return 0;
        if(key[i]==k)
           return i;
        return SEQSEARCH2(key,n,k,i+1);
    }
    
    //该函数调用方式如下:
    int pos =  SEQSEARCH2(key,n,k,1);          //从1开始
    
    
    查找效率

    平均查找长度ASL:确定一个记录在文件中的位置所需要进行的关键字值的比较次数的期望值(平均值);

    对于具有n个记录的文件,有
    在这里插入图片描述
    其中,pi为查找第i个记录的概率,ci为查找第i个记录所进行过的关键字的比较次数。

    对于具有n个记录的顺序文件,若查找概率相等,则有
    在这里插入图片描述
    算法的时间复杂度为O(n)

    顺序查找法的优点和缺点

    优点
    1、查找原理和过程简单,易于理解;
    2、对于被查找对象的排列次序没有限制;

    缺点
    1、查找的时间效率低;

    排序连续顺序文件的折半查找法(二分查找法)

    核心思想:

    将要查找的关键字值与当前查找范围内位置居中的记录的关键字的值进行比较。
    若匹配,则查找成功,给出被查到记录在文件中的位置,查找结束。
    若要查找的关键字值小于位置居中的记录的关键字值,则到当前查找范围的前半部分重复上述查找过程,否则,到当前查找范围的后半部分重复上述查找过程,直到查找成功或者失败。
    若查找失败,则给出信息0。

    为实现二分查找法,需要几个变量,如下:
    n :排序连续顺序文件中记录的个数
    low:当前查找范围内第一个记录在文件中的位置。初值 low=1
    high:当前查找范围内最后那个记录在文件中的位置。初值 high=n
    mid:当前查找范围内位置居中的那个记录在文件中的位置,
    mid初值为:
    在这里插入图片描述
    ((low+high)/2 向下取整)

    查找失败的标志为 low > high

    非递归算法的C语言实现:
    int BINSEARCH1(keytype key[ ], int n, keytype k)
    {
        int low=1, high=n, mid;
        while(low<=high){
            mid=(low+high)/2;           //向下取整
            if(key[mid]==k)
               return mid;              // 查找成功
            if(k>key[mid])
               low=mid+1;               // 准备查找后半部分
            else
               high=mid–1;              // 准备查找前半部分
         }
         return 0;                      //查找失败
    }
    
    递归算法的C语言实现:
    int BINSEARCH2(keytype key[ ], int low, int high, keytype k)
    {
        int mid;
        if(low>high)
           return 0;
        else{
           mid=(low+high)/2;
           if(key[mid]==k)
               return mid;
           else
               if(k<key[mid])
                  return BINSEARCH2(key,low,mid–1,k);
               else
                  return BINSEARCH2(key,mid+1,high,k);
       }
    }
    
    查找效率

    若把当前查找范围内居中的记录的位置作为根结点前半部分与后半部分的记录的位置分别构成根结点的左子树与右子树,则由此得到一棵称为“ 判定树”的二叉树,利用它来描述折半查找的过程。如下图:
    在这里插入图片描述

    成功的查找过程正好等于走了一条从根结点到被查找结点的路径,经历的比较次数恰好是被查找结点在二叉树中所处的层次数

    基于此,二分查找的ASL计算如下:
    在这里插入图片描述

    二分查找算法的优点和缺点

    优点
    1、查找原理和过程简单,易于理解。
    2、查找的时间效率较高

    缺点
    1、要求文件的记录按照关键字值有序排列;
    2、对于文件,只适用于排序连续顺序文件;

    为了保持文件为排序顺序文件,在文件中插入和删除记录时需要移动大量的其它记录,所以折半查找方法适用于一经建立就很少改动、而又经常需要查找的文件

    Q:在线性表中采用折半查找方法查找数据元素,该线性表应该满足什么条件?
    A:1、数据元素按值有序排列;2、必须采用顺序存储结构。

    链接顺序文件的查找

    链结点构造

    链结点构造及文件整体构造如下:
    在这里插入图片描述
    C语言实现如下:

    typedef struct node {
        keytype key;
        rectype rec;
        struct node *link;
    } *KeyLink;
    

    非递归查找算法实现如下:

    KeyLink SEARCH1(KeyLink F, keytype k)
    {
        KeyLink p;
        p=F;
        while(p!=NULL){
            if(p->key==k)
                return p; /* 查找成功 */
            p=p->link;
        }
        return NULL; /* 查找失败 */
    }
    

    递归算法实现如下:

    KeyLink SEARCH2(KeyLink F, keytype k)
    {
        if(F!=NULL)
            if(F->key==k )
                return F; /* 查找成功 */
            else
                return SEARCH2(F->link, k );
        return NULL; /* 查找失败 */
    }
    
    展开全文
  • 顺序文件 说法题目

    千次阅读 2019-04-12 11:29:15
    以下对顺序文件描述错误的是() A 插入新的记录时需要将整个文件复制 B 用顺序查找法存取第i个记录,必须先搜索在它之前的i-1个记录 C 如要更新文件中的记录,必须将整个文件复制 D 顺序文件中物理记录的顺序和逻辑...

    以下对顺序文件描述错误的是()

    A 插入新的记录时需要将整个文件复制

    B 用顺序查找法存取第i个记录,必须先搜索在它之前的i-1个记录

    C 如要更新文件中的记录,必须将整个文件复制

    D 顺序文件中物理记录的顺序和逻辑记录的顺序不一致


    顺序文件的最佳应用场合,是在对诸记录进行批量存取时,即每次要读或写一大批记录。此时,对顺序文件的存取效率是所有逻辑文件中最高的;此外,也只有顺序文件才能存储在磁带上,并能有效地工作。 在交互应用的场合,如果用户(程序)要求查找或修改单个记录,为此系统便要去逐个地查找诸记录。这时,顺序文件所表现出来的性能就可能很差,尤其是当文件较大时,情况更为严重。例如,有一个含有104个记录的顺序文件,如果对它采用顺序查找法去查找一个指定的记录,则平均需要查找5×103个记录;如果是可变长记录的顺序文件,则为查找一个记录所需付出的开销将更大,这就限制了顺序文件的长度。

    答案解析

    顺序文件是指按记录进入文件的先后顺序存放、其逻辑顺序和物理顺序一致的文件。
    一切存储在顺序存取存储器(如磁带)上的文件,都只能是顺序文件。
    对A:显然,插入新纪录时不能插入到已经有顺序的文件的中间,只能在末尾。
    对B:如果查找第i个记录,必须从头找起。
    对C:如果要更新,必须复制整个文件,更新,然后在放到另外一块顺序存储器上。
    显然,D是错误的,顺序记录的顺序和逻辑记录的顺序是一致的,也因此导致了前三个选项是正确的。

    展开全文
  • linux库文件头文件查找顺序

    千次阅读 2012-05-14 20:57:54
    Include的header文件,连结数据库,系统定义,总共有下列来源指定gcc去那找。 当初在编译时指定的(在~gcc/gcc/collect2.c:locatelib() 写在specs内的 后来用-D -I -L指定的 gcc环境变量设定(编译的时候) ld.so的...

    Include的header文件,连结数据库,系统定义,总共有下列来源指定gcc去那找。

    当初在编译时指定的(在~gcc/gcc/collect2.c:locatelib()

    写在specs内的

    后来用-D -I -L指定的

    gcc环境变量设定(编译的时候)

    ld.so的环境变量(这是run time的时候)

    一、头文件

    gcc 在编译时如何去寻找所需要的头文件 :

    ※所以header file的搜寻会从-I开始

    ※然后找gcc的环境变量 C_INCLUDE_PATH,CPLUS_INCLUDE_PATH,OBJC_INCLUDE_PATH

    ※再找内定目录

    /usr/include

    /usr/local/include

    /usr/lib/gcc-lib/i386-linux/2.95.2/include

    /usr/lib/gcc-lib/i386-linux/2.95.2/../../../../include/g -3

    /usr/lib/gcc-lib/i386-linux/2.95.2/../../../../i386-linux/include

    库文件但是如果装gcc的时候,是有给定的prefix的话,那么就是

    /usr/include

    prefix/include

    prefix/xxx-xxx-xxx-gnulibc/include

    prefix/lib/gcc-lib/xxxx-xxx-xxx-gnulibc/2.8.1/include

    二、库文件

    cos()等函式库的选项要多加 -lm

    编译的时候:

    ※gcc会去找-L

    ※再找gcc的环境变量LIBRARY_PATH

    ※再找内定目录 /lib /usr/lib /usr/local/lib 这是当初compile gcc时写在程序内的

    三、运行时动态库的搜索路径

    1、在配置文件/etc/ld.so.conf中指定动态库搜索路径

    2、通过环境变量LD_LIBRARY_PATH指定动态库搜索路径(当通过该环境变量指定多个动态库搜索路径时,路径之间用冒号":"分隔)

    3、在编译目标代码时指定该程序的动态库搜索路径(还可以在编译目标代码时指定程序的动态库搜索路径。

    这是通过gcc 的参数"-Wl,-rpath,"指定(如例3所示)。当指定多个动态库搜索路径时,路径之间用冒号":"分隔)

    4、默认的动态库搜索路径/lib

    5、默认的动态库搜索路径/usr/lib

    可以通过执行可执行文件pos得到的结果不同获知其搜索到了哪个动态库,从而获得第1个动态库搜索顺序,然后删除该动态库,

    再执行程序pos,获得第2个动态库搜索路径,再删除第2个被搜索到的动态库,

    如此往复,将可得到Linux搜索动态库的先后顺序。

    程序pos执行的输出结果和搜索到的动态库的对应关系如表1所示

    程序pos输出结果 使用的动态库 对应的动态库搜索路径指定方式

    ./ ./libpos.so 编译目标代码时指定的动态库搜索路径

    /root/test/env/lib /root/test/env/lib/libpos.so 环境变量LD_LIBRARY_PATH指定的动态库搜索路径

    /root/test/conf/lib /root/test/conf/lib/libpos.so 配置文件/etc/ld.so.conf中指定的动态库搜索路径

    /lib /lib/libpos.so 默认的动态库搜索路径/lib

    /usr/lib /usr/lib/libpos.so 默认的动态库搜索路径/usr/lib

    综合以上结果可知,动态库的搜索路径搜索的先后顺序是:

    1.编译目标代码时指定的动态库搜索路径;

    2.环境变量LD_LIBRARY_PATH指定的动态库搜索路径;

    3.配置文件/etc/ld.so.conf中指定的动态库搜索路径;

    4.默认的动态库搜索路径/lib;

    5.默认的动态库搜索路径/usr/lib。


    ====================================================================================

    Linux动态链接库 笔记

    程序执行加载动态库的搜索路径:



     [1]首先查看 .dynamic 段是否包含了一个叫DT_RPATH的项(它是一个以冒号分隔的库文件搜索目录列表)。这个项是在程序被连接器连接时,由命令行开关或者环境变量添加上去的。它常应用于子系统中,比如像数据库应用,我们要装载一些程序集合以及支持库到一个目录中去的时候。


     [2]查看是否存在环境变量 LD_LIBRARY_PATH(它是一个以冒号分隔的库文件搜索目录列表)。这个项可以帮助开发者建立一个新版本的库,把他的路径添加到LD_LIBRARY_PATH中,把它和现存的可连接程序一同使用,用来测试新的库,


    [3]连接器查看库高速缓存文件 /etc/ld.so.conf ,它包含了库名和路径的一个对应列表,如果库名存在,连接器就使用它对应的路径,用这个查找方法能够找到大部分的库(文件名不需要和要求完全符合,这点可以参考接下来的“库的版本”)。


    如果上叙的查找都失败,连接器就查找默认路径 /usr/lib和/lib ,如果库文件依旧没有找到,则显示一个错误然后退出。

           连接器找到了库文件后,先打开它,然后读取ELF头,找到指向各个段的指针。连接器为库的代码段和数据段分配空间并映射到内存,随后是bss(不分配空间)。.通过库的 .dynamic 段,连接器添加这个库的符号表到符号表链,如果库所依赖的其它库没有装载的话,则添加那个库到装载队列中。


    编译程序时动态链接库搜索路径:

    编译程序时如果程序依赖的动态链接库没有安装在系统标准路径:/lib/或/usr/lib程序运行时往往提示找不到相应的动态链接库文件无法执行,原因就在于动态链接加载器ld的搜索路径列表里没有你的库安装路径。

    Linux动态链接库的搜索路径按优先级排序为:


    1.编译目标代码时指定的动态库搜索路径;

         (1)在编译时通过gcc 的参数"-Wl,-rpath,"指定。当指定多个动态库搜索路径时,路径之间用冒号":"分隔。

         (2)用编译选项-L来指定动态链接库所在的目录(供编译器查找用),同时用-l选项指定缩写的动态链接库名。

    这两者之间的区别:

    2.环境变量LD_LIBRARY_PATH指定的动态库搜索路径;
    3.配置文件/etc/ld.so.conf中指定的动态库搜索路径;

       /etc/ld.so.conf的第一行有个引用命令:include ld.so.conf.d/*.conf

          因此,最优雅的方式是在ld.so.conf.d目录下创建一个你的程序依赖的配置文件,配置文件内容为程序依赖的动态链接库的路径,一个路径一行。

         添加完配置文件后执行ldconfig使其生效。
    4.默认的动态库搜索路径/lib;
    5.默认的动态库搜索路径/usr/lib;


    动态链接库如何共享

     
    我们可以采用以下三种方法来共享动态链接库:(注:均须在超级用户状态下操作,以我的动态链接库libmy.so共享过程为例)
     
    (1)拷贝动态链接库到系统共享目录下,或在系统共享目录下为该动态链接库建立个连接(硬连接或符号连接均可,常用符号连接).这里说的系统共享目录,指的是LINUX动态链接库存放的目录,它包含/lib,/usr/lib以及/etc/ld.so.conf文件内所列的一系列目录.
     
    # cp libmy.so /lib
    # ldconfig
    #
     
    或:
     
    # ln -s `pwd`/libmy.so /lib
    # ldconfig
    #
     
    (2)将动态链接库所在目录名追加到动态链接库配置文件/etc/ld.so.conf中.
     
    # pwd >> /etc/ld.so.conf
    # ldconfig
    #
     
    (3)利用动态链接库管理命令ldconfig,强制其搜索指定目录,并更新缓存文件,便于动态装入.
     
    # ldconfig `pwd`
    #
     
    需要说明的是,这种操作方法虽然有效,但效果是暂时的,供程序测试还可以,一旦再度运行ldconfig,则缓存文件内容可能改变,所需的动态链接库可能不被系统共享了.与之相比较,前两种方法是可靠的方法,值得业已定型的动态链接库共享时采用.前两种方法还有一个特点,即最后一条命令都是ldconfig,也即均需要更新一下缓存文件,以确保动态链接库的共享生效.


    展开全文
  • 一、顺序查找 顺序查找适合于存储结构为顺序存储或链接存储的线性表。 基本思想:顺序查找也称为线形查找,属于无序查找算法。从数据结构线形表的一端开始,顺序扫描,依次将扫描到的结点关键字与给定值k相比较,若...

    一、顺序查找
    顺序查找适合于存储结构为顺序存储或链接存储的线性表。

    基本思想:顺序查找也称为线形查找,属于无序查找算法。从数据结构线形表的一端开始,顺序扫描,依次将扫描到的结点关键字与给定值k相比较,若相等则表示查找成功;若扫描结束仍没有找到关键字等于k的结点,表示查找失败。
    

    二、折半查找
    元素必须是有序的,如果是无序的则要先进行排序操作。

    基本思想:也称为是折半查找,属于有序查找算法。用给定值k先与中间结点的关键字比较,中间结点把线性表分成两个子表,若相等则查找成功;若不相等,再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表,这样递归进行,直到查找到或查找结束发现表中没有这样的结点。
    

    三、插值查找
    在介绍插值查找之前,首先考虑一个新问题,为什么折半查找一定要是折半,而不是折四分之一或者折更多呢?

    打个比方,在英文字典里面查“apple”,你下意识翻开字典是翻前面的书页还是后面的书页呢?如果再让你查“zoo”,你又怎么查?很显然,这里你绝对不会是从中间开始查起,而是有一定目的的往前或往后翻。
    
    同样的,比如要在取值范围1 ~ 10000 之间 100 个元素从小到大均匀分布的数组中查找5, 我们自然会考虑从数组下标较小的开始查找。
    
    经过以上分析,折半查找这种查找方式,不是自适应的(也就是说是傻瓜式的)。二分查找中查找点计算如下:
    
    
    mid=(low+high)/2, 即mid=low+1/2*(high-low);
    
    通过类比,我们可以将查找的点改进为如下:
    
    mid=
    low+    (key-a[low])/(a[high]-a[low])    *(high-low),
    
    
    也就是将上述的比例参数1/2改进为自适应的,根据关键字在整个有序表中所处的位置,让mid值的变化更靠近关键字key,这样也就间接地减少了比较次数。
    
    基本思想:基于二分查找算法,将查找点的选择改进为自适应选择,可以提高查找效率。当然,差值查找也属于有序查找。
    
    注:对于表长较大,而关键字分布又比较均匀的查找表来说,插值查找算法的平均性能比折半查找要好的多。反之,数组中如果分布非常不均匀,那么插值查找未必是很合适的选择
    

    四、斐波那契查找

    在介绍斐波那契查找算法之前,我们先介绍一下跟它紧密相连并且大家都熟知的一个概念——黄金分割。
    
    黄金比例又称黄金分割,是指事物各部分间一定的数学比例关系,即将整体一分为二,较大部分与较小部分之比等于整体与较大部分之比,其比值约为1:0.618或1.618:1。
    
    0.618被公认为最具有审美意义的比例数字,这个数值的作用不仅仅体现在诸如绘画、雕塑、音乐、建筑等艺术领域,而且在管理、工程设计等方面也有着不可忽视的作用。因此被称为黄金分割。
    
    大家记不记得斐波那契数列:1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….在数学上,斐波那契被递归方法如下定义:F(1)=1,F(2)=1,F(n)=f(n-1)+F(n-2) (n>=2)。(从第三个数开始,后边每一个数都是前两个数的和)。然后我们会发现,随着斐波那契数列的递增,前后两个数的比值会越来越接近0.618,利用这个特性,我们就可以将黄金比例运用到查找技术中。
    
    基本思想:也是二分查找的一种提升算法,通过运用黄金比例的概念在数列中选择查找点进行查找,提高查找效率。同样地,斐波那契查找也属于一种有序查找算法。
    
    斐波那契查找就是在二分查找的基础上根据斐波那契数列进行分割的。在斐波那契数列找一个等于略大于查找表中元素个数的数F[n],将原查找表扩展为长度为F[n](如果要补充元素,则补充重复最后一个元素,直到满足F[n]个元素),完成后进行斐波那契分割,即F[n]个元素分割为前半部分F[n-1]个元素,后半部分F[n-2]个元素,找出要查找的元素在那一部分并递归,直到找到。
    
    当有序表的元素个数不是斐波那契数列中的某个数字时,需要把有序表的元素个数长度补齐,让它成为斐波那契数列中的一个数值,当然把原有序表截断肯定是不可能的,不然还怎么查找。然后图中标识每次取斐波那契数列中的某个值时(F[k]),都会进行-1操作,这是因为有序表数组位序从0开始的,纯粹是为了迎合位序从0开始。
    
    斐波那契查找的时间复杂度还是O(log 2 n ),但是 与折半查找相比,斐波那契查找的优点是它只涉及加法和减法运算,而不用除法,而除法比加减法要占用更多的时间,因此,斐波那契查找的运行时间理论上比折半查找小,但是还是得视具体情况而定。
    

    五、分块查找
    分块查找又称索引顺序查找,它是顺序查找的一种改进方法,要求按块有序,块内无序。

    算法思想:将n个数据元素"按块有序"划分为m块(m ≤ n)。查找表中共 18 个查找关键字,将其平均分为 3 个子表,对每个子表建立一个索引,索引中包含两部分内容:该子表部分中最大的关键字以及第一个关键字在总表中的位置,即该子表的起始位置。
    
    建立的索引表要求按照关键字进行升序排序,查找表要么整体有序,要么分块有序。
    
    分块有序指的是第二个子表中所有关键字都要大于第一个子表中的最大关键字,第三个子表的所有关键字都要大于第二个子表中的最大关键字,依次类推。
    
    块(子表)中各关键字的具体顺序,根据各自可能会被查找到的概率而定。如果各关键字被查找到的概率是相等的,那么可以随机存放;否则可按照被查找概率进行降序排序,以提高算法运行效率。 
    
    算法流程:
    	1. 先选取各块中的最大关键字构成一个索引表;
    	2. 查找分两个部分:先对索引表进行二分查找或顺序查找,以确定待查记录在哪一块中;然后,在已确定的块中用顺序法进行查找。
    

    六、哈希查找
    1.定义:
    哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

    	哈希表hashtable(key,value) 的做法其实很简单,就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标的数组空间里。
    
    	而当使用哈希表进行查询的时候,就是再次使用哈希函数将key转换为对应的数组下标,并定位到该空间获取value,如此一来,就可以充分利用到数组的定位性能进行数据定位
    
    
    2.哈希查找的操作步骤:
    
    	1)用给定的哈希函数构造哈希表;
    
    	2)根据选择的冲突处理方法解决地址冲突;
    
    	3)在哈希表的基础上执行哈希查找。
    
    3.建立哈希表操作步骤:
    
    	1)step1 取数据元素的关键字key,计算其哈希函数值(地址)。若该地址对应的存储空间还没有被占用,则将该元素存入;否则执行step2解决冲突。
    
    	2)step2 根据选择的冲突处理方法,计算关键字key的下一个存储地址。若下一个存储地址仍被占用,则继续执行step2,直到找到能用的存储地址为止。
    
    
    4.哈希查找步骤为:
    
    	1)Step1 对给定k值,计算哈希地址 Di=H(k);若HST为空,则查找失败;若HST=k,则查找成功;否则,执行step2(处理冲突)。
    
    	2)Step2 重复计算处理冲突的下一个存储地址 Dk=R(Dk-1),直到HST[Dk]为空,或HST[Dk]=k为止。若HST[Dk]=K,则查找成功,否则查找失败。
    
    
    	比如说:”5“是一个要保存的数,然后我丢给哈希函数,哈希函数给我返回一个”2",那么此时的”5“和“2”就建立一种对应关系,这种关系就是所谓的“哈希关系”,在实际应用中也就形成了”2“是key,”5“是value。
    
    
    5.如何做哈希:
    
    做哈希必须要遵守两点原则:
    
    	1)key尽可能的分散,也就是我丢一个“6”和“5”给你,你都返回一个“2”,那么这样的哈希函数不尽完美。
    
    	2)哈希函数尽可能的简单,也就是说丢一个“6”给你,你哈希函数要搞1小时才能给我,这样也是不好的。
    
    其实常用的做哈希的手法有“五种”:
    
    	第一种:”直接定址法“。
    
    		很容易理解,key=Value+C;这个“C"是常量。Value+C其实就是一个简单的哈希函数。
    
    	第二种:“除法取余法”。
    
    		很容易理解, key=value%C;解释同上。
    
    	第三种:“数字分析法”。
    
    		这种蛮有意思,比如有一组value1=112233,value2=112633,value3=119033,
    
    		针对这样的数我们分析数中间两个数比较波动,其他数不变。那么我们取key的值就可以是
    
    		key1=22,key2=26,key3=90。
    
    	第四种:“平方取中法”。此处忽略,见名识意。
    
    	第五种:“折叠法”。
    
    		这种蛮有意思,比如value=135790,要求key是2位数的散列值。那么我们将value变为13+57+90=160,然后去掉高位“1”,此时key=60,哈哈,这就是他们的哈希关系,这样做的目的就是key与每一位value都相关,来做到“散列地址”尽可能分散的目地。
    
    	影响哈希查找效率的一个重要因素是哈希函数本身。当两个不同的数据元素的哈希值相同时,就会发生冲突。为减少发生冲突的可能性,哈希函数应该将数据尽可能分散地映射到哈希表的每一个表项中。
    
    
    6.解决冲突的方法有以下两种:  
    
    	1)开放地址法  
    
    		如果两个数据元素的哈希值相同,则在哈希表中为后插入的数据元素另外选择一个表项。当程序查找哈希表时,如果没有在第一个对应的哈希表项中找到符合查找要求的数据元素,程序就会继续往后查找,直到找到一个符合查找要求的数据元素,或者遇到一个空的表项。这样做容易造成冲突的堆积。  
    
    	2)链地址法
    
    		将哈希值相同的数据元素存放在一个链表中,在查找哈希表的过程中,当查找到这个链表时,必须采用线性查找方法。这样的好处是,不怕冲突多;缺点是降低了散列结构的随机存储性能。本质是用单链表结构辅助散列结构的不足。
    
    7.问题:
    	给定a、b两个文件,各存放50亿个url,每个url各占用64字节,内存限制是4G,如何找出a、b文件共同的url?
    	
    	解法一:
    
    		可以估计每个文件的大小为5G*64=300G (50亿是5000000000,即5G),远大于4G。
    
    		所以不可能将其完全加载到内存中处理,考虑采取分而治之的方法。
    		遍历文件a,对每个url求取hash(url)%1000,然后根据所得值将url分别存储到1000个小文件(设为a0,a1,…a999)当中。这样每个小文件的大小约为300M。
    
    		遍历文件b,采取和a相同的方法将url分别存储到1000个小文件(b0,b1….b999)中。
    
    		这样处理后,所有可能相同的url都在对应的小文件(a0 vs b0, a1 vs b1….a999 vs b999)当中,不对应的小文件(比如a0 vs b99)不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可。
    
    		比如对于a0 vs b0,我们可以遍历a0,将其中的url存储到hash_map当中。然后遍历b0,如果url在hash_map中,则说明此url在a和b中同时存在,保存到文件中即可。
    
    		如果分成的小文件不均匀,导致有些小文件太大(比如大于2G),可以考虑将这些太大的小文件再按类似的方法分成小小文件即可。
    

    七、树表查找

    1.二叉树查找
    
    	基本思想:二叉查找树是先对待查找的数据进行生成树,确保树的左分支的值小于右分支的值,然后在就行和每个节点的父节点比较大小,查找最适合的范围。 这个算法的查找效率很高,但是如果使用这种查找方法要首先创建树。 
    
    	特征:
    		(1)若左子树不为空,则左子树上所有结点的值一定小于根结点的值
    		(2)若右子树不为空,则右子树上所有结点的值一定大于根结点的值
    		(3)左子树和右子树都为二叉排序树。(递归)
    		(4)中序遍历二叉排序树可以得到一个结点值递增的有序线性表
    

    查找算法思路:
    (1)若二叉树为空,查找失败,返回空指针。
    (2)若二叉树不为空,比较根结点的关键字的值data.key和给定值key:
    1)若 data.key = key,则查找成功,返回根结点的地址;
    2)若 data.key < key,则递归查找右子树;
    3)若 data.key > key,则递归查找左子树。

    	***基于二叉查找树进行优化,进而可以得到其他的树表查找算法,如平衡树、红黑树等高效算法。
    
    2.平衡查找树之2-3查找树
    
    	定义:和二叉树不一样,2-3树运行每个结点保存1个或者两个的值:
    		1)要么为空,否则:
    		2)对于2结点,该结点保存一个key以及对应的value,以及两个指向左右结点的值,左节点也是一个2-3结点,所有的值都bikey要小,右结点也是一个2-3结点,所有的值都比key大。
    		3)对于3结点,该结点保存两个key及对应的value,以及三个指向左中右的结点。左结点也是一个2-3结点,所有的值均比两个key中的最小的key还小;中间结点也是一个2-3结点,中间结点的key值在两个根节点的key值之间;右结点也是一个2-3结点,结点的所有值比两个key中的值都大。
    
    	2-3查找树的性质:
    		(1)如果中序遍历2-3查找树,就可以得到排好序的序列
    		(2)在一个完全平衡的2-3查找树中,根节点到每一个为空结点的距离都相同(这也是平衡树中“平衡”一词的概念,根结点到叶结点的最长距离对应于查找算法的最坏情况,而平衡树中根节点到叶结点的距离都一样)
    
    3.平衡查找树之红黑树(Red-Black Tree)
    
    	2-3查找树能保证在插入元素之后能保持树的平衡状态,最坏情况下即所有的子节点都是2-node,树的高度为lgn,从而保证了最坏情况下的时间复杂度。但是2-3树实现起来比较复杂,于是就有了一种简单实现2-3树的数据结构,即红黑树(Red-Black Tree)。
    
    展开全文
  • 查找,就是根据给定的某个值在一组记录集合中确定某个“特定的”数据元素(记录)或者找到属性值符合特定条件的某些记录。 查找表是由同一类型的数据元素(或记录)构成的集合。 关键字:是数据元素(或记录)中某个...
  • 2、文件的逻辑结构思维导图逻辑结构VS物理结构文件的逻辑结果分类1、无结构文件2、有结构文件按照记录的长度来分:按照逻辑结构来分:1、顺序文件问题:能否实现随机存取?2、索引文件3、索引顺序文件梳理: 思维导图...
  • 查找——线性表顺序查找算法

    千次阅读 2015-12-05 15:55:42
    *文件名称: 线性表顺序查找算法.cpp *作 者: 郑兆涵 *查找——线性表顺序查找算法 */ 问题:对线性表顺序查找算法进行分析 编程代码: //线性表顺序查找算法 #include #define MAXL 100 typedef int KeyTy
  • 索引顺序文件

    千次阅读 2013-04-05 15:56:39
    6.5 索引顺序文件 读书笔记整理:文件系统 索引顺序文件顺序文件的扩展,其中各记录本身在介质上也是顺序排列的,它包含了直接处理和修改记录的能力。索引顺序文件能像顺序文件一样进行快速顺序处理,既...
  • 转自 : http://blog.csdn.net/hackerain/article/details/6093165 #include  using namespace std;  typedef struct  {   int r[100];   int length;  ...//顺序查找  int
  • 文件组织:索引顺序文件

    千次阅读 2013-11-08 23:42:39
    ISAM文件和VSAM文件是常用的索引顺序文件。 ISAM文件  ISAM为Indexed Sequential Access Methed(索引顺序存取方法)的缩写,它是一种专为磁盘存取文件设计的文件组织方式,采用静态索引结构。由于磁盘是以盘组、...
  • GCC、头文件查找顺序总结

    万次阅读 2016-04-28 21:56:52
    注意:若编译器在命令行中从左向右顺序读取.o文件,则它们的出现顺序有限制:含有某函数定义的文件 必须出现在含有调用该函数的文件之后。好在GCC无此限制。 编译预处理 ------------------...
  • 1、CFileFind类的声明文件保存在afx.h头文件中。...2、该类的实现的功能:执行本地文件查找(查找某个具体的文件查找某类文件x*.x*,查找所有文件*.*) 3、CFileFind类是CGopherFileFind和CFtpF
  • 文章目录初始化顺序表销毁顺序表打印顺序表增加头插尾插删除查找修改 初始化顺序表 销毁顺序表 打印顺序表 增加 头插 尾插 删除 查找 修改
  • Linux shell指令:查找文件操作

    千次阅读 2018-10-26 10:59:25
    目录下的所有文件查找字符串 find .| xargs grep -ri "class" 目录下的所有文件查找字符串,并且只打印出含有该字符串的文件名 find .| xargs grep -ri "class" -l 另一种方法:...
  • (1)采用交互工作方式 (2)可以增加、删除、修改信息 (3)建立数据文件,数据文件按关键字(姓名、学号、房号)进行排序(选择、快速排序、堆排序等任选一种) (4)查询: a.按姓名查询 ;b.按学号查询 ;c按房号...
  • 五款优秀重复文件查找工具

    万次阅读 2013-01-29 09:53:37
    五款优秀重复文件查找工具推荐 电脑长时间使用之后,不可避免的会产生各种无用的文件,而这其中有很大一部分都是重复文件,这些重复文件可能是你出于临时备份多次复制而产生的,也有可能是某些软件程序自动生成...
  • ubuntu 查找文件中的字符串

    千次阅读 2018-10-26 17:57:44
    查找目录下的所有文件中是否含有某个字符串  find .|xargs grep -ri "IBM"  查找目录下的所有文件中是否含有某个字符串,并且只打印出文件名  find .|xargs grep -ri "IBM" -l  1.正则表达式...
  • Linux命令查找目录下的所有文件

    千次阅读 2019-09-13 18:47:11
    查找目录下的所有文件中是否含有某个字符串 find .|xargs grep -ri "IBM" 查找目录下的所有文件中是否含有某个字符串,并且只打印出文件名 find .|xargs grep -ri "IBM" -l 1.正则表达式 (1)正则表达式一般用来描述...
  • 目录下的所有文件查找字符串 find .| xargs grep -ri "class" 目录下的所有文件查找字符串,并且只打印出含有该字符串的文件名 find .| xargs grep -ri "class" -l 另一种方法:
  • 查找目录下的所有文件中是否含有某个字符串  find .|xargs grep -ri "IBM"  查找目录下的所有文件中是否含有某个字符串,并且只打印出文件名  find .|xargs grep -ri "IBM" -l  1.正则表达式   (1)正则...
  • C语言头文件、库文件查找路径

    千次阅读 2015-06-08 18:11:57
    在程序设计中,文件包含是很有用的。...有 些公 用的符号常量或宏定义等可单独组成一个文件,在其它文件的开头用包含命令包含该文件即可使用。这样,可避免在每个文件开头都去书写那些公用量,从而节省时间
  • Linux C/C++语言头文件、库文件查找路径  在程序设计中,文件包含是很有用的。一个大的程序可以分为多个模块,由多个程序员分别编程。有 些公 用的符号常量或宏定义等可单独组成一个文件,在其它文件的...
  • Linux查找文件内容的常用命令方法。 从文件内容查找匹配指定字符串的行: $ grep "被查找的字符串" 文件名 例子:在当前目录里第一级文件夹中寻找包含指定字符串的.in文件 grep "thermcontact" */*.in ...
  • Linux中查找目录或文件中的内容总结

    千次阅读 2016-09-28 12:38:44
    查找目录下的所有文件中是否含有某个字符串  find .|xargs grep -ri "IBM"  查找目录下的所有文件中是否含有某个字符串,并且只打印出文件名  find .|xargs grep -ri "IBM" -l  1.正则表达式   (1)正则...
  • 查找习题

    千次阅读 2018-06-03 14:53:17
    查找每个记录的概率均等,则在具有n个记录的连续顺序文件采用顺序查找查找一个记录,其平均查找长度ASL为( C )。 A. (n-1)/2 B. n/2 C. (n+1)/2 D. n2. 对N个元素的表做顺序...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 195,327
精华内容 78,130
关键字:

对于顺序文件采用什么查找