首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【Python数据结构系列】☀️《查找、排序-基础知识》——知识点讲解+代码实现☀️

【Python数据结构系列】☀️《查找、排序-基础知识》——知识点讲解+代码实现☀️

作者头像
天道Vax的时间宝藏
发布2021-09-26 11:36:24
4170
发布2021-09-26 11:36:24
举报

数据结构之查找

1、线性表的查找

在查找表的组织方式中,线性表示最简单的一种。本节将介绍基于线性表的顺序查找、折半查找和分块查找

1.1 顺序查找

顺序查找的查找过程为:从表的一端开始,依次将记录的关键字和给定值进行比较,若某个记录的关键字和给定值相等,则查找成功;反之,若扫描整个表后,仍未找到关键字和给定值相等的记录,则查找失败。

1.2 折半查找

折半查找也称二分查找,它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。在下面及后序的讨论中,均假设有序表是递增有序的。 折半查找的查找过程为:从表的中间记录开始,如果给定值和中间记录的关键字相等,则查找成功;如果给定值大于或者小于中间记录的关键字,则在表中大于或小于中间记录的那一半中查找,这样重复操作,直到查找成功,或者在某一步中查找区间为空,则代表查找失败。

折半查找每一次查找比较都使查找范围缩小一半,与顺序查找相比,很显然会提高查找效率。 如有序表(05,13,19,21,37,56,64,75,80,92),描述查找关键字21的过程如下:

Image Name
Image Name

1.3 分块查找

分块查找又称为索引顺序查找,它吸取了顺序查找和折半查找各自的优点,既有动态结构,又适于快速查找。

分块查找的思想:将查找表分为若干子块。块内的元素可以无序,但块之间是有序的,即第一块中的最大关键字小于第二块中的所有记录的关键字,第二个块中的最大关键字小于第三块中的所有记录的关键字,以此类推。再建立一个索引表,索引表中的每个元素含有各块的最大关键字和各块中的第一个元素的地址,索引表按关键字有序排列。

分块查找的过程分为两步

  • 第一步实在索引表中确定待查记录所在的块,可以顺序查找或折半查找索引表;
  • 第二步是在块内顺序查找。

例如:关键码集合为{88,24,72,61,21,6,32,11,8,31,22,83,78,54},按照关键码值24,54,78,88分为四个块和索引表,如下图所示:

Image Name
Image Name

大作业一:实现简单查找

  • 实现顺序查找
  • 实现折半查找
  • 实现分块查找

最后输出结果要求:   三种查找的结果返回形式为:存在返回值得索引,不存在则返回None。   输入案例为一个列表,自拟即可。

代码思路:(仅供参考,思路不限)

顺序查找:遍历一下列表,然后跟目标值比较,直到查找成功或查找失败。 折半查找:从有序列表的初始候选区 list[0:n-1] 开始,通过对待查找的值与候选区中间值得比较,可以使候选区减少一半。定义一个初始的left=0,right=n-1,然后计算中间值mid=(left+right)/2(整除),然后判断出中间元素与我们查找的元素的关系,如果一致则查找成功,如果不一致则更新left和right的值,再计算新的mid,重复上述步骤,直到查找成功或查找结束。

注:只有left小于right的时候候选区是有值的,也就是说只要left大于了right则查找失败。

分块查找:分块是在列表加入一个分块的操作,可以自己定义每一块的长度,最后一个不够该长度的也要自成一块,然后每一块中的最大值为该块的索引,因此在查找过程中,我们先在块与块之间使用折半查找或顺序查找,来定位待查找的数所处哪一块中,然后再在该块上使用顺序查找,最终查找成功或者失败。

# 遍历一下列表,然后跟目标值比较,直到查找成功或查找失败。
List = [1,10,23,3,11,30,5,16,34,7,20,50]

def find(x,List):
    n = 0
    index = None
    for i in List:
        if x==i:
            index = n
        n += 1
    return index

find(7,List)
在这里插入图片描述
在这里插入图片描述
def binarySearch(x, arr, low, high):#迭代算法
    while low <= high:
        mid = (low+high)//2
        if x == arr[mid]:
            break
        elif x < arr[mid]:
            high = mid -1
        else:
            low = mid + 1
    else:
        print(None)
        return
    print(mid)
    return

List=[2,4,5,6,8,9,12,45,65,70,83]

binarySearch(93,List,0,len(List)-1)
binarySearch(5,List,0,len(List)-1)
在这里插入图片描述
在这里插入图片描述
def search(data, key):  # 用二分查找 想要查找的数据在哪块内
    length = len(data)  # 数据列表长度
    first = 0  # 第一位数位置
    last = length - 1  # 最后一个数据位置
    print(f"长度:{length} 分块的数据是:{data}")  # 输出分块情况
    while first <= last:
        mid = (last + first) // 2  # 取中间位置
        if data[mid] > key:  # 中间数据大于想要查的数据
            last = mid - 1  # 将last的位置移到中间位置的前一位
        elif data[mid] < key:  # 中间数据小于想要查的数据
            first = mid + 1  # 将first的位置移到中间位置的后一位
        else:
            return mid  # 返回中间位置
    return False

def block(data, count, key):  # 分块查找数据,data是列表,count是每块的长度,key是想要查找的数据
    length = len(data)  # 表示数据列表的长度
    block_length = length // count  # 一共分的几块
    if count * block_length != length:  # 每块长度乘以分块总数不等于数据总长度
        block_length += 1  # 块数加1
    print("一共分", block_length, "块")  # 块的多少
    print("分块情况如下:")
    for block_i in range(block_length):  # 遍历每块数据
        block_data = []  # 每块数据初始化
        for i in range(count):  # 遍历每块数据的位置
            if block_i * count + i >= length:  # 每块长度要与数据长度比较,一旦大于数据长度
                break  # 就退出循环
            block_data.append(data[block_i * count + i])  # 每块长度要累加上一块的长度
        result = search(block_data, key)  # 调用二分查找的值
        if result != False:  # 查找的结果不为False
            return block_i * count + result  # 就返回块中的索引位置
    return False

data = [23, 43, 56, 78, 97, 100, 120, 135, 147, 150, 155]  # 数据列表
print('数据列表为:[23, 43, 56, 78, 97, 100, 120, 135, 147, 150, 155]')
goal = 100
print('查找 ',goal,'\n')
result = block(data, 4, 100)
print("查找的值的索引位置是:", result)  # 输出结果
在这里插入图片描述
在这里插入图片描述

大作业二:完成排序

