第1章 基础

1 public class Bag
      
        : IEnumerable
       
         { 2  3     private T[] values = new T[100]; 4     private int count = 0; 5  6     public void Add(T t) { 7         values[count++] = u; 8     } 9 10     public bool IsEmpty() {11         return count == 0;12     }13 14     public int Size() {15         return count;16     }17 18     public IEnumerator
        
          GetEnumerator() {19         for (int i = 0; i < count; i++) {20             yield return values[i];21         }22     }23 24     IEnumerator IEnumerable.GetEnumerator() {25         return GetEnumerator();26     }27 }
        
       
      

1 public class Stack
      
        : IEnumerable
       
         { 2  3     private T[] values = new T[100]; 4     private int count = 0; 5  6     public void Push(T t) { 7         values[count++] = t; 8     } 9 10     public T Pop() {11         return values[--count];12     }13 14     public bool IsEmpty() {15         return count == 0;16     }17 18     public int Size() {19         return count;20     }21 22     public IEnumerator
        
          GetEnumerator() {23         for (int i = count - 1; i >= 0; i--) {24             yield return values[i];25         }26     }27 28     IEnumerator IEnumerable.GetEnumerator() {29         return GetEnumerator();30     }31 }
        
       
      

1 public class Queue
      
        : IEnumerable
       
         { 2     private T[] values = new T[100]; 3     private int head = 0; 4     private int tail = 0; 5  6     public void Enqueue(T t) { 7         values[tail++] = t; 8     } 9 10     public T Dequeue() {11         return values[head++];12     }13 14     public bool IsEmpty() {15         return head == tail;16     }17 18     public int Size() {19         return tail - head;20     }21 22     public IEnumerator
        
          GetEnumerator() {23         for (int i = head; i < tail; i++) {24             yield return values[i];25         }26     }27 28     IEnumerator IEnumerable.GetEnumerator() {29         return GetEnumerator();30     }31 }
        
       
      

 

 

第2章 排序

选择排序 SelectionSort : 选择剩余元素之中的最小者

命题A:对于长度为N的数组,选择排序需要大于(NxN)/2次比较和N次交换

1 public class SelectionSort { 2  3     static public void Sort(int[] arr) { 4         for (int i = 0; i < arr.Length; i++) { 5             int min = i; 6             for (int j = i; j < arr.Length; j++) { 7                 if(arr[j] < arr[min]) { 8                     min = j; 9                 }10             }11             Exchange(arr, min, i);12         }13     }14 15     static public void Exchange(int[] arr,int a,int b) {16         int temp = arr[a];17         arr[a] = arr[b];18         arr[b] = temp;19     }20 }

插入排序 InsertionSort : 想象初始手里有一张牌,每次从牌堆里拿一张牌有序插入手中的牌里.

倒置 指的是数组中的两个顺序颠倒的元素.

命题B:对于随机排列的长度为N且主键不重复的数组,平均情况下插入排序需要~(NxN)/4次比较以及~(NxN)/4次交换.最坏情况下需要~(NxN)/2次比较和~(NxN)/2次交换,最好情况下需要N-1次比较和0次交换

命题C:插入排序需要的交换操作和数组中倒置的数量相同,需要的比较次数大于等于倒置的数量,小于等于倒置的数量加上数组的大小再减一

1 public class InsertionSort { 2     static public void Sort(int[] arr) { 3         for (int i = 1; i < arr.Length; i++) { 4             for (int j = i; j > 0; j--) { 5                 if(arr[j] < arr[j - 1]) { 6                     Exchange(arr, j, j - 1); 7                 } 8             } 9         }10     }11 12     static public void Exchange(int[] arr,int a,int b) {13         int temp = arr[a];14         arr[a] = arr[b];15         arr[b] = temp;16     }17 }

希尔排序:ShellSort : 希尔排序的思想是使数组中任意间隔为h的元素都是有序的.这样的数组被称为h有序数组

1 public class ShellSort { 2     static public void Sort(int[] arr) { 3         int n = arr.Length; 4         int h = 1; 5         while(h < n / 3) { 6             h = 3 * h + 1; 7         } 8         while(h >= 1) { 9             for (int i = h; i < n; i++) {10                 for (int j = i; j >= h; j -= h) {11                     if(arr[j] < arr[j - h]) {12                         Exchange(arr, j, j - h);13                     }14                 }15             }16             h = h / 3;17         }18     }19 20     static public void Exchange(int[] arr,int a,int b) {21         int temp = arr[a];22         arr[a] = arr[b];23         arr[b] = temp;24     }25 }

归并排序:MergeSort

1 public class Merge { 2     private static IComparable[] auxiliary; 3  4     public static void Sort(IComparable[] a) { 5         auxiliary = new IComparable[a.Length]; 6         Sort(a, 0, a.Length - 1); 7     } 8  9     private static void Sort(IComparable[] a,int lo,int hi) {10         if(hi <= lo) {11             return;12         }13         int mid = lo + (hi - lo) / 2;14         Sort(a, lo, mid);15         Sort(a, mid + 1, hi);16         MergeMethod(a, lo, mid, hi);17     }18 19     public static void MergeMethod(IComparable[] a,int lo,int mid,int hi) {20         int i = lo;21         int j = mid + 1;22 23         for (int k = lo; k <= hi; k++) {24             auxiliary[k] = a[k];25         }26 27         for (int k = lo; k <= hi; k++) {28             if (i > mid) {29                 a[k] = auxiliary[j++];30             } else if (j > hi) {31                 a[k] = auxiliary[i++];32             } else if (Less(auxiliary[j], auxiliary[i])) {33                 a[k] = auxiliary[j++];34             } else {35                 a[k] = auxiliary[i++];36             }37         }38     }39 40     public static bool Less(IComparable a,IComparable b) {41         if(a.CompareTo(b) < 0) {42             return true;43         } else {44             return false;45         }46     }47 }

快速排序:QuickSort

