老师，你写的find_key方法还有bug。

1. 在获取一个未设置的key时，运行结果可能显示None类型没有属性key

2. 在获取一个未设置的key时，可能陷入死循环

我修改后的代码如下：

class Array():
    def __init__(self,size=4):
        self.__size = size # 记录容器大小
        self.__item = [None]*size #分配空间
        self.__length = 0

    def __setitem__(self,key,value):
        self.__item[key] = value
        self.__length += 1

    def __getitem__(self,key):
        return self.__item[key]
    
    def __len__(self):
        return self.__length
    
    def __iter__(self):
        for value in self.__item:
            yield value


class Slot():
    def __init__(self,key=None,value=None):
        self.key = key
        self.value = value
    
    def __str__(self):
        return 'key:{},value:{}'.format(self.key,self.value)
    
class HashTable():
    def __init__(self,size=4):
        self.size = size # 用来记录空间大小
        self.item = Array(self.size)
        self.length = 0 # 用来记录元素的个数
    
    def get_index(self,key):
        return hash(key) % self.size
    
    def find_index_to_insert(self,key):
        index = self.get_index(key) # 获取key对应的索引
        if self.item[index] == None: # 索引没被占用
            return index
        else:
            while self.item[index] is not None:
                if key == self.item[index].key: # 获取到相同的key
                    return index
                else:
                    index = (index*5+1) % self.size
            return index

    def push(self,key,value): # 存放数据
        index = self.find_index_to_insert(key)  # 获取key对应的索引
        self.item[index] = Slot(key,value)
        self.length += 1

    def find_key(self,key):  
        index = self.get_index(key) # 获取key对应的索引
        if self.item[index] == None:
            return None
        else:
            count = 0
            while self.item is not None: # 这里不能写成self.item[index] is not None
                # 判断查找的Key是否与item里的key相同，注意防止self.item[index]为空,否则报None类型没有属性key的错误
                if self.item[index] is not None and key == self.item[index].key:
                    return index
                else:
                    index = (index*5+1) % self.size
                    count += 1
                while count > self.size**self.length: # 解决死循环的问题
                    return None
            return None
    
    def get(self,key): # 获取数据
        index = self.find_key(key) # 获取key对应的索引
        if index is not None:
            return self.item[index]
        return None
    
if __name__ == "__main__":
    h = HashTable()
    h.push('name','吕布')
    h.push('sex1','男')
    h.push('sex2','女')
    h.push('sex3','保密')

    print(h.get('name'))
    print(h.get('sex3'))
    print(h.get('sex2'))
    print(h.get('sex1'))
    print(h.get('age'))  # 这里要解决陷入死循环的问题

老师，我是照着你的代码的逻辑写的，为什么你的运行没出问题，我的运行出问题了，麻烦帮忙看下，谢谢！

class Array():
    def __init__(self,size=4):
        self.__size = size # 记录容器大小
        self.__item = [None]*size #分配空间
        self.__length = 0

    def __setitem__(self,key,value):
        self.__item[key] = value
        self.__length += 1

    def __getitem__(self,key):
        return self.__item[key]
    
    def __len__(self):
        return self.__length
    
    def __iter__(self):
        for value in self.__item:
            yield value


class Slot():
    def __init__(self,key=None,value=None,next=None):
        self.key = key
        self.value = value
        self.next = next
    
    def __str__(self):
        return 'key:{},value:{}'.format(self.key,self.value)
    
class HashTable():
    def __init__(self,size=4):
        self.size = size
        self.item = Array(self.size)
    
    def get_index(self,key):
        return hash(key) % self.size
    
    def push(self,key,value): # 存放数据
        s = Slot(key,value)
        index = self.get_index(key)  # # 获取默认的索引位置
        if self.item[index] == None: # 索引位置是空的
            self.item[index] = s
        else: # 索引位置是非空的
            if self.item[index].key == key: # 所占空间的数据的key 与 传入数据 key 相同
                self.item[index].value = value 
            else: # 所占空间的数据的key 与 传入数据 key 不相同
                temp_next = self.item[index].next # 记录下一个节点
                while temp_next is not None:
                    if temp_next.key == key:
                        temp_next.value = value # 更新原来节点的数据
                        return
                    temp_next = temp_next.next # 继续往下移动一个节点
                temp_next = s
    
    def get(self,key): # 获取数据
        index = self.get_index(key) # 获取key对应的索引
        if self.item[index]: # 索引位置不为空
            if self.item[index].key == key:  # 索引位置的key 与 传入数据 key 相同
                return self.item[index].value # 获取索引位置的key对应的value
            else:
                temp_next = self.item[index].next # 记录下一个节点
                while temp_next is not None: # 下一个节点不为空
                    if temp_next.key == key:
                        return temp_next.value # 找到则获取
                    temp_next = temp_next.next  # 未找到则继续往下移动一个节点
                return None
        return None

