元素长度是4？

老师，你写的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'))  # 这里要解决陷入死循环的问题

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

这里的O（n）不应该是算法的增速随数据量增加线性增长吗

老师，数组就是列表，为什么还要怎么写，为什么不直接用Python列表中的方法

NODE_LIST = [
    {'data': 60, 'left': 12, 'right': 90, 'is_root': True},
    {'data': 12, 'left': 4, 'right': 41, 'is_root': False},
    {'data': 4, 'left': 1, 'right': None, 'is_root': False},
    {'data': 1, 'left': None, 'right': None, 'is_root': False},
    {'data': 41, 'left': 29, 'right': None, 'is_root': False},
    {'data': 29, 'left': 23, 'right': 37, 'is_root': False},
    {'data': 23, 'left': None, 'right': None, 'is_root': False},
    {'data': 37, 'left': None, 'right': None, 'is_root': False},
    {'data': 90, 'left': 71, 'right': 100, 'is_root': False},
    {'data': 71, 'left': None, 'right': 84, 'is_root': False},
    {'data': 100, 'left': None, 'right': None, 'is_root': False},
    {'data': 84, 'left': None, 'right': None, 'is_root': False},
]


class Node():
    def __init__(self, date, left=None, right=None):
        self.date = date
        self.left = left
        self.right = right

    def __str__(self):
        return "数据是：{}".format(self.date)


class Tree():
    def __init__(self, root=None):
        self.root = root

    def install_date(self, dates):
        node_list = {}
        for n in dates:
            node = Node(n['data'], n['left'], n['right'])
            node_list[n['data']] = node
        for m in dates:
            node = node_list[m['data']]
            if node.left:
                node.left = node_list[node.left]
            if node.right:
                node.right = node_list[node.right]
            if m["is_root"]:
                self.root = node

    def search(self, subtree, value):
        if subtree is None:
            return None
        elif subtree.date > value:
            return self.search(subtree.left, value)
        elif subtree.date < value:
            return self.search(subtree.right, value)
        else:
            return subtree

    def iter_node(self, node):
        if node:
            print(node.date)
            self.iter_node(node.left)
            self.iter_node(node.right)

    def get_min(self, subtree):
        if subtree is None:
            return None
        elif subtree.left:
            return self.get_min(subtree.left)
        else:
            return subtree

    def add(self, value):
        node = self.search(self.root, value)
        if node:
            return False
        else:
            self.root = self.insert_data(self.root,value)
            return True

    def insert_data(self, subtress, value):
        if subtress is None:
            subtress = Node(value)
        elif subtress.date > value:
            subtress.left = self.insert_data(subtress.left, value)
        else:
            subtress.right = self.insert_data(subtress.right, value)
        return subtress

老师，我这里为啥曝出 重复代码片段，我找不到哪里重复了

老师，你的这个 self.search 没有加任何参数，这样写有什么作用？

self.__item = [None]*size，老师说是分配空间，没太看懂

老师，根据两两排序，7个数字，第一轮应该是6次吧老师

def remove(self,value):
    prev = self.root
    for n in self.__iter__():
        if n.value == value:
            if not n.next:
                self.next = prev
                # 这里不能直接break,因为self.size没有减1
            else:
                prev.next = n.next
            self.size-=1
        prev = n

老师，请问如果我这样写，就是把删除的节点脱离了链，那请问被删除的节点会被垃圾回收吗

老师，请问这个optional，List 指的是啥，为何要从typing里导入呢

还有这个判断遍历结束的条件如何理解呢

老师，这个线式队列，当put（）进去超过size的数后，就不符合FIFO了

你看看测试结果

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 Queue():
    def __init__(self,size=4):
        self.item = Array(size)
        self.size = size
        self.head = 0
        self.end = 0
    def put(self,value):
        self.item[self.head % self.size] = value
        self.head += 1
    def pop(self):
        temp =  self.item[self.end % self.size]
        self.end += 1
        return temp

if __name__ == "__main__":
    #q = Queue()
    #q.put('曹操')
    #q.put('刘备')
    #q.put('孙权')

    #print(q.pop())
    #print(q.pop())
    #print(q.pop())
    q = Queue()
    for i in range(1, 6):
        q.put(i)

    for i in range(q.size):
        print(q.pop())

class Node():
    def __init__(self, prev = None, next = None, value = None):
        self.value = value
        self.prev = prev
        self.next = next
    def __str__(self):
        return f'Node:{self.value}'

class DoubleLinkList():
    def __init__(self):
        self.root = Node()  # 初始化root节点
        self.end = None  # 最后一个节点
        self.size = 0  # 链式结构的长度

    def append(self, value):
        node = Node(value)  # 实例化node  封装节点对象
        # 判断是否含有元素
        if not self.end:  # 如果没有数据
            self.root.next = node  # 将root的下一个节点设置为新的node节点
            node.prev = self.root  # 设置新的节点的 上一个节点为root节点
        else:
            self.end.next = node  # 将原来最后一个节点的下一个节点设置为 node节点
            node.prev = self.end  # 设置新节点的上一个节点为原来的最后一个节点 
        self.end = node   # 更新最后一个节点为新加的 node节点
        self.size += 1  # 更新链式结构大小

    def append_first(self, value):
        node = Node(value)
        if not self.end:
            self.end = node
        else:
            temp = self.root.next
            node.next = temp
            temp.prev = node
        node.prev = self.root  # 将node的前一个节点设置为根节点        
        self.root.next = node  # 将root的下一个节点设置为新的node节点
        self.size += 1  # 更新链式结构大小
    def __iter__(self):
        current = self.root.next
        if current:
            while current is not self.end:
                yield current.value
                current = current.next
            yield current.value

    def revers_iter(self):
        current = self.end  # 获取最后一个节点
        if current:
            while current is not self.root:
                yield current
                current = current.prev





if __name__ == '__main__':
    dlink = DoubleLinkList()
    dlink.append('孙悟空')
    dlink.append('唐僧')
    dlink.append('猪八戒')
    dlink.append('孙悟空')

    for i in dlink:
        print(i)
    print('------逆向遍历----')
    for i in dlink.revers_iter():
        print(i)

错误：

老师，我检查了好几遍也没找出来是哪里出错了 为什么显示的都是None？

老师，几个不部分的subtree 是return到哪里？这里的逻辑我搞不清楚了