許多基礎數據類型都和對象的集合有關。數據類型的值就是一組對象的集合，所有操作都是關於添加，刪除或是訪問集合中的對象。背包（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. 總結
在結構化存儲數據集時，鏈表是數組的一種重要的替代方式。
數組和鏈表這兩種數據類型為研究算法和更高級的數據結構打下了基礎。
基礎數據結構：
| 數據結構 | 優點 | 缺點 |
| 數組 | 通過索引可以直接訪問任意元素 | 在初始化時就需要知道元素的數量 |
| 鏈表 | 使用的空間大小和元素數量成正比 | 需要同引用訪問任意元素 |
在研究一個新的應用領域時，可以按照以下步驟識別目標，定義問題和使用數據抽象解決問題：
1. 定義 API
2. 根據特定的應用場景開發用例代碼
3. 描述一種數據結構（即一組值的表示），並在 API 的實現中根據它定義類的實例變量。
4. 描述算法，即實現 API，並根據它應用於用例
5. 分析算法的性能
本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】
※廣告預算用在刀口上，台北網頁設計公司幫您達到更多曝光效益
※新北清潔公司,居家、辦公、裝潢細清專業服務
※別再煩惱如何寫文案,掌握八大原則!
※教你寫出一流的銷售文案?
※超省錢租車方案
