基于二分查找的有序符号表.zip_bst_基于二分查找的有序符号表_有序符号表_链表python实现

#_*_ encoding: utf-8 _*_ ''' Created on 2017年12月28日 @author: wangs0622 function: 有序符号表 ''' from LinkedList.Link import Link from LinkedList import Node class ST(Link): def __init__(self): Link.__init__(self) def put(self, key, value): data = Node([key, value]) node = self._find(key) if node: node.data[1] = value self.appendFirst(data) def get(self, key): node = self._find(key) if node: return node.data[1] return None def delete(self, key): pass def __contains__(self, key): node = self._find(key) if node: return True return False def _find(self, key): ''' function: 寻找到 key 对应得结点，并返回此结点，没有找到返回 None ''' temp = self.first while True: if temp is None: break if temp.data[0] == key: return temp temp = temp.next return None class OrderedST(): def __init__(self): self.keys = [] self.values = [] self.comparetimes = 0 def put(self, key, value): ''' function: 将 key=value 这一键值对按顺序插入 ''' if value is None: raise ValueError('value can not be None') if key is None: raise KeyError('key can not be None') if self.len() == 0: self.keys.append(key) self.values.append(value) return i = self.rank(key) if i >= self.len(): #如果 key 最大，直接插入 self.keys.append(key) self.values.append(value) return if self.keys[i] == key: self.values[i] = value else: self.keys.insert(i, key) self.values.insert(i, value) def get(self, key): if key in self.keys: return self.values[self.keys.index(key)] else: return None def len(self): return self.size() def size(self, lokey=None, hikey=None): if lokey == hikey == None: return len(self.keys) elif lokey != None and hikey == None: return len(self.keys[self.rank(lokey):]) elif lokey == None and hikey != None: return len(self.keys[:self.rank(hikey)]) else: return len(self.keys[self.rank(lokey):self.rank(hikey)]) def rank(self, key): ''' function: 二分查找确定 key 的位置 ''' lo = 0 hi = self.len()-1 while lo <= hi: mid = lo + int((hi-lo)/2) if key < self.keys[mid]: hi = mid - 1 elif key > self.keys[mid]: lo = mid + 1 else: return mid return lo def delete(self, key): if key in self.keys: value = self.values.pop(self.keys.index(key)) self.keys.remove(key) return (key, value) else: raise KeyError('key:"{}" is not found'.format(key)) def __contians__(self, key): if key in self.keys: return True else: return False def min(self): return self.keys[0] def max(self): return self.keys[-1] def floor(self, key): if key in self.keys: return key i = self.rank(key) if i-1 < 0: raise KeyError('there is not key in keys list samller than the given key') return self.keys[i-1] def ceiling(self, key): if key in self.keys: return key i = self.rank(key) if i >= self.len()-1: raise KeyError('there is not key in keys list bigger than the given key') return self.keys[i] def select(self, k): return self.keys[k] def deleteMin(self): return self.delete(self.min()) def deleteMax(self): return self.delete(self.max()) def getKeys(self, lokey=None, hikey=None): ''' function: 返回大于等于 lokey 且 小于 hikey 的所有 key 值， lokey 与 hikey可以不必在 self.keys 中 ''' if lokey == hikey == None: return self.keys elif lokey is not None and hikey is None: return self.keys[self.rank(lokey):] elif lokey is None and hikey is not None: return self.keys[:self.rank(hikey)] else: return self.keys[self.rank(lokey):self.rank(hikey)] if __name__ == '__main__': st = ST() st.put('b','b') st.put('y','g') st.put('s','d') st.put('f','b') st.put('m','1d') print(st.get('hu'))