▶ 书中第三章部分程序，加上自己补充的代码，包括单词频率统计，（单链表）顺序查找表，二分查找表
● 单词频率统计
package package01; import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.ST;
import edu.princeton.cs.algs4.StdOut; public class class01
{
private class01() {} public static void main(String[] args)
{
int distinct = 0, words = 0;
int minlen = Integer.parseInt(args[0]); // 第一个参数，参与统计的单词长度下限
ST<String, Integer> st = new ST<String, Integer>(); for(;!StdIn.isEmpty();)
{
String key = StdIn.readString();
if (key.length() < minlen) // 过短的单词不参与处理
continue;
words++;
if (st.contains(key)) // 已有就计数 +1，没有就新添记录
st.put(key, st.get(key) + 1);
else
{
st.put(key, 1);
distinct++;
}
} String max = ""; // 迭代器遍历符号表，查找频率最高的单词
st.put(max, 0);
for (String word : st.keys())
{
if (st.get(word) > st.get(max))
max = word;
}
StdOut.println(max + " " + st.get(max));
StdOut.println("distinct = " + distinct);
StdOut.println("words = " + words);
}
}
● （单链表）顺序查找表
package package01; import edu.princeton.cs.algs4.Queue;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut; public class class01<Key, Value>
{
private int n;
private Node first; private class Node
{
private Key key;
private Value val;
private Node next; public Node(Key inputKey, Value inputVal, Node inputNext)
{
key = inputKey;
val = inputVal;
next = inputNext;
}
} public class01() {} public int size()
{
return n;
} public boolean isEmpty()
{
return size() == 0;
} public boolean contains(Key key) // 判断是否存在键 key
{
if (key == null)
throw new IllegalArgumentException("\n<contains> key == null.\n");
return get(key) != null;
} public Value get(Key key) // 查询元素的值
{
if (key == null)
throw new IllegalArgumentException("\n<get> key == null.\n");
for (Node x = first; x != null; x = x.next)
{
if (key.equals(x.key))
return x.val;
}
return null;
} public void put(Key key, Value val) // 插入元素
{
if (key == null)
throw new IllegalArgumentException("\n<put> key == null.\n");
if (val == null) // 空值用于删除
{
delete(key);
return;
}
for (Node x = first; x != null; x = x.next)
{
if (key.equals(x.key))
{
x.val = val;
return;
}
}
first = new Node(key, val, first);
n++;
} public void delete(Key key) // 删除元素
{
if (key == null)
throw new IllegalArgumentException("\n<delete> key == null.\n");
first = deleteKernel(first, key);
} private Node deleteKernel(Node x, Key key) // 删除元素的递归内核
{
if (x == null)
return null;
if (key.equals(x.key)) // x 头节点的键等于 key
{
n--;
return x.next;
}
x.next = deleteKernel(x.next, key); // 递归删除目标节点，需要用栈保存从链表开头到目标节点之间的所有节点
return x;
} public Iterable<Key> keys() // 将单链表依次入队，构成迭代器
{
Queue<Key> queue = new Queue<Key>();
for (Node x = first; x != null; x = x.next)
queue.enqueue(x.key);
return queue;
} public static void main(String[] args)
{
class01<String, Integer> st = new class01<String, Integer>();
for (int i = 0; !StdIn.isEmpty(); i++)
{
String key = StdIn.readString();
st.put(key, i);
}
for (String s : st.keys())
StdOut.println(s + " " + st.get(s));
}
}
● 二分查找表
package package01; import java.util.NoSuchElementException;
import edu.princeton.cs.algs4.Queue;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut; public class class01<Key extends Comparable<Key>, Value>
{
private Key[] keys;
private Value[] vals;
private int n = 0; public class01()
{
this(2); // 省缺初始尺寸为 2
} public class01(int capacity)
{
keys = (Key[]) new Comparable[capacity];
vals = (Value[]) new Object[capacity];
} private void resize(int capacity) // 尺寸扩展为 capacity
{
assert capacity >= n;
Key[] tempk = (Key[]) new Comparable[capacity];
Value[] tempv = (Value[]) new Object[capacity];
for (int i = 0; i < n; i++)
{
tempk[i] = keys[i];
tempv[i] = vals[i];
}
vals = tempv;
keys = tempk;
} public int size()
{
return n;
} public boolean isEmpty()
{
return size() == 0;
} public boolean contains(Key key)
{
if (key == null)
throw new IllegalArgumentException("\n<contains> key == null.\n");
return get(key) != null;
} public Value get(Key key)
{
if (key == null)
throw new IllegalArgumentException("\n<get> key == null.\n");
if (isEmpty())
return null;
int i = rank(key);
if (i < n && keys[i].compareTo(key) == 0)
return vals[i];
return null;
} public int rank(Key key) // 二分搜索
{
if (key == null)
throw new IllegalArgumentException("\n<rank> key == null.\n");
int lo = 0, hi = n - 1;
for (; lo <= hi;)
{
int mid = lo + (hi - lo) / 2;
int cmp = key.compareTo(keys[mid]);
if (cmp < 0)
hi = mid - 1;
else if (cmp > 0)
lo = mid + 1;
else return mid;
}
return lo;
} public void put(Key key, Value val)
{
if (key == null)
throw new IllegalArgumentException("\n<put> key == null.\n");
if (val == null)
{
delete(key);
return;
}
int i = rank(key);
if (i < n && keys[i].compareTo(key) == 0)
{
vals[i] = val;
return;
}
if (n == keys.length)
resize(2 * keys.length);
for (int j = n; j > i; j--)
{
keys[j] = keys[j - 1];
vals[j] = vals[j - 1];
}
keys[i] = key;
vals[i] = val;
n++;
//assert check();
} public void delete(Key key)
{
if (key == null)
throw new IllegalArgumentException("\n<delete> key == null.\n");
if (isEmpty())
return;
int i = rank(key);
if (i == n || keys[i].compareTo(key) != 0)
return;
for (int j = i; j < n - 1; j++) // 删除节点时要依次挪动
{
keys[j] = keys[j + 1];
vals[j] = vals[j + 1];
}
n--;
keys[n] = null; // 方便垃圾回收
vals[n] = null;
if (n > 0 && n == keys.length / 4)
resize(keys.length / 2);
//assert check();
} public void deleteMin()
{
if (isEmpty())
throw new NoSuchElementException("\n<deleteMin> underflow.\n");
delete(min());
} public void deleteMax()
{
if (isEmpty())
throw new NoSuchElementException("\n<deleteMax> underflow.\n");
delete(max());
} public Key min()
{
if (isEmpty())
throw new NoSuchElementException("\n<min> empty.\n");
return keys[0];
} public Key max()
{
if (isEmpty())
throw new NoSuchElementException("\n<max> empty.\n");
return keys[n - 1];
} public Key select(int k)
{
if (k < 0 || k >= size())
throw new IllegalArgumentException("\n<select> k < 0 || k >= size.\n");
return keys[k];
} public Key floor(Key key) // 返回 key 的上一个元素
{
if (key == null)
throw new IllegalArgumentException("\n<floor> key == null.\n");
int i = rank(key);
if (i < n && key.compareTo(keys[i]) == 0)
return keys[i];
if (i == 0)
return null;
else return keys[i - 1];
} public Key ceiling(Key key) // 返回 key 的下一个元素
{
if (key == null)
throw new IllegalArgumentException("\n<ceiling> key == null.\n");
int i = rank(key);
if (i == n)
return null;
else return keys[i];
} public int size(Key lo, Key hi) // 返回 lo 到 hi 的元素个数
{
if (lo == null)
throw new IllegalArgumentException("\n<size> lo == null.\n");
if (hi == null)
throw new IllegalArgumentException("\n<size> hi == null.\n");
if (lo.compareTo(hi) > 0)
return 0;
return rank(hi) - rank(lo) + (contains(hi) ? 1 : 0); } public Iterable<Key> keys()
{
return keys(min(), max());
} public Iterable<Key> keys(Key lo, Key hi)
{
if (lo == null)
throw new IllegalArgumentException("\n<keys> lo == null.\n");
if (hi == null)
throw new IllegalArgumentException("\n<keys> lo == null.\n");
Queue<Key> queue = new Queue<Key>();
if (lo.compareTo(hi) > 0)
return queue;
for (int i = rank(lo); i < rank(hi); i++)
queue.enqueue(keys[i]);
if (contains(hi))
queue.enqueue(keys[rank(hi)]);
return queue;
} private boolean check()
{
for (int i = 1; i < size(); i++)
{
if (keys[i].compareTo(keys[i - 1]) < 0)
return false;
}
for (int i = 0; i < size(); i++)
{
if (i != rank(select(i)))
return false;
}
for (int i = 0; i < size(); i++)
{
if (keys[i].compareTo(select(rank(keys[i]))) != 0)
return false;
}
return true;
}
public static void main(String[] args)
{
class01<String, Integer> st = new class01<String, Integer>();
for (int i = 0; !StdIn.isEmpty(); i++)
{
String key = StdIn.readString();
st.put(key, i);
}
for (String s : st.keys())
StdOut.println(s + " " + st.get(s));
}
}