哈希表C语言程序设计：二叉堆、队列、堆和哈希表

[TOC]

本文介绍几种常见的数据结构:栈、队列、堆、哈希表，等等。

写在前面Stacks(栈)

LIFO(后进先出):last in first out.

保存指向第一个节点的指针，每次从前面插入／删除节点。

以字符串栈为例，示例代码：

public class LinkedStackOfStrings {    private Node first = null;    private class Node {        String item;        Node next;    }    public boolean isEmpty() {        return first == null;    }    public void push(String item) {        Node oldfirst = first;        first = new Node();        first.item = item;        first.next = oldfirst;    }    public String pop() {        String item = first.item;        first = first.next;        return item;    }}

使用数组来存储栈中的项

public class FixedCapacityStackOfStrings {    private String[] s;    private int N = 0;    public FixedCapacityStackOfStrings(int capacity) {        s = new String[capacity];    }    public boolean isEmpty() {        return N == 0;    }    public void push(String item) {        s[N++] = item;    }    public String pop() {        String item = s[--N];        s[N] = null;        return item;    }}

上面的实现会有几个问题：

从空栈pop会抛出异常

插入元素过多会超出数组上界

这里重点解决第二个问题，resizing arrays.一个可行的方案是: 当数组满的时候，数组大小加倍；当数组是1/4满的时候，数组大小减半。 这里不是在数组半满时削减size,这样可以避免数组在将满未满的临界点多次push-pop-push-pop操作造成大量的数组拷贝操作。

插入N个元素，N + (2 + 4 + 8 + … + N) ~ 3N。

由于resize操作不是经常发生，所以均摊下来，平均每次push/pop操作的还是常量时间(constant amortized time).

Queues(队列)

FIFO(先进先出):first in first out.

保存指向首尾节点的指针，每次从链表尾插入，从链表头删除。

public class LinkedQueueOfStrings {    private Node first, last;    private class Node {          /* same as in StackOfStrings */    }    public boolean isEmpty() {        return first == null;    }    public void enqueue(String item) {        Node oldlast = last;        last = new Node();        last.item = item;        last.next = null;        if (isEmpty()) {            first = last;        } else {            oldlast.next = last;        }    }    public String dequeue() {        String item = first.item;        first = first.next;        if (isEmpty()) last = null;        return item;    }}

・Use array q[] to store items in queue.・enqueue(): add new item at q[tail].・dequeue(): remove item from q[head].・Update head and tail modulo the capacity.・Add resizing array.

Priority Queues

Collections. Insert and delete items.

unordered array 实现

public class UnorderedMaxPQ<Key extends Comparable> {    private Key[] pq;   // pq[i] = ith element on pq    private int N;      // number of elements on pq    public UnorderedMaxPQ(int capacity) {        pq = (Key[]) new Comparable[capacity];    }    public boolean isEmpty() {        return N == 0;    }    public void insert(Key x) {        pq[N++] = x;    }    public Key delMax() {        int max = 0;        for (int i = 1; i < N; i++)            if (less(max, i)) max = i;        exch(max, N - 1);        return pq[--N];    }}

Binary Heaps(二叉堆)

使用数组来表示一个二叉堆。根节点索引从1开始。索引对应在树中的位置，最大的键值是a[1],同时也是二叉树的根节点。

上浮和下沉

有两种情况会触发节点移动：

子节点的键值变为比父节点大

父节点的键值变为比子节点（一个或两个）小

而 要消除这种违反最大堆定义的结构，就需要进行节点移动和交换， 使之满足父节点键值不小于两个子节点 。对应的操作分别是 上浮 和 下沉

下沉：父节点key比子节点（one or both）小

/* 上浮 */private void swim(int k) {    while (k > 1 && less(k / 2, k)) {        exch(k, k / 2);        k = k / 2;    }}/* 下沉 */private void sink(int k) {   while (2 * k <= N) {       int j = 2 * k;       if (j < N && less(j, j + 1)) j++;       if (!less(k, j)) break;       exch(k, j);       k = j;   }}

插入和删除

所有操作（插入和删除）都保证在log N 时间内。

/* 插入 */public void insert(Key x){  pq[++N] = x;  swim(N);}/* 删除 */public Key delMax(){  Key max = pq[1];  exch(1, N--);  sink(1);  pq[N+1]=null;  return max;}

最后，堆中的键值是不能变的，即Immutable.不然就不能保证父节点不小于子节点。

Symbol Tables

键值对的抽象.其中键一般使用immutable的类型，值是任何普通类型。

关于比较哈希表，所有的java类都继承了equals()方法，要求对于引用x,y,z

对于用户自定义的类型，一般按如下流程实现equals()方法:

两种实现的数据结构：

无序链表：Maintain an (unordered) linked list of key-value pairs.

有序数组：Maintain an ordered array of key-value pairs.

在有序数组进行查找时使用二分查找。两种方式的对比如下图：

Hash Tables(哈希表)

上面几种数据结构都是通过遍历或者二分查找去搜寻某个元素，而哈希表则是通过一个key-indexed table来存储其中的项，即“索引”是“键”的一个函数。换句话说，哈希是通过定义一种函数/计算方法，把键直接映射成一个哈希值（再通过取余操作换算成数组的下标索引），从而定位元素，而避免耗时的逐个比较和遍历的操作。

//这里hashCode可能为负，且-2^31取绝对值会溢出，所以要“位与”private int hash(Key key){    return (key.hashCode() & 0x7fffffff) % M;  }

所有的java类均继承了hashCode()方法来计算哈希值, 返回一个32-bit的int.默认实现是返回该对象的内存地址。对常用的类型有自己的实现，以java的String类为例子：

public int hashCode() {    int h = hash;    if (h == 0 && value.length > 0) {        char val[] = value;        for (int i = 0; i < value.length; i++) {            h = 31 * h + val[i];        }        hash = h;    }    return h;}

hash code design.”Standard” recipe for user-defined types：

当然，这种映射并不能保证是一对一的，所以一定会出现多个键映射到同一个哈希值的尴尬情况（尤其是对数组的size取余操作后,映射到同一数组下标），即哈希冲突哈希表，这是就需要一些方法来解决。这里介绍两种常用的方法：

separate chaining

Use an array of M < N linked lists.

linear probing

开放地址：如果发生冲突，将值放入下一个空的位置.(数组尺寸 M 必须比键值对的数目 N 要多.)

作者@brianway更多文章：个人网站 | CSDN | oschina