内容：
无序链表实现符号表
有序数组对实现符号表
二叉树结构
红黑树结构（无删除方法）
拉链法哈希表
线性探测法哈希表
import java.io.CharArrayReader; import java.util.ArrayList; import java.util.Iterator; /** * @ClassName LinkedST * @Author wangyudi * @Version 1.0 * @Description 无序链表（将键值对存储在链表的结点中）实现的符号表 * <p> * 成员变量：头指针 first、链表大小 count 、匿名内部类结点 Node * 成员方法: 获取值get()、插入/更新值put()、大小size()、删除delete() (实现基本的增删该查) * <p> * 匿名内部类Node * 成员变量：键key、值value、下一个节点 next */ public class LinkedST<Key extends Comparable<Key>, Value> implements Iterable<Value> { private Node first; private int count; //链表结点数量 private class Node { Key key; Value val; Node next; public Node(Key key, Value val, Node next) { this.key = key; this.val = val; this.next = next; } } public LinkedST() { this.first = null; this.count = 0; } /** * 根据键从符号表中查询值 * 实现方法：遍历整个链表 * 注意：符号表为空的情况 * * @param key * @return */ public Value get(Key key) { for (Node i = first; i != null; i = i.next) { //链表遍历的通用方法 if (i.key == key) return i.val; //找到 } return null; } /** * 向符号表更新或插入一个键值对 * 实现方法：遍历 * 注意：先空符号表插入键值对的情况 * * @param key * @param val */ public void put(Key key, Value val) { for (Node i = first; i != null; i = i.next) { if (i.key == key) { //找到相同的键，更新后返回 i.val = val; return; } } count++; first = new Node(key, val, first); //考虑了空链表的情况 } /** * 根据键删除键值对 * 注意点：空符号表的情况; 需要操作被删除结点的前一个结点故使用两个指针 * * @param key * @return */ public Value delete(Key key) { Node p1 = null; //考录到需要访问链表删除结点的前一结点 Node p2 = first; while (p2 != null) { if (p2.key == key) { Value temp = null; if (p1 == null) { //删除头结点的情况 temp = p2.val; first = first.next; } else { //非删除头结点 p1.next = p2.next; temp = p2.val; } p1 = null; p2 = null; count--; return temp; } p1 = p2; p2 = p2.next; } return null; } @Override public Iterator<Value> iterator() { return new Iterator<Value>() { Node i = first; @Override public boolean hasNext() { if (i != null) return true; return false; } @Override public Value next() { Value temp = i.val; i = i.next; return temp; } }; } } /** * @ClassName ArrayST * @Author wangyudi * @Date 2019/6/27 16:46 * @Version 1.0 * @Description 有序平行数组对实现符号表 * 成员变量：键数组、值数组、数量 * 成员函数：获取值get()、添加/更新值put()、获取键的排名rank()、删除键值对delete()、获取大小size()、显示display()、调整内部数组的大小resize() * 注意：实现的关键在于 ：获取键的排名方法rank(),使用二分法实现快速的查找，其他操作都依赖该方法。 */ class ArrayST<Key extends Comparable<Key>, Value> { private Key[] keys; private Value[] vals; private int count; //数组中元素的个数 private int capacity; //数组容量 public ArrayST(int capacity) { this.capacity = capacity; //必要情况下可以扩容 this.count = 0; this.keys = (Key[]) new Comparable[capacity]; this.vals = (Value[]) new Object[capacity]; } public ArrayST() { this(100); } /** * 根据键获取值 * 注意点： rank()方法返回的数组索引是向上取整的 * * @param key * @return */ public Value get(Key key) { int index = rank(key); //需要通过以下两条来判断是否找到相同的键 //使用compareTo方法来判断是否相等，而不是直接使用== if (index < count && keys[index].compareTo(key) == 0) { //index在有效元素的索引范围内（index为向上取整，很有可能会超出数组的范围）；检查index所在位置的值是否相同 return vals[index]; } return null; } public void put(Key key, Value val) { int index = rank(key); if (index < count && keys[index] == key) { //找到对应的键 vals[index] = val; return; } ensureCapacity(); //添加前确保数组的容量 for (int i = count - 1; i >= index; i--) { //后移 keys[i + 1] = keys[i]; vals[i + 1] = vals[i]; } keys[index] = key; vals[index] = val; count++; } public Value delete(Key key) { int index = rank(key); if (index < count && keys[index] == key) { //找到对应的键 Value tempVal = vals[index]; for (int i = index + 1; i < count; i++) { keys[i - 1] = keys[i]; vals[i - 1] = vals[i]; } keys[count - 1] = null; vals[count - 1] = null; count--; ensureCapacity(); return tempVal; } return null; } /** * 该数据结构的关键 * 这里使用循环实现的二分法查找 * 注意点：空数组的情况； 返回lo，这里返回值是rank的向上取整值 * * @param key * @return */ public int rank(Key key) { if (keys.length == 0) ;//空数组的情况 int lo = 0; int hi = count - 1; int mid = 0; while (lo <= hi) { mid = lo + (hi - lo) / 2; int cmp = keys[mid].compareTo(key); if (cmp < 0) lo = mid + 1; else if (cmp > 0) hi = mid - 1; else return mid; //找到键 } return lo; //向上取整 } private void resize(int newCapacity) { Key[] newkeys = (Key[]) new Comparable[newCapacity]; Value[] newvals = (Value[]) new Object[newCapacity]; for (int i = 0; i < count; i++) { newkeys[i] = keys[i]; newvals[i] = vals[i]; } this.keys = newkeys; this.vals = newvals; System.out.println("resize capacite down"); capacity = newCapacity; } public void ensureCapacity() { if (count > capacity / 2) resize(capacity * 2); if (count > 0 && count < capacity / 8) resize(capacity / 2); } public void exch(int a, int b) { //交换两处索引对应的键值对 Key tempKey = keys[a]; Value tempVal = vals[a]; keys[a] = keys[b]; vals[a] = vals[b]; keys[b] = tempKey; vals[b] = tempVal; } public int size() { return count; } public void display() { for (int i = 0; i < count; i++) { System.out.print(keys[i] + " "); } System.out.println(); for (int i = 0; i < count; i++) { System.out.print(vals[i] + " "); } System.out.println(); } } /** * @ClassName BinaryTree * @Author wangyudi * @Version 1.0 * @Description 二叉数数据结构 * 成员变量：根结点 root 结点类 Node * 成员方法：大小 size、获取值 get、加入值 put、 * 最大键 max、最小键 min、向下取整floor、向上取整ceiling、 * 根据排名选择 select、排名 rank、 * 删除最小键 deleteMin、删除任意键 delete; */ class BinaryTree<Key extends Comparable<Key>, Value> { public Node root; //只需要一个根结点便可以访问整个二叉树 private class Node { Key key; Value val; Node left; Node right; int size; //用于rank() select()方法 public Node(Key key, Value val, Node left, Node right, int size) { this.key = key; this.val = val; this.left = left; this.right = right; this.size = size; } } public BinaryTree() { root = null; } public int size() { return size(root); } public int size(Node node) { if (node == null) return 0; // return size(node.left)+size(node.right)+1; //这种递归的方法不好，要充分利用节点中保存的size return node.size; } public void display() { display(root); } public void display(Node node) { if (node == null) return; //中序遍历 display(node.left); System.out.print(node.val + " "); display(node.right); } public void put(Key key, Value val) { root = put(key, val, root);//注意 } public Node put(Key key, Value val, Node node) { //需要向父亲接返回子节点 if (node == null) { //没有找到 return new Node(key, val, null, null, 1); } int cmp = key.compareTo(node.key); if (cmp < 0) node.left = put(key, val, node.left); else if (cmp > 0) node.right = put(key, val, node.right); else { //找到相同的键 node.val = val; return node; } node.size = 1 + size(node.right) + size(node.left); return node; } public Value get(Key key) { return get(root, key); } public Value get(Node node, Key key) { if (node == null) return null; //没有找到 int cmp = key.compareTo(node.key); if (cmp < 0) return get(node.left, key); else if (cmp > 0) return get(node.right, key); else return node.val; } /** * 从二叉树中删除一个结点 * 找到结点并删除的情况有四种： * 只有左结点 * 只有右结点 * 没有结点 * 有两个结点 * * @param key * @return */ public void delete(Key key) { root = delete(key, root); } public Node delete(Key key, Node node) { if (node == null) return null; //do not find the target node int cmp = key.compareTo(node.key); if (cmp < 0) node.left = delete(key, node.left); else if (cmp > 0) node.right = delete(key, node.right); else { //找到需要删除的结点 分为四种情况 if (node.left == null) return node.right; if (node.right == null) return node.left; //删除的结点有两个子节点 后续结点为右子树中的最小结点 Node temp = node; //保存即将删除的接点 node = min(node.right);//后继接点是右子树中的最小键 同时需要将该后继接点返回 node.right = deleteMin(node.right); node.left = temp.left; } node.size = 1 + size(node.left) + size(node.right); return node; } public Node deleteMin() { return deleteMin(root); } public Node deleteMin(Node node) { if (node == null) return null; if (node.left == null) { return node.right; } node.left = deleteMin(node.left); node.size = 1 + size(node.left) + size(node.right); return node; } public Node min(Node node) { if (node.left == null) return node; return min(node.left); } /** * 向下取整 * * @param key * @param node * @return */ public Node floor(Key key, Node node) { if (node == null) return null; int cmp = key.compareTo(node.key); if (cmp < 0) return floor(key, node.left);//左子树中 else if (cmp == 0) return node; else { //向下取整结点为根节点或者是在右子树中的 Node temp = floor(key, node.right); if (temp != null) return temp; return node; } } public int rank(Key key, Node node) { if (node == null) return 0; int cmp = key.compareTo(node.key); if (cmp < 0) return rank(key, node.left); else if (cmp > 0) return 1 + size(node.left) + rank(key, node.right); else return size(node.left); } public Node select(int k) { return select(k, root); } public Node select(int k, Node node) { if (k < 0 || node == null) return null; //非法输入 int leftSize = size(node.left); if (leftSize == k) return node; else if (leftSize < 0) { return select(k - 1 - size(node.left), node.right); //-1 是根节点 } else { return select(k, node.left); } } } /** * @ClassName RedBlackTree * @Author wangyudi * @Date 2019/7/2 20:57 * @Version 1.0 * @Description 红黑树：在二叉树的基础上增加了红键和黑键，保证了树的平衡性。（除了put delete方法，其他方法与二叉树共用） * 增改put 查get * 注意：在红黑树中，不允许有红右键、不允许有两个连续的红键、不允许有两个红子节点。 * 实现上述要求的红黑二叉树与2-3树等价，能够满足平衡性 */ class RedBlackTree<Key extends Comparable<Key>, Value> { private Node root; private class Node { Key key; Value val; Node left; Node right; boolean color; int size; public Node(Key key, Value val, Node left, Node right, boolean color, int size) { this.key = key; this.val = val; this.left = left; this.right = right; this.color = color; this.size = size; } } public void display() { display(root); } public void display(Node node) { if (node == null) return; display(node.left); System.out.print(node.val); display(node.right); } /** * 查找（与二叉树一致） * * @param key * @return */ public Value get(Key key) { return get(key, root); } public Value get(Key key, Node node) { if (node == null) return null; int cmp = key.compareTo(node.key); if (cmp < 0) return get(key, node.left); else if (cmp > 0) return get(key, node.right); else { return node.val; } } /** * 向红黑树中插入键值对 * 注意点：查询等不需要改变红黑树结构的方法与二叉树一致 * 没有实现比较困难的删除方法 * * @param key * @param val */ public void put(Key key, Value val) { root = put(key, val, root); root.color = false; } public Node put(Key key, Value val, Node node) { //没有找到结点，则插入一个红结点 if (node == null) return new Node(key, val, null, null, true, 1); int cmp = key.compareTo(node.key); if (cmp < 0) node.left = put(key, val, node.left); else if (cmp > 0) node.right = put(key, val, node.right); else { //在树中找到结点 node.val = val; return node; } //沿着查询的路线回归 //回归的过程中，对父节点进行相应的操作，以保证树的平衡性（记住） if (isRed(node.right) && !isRed(node.left)) node = rotateLeft(node); if (isRed(node.left) && isRed(node.left.left)) node = rotateRight(node); if (isRed(node.left) && isRed(node.right)) node = filpColor(node); node.size = 1 + size(node.right) + size(node.left); return node; } /** * 将右红节点旋转到左边 * * @param node * @return */ private Node rotateLeft(Node node) { Node temp = node; node = temp.right; //需要返回的节点 temp.right = node.left; node.left = temp; node.color = temp.color; node.size = temp.size; temp.color = true; temp.size = 1 + size(node.left) + size(node.right); return node; } private Node rotateRight(Node node) { Node temp = node; node = temp.left; temp.left = node.right; node.right = temp; node.color = temp.color; node.size = temp.size; temp.color = true; temp.size = 1 + size(node.left) + size(node.right); return node; } /** * 处理两个节点都是红节点的情况 * * @param node * @return */ private Node filpColor(Node node) { node.color = true; node.right.color = node.left.color = false; return node; } private boolean isRed(Node node) { if (node == null) return false; return node.color; } private int size(Node node) { if (node == null) return 0; return node.size; } } /** * @ClassName SeparateChainHashST * @Author wangyudi * @Date 2019/7/2 22:25 * @Version 1.0 * @Description 拉链法散列表（哈希表） * 数组和链表的组合 * 需要解决的问题：1 散列值的计算 2 解决冲突碰撞 * <p> * 成员变量： 保存链表的数组 数组的大小 键值对数 * 方法：get put delete */ class SeparateChainHashST<Key extends Comparable<Key>, Value> { private Chain<Key, Value>[] st; //链表对象数组 private int capacity; private int count; public SeparateChainHashST(int capacity) { this.capacity = capacity; this.st = (Chain<Key, Value>[]) new Chain[capacity]; //注意： 数组初始化 for (int i = 0; i < capacity; i++) { st[i] = new Chain<Key, Value>(); } this.count = 0; } public SeparateChainHashST() { this(996); } public int size() { return count; } private int hash(Key key) { if (key == null) return -1; return (key.hashCode() & 0x7FFFFFFF) % capacity; } //关于拉链法实现的哈希表的方法 //第一步，根据哈希值找到相应的数组中存储的链表 //第二步，接下来的增删改查是链表的问题 public Value get(Key key) { int index = hash(key); return st[index].get(key); } public void put(Key key, Value val) { int index = hash(key); if (st[index].put(key, val)) count++; //插入的情况加 1 } public Value delete(Key key) { int index = hash(key); Value val = st[index].delete(key); if (val != null) count--; return val; } public void display() { for (int i = 0; i < capacity; i++) { for (Object[] info : st[i]) { System.out.println((Value) info[1]); } } } } /** * 用于实现拉链法哈希表的链表数据结构 * * @param <Key> * @param <Value> */ class Chain<Key extends Comparable<Key>, Value> implements Iterable<Object[]> { private Node first; private class Node { Key key; Value value; Node next; public Node(Key key, Value value, Node next) { this.key = key; this.value = value; this.next = next; } } public Value get(Key key) { for (Node i = first; i != null; i = i.next) { //遍历查找 if (i.key == key) { return i.value; //找到则返回 } } return null; } public boolean put(Key key, Value value) { for (Node i = first; i != null; i = i.next) { if (key.compareTo(i.key) == 0) { i.value = value; return false; //找到相同的键 } } first = new Node(key, value, first); return true;//在头部加入键值对 } /** * 删除单向链表中的某一个结点 * * @param key * @return */ public Value delete(Key key) { Node f = null; //保存前一结点的信息 Node b = first; while (b != null && b.key != key) { f = b; b = b.next; } if (b != null) { //找到要删除的对象 Value val = null; if (f == null) { val = first.value; first = b.next; //特殊处理 } else { val = b.value; f.next = b.next; } b.next = null;//为了尽快GC b = null; return val; } return null; } @Override public Iterator<Object[]> iterator() { return new Iterator() { Node i = first; @Override public boolean hasNext() { if (i != null) return true; return false; } @Override public Object[] next() { Key tempkey = i.key; Value tempValue = i.value; Object[] info = new Object[]{(Object) tempkey, (Object) tempValue}; i = i.next; return info; } }; } } /** * @ClassName LinearProbeHashST * @Author wangyudi * @Date 2019/7/3 10:53 * @Version 1.0 * @Description 用线性试探法实现哈希表 * <p> * 成员变量： 键数组 值数组 容量 键值对数量 * 成员方法： get put delete resize */ class LinearProbeHashST<Key extends Comparable<Key>, Value> { private Key[] keys; private Value[] vals; private int count; private int capacity; public LinearProbeHashST(int capacity) { this.capacity = capacity; this.count = 0; keys = (Key[]) new Comparable[capacity]; vals = (Value[]) new Object[capacity]; } public LinearProbeHashST() { this(100); } private int hash(Key key) { if (key == null) return -1; return (key.hashCode() & 0x7FFFFFFF) % capacity; } public Value get(Key key) { int index = hash(key); while (keys[index] != null) { //在NULL之前遍历查找，如果找到则直接返回 if (keys[index] == key) return vals[index]; index = (index + 1) % capacity; } return null; } public void put(Key key, Value val) { ensureCapacity(); //调整容量大小会影响哈希值的计算 int index = hash(key); for (; keys[index] != null; index = (index + 1) % capacity) { if (key.compareTo(keys[index])==0) { vals[index] = val; //找到相同的值，用ComparaTo()比较 return; } } keys[index] = key; vals[index] = val; count++; } /** * 删除之后，被删除键值对后面的键值对需要重新插入 * * @param key * @return */ public Value delete(Key key) { int index = hash(key); Value retVal = null; while (keys[index] != null) { if (keys[index] == key) {//找到相同的键 retVal = vals[index]; keys[index] = null; vals[index] = null; count--; } index = (index + 1) % capacity; } //如果没有删除，则指向null //如果删除，index指向被删除键值对的下一键值对 while (keys[index] != null) { Key tempKey = keys[index]; Value tempVal = vals[index]; keys[index] = null; vals[index] = null; count--; put(tempKey, tempVal); index = (index + 1) % capacity; } ensureCapacity(); return retVal; } public void ensureCapacity() { if (count > capacity / 2) resize(capacity * 2); if (count > 0 && count < capacity / 8) resize(capacity / 2); } public void resize(int newCapacity) { LinearProbeHashST<Key, Value> tempST = new LinearProbeHashST<>(newCapacity); //该临时哈希表也会调用resize() for (int i = 0; i < capacity; i++) { if (keys[i] != null) { tempST.put(keys[i], vals[i]); tempST.count++; }//注意：遍历所有键值对，只对键不为空的对象操作 } // capacity = newCapacity;//错误，临时哈希表也会调用resize()，导致capacity出错 capacity = tempST.capacity; keys = tempST.keys; vals = tempST.vals; } /** * 返回实现迭代器的对象 * * @return */ public Iterable<Key> keys() { ArrayList<Key> arr = new ArrayList<>(); for (int i = 0; i < capacity; i++) { if (keys[i] != null) { arr.add(keys[i]); } } return arr; } } class TestCase { public static void main(String[] args) { //无序符号表 LinkedST<Integer, String> st = new LinkedST<>(); st.put(3, "3.."); st.put(7, "7.."); st.put(64, "64.."); st.put(23, "23.."); st.put(11, "11.."); st.delete(64); for (String e : st) { System.out.println(e); } System.out.println("================="); //有序符号表 ArrayST<Integer, String> st2 = new ArrayST<>(); st2.put(5, "5.."); st2.put(2, "2.."); st2.put(34, "34.."); st2.put(17, "17.."); st2.put(55, "55.."); st2.put(214, "214.."); st2.delete(34); System.out.println(st2.get(214)); System.out.println(st2.size()); st2.display(); System.out.println("================="); //二叉树 BinaryTree<Integer, String> tree = new BinaryTree<>(); tree.put(12, "12.."); tree.put(2, "2.."); tree.put(34, "34.."); tree.put(17, "17.."); tree.put(55, "55.."); tree.put(214, "214.."); tree.display(); System.out.println(); tree.deleteMin(); tree.delete(12); tree.delete(222); tree.delete(214); tree.display(); System.out.println(); System.out.println(tree.select(0)); System.out.println(tree.rank(55, tree.root)); System.out.println("================="); //红黑树 System.out.println("------------------对二叉树的测试---------------------"); RedBlackTree<Integer, String> blackRedTree = new RedBlackTree<>(); blackRedTree.put(12, "12.."); blackRedTree.put(2, "2.."); blackRedTree.put(34, "34.."); blackRedTree.put(17, "17.."); blackRedTree.put(55, "55.."); blackRedTree.put(214, "214.."); blackRedTree.display(); System.out.println(); System.out.println("================="); //拉链法哈希表 SeparateChainHashST<Integer, String> separateChainHashST = new SeparateChainHashST<>(100); separateChainHashST.put(12, "12.."); separateChainHashST.put(2, "2.."); separateChainHashST.put(34, "34.."); separateChainHashST.put(17, "17.."); separateChainHashST.put(55, "55.."); separateChainHashST.put(214, "214.."); separateChainHashST.put(12, "12.."); separateChainHashST.put(2, "2.."); separateChainHashST.put(34, "34.."); separateChainHashST.put(17, "17.."); separateChainHashST.put(55, "55.."); separateChainHashST.put(214, "214.."); separateChainHashST.display(); System.out.println("===="); separateChainHashST.delete(34); separateChainHashST.display(); System.out.println("====="); System.out.println(separateChainHashST.get(17)); System.out.println("==="); System.out.println(separateChainHashST.size()); //线性探测法哈希表 System.out.println("-------------线性探测法哈希表----------------"); LinearProbeHashST<Integer, String> linearProbeHashST = new LinearProbeHashST<>(); linearProbeHashST.put(12, "12.."); linearProbeHashST.put(2, "2.."); linearProbeHashST.put(34, "34.."); linearProbeHashST.put(17, "17.."); linearProbeHashST.put(55, "55.."); linearProbeHashST.put(214, "214.."); for (Integer i : linearProbeHashST.keys()) { System.out.println(i); } System.out.println("delete key 34"); System.out.println(linearProbeHashST.delete(34)); System.out.println("show all keys"); for (Integer i : linearProbeHashST.keys()) { System.out.println(i); } System.out.println("get value of key 55"); System.out.println(linearProbeHashST.get(55)); } }