写在前面

新增了一行内容。
整个项目都托管在了 Github 上：https://github.com/ikesnowy/Algorithms-4th-Edition-in-Csharp
查找更方便的版本见：https://alg4.ikesnowy.com/
这一节内容可能会用到的库文件有 SymbolTable，同样在 Github 上可以找到。
善用 Ctrl + F 查找题目。

习题&题解

3.1.1

解答

官方解答：https://algs4.cs.princeton.edu/31elementary/GPA.java.html
ST.java：https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/ST.java.html

建立一个符号表，然后把键值放进去，读取计算即可。
和上一章节用过的方法类似，先定义了一个接口 IST<Key, Value> ，包含书中提到的基本 API。
然后定义类 ST ，用标准库里面的 Dictionary 实现了 IST 。

代码

using System.Collections; using System.Collections.Generic;  namespace SymbolTable {     /// <summary> 利用库函数实现的标准符号表。 </summary>     public class ST<Key, Value> : IST<Key, Value>, IEnumerable<Key>     {         private Dictionary<Key, Value> st;          /// <summary> 新建一个符号表。 </summary>         public ST() => this.st = new Dictionary<Key, Value>();          /// <summary> 检查符号表中是否存在与键 <paramref name="key"/> 对应的值。 </summary>         public virtual bool Contains(Key key) => this.st.ContainsKey(key);          /// <summary> 从符号表中删除键 <paramref name="key"/> 及对应的值。 </summary>         public virtual void Delete(Key key) => this.st.Remove(key);          /// <summary> 获取键 <paramref name="key"/> 对应的值，不存在时返回 null。 </summary>         public virtual Value Get(Key key) => this.st[key];          /// <summary> 获取枚举器。 </summary>         public IEnumerator<Key> GetEnumerator() => this.st.Keys.GetEnumerator();          /// <summary> 检查符号表是否为空。 </summary>         public virtual bool IsEmpty() => this.st.Count == 0;          /// <summary> 获得符号表中所有键的集合。 </summary>         public virtual IEnumerable<Key> Keys() => this.st.Keys;          /// <summary> 向符号表中插入新的键值对。 </summary>         public virtual void Put(Key key, Value value) => this.st.Add(key, value);          /// <summary> 获取符号表中键值对的数量。 </summary>         public virtual int Size() => this.st.Count;          /// <summary> 获取枚举器。 </summary>         IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();     } } 

另请参阅

SymbolTable 库

3.1.2

解答

官方解答：https://algs4.cs.princeton.edu/31elementary/ArrayST.java.html

建立两个数组，分别存放键和值，一一对应。
添加时直接将新键值对放到数组最后即可。
删除时将待删除的键值对和位于最后的键值对交换，然后将其置空即可。

代码

using System; using System.Collections.Generic;  namespace SymbolTable {     /// <summary>     /// 符号表（数组实现）。     /// </summary>     /// <typeparam name="Key">键类型。</typeparam>     /// <typeparam name="Value">值类型。</typeparam>     public class ArrayST<Key, Value> : IST<Key, Value>      {         private Key[] keys;             // 键数组         private Value[] values;         // 值数组         private int n = 0;              // 键值对数目          /// <summary>         /// 建立基于数组实现的符号表。         /// </summary>         public ArrayST() : this(8) { }          /// <summary>         /// 建立基于数组实现的符号表。         /// </summary>         /// <param name="initCapacity">初始大小。</param>         public ArrayST(int initCapacity)         {             this.keys = new Key[initCapacity];             this.values = new Value[initCapacity];         }          /// <summary>         /// 检查键 <typeparamref name="Key"/> 是否存在。         /// </summary>         /// <param name="key">需要检查是否存在的键。</param>         /// <returns></returns>         public bool Contains(Key key) => Get(key).Equals(default(Key));          /// <summary>         /// 删除键 <paramref name="key"/> 及对应的值。         /// </summary>         /// <param name="key">需要删除的键。</param>         public void Delete(Key key)         {             for (int i = 0; i < this.n; i++)             {                 if (key.Equals(this.keys[i]))                 {                     this.keys[i] = this.keys[this.n - 1];                     this.values[i] = this.values[this.n - 1];                     this.keys[this.n - 1] = default(Key);                     this.values[this.n - 1] = default(Value);                     this.n--;                     if (this.n > 0 && this.n == this.keys.Length / 4)                         Resize(this.keys.Length / 2);                     return;                 }             }         }          /// <summary>         /// 获取键对应的值，若键不存在则返回 null。         /// </summary>         /// <param name="key">需要查找的键。</param>         /// <returns></returns>         public Value Get(Key key)         {             for (int i = 0; i < this.n; i++)                 if (this.keys[i].Equals(key))                     return this.values[i];             return default(Value);         }          /// <summary>         /// 检查符号表是否为空。         /// </summary>         /// <returns></returns>         public bool IsEmpty() => this.n == 0;          /// <summary>         /// 获得包含全部键的集合。         /// </summary>         /// <returns></returns>         public IEnumerable<Key> Keys()         {             Key[] result = new Key[this.n];             Array.Copy(this.keys, result, this.n);             return result;         }          /// <summary>         /// 向符号表中插入新元素，若键存在将被替换。         /// </summary>         /// <param name="key">键。</param>         /// <param name="value">值。</param>         public void Put(Key key, Value value)         {             Delete(key);              if (this.n >= this.values.Length)                 Resize(this.n * 2);              this.keys[this.n] = key;             this.values[this.n] = value;             this.n++;         }          /// <summary>         /// 返回符号表中键值对的数量。         /// </summary>         /// <returns>键值对数量。</returns>         public int Size() => this.n;          /// <summary>         /// 为符号表重新分配空间。         /// </summary>         /// <param name="capacity">新分配的空间大小。</param>         private void Resize(int capacity)         {             Key[] tempKey = new Key[capacity];             Value[] tempValue = new Value[capacity];              for (int i = 0; i < this.n; i++)                 tempKey[i] = this.keys[i];             for (int i = 0; i < this.n; i++)                 tempValue[i] = this.values[i];              this.keys = tempKey;             this.values = tempValue;         }     } } 

另请参阅

SymbolTable 库

本文由博客群发一文多发等运营工具平台 OpenWrite 发布