C#資料型別實現揹包、佇列和棧

2022-04-15 13:00:57

基礎程式設計模型和資料抽象

把描述和實現演演算法所用到的語言特性，軟體庫和作業系統特性總稱為基礎程式設計模型。

編寫遞迴程式碼注意的點：

1. 遞迴總有一個最簡單的情況 —— 方法的第一條語句總是包含 return 的條件語句。
2. 遞迴呼叫總是嘗試解決一個規模更小的子問題，這樣遞迴才能收斂到最簡單的情況。
3. 遞迴呼叫的父問題和嘗試解決的子問題之間不應該有交集。

資料型別指的是一組值和一組對這些值的操作的集合。抽象資料型別（ADT）是一種能夠對使用者隱藏資料表示的資料型別。用高階語言的類來實現抽象資料型別和用一組靜態方法實現一個函數庫並沒有什麼不同。抽象資料型別的主要不同之處在於它將資料和函數的實現關聯，並將資料的表示方式隱藏起來。在使用抽象資料型別時，我們的注意力集中在API 描述的操作上而不會去關心資料的表示；在實現抽象資料型別時，我們的注意力集中在資料本身並將實現對該資料的各種操作。

抽象資料之所以重要是因為在程式設計上支援封裝。

我們研究同一問題的不同演演算法的主要原因在於他們的效能特點不同。抽象資料型別可以在不修改測試程式碼的情況下用一種演演算法替換另一種演演算法。

資料抽象中的一個基礎概念：物件是能夠承載資料型別的值的實體。所有的物件都有三大特性：狀態，標識和行為。物件的狀態即資料型別中的值。物件的標識就是它在記憶體中的位置。物件的行為就是資料型別的操作。

許多基礎資料型別都和物件的集合有關。資料型別的值就是一組物件的集合，所有操作都是關於新增，刪除或是存取集合中的物件。揹包（Bag），佇列（Quene）和棧（Stack）它們的不同之處在於刪除或者存取物件的順序不同。

1. API

Stack 和 Quene 都含有一個能夠刪除集合中特定元素的方法。

實現上面API需要高階語言的特性：泛型，裝箱拆箱，可迭代（實現IEnumerable 介面）。

1. 揹包

揹包是一種不支援從中刪除元素的集合型別——它的目的就是幫助用例收集元素並迭代遍歷所有元素。用例也可以使用棧或者佇列，但使用 Bag 可以說明元素的處理順序不重要。

2.先進先出佇列

佇列是基於先進先出（FIFO）策略的集合型別。

3. 下壓棧

下壓棧（簡稱棧）是一種基於後進先出（LIFO）策略的集合型別。

應用例子：計算輸入字串（1+（（2+3）*（4*5）））表示式的值。

使用雙棧解決：

1. 將運算元壓入運算元棧；
2. 將運運算元壓入運運算元棧；
3. 忽略做括號；
4. 在遇到右括號時，彈出一個運運算元，彈出所需數量的運算元，並將運運算元和運算元的運算結果壓入運算元棧。

2.用陣列實現

實現下壓棧：

//想要資料型別可迭代，需要實現IEnumerable
    public class ResizingStack<Item> : IEnumerable<Item>
    {
        private Item[] a = new Item[1];
        private int N = 0;
        public bool IsEmpty{ get {
                return N == 0;
            } }
        public int Size { get {
                return N;
            } }
        public int Count { get; set; }

        /// <summary>
        /// 使陣列處於半滿
        /// </summary>
        /// <param name="max"></param>
        private void Resize(int max)
        {
            Count = 0;
            Item[] temp = new Item[max];
            for(var i = 0;i<N;i++)
            {
                temp[i] = a[i];
                Count++;
            }
            a = temp;
        }

        public void push(Item item)
        {
            if (N == a.Length)
                Resize(a.Length * 2);
            a[N++] = item;
        }

        public Item Pop()
        {
            Item item = a[--N];
            a[N] = default(Item); //避免物件遊離
            if (N > 0 && N == a.Length / 4)
                Resize(a.Length/2);
            return item;
        }

        IEnumerator<Item> IEnumerable<Item>.GetEnumerator()
        {
            return new ResizingStackEnumerator<Item>(a);
        }

        public IEnumerator GetEnumerator()
        {
            return new ResizingStackEnumerator<Item>(a);
        }

    }
    class ResizingStackEnumerator<Item> : IEnumerator<Item>
    {
        private Item[] a;
        private int N = 0;
        public ResizingStackEnumerator(Item[] _a)
        {
            a = _a;
            N = a.Length-1;
        }

        public object Current => a[N--];

        Item IEnumerator<Item>.Current => a[N--];

        public void Dispose()
        {
            throw new NotImplementedException();
        }

        public bool MoveNext()
        {
            return N > 0;
        }

        public void Reset()
        {
            throw new NotImplementedException();
        }
    }