题目:给定一个m×n的二维列表,查找一个数是否存在。列表有下列特性:

  • 每一行的列表从左到右已经排序好。
  • 每一行第一个数比上一行最后一个数大。

测试案例:输入如下列表(list = x),找数值3(target = 3),找到返回True,找不到返回False。 x = [[1,3,5,7], [10,11,16,20], [23,30,34,50] ]

代码思路:(仅供参考,思路不限) 可采用折半查找,但是要思考的是此时我们需要定位的数值的索引值将是二维列表的下标,因此mid将不是一个一维数字。

def find(target,arr):
    rows=len(arr)-1
    cols=len(arr[0])-1
    i=rows
    j=0
    while i>=0 and j<=cols:
        if target<arr[i][j]:
            i-=1
        elif target>arr[i][j]:
            j+=1
        else:
            print(True,i,j)
            return
    print(None)
    return

List = [
    [1,3,5,7],
    [10,11,16,20],
    [23,30,34,50]
]

find(3,List)
print()
find(4,List)
在这里插入图片描述
在这里插入图片描述

大作业三:查找目标值

题目:给定一个有序列表和一个整数,设计算法找到两个数的下标,使得两个数之和为给定的整数。保证肯定且仅有一个结果。

测试案例:例如,输入列表[1,2,5,4]与目标整数3, 由1+2=3,因此输出的结果为(0,1)。

代码思路:(仅供参考,思路不限) (1)可使用顺序查找,循环判断找到我们的目标值。 (2)我们可以根据一个数,通过目标数减去这个树然后得到另一个数,再来判断另一个数是否窜在,存在则输出他们的索引,不存在则换一个数重复上述步骤,直至成功。

def brute_force(li,target):
    n=len(li)
 
    for i in range(0,n):
        for j in range(i+1,n):
            if li[i]+li[j]==target:
                return i,j
            
List = [1,2,5,4]
target = 3
brute_force(List,target)
在这里插入图片描述
在这里插入图片描述

2、B-树

二叉排序树和平衡二叉树的查找方法均适用于存储在计算机内存中较小的文件,统称为内查找法。若文件很大且存放与外存进行查找时,这些查找方法就不适用了。内查找法都以结点为单位进行查找,这样需要反复进行内、外存的交换,是很费时的。因此,提出了一种适用于外查找的平衡多叉树——B-树,磁盘管理系统中的目录管理,以及数据库系统中的索引组织多数都采用B-树这种数据结构。

2.1 、B-树的定义

一棵m阶的B-树,或为空树,或为满足下列特性的m叉树:   (1)树中每个结点至多有m棵子树;   (2)若根结点不是叶子结点,则至少有两棵子树;   (3)除根之外的所有非终端结点至少有[m/2]棵子树   (4)所有的叶子结点都出现在同一层次上,并且不带信息,通常称为失败结点(失败结点并不存在,指向这些结点的指针为空。引入失败结点是为了便于分析B-树的查找性能);   (5)所有的非终端结点最多有m-1个关键字,结点的结构如下图所示。

Image Name
Image Name

B-树具有平衡、有序、多路的特点,下图所示为一棵四阶的B-树,能很好地说明其特点。

Image Name
Image Name

(1)所有叶子结点均在同一层次,这体现出其平衡的特点。   (2)树中每个结点中的关键字都是有序的,且关键字Ki “左子树”中的关键字均小于Ki,而其“右子树”中的关键字均大于Ki,这体现出其有序的特点。   (3)除叶子结点外,有的结点中有一个关键字,两棵子树,有的结点中有两个关键字,三颗子树。这种4阶的B-树最多有三个关键字,四棵子树,这体现出其多路的特点。   在具体实现时,为记录其双亲结点,B-树结点的存储结构通常增加一个parent指针,指向其双亲结点,存储结构示意图如下图所示。

Image Name
Image Name

2.2 B-树的查找

由B-树的定义可知,在B-树上进行查找的过程和二叉排序树的查找类似,可以看成二叉排序树的扩展,知识二叉排序树是二路查找,B-树是多路查找。在B-树查找时,结点内进行查找的时候除了顺序查找之外,还可以用二分查找来提高效率。 例如,上述展示的4阶的B-树查找关键字47的过程如下:首先从根开始,根据根结点指针 t 找到 *a 结点,因 *a结点中只有一个关键字,且47>35,若查找的记录存在,则必在指针 P1 所指的子树内,顺指针找到 *c结点,该结点有两个关键字(43和78),而43<47<78,若查找的记录存在,则必在指针P1所指的子树中。同样,顺指针找到 *g 结点,在该结点中顺序查找,查找到关键字47,由此,查找成功。 查找不成功的过程也类似,例如,在同一棵树中查找23。从根开始,因为23<35,则顺该结点中指针 Po 找到 *b 结点,又因为 *b 结点中只有一个关键字18,且23>18,所以顺结点中第二个指针 P1 找到 *e 结点。同理,因为23<27,则顺指针往下找,此时因指针所指为叶子结点,说明此棵B-树中不存在关键字23,查找因失败而告终。 由此可见,在B-树上进行查找的过程是一个顺指针查找结点,和在结点的关键字中查找交叉进行的过程。

在B-树上进行查找包含两种基本操作:(1)在B-树中找结点;(2)在结点中找关键字。

2.3 B-树的插入

B-树是动态查找树,因此其生成过程是从空树起,在查找的过程中通过逐个插入关键字而得到。但由于B-树中除根之外的所有非终端结点中的关键字个数必须大于等于[m/2]-1,因此,每次插入一个关键字不是在树中添加一个叶子结点,而是首先在最底层的某个非终端结点中添加一个关键字,若该结点的关键字个数不超过m-1,则插入完成,否则表明结点已满,要产生结点的“分裂”,将此结点在同一层分成两个结点。一般情况下,结点分裂方法是:以中间关键字为界把结点一分为二,成为两个结点,并把中间关键字向上插入到双亲结点上,若双亲结点已满,则采用同样的方法继续分解。最坏的情况下,一直分解到树根结点,这时B-树高度增加1。   例如,下图中(a)所示为3阶的B-树(图中省去F结点即叶子结点),假设需要依次插入的关键字30、26、85和7。首先通过查找确定应插入的位置。   由根*a 起进行查找,确定30应插入在*d 结点中,由于*d 中关键字数目不超过2即(m-1),故第一个关键字插入完成。插入30后的B-树如图(b)所示。   同样,通过查找确定关键字26亦应插入在*d 结点中。由于*d 中关键字的数目超过2,此时需要将*d分裂成两个结点,关键字26及其前、后两个指针仍保留在*d结点中,而关键字37及其前、后两个指针存储到新产生的结点 *d’ 中。同时,将关键字30和指示结点 *d’ 的指针插入到其双亲结点中。由于*b结点中的关键字数目没有超过2,则插入完成。插入后B-树如图(d)所示。   类似地,在*g中插入85之后需要分裂成两个结点,而当70继而插入到双亲结点中时,由于*e中关键字数目超过2,则再次分裂为结点*e 和*e’,如图(g)所示。   最后在插入关键字7时,*c、*b和*a相继分裂,并生成一个新的根结点*m,如图(h)~(j)所示。