1 public class Quick { 2     public static void Sort(IComparable[] a) { 3         Sort(a, 0, a.Length - 1); 4     } 5  6     private static void Sort(IComparable[] a,int lo,int hi) { 7         if(hi <= lo) { 8             return; 9         }10         int j = Partition(a, lo, hi);11         Sort(a, lo, j - 1);12         Sort(a, j + 1, hi);13     }14 15 16     private static int Partition(IComparable[] a,int lo, int hi) {17         // 将数组切分为a[lo...i-1],a[i],a[i+1...hi]18         int i = lo; // 左扫描指针19         int j = hi + 1; // 右扫描指针20         IComparable v = a[lo]; // 切分元素21         while (true) {22             while (Less(a[++i], v)) {23                 if(i == hi) {24                     break;25                 }26             }27             while (Less(v, a[--j])) {28                 if (j == lo) {29                     break;30                 }31             }32             if (i >= j) {33                 break;34             }35             Exchange(a, i, j);36         }37         Exchange(a, lo, j);38         return j;39     }40 41 42     private static bool Less(IComparable a,IComparable b) {43         if (a.CompareTo(b) < 0) {44             return true;45         } else {46             return false;47         }48     }49 50     private static void Exchange(IComparable[] a,int i,int j) {51         IComparable v = a[i];52         a[i] = a[j];53         a[j] = v;54     }55 }

三向快速排序:

 

定义 当一个二叉树的每个结点都大于等于它的两个子结点时,它被称为堆有序

定义 二叉堆是一组能够用堆有序的完全二叉树排序的元素,并在数组中按照层级储存(不使用数组的第一个位置)

1 public class MaxPriorityQueue
      
        where Key : IComparable { 2     public Key[] m_pq; 3     public int m_n = 0; 4  5     public MaxPriorityQueue(int n) { 6         m_pq = new Key[n + 1]; 7     } 8  9     public bool IsEmpty() {10         return m_n == 0;11     }12 13     public int Size() {14         return m_n;15     }16 17     public void Insert(Key key) {18         m_pq[++m_n] = key;19         Swim(m_n);20     }21 22     public Key DelMax() {23         Key max = m_pq[1];24         Exchange(1, m_n--);25         m_pq[m_n + 1] = default(Key);26         Sink(1);27         return max;28     }29 30     private bool Less(int i,int j) {31         return m_pq[i].CompareTo(m_pq[j]) < 0;32     }33 34     private void Exchange(int i,int j) {35         Key k = m_pq[i];36         m_pq[i] = m_pq[j];37         m_pq[j] = k;38     }39 40     private void Swim(int k) {41         while(k > 1 && Less(k / 2, k)) {42             Exchange(k / 2, k);43             k = k / 2;44         }45     }46 47     private void Sink(int k) {48         while (2 * k <= m_n) {49             int j = 2 * k;50             if (j < m_n && Less(j, j + 1)) {51                 j++;52             }53             if (!Less(k, j)) {54                 break;55             }56             Exchange(k, j);57             k = j;58         }59     }60 }
      

1 public class IndexMinPQ
      
       > 2         IndexMinPQ(int maxN)            创建一个最大容量为maxN的优先队列,索引的取值范围为0至maxN-1 3     void    Insert(int k,Item item)            插入一个元素,将它和索引k相关联 4     void    Change(int k,Item item)            将索引为k的元素设为item 5     bool    Contains(int k)                是否存在索引为k的元素 6     void    Delete(int k)                删去索引k及其相关联的元素 7     Item    Min()                    返回最小元素 8     int     MinIndex()                返回最小元素的索引 9     int    DelMin()                删除最小元素并返回它的索引10     bool    IsEmpty()                优先队列是否为空11     int    Size()                    优先队列中的元素数量
      

1 public class IndexMinPQ
      
        where Key : IComparable
       
         {  2     private int m_maxN;  3     private int m_n;  4     private int[] m_pq;  5     private int[] m_qp;  6     private Key[] m_keys;  7   8     public IndexMinPQ(int maxN) {  9         if(maxN < 0) { 10             throw new ArgumentOutOfRangeException(); 11         } 12         m_maxN = maxN; 13         m_n = 0; 14         m_keys = new Key[maxN + 1]; 15         m_pq = new int[maxN + 1]; 16         m_qp = new int[maxN + 1]; 17         for (int i = 0; i <= maxN; i++) { 18             m_qp[i] = -1; 19         } 20     } 21  22     public bool IsEmpty() { 23         return m_n == 0; 24     } 25  26     public bool Contains(int i) { 27         if (i < 0 || i >= m_maxN) { 28             throw new ArgumentOutOfRangeException(); 29         } 30         return m_qp[i] != -1; 31     } 32  33     public int Size() { 34         return m_n; 35     } 36  37     public void Insert(int i,Key key) { 38         if(i < 0 || i >= m_maxN) { 39             throw new ArgumentOutOfRangeException(); 40         } 41         if (Contains(i)) { 42             throw new ArgumentOutOfRangeException("index is already in the priority queue"); 43         } 44         m_n++; 45         m_pq[m_n] = i; 46         m_qp[i] = m_n; 47         m_keys[i] = key; 48         Swim(m_n); 49     } 50  51     public int MinIndex() { 52         if(m_n == 0) { 53             throw new ArgumentNullException("Priority queue underflow"); 54         } 55         return m_pq[1]; 56     } 57  58     public Key MinKey() { 59         if(m_n == 0) { 60             throw new ArgumentNullException("Priority queue underflow"); 61         } 62         return m_keys[m_pq[1]]; 63     } 64  65     public int DelMin() { 66         if (m_n == 0) { 67             throw new ArgumentNullException("Priority queue underflow"); 68         } 69         int min = m_pq[1]; 70         Exchange(1, m_n--); 71         Sink(1); 72         Trace.Assert(min == m_pq[m_n + 1]); 73         m_keys[min] = default(Key); 74         m_pq[m_n + 1] = -1; 75         m_qp[min] = -1; 76         return min; 77     } 78  79     public Key KeyOf(int i) { 80         if(i<0 || i >= m_maxN) { 81             throw new ArgumentOutOfRangeException(); 82         } 83         if (!Contains(i)) { 84             throw new ArgumentNullException("index is not in the priority queue"); 85         } else { 86             return m_keys[i]; 87         } 88     } 89  90     public void ChangeKey(int i,Key key) { 91         if (i < 0 || i >= m_maxN) { 92             throw new ArgumentOutOfRangeException(); 93         } 94         if (!Contains(i)) { 95             throw new ArgumentOutOfRangeException("index is not in the priority queue"); 96         } 97         m_keys[i] = key; 98         Swim(m_qp[i]); 99         Sink(m_qp[i]);100     }101 102     public void DecreaseKey(int i,Key key) {103         if(i < 0 || i >= m_maxN) {104             throw new ArgumentOutOfRangeException();105         }106         if (!Contains(i)) {107             throw new ArgumentNullException("index is not in the priority queue");108         }109         if(m_keys[i].CompareTo(key) <= 0) {110             throw new ArgumentOutOfRangeException("Calling DecreaseKey() with given argument would not strictly decrease the key");111         }112         m_keys[i] = key;113         Swim(m_qp[i]);114     }115 116     public void InCreaseKey(int i,Key key) {117         if(i < 0 || i >= m_maxN) {118             throw new ArgumentOutOfRangeException();119         }120         if (!Contains(i)) {121             throw new ArgumentNullException("index is not in the priority queue");122         }123         if(m_keys[i].CompareTo(key) >= 0) {124             throw new ArgumentOutOfRangeException("Calling InCreaseKey() with given argument would not strictly increase the key");125         }126         m_keys[i] = key;127         Sink(m_qp[i]);128     }129 130     public void Delete(int i) {131         if(i < 0 || i >= m_maxN) {132             throw new ArgumentOutOfRangeException();133         }134         if (!Contains(i)) {135             throw new ArgumentNullException("index is not in the priority queue");136         }137         int index = m_qp[i];138         Exchange(index, m_n--);139         Swim(index);140         Sink(index);141         m_keys[i] = default(Key);142         m_qp[i] = -1;143     }144 145 146     private bool Greater(int i,int j) {147         return m_keys[m_pq[i]].CompareTo(m_keys[m_pq[j]]) > 0;148     }149 150     private void Exchange(int i,int j) {151         int swap = m_pq[i];152         m_pq[i] = m_pq[j];153         m_pq[j] = swap;154         m_qp[m_pq[i]] = i;155         m_qp[m_pq[j]] = j;156     }157 158     private void Swim(int k) {159         while(k > 1 && Greater(k / 2, k)) {160             Exchange(k, k / 2);161             k = k / 2;162         }163     }164 165     private void Sink(int k) {166         while(2 * k <= m_n) {167             int j = 2 * k;168             if(j < m_n && Greater(j, j + 1)) {169                 j++;170             }171             if (!Greater(k, j)){172                 break;173             }174             Exchange(k, j);175             k = j;176         }177     }178 }
       
      

1 public static void Sort(IComparable[] a) { 2     int N = a.Length; 3     for (int k = N / 2; k >= 1; k--) { 4         Sink(a, k, N); 5         while(N > 1) { 6             Exchange(a, 1, N--); 7             Sink(a, 1, N); 8         } 9     }10 }

第3章 查找

我们会使用符号表(Symbol Table)这个词来描述一张抽象的表格,我们会将信息(值)存储在其中,然后按照指定的键来搜索并获取这些信息.

符号表有时被称为字典,类似于那本将单词的释义按照字母顺序排列起来的历史悠久的参考书.

在英语字典里,键就是单词,值就是单词对应的定义,发音和词源.符号表有时又叫做索引,即书本最后将术语按照字母顺序列出以方便查找的那部分.

在一本书的索引中,键就是术语,而值就是书中该术语出现的所有页码.

定义: 符号表是一种存储键值对的数据结构,支持两种操作:插入(put),即将一组新的键值对存入表中;查找(get),即根据给定的键得到相应的值

1 public class SymbolTable
      
       2             SymbolTable()            创建一张符号表3     void        Put(Key key,Value value)    将键值对存入表中(若值为空则将键key从表中删除)4     Value        Get(Key key)            获取键key对应的值(若键key不存在则返回null)5     void        Delete(Key key)            从表中删除键key(及其对应的值)6     bool        Contains(Key key)        键key在表中是否有对应的值7     bool        IsEmpty()            表是否为空8     int        Size()                表中的键值对数量9     Iterable
       
            Keys()                表中的所有键的集合
       
      

1 public class SymbolTable
      
       ,Value> 2             SymbolTable()            创建一张有序符号表 3     void        Put(Key key,Value value)    将键值对存入表中(若值为空则将键key从表中删除) 4     Value        Get(Key key)            获取键key对应的值(若键key不存在则返回null) 5     void        Delete(Key key)            从表中删除键key(及其对应的值) 6     bool        Contains(Key key)        键key在表中是否有对应的值 7     bool        IsEmpty()            表是否为空 8     int        Size()                表中的键值对数量 9     Key        Min()                最小的键10     Key        Max()                最大的键11     Key        Floor(Key key)            小于等于key的最大键12     Key        Ceiling(Key key)        小于等于key的最小键13     int        Rank(Key key)            小于key的键的数量14     Key        Select(int k)            排名为k的键15     void        DeleteMin()            删除最小的键16     void        DeleteMax()            删除最大的键17     int        Size(Key lo,Key hi)        [lo..hi]之间键的数量18     Iterable
       
            Keys(Key lo,Key hi)        [lo..hi]之间的所有键,已排序19     Iterable
        
             Keys()                表中的所有键的集合,已排序
        
       
      

顺序查找(基于无序链表)

在查找中我们一个一个地顺序遍历符号表中的所有键并使用equals()方法来寻找与被查找的键匹配的键

1 public class SequentialSearchSymbolTable
      
        { 2     private class Node { 3         public Key m_key; 4         public Value m_value; 5         public Node m_next; 6  7         public Node(Key key,Value value,Node next) { 8             m_key = key; 9             m_value = value;10             m_next = next;11         }12     }13 14     private Node m_first;15 16     public Value Get(Key key) {17         for (Node x = m_first; x != null; x = x.m_next) {18             if (key.Equals(x.m_key)) {19                 return x.m_value;20             }21         }22         return default(Value);23     }24 25     public void Put(Key key, Value value) {26         for (Node x = m_first; x != null; x = x.m_next) {27             if (key.Equals(x.m_key)) {28                 x.m_value = value;29                 return;30             }31         }32         m_first = new Node(key, value, m_first);33     }34 }
      

二分查找(基于有序数组)

1 public class BinarySearchSymbolTable
      
        where Key:IComparable { 2     private Key[] m_keys; 3     private Value[] m_values; 4     private int N; 5  6     public BinarySearchSymbolTable(int capacity) { 7         m_keys = new Key[capacity]; 8         m_values = new Value[capacity]; 9     }10 11     public int Size() {12         return N;13     }14 15     //小于key的键的数量16     public int Rank(Key key) {17         int lo = 0;18         int hi = N - 1;19 20         while(lo <= hi) {21             int mid = lo + (hi - lo) / 2;22             int cmp = key.CompareTo(m_keys[mid]);23             if(cmp < 0) {24                 hi = mid - 1;25             } else if(cmp > 0) {26                 lo = mid + 1;27             } else {28                 return mid;29             }30         }31         return lo;32     }33 34     public void Put(Key key,Value value) {35         int i = Rank(key);36         if(i < N && m_keys[i].CompareTo(key) == 0) {37             m_values[i] = value;38             return;39         }40         for (int j = N; j > i; j--) {41             m_keys[j] = m_keys[j - 1];42             m_values[j] = m_values[j - 1];43         }44         m_keys[i] = key;45         m_values[i] = value;46         N++;47     }48 49     public Value Get(Key key) {50         if (IsEmpty()) {51             return default(Value);52         }53         int i = Rank(key);54         if(i < N && m_keys[i].CompareTo(key) == 0) {55             return m_values[i];56         } else {57             return default(Value);58         }59     }60 61     public void Delete(Key key) {62 63     }64 65     public bool IsEmpty() {66         return N == 0;67     }68 }
      

二叉查找树

定义 : 一颗二叉查找树(BST)是一颗二叉树,其中每个节点都含有一个Comparable的键(以及相关联的值)且每个节点的键都大于其左子树中的任意结点的键而小于右子树的任意节点的键

1 public class BinarySearchTree
      
        where Key : IComparable
       
         where Value:class {  2   3     public class Node {  4         public Key m_key;  5         public Value m_value;  6         public Node m_left;  7         public Node m_right;  8         public int m_count;  9  10         public Node(Key key,Value value,int count) { 11             m_key = key; 12             m_value = value; 13             m_count = count; 14         } 15     } 16  17     private Node m_root; 18  19     public int Size() { 20         return Size(m_root); 21     } 22  23     private int Size(Node node) { 24         if(node == null) { 25             return 0; 26         } else { 27             return node.m_count; 28         } 29     } 30  31     public Value Get(Key key) { 32         return Get(m_root, key); 33     } 34  35     private Value Get(Node node,Key key) { 36         if(node == null) { 37             return null; 38         } 39         int cmp = key.CompareTo(node.m_key); 40         if(cmp < 0) { 41             return Get(node.m_left, key); 42         } else if(cmp > 0) { 43             return Get(node.m_right, key); 44         } else { 45             return node.m_value; 46         } 47     } 48  49     public void Put(Key key,Value value) { 50         m_root = Put(m_root, key, value); 51     } 52  53     private Node Put(Node node,Key key,Value value) { 54         if(node == null) { 55             return new Node(key, value, 1); 56         } 57         int cmp = key.CompareTo(node.m_key); 58         if(cmp < 0) { 59             node.m_left = Put(node.m_left, key, value); 60         } else if(cmp > 0) { 61             node.m_right = Put(node.m_right, key, value); 62         } else { 63             node.m_value = value; 64         } 65         node.m_count = Size(node.m_left) + Size(node.m_right) + 1; 66         return node; 67     } 68  69     public Key Min() { 70         return Min(m_root).m_key; 71     } 72  73     private Node Min(Node node) { 74         if(node.m_left == null) { 75             return node; 76         } 77         return Min(node.m_left); 78     } 79  80     public Key Max() { 81         return Max(m_root).m_key; 82     } 83  84     private Node Max(Node node) { 85         if(node.m_right == null) { 86             return node; 87         } 88         return Max(node.m_right); 89     } 90  91     public Key Floor(Key key) { 92         Node node = Floor(m_root, key); 93         if(node == null) { 94             return default(Key); 95         } 96         return node.m_key; 97     } 98  99     private Node Floor(Node node,Key key) {100         if(node == null) {101             return null;102         }103         int cmp = key.CompareTo(node.m_key);104         if(cmp == 0) {105             return node;106         }107         if(cmp < 0) {108             return Floor(node.m_left, key);109         }110         Node n = Floor(node.m_right, key);111         if(n != null) {112             return n;113         } else {114             return node;115         }116     }117 118     public Key Select(int k) {119         return Select(m_root, k).m_key;120     }121 122     private Node Select(Node node,int k) {123         if(node == null) {124             return null;125         }126         int size = Size(node.m_left);127         if(size > k) {128             return Select(node.m_left, k);129         } else if(size < k) {130             return Select(node.m_right, k - size - 1);131         } else {132             return node;133         }134     }135 136     public int Rank(Key key) {137         return Rank(key, m_root);138     }139 140     private int Rank(Key key,Node node) {141         if(node == null) {142             return 0;143         }144         int cmp = key.CompareTo(node.m_key);145         if(cmp < 0) {146             return Rank(key, node.m_left);147         } else if(cmp > 0) {148             return 1 + Size(node.m_left) + Rank(key, node.m_right);149         } else {150             return Size(node.m_left);151         }152     }153 154     public void DeleteMin() {155         m_root = DeleteMin(m_root);156     }157 158     private Node DeleteMin(Node node) {159         if(node.m_left == null) {160             return node.m_right;161         }162         node.m_left = DeleteMin(node.m_left);163         node.m_count = Size(node.m_left) + Size(node.m_right) + 1;164         return node;165     }166 167     public void Delete(Key key) {168         m_root = Delete(m_root, key);169     }170 171     private Node Delete(Node node,Key key) {172         if(node == null) {173             return null;174         }175         int cmp = key.CompareTo(node.m_key);176         if (cmp < 0) {177             node.m_left = Delete(node.m_left, key);178         } else if (cmp > 0) {179             node.m_right = Delete(node.m_right, key);180         } else {181             if(node.m_right == null) {182                 return node.m_left;183             }184             if(node.m_left == null) {185                 return node.m_right;186             }187             Node n = node;188             node = Min(n.m_right);189             node.m_right = DeleteMin(n.m_right);190             node.m_left = n.m_right;191         }192         node.m_count = Size(node.m_left) + Size(node.m_right) + 1;193         return node;194     }195 196     public IEnumerable
        
          Keys() {197         return Keys(Min(), Max());198     }199 200     public IEnumerable
         
           Keys(Key lo,Key hi) {201         Queue
          
            queue = new Queue
           
            ();202 Keys(m_root, queue, lo, hi);203 return queue;204 }205 206 private void Keys(Node node,Queue
            
              queue,Key lo,Key hi) {207 if(node == null) {208 return;209 }210 int cmplo = lo.CompareTo(node.m_key);211 int cmphi = hi.CompareTo(node.m_key);212 if(cmplo < 0) {213 Keys(node.m_left, queue, lo, hi);214 }215 if(cmplo <= 0 && cmphi >= 0) {216 queue.Enqueue(node.m_key);217 }218 if(cmphi > 0) {219 Keys(node.m_right, queue, lo, hi);220 }221 }222 }
            
           
          
         
        
       
      

2-3查找树

定义 : 一棵2-3查找树或为一个空树,或由以下结点组成:

　　2- 结点,含有一个键(及其对应的值)和两条链接,左链接指向的2-3树中的键都小于该结点,右链接指向的2-3树中的键都大于该结点

　　3- 结点,含有两个键(及其对应的值)和三条链接,左链接指向的2-3树中的键都小于该结点,中链接指向的2-3树中的键都位于该结点的两个键之间,右链接指向的2-3树中的键都大于该结点

和以前一样,我们将指向一颗空树的链接称为空链接

1 public class RedBlackBST
      
        where Key : IComparable
       
         { 2  3     public Node m_root; 4  5     public class Node { 6         public Key m_key; 7         public Value m_value; 8         public Node m_left, m_right; 9         public int m_n;10         public bool m_color;11 12         public Node(Key key,Value value,int n,bool color) {13             m_key = key;14             m_value = value;15             m_n = n;16             m_color = color;17         }18     }19 20     public bool IsRed(Node x) {21         if(x == null) {22             return false;23         }24         return x.m_color == true;25     }26 27     public int Size(Node n) {28         if(n == null) {29             return 0;30         } else {31             return n.m_n;32         }33     }34 35     Node RotateLeft(Node h) {36         Node x = h.m_right;37         h.m_right = x.m_left;38         x.m_left = h;39         x.m_color = h.m_color;40         h.m_color = true;41         x.m_n = h.m_n;42         h.m_n = 1 + Size(h.m_left) + Size(h.m_right);43         return x;44     }45 46     Node RotateRight(Node h) {47         Node x = h.m_left;48         h.m_left = x.m_right;49         x.m_right = h;50         x.m_color = h.m_color;51         h.m_color = true;52         x.m_n = h.m_n;53         h.m_n = 1 + Size(h.m_left) + Size(h.m_right);54         return x;55     }56 57     void FlipColors(Node h) {58         h.m_color = true;59         h.m_left.m_color = false;60         h.m_right.m_color = false;61     }62 63     public void Put(Key key,Value value) {64         m_root = Put(m_root, key, value);65         m_root.m_color = false;66     }67 68     public Node Put(Node h,Key key,Value value) {69         if(h == null) {70             return new Node(key, value, 1, true);71         }72 73         int cmp = key.CompareTo(h.m_key);74         if(cmp < 0) {75             h.m_left = Put(h.m_left, key, value);76         } else if(cmp > 0) {77             h.m_right = Put(h.m_right, key, value);78         } else {79             h.m_value = value;80         }81 82         if(IsRed(h.m_right) && !IsRed(h.m_left)) {83             h = RotateLeft(h);84         }85         if(IsRed(h.m_left) && IsRed(h.m_left.m_left)) {86             h = RotateRight(h);87         }88         if(IsRed(h.m_left) && IsRed(h.m_right)) {89             FlipColors(h);90         }91 92         h.m_n = Size(h.m_left) + Size(h.m_right) + 1;93         return h;94     }95 }
       
      

基于拉链法的散列表

1 public class SeparateChainingHashSymbolTable
      
        { 2     public int N; 3     public int M; 4     private SequentialSearchSymbolTable
       
        [] ssst; 5  6     public SeparateChainingHashSymbolTable() { 7  8     } 9 10     public SeparateChainingHashSymbolTable(int m) {11         M = m;12 13     }14 15     public int Hash(Key key) {16         return (key.GetHashCode() & 0x7fffffff) % M;17     }18 19     public Value Get(Key key) {20         return (Value)ssst[Hash(key)].Get(key);21     }22 23     public void Put(Key key,Value value) {24         ssst[Hash(key)].Put(key, value);25     }26 27     public IEnumerable
        
          Keys()28 }
        
       
      

基于线性探测的符号表

1 public class LinearProbingHashSymbolTable
      
        where Key : class where Value : class { 2     private int m_n; 3     private int m_m = 16; 4     private Key[] m_keys; 5     private Value[] m_values; 6  7     public LinearProbingHashSymbolTable(int m) { 8         m_m = m; 9         m_keys = new Key[m_m];10         m_values = new Value[m_m];11     }12 13     public int Hash(Key key) {14         return (key.GetHashCode() & 0x7fffffff) % m_m;15     }16 17     public void Put(Key key, Value value) {18         if (m_n >= m_m / 2) {19             Resize(2 * m_m);20         }21         int i;22         for (i = Hash(key); m_keys[i] != null; i = (i+1)%m_m) {23             if (m_keys[i].Equals(key)) {24                 m_values[i] = value;25                 return;26             }27         }28         m_keys[i] = key;29         m_values[i] = value;30         m_n++;31     }32 33     public Value Get(Key key) {34         for (int i = Hash(key); m_keys[i] != null; i = (i + 1) % m_m) {35             if (m_keys[i].Equals(key)) {36                 return m_values[i];37             }38         }39         return null;40     }41 42     public void Resize(int capacity) {43         LinearProbingHashSymbolTable
       
         t = new LinearProbingHashSymbolTable
        
         (capacity);44         for (int i = 0; i < m_m; i++) {45             if(m_keys[i] != null) {46                 t.Put(m_keys[i], m_values[i]);47             }48         }49         m_keys = t.m_keys;50         m_values = t.m_values;51         m_m = t.m_m;52     }53 }
        
       
      

 

第4章 图

Graph

定义 图是由一组顶点和一组能够将两个顶点相连的边组成的.

定义 在图中,路径是由边顺序连接的一系列顶点.简单路径是一条没有重复顶点的路径.环是一条至少含有一条边且起点和终点相同的路径.简单环是一条(除了起点和终点必须相同之外)不含有重复顶点和边的环.

　　路径或者环的长度为其中所包含的边数.

定义 如果从任意一个顶点都存在一条路径到达另一个任意顶点,我们称这副图是连通图.一幅非连通的图由若干连通的部分组成,他们都是其极大连通子图

定义 树是一幅无环连通图.互不相连的树组成的集合称为森林.连通图的生成树是它的一幅子图,它含有图中的所有顶点且是一颗树.图的生成树森林是它的所有连通子图的生成树的集合.

1 public class Graph { 2     public int m_v; 3     public int m_e; 4  5     public List
      
       
        > m_adj; 6  7     public Graph(int v) { 8         m_v = v; 9         m_e = 0;10         m_adj = new List
        
         
          >();11         for (int i = 0; i < m_v; i++) {12             m_adj.Add(new List
          
           ());13         }14     }15 16     public int V() {17         return m_v;18     }19 20     public int E() {21         return m_e;22     }23 24     public void AddEdge(int v,int w) {25         m_adj[v].Add(w);26         m_adj[w].Add(v);27         m_e++;28     }29 30     public IEnumerable
           
             Adj(int v) {31 return m_adj[v];32 }
           
          
         
        
       
      

1 private class DepthFirstPaths { 2     private bool[] m_marked; //这个顶点上调用过DFS吗 3     private int[] m_edgeTo; //到达该顶点的路径 4     private int m_source;   //起点 5  6     public DepthFirstPaths(Graph g,int s) { 7         m_marked = new bool[g.V()]; 8         m_edgeTo = new int[g.V()]; 9         m_source = s;10     }11 12     public void DFS(Graph g,int v) {13         m_marked[v] = true;14         foreach (var item in g.Adj(v)) {15             if (!m_marked[item]) {16                 m_edgeTo[item] = v;17                 DFS(g, item);18             }19         }20     }21 22     public bool HasPathTo(int v) {23         return m_marked[v];24     }25 26     public IEnumerable
      
        PathTo(int v) {27         if (!HasPathTo(v)) {28             return null;29         }30         Stack
       
         path = new Stack
        
         ();31         for (int i = v; i != m_source; i = m_edgeTo[i]) {32             path.Push(i);33         }34         path.Push(m_source);35         return path;36     }37 }
        
       
      

1 public class BreadthFirstPaths { 2     private bool[] m_marked; //这个顶点上调用过BFS吗 3     private int[] m_edgeTo; //到达该顶点的路径 4     private int m_source;   //起点 5  6     public BreadthFirstPaths(Graph g,int s) { 7         m_marked = new bool[g.V()]; 8         m_edgeTo = new int[g.V()]; 9         m_source = s;10     }11 12     public void BFS(Graph g,int s) {13         Queue
      
        queue = new Queue
       
        ();14         m_marked[s] = true;15         queue.Enqueue(s);16 17         while (queue.Count != 0) {18             int v = queue.Dequeue();19             foreach (var item in g.Adj(v)) {20                 if (!m_marked[item]) {21                     m_edgeTo[item] = v;22                     m_marked[item] = true;23                     queue.Enqueue(item);24                 }25             }26         }27     }28 29     public bool HasPathTo(int v) {30         return m_marked[v];31     }32 33     public IEnumerable
        
          PathTo(int v) {34         if (!HasPathTo(v)) {35             return null;36         }37         Stack
         
           path = new Stack
          
           ();38         for (int i = v; i != m_source; i = m_edgeTo[i]) {39             path.Push(i);40         }41         path.Push(m_source);42         return path;43     }44 }
          
         
        
       
      

1 public class ConnectedComponent { 2     public bool[] m_marked; 3     public int[] m_id; 4     public int m_count; 5  6     public ConnectedComponent(Graph g) { 7         m_marked = new bool[g.V()]; 8         m_id = new int[g.V()]; 9         for (int i = 0; i < g.V(); i++) {10             if (!m_marked[i]) {11                 DFS(g, i);12                 m_count++;13             }14         }15     }16 17     public void DFS(Graph g,int v) {18         m_marked[v] = true;19         m_id[v] = m_count;20         foreach (var item in g.Adj(v)) {21             if (!m_marked[item]) {22                 DFS(g, item);23             }24         }25     }26 27     public bool Connected(int v,int w) {28         return m_id[v] == m_id[w];29     }30 31     public int ID(int v) {32         return m_id[v];33     }34 35     public int Count() {36         return m_count;37     }38 }

Digraph

定义 一幅有方向性的图(或有向图)是由一组顶点和一组有方向的边组成的,每条有方向的边都连接着有序的一对顶点.

定义 在一幅有向图中,有向路径由一系列顶点组成,对于其中的每个顶点都存在一条有向边从它指向序列中的下一个顶点.有向环为一条至少含有一条边且起点和终点相同的有向路径.

　　简单有向环是一条(除了起点和终点必须相同之外)不含有重复的顶点和边的环.路径或者环的长度即为其中所包含的边数.

1 public class Digraph { 2     public int m_v; 3     public int m_e; 4     public List
      
       
        > m_adj; 5  6     public Digraph(int v) { 7         m_v = v; 8         m_e = 0; 9         m_adj = new List
        
         
          >();10         for (int i = 0; i < m_v; i++) {11             m_adj.Add(new List
          
           ());12         }13     }14 15     public int V() {16         return m_v;17     }18 19     public int E() {20         return m_e;21     }22 23     public void AddEdge(int v,int w) {24         m_adj[v].Add(w);25         m_e++;26     }27 28     public IEnumerable
           
             Adj(int v) {29 return m_adj[v];30 }31 32 public Digraph Reverse() {33 Digraph r = new Digraph(m_v);34 for (int i = 0; i < m_v; i++) {35 foreach (var item in m_adj[i]) {36 r.AddEdge(item, i);37 }38 }39 return r;40 }41 }
           
          
         
        
       
      

1 public class DirectedDFS { 2     public bool[] m_marked; 3  4     public DirectedDFS(Digraph g,int s) { 5         m_marked = new bool[g.V()]; 6         DFS(g, s); 7     } 8  9     public DirectedDFS(Digraph g,IEnumerable
      
        sources) {10         m_marked = new bool[g.V()];11         foreach (var item in sources) {12             if (!m_marked[item]) {13                 DFS(g, item);14             }15         }16     }17 18     private void DFS(Digraph g,int v) {19         m_marked[v] = true;20         foreach (var item in g.m_adj[v]) {21             if (!m_marked[item]) {22                 DFS(g, item);23             }24         }25     }26 27     public bool Marked(int v) {28         return m_marked[v];29     }30 }
      

定义 有向无环图(DAG)就是一幅不含有向环的有向图

1 public class DirectedCycle { 2     public bool[] m_marked; 3     public int[] m_edgeTo; 4     public Stack
      
        m_cycle; 5     public bool[] m_onStack; 6  7     public DirectedCycle(Digraph g) { 8         m_onStack = new bool[g.V()]; 9         m_edgeTo = new int[g.V()];10         m_marked = new bool[g.V()];11         for (int i = 0; i < g.V(); i++) {12             if (!m_marked[i]) {13                 DFS(g, i);14             }15         }16     }17 18     public void DFS(Digraph g,int v) {19         m_onStack[v] = true;20         m_marked[v] = true;21         foreach (var item in g.Adj(v)) {22             if (HasCycle()) {23                 return;24             }25             else if (!m_marked[item]) {26                 m_edgeTo[item] = v;27                 DFS(g, item);28             } else if (m_onStack[item]) {29                 m_cycle = new Stack
       
        ();30                 for (int i = v; i != item; i = m_edgeTo[i]) {31                     m_cycle.Push(i);32                 }33                 m_cycle.Push(item);34                 m_cycle.Push(v);35             }36         }37     }38 39     public bool HasCycle() {40         return m_cycle != null;41     }42 43     public IEnumerable
        
          Cycle() {44         return m_cycle;45     }46 }
        
       
      

1 public class DepthFirstOrder { 2     public bool[] m_marked; 3     public Queue
      
        m_pre; 4     public Queue
       
         m_post; 5     public Stack
        
          m_reversePost; 6  7     public DepthFirstOrder(Digraph g) { 8         m_pre = new Queue
         
          (); 9         m_post = new Queue
          
           ();10         m_reversePost = new Stack
           
            ();11 m_marked = new bool[g.V()];12 for (int i = 0; i < g.V(); i++) {13 if (!m_marked[i]) {14 DFS(g, i);15 }16 }17 }18 19 public void DFS(Digraph g,int v) {20 m_pre.Enqueue(v);21 22 m_marked[v] = true;23 foreach (var item in g.Adj(v)) {24 if (!m_marked[item]) {25 DFS(g, v);26 }27 }28 29 m_post.Enqueue(v);30 m_reversePost.Push(v);31 }32 33 public IEnumerable
            
              Pre() {34 return m_pre;35 }36 37 public IEnumerable
             
               Post() {38 return m_post;39 }40 41 public IEnumerable
              
                ReversePost() {42 return m_reversePost;43 }44 }
              
             
            
           
          
         
        
       
      

1 public class Topological { 2     public IEnumerable
      
        m_order; 3  4     public Topological(Digraph g) { 5         DirectedCycle cycleFinder = new DirectedCycle(g); 6         if (!cycleFinder.HasCycle()) { 7             DepthFirstOrder dfs = new DepthFirstOrder(g); 8             m_order = dfs.ReversePost(); 9         }10     }11 12     public IEnumerable
       
         Order() {13         return m_order;14     }15 16     public bool IsDAG() {17         return m_order != null;18     }19 }
       
      

1 public class KosarajuStronglyConnectedComponent { 2     private bool[] m_marked;    // 已访问过的顶点 3     private int[] m_id; // 强连通分量的标识符 4     private int m_count;  // 强连通分量的数量 5  6     public KosarajuStronglyConnectedComponent(Digraph g) { 7         m_marked = new bool[g.V()]; 8         m_id = new int[g.V()]; 9 10         DepthFirstOrder order = new DepthFirstOrder(g.Reverse());11         foreach (var item in order.ReversePost()) {12             if (!m_marked[item]) {13                 DFS(g, item);14                 m_count++;15             }16         }17     }18 19     public void DFS(Digraph g,int v) {20         m_marked[v] = true;21         m_id[v] = m_count;22         foreach (var item in g.Adj(v)) {23             if (!m_marked[item]) {24                 DFS(g, item);25             }26         }27     }28 29     public bool StronglyConnected(int v,int w) {30         return m_id[v] == m_id[w];31     }32 33     public int Id(int v) {34         return m_id[v];35     }36 37     public int Count() {38         return m_count;39     }40 }

MST(minimum spanning tree) 定义 图的生成树是它的一棵含有其所有顶点的无环连通子图.一幅加权图的最小生成树(MST)是它的一颗权值(树中所有边的权值之和)最小的生成树

定义 图的一种切分是将图的所有顶点分为两个非空且不重叠的两个集合.横切边是一条连接两个属于不同集合的顶点的边.

1 public class Edge : IComparable
      
        { 2     private int m_v; 3     private int m_w; 4     private double m_weight; 5  6     public Edge(int v, int w, double weight) { 7         m_v = v; 8         m_w = w; 9         m_weight = weight;10     }11 12     public double Weight() {13         return m_weight;14     }15 16     public int Either() {17         return m_v;18     }19 20     public int Other(int vertex) {21         if(vertex == m_v) {22             return m_w;23         } else if(vertex == m_w) {24             return m_v;25         } else {26             throw new Exception("Inconsistent edge");27         }28     }29 30     public int CompareTo(Edge that) {31         if(Weight() < that.Weight()) {32             return -1;33         } else if(Weight() > that.Weight()) {34             return +1;35         } else {36             return 0;37         }38     }39 40     override public string ToString() {41         return string.Format("{0:d}-{1:d} {2:f}", m_v, m_w, m_weight);42     }43 }
      

1 public class EdgeWeightedGraph { 2     private int m_v; 3     private int m_e; 4     private List
      
       
        > m_adj; 5  6     public EdgeWeightedGraph(int v) { 7         m_v = v; 8         m_e = 0; 9         m_adj = new List
        
         
          >();10         for (int i = 0; i < m_v; i++) {11             m_adj.Add(new List
          
           ());12         }13     }14 15     public int V() {16         return m_v;17     }18 19     public int E() {20         return m_e;21     }22 23     public void AddEdge(Edge e) {24         int v = e.Either();25         int w = e.Other(v);26         m_adj[v].Add(e);27         m_adj[w].Add(e);28         m_e++;29     }30 31     public IEnumerable
           
             Adj(int v) {32 return m_adj[v];33 }34 35 public IEnumerable
            
              Edges() {36 List
             
               b = new List
              
               ();37 for (int i = 0; i < m_v; i++) {38 foreach (var item in m_adj[i]) {39 if(item.Other(i) > i) {40 b.Add(item);41 }42 }43 }44 return b;45 }46 }
              
             
            
           
          
         
        
       
      

1 public class LazyPrimMST { 2     public bool[] m_marked; // 最小生成树的定点 3     public Queue
      
        m_mst;   // 最小生成树的边 4     public MinPQ
       
         m_pq;    // 横切边(包括失效的边) 5  6     public LazyPrimMST(EdgeWeightedGraph g) { 7         m_pq = new MinPQ
        
         (); 8         m_marked = new bool[g.V()]; 9         m_mst = new Queue
         
          ();10 11         Visit(g, 0);    // 假设g是连通的12         while (!m_pq.IsEmpty()) {13             Edge e = m_pq.delMin(); //从pq中得到权重最小的边14 15             int v = e.either();16             int w = e.other(v);17 18             if(m_marked[v] && m_marked[w]) {19                 continue;20             }21 22             if (!m_marked[v]) {23                 Visit(g, v);24             }25 26             if (!m_marked[w]) {27                 Visit(g, w);28             }29         }30     }31 32     public void Visit(EdgeWeightedGraph g,int v) {33         m_marked[v] = true;34         foreach (var item in g.adj(v)) {35             if (!m_marked[item.other(v)]) {36                 m_pq.insert(item);37             }38         }39     }40 41     public IEnumerable
          
            Edges() {42         return m_mst;43     }44 45     public double Weight() { }46 47 }
          
         
        
       
      

1 public class PrimMST { 2     public Edge[] m_edgeTo; // 距离树最近的边 3     public double[] m_distTo;   // distTo[w] = m_edgeTo[w].weight(); 4     public bool[] m_marked; // 如果v在树中则为true 5     public IndexMinPQ
      
        m_pq; // 有效的横切边 6  7     public PrimMST(EdgeWeightedGraph g) { 8         m_edgeTo = new Edge[g.V()]; 9         m_distTo = new double[g.V()];10         m_marked = new bool[g.V()];11         for (int i = 0; i < g.V(); i++) {12             m_distTo[i] = double.PositiveInfinity;13         }14         m_pq = new IndexMinPQ
       
        (g.V());15 16         m_distTo[0] = 0.0;17         m_pq.insert(0, 0.0);    // 用顶点0和权重0初始化m_pq18 19         while (!m_pq.isEmpty()) {20             Visit(g, m_pq.delMin());21         }22     }23 24     public void Visit(EdgeWeightedGraph g,int v) {25         // 将顶点v添加到树中,更新数据26         m_marked[v] = true;27         foreach (var item in g.adj(v)) {28             int w = item.other(v);29 30             if (m_marked[w]) {31                 continue;   // v-w失效32             }33             if(item.Weight() < m_distTo[w]) {34                 // 连接w和树的最佳边Edge变成e35                 m_edgeTo[w] = item;36 37                 m_distTo[w] = item.weight();38                 if (m_pq.contains(w)) {39                     m_pq.change(w, m_distTo[w]);40                 } else {41                     m_pq.insert(w, m_distTo[w]);42                 }43             }44         }45     }46 }
       
      

1 public class KruskalMST { 2     public Queue
      
        m_mst; 3  4     public KruskalMST(EdgeWeightedGraph g) { 5         m_mst = new Queue
       
        (); 6         MinPQ
        
          pq = new MinPQ
         
          (); 7  8         foreach (var item in g.edges()) { 9             pq.insert(item);10         }11 12         UF uf = new UF(g.V());13 14         while(!pq.isEmpty() && m_mst.size() < g.V() - 1) {15             Edge e = pq.delMin();   // 从pq得到权重最小的边和它的顶点16             int v = e.either();17             int w = e.other(v);18             if (uf.connected(v, w)) {19                 continue;   // 忽略失效的边20             }21             uf.union(v, w); // 合并分量22             m_mst.Enqueue(e);   // 将边添加到最下生成树中23         }24     }25 26     public IEnumerable
          
            Edges() {27         return m_mst;28     }29 30     public double Weight() {31 32     }33 }
          
         
        
       
      

最短路径

定义 在一幅加权有向图中,从顶点s到顶点t的最短路径是所有从s到t的路径中的权重最小者

定义 给定一幅加权有向图和一个顶点s,以s为起点的一颗最短路径树是图的一幅子图,它包含s和从s可达的所有顶点.这棵有向树的根结点为s,树的每条路径都是有向图中的一条最短路径.

1 public class DirectedEdge { 2     public int m_v; // 边的起点 3     public int m_w; // 边的终点 4     public double m_weight; // 边的权重 5  6     public DirectedEdge(int v,int w,double weight) { 7         m_v = v; 8         m_w = w; 9         m_weight = weight;10     }11 12     public double Weight() {13         return m_weight;14     }15 16     public int From() {17         return m_v;18     }19 20     public int To() {21         return m_w;22     }    23 }

1 public class EdgeWeightedDigraph { 2     public int m_v; // 顶点总数 3     public int m_e; // 边的总数 4     public Bag
      
       [] m_adj;   // 邻接表 5  6     public EdgeWeightedDigraph(int v) { 7         m_v = v; 8         m_e = 0; 9         m_adj = new Bag
       
        [v];10 11         for (int i = 0; i < v; i++) {12             m_adj[i] = new Bag
        
         ();13         }14     }15 16     public int V() {17         return m_v;18     }19 20     public int E() {21         return m_e;22     }23 24     public void AddEdge(DirectedEdge e) {25         m_adj[e.From()].add(e);26         m_e++;27     }28 29     public IEnumerable
         
           Adj(int v) {30         return m_adj[v];31     }32 33     public IEnumerable
          
            Edges() {34         Bag
           
             bag = new Bag
            
             ();35 for (int i = 0; i < m_v; i++) {36 foreach (var item in m_adj[m_v]) {37 bag.add(item);38 }39 }40 return bag;41 }42 }
            
           
          
         
        
       
      

 

第5章 字符串

1 public class LSD { 2     public static void Sort(string[] a, int w) { 3         int n = a.Length; 4         int r = 256; 5         string[] auxiliary = new string[n]; 6  7         for (int i = w - 1; i >= 0; i--) { 8             int[] count = new int[r + 1]; 9                 10             //计算出现频率11             for (int j = 0; j < n; j++) {12                 count[a[j].CharAt(i) + 1]++;13             }14 15             //将频率转换为索引16             for (int j = 0; j < r; j++) {17                 count[j + 1] += count[j];18             }19 20             //将元素分类21             for (int j = 0; j < n; j++) {22                 auxiliary[count[a[j].CharAt(i)]++] = a[j];23             }24 25             //回写26             for (int j = 0; j < n; j++) {27                 a[j] = auxiliary[j];28             }29         }30     }31 }

 

 

1 public class TrieSymbolTable
      
        { 2     public static int m_R = 256; 3     public Node m_root; 4          5     public class Node { 6         public object m_value; 7         public Node[] m_next = new Node[m_R]; 8     } 9 10     public Value Get(string key) {11         Node node = Get(m_root, key, 0);12         if(node == null) {13             return default(Value);14         }15         return (Value)node.m_value;16     }17 18     public Node Get(Node node,string key,int d) {19         if(node == null) {20             return null;21         }22         if(d == key.Length) {23             return node;24         }25         char c = key.CharAt(d);26         return Get(node.m_next[c], key, d + 1);27     }28 29     public void Put(string key,Value value) {30             31     }32 33     public Node Put(Node node,string key,Value value,int d) {34         if(node == null) {35             node = new Node();36         }37         if(d == key.Length) {38             node.m_value = value;39             return node;40         }41         char c = key.CharAt(d);42         node.m_next[c] = Put(node.m_next[c], key, value, d + 1);43         return node;44     }45 }
      

 

 

 

 

 

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------