3.連結串列

連結串列是在集合類的抽象資料型別實現中表示資料的另一種基礎資料結構。

定義：連結串列是一種遞迴的資料結構，它或者指向空，或者指向另一個節點的參照，該節點含有一個泛型元素和一個指向另一個連結串列的參照。

class Node<Item>
    {
        public Item item { get; set; }
        public Node<Item> Next { get; set; }
    }

1.構造連結串列

連結串列表示的是一列元素。

根據遞迴的定義，只需要一個 Node 型別的變數就能表示一條連結串列，只要保證它的 Next 值是 null 或指向另一個 Node 物件，該物件的 Next 指向另一條連結串列。

2.在表頭插入結點

在連結串列列表中插入新節點的最簡單位置是開始。要在首結點為 first 的給定連結串列開頭插入字串 not ，先將 first 儲存在 oldfirst 中，然後將一個新結點賦予 first ，並將 first 的 item 設為 not, Next 設定為 oldfirst 。

在連結串列開頭插入一個結點所需的時間和連結串列長度無關。

3.從表頭刪除結點

只需將 first 指向 first.next 即可。first 原來指向的物件變成了一個孤兒，垃圾回收機制會將其回收。

同樣，該操作所需的時間和連結串列長度無關。

4.在表尾插入結點

當連結串列不止有一個結點時，需要一個指向連結串列最後結點的連結 oldlast，建立新的結點，last 指向新的最後結點。然後 oldlast.next 指向 last。

當連結串列只有一個結點時，首結點又是尾結點。只需將 last 指向新的結點，然後 first.next 指向 last。

5.其他位置的插入和刪除操作

上述操作可以很容易的實現，但是下面的操作比較複雜：

1. 刪除指定的結點
2. 在指定結點前插入一個新結點

這些操作需要我們遍歷連結串列，它所需的時間和連結串列的長度成正比。想要實現任意插入和刪除結點需要使用雙向連結串列，其中每個結點都含有兩個連結，分別指向上一個和下一個結點。

6. 遍歷

簡單實現：

public class Bag<Item>
    {
        private Node<Item> first;
        public void Add(Item item)
        {
            Node<Item> oldFirst = first;
            first = new Node<Item>() { 
                item = item,
                Next = oldFirst
            };

        }
    }

Bag<int> bags = new Bag<int>();
            for (var i = 0; i < 10; i++)
            {
                bags.Add(i);
            }

            for (var x = bags.first; x != null; x = x.Next)
            {
                Console.WriteLine(x.item);
            }

實現 IEnumerable 介面實現遍歷：

public class Bag<Item>: IEnumerable<Item>
    {
        public Node<Item> first;
        public void Add(Item item)
        {
            Node<Item> oldFirst = first;
            first = new Node<Item>() { 
                item = item,
                Next = oldFirst
            };

        }

        public IEnumerator<Item> GetEnumerator()
        {
            return new LineEnumerator<Item>(first);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return new LineEnumerator<Item>(first);
        }
    }

    public class LineEnumerator<Item> : IEnumerator<Item>
    {
        public Node<Item> first;
        public LineEnumerator(Node<Item> _first)
        {
            first = _first;
        }
        public Item Current { get {
                var oldfirst = first;
                first = first.Next;
                return oldfirst.item;
            } }

        object IEnumerator.Current => first;

        public void Dispose()
        {
            return;
        }

        public bool MoveNext()
        {
            if (first != null)
                return true;
            return false;
        }

        public void Reset()
        {
            throw new NotImplementedException();
        }
    }