Image Name
Image Name
Image Name
Image Name
Image Name
Image Name
Image Name
Image Name

2.4 B-树的删除

m阶B-树的删除操作是在B-树的某个结点中删除制定的关键字及其邻近的一个指针,删除后应进行调整使该树仍然满足B-树的定义,也就是要保证每个结点的关键字数目范围为[[m/2]-1,m]。删除记录后,结点的关键字个数如果小于[m/2]-1,则要进行“合并”结点的操作。除了删除记录,还要删除该记录邻近的指针。

  • 若该结点为最下层的非终端结点,由于其指针均为空,删除后不会影响其他结点,可直接删除;
  • 若该结点不是最下层的非终端结点,邻近的指针则指向一棵子树,不可直接删除。此时可做如下处理:将要删除记录用其右(左)边邻近指针指向的子树中关键字最小(大)的记录(该记录必定在最下层的非终端结点中)替换。采用这种方法进行处理,无论要删除的记录所在的结点是否为最下层的非终端结点,都可归结为在最下层的非终端结点中删除记录的情况。   例如,在下图所示的B-树上删去45,可以用*f结点中的50替代45,然后在*f结点中删去50。因此,下面可以只讨论删除最下层非终端结点中的关键字的情形。以下有3种可能:
Image Name
Image Name
  • (1)被删关键字所在结点中的关键字数目不小于[m/2],则只需从该结点中删去该关键字Ki和相应指针Pi,树的其他部分不变。例如,从上图所示B-树中删去关键字12,删除后的B-树如图(a)所示。
Image Name
Image Name
  • (2)被删关键字所在结点中的关键字数目等于[m/2]-1,而与该结点相邻的右兄弟(或左兄弟)结点中的关键字数目大于[m/2]-1,则需将其兄弟结点中的最小(或最大)的关键字上移至双亲结点中,而将双亲结点中小于(或大于)且紧靠该上移关键字的关键字下移至被删关键字所在结点中。例如,从上图(a)中删去50,需将其右兄弟结点中的61上移至*e结点中,而将*e结点中的53移至*f,从而使*f和*g中关键字数目均不小于[m/2]-1,而双亲结点中的关键字数目不变,如图(b)所示。
Image Name
Image Name
  • (3)被删关键字所在结点和其相邻的兄弟结点中的关键字数目均等于[m/2]-1。假设该结点有右兄弟,且右兄弟结点地址由双亲结点中的指针Pi所指,则在删去关键字之后,它所在结点中剩余的关键字和指针,加上双亲结点中的关键字Ki一起,合并到Pi所指兄弟结点中(若没有右兄弟,则合并至左兄弟结点中)。例如,从上图(b)中删去53,则应删去*f结点,并将*f的剩余信息(指针“空”)和双亲*e结点中的61一起合并到右兄弟结点*g中,删除后的树如图(c)所示。
Image Name
Image Name
  • (4)如果因此使双亲结点中关键字数目小于[m/2]-1,则依次类推做相应处理。例如,在图(c)的B-树中删去关键字37之后,双亲*b结点中剩余信息(指针c)应和其双亲*a结点中关键字45一起合并至右兄弟结点*e中,删除后的B-树如图(d)所示。
Image Name
Image Name

大作业四:完成B-树的操作

构建一个B-树的结点类和一个B-树

  • 实现查找操作
  • 实现插入操作
  • 实现删除操作

最后输出结果要求:   测试列表为[45, 12, 53, 70, 3, 24, 37, 50, 61, 90, 100],生成的B-树为:

Image Name
Image Name

  输出形式不限,参考格式为:

Image Name
Image Name

代码思路:(仅供参考,思路不限)

查找操作:将给定值key与根结点的各个关键字K1,K2,…,Kj(1<= j <= m-1)进行比较,由于该关键字序列是有序的,所以查找时可采用顺序查找,也可采用折半查找。查找时: (1)若key = Ki(1<= i <=j),则查找成功; (2)若key < K1,则顺着指针Po所指向的字数继续向下查找; (3)若Ki < key < Ki+1(1<=i<=j-1),则顺着指针Pi所指向的子树继续向下查找; (4)若key > Kj,则顺着指针Pj所指向的子树继续向下查找。 如果再自上而下的查找过程中,找到了值为key的关键字,则查找成功;如果直到叶子结点也未找到,则查找失败。

插入操作: (1)在B-树中查找给定关键字的记录,若查找成功,则插入操作失败;否则将新纪录作为空指针ap插入到查找失败的叶子结点的上一层结点(由q指向)中。 (2)若插入新纪录和空指针后,q指向的结点的关键字个数未超过m-1,则插入操作成功,否则转入步骤(3). (3)以该结点的第[m/2]个关键字K[m/2]为拆分点,将该结点分成3个部分:K[m/2]左边部分、K[m/2]、K[m/2]右边部分。K[m/2]部分仍然保留在原结点中;K[m/2]右边部分存放在一个新创建的结点(由ap指向)中;关键字值为K[m/2]的记录和指针ap插入到q的双亲结点中。因q的双亲结点增加一个新的记录,所以必须对q的双亲结点重复(2)和(3)的操作,依次类推,直至由q指向的结点是根结点,转入步骤(4)。 (4)由于根结点无双亲,则由其分裂产生的两个结点的指针ap和q,以及关键字为K[m/2]的记录构成一个新的根结点。此时,B-树的高度增加1。

删除操作: (1)删除结点在叶子结点上

  • 结点内的关键字个数大于d-1,可以直接删除(大于关键字个数下限,删除不影响 B - 树特性)
  • 结点内的关键字个数等于d-1(等于关键字个数下限,删除后将破坏 特性),此时需观察该节点左右兄弟结点的关键字个数: a. 旋转: 如果其左右兄弟结点中存在关键字个数大于d-1 的结点,则从关键字个数大于 d-1 的兄弟结点中借关键字:(这里看了网上的很多说法, 都是在介绍关键字的操作,而没有提到孩子结点. 我实现的时候想了很久才想出来: 借关键字时, 比如从右兄弟借一个关键字(第一个), 此时即为左旋, 将父亲结点对应关键字移到当前结点, 再将右兄弟的移动父亲结点(因为要满足排序性质, 类似二叉树的选择) 然后进行孩子操作, 将右兄弟的 插入到 当前结点的孩子指针末尾) 左兄弟类似, 而且要注意到边界条件, 比如当前结点是第0个/最后一个孩子, 则没有 左兄弟/右兄弟)

