溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本文小編為大家詳細介紹“C#數據類型怎么實現背包、隊列和棧”，內容詳細，步驟清晰，細節處理妥當，希望這篇“C#數據類型怎么實現背包、隊列和棧”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學習新知識吧。
把描述和實現算法所用到的語言特性，軟件庫和操作系統特性總稱為基礎編程模型。
編寫遞歸代碼注意的點：
1. 遞歸總有一個最簡單的情況 —— 方法的第一條語句總是包含 return 的條件語句。
2. 遞歸調用總是嘗試解決一個規模更小的子問題，這樣遞歸才能收斂到最簡單的情況。
3. 遞歸調用的父問題和嘗試解決的子問題之間不應該有交集。
數據類型指的是一組值和一組對這些值的操作的集合。抽象數據類型（ADT） 是一種能夠對使用者隱藏數據表示的數據類型。用高級語言的類來實現抽象數據類型和用一組靜態方法實現一個函數庫并沒有什么不同。抽象數據類型的主要不同之處在于它將數據和函數的實現關聯，并將數據的表示方式隱藏起來。在使用抽象數據類型時，我們的注意力集中在API 描述的操作上而不會去關心數據的表示；在實現抽象數據類型時，我們的注意力集中在數據本身并將實現對該數據的各種操作。
抽象數據之所以重要是因為在程序設計上支持封裝。
我們研究同一問題的不同算法的主要原因在于他們的性能特點不同。抽象數據類型可以在不修改測試代碼的情況下用一種算法替換另一種算法。
數據抽象中的一個基礎概念：對象是能夠承載數據類型的值的實體。所有的對象都有三大特性：狀態，標識和行為。對象的狀態即數據類型中的值。對象的標識就是它在內存中的位置。對象的行為就是數據類型的操作。
許多基礎數據類型都和對象的集合有關。數據類型的值就是一組對象的集合，所有操作都是關于添加，刪除或是訪問集合中的對象。背包（Bag），隊列（Quene）和棧（Stack） 它們的不同之處在于刪除或者訪問對象的順序不同。
Stack 和 Quene 都含有一個能夠刪除集合中特定元素的方法。
實現上面API需要高級語言的特性：泛型，裝箱拆箱，可迭代（實現IEnumerable 接口）。
背包是一種不支持從中刪除元素的集合類型——它的目的就是幫助用例收集元素并迭代遍歷所有元素。用例也可以使用棧或者隊列，但使用 Bag 可以說明元素的處理順序不重要。
隊列是基于先進先出（FIFO）策略的集合類型。
下壓棧（簡稱棧）是一種基于后進先出（LIFO）策略的集合類型。
應用例子：計算輸入字符串 （1+（（2+3）*（4*5）））表達式的值。
使用雙棧解決：
1. 將操作數壓入操作數棧；
2. 將運算符壓入運算符棧；
3. 忽略做括號；
4. 在遇到右括號時，彈出一個運算符，彈出所需數量的操作數，并將運算符和操作數的運算結果壓入操作數棧。
實現下壓棧：
//想要數據類型可迭代，需要實現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();
}
}鏈表是在集合類的抽象數據類型實現中表示數據的另一種基礎數據結構。
定義：鏈表是一種遞歸的數據結構，它或者指向空，或者指向另一個節點的引用，該節點含有一個泛型元素和一個指向另一個鏈表的引用。
class Node<Item>
{
public Item item { get; set; }
public Node<Item> Next { get; set; }
}鏈表表示的是一列元素。
根據遞歸的定義，只需要一個 Node 類型的變量就能表示一條鏈表，只要保證它的 Next 值是 null 或指向另一個 Node 對象，該對象的 Next 指向另一條鏈表。
在鏈表列表中插入新節點的最簡單位置是開始。要在首結點為 first 的給定鏈表開頭插入字符串 not ，先將 first 保存在 oldfirst 中，然后將一個新結點賦予 first ，并將 first 的 item 設為 not, Next 設置為 oldfirst 。
在鏈表開頭插入一個結點所需的時間和鏈表長度無關。
只需將 first 指向 first.next 即可。first 原來指向的對象變成了一個孤兒，垃圾回收機制會將其回收。
同樣，該操作所需的時間和鏈表長度無關。
當鏈表不止有一個結點時，需要一個指向鏈表最后結點的鏈接 oldlast，創建新的結點，last 指向新的最后結點。然后 oldlast.next 指向 last。
當鏈表只有一個結點時，首結點又是尾結點。只需將 last 指向新的結點，然后 first.next 指向 last。
上述操作可以很容易的實現，但是下面的操作比較復雜：
1. 刪除指定的結點
2. 在指定結點前插入一個新結點
這些操作需要我們遍歷鏈表，它所需的時間和鏈表的長度成正比。想要實現任意插入和刪除結點需要使用雙向鏈表，其中每個結點都含有兩個鏈接，分別指向上一個和下一個結點。
簡單實現：
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);
}
}見上述代碼。
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. 操作所需的時間總是和集合的大小無關；
需要兩個實例變量，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();
}
}在結構化存儲數據集時，鏈表是數組的一種重要的替代方式。
數組和鏈表這兩種數據類型為研究算法和更高級的數據結構打下了基礎。
基礎數據結構：
| 數據結構 | 優點 | 缺點 |
| 數組 | 通過索引可以直接訪問任意元素 | 在初始化時就需要知道元素的數量 |
| 鏈表 | 使用的空間大小和元素數量成正比 | 需要通過引用訪問任意元素 |
在研究一個新的應用領域時，可以按照以下步驟識別目標，定義問題和使用數據抽象解決問題：
1. 定義 API
2. 根據特定的應用場景開發用例代碼
3. 描述一種數據結構（即一組值的表示），并在 API 的實現中根據它定義類的實例變量。
4. 描述算法，即實現 API，并根據它應用于用例
5. 分析算法的性能
讀到這里，這篇“C#數據類型怎么實現背包、隊列和棧”文章已經介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領會，如果想了解更多相關內容的文章，歡迎關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
