哈希表C语言程序设计:二叉堆、队列、堆和哈希表
哈希表C语言程序设计:二叉堆、队列、堆和哈希表本文介绍几种常见的数据结构:栈、队列、堆、哈希表,等等。以字符串栈为例,示例代码:使用数组来存储栈中的项使用数组来表示一个二叉堆。table来存储其中的项,即“索引”是“键”的一个函数。换句话说,哈希是通过定义一种函数/计算方法,把键直接映射成一个哈希值(再通过取余操作换算成数组的下标索引),从而定位元素,而避免耗时的逐个比较和遍历的操作。
[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