b. 合并: 如果其左右兄弟结点中不存在关键字个数大于 t-1 的结点,进行结点合并:将其父结点中的关键字拿到下一层,与该节点的左右兄弟结点的所有关键字合并,同样要注意到边界条件, 比如当前结点是第0个/最后一个孩子, 则没有 左兄弟/右兄弟 自底向上地检查来到这个叶子结点的路径上的结点是否满足关键字数目的要求, 只要关键字少于d-1,则进行旋转(2a)或者合并(2b)操作

(2)删除结点在非叶子结点上 查到到该结点, 然后转化成 上述 叶子结点中情况转化过程: a. 找到相邻关键字:即需删除关键字的左子树中的最大关键字或右子树中的最小关键字 b. 用相邻关键字来覆盖需删除的非叶子节点关键字,再删除原相邻关键字(在;叶子上,这即为上述情况)。

from collections import deque
import math

m = 3
# m = 4

class MbtNode:
    def __init__(self):
        self.parent = None
        self.key_num = 0
        self.keys = deque()
        self.sub_trees = deque()

        # keys中keys[0]不会使用,keys[1]到keys[m-1]用于存储m-1个关键字,keys[m]用于插入第m个时结点会进行分裂,
        # sub_trees[0]-sub_trees[m-1]用于存储m个子树,sub_trees[m]用于存储第m个时结点会进行分裂,
        for i in range(m+1):
            self.keys.append(None)
            self.sub_trees.append(None)
        self.info = None


class MbTree:
    def __init__(self):
        self.root = None


def search(mbt_node: MbtNode, key) -> int:
    """
    在结点mbt_node中,寻找小于等于key的最大关键字序号

    :param mbt_node: 在bmt_node中查找关键字key
    :param key: 所查找关键字
    :return: 返回key在mbt_node的keys中的所在位置或应插位置
    """
    key_num = mbt_node.key_num
    i = 1
    while i <= key_num and mbt_node.keys[i] <= key:
        i += 1
    return i-1  # 返回key在mbt_node的keys中的所在位置或应插位置


def search_mb_tree(mb_tree: MbTree, key):
    """
    在bm_tree的B树中查找关键字为key的结点,若查找成功,则将(所在结点、所在结点中的位置、True)返回;否则
    将(key应插入的结点,插入结点的插入位置,False)返回

    :param mb_tree: 查找的B树
    :param key: 所查找的关键字
    :return: 成功返回(所在结点、所在结点中的位置、True),失败返回(key应插入的结点,插入结点的插入位置,False)
    """
    p = mb_tree.root
    fp = None  # p的双亲结点,当p为空时,fp就是key应插入的结点
    i = 0  # 成功时i为key在所在结点中的位置,失败时为key应插入结点的插入位置
    found = False  # 表示是否找到key所在的结点
    while p and not found:
        # 退出循环时有两种情况
        # (1) p为None时表示树中没有结点的keys中包含key
        # (2) found为True时表示在树中找到key所在结点
        i = search(p, key)  # 查找key在p结点中的所在位置或应插位置
        if p.keys[i] == key:
            # 表示已找到key所在结点,需要退出循环
            found = True
        else:
            # 表示为找到应到p.sub_trees[i]中去继续查找key
            fp = p
            p = p.sub_trees[i]
    if found:
        return p, i, True  # 成功返回(所在结点、所在结点中的位置、True)
    else:
        return fp, i, False  # 失败返回(key应插入的结点,插入结点的插入位置,False)


def insert(mbp: MbtNode, ipos: int, key, rp: MbtNode):
    """
    在mbp结点的keys[ipos+1]处插入关键字key,sub_trees[ipos+1]处插入子结点rp
    :param mbp:
    :param ipos:
    :param key:
    :param rp:
    :return: None
    """
    mbp.keys.insert(ipos+1, key)
    mbp.keys.pop()
    mbp.sub_trees.insert(ipos+1, rp)
    mbp.sub_trees.pop()
    mbp.key_num += 1


def split(oldp: MbtNode):
    """
    对oldp结点进行分裂

    :param oldp: 所需分裂的旧结点
    :return: # 返回根据旧结点右半部分所创建的新结点
    """
    s = math.ceil(m/2)  # 获取oldp的⌈m/2⌉的位置
    n = m-s  # 计算oldp的右半部分的key的个数
    newp = MbtNode()  # 创建新结点
    newp.parent = oldp.parent  # 新结点的双亲为旧结点的双亲
    newp.key_num = n  # 新结点的key的个数
    if oldp.sub_trees[s]:
        newp.sub_trees[0] = oldp.sub_trees[s]  # 新结点的第0个子结点为oldp的第s个子结点
        oldp.sub_trees[s] = None
        newp.sub_trees[0].parent = newp  # 将新结点的第一个子结点的双亲结点改为新结点
    for i in range(1, n+1):
        # 为新结点的keys和sub_trees赋值,新结点从下标为1处开始,旧结点从下标为s+1处开始
        newp.keys[i] = oldp.keys[s+i]
        oldp.keys[s + i] = None  # 将旧结点的keys从s+1处变为None
        if oldp.sub_trees[s+i]:
            newp.sub_trees[i] = oldp.sub_trees[s+i]
            oldp.sub_trees[s + i] = None  # 将旧结点的sub_trees从s+1处变为None
            newp.sub_trees[i].parent = newp  # 将新结点的子结点的双亲结点改为新结点

    oldp.keys[s] = None  # 将旧结点的keys[s]变为None,keys[s]处的值会插入到旧结点和新结点的双亲结点中
    oldp.key_num = s - 1  # 旧结点的key的个数变为⌈m/2⌉-1,而此时旧结点的子结点个数变为⌈m/2⌉
    return newp  # 返回新创建的结点


