寫在前面

新增了一行內容，
整個專案都托管在了 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 = https://www.cnblogs.com/tribes/p/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 發布

標籤：C#

上一篇：型別是什么

下一篇：ServiceStack.Redis 的 ASP.NET Core 擴展庫