开发系统的流程,专业网站优化报价,建筑网站起名,WordPress qinmei影视主题在Python中#xff0c;链表和哈希表都是常见的数据结构#xff0c;可以用来存储和处理数据。
链表是一种线性数据结构#xff0c;由一系列节点组成#xff0c;每个节点包含一个数据元素和一个指向下一个节点的指针。链表可以用来实现栈、队列以及其他数据结构。Python中可…在Python中链表和哈希表都是常见的数据结构可以用来存储和处理数据。
链表是一种线性数据结构由一系列节点组成每个节点包含一个数据元素和一个指向下一个节点的指针。链表可以用来实现栈、队列以及其他数据结构。Python中可以使用自定义类来实现链表也可以使用内置的数据结构如list、collections.deque。
哈希表散列表是一种根据关键字直接访问内存中存储位置的数据结构通过哈希函数将关键字映射到内存地址。Python中的哈希表实现主要是通过字典dict数据类型实现的。
目录
链表
介绍
链表的创建和遍历
链表的插入和删除
双链表
哈希表
哈希表
哈希表的实现
哈希表的应用 链表
介绍
线性结构 class Node:def __init__(self,item):self.item itemself.next None
a Node(1)
b Node(2)
c Node(3)
a.next b
b.next c
print(a.next.next.item)
链表的创建和遍历
头插法 尾差法
class Node:def __init__(self,item):self.item itemself.next None
def create_linklist_head(li):head Node(li[0])for element in li[1:]:node Node(element)node.next headhead nodereturn head
def create_linklist_tail(li):head Node(li[0])tail headfor element in li[1:]:node Node(element)tail.next nodetail nodereturn head
def print_lk(lk):while lk:print(lk.item,end,)lk lk.next
lk create_linklist_tail([1,2,3,5,8])
print_lk(lk)
链表的插入和删除 双链表 哈希表
哈希表 # python中的字典 集合key 不能重复都是使用的这种数据结构来存储的
# 一个通过哈希函数来计算数据存储位置的数据结构
insert(key,value):插入键值对
get(key):如果存在键为key的键值对则返回其value值否则返回空值
delete(key):删除键为key的键值对# 直接寻址表哈希函数 哈希表 浪费空间
# 哈希冲突# 开放寻址法:
线性探查:位置被占用,寻找i1,......
查找规则:22%71,1位置被占用,继续向后查找
二次探查:探查i1^2,i-1^2,...
二度哈希:有n个哈希函数,当使用第一个哈希函数h1发生冲突时,尝试使用h2,h3??????# 拉链法 常用
# 哈希表每个位置都连接一个链表,当冲突发生时,冲突的元素将被加到该位置链表的最后
# 常见哈希函数除法哈希法:h(k) k%m乘法哈希法 ??????
h(k) floor(m(A*key%1)) 向下取整
全域哈希.....
哈希表的实现
# 哈希表的实现
class LinkList:class Node:def __init__(self,itemNone):self.item itemself.next None
# 迭代器class LinkListIterator:def __init__(self,node):self.node nodedef __next__(self):if self.node:cur_node self.nodeself.node cur_node.nextreturn cur_node.itemelse:raise StopIterationdef __iter__(self):return self
def __init__(self,iterableNone):self.head Noneself.tail Noneif iterable:self.extend(iterable)
def append(self,obj):s LinkList.Node(obj)if not self.head:self.head sself.tail selse:self.tail.next sself.tail s
def extend(self,iterable):for obj in iterable:self.append(obj)
def find(self,obj):for n in self:if n obj:return Trueelse:return False# 迭代器def __iter__(self):return self.LinkListIterator(self.head)#转换成字符串def __repr__(self):return ,.join(map(str,self))
# 类似于集合的结构
class HashTable:def __init__(self,size 101):self.size sizeself.T [LinkList() for i in range(self.size)]
def h(self,k):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)
ht HashTable()
ht.insert(0)
ht.insert(1)
ht.insert(3)
ht.insert(102)
ht.insert(508)
# print(,.join(map(str,ht.T)))
print(ht.find(3))
哈希表的应用
加密不能解密
哈希冲突不同的值使用哈希函数计算出来的哈希值可能相同