def ins_mbtree(mb_tree: MbTree, key, q: MbtNode, i):
    """
    在m阶mb_tree树的q结点的i位置插入关键字key

    算法思想:
            如果mb_tree为None,则生成初始根(此时q=None, i=);否则q指向某个最下层非终端结点,key应插在该结点
        中q.keys[i+1]处,插入后如果q.key_num > m-1,则进行分裂处理

    :param mb_tree: 已创建好的B树
    :param key: 插入的关键字
    :param q: 关键字所插入的结点
    :param i: 关键字在所插入结点中的位置
    :return: 关键字已插入进去的B树
    """
    if not mb_tree.root:
        # 所创建好的的mb_tree是一棵空树
        mb_tree.root = MbtNode()
        mb_tree.root.key_num = 1
        mb_tree.root.keys[1] = key
    else:
        # 所创建好的的mb_tree是一棵非空树
        x = key  # 将x插入到q.keys[i+1]处
        ap = None  # 将ap插入到q.sub_trees[i+1]处
        finished = False  # 表示关键字插入过程未完成
        while q and not finished:
            # 退出while循环有两种情况
            # (1) q为None表示已经分裂到根,退出while后需创建新根;
            # (2) finished为True表示分裂已完成,此时并未分裂到根,退出while后不需要创建新根。
            insert(q, i, x, ap)  # 在q结点的keys的下标为i+1位置插入x,sub_trees的下标为i+1位置插入ap
            if q.key_num < m:  # 判断关键字是否插入完成
                # 表示关键字插入过程完成
                finished = True  # 插入完成时退出循环,此时并未分裂到根
            else:
                # 表示关键字插入过程完成,需要分裂结点q
                s = math.ceil(m/2)  # 获取q的⌈m/2⌉的位置
                x = q.keys[s]  # 获取q的keys的⌈m/2⌉处元素
                q.keys[s] = None
                ap = split(q)  # 对q结点进行分裂,并获取根据q的右半部分所创建的新结点
                q = q.parent  # 将q结点重新设置为其双亲结点
                if q:  # 若双亲结点存在,则搜索关键字x在双亲结点中的应插入的下标值
                    i = search(q, x)

        if not finished:
            # 表示根结点要分裂,并产生新根

            # 对创建新根结点并对其进行赋值操作
            new_root = MbtNode()
            new_root.key_num = 1
            new_root.keys[1] = x
            new_root.sub_trees[0] = mb_tree.root
            new_root.sub_trees[1] = ap

            # 为新根的子结点设置双亲
            mb_tree.root.parent = new_root
            ap.parent = new_root

            # 将mb_tree根结点设置为新创建的新根结点
            mb_tree.root = new_root
    return mb_tree  # 返回关键字已插入进去的B树


def create_mb_tree(mb_tree: MbTree, key_list: deque):
    """
    创建一棵B树

    :param mb_tree: 创建好的一棵空树
    :param key_list: 关键字列表
    :return: 创建好的一棵B树
    """
    for key in key_list:
        q, i, _ = search_mb_tree(mb_tree, key)  # 寻找关键字插入结点q与在结点中得位置i
        mb_tree = ins_mbtree(mb_tree, key, q, i)  # 在mb_tree树的q结点的i位置插入关键字key
    return mb_tree  # 返回创建好的一棵B树


def is_bottom(mb_tree: MbTree, key):
    p, i, success = search_mb_tree(mb_tree, key)
    if success:  # 判断mb_tree中是否存在包含关键字key的结点
        # mb_tree中存在包含关键字key的结点
        if p.sub_trees[0]:  # 判断关键字key的所在结点是否是最底层结点
            # 关键字key的所在结点不是最底层结点
            is_bottom_ = False
        else:
            # 关键字key的所在结点是最底层结点
            is_bottom_ = True
    else:
        # mb_tree中不存在包含关键字key的结点
        is_bottom_ = p = i = None
    return is_bottom_, p, i