public static void LineTest()
        {
            Bag<int> bags = new Bag<int>();
            for (var i = 0; i < 10; i++)
            {
                bags.Add(i);
            }

            foreach(var bag in bags)
            {
                Console.WriteLine(bag);
            }
        }

4. 用連結串列實現揹包

見上述程式碼。

5. 用連結串列實現棧

Stack API 中 Pop() 刪除一個元素，按照前面的從表頭刪除結點實現，Push() 新增一個元素，按照前面在表頭插入結點。

public class Stack<Item> : IEnumerable<Item>
    {
        public Node<Item> first;
        private int N;


        public bool IsEmpty()
        {
            return first == null; //或 N == 0
        }

        public int Size()
        {
            return N;
        }

        public void Push(Item item)
        {
            Node<Item> oldfirst = first;
            first = new Node<Item>() { 
                item = item,
                Next = oldfirst
            };
            N++;
        }

        public Item Pop()
        {
            Item item = first.item;
            first = first.Next;
            N--;
            return item;
        }

        public IEnumerator<Item> GetEnumerator()
        {
            return new StackLineIEnumerator<Item>(first);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return new StackLineIEnumerator<Item>(first);
        }
    }

    public class StackLineIEnumerator<Item> : IEnumerator<Item>
    {
        private Node<Item> first;
        public StackLineIEnumerator(Node<Item> _first)
        {
            first = _first;
        }
        public Item Current { get {
                var oldfirst = first;
                first = first.Next;
                return oldfirst.item;
            } }

        object IEnumerator.Current => throw new NotImplementedException();

        public void Dispose()
        {
            return;
        }

        public bool MoveNext()
        {
            return first != null;
        }

        public void Reset()
        {
            throw new NotImplementedException();
        }
    }

連結串列的使用達到了最優設計目標：

1. 可以處理任意型別的資料；
2. 所需的空間總是和集合的大小成正比；
3. 操作所需的時間總是和集合的大小無關；

6. 用連結串列實現佇列

需要兩個範例變數，first 指向佇列的開頭，last 指向佇列的表尾。新增一個元素 Enquene() ，將結點新增到表尾（連結串列為空時，first 和 last 都指向新結點）。刪除一個元素 Dequene() ，刪除表頭的結點（刪除後，當佇列為空時，將 last 更新為 null）。

    public class Quene<Item> : IEnumerable<Item>
    {
        public Node<Item> first;
        public Node<Item> last;
        private int N;

        public bool IsEmpty()
        {
            return first == null;
        }

        public int Size()
        {
            return N;
        }

        public void Enquene(Item item)
        {
            var oldlast = last;
            last = new Node<Item>() { 
                item = item,
                Next = null
            };

            if (IsEmpty())
                first = last;
            else
                oldlast.Next = last;
            N++;
        }

        public Item Dequene()
        {
            if (IsEmpty())
                throw new Exception();
            Item item = first.item;
            first = first.Next;
            if (IsEmpty())
                last = null;
            N--;
            return item;
        }

        public IEnumerator<Item> GetEnumerator()
        {
            return new QueneLineEnumerator<Item>(first);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return new QueneLineEnumerator<Item>(first);
        }
    }
    public class QueneLineEnumerator<Item> : IEnumerator<Item>
    {
        private Node<Item> first;
        public QueneLineEnumerator(Node<Item> _first)
        {
            first = _first;
        }
        public Item Current { get {
                var oldfirst = first;
                first = first.Next;
                return oldfirst.item;
            } }

        object IEnumerator.Current => throw new NotImplementedException();

        public void Dispose()
        {
            return;
        }

        public bool MoveNext()
        {
            return first != null ;
        }

        public void Reset()
        {
            throw new NotImplementedException();
        }
    }

7. 總結

在結構化儲存資料集時，連結串列是陣列的一種重要的替代方式。

陣列和連結串列這兩種資料型別為研究演演算法和更高階的資料結構打下了基礎。

基礎資料結構：

資料結構	優點	缺點
陣列	通過索引可以直接存取任意元素	在初始化時就需要知道元素的數量
連結串列	使用的空間大小和元素數量成正比	需要通過參照存取任意元素

在研究一個新的應用領域時，可以按照以下步驟識別目標，定義問題和使用資料抽象解決問題：