查找算法之——符号表(引入篇)

博客园首页 William 172浏览 0评论

符号表的主要目的是用来存储键值对,也就是将一个键和一个值关联起来,它的主要操作为插入和查找。

这篇只是为下一篇文章作为抛砖引玉,为不熟悉符号表的朋友做了一个大体的介绍,在文章的结尾列出了符号表的基本操作,有一定了解的朋友可以跳的下一篇文章(二叉查找树)。

首先我们必须讨论几个基本问题,这在之后的思想中将会一直用到:

1、重复的键

符号表不允许出现重复的键,当向表中插入的键值对的键已经出现在标中,当前加入的键值对会覆盖原有的键值对,也就是进行了更新。

2、空键或空值

键不能为空,这在java机制中会产生异常。我们还规定,值也不能为空。(get()方法能通过查找键返回其关联的值,当键不存在时get()方法会返回null)

这个规定有两个作用:

第一、我们能判断一个键值对是否存在符号表中。

第二、我们可以将null作为put()的第二个参数来实现删除操作,

3、删除操作

删除操作的实现有两种思路:即时删除和延时删除,延时删除就是上面提到的,先将其值置位为空,然后在某个时刻删除所有值为空的键。即时删除也就是立即从表中删除指定的键。(本文中将使用即时删除)

4、键的等价性

键可以是任意类型(我们将其设置为泛型),可以是integer,double和string等等,java已经为他们实现了equals()方法来判断相等,如果是自定义的键,则需要重写equals()方法。

 

下面我们进入正题:

一、无序链表中的顺序查找

顾名思义,无序链表就是通常意义上的链表,只是链表的节点被定义为了键值对的形式,无序链表每次插入操作会在头部插入一个新节点,而查找操作是从链表的头部开始一个个地遍历符号表并使用equals()方法来进行匹配。这种方法的效率是非常低的(它的查找操作是线性级别的),查找第一个键需要1次比较,第二个键需要2次比较…因此平均比较次数为(1+2+…+n)/n =(n+1)/2~n/2。它无法适用于大型符号表。

 

 1 public class SequentialSearchST<Key, Value> {// 基于无序链表
 2     private int n;// number of key-value pairs
 3     private Node first;
 4 
 5     private class Node {// 链表节点的定义
 6         Key key;
 7         Value val;
 8         Node next;
 9 
10         public Node(Key key, Value val, Node next) {
11             this.key = key;
12             this.val = val;
13             this.next = next;
14         }
15     }
16 
17     public Value get(Key key) {// 查找给定的键,返回关联的值
18         for (Node x = first; x != null; x = x.next) {
19             if (key.equals(x.key)) {
20                 return x.val;
21             }
22         }
23         return null;
24     }
25 
26     public void put(Key key, Value val) {// 查找给定的键,找到就更新其值,没找到将其插入最前
27         // **********************
28         if (key == null) {
29             throw new IllegalArgumentException("first argument to put() is null");
30         }
31         if (val == null) {
32             delete(key);
33             return;
34         }
35         // *********************防御性代码,这保证了任何键的值都不为空
36         for (Node x = first; x != null; x = x.next) {
37             if (key.equals(x.key)) {
38                 x.val = val;
39                 return;
40             }
41         }
42         first = new Node(key, val, first);// 插入最前
43         n++;
44     }
45 }

 

二、有序数组中的二分查找

如果能用上二分查找的思想,我们就能把查找的效率提升到对数级别(当然前提是数组有序)

这时插入和查找算法都发生了改变,为了让数组前提有序,插入时我们会用rank()方法来确定键的位置,再将此位置后的键后移一位,最后插入键。rank()返回的是键在符号表中排名。在这里如果键存在rank()将返回键在有序数组中的下标。