def del_bottom(mb_tree: MbTree, key, p: MbtNode, i):
    """
    删除最底层结点中的关键字

    :param mb_tree: B树
    :param key: 所需删除关键字
    :param p: 所需删除关键字所在结点
    :param i: 所需删除关键字在所在结点中的位置
    :return: 删除关键字后的B树
    """
    s = math.ceil(m/2)
    if p.key_num > s - 1:  # 判断p中的关键字数是否大于⌈m/2⌉-1 或 p结点是否是根结点
        # p中的关键字数是否大于⌈m/2⌉-1 或 p结点是根结点
        del p.keys[i]  # 删除关键字key
        p.keys.append(None)  # 为保证 p.keys长度为m+1
        p.key_num -= 1  # p结点的关键字字数减1
    else:
        # p中的关键字数不大于⌈m/2⌉-1
        p_parent = p.parent  # 获取p的双亲结点
        j = search(p_parent, key)  # 获取key所在结点在双亲结点中的应插位置j,j也是key所在结点p在p_parent.sub_trees中的下标,
        p_left_sibling = p_parent.sub_trees[j-1]
        p_right_sibling = p_parent.sub_trees[j+1]
        if j > 0 and p_left_sibling.key_num > s - 1:
            # p的左兄弟结点关键字个数大于⌈m/2⌉-1,当j==0时,p没有左兄弟,不能使用该部分代码
            del p.keys[i]  # 删除关键字key
            p.keys.insert(1, p_parent.keys[j])  # 将p_parent.keys[j]插入p.keys的开始位置
            p_parent.keys[j] = p_left_sibling.keys[p_left_sibling.key_num]  # 将key所在结点p的左兄弟结点的最后一个关键字赋值给key所在结点p的双亲结点的第j个关键字处,保持中序
            del p_left_sibling.keys[p_left_sibling.key_num]  # 删除p_left_sibling.keys[p_left_sibling.key_num]的最后一个关键字删除
            p_left_sibling.keys.append(None)  # 保证p_left_sibling.keys的长度为m+1
            p_left_sibling.key_num -= 1  # 将key所在结点p的左兄弟结点的关键字个数减1
        elif j < p_parent.key_num and p_right_sibling.key_num > s - 1:
            # p的右兄弟结点关键字个数大于⌈m/2⌉-1,当j==p_parent.key_num时p没有右兄弟,不能使用该部分代码
            del p.keys[i]  # 删除关键字key
            p.keys.insert(p.key_num, p_parent.keys[j])  # 将key所在结点p的双亲结点的第j个关键字添加到key所在关键字结点的最后,保持中序
            p_parent.keys[j] = p_right_sibling.keys[1]  # 将key所在结点p的右兄弟结点的第一个关键字赋值给key所在结点p的双亲结点的第j个关键字处,保持中序
            del p_right_sibling.keys[1]  # 删除_right_sibling.keys的第一个关键字删除
            p_right_sibling.keys.append(None)  # 保证p_right_sibling.keys的长度为m+1
            p_right_sibling.key_num -= 1  # 将key所在结点p的右兄弟结点的关键字个数减1
        else:
            # p的左右兄弟结点关键字个数都不大于⌈m/2⌉-1
            del p.keys[i]  # 删除p中的keys中的第i个关键字
            p.keys.append(None)  # 保持p.keys的长度为m+1
            p.key_num -= 1  # p的关键字个数减1
            while p.parent:
                # 表示当前结点p已经为根结点退出循环
                p_parent = p.parent  # 获取p结点的双亲结点
                j = search(p_parent, key)  # 在p的双亲结点中搜索应插位置
                p_left_sibling = p_parent.sub_trees[j - 1]  # 获取当前结点的左兄弟结点
                p_right_sibling = p_parent.sub_trees[j + 1]  # 获取当前结点的右兄弟结点
                if j > 0:
                    # 当j==0时,p没有左兄弟,不能使用该部分代码
                    p.keys.insert(1, p_parent.keys[j])  # 将p_parent.keys[j]插入p的关键字的第一个位置
                    p.keys.pop()  # 为保证 p.keys长度为m+1
                    p.key_num += 1  # p的关键字个数加1
                    for k in range(1, p.key_num+1):  # 将p中的关键字及子树合并到其左兄弟中,放到左兄弟的最后
                        p_left_sibling.keys[p_left_sibling.key_num+k] = p.keys[k]  # 将p.keys值依次插入p_left_sibling.keys尾部
                        p_left_sibling.sub_trees[p_left_sibling.key_num+k] = p.sub_trees[k]  # psub_trees的第0个已为空,从第p.key_num个开始
                    p_left_sibling.key_num += p.key_num  # p的左兄弟关键字个数需再加上p的关键字个数
                    del p_parent.keys[j]  # 删除p的双亲结点中关键字p_parent.keys[j]
                    p_parent.keys.append(None)  # 为保证 p_parent.keys长度为m+1
                    p_parent.key_num -= 1  # p的双亲结点个数减1
                    del p_parent.sub_trees[j]  # 从p的双亲结点中删除p结点
                    p_parent.sub_trees.append(None)  # 为保证 p_parent.sub_trees 长度为m+1
                else:
                    # 当j==p_parent.key_num时p没有右兄弟,不能使用该部分代码
                    p.keys.insert(p.key_num+1, p_parent.keys[j+1])  # 将p_parent.keys[j+1]插入p的最后一个位置
                    p.keys.pop()  # 为保证 p.keys长度为m+1
                    p.key_num += 1  # p的关键字个数加1
                    for k in range(p.key_num, 0, -1):  # # 将p中的关键字及子树合并到其右兄弟中,放到右兄弟的最开始
                        p_right_sibling.keys.insert(1, p.keys[k])  # 将p.keys值依次插入p_right_sibling.keys的第1个位置
                        p_right_sibling.keys.pop()  # 为保证 p_right_sibling.keys长度为m+1
                        p_right_sibling.sub_trees.insert(0, p.sub_trees[k-1])  # p.sub_trees第p.key_num个已删除从第p.key_num-1个开始
                        p_right_sibling.sub_trees.pop()  # 为保证 p_right_sibling.sub_trees长度为m+1
                    del p_parent.keys[j+1]  # 删除p的双亲结点中关键字p_parent.keys[j+1]
                    p_parent.keys.append(None)  # 为保证 p_parent.keys长度为m+1
                    p_parent.key_num -= 1  # p的双亲结点个数减1
                    del p_parent.sub_trees[j]  # 从p的双亲结点中删除p结点
                    p_parent.sub_trees.append(None)  # 为保证 p_parent.sub_trees 长度为m+1

                if p_parent.key_num >= s - 1:
                    # 当前结点p的关键字数大于等于⌈m / 2⌉-1,结点合并已完成,退出循环
                    break
                p = p.parent
            if not p.parent:  # 判断p结点是否是根结点
                # 表示p是根结点
                if p_left_sibling:
                    # p_left_sibling与p_right_sibling中必有一个不为空作为根结点
                    mb_tree.root = p_left_sibling
                else:
                    mb_tree.root = p_right_sibling
    return mb_tree  # 删除关键字后的B树


def del_non_bottom(mb_tree: MbTree, p: MbtNode, i):
    """
    删除非最下层结点中的关键字

    算法思想:
            (1) 找到所删关键字结点的右子结点的最左下端的结点的第一个关键字替换掉所删关键字,然后转化为删除右子
        结点的最左下端的结点的第一个关键字。
            (2) 找到所删关键字结点的左子结点的最右下端的结点的最后一个关键字替换掉所删关键字,然后转化为删除左
        子结点的最右下端的结点的最后一个关键字替换掉所删关键字。
            以上两种方法都可,此处使用第一种方法,总之,删除非最下层结点中的关键字可转化为删除最下层结点中的关
        键字。

    :param mb_tree: B树
    :param p: 所删关键字所在结点
    :param i: 所删关键字在结点的keys的下标
    :return: 删除关键字后的B树
    """
    q = p.sub_trees[i]
    while q.sub_trees[0]:
        q = q.sub_trees[0]
    p.keys[i] = q.keys[1]
    mb_tree = del_bottom(mb_tree, q.keys[1], q, 1)
    return mb_tree


def del_mb_tree(mb_tree: MbTree, key):
    """
    删除B树中关键字key

    :param mb_tree: B树
    :param key: 所删关键字
    :return: 删除关键字后的B树
    """
    is_bottom_, p, i = is_bottom(mb_tree, key)
    if is_bottom_ is None:  # 判断mb_tree中是否存在包含关键字key的结点
        return -1  # 表示mb_tree中不存在包含关键字key的结点
    if is_bottom_:  # 判断关键字key的所在结点是否是最底层结点
        # 关键字key的所在结点是最底层结点
        mb_tree = del_bottom(mb_tree, key, p, i)
    else:
        # 关键字key的所在结点不是最底层结点
        mb_tree = del_non_bottom(mb_tree, p, i)
    return mb_tree  # 返回删除关键字key以后的mb_tree

def print_tree():
    print(mb_tree.root.keys)
    print(mb_tree.root.sub_trees[0].keys,end=',')
    print(mb_tree.root.sub_trees[1].keys)
    print(mb_tree.root.sub_trees[0].sub_trees[0].keys,end=',')
    print(mb_tree.root.sub_trees[0].sub_trees[1].keys,end=',')
    print(mb_tree.root.sub_trees[1].sub_trees[0].keys,end=',')
    print(mb_tree.root.sub_trees[1].sub_trees[1].keys,end=',')
    print(mb_tree.root.sub_trees[1].sub_trees[2].keys)