if __name__ == "__main__":
    h = HashTable()
    h.push('name','吕布')
    h.push('sex1','男')
    h.push('sex2','女')
    h.push('sex3','保密')

    print(h.get('name'))
    print(h.get('sex3'))
    print(h.get('sex2'))
    print(h.get('sex1'))
    # print(h.get('age'))

运行截图：

老师，我感觉是照着你的代码写的，但是发现运行结果不对，我觉得是find_key方法写的有问题。

class Array():
    def __init__(self,size=4):
        self.__size = size # 记录容器大小
        self.__item = [None]*size #分配空间
        self.__length = 0

    def __setitem__(self,key,value):
        self.__item[key] = value
        self.__length += 1

    def __getitem__(self,key):
        return self.__item[key]
    
    def __len__(self):
        return self.__length
    
    def __iter__(self):
        for value in self.__item:
            yield value


class Slot():
    def __init__(self,key=None,value=None):
        self.key = key
        self.value = value
    
    def __str__(self):
        return 'key:{},value:{}'.format(self.key,self.value)
    
class HashTable():
    def __init__(self,size=4):
        self.size = size
        self.item = Array(self.size)
    
    def get_index(self,key):
        return hash(key) % self.size
    
    def find_index_to_insert(self,key):
        index = self.get_index(key) # 获取key对应的索引
        if self.item[index] == None: # 索引没被占用
            return index
        else:
            while self.item[index] is not None:
                if key == self.item[index].key: # 获取到相同的key
                    return index
                else:
                    index = (index*5+1) % self.size
            return index

    def push(self,key,value): # 存放数据
        index = self.find_index_to_insert(key)  # 获取key对应的索引
        self.item[index] = Slot(key,value)

    def find_key(self,key):
        index = self.get_index(key) # 获取key对应的索引
        if self.item[index] == None:
            return None
        else:
            while self.item is not None:
                if key == self.item[index].key: # 判断查找的Key是否与item里的key相同
                    return index
                else:
                    index = (index*5+1) % self.size
            return None
    
    def get(self,key): # 获取数据
        index = self.find_key(key) # 获取key对应的索引
        if index:
            return self.item[index]
        return None
    
if __name__ == "__main__":
    h = HashTable()
    h.push('name','吕布')
    h.push('sex1','男')
    h.push('sex2','女')
    h.push('sex3','保密')

    print(h.get('name'))
    print(h.get('sex3'))
    print(h.get('sex2'))
    print(h.get('sex1'))
    # print(h.get('age'))

运行结果：

老师您好，我在运行这个程序的时候，有时候会报错但有时候又是好的，不知道是个什么情况……

程序：

class Array:
    def __init__(self, size=4):
        self.__size = size
        self.__item = [None] * size
        self.__length = 0

    def __setitem__(self, key, value):
        self.__item[key] = value
        self.__length += 1

    def __getitem__(self, key):
        return self.__item[key]

    def __len__(self):
        return self.__length

    def __iter__(self):
        for value in self.__item:
            yield value


class Slot:
    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value

    def __str__(self):
        return 'key:{},value:{}'.format(self.key, self.value)


class HashTable:
    def __init__(self):
        self.size = 4
        self.items = Array(self.size)

    def find_index(self, key):
        index = self.get_index(key)
        if self.items[index] == None:
            return index
        else:
            while self.items[index] is not None:
                if self.items[index].key == key:
                    return index
                else:
                    index = (5*index+1) % self.size
            return index

    def get_index(self, key):
        return hash(key) % self.size

    def put(self, key, value):
        s = Slot(key, value)
        index = self.get_index(key)
        self.items[index] = s

    def find_key(self, key):
        index = self.get_index(key)
        if self.items[index] == None:
            return None
        else:
            while self.items[index] is not None:
                if key == self.items[index].key:
                    return index
                else:
                    index = (5*index+1) % self.size
            return None

    def get(self, key):
        index = self.find_key(key)
        return self.items[index]


