精华内容
下载资源
问答
  • 列表法需要注意什么
    千次阅读
    2021-10-09 22:35:04

    散列表

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

    装填因子

            关键字个数 / 表长

    处理冲突

            一般来说冲突不可避免的,只能尽可能地减少冲突的发生。在建立Hash表的时候必须进行冲突处理。
            下面主要介绍线性探测法:也是一种比较常用的处理冲突的方法(但是极易产生堆积问题)

    • 线性探测法 即从发生冲突的地址(记做d)开始,依次探查d的下一个地址,直至找到一个空位置为止。记住这句话。查找时若查到空位置还没有找到需要查找的元素则说明不在列表中,结合前一句话理解一下,还是比较容易理解的。这个为后面计算查找失败的平均长度提供了计算思路。
    • 链地址法 通过单链表将关键字连接起来,利用这种方法不会产生堆积问题。但是所谓的堆积问题,并不能完全通过利用单链表法来避免。毕竟并不是适用于任何问题,在能够利用链地址法不能解决冲突的问题,也许利用线性探测法可以有着不错的效果。

    性能分析

    即本文的主要内容,查找成功与查找失败的分析。

    • 查找成功平均查找长度即找到表中已有表项的平均比较次数
    • 查找失败平均查找长度即找不到待查的表项但能找到插入位置的平均比较次数

    平均查找长度的计算

    直接以题目来理解会比较快些:

            现有长度为11 且初始为空的散列表HT,散列函数H(key) = key % 7,采用线性探查法解决冲突。将关键字序列87,40,30,6,11,22,98,20 依次插入HT后,HT的查找失败的平均长度是多少呢? 查找成功的平均查找长度又是多少呢?
            ① 首先,通过散列函数并且利用线性探测法给他们每个字划分好自己的位置;
            ② 记录每个字冲突的次数,后面在计算查找成功的平均长度会用到;
            ③ 查找失败计算每个查找失败对应地址的查找次数,即从所查位置开始往后查直至查到空位置位置;
            ④ 其实,后面熟悉过程之后,在列出下面的每个关键字对应地址的表格之后就可以秒出答案;

    注意事项 查找失败时对应的地址在这个题目,只能是7 即 0~6 ;

    ASL 查找失败= (9 + 8 + 7 + 6 + 5 + 4 + 3 )/ 7 = 6

    ASL 查找成功= (1 + 1 + 1 + 1 + 1 + 1 + 1 + 2)/ 8 = 9 / 8

    散列地址012345678910
    关键字982230871140620
    冲突次数00000001

    OK,上面把例子说完了,可以再看看下面这个题目,来测试下是否理解了上面的那些需要注意的点。
            将关键字序列(7,8,30,11,18,9,14)散列存储到散列表中。散列表的存储空间是从0开始的一维数组,散列函数为H(key) = (3*key)mod 7,处理冲突采用线性探测法,要求装填因子为0.7。
            (1)画出所构造的散列表。
            (2)分别计算等概率情况下的查找成功和不成功的平均查找长度。(12/7 和 18/7

    (1)数组大小 = 7 / 0.7 = 10

    散列地址0123456789
    关键字71481130189

    (2)
            ①查找成功时

    散列地址0123456789
    关键字71481130189
    冲突次数0100022
    比较次数1211133

            ASL 查找成功= (1 + 2 + 1 + 1 + 1 + 3 + 3 )/ 7 = 12 / 7
            ②查找失败时

    散列地址0123456789
    关键字71481130189
    比较次数3212154

            ASL 查找失败= (3 + 2 + 1 + 2 + 5 + 4)/ 7 = 18 / 7

    【总结】简单吧,主要就是查找失败时除以的分母是 mod 后面的那个数,而不是关键字的个数。

    更多相关内容
  • 表格/列表法之分部积分

    万次阅读 多人点赞 2020-05-28 18:13:32
    在求积分的过程中,我们经常使用微积分里的分布积分,但对于一些复杂的函数,需要运用多次分布积分,比如你可能见过这样的, 处理起来很是头疼,然而用表格就能起到这样的效果 下面说明一下如何使用这种方法 ...

    在求积分的过程中,我们经常使用微积分里的分布积分法,但对于一些复杂的函数,需要运用多次分布积分,比如你可能见过这样的,
    在这里插入图片描述
    处理起来很是头疼,然而用表格法就能起到这样的效果
    在这里插入图片描述
    在这里插入图片描述
    下面说明一下如何使用这种方法
    对积分 ∫ v u   d x \int vu\,dx vudx
    列成表格
    在这里插入图片描述
    第一行表示求导,第二行求原函数
    表中内容可分为三部分,连线的地方将他们相乘
    图中红色地方表示正
    比如 v ∫ u   d x , v ′ ′ ∫ ∫ ∫ u   d x v\int u\,dx,v''\int\int\int u\,dx vudx,vudx
    图中黑色地方表示负
    比如 − v ′ ∫ ∫ u   d x -v'\int\int u\,dx vudx
    绿色地方表示
    ( − 1 ) n ∫ ( v n ( ∫ ) n u ) d x (-1)^n\int (v^n(\int)^nu)dx (1)n(vn()nu)dx 注意:这里的n表示求导或积分的总次数
    最后把这三部分加起来即可,不理解的话请看下面这个例子


    C n = 2 l ∫ 0 l x ( l − x ) s i n n π x l d x Cn =\frac{2}{l}\int_0^l x(l-x)sin\frac{nπx}{l}dx Cn=l20lx(lx)sinlnπxdx
    正常计算:
    在这里插入图片描述
    表格法:

    x ( l − x ) x(l-x) x(lx) l − 2 x l-2x l2x − 2 -2 2
    2 l s i n n π x l \frac2lsin\frac{nπx}{l} l2sinlnπx − 2 n π c o s n π x l -\frac{2}{nπ}cos\frac{nπx}{l} nπ2coslnπx − 2 l n 2 π 2 s i n n π x l -\frac{2l}{n^2π^2}sin\frac{nπx}{l} n2π22lsinlnπx

    C n = [ x ( l − x ) ( − 2 n π c o s n π x l ) − ( l − 2 x ) ( − 2 l n 2 π 2 s i n n π x l ) ] ∣ l 0 ∣ + Cn=\left[x(l-x)(-\frac{2}{nπ}cos\frac{nπx}{l})\right.\\-(l-2x)(-\frac{2l}{n^2π^2}sin\frac{nπx}{l})]\begin{vmatrix} l \\ 0\end{vmatrix}+ Cn=[x(lx)(nπ2coslnπx)(l2x)(n2π22lsinlnπx)]l0+ ( − 1 ) 2 ∫ 0 l ( − 2 ) − 2 l n 2 π 2 s i n n π x l d x (-1)^2\int_0^l(-2) \frac{-2l}{n^2π^2}sin\frac{nπx}{l}dx (1)20l(2)n2π22lsinlnπxdx
    = 0 − 4 l 2 n 3 π 3 c o s n π x l ∣ l 0 ∣ =0-\frac{4l^2}{n^3π^3}cos\frac{nπx}{l}\begin{vmatrix} l \\ 0\end{vmatrix} =0n3π34l2coslnπxl0
    = 4 l 2 n 3 π 3 ( 1 − c o s n π ) =\frac{4l^2}{n^3π^3}(1-cosnπ) =n3π34l2(1cosnπ)

    如果还不太懂可以看一下文章开头的那个例子,自己算一下

    运用表格法只需进行对被积函数进行求导积分运算,一步得结果,大大减少了出错率。

    在这里插入图片描述

    展开全文
  • python list列表的乘除

    万次阅读 2020-04-30 20:46:05
    由于需要列表数据整体处理,所以需要遍历整个 列表元素,这里 以全int型数据为例 x = [72, 50, 81, 74, 94, 86, 59, 83, 65, 33, 88, 81] x_=[] for i in x: i/=10 #对数据逐个处理 x_.append(i) x=x_ print(x) ...

    1

    由于需要对列表数据整体处理,所以需要遍历整个 列表元素,这里 以全int型数据为例

    x = [72, 50, 81, 74, 94, 86, 59, 83, 65, 33, 88, 81]
    x_=[]
    for i in x:
        i/=10   #对数据逐个处理
        x_.append(i)
    x=x_
    print(x)
    

    2

    上述是利用for 循环实现的,也可不用,如下:

    x = [72, 50, 81, 74, 94, 86, 59, 83, 65, 33, 88, 81]
    s=[10,10,10,10,10,10,10,10,10,10,10,10]
    xx=[a/b for a,b in zip(x,s)]     #利用该语句实现
    x=xx
    print(x)
    
    

    3

    还有一种情况假如要除的数是数值,但是由这个列表内数值计算出的,那么可以用

    x[:]=x[:]/x_std
    

    这条语句来实现,以下面例子来方便读者体会:

        x=[]
        y=[]
        data = [[72, 84], [50, 63], [81, 77], [74, 78], [94, 90], [86, 75], [59, 49], [83, 79], [65, 77], [33, 52],
                [88, 74], [81, 90]]
        for a,b in data:
            x.append(a)
            y.append(b)
        x_mean = np.mean(x)
        x_std = np.std(x)
        y_mean = np.mean(y)
        y_std = np.std(y)
        xx=[]
        yy=[]
        xx[:]=x[:]-x_mean
        xx[:]=x[:]/x_std
        yy[:]=y[:]-y_mean
        yy[:]=y[:]/y_std
    

    4

    当然 可以用numpy数组 ,将列表转为numpy数组,之后循环遍历也可以
    如下:

    import numpy as np
     
    a = np.array([1,1,1])  #这样的确简单,但考虑到可能你还需要再转回list类型,也可以不用这种方法,而用上面几种
    c = a/3
    print(c)
    

    注意以下是不可以的!!!

    a = [1.0, 1.0, 1.0]
    c = a/3          # 这样是不可以的
    #会出现 TypeError: unsupported operand type(s) for /: 'list' and 'int'
    print(c)
    

    另附笔记二维列表不能和数组一样循环遍历

    在这里插入图片描述

    另外对列表的拼接以及元素级的相加,还有相减,相乘等看下面这个blog:
    https://blog.csdn.net/jp_666/article/details/98055191?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-1&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromBaidu-1

    展开全文
  • 数据结构——散列表--线性探测

    千次阅读 2019-12-07 16:18:56
    下面对散列表的构造方式加以说明,注意表1中的关键字7和14,30和9, 11和18,这三组关键子的H(Key)值相同,这在构建散列表时就会产生冲突,因为他们的地址相同,所以要通过一定的冲突处理方法来解决这个问题。...

    最近复习了下数据结构中的哈希表,发现在计算等概率情况下查找不成功的平均查找长度时比较迷茫,不知道到底是怎么计算出来的。现在通过查阅资料终于知道如何计算了,所以记录下来以供以后查阅。

       下面看下2010年2010年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题中一个考哈希表的题。

    Question1:

    将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组,散列函数为:      H(key) = (keyx3) MOD 7,处理冲突采用线性探测再散列法,要求装填(载)因子为0.7。

    (1) 请画出所构造的散列表。

    (2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。

    Ans:

    (1).首先明确一个概念装载因子,装载因子是指所有关键子填充哈希表后饱和的程度,它等于 关键字总数/哈希表的长度。 根据题意,我们可以确定哈希表的长度为 L = 7/0.7 = 10;因此此题需要构建的哈希表是下标为0~9的一维数组。根据散列函数可以得到如下散列函数值表。

    H(Key) = (keyx3) MOD 7, 例如key=7时, H(7) = (7x3)%7 = 21%7=0,其他关键字同理。

    Key78301118914
    H(Key)0365560

    (表1)

    采用线性探测再散列法处理冲突,所构造的散列表为:

    地址0123456789
    关键字714 8 1130189 

    (表2)

    下面对散列表的构造方式加以说明,注意表1中的关键字7和14,30和9, 11和18,这三组关键子的H(Key)值相同,这在构建散列表时就会产生冲突,因为他们的地址相同,所以要通过一定的冲突处理方法来解决这个问题。依题,采用线性探测再散列法处理冲突。下面详细介绍如何构建散列表:

           第一个key 7,它的地址是0,因此放到散列表的数组下表为0的位置,这个位置上没有关键字,因此没有冲突可以直接填入;

           第二个key 8,它的地址是3,因此放到散列表的数组下表为3的位置,这个位置上没有关键字,因此没有冲突可以直接填入;

           第三个key 30,它的地址是6,因此放到散列表的数组下表为6的位置,这个位置上没有关键字,因此没有冲突可以直接填入;

           第四个key 11,它的地址是5,因此放到散列表的数组下表为5的位置,这个位置上没有关键字,因此没有冲突可以直接填入;

           第五个key 18,它的地址是5,因此放到散列表的数组下表为5的位置,但这个位置上已经有关键字11,遇到了冲突,此时我们根据线性探测再散列法来处理这个冲突,探测下一个位置6, 6这个位置上已经存在关键字30则继续增加步长1,因此现在的新地址应为7,位置7上没有关键字,放入即可,到此冲突已经解决;

           第六个key 9,它的地址是6,因此放到散列表的数组下表为6的位置,但这个位置上已经有关键字30,遇到了冲突,探测下一个位置7, 7这个位置上已经存在关键字18则继续增加步长1,因此现在的新地址应为8,位置8上没有关键字,放入即可;   

           第七个key 14,它的地址是0,因此放到散列表的数组下表为0的位置,但这个位置上已经有关键字7,遇到了冲突,探测下一个位置1, 位置1上没有关键字,放入即可;   

           到这一步所有关键字均已填入,散列表已经构造完成,如表2所示。

    (2)等概率情况下查找成功平均查找长度:

            这一问可以根据第一问的构造过程求解:

            key7一次就填入了表中,因此查找次数为1,同理8, 30, 11查找次数均为1; key18 进行了3次放入操作,探测位置分别是5,6,7 ,因此查找次数为3;key9也是3次;key14 进行了两次探测,因此查找次数为2。次数表如表3所示

    Key78301118914
    Count1111332

    (表3)

            所以ASLsuccess= (1+1+1+1+3+3+2)/ 7 = 12/7。  

            等概率情况下查找不成功的平均查找长度:

            接下来讨论不成功的情况, 看表2,计算查找不成功的次数就直接找关键字到第一个地址上关键字为空的距离即可, 但根据哈希函数地址为MOD7,因此初始只可能在0~6的位置。等概率情况下,查找0~6位置查找失败的查找次数为:

       看地址0,到第一个关键字为空的地址2的距离为3,因此查找不成功的次数为3.     

            地址1, 到第一个关键为空的地址2的距离为2,因此查找不成功的次数为2.

            地址2,  到第一个关键为空的地址2的距离为1,因此查找不成功的次数为1.

            地址3,到第一个关键为空的地址4的距离为2,因此查找不成功的次数为2.

            地址4,到第一个关键为空的地址4的距离为1,因此查找不成功的次数为1.

            地址5,到第一个关键为空的地址2(注意不是地址9,因为初始只可能在0~6之间,因此循环回去)的距离为5,因此查找不成功的次数为5.

            地址6,到第一个关键为空的地址2(注意不是地址9,因为初始只可能在0~6之间,因此循环回去)的距离为4,因此查找不成功的次数为4.

            因此查找不成功的次数表如下表所示

    Key78301118914
    Count3212154

    (表4)

           所以ASLunsuccess= (3+2+1+2+1+5+4)/ 7 = 18/7。

    展开全文
  • 列表相关题目(线性探测再散列

    千次阅读 多人点赞 2020-12-02 02:05:00
    列表相关题目(线性探测再散列) 一、题目 将关键字序列(7、8、30、11、18、9、14)散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组,散列函数为H(key)=(key×3) mod 7,处理冲突采用线性...
  • Python数据结构-列表

    千次阅读 多人点赞 2021-12-24 10:29:01
    需要注意的是:列表可包含任何类型的值:数字、字符串甚至其他序列。空列表用 [] 表示,而只包含一个元素(x)的单元素列表写做 [x] 。其访问方式与字符串的索引方式一样,以num2为例,如下图:列表索引从 0 开始,...
  • 列表之链接

    千次阅读 2015-06-14 12:38:37
    列表之链接列表的定义 散列表的基本操作 散列表的编码实现 散列表的设计 主测试文件 编译运行 结论注意: 本文中的所有代码你可以在这里 ...或者这里 ...
  • 列表(上)——开放定址

    万次阅读 多人点赞 2017-09-20 19:23:15
    概述散列表,又称哈希表,hash表。散列表是一种特殊的数据结构,它同数组、链表以及二叉排序树等相比较有很明显的区别,它能够快速定位到想要查找的记录,而不是与表中存在的记录的关键字进行比较来进行查找。这个...
  • 【哈希表 | 散列表】根据关键字的值来计算出关键字在表中的地址 address = H(key) 【哈希函数|散列函数】函数H(key) 举例 构造 查找 查找成功的分析 查找失败的分析 构造哈希函数 哈希函数...
  • 列表之开放定址

    万次阅读 2015-07-12 00:13:46
    列表之开放定址列表的基本操作 插入操作_INSERT 查找操作_SEARCH 删除操作_DELETE 散列表的探查方法probe methods 散列表探查的定义 线性探查 二次探查 双重散列 总结注意: 本文中所有的代码你可以在这里:...
  • Web测试需要注意的点

    万次阅读 多人点赞 2019-04-16 16:35:24
    测试用例是测试的核心,测试用例的设计是一种思维方式的体现,在用例的设计中,用的比较多的方法是边界值分析和等价类划分,下面主要从输入框,搜索功能,添加、修改功能,删除功能,注册、登录功能以及上传图片...
  • Python基础之:数字字符串和列表

    千次阅读 2021-02-22 19:13:04
    Python的主要应用是进行科学计算,科学计算的基础就是数字,字符串和列表。本文将会详细的给大家介绍一下这三个数据类型的使用情况。
  • 详解Python列表

    千次阅读 2020-12-16 00:47:16
    一、概念在Python中,列表(list)是常用的数据类型。...例如,下面的列表包含了数字和字符串:列表还可以为空,空列表可以使用空的方括号创建:二、索引列表是有序的,可以通过索引(index)访问列表中的项。...
  • 在Java 9+版本中,接口的内容可以有: 1.成员变童其实是常童,格式: [public] [static] [final] 数据类型 常置名称 = 数据值...[public] [abstract] 返回值类型 方法名称(参数列表〉; 注意:实现类必须覆盖重写...
  • 在最近对散列表的学习中,以线性探测处理的散列表的删除操作让我无所适从,从网上、考研参考书等等各方面查找到的资料也都不尽人意,因此写写博客,希望能够给同样无所适从的朋友一点思路。 我主要针对机械工业...
  • 列表--线性探测

    千次阅读 2014-10-13 15:36:49
    下面对散列表的构造方式加以说明,注意表1中的关键字7和14,30和9, 11和18,这三组关键子的H(Key)值相同,这在构建散列表时就会产生冲突,因为他们的地址相同,所以要通过一定的冲突处理方法来解决这个问题。...
  • 列表查找失败平均查找长度

    万次阅读 多人点赞 2020-11-01 21:04:40
    要想知道 散列表查找失败的平均查找长度,就要知道什么叫做查找失败!举个栗子:8个数字 key%11 如下算好了: 散列地址 0 1 2 3 4 5 6 7 8 9 10 关键字 33 1 13 12...
  • 注意力机制最新综述解读

    万次阅读 多人点赞 2019-04-16 18:02:24
    注意力模型(Attention Model,AM)已经成为神经网络中的一个重要概念,并在不同的应用领域进行了充分的研究。这项调查提供了一个结构化和全面的概述关于attention的发展。我们回顾了注意力机制被纳入的不同的神经网络...
  • Python数据结构与算法 列表和字典性能比较

    千次阅读 多人点赞 2021-02-18 13:57:39
    前面我们了解了 “大O表示” 以及对不同的算法的评估,下面来讨论下 Python 两种内置数据类型有关的各种操作的大O数量级:列表 list 和字典dict。 这是两种非常重要的 Python 数据类型,后面会用来实现各种数据...
  • 基本创建:把逗号分隔的不同数据项采用方括号括起来,注意列表索引值从0开始;list_1 = [1, 2, 3, 4, 5] 利用list()函数创建; list_2 = list([6, 7, 8, 9, 10]) 添加元素: list_2.append(1) 删除元素:del list_...
  • 分治( Divide and Conquer)

    千次阅读 2021-12-05 17:08:05
    分治也称为分解、分治策略等。本文梳理下梳理下分治
  • 什么是番茄工作

    千次阅读 多人点赞 2021-02-14 22:58:03
    1什么是番茄工作 2番茄工作的基本原则 3番茄工作的目的 4番茄工作的做法 5番茄工作的五个基本流程 6番茄工作的经验技巧 7番茄工作案例[1] 什么是番茄工作 番茄工作是简单易行的时间管理...
  • 列表-拉链

    千次阅读 2014-09-30 11:48:29
    若选定的散列表长度为m,则可将散列表定义为一个由m个头指针组成的指针数组T[0..m-1]。凡是散列地址为i的结点,均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。在拉链中,装填因子α可以大于1,...
  • 列表的乘法

    千次阅读 2020-02-25 14:29:58
    a=list(range(1,6)) a ## 方法一 ...##如果列表直接乘5,表示将列表复制五倍,而不是每个元素都乘5 a*5 ##加载一个numpy包 import numpy as np np.array(a) ##此时直接乘5即可实现之前操作 ...
  • H(key) = (keyx3) MOD 7,处理冲突采用线性探测再散列,要求装填(载)因子为0.7。 (1) 请画出所构造的散列表。 (2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。 Ans: (1).首先明
  • 【数据结构】散列表知识点

    千次阅读 2021-04-16 09:29:56
    1. 散列存储的特性 散列存储:散列表,采用的存储方式是散列存储。那么何为散列存储呢?...2. 什么是散列表列表:散列表是根据数据元素的关键字而直接进行访问的数据结构。通俗地讲,就是散列表建立了
  • 云 mixly 扩展库

    千次阅读 热门讨论 2021-09-28 14:30:00
    第一,安装扩展库 ...下载完成后解压,在mixly软件中,选择「导入库」→「本地导入」,选择解压文件夹中的「Bemfa.xml」即可。或者使选择云端导入,点击「巴云」导入即可。 第二,tcp协议使用教程 ...在需要
  • 目录: 一:直接定址 二:数字分析 三:平方取中法 四:折叠 五:除留余数 ...六:随机数 ...但问题是这需要事先知道关键字的分布情况 适合查找表较小且连续的情况 由于这样的限制,在现...
  • 【人事】电话面试时需要注意什么

    万次阅读 2018-05-12 18:44:51
    电话面试时需要注意的地方,主要是一些细节上的注意事项。 1、电话突然打来怎么办 企业突然来电,往往令你措手不及,也许你正在上课,也许正在运动,也许正在公车上,此时没有任何准备,建议你首先试探看看对方...
  • 代码详解使用循环输出列表,利用 计数器控制输出数量,当输出到第十个,计数器归零,重新开始计数print输出增加end参数可以控制输出后以什么结尾这里使用range方法快速生成10-90的数字添加进list列表results = list...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 211,444
精华内容 84,577
关键字:

列表法需要注意什么