在这里我们用两个数组分别存储键值对的键和值,同一键值对在数组中的下标是一样的。

 

  1 public class BinarySearchST<Key extends Comparable<Key>, Value> {// 有序查找表(基于有序数组)
  2     private Key[] keys;
  3     private Value[] vals;
  4     private int n = 0;// 用于记录符号表中键值对的个数
  5 
  6     public BinarySearchST(int capacity) {// 动态调整大小
  7         keys = (Key[]) new Comparable[capacity];
  8         vals = (Value[]) new Object[capacity];
  9     }
 10 
 11     public boolean contains(Key key) {
 12         if (key == null) {
 13             throw new IllegalArgumentException("argument to contains is null");
 14         }
 15         return get(key) != null;
 16     }
 17 
 18     public int size() {
 19         return n;
 20     }
 21 
 22     public int size(Key lo, Key hi) {
 23         if (lo == null) {
 24             throw new IllegalArgumentException("first argument to size() is null");
 25         }
 26         if (hi == null) {
 27             throw new IllegalArgumentException("second argument to size() is null");
 28         }
 29         if (lo.compareTo(hi) > 0) {
 30             return 0;
 31         }
 32         if (contains(hi)) {
 33             return rank(hi) - rank(lo) + 1;
 34         } else {
 35             return rank(hi) - rank(lo);
 36         }
 37     }
 38 
 39     public Key min() {
 40         if (isEmpty()) {
 41             throw new NoSuchElementException("called min with empty symbol table");
 42         }
 43         return keys[0];
 44     }
 45 
 46     public Key max() {
 47         if (isEmpty()) {
 48             throw new NoSuchElementException("called max with empty symbol table");
 49         }
 50         return keys[n - 1];
 51     }
 52 
 53     public Value get(Key key) {
 54         if (key == null) {
 55             throw new IllegalArgumentException("argument to get is null");
 56         }
 57         if (isEmpty()) {
 58             return null;
 59         }
 60         int i = rank(key);
 61         if (i < n && keys[i].compareTo(key) == 0) {
 62             return vals[i];
 63         }
 64         return null;
 65     }
 66 
 67     private int rank(Key key) {// 基于有序数组的二分查找(迭代)
 68         if (key == null) {
 69             throw new IllegalArgumentException("argument to rank is null");
 70         }
 71         int lo = 0, hi = n - 1;
 72         while (lo <= hi) {
 73             int mid = lo + (hi - lo) / 2;
 74             int cmp = key.compareTo(keys[mid]);
 75             if (cmp > 0) {
 76                 lo = mid + 1;
 77             } else if (cmp < 0) {
 78                 hi = mid - 1;
 79             } else {
 80                 return mid;
 81             }
 82         }
 83         return lo;// 找不到的情况
 84     }
 85 
 86     public Iterable<Key> keys() {
 87         return keys(min(), max());
 88     }
 89 
 90     private Iterable<Key> keys(Key lo, Key hi) {
 91         if (lo == null) {
 92             throw new IllegalArgumentException("first argument to keys() is null");
 93         }
 94         if (hi == null) {
 95             throw new IllegalArgumentException("second argument to keys() is null");
 96         }
 97         Queue<Key> queue = new Queue<Key>();
 98         if (lo.compareTo(hi) > 0) {
 99             return queue;
100         }
101         for (int i = rank(lo); i < rank(hi); i++) {
102             queue.enqueue(keys[i]);
103         }
104         if (contains(hi)) {
105             queue.enqueue(keys[rank(hi)]);
106             //queue.enqueue(hi);
107         }
108         return queue;
109     }
110 
111     private boolean isEmpty() {
112         // TODO Auto-generated method stub
113         return n == 0;
114     }
115 
116     public void put(Key key, Value val) {
117         if (key == null) {
118             throw new IllegalArgumentException("first argument to put is null");
119         }
120         if (val == null) {
121             delete(key);
122             return;
123         }
124         int i = rank(key);
125         if (i < n && key.compareTo(keys[i]) == 0) {//已有元素进行更新
126             vals[i] = val;
127             return;
128         }
129         for (int j = n; j > i; j--)  {//键值对后移
130             keys[j] = keys[j-1];
131             vals[j] = vals[j-1];
132         }
133         keys[i] = key;
134         vals[i] = val;
135         n++;
136     }
137 
138     public void delete(Key key) {
139         if (key == null) {// 避免空指针错误
140             throw new IllegalArgumentException("argument to delete is null");
141         }
142         if (isEmpty()) {
143             return;
144         }
145         int i = rank(key);
146         if (i == n || key.compareTo(keys[i]) != 0) {
147             return;
148         }
149         for (int j = i; j < n - 1; j++) {//元素前移
150             keys[j] = keys[j + 1];
151             vals[j] = vals[j + 1];
152         }
153         n--;
154         keys[n] = null;
155         vals[n] = null;
156     }
157 }

 

 

 

 

我们默认使用的二分查找是迭代进行,下面给出递归的形式:

 1     public int rank(Key key,int lo,int hi) {
 2         if(hi<lo) {
 3             return lo;
 4         }
 5         int mid=lo+(hi-lo)/2;
 6         int cmp=key.compareTo(keys[mid]);
 7         if(cmp<0) {
 8             return rank(key,lo,mid-1);
 9         }else  if(cmp>0) {
10             return rank(key,mid+1,hi);
11         }else {
12             return mid;
13         }
14     }

 

如果理解了迭代的形式,就能很容易改写出递归了。

 

用对象的数组代替两个平行数组(求指点):

定义一个以键和值为属性的对象,用对象数组来代替两个平行数组,由于本人学术不精,未能完成,主要问题是不知如何创建不同类型属性的泛型数组(key继承了comparable而value继承了object)。在此提出问题,希望高人指点!

 

 1 public class BSST<Key extends Comparable<Key>, Value> {
 2     class Item{//内部类
 3         Key key;
 4         Value val;
 5     }
 6     private Item[] item;
 7     private int n = 0;
 8     public BSST(int capacity) {// 动态调整大小
 9         item = (Item[]) new Object[capacity];//出现类型转换错误
10     //item = (Item[]) new Comparable[capacity];//出现类型转换错误
11
12 } 13 }

 

 

 

 

四、符号表的基本操作

符号表的基本操作远远不止本文提到的rank()、put()、get()、delete()。下面将他们列出来,了解个大概,在下一篇文章中将会一一实现他们。

boolean contains(Key key):判断key是否存在于符号表中

int size(Key lo,Key hi):返回lo到hi之间的键值对数量

Key min():返回最小键

Key max():返回最大键

Key floor(Key key):返回小于等于key的最大键

Key ceiling(Key key):返回大于等于key的最小键

Key select(int k):返回排名为k的键

Iterable<Key> keys(Key lo,Key hi):返回一个队列,包含lo-hi之间的所有键(已排序)

 

rank(select(k))==k ture

select(rank(key))==key ture


注:www2014.aspxhtml.com转载自cnblogs,若看不到图片,请移步来源网址查看。
via:https://www.cnblogs.com/Unicron/p/9787726.html

转载请注明:AspxHtml学习分享网 » 查找算法之——符号表(引入篇)

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址