if __name__ == '__main__':
    h = HashTable()
    h.put('name', '王凯')
    h.put('sex', '男')
    h.put('age', '18')

    print(h.get('name'))
    print(h.get('age'))
    print(h.get('sex'))

错误情况：

正确情况：

老师您好，这块的知识我一直不是特别熟，我自己缕了一下，麻烦您看下我想的是不是对的呢？

老师，讲课过程中用来画图的这个软件是什么？

老师，我想求出二叉树中两个节点的距离，我的代码如下，函数已经写出来了，但是不知道如何返回level值，麻烦您帮我改一下，谢谢您了

class BiTNode:
    def __init__(self):
        self.data = None
        self.lchild = None
        self.rchild = None

def arraytotree(arr,start,end):
    #中序遍历生成二叉树
    root = None
    if end >= start:
        root = BiTNode()
        mid = (start+end+1)//2
        root.data = arr[mid]
        root.lchild = arraytotree(arr,start,mid-1)
        root.rchild = arraytotree(arr,mid+1,end)
    else:
        root = None
    return root

def FindParentNode(root,node1,node2):
    #找到公共父节点
    if root == None or root == node1 or root == node2:
        return root
    lchild = FindParentNode(root.lchild,node1,node2)
    rchild = FindParentNode(root.rchild,node1,node2)
    if lchild == None:
        return rchild
    elif rchild == None:
        return lchild
    else: return root

def printTree(root,node,level=1):
    #输出节点与根节点的距离level

    if root == node:
        return 0
    if root.lchild != None:
        if root.lchild == node:
            print(level)
        printTree(root.lchild,node,level=level+1)
    # print(root.data,end=" ")
    if root.rchild != None:
        if root.rchild == node:
            print(level)
        printTree(root.rchild,node,level=level+1)

if __name__=="__main__":
    arr = [1,2,3,4,5,6,7,8,9,10]
    root = arraytotree(arr,0,len(arr)-1)
    node1 = root.rchild.lchild.lchild
    node2 = root.lchild.rchild.lchild
    L = printTree(root,node1)
    M = printTree(root,node2)
    res = FindParentNode(root,node1,node2)
    N = printTree(root,res)
    print(L,M,N)
    distance = printTree(root,node1)+printTree(root,node2)-2*printTree(root,res)
    # if res != None:
    #     print(str(node1.data))
    #     print(str(node2.data))
    #     print(str(res.data))
    # print(distance)

十八十九分钟的时候听到了猫叫，感觉它应该是饿了

这个在网站的哪个文件里参考，没找到，懵逼

老师，如果1变成3，23变成2，要删除12的话，把2提到了12的位置，现在2的左子树是4，右子树是41，那不是两个子树都大于2了吗？这还符合规则吗？不是说左子树小于父节点，右子树大于父节点吗？谢谢老师

代码中left和right事一个列表得意思？

视频中是通过eumerate函数，去遍历枚举类型中的每个下标和值，为什么我通过遍历列表的下标去查找对应的index 的方法总是找不到呢？不知道问题出在哪里？为什么这种方法不行？

"""
线性查找方法
"""
def linear_search(find_value, argus):
    for index in range(len(argus)):
        if find_value == argus[index]:
            return index
        else:
            return -1


if __name__ == '__main__':
    nums = [1,2,3,5,6,7,8,9,14,23,34,56,42,64]
    print(linear_search(7, nums))

结果：

我认为视频中有两处错误：

1.在定义bubble_sort(array)时:

if num[j]>num[j+1]:
    num[j], num[j+1] = num[j+1], num[j]

此时应该是用的形参，所以不是实参num，而应该是array.

if array[j]>array[j+1]:
    array[j], array[j+1] = array[j+1], array[j]

2. 在进行最优优化时，认为运行了i 次，这个应该不对

print("比较了{}次".format(i))

而i 是从0起始的， 所以应该是运行了i+1次

print("比较了{}次".format(i+1))

老师，线性结构扩容为什么要重新分配空间，不能在原来空间后面继续移位呢？

老师，在截图中红线圈出的这行代码是不是多余了？