mb_tree = MbTree()
mb_tree = create_mb_tree(mb_tree, deque([45, 12, 53, 70, 3, 24, 37, 50, 61, 90, 100]))
print_tree()

print('\n查找 61 ')
q, i, success = search_mb_tree(mb_tree, 61)
print(q.keys, i, success)

print('\n插入 33 ')
key = 33
q, i, _ = search_mb_tree(mb_tree, key)  # 寻找关键字插入结点q与在结点中得位置i
mb_tree = ins_mbtree(mb_tree, key, q, i)  # 在mb_tree树的q结点的i位置插入关键字key
print_tree()

print('\n删除 61 ')
del_mb_tree(mb_tree, 61)
print_tree()
在这里插入图片描述
在这里插入图片描述

3、哈希表

3.1 什么是哈希表

前面讨论的各种结构中,记录在结构中的相对位置是随机的,和记录的关键字之间不存在确定的关系,因此,在结构中查找记录时需要进行一系列和关键字的比较。这一类查找方法建立在“比较”的基础上。理想的情况是希望不经过任何比较,一次存取便能得到所查记录,那就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系 F ,使每个关键字和结构中一个唯一的存储位置相对应。因而在查找时,只要根据这个对应关系 F 找到给定值K得像F(K)。若结构中存在关键字和K 相等的记录,则必定在F(K)的存储位置上,由此,不需要进行比较便可直接取得所查记录。在此,我们称这个对应关系F为哈希函数,按这个思想建立的表为哈希表。   哈希表是一个通过哈希函数来计算数据存储位置的数据结构,通常支持如下操作

  • insert(key,value):插入键值对(key,value)
  • get(key):如果存在键为key的键值对则返回其value,否则返回空值
  • delete(key):删除键为key的键值对

例如,这里有一个电话簿(查找表),电话簿有四个人的联系方式:

Image Name
Image Name

假如想查找李四的电话号码,对于一般的查找方式最先想到的是从头遍历,一一比较。而如果将电话簿构建成一张哈希表,可以直接通过名字“李四”直接找到电话号码在表中的位置。

在构建哈希表时,最重要的是哈希函数的设计。例如设计电话簿案例中的哈希函数为:每个名字的姓的首字母的 ASCII 值即为对应的电话号码的存储位置。这时会发现,张三和赵六两个关键字的姓的首字母都是 Z ,最终求出的电话号码的存储位置相同,这种现象称为冲突。在设计哈希函数时,要尽量地避免冲突现象的发生。

对于哈希表而言,冲突只能尽可能地少,无法完全避免。

3.2 哈希表的构造方法

常用的哈希函数的构造方法有 6 种:直接定址法、数字分析法、平方取中法、折叠法、除留余数法和随机数法。

1、直接定址法:其哈希函数为一次函数,即以下两种形式:

H(key)= key 或者 H(key)=a * key + b   其中 H(key)表示关键字为 key 对应的哈希地址,a 和 b 都为常数。

例如有一个从 1 岁到 100 岁的人口数字统计表,如下表所示:

Image Name
Image Name

假设其哈希函数为第一种形式,其关键字的值表示最终的存储位置。若需要查找年龄为 25 岁的人口数量,将年龄 25 带入哈希函数中,直接求得其对应的哈希地址为 25(求得的哈希地址表示该记录的位置在查找表的第 25 位)。

2、数字分析法:如果关键字由多位字符或者数字组成,就可以考虑抽取其中的 2 位或者多位作为该关键字对应的哈希地址,在取法上尽量选择变化较多的位,避免冲突发生。

例如下表中列举的是一部分关键字,每个关键字都是有 8 位十进制数组成:

Image Name
Image Name

通过分析关键字的构成,很明显可以看到关键字的第 1 位和第 2 位都是固定不变的,而第 3 位不是数字 3 就是 4,最后一位只可能取 2、7 和 5,只有中间的 4 位其取值近似随机,所以为了避免冲突,可以从 4 位中任意选取 2 位作为其哈希地址。

3、平方取中法是对关键字做平方操作,取中间得几位作为哈希地址。此方法也是比较常用的构造哈希函数的方法。

例如关键字序列为{421,423,436},对各个关键字进行平方后的结果为{177241,178929,190096},则可以取中间的两位{72,89,00}作为其哈希地址。

4、折叠法是将关键字分割成位数相同的几部分(最后一部分的位数可以不同),然后取这几部分的叠加和(舍去进位)作为哈希地址。此方法适合关键字位数较多的情况。

例如,在图书馆中图书都是以一个 10 位的十进制数字为关键字进行编号的,若对其查找表建立哈希表时,就可以使用折叠法。

若某书的编号为:0-442-20586-4,分割方式如图 1 中所示,在对其进行折叠时有两种方式:一种是移位折叠,另一种是间界折叠:

  • 移位折叠是将分割后的每一小部分,按照其最低位进行对齐,然后相加,如下图(a);
  • 间界折叠是从一端向另一端沿分割线来回折叠,如下图(b)。
Image Name
Image Name

5、除留余数法:若已知整个哈希表的最大长度 m,可以取一个不大于 m 的数 p,然后对该关键字 key 做取余运算,即:H(key)= key % p。

在此方法中,对于 p 的取值非常重要,由经验得知 p 可以为不大于 m 的质数或者不包含小于 20 的质因数的合数。

6、随机数法:是取关键字的一个随机函数值作为它的哈希地址,即:H(key)=random(key),此方法适用于关键字长度不等的情况。

注意:这里的随机函数其实是伪随机函数,随机函数是即使每次给定的 key 相同,但是 H(key)都是不同;而伪随机函数正好相反,每个 key 都对应的是固定的 H(key)。

如此多的构建哈希函数的方法,在选择的时候,需要根据实际的查找表的情况采取适当的方法。通常考虑的因素有以下几方面:

  • 关键字的长度。如果长度不等,就选用随机数法。如果关键字位数较多,就选用折叠法或者数字分析法;反之如果位数较短,可以考虑平方取中法;
  • 哈希表的大小。如果大小已知,可以选用除留余数法;
  • 关键字的分布情况
  • 查找表的查找频率
  • 计算哈希函数所需的时间(包括硬件指令的因素)

3.3处理冲突的办法

对于哈希表的建立,需要选取合适的哈希函数,但是对于无法避免的冲突,需要采取适当的措施去处理。通常用的处理冲突的方法有以下几种:

