正文
算法(第4版) (Robert Sedgewick / Kevin Wayne 著)
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
第1章 基础
第2章 排序
第3章 查找
第4章 图
第5章 字符串
第1章 基础
public class Bag<T> : IEnumerable<T> {
];
;
public void Add(T t) {
values[count++] = u;
}
public bool IsEmpty() {
;
}
public int Size() {
return count;
}
public IEnumerator<T> GetEnumerator() {
; i < count; i++) {
yield return values[i];
}
}
IEnumerator IEnumerable.GetEnumerator() {
return GetEnumerator();
}
}
Bag 数组实现
public class Stack<T> : IEnumerable<T> {
];
;
public void Push(T t) {
values[count++] = t;
}
public T Pop() {
return values[--count];
}
public bool IsEmpty() {
;
}
public int Size() {
return count;
}
public IEnumerator<T> GetEnumerator() {
; i >= ; i--) {
yield return values[i];
}
}
IEnumerator IEnumerable.GetEnumerator() {
return GetEnumerator();
}
}
Stack 数组实现
public class Queue<T> : IEnumerable<T> {
];
;
;
public void Enqueue(T t) {
values[tail++] = t;
}
public T Dequeue() {
return values[head++];
}
public bool IsEmpty() {
return head == tail;
}
public int Size() {
return tail - head;
}
public IEnumerator<T> GetEnumerator() {
for (int i = head; i < tail; i++) {
yield return values[i];
}
}
IEnumerator IEnumerable.GetEnumerator() {
return GetEnumerator();
}
}
Queue 数组实现
第2章 排序
选择排序 SelectionSort : 选择剩余元素之中的最小者
命题A:对于长度为N的数组,选择排序需要大于(NxN)/2次比较和N次交换
public class SelectionSort {
static public void Sort(int[] arr) {
; i < arr.Length; i++) {
int min = i;
for (int j = i; j < arr.Length; j++) {
if(arr[j] < arr[min]) {
min = j;
}
}
Exchange(arr, min, i);
}
}
static public void Exchange(int[] arr,int a,int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
2.1 选择排序
插入排序 InsertionSort : 想象初始手里有一张牌,每次从牌堆里拿一张牌有序插入手中的牌里.
倒置 指的是数组中的两个顺序颠倒的元素.
命题B:对于随机排列的长度为N且主键不重复的数组,平均情况下插入排序需要~(NxN)/4次比较以及~(NxN)/4次交换.最坏情况下需要~(NxN)/2次比较和~(NxN)/2次交换,最好情况下需要N-1次比较和0次交换
命题C:插入排序需要的交换操作和数组中倒置的数量相同,需要的比较次数大于等于倒置的数量,小于等于倒置的数量加上数组的大小再减一
public class InsertionSort {
static public void Sort(int[] arr) {
; i < arr.Length; i++) {
; j--) {
]) {
Exchange(arr, j, j - );
}
}
}
}
static public void Exchange(int[] arr,int a,int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
2.2 插入排序
希尔排序:ShellSort : 希尔排序的思想是使数组中任意间隔为h的元素都是有序的.这样的数组被称为h有序数组
public class ShellSort {
static public void Sort(int[] arr) {
int n = arr.Length;
;
) {
h = * h + ;
}
) {
for (int i = h; i < n; i++) {
for (int j = i; j >= h; j -= h) {
if(arr[j] < arr[j - h]) {
Exchange(arr, j, j - h);
}
}
}
h = h / ;
}
}
static public void Exchange(int[] arr,int a,int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
2.3 希尔排序
归并排序:MergeSort
public class Merge {
private static IComparable[] auxiliary;
public static void Sort(IComparable[] a) {
auxiliary = new IComparable[a.Length];
Sort(a, , a.Length - );
}
private static void Sort(IComparable[] a,int lo,int hi) {
if(hi <= lo) {
return;
}
;
Sort(a, lo, mid);
Sort(a, mid + , hi);
MergeMethod(a, lo, mid, hi);
}
public static void MergeMethod(IComparable[] a,int lo,int mid,int hi) {
int i = lo;
;
for (int k = lo; k <= hi; k++) {
auxiliary[k] = a[k];
}
for (int k = lo; k <= hi; k++) {
if (i > mid) {
a[k] = auxiliary[j++];
} else if (j > hi) {
a[k] = auxiliary[i++];
} else if (Less(auxiliary[j], auxiliary[i])) {
a[k] = auxiliary[j++];
} else {
a[k] = auxiliary[i++];
}
}
}
public static bool Less(IComparable a,IComparable b) {
) {
return true;
} else {
return false;
}
}
}
2.4 自顶向下的归并排序
快速排序:QuickSort
public class Quick {
public static void Sort(IComparable[] a) {
Sort(a, , a.Length - );
}
private static void Sort(IComparable[] a,int lo,int hi) {
if(hi <= lo) {
return;
}
int j = Partition(a, lo, hi);
Sort(a, lo, j - );
Sort(a, j + , hi);
}
private static int Partition(IComparable[] a,int lo, int hi) {
// 将数组切分为a[lo...i-1],a[i],a[i+1...hi]
int i = lo; // 左扫描指针
; // 右扫描指针
IComparable v = a[lo]; // 切分元素
while (true) {
while (Less(a[++i], v)) {
if(i == hi) {
break;
}
}
while (Less(v, a[--j])) {
if (j == lo) {
break;
}
}
if (i >= j) {
break;
}
Exchange(a, i, j);
}
Exchange(a, lo, j);
return j;
}
private static bool Less(IComparable a,IComparable b) {
) {
return true;
} else {
return false;
}
}
private static void Exchange(IComparable[] a,int i,int j) {
IComparable v = a[i];
a[i] = a[j];
a[j] = v;
}
}
2.5 快速排序
三向快速排序:
定义 当一个二叉树的每个结点都大于等于它的两个子结点时,它被称为堆有序
定义 二叉堆是一组能够用堆有序的完全二叉树排序的元素,并在数组中按照层级储存(不使用数组的第一个位置)
public class MaxPriorityQueue<Key> where Key : IComparable {
public Key[] m_pq;
;
public MaxPriorityQueue(int n) {
m_pq = ];
}
public bool IsEmpty() {
;
}
public int Size() {
return m_n;
}
public void Insert(Key key) {
m_pq[++m_n] = key;
Swim(m_n);
}
public Key DelMax() {
Key max = m_pq[];
Exchange(, m_n--);
m_pq[m_n + ] = default(Key);
Sink();
return max;
}
private bool Less(int i,int j) {
;
}
private void Exchange(int i,int j) {
Key k = m_pq[i];
m_pq[i] = m_pq[j];
m_pq[j] = k;
}
private void Swim(int k) {
&& Less(k / , k)) {
Exchange(k / , k);
k = k / ;
}
}
private void Sink(int k) {
* k <= m_n) {
* k;
)) {
j++;
}
if (!Less(k, j)) {
break;
}
Exchange(k, j);
k = j;
}
}
}
2.6 基于堆的优先队列
public class IndexMinPQ<Item extends Comparable<Item>>
IndexMinPQ(
void Insert(int k,Item item) 插入一个元素,将它和索引k相关联
void Change(int k,Item item) 将索引为k的元素设为item
bool Contains(int k) 是否存在索引为k的元素
void Delete(int k) 删去索引k及其相关联的元素
Item Min() 返回最小元素
int MinIndex() 返回最小元素的索引
int DelMin() 删除最小元素并返回它的索引
bool IsEmpty() 优先队列是否为空
int Size() 优先队列中的元素数量
关联索引的泛型优先队列的API
public class IndexMinPQ<Key> where Key : IComparable<Key> {
private int m_maxN;
private int m_n;
private int[] m_pq;
private int[] m_qp;
private Key[] m_keys;
public IndexMinPQ(int maxN) {
) {
throw new ArgumentOutOfRangeException();
}
m_maxN = maxN;
m_n = ;
m_keys = ];
m_pq = ];
m_qp = ];
; i <= maxN; i++) {
m_qp[i] = -;
}
}
public bool IsEmpty() {
;
}
public bool Contains(int i) {
|| i >= m_maxN) {
throw new ArgumentOutOfRangeException();
}
;
}
public int Size() {
return m_n;
}
public void Insert(int i,Key key) {
|| i >= m_maxN) {
throw new ArgumentOutOfRangeException();
}
if (Contains(i)) {
throw new ArgumentOutOfRangeException("index is already in the priority queue");
}
m_n++;
m_pq[m_n] = i;
m_qp[i] = m_n;
m_keys[i] = key;
Swim(m_n);
}
public int MinIndex() {
) {
throw new ArgumentNullException("Priority queue underflow");
}
];
}
public Key MinKey() {
) {
throw new ArgumentNullException("Priority queue underflow");
}
]];
}
public int DelMin() {
) {
throw new ArgumentNullException("Priority queue underflow");
}
];
Exchange(, m_n--);
Sink();
Trace.Assert(min == m_pq[m_n + ]);
m_keys[min] = default(Key);
m_pq[m_n + ] = -;
m_qp[min] = -;
return min;
}
public Key KeyOf(int i) {
|| i >= m_maxN) {
throw new ArgumentOutOfRangeException();
}
if (!Contains(i)) {
throw new ArgumentNullException("index is not in the priority queue");
} else {
return m_keys[i];
}
}
public void ChangeKey(int i,Key key) {
|| i >= m_maxN) {
throw new ArgumentOutOfRangeException();
}
if (!Contains(i)) {
throw new ArgumentOutOfRangeException("index is not in the priority queue");
}
m_keys[i] = key;
Swim(m_qp[i]);
Sink(m_qp[i]);
}
public void DecreaseKey(int i,Key key) {
|| i >= m_maxN) {
throw new ArgumentOutOfRangeException();
}
if (!Contains(i)) {
throw new ArgumentNullException("index is not in the priority queue");
}
) {
throw new ArgumentOutOfRangeException("Calling DecreaseKey() with given argument would not strictly decrease the key");
}
m_keys[i] = key;
Swim(m_qp[i]);
}
public void InCreaseKey(int i,Key key) {
|| i >= m_maxN) {
throw new ArgumentOutOfRangeException();
}
if (!Contains(i)) {
throw new ArgumentNullException("index is not in the priority queue");
}
) {
throw new ArgumentOutOfRangeException("Calling InCreaseKey() with given argument would not strictly increase the key");
}
m_keys[i] = key;
Sink(m_qp[i]);
}
public void Delete(int i) {
|| i >= m_maxN) {
throw new ArgumentOutOfRangeException();
}
if (!Contains(i)) {
throw new ArgumentNullException("index is not in the priority queue");
}
int index = m_qp[i];
Exchange(index, m_n--);
Swim(index);
Sink(index);
m_keys[i] = default(Key);
m_qp[i] = -;
}
private bool Greater(int i,int j) {
;
}
private void Exchange(int i,int j) {
int swap = m_pq[i];
m_pq[i] = m_pq[j];
m_pq[j] = swap;
m_qp[m_pq[i]] = i;
m_qp[m_pq[j]] = j;
}
private void Swim(int k) {
&& Greater(k / , k)) {
Exchange(k, k / );
k = k / ;
}
}
private void Sink(int k) {
* k <= m_n) {
* k;
)) {
j++;
}
if (!Greater(k, j)){
break;
}
Exchange(k, j);
k = j;
}
}
}
IndexMinPQ
public static void Sort(IComparable[] a) {
int N = a.Length;
; k >= ; k--) {
Sink(a, k, N);
) {
Exchange(a, , N--);
Sink(a, , N);
}
}
}
2.7 堆排序
第3章 查找
我们会使用符号表(Symbol Table)这个词来描述一张抽象的表格,我们会将信息(值)存储在其中,然后按照指定的键来搜索并获取这些信息.
符号表有时被称为字典,类似于那本将单词的释义按照字母顺序排列起来的历史悠久的参考书.
在英语字典里,键就是单词,值就是单词对应的定义,发音和词源.符号表有时又叫做索引,即书本最后将术语按照字母顺序列出以方便查找的那部分.
在一本书的索引中,键就是术语,而值就是书中该术语出现的所有页码.
定义: 符号表是一种存储键值对的数据结构,支持两种操作:插入(put),即将一组新的键值对存入表中;查找(get),即根据给定的键得到相应的值
public class SymbolTable<Key,Value>
SymbolTable() 创建一张符号表
void Put(Key key,Value value) 将键值对存入表中(若值为空则将键key从表中删除)
Value Get(Key key) 获取键key对应的值(若键key不存在则返回null)
void Delete(Key key) 从表中删除键key(及其对应的值)
bool Contains(Key key) 键key在表中是否有对应的值
bool IsEmpty() 表是否为空
int Size() 表中的键值对数量
Iterable<Key> Keys() 表中的所有键的集合
一种简单的泛型符号表API
public class SymbolTable<Key extends Comparable<key>,Value>
SymbolTable() 创建一张有序符号表
void Put(Key key,Value value) 将键值对存入表中(若值为空则将键key从表中删除)
Value Get(Key key) 获取键key对应的值(若键key不存在则返回null)
void Delete(Key key) 从表中删除键key(及其对应的值)
bool Contains(Key key) 键key在表中是否有对应的值
bool IsEmpty() 表是否为空
int Size() 表中的键值对数量
Key Min() 最小的键
Key Max() 最大的键
Key Floor(Key key) 小于等于key的最大键
Key Ceiling(Key key) 小于等于key的最小键
int Rank(Key key) 小于key的键的数量
Key Select(int k) 排名为k的键
void DeleteMin() 删除最小的键
void DeleteMax() 删除最大的键
int Size(Key lo,Key hi) [lo..hi]之间键的数量
Iterable<Key> Keys(Key lo,Key hi) [lo..hi]之间的所有键,已排序
Iterable<Key> Keys() 表中的所有键的集合,已排序
一种有序的泛型符号表API
顺序查找(基于无序链表)
在查找中我们一个一个地顺序遍历符号表中的所有键并使用equals()方法来寻找与被查找的键匹配的键
public class SequentialSearchSymbolTable<Key, Value> {
private class Node {
public Key m_key;
public Value m_value;
public Node m_next;
public Node(Key key,Value value,Node next) {
m_key = key;
m_value = value;
m_next = next;
}
}
private Node m_first;
public Value Get(Key key) {
for (Node x = m_first; x != null; x = x.m_next) {
if (key.Equals(x.m_key)) {
return x.m_value;
}
}
return default(Value);
}
public void Put(Key key, Value value) {
for (Node x = m_first; x != null; x = x.m_next) {
if (key.Equals(x.m_key)) {
x.m_value = value;
return;
}
}
m_first = new Node(key, value, m_first);
}
}
3.1 顺序查找(基于无序链表)
二分查找(基于有序数组)
public class BinarySearchSymbolTable<Key, Value> where Key:IComparable {
private Key[] m_keys;
private Value[] m_values;
private int N;
public BinarySearchSymbolTable(int capacity) {
m_keys = new Key[capacity];
m_values = new Value[capacity];
}
public int Size() {
return N;
}
//小于key的键的数量
public int Rank(Key key) {
;
;
while(lo <= hi) {
;
int cmp = key.CompareTo(m_keys[mid]);
) {
hi = mid - ;
} ) {
lo = mid + ;
} else {
return mid;
}
}
return lo;
}
public void Put(Key key,Value value) {
int i = Rank(key);
) {
m_values[i] = value;
return;
}
for (int j = N; j > i; j--) {
m_keys[j] = m_keys[j - ];
m_values[j] = m_values[j - ];
}
m_keys[i] = key;
m_values[i] = value;
N++;
}
public Value Get(Key key) {
if (IsEmpty()) {
return default(Value);
}
int i = Rank(key);
) {
return m_values[i];
} else {
return default(Value);
}
}
public void Delete(Key key) {
}
public bool IsEmpty() {
;
}
}
3.2 二分查找(基于有序数组)
二叉查找树
定义 : 一颗二叉查找树(BST)是一颗二叉树,其中每个节点都含有一个Comparable的键(以及相关联的值)且每个节点的键都大于其左子树中的任意结点的键而小于右子树的任意节点的键
public class BinarySearchTree<Key,Value> where Key : IComparable<Key> where Value:class {
public class Node {
public Key m_key;
public Value m_value;
public Node m_left;
public Node m_right;
public int m_count;
public Node(Key key,Value value,int count) {
m_key = key;
m_value = value;
m_count = count;
}
}
private Node m_root;
public int Size() {
return Size(m_root);
}
private int Size(Node node) {
if(node == null) {
;
} else {
return node.m_count;
}
}
public Value Get(Key key) {
return Get(m_root, key);
}
private Value Get(Node node,Key key) {
if(node == null) {
return null;
}
int cmp = key.CompareTo(node.m_key);
) {
return Get(node.m_left, key);
} ) {
return Get(node.m_right, key);
} else {
return node.m_value;
}
}
public void Put(Key key,Value value) {
m_root = Put(m_root, key, value);
}
private Node Put(Node node,Key key,Value value) {
if(node == null) {
);
}
int cmp = key.CompareTo(node.m_key);
) {
node.m_left = Put(node.m_left, key, value);
} ) {
node.m_right = Put(node.m_right, key, value);
} else {
node.m_value = value;
}
node.m_count = Size(node.m_left) + Size(node.m_right) + ;
return node;
}
public Key Min() {
return Min(m_root).m_key;
}
private Node Min(Node node) {
if(node.m_left == null) {
return node;
}
return Min(node.m_left);
}
public Key Max() {
return Max(m_root).m_key;
}
private Node Max(Node node) {
if(node.m_right == null) {
return node;
}
return Max(node.m_right);
}
public Key Floor(Key key) {
Node node = Floor(m_root, key);
if(node == null) {
return default(Key);
}
return node.m_key;
}
private Node Floor(Node node,Key key) {
if(node == null) {
return null;
}
int cmp = key.CompareTo(node.m_key);
) {
return node;
}
) {
return Floor(node.m_left, key);
}
Node n = Floor(node.m_right, key);
if(n != null) {
return n;
} else {
return node;
}
}
public Key Select(int k) {
return Select(m_root, k).m_key;
}
private Node Select(Node node,int k) {
if(node == null) {
return null;
}
int size = Size(node.m_left);
if(size > k) {
return Select(node.m_left, k);
} else if(size < k) {
);
} else {
return node;
}
}
public int Rank(Key key) {
return Rank(key, m_root);
}
private int Rank(Key key,Node node) {
if(node == null) {
;
}
int cmp = key.CompareTo(node.m_key);
) {
return Rank(key, node.m_left);
} ) {
+ Size(node.m_left) + Rank(key, node.m_right);
} else {
return Size(node.m_left);
}
}
public void DeleteMin() {
m_root = DeleteMin(m_root);
}
private Node DeleteMin(Node node) {
if(node.m_left == null) {
return node.m_right;
}
node.m_left = DeleteMin(node.m_left);
node.m_count = Size(node.m_left) + Size(node.m_right) + ;
return node;
}
public void Delete(Key key) {
m_root = Delete(m_root, key);
}
private Node Delete(Node node,Key key) {
if(node == null) {
return null;
}
int cmp = key.CompareTo(node.m_key);
) {
node.m_left = Delete(node.m_left, key);
} ) {
node.m_right = Delete(node.m_right, key);
} else {
if(node.m_right == null) {
return node.m_left;
}
if(node.m_left == null) {
return node.m_right;
}
Node n = node;
node = Min(n.m_right);
node.m_right = DeleteMin(n.m_right);
node.m_left = n.m_right;
}
node.m_count = Size(node.m_left) + Size(node.m_right) + ;
return node;
}
public IEnumerable<Key> Keys() {
return Keys(Min(), Max());
}
public IEnumerable<Key> Keys(Key lo,Key hi) {
Queue<Key> queue = new Queue<Key>();
Keys(m_root, queue, lo, hi);
return queue;
}
private void Keys(Node node,Queue<Key> queue,Key lo,Key hi) {
if(node == null) {
return;
}
int cmplo = lo.CompareTo(node.m_key);
int cmphi = hi.CompareTo(node.m_key);
) {
Keys(node.m_left, queue, lo, hi);
}
&& cmphi >= ) {
queue.Enqueue(node.m_key);
}
) {
Keys(node.m_right, queue, lo, hi);
}
}
}
3.3 基于二叉查找树的符号表
2-3查找树
定义 : 一棵2-3查找树或为一个空树,或由以下结点组成:
2- 结点,含有一个键(及其对应的值)和两条链接,左链接指向的2-3树中的键都小于该结点,右链接指向的2-3树中的键都大于该结点
3- 结点,含有两个键(及其对应的值)和三条链接,左链接指向的2-3树中的键都小于该结点,中链接指向的2-3树中的键都位于该结点的两个键之间,右链接指向的2-3树中的键都大于该结点
和以前一样,我们将指向一颗空树的链接称为空链接
public class RedBlackBST<Key,Value> where Key : IComparable<Key> {
public Node m_root;
public class Node {
public Key m_key;
public Value m_value;
public Node m_left, m_right;
public int m_n;
public bool m_color;
public Node(Key key,Value value,int n,bool color) {
m_key = key;
m_value = value;
m_n = n;
m_color = color;
}
}
public bool IsRed(Node x) {
if(x == null) {
return false;
}
return x.m_color == true;
}
public int Size(Node n) {
if(n == null) {
;
} else {
return n.m_n;
}
}
Node RotateLeft(Node h) {
Node x = h.m_right;
h.m_right = x.m_left;
x.m_left = h;
x.m_color = h.m_color;
h.m_color = true;
x.m_n = h.m_n;
h.m_n = + Size(h.m_left) + Size(h.m_right);
return x;
}
Node RotateRight(Node h) {
Node x = h.m_left;
h.m_left = x.m_right;
x.m_right = h;
x.m_color = h.m_color;
h.m_color = true;
x.m_n = h.m_n;
h.m_n = + Size(h.m_left) + Size(h.m_right);
return x;
}
void FlipColors(Node h) {
h.m_color = true;
h.m_left.m_color = false;
h.m_right.m_color = false;
}
public void Put(Key key,Value value) {
m_root = Put(m_root, key, value);
m_root.m_color = false;
}
public Node Put(Node h,Key key,Value value) {
if(h == null) {
, true);
}
int cmp = key.CompareTo(h.m_key);
) {
h.m_left = Put(h.m_left, key, value);
} ) {
h.m_right = Put(h.m_right, key, value);
} else {
h.m_value = value;
}
if(IsRed(h.m_right) && !IsRed(h.m_left)) {
h = RotateLeft(h);
}
if(IsRed(h.m_left) && IsRed(h.m_left.m_left)) {
h = RotateRight(h);
}
if(IsRed(h.m_left) && IsRed(h.m_right)) {
FlipColors(h);
}
h.m_n = Size(h.m_left) + Size(h.m_right) + ;
return h;
}
}
3.4 红黑树的插入算法
基于拉链法的散列表
public class SeparateChainingHashSymbolTable<Key, Value> {
public int N;
public int M;
private SequentialSearchSymbolTable<Key, Value>[] ssst;
public SeparateChainingHashSymbolTable() {
}
public SeparateChainingHashSymbolTable(int m) {
M = m;
}
public int Hash(Key key) {
return (key.GetHashCode() & 0x7fffffff) % M;
}
public Value Get(Key key) {
return (Value)ssst[Hash(key)].Get(key);
}
public void Put(Key key,Value value) {
ssst[Hash(key)].Put(key, value);
}
public IEnumerable<Key> Keys()
}
3.5 基于拉链法的散列表
基于线性探测的符号表
public class LinearProbingHashSymbolTable<Key, Value> where Key : class where Value : class {
private int m_n;
;
private Key[] m_keys;
private Value[] m_values;
public LinearProbingHashSymbolTable(int m) {
m_m = m;
m_keys = new Key[m_m];
m_values = new Value[m_m];
}
public int Hash(Key key) {
return (key.GetHashCode() & 0x7fffffff) % m_m;
}
public void Put(Key key, Value value) {
) {
Resize( * m_m);
}
int i;
)%m_m) {
if (m_keys[i].Equals(key)) {
m_values[i] = value;
return;
}
}
m_keys[i] = key;
m_values[i] = value;
m_n++;
}
public Value Get(Key key) {
) % m_m) {
if (m_keys[i].Equals(key)) {
return m_values[i];
}
}
return null;
}
public void Resize(int capacity) {
LinearProbingHashSymbolTable<Key, Value> t = new LinearProbingHashSymbolTable<Key, Value>(capacity);
; i < m_m; i++) {
if(m_keys[i] != null) {
t.Put(m_keys[i], m_values[i]);
}
}
m_keys = t.m_keys;
m_values = t.m_values;
m_m = t.m_m;
}
}
3.6 基于线性探测的符号表
第4章 图
Graph
定义 图是由一组顶点和一组能够将两个顶点相连的边组成的.
定义 在图中,路径是由边顺序连接的一系列顶点.简单路径是一条没有重复顶点的路径.环是一条至少含有一条边且起点和终点相同的路径.简单环是一条(除了起点和终点必须相同之外)不含有重复顶点和边的环.
路径或者环的长度为其中所包含的边数.
定义 如果从任意一个顶点都存在一条路径到达另一个任意顶点,我们称这副图是连通图.一幅非连通的图由若干连通的部分组成,他们都是其极大连通子图
定义 树是一幅无环连通图.互不相连的树组成的集合称为森林.连通图的生成树是它的一幅子图,它含有图中的所有顶点且是一颗树.图的生成树森林是它的所有连通子图的生成树的集合.
public class Graph {
public int m_v;
public int m_e;
public List<List<int>> m_adj;
public Graph(int v) {
m_v = v;
m_e = ;
m_adj = new List<List<int>>();
; i < m_v; i++) {
m_adj.Add(new List<int>());
}
}
public int V() {
return m_v;
}
public int E() {
return m_e;
}
public void AddEdge(int v,int w) {
m_adj[v].Add(w);
m_adj[w].Add(v);
m_e++;
}
public IEnumerable<int> Adj(int v) {
return m_adj[v];
}
Graph数据类型
private class DepthFirstPaths {
private bool[] m_marked; //这个顶点上调用过DFS吗
private int[] m_edgeTo; //到达该顶点的路径
private int m_source; //起点
public DepthFirstPaths(Graph g,int s) {
m_marked = new bool[g.V()];
m_edgeTo = new int[g.V()];
m_source = s;
}
public void DFS(Graph g,int v) {
m_marked[v] = true;
foreach (var item in g.Adj(v)) {
if (!m_marked[item]) {
m_edgeTo[item] = v;
DFS(g, item);
}
}
}
public bool HasPathTo(int v) {
return m_marked[v];
}
public IEnumerable<int> PathTo(int v) {
if (!HasPathTo(v)) {
return null;
}
Stack<int> path = new Stack<int>();
for (int i = v; i != m_source; i = m_edgeTo[i]) {
path.Push(i);
}
path.Push(m_source);
return path;
}
}
4.1 使用深度优先搜索查找图中的路径
public class BreadthFirstPaths {
private bool[] m_marked; //这个顶点上调用过BFS吗
private int[] m_edgeTo; //到达该顶点的路径
private int m_source; //起点
public BreadthFirstPaths(Graph g,int s) {
m_marked = new bool[g.V()];
m_edgeTo = new int[g.V()];
m_source = s;
}
public void BFS(Graph g,int s) {
Queue<int> queue = new Queue<int>();
m_marked[s] = true;
queue.Enqueue(s);
) {
int v = queue.Dequeue();
foreach (var item in g.Adj(v)) {
if (!m_marked[item]) {
m_edgeTo[item] = v;
m_marked[item] = true;
queue.Enqueue(item);
}
}
}
}
public bool HasPathTo(int v) {
return m_marked[v];
}
public IEnumerable<int> PathTo(int v) {
if (!HasPathTo(v)) {
return null;
}
Stack<int> path = new Stack<int>();
for (int i = v; i != m_source; i = m_edgeTo[i]) {
path.Push(i);
}
path.Push(m_source);
return path;
}
}
4.2 使用广度优先搜索查找图中的路径
public class ConnectedComponent {
public bool[] m_marked;
public int[] m_id;
public int m_count;
public ConnectedComponent(Graph g) {
m_marked = new bool[g.V()];
m_id = new int[g.V()];
; i < g.V(); i++) {
if (!m_marked[i]) {
DFS(g, i);
m_count++;
}
}
}
public void DFS(Graph g,int v) {
m_marked[v] = true;
m_id[v] = m_count;
foreach (var item in g.Adj(v)) {
if (!m_marked[item]) {
DFS(g, item);
}
}
}
public bool Connected(int v,int w) {
return m_id[v] == m_id[w];
}
public int ID(int v) {
return m_id[v];
}
public int Count() {
return m_count;
}
}
4.3 使用深度优先搜索找出图中的所有连通分量
Digraph
定义 一幅有方向性的图(或有向图)是由一组顶点和一组有方向的边组成的,每条有方向的边都连接着有序的一对顶点.
定义 在一幅有向图中,有向路径由一系列顶点组成,对于其中的每个顶点都存在一条有向边从它指向序列中的下一个顶点.有向环为一条至少含有一条边且起点和终点相同的有向路径.
简单有向环是一条(除了起点和终点必须相同之外)不含有重复的顶点和边的环.路径或者环的长度即为其中所包含的边数.
public class Digraph {
public int m_v;
public int m_e;
public List<List<int>> m_adj;
public Digraph(int v) {
m_v = v;
m_e = ;
m_adj = new List<List<int>>();
; i < m_v; i++) {
m_adj.Add(new List<int>());
}
}
public int V() {
return m_v;
}
public int E() {
return m_e;
}
public void AddEdge(int v,int w) {
m_adj[v].Add(w);
m_e++;
}
public IEnumerable<int> Adj(int v) {
return m_adj[v];
}
public Digraph Reverse() {
Digraph r = new Digraph(m_v);
; i < m_v; i++) {
foreach (var item in m_adj[i]) {
r.AddEdge(item, i);
}
}
return r;
}
}
Digraph
public class DirectedDFS {
public bool[] m_marked;
public DirectedDFS(Digraph g,int s) {
m_marked = new bool[g.V()];
DFS(g, s);
}
public DirectedDFS(Digraph g,IEnumerable<int> sources) {
m_marked = new bool[g.V()];
foreach (var item in sources) {
if (!m_marked[item]) {
DFS(g, item);
}
}
}
private void DFS(Digraph g,int v) {
m_marked[v] = true;
foreach (var item in g.m_adj[v]) {
if (!m_marked[item]) {
DFS(g, item);
}
}
}
public bool Marked(int v) {
return m_marked[v];
}
}
4.4 有向图的可达性
定义 有向无环图(DAG)就是一幅不含有向环的有向图
public class DirectedCycle {
public bool[] m_marked;
public int[] m_edgeTo;
public Stack<int> m_cycle;
public bool[] m_onStack;
public DirectedCycle(Digraph g) {
m_onStack = new bool[g.V()];
m_edgeTo = new int[g.V()];
m_marked = new bool[g.V()];
; i < g.V(); i++) {
if (!m_marked[i]) {
DFS(g, i);
}
}
}
public void DFS(Digraph g,int v) {
m_onStack[v] = true;
m_marked[v] = true;
foreach (var item in g.Adj(v)) {
if (HasCycle()) {
return;
}
else if (!m_marked[item]) {
m_edgeTo[item] = v;
DFS(g, item);
} else if (m_onStack[item]) {
m_cycle = new Stack<int>();
for (int i = v; i != item; i = m_edgeTo[i]) {
m_cycle.Push(i);
}
m_cycle.Push(item);
m_cycle.Push(v);
}
}
}
public bool HasCycle() {
return m_cycle != null;
}
public IEnumerable<int> Cycle() {
return m_cycle;
}
}
DirectedCycle 寻找有向环
public class DepthFirstOrder {
public bool[] m_marked;
public Queue<int> m_pre;
public Queue<int> m_post;
public Stack<int> m_reversePost;
public DepthFirstOrder(Digraph g) {
m_pre = new Queue<int>();
m_post = new Queue<int>();
m_reversePost = new Stack<int>();
m_marked = new bool[g.V()];
; i < g.V(); i++) {
if (!m_marked[i]) {
DFS(g, i);
}
}
}
public void DFS(Digraph g,int v) {
m_pre.Enqueue(v);
m_marked[v] = true;
foreach (var item in g.Adj(v)) {
if (!m_marked[item]) {
DFS(g, v);
}
}
m_post.Enqueue(v);
m_reversePost.Push(v);
}
public IEnumerable<int> Pre() {
return m_pre;
}
public IEnumerable<int> Post() {
return m_post;
}
public IEnumerable<int> ReversePost() {
return m_reversePost;
}
}
DepthFirstOrder 有向图中基于深度优先搜索的顶点排序
public class Topological {
public IEnumerable<int> m_order;
public Topological(Digraph g) {
DirectedCycle cycleFinder = new DirectedCycle(g);
if (!cycleFinder.HasCycle()) {
DepthFirstOrder dfs = new DepthFirstOrder(g);
m_order = dfs.ReversePost();
}
}
public IEnumerable<int> Order() {
return m_order;
}
public bool IsDAG() {
return m_order != null;
}
}
4.5 拓扑排序
public class KosarajuStronglyConnectedComponent {
private bool[] m_marked; // 已访问过的顶点
private int[] m_id; // 强连通分量的标识符
private int m_count; // 强连通分量的数量
public KosarajuStronglyConnectedComponent(Digraph g) {
m_marked = new bool[g.V()];
m_id = new int[g.V()];
DepthFirstOrder order = new DepthFirstOrder(g.Reverse());
foreach (var item in order.ReversePost()) {
if (!m_marked[item]) {
DFS(g, item);
m_count++;
}
}
}
public void DFS(Digraph g,int v) {
m_marked[v] = true;
m_id[v] = m_count;
foreach (var item in g.Adj(v)) {
if (!m_marked[item]) {
DFS(g, item);
}
}
}
public bool StronglyConnected(int v,int w) {
return m_id[v] == m_id[w];
}
public int Id(int v) {
return m_id[v];
}
public int Count() {
return m_count;
}
}
4.6 计算强连通分量的Kosaraju算法 KosarajuStronglyConnectedComponent
MST(minimum spanning tree) 定义 图的生成树是它的一棵含有其所有顶点的无环连通子图.一幅加权图的最小生成树(MST)是它的一颗权值(树中所有边的权值之和)最小的生成树
定义 图的一种切分是将图的所有顶点分为两个非空且不重叠的两个集合.横切边是一条连接两个属于不同集合的顶点的边.
public class Edge : IComparable<Edge> {
private int m_v;
private int m_w;
private double m_weight;
public Edge(int v, int w, double weight) {
m_v = v;
m_w = w;
m_weight = weight;
}
public double Weight() {
return m_weight;
}
public int Either() {
return m_v;
}
public int Other(int vertex) {
if(vertex == m_v) {
return m_w;
} else if(vertex == m_w) {
return m_v;
} else {
throw new Exception("Inconsistent edge");
}
}
public int CompareTo(Edge that) {
if(Weight() < that.Weight()) {
;
} else if(Weight() > that.Weight()) {
;
} else {
;
}
}
override public string ToString() {
return string.Format("{0:d}-{1:d} {2:f}", m_v, m_w, m_weight);
}
}
带权重的边的数据类型
public class EdgeWeightedGraph {
private int m_v;
private int m_e;
private List<List<Edge>> m_adj;
public EdgeWeightedGraph(int v) {
m_v = v;
m_e = ;
m_adj = new List<List<Edge>>();
; i < m_v; i++) {
m_adj.Add(new List<Edge>());
}
}
public int V() {
return m_v;
}
public int E() {
return m_e;
}
public void AddEdge(Edge e) {
int v = e.Either();
int w = e.Other(v);
m_adj[v].Add(e);
m_adj[w].Add(e);
m_e++;
}
public IEnumerable<Edge> Adj(int v) {
return m_adj[v];
}
public IEnumerable<Edge> Edges() {
List<Edge> b = new List<Edge>();
; i < m_v; i++) {
foreach (var item in m_adj[i]) {
if(item.Other(i) > i) {
b.Add(item);
}
}
}
return b;
}
}
加权无向图的数据类型
public class LazyPrimMST {
public bool[] m_marked; // 最小生成树的定点
public Queue<Edge> m_mst; // 最小生成树的边
public MinPQ<Edge> m_pq; // 横切边(包括失效的边)
public LazyPrimMST(EdgeWeightedGraph g) {
m_pq = new MinPQ<Edge>();
m_marked = new bool[g.V()];
m_mst = new Queue<Edge>();
Visit(g, ); // 假设g是连通的
while (!m_pq.IsEmpty()) {
Edge e = m_pq.delMin(); //从pq中得到权重最小的边
int v = e.either();
int w = e.other(v);
if(m_marked[v] && m_marked[w]) {
continue;
}
if (!m_marked[v]) {
Visit(g, v);
}
if (!m_marked[w]) {
Visit(g, w);
}
}
}
public void Visit(EdgeWeightedGraph g,int v) {
m_marked[v] = true;
foreach (var item in g.adj(v)) {
if (!m_marked[item.other(v)]) {
m_pq.insert(item);
}
}
}
public IEnumerable<Edge> Edges() {
return m_mst;
}
public double Weight() { }
}
最小生成树的Prim算法的延时实现
public class PrimMST {
public Edge[] m_edgeTo; // 距离树最近的边
public double[] m_distTo; // distTo[w] = m_edgeTo[w].weight();
public bool[] m_marked; // 如果v在树中则为true
public IndexMinPQ<double> m_pq; // 有效的横切边
public PrimMST(EdgeWeightedGraph g) {
m_edgeTo = new Edge[g.V()];
m_distTo = new double[g.V()];
m_marked = new bool[g.V()];
; i < g.V(); i++) {
m_distTo[i] = double.PositiveInfinity;
}
m_pq = new IndexMinPQ<double>(g.V());
m_distTo[] = 0.0;
m_pq.insert(, 0.0); // 用顶点0和权重0初始化m_pq
while (!m_pq.isEmpty()) {
Visit(g, m_pq.delMin());
}
}
public void Visit(EdgeWeightedGraph g,int v) {
// 将顶点v添加到树中,更新数据
m_marked[v] = true;
foreach (var item in g.adj(v)) {
int w = item.other(v);
if (m_marked[w]) {
continue; // v-w失效
}
if(item.Weight() < m_distTo[w]) {
// 连接w和树的最佳边Edge变成e
m_edgeTo[w] = item;
m_distTo[w] = item.weight();
if (m_pq.contains(w)) {
m_pq.change(w, m_distTo[w]);
} else {
m_pq.insert(w, m_distTo[w]);
}
}
}
}
}
4.7 最小生成树的Prim算法(即时版本)
public class KruskalMST {
public Queue<Edge> m_mst;
public KruskalMST(EdgeWeightedGraph g) {
m_mst = new Queue<Edge>();
MinPQ<Edge> pq = new MinPQ<Edge>();
foreach (var item in g.edges()) {
pq.insert(item);
}
UF uf = new UF(g.V());
) {
Edge e = pq.delMin(); // 从pq得到权重最小的边和它的顶点
int v = e.either();
int w = e.other(v);
if (uf.connected(v, w)) {
continue; // 忽略失效的边
}
uf.union(v, w); // 合并分量
m_mst.Enqueue(e); // 将边添加到最下生成树中
}
}
public IEnumerable<Edge> Edges() {
return m_mst;
}
public double Weight() {
}
}
4.8 最小生成树的Kruskal算法
最短路径
定义 在一幅加权有向图中,从顶点s到顶点t的最短路径是所有从s到t的路径中的权重最小者
定义 给定一幅加权有向图和一个顶点s,以s为起点的一颗最短路径树是图的一幅子图,它包含s和从s可达的所有顶点.这棵有向树的根结点为s,树的每条路径都是有向图中的一条最短路径.
public class DirectedEdge {
public int m_v; // 边的起点
public int m_w; // 边的终点
public double m_weight; // 边的权重
public DirectedEdge(int v,int w,double weight) {
m_v = v;
m_w = w;
m_weight = weight;
}
public double Weight() {
return m_weight;
}
public int From() {
return m_v;
}
public int To() {
return m_w;
}
}
加权有向边的数据类型
public class EdgeWeightedDigraph {
public int m_v; // 顶点总数
public int m_e; // 边的总数
public Bag<DirectedEdge>[] m_adj; // 邻接表
public EdgeWeightedDigraph(int v) {
m_v = v;
m_e = ;
m_adj = new Bag<DirectedEdge>[v];
; i < v; i++) {
m_adj[i] = new Bag<DirectedEdge>();
}
}
public int V() {
return m_v;
}
public int E() {
return m_e;
}
public void AddEdge(DirectedEdge e) {
m_adj[e.From()].add(e);
m_e++;
}
public IEnumerable<DirectedEdge> Adj(int v) {
return m_adj[v];
}
public IEnumerable<DirectedEdge> Edges() {
Bag<DirectedEdge> bag = new Bag<DirectedEdge>();
; i < m_v; i++) {
foreach (var item in m_adj[m_v]) {
bag.add(item);
}
}
return bag;
}
}
加权有向图的数据类型
第5章 字符串
public class LSD {
public static void Sort(string[] a, int w) {
int n = a.Length;
;
string[] auxiliary = new string[n];
; i >= ; i--) {
];
//计算出现频率
; j < n; j++) {
count[a[j].CharAt(i) + ]++;
}
//将频率转换为索引
; j < r; j++) {
count[j + ] += count[j];
}
//将元素分类
; j < n; j++) {
auxiliary[count[a[j].CharAt(i)]++] = a[j];
}
//回写
; j < n; j++) {
a[j] = auxiliary[j];
}
}
}
}
5.1 低位优先的字符串排序
public class TrieSymbolTable<Value> {
;
public Node m_root;
public class Node {
public object m_value;
public Node[] m_next = new Node[m_R];
}
public Value Get(string key) {
Node node = Get(m_root, key, );
if(node == null) {
return default(Value);
}
return (Value)node.m_value;
}
public Node Get(Node node,string key,int d) {
if(node == null) {
return null;
}
if(d == key.Length) {
return node;
}
char c = key.CharAt(d);
);
}
public void Put(string key,Value value) {
}
public Node Put(Node node,string key,Value value,int d) {
if(node == null) {
node = new Node();
}
if(d == key.Length) {
node.m_value = value;
return node;
}
char c = key.CharAt(d);
node.m_next[c] = Put(node.m_next[c], key, value, d + );
return node;
}
}
5.4 基于单词查找树的符号表
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
http://algs4.cs.princeton.edu
https://www.coursera.org/learn/algorithms-part1
https://www.coursera.org/learn/algorithms-part2
C# Code
