3 查找

3.1 符号表

定义:符号表是一种存储键值对的数据结构:支持两种操作:插入(put),即将一组新的键值对存入表中;查找(get),即根据给定的键得到相应的值.

3.1.1 一些规定:

  1. 重复键:每个键只对应一个值,若新存入键值对和已有键冲突则新值会更新旧值
  2. 空(null)键:键(key)不能为空
  3. 空值:值(value)不允许为空
  4. 删除操作:延时删除:将键对应值置空,然后一并删除空值键.put(key,null)可作为delete(key)的延时实现;即时删除:即delete()

3.1.2 有序符号表

API

public class ST<Key extends Comparable<Key>, Value>

方法 注释
ST() 创建符号表
void put(Key key, Value val) 存入键值对
Value get(Key key) 获取键key的对应值
void delete(Key key) 删去键值对key
boolean contains(Key key) 判断键是否存在
boolean isEmpty() 表是否为空
int size() 表中键值对数量
Key min() 最小的键
Key max() 最大的键
Key floor(Key key) 小于等于key的最大键
Key ceiling(Key key) 大于等于key的最小键
int rank(Key key) 小于key的键个数
Key select(int k) 排名为k的键
  • 排名(rank):找出小于指定键的键数;选择(select)找出排名为k的键,即表中比该键小的键数为k.对于0到size()-1的所有i都有i == rank(select(i))且所有键都满足key = select(rank(key))

3.1.4无序链表中的顺序查找(见算法3.1)

3.1.5有序数组中的二分查找(见算法3.2)