1、开放定址法   H(key)=(H(key)+ d)MOD m(其中 m 为哈希表的表长,d 为一个增量) 当得出的哈希地址产生冲突时,选取以下 3 种方法中的一种获取 d 的值,然后继续计算,直到计算出的哈希地址不在冲突为止,这 3 种方法为:   -线性探测法:d=1,2,3,…,m-1   -二次探测法:d=12,-12,22,-22,32,…   -伪随机数探测法:d=伪随机数   例如,在长度为 11 的哈希表中已填写好 17、60 和 29 这 3 个数据(如下图(a) 所示),其中采用的哈希函数为:H(key)=key MOD 11,现有第 4 个数据 38 ,当通过哈希函数求得的哈希地址为 5,与 60 冲突,则分别采用以上 3 种方式求得插入位置如下图(b)所示:

Image Name
Image Name

** 注释**:在线性探测法中,当遇到冲突时,从发生冲突位置起,每次 +1,向右探测,直到有空闲的位置为止;二次探测法中,从发生冲突的位置起,按照 +12,-12,+22,…如此探测,直到有空闲的位置;伪随机探测,每次加上一个随机数,直到探测到空闲位置结束。

2、链地址法   基本思想是:将所有产生冲突的关键字所对应的数据全部存储在同一个线性链表中。例如有一组关键字为{19,14,23,01,68,20,84,27,55,11,10,79},其哈希函数为:H(key)=key MOD 13,使用链地址法所构建的哈希表如下图所示:

Image Name
Image Name

大作业五:完成哈希表操作

操作1:   构造一个链表类,实现以下操作:

  • 使链表支持迭代功能(即可链表支持for循环操作)
  • 实现python中append函数,向链表中尾插一个元素
  • 实现python中extend函数,向链表中插入一个列表
  • 实现查找find函数,存在返回True,不存在返回False

操作2:   构造一个哈希表类,使用链地址法处理冲突,实现以下操作:

  • 定义一个哈希函数
  • 插入一个元素
  • 查找一个元素

最后输出结果要求:

需要将哈希表中插入元素之后的n个单链表打印出来。

代码思路: (仅供参考,思路不限)   这边有两个操作,但其实操作1是为了给操作2创造了链表的使用条件。

对于操作1来说,我们是为了实现链表支持for循环操作,定义一个链表的类

  • 迭代器的类(嵌套在链表的类中)
  • 链表结点的类(嵌套在链表的类中)
  • append函数:传进一个元素,表示尾插一个元素。创建一个结点,然后将其与尾巴连接起来,其中需要判断一下头结点是否为空,若为空则传进来的元素就是头结点。
  • extend函数:传进一个列表,然后循环调用一下append函数,即可将列表中的元素插入进来。
  • find函数:循环链表自身的数,然后判断是否存在某一个数等于该元素,若存在则查找成功返回True,若不存在则返回False。

操作2,其实哈希表的查找就是哈希表的创建,我们采用链地址法处理冲突,因此我们再创建哈希表类的时候,需要先定义一个空链表来,对于哈希表的size,可以设置默认值,也可以进行传参数来确定。哈希树类包括:

  • 哈希函数的确定:通常采用H(k)= k%size
  • 插入操作:我们通过计算插入的 k 对应的哈希值,来确定其应处于第几个链表,进而将其通过链表的append方法插入该链表中。
  • 查找操作:先计算查找的 k 对应的哈希值,进而定位其处于第几个链表,然后通过链表的find方法来进行查找。
class SignLinklist:

    # 节点类
    class Node:
        def __init__(self, item):
            self.item = item
            self.next = None

        def __str__(self):
            return str(self.item)

    # 可迭代链表类
    class LinklistIterator:
        def __init__(self, node):
            self.node = node

        def __next__(self):
            if self.node:
                cur_node = self.node
                self.node = cur_node.next
                return cur_node.item
            else:
                raise StopIteration

        def __iter__(self):
            return self

    def __init__(self, iterable=None):
        self.head = None
        self.tail = None
        if iterable:
            self.extend(iterable)

    # 添加节点
    def append(self, obj):
        node = SignLinklist.Node(obj)
        if not self.head:
            self.head = node
            self.tail = node
        else:
            self.tail.next = node
            self.tail = node

    # 批量添加节点
    def extend(self, iterable):
        for obj in iterable:
            self.append(obj)

    # 查找节点
    def find(self, obj):
        for n in self:
            if n == obj:
                return True
        else:
            return False

    # 遍历链表
    def __iter__(self):
        return self.LinklistIterator(self.head)

    # print 调用打印链表
    def __repr__(self):
        return '<<' + ','.join(map(str, self)) + '>>'


# 哈希表
class HashTable:

    def __init__(self, size=10):
        self.size = size
        self.T = [SignLinklist() for x in range(self.size)]

    def h(self, k):   # hash函数
        return k % self.size

    def insert(self, k):
        i = self.h(k)
        if self.find(k):
            print('Duplicated Insert')
        else:
            self.T[i].append(k)

    def find(self, k):
        i = self.h(k)
        return self.T[i].find(k)


if __name__ == '__main__':
    ht = HashTable()
    ht.insert(10)
    ht.insert(110)
    ht.insert(210)
    ht.insert(310)
    ht.insert(12)
    ht.insert(123)
    ht.insert(64)
    ht.insert(97)
    ht.insert(78)
    ht.insert(56)
    ht.insert(31)
    ht.insert(35)
    ht.insert(68)
    print('\n'.join(map(str, ht.T)),'\n')

    print(ht.find(210))
    print(ht.find(46))
在这里插入图片描述
在这里插入图片描述
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2021-09-19 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 数据结构之查找
  • 1、线性表的查找
    • 1.1 顺序查找
      • 1.2 折半查找
        • 1.3 分块查找
        • 大作业一:实现简单查找
        • 大作业二:完成排序
        • 大作业三:查找目标值
        • 2、B-树
          • 2.1 、B-树的定义
            • 2.2 B-树的查找
              • 2.3 B-树的插入
                • 2.4 B-树的删除
                • 大作业四:完成B-树的操作
                • 3、哈希表
                  • 3.1 什么是哈希表
                    • 3.2 哈希表的构造方法
                      • 3.3处理冲突的办法
                      • 大作业五:完成哈希表操作
                      相关产品与服务
                      数据保险箱
                      数据保险箱(Cloud Data Coffer Service,CDCS)为您提供更高安全系数的企业核心数据存储服务。您可以通过自定义过期天数的方法删除数据,避免误删带来的损害,还可以将数据跨地域存储,防止一些不可抗因素导致的数据丢失。数据保险箱支持通过控制台、API 等多样化方式快速简单接入,实现海量数据的存储管理。您可以使用数据保险箱对文件数据进行上传、下载,最终实现数据的安全存储和提取。
                      领券
                      问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档