（python）实现Map的两种方法

77 阅读 0 评论 51 点赞

我是靠谱客的博主悦耳小鸽子，最近开发中收集的这篇文章主要介绍（python）实现Map的两种方法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1.二分搜索树实现：

class BSTMap:
class _Node:
def __init__(self,key=None,value=None):
self.key=key
self.value=value
self.left=None
self.right=None
def __str__(self):
return "key:{},Value:{}".format(str(self.key),str(self.value))
def __init__(self):
self._size=0
self._root=None
def get_size(self):
return self._size
def add(self,key,value):
self._root=self._add(self._root,key,value)
def _add(self,node,key,value):
if not node:
self._size+=1
node=self._Node(key,value)
elif node.key==key:
node.value=value
elif node.key>key:
node.left=self._add(node.left,key,value)
else node.key<key:
node.right=self._add(node.right,key,value)
return node
def _get_node(self,node,key):
if not node:
return None
elif node.key==key:
return node.value
elif node.key>key:
return self._get_node(node.left,key)
else:
return self._get_node(node.right,key)
def contains(self,key):
return self._get_node(self._root,key) is not None
def getter(self,key):
node=self._get_node(self._root,key)
return node.value if node is not None else None
def setter(self,key,value):
node=self._get_node(self._root,key)
if not node:
raise ValueError('key{},doesn't exist'.format(str(key)))
node.value=value
def remove(self,key):
node=self._get_node(self.root,key)
if not node:
self._root=self._remove(self._root,key)
return node.value
else:
return None
def _remove(self,node,key):
if not node:
return
if node.key>key:
node.left=self._remove(node.left,key)
elif node.key<key:
node.right=self._remove(node.right,key)
else:
if not node.left:
ret_node=node.right
node.right=None
self._size-=1
return ret_node
elif not node.right:
ret_node=node.left
node.left=None
self._size-=1
return ret_node
else:
ret_node=self._minimun(node.right,node.key)
ret_node.right=self._remove_min(node.right)
ret_node.left=node.left
node.left=node.right=None
return ret_node
def _minimum(self,node):
if not node.left:
return node
return self._minimum(node.left)
def _remove_min(self,node):
if not ndoe.left:
ret_node=node.right
node.right=None
self._size-=1
return ret_node
node.left=self._remove_min(node.left)
return node

2.链表实现（不推荐时间复杂度高）：

class LinkedListMap:
def _Node:
def __init__(self,key=None,value,next=None):
self.key=key
self.value=value
self.next=next
def __str(self):
return "Key:{},Value:{}".format(str(self.key),str(self.value))
def __init__(self):
self._dummy_head=self._Node()
self._size=0
def get_node(self,key):
curr=self._dummy_head.next
while curr:
if curr.key==key:
return curr
curr=curr.next
def setter(self,key,value):
node=self.get_node(key)
if not node:
raise ValueError('Key Error')
node.value=value
def add(node,key,value):
node=self.get_node(key)
if not node:
self._dummy_head.next=(self._Node(key,value,self._dummy_head.next)
self._size+=1
else:
node.value=value
def remove(self,key):
pre=self._dummy_head
while prev.next:
if prev.next.key==key
break
prev=pre.next
if pre.next:
del_node=pre.next
pre.next=del_node.next
del_node.next=None
return del_node.value