C#數(shù)據(jù)類型實現(xiàn)背包、隊列和棧
基礎(chǔ)編程模型和數(shù)據(jù)抽象
把描述和實現(xiàn)算法所用到的語言特性，軟件庫和操作系統(tǒng)特性總稱為基礎(chǔ)編程模型。
編寫遞歸代碼注意的點：
- 1. 遞歸總有一個最簡單的情況 —— 方法的第一條語句總是包含 return 的條件語句。
- 2. 遞歸調(diào)用總是嘗試解決一個規(guī)模更小的子問題，這樣遞歸才能收斂到最簡單的情況。
- 3. 遞歸調(diào)用的父問題和嘗試解決的子問題之間不應(yīng)該有交集。
數(shù)據(jù)類型指的是一組值和一組對這些值的操作的集合。抽象數(shù)據(jù)類型（ADT） 是一種能夠?qū)κ褂谜唠[藏數(shù)據(jù)表示的數(shù)據(jù)類型。用高級語言的類來實現(xiàn)抽象數(shù)據(jù)類型和用一組靜態(tài)方法實現(xiàn)一個函數(shù)庫并沒有什么不同。抽象數(shù)據(jù)類型的主要不同之處在于它將數(shù)據(jù)和函數(shù)的實現(xiàn)關(guān)聯(lián)，并將數(shù)據(jù)的表示方式隱藏起來。在使用抽象數(shù)據(jù)類型時，我們的注意力集中在API 描述的操作上而不會去關(guān)心數(shù)據(jù)的表示；在實現(xiàn)抽象數(shù)據(jù)類型時，我們的注意力集中在數(shù)據(jù)本身并將實現(xiàn)對該數(shù)據(jù)的各種操作。
抽象數(shù)據(jù)之所以重要是因為在程序設(shè)計上支持封裝。
我們研究同一問題的不同算法的主要原因在于他們的性能特點不同。抽象數(shù)據(jù)類型可以在不修改測試代碼的情況下用一種算法替換另一種算法。
數(shù)據(jù)抽象中的一個基礎(chǔ)概念：對象是能夠承載數(shù)據(jù)類型的值的實體。所有的對象都有三大特性：狀態(tài)，標識和行為。對象的狀態(tài)即數(shù)據(jù)類型中的值。對象的標識就是它在內(nèi)存中的位置。對象的行為就是數(shù)據(jù)類型的操作。
許多基礎(chǔ)數(shù)據(jù)類型都和對象的集合有關(guān)。數(shù)據(jù)類型的值就是一組對象的集合，所有操作都是關(guān)于添加，刪除或是訪問集合中的對象。背包（Bag），隊列（Quene）和棧（Stack） 它們的不同之處在于刪除或者訪問對象的順序不同。
1. API
Stack 和 Quene 都含有一個能夠刪除集合中特定元素的方法。
實現(xiàn)上面API需要高級語言的特性：泛型，裝箱拆箱，可迭代（實現(xiàn)IEnumerable 接口）。
1. 背包
背包是一種不支持從中刪除元素的集合類型——它的目的就是幫助用例收集元素并迭代遍歷所有元素。用例也可以使用?；蛘哧犃?，但使用 Bag 可以說明元素的處理順序不重要。
2.先進先出隊列
隊列是基于先進先出（FIFO）策略的集合類型。
3. 下壓棧
下壓棧（簡稱棧）是一種基于后進先出（LIFO）策略的集合類型。
應(yīng)用例子：計算輸入字符串 （1+（（2+3）*（4*5）））表達式的值。
使用雙棧解決：
- 1. 將操作數(shù)壓入操作數(shù)棧；
- 2. 將運算符壓入運算符棧；
- 3. 忽略做括號；
- 4. 在遇到右括號時，彈出一個運算符，彈出所需數(shù)量的操作數(shù)，并將運算符和操作數(shù)的運算結(jié)果壓入操作數(shù)棧。
2.用數(shù)組實現(xiàn)
實現(xiàn)下壓棧：
//想要數(shù)據(jù)類型可迭代，需要實現(xiàn)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>
/// 使數(shù)組處于半滿
/// </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.鏈表
鏈表是在集合類的抽象數(shù)據(jù)類型實現(xiàn)中表示數(shù)據(jù)的另一種基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)。
定義：鏈表是一種遞歸的數(shù)據(jù)結(jié)構(gòu)，它或者指向空，或者指向另一個節(jié)點的引用，該節(jié)點含有一個泛型元素和一個指向另一個鏈表的引用。
class Node<Item>
{
public Item item { get; set; }
public Node<Item> Next { get; set; }
}1.構(gòu)造鏈表
鏈表表示的是一列元素。
根據(jù)遞歸的定義，只需要一個 Node 類型的變量就能表示一條鏈表，只要保證它的 Next 值是 null 或指向另一個 Node 對象，該對象的 Next 指向另一條鏈表。
2.在表頭插入結(jié)點
在鏈表列表中插入新節(jié)點的最簡單位置是開始。要在首結(jié)點為 first 的給定鏈表開頭插入字符串 not ，先將 first 保存在 oldfirst 中，然后將一個新結(jié)點賦予 first ，并將 first 的 item 設(shè)為 not, Next 設(shè)置為 oldfirst 。
在鏈表開頭插入一個結(jié)點所需的時間和鏈表長度無關(guān)。
3.從表頭刪除結(jié)點
只需將 first 指向 first.next 即可。first 原來指向的對象變成了一個孤兒，垃圾回收機制會將其回收。
同樣，該操作所需的時間和鏈表長度無關(guān)。
4.在表尾插入結(jié)點
當鏈表不止有一個結(jié)點時，需要一個指向鏈表最后結(jié)點的鏈接 oldlast，創(chuàng)建新的結(jié)點，last 指向新的最后結(jié)點。然后 oldlast.next 指向 last。
當鏈表只有一個結(jié)點時，首結(jié)點又是尾結(jié)點。只需將 last 指向新的結(jié)點，然后 first.next 指向 last。
5.其他位置的插入和刪除操作
上述操作可以很容易的實現(xiàn)，但是下面的操作比較復(fù)雜：
- 1. 刪除指定的結(jié)點
- 2. 在指定結(jié)點前插入一個新結(jié)點
這些操作需要我們遍歷鏈表，它所需的時間和鏈表的長度成正比。想要實現(xiàn)任意插入和刪除結(jié)點需要使用雙向鏈表，其中每個結(jié)點都含有兩個鏈接，分別指向上一個和下一個結(jié)點。
6. 遍歷
簡單實現(xiàn)：
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);
}實現(xiàn) IEnumerable 接口 實現(xiàn)遍歷：
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. 用鏈表實現(xiàn)背包
見上述代碼。
5. 用鏈表實現(xiàn)棧
Stack API 中 Pop() 刪除一個元素，按照前面的從表頭刪除結(jié)點實現(xiàn)，Push() 添加一個元素，按照前面在表頭插入結(jié)點。
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();
}
}鏈表的使用達到了最優(yōu)設(shè)計目標：
- 1. 可以處理任意類型的數(shù)據(jù)；
- 2. 所需的空間總是和集合的大小成正比；
- 3. 操作所需的時間總是和集合的大小無關(guān)；
6. 用鏈表實現(xiàn)隊列
需要兩個實例變量，first 指向隊列的開頭，last 指向隊列的表尾。添加一個元素 Enquene() ，將結(jié)點添加到表尾（鏈表為空時，first 和 last 都指向新結(jié)點）。刪除一個元素 Dequene() ，刪除表頭的結(jié)點（刪除后，當隊列為空時，將 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. 總結(jié)
在結(jié)構(gòu)化存儲數(shù)據(jù)集時，鏈表是數(shù)組的一種重要的替代方式。
數(shù)組和鏈表這兩種數(shù)據(jù)類型為研究算法和更高級的數(shù)據(jù)結(jié)構(gòu)打下了基礎(chǔ)。
基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)：
| 數(shù)據(jù)結(jié)構(gòu) | 優(yōu)點 | 缺點 |
|---|---|---|
| 數(shù)組 | 通過索引可以直接訪問任意元素 | 在初始化時就需要知道元素的數(shù)量 |
| 鏈表 | 使用的空間大小和元素數(shù)量成正比 | 需要通過引用訪問任意元素 |
在研究一個新的應(yīng)用領(lǐng)域時，可以按照以下步驟識別目標，定義問題和使用數(shù)據(jù)抽象解決問題：
- 1. 定義 API
- 2. 根據(jù)特定的應(yīng)用場景開發(fā)用例代碼
- 3. 描述一種數(shù)據(jù)結(jié)構(gòu)（即一組值的表示），并在 API 的實現(xiàn)中根據(jù)它定義類的實例變量。
- 4. 描述算法，即實現(xiàn) API，并根據(jù)它應(yīng)用于用例
- 5. 分析算法的性能
到此這篇關(guān)于C#數(shù)據(jù)類型實現(xiàn)背包、隊列和棧的文章就介紹到這了。希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
最近由于興趣學(xué)習(xí)了下在C#上使用AForge錄制攝像頭視頻并壓縮編碼。總體上來說這個第三方.net視覺開發(fā)庫還是比較穩(wěn)定的2017-09-09
c# 如何實現(xiàn)獲取二維數(shù)組的列數(shù)
這篇文章主要介紹了c# 實現(xiàn)獲取二維數(shù)組的列數(shù)操作，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2021-04-04
C#使用Oracle.ManagedDataAccess.dll組件連接Oracle數(shù)據(jù)庫
這篇文章介紹了C#使用Oracle.ManagedDataAccess.dll組件連接Oracle數(shù)據(jù)庫的方法，文中通過示例代碼介紹的非常詳細。對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-05-05
本篇文章主要介紹了表達式樹 Expression Trees的基礎(chǔ)知識：Lambda 表達式創(chuàng)建表達式樹；API 創(chuàng)建表達式樹；編譯表達式樹；執(zhí)行表達式樹；修改表達式樹等等，具有一定的參考價值，下面跟著小編一起來看下吧2017-01-01
這篇文章主要介紹了c#唯一值渲染實例代碼，有需要的朋友可以參考一下2013-12-12
本文詳細講解了C#多線程中的手動線程通知，文中通過示例代碼介紹的非常詳細。對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-02-02
這篇文章主要介紹了C#中進程的掛起與恢復(fù)操作方法，非常不錯，具有參考借鑒價值,需要的朋友可以參考下2017-03-03
C# HttpClient上傳文件并附帶其它參數(shù)方式
這篇文章主要介紹了C# HttpClient上傳文件并附帶其它參數(shù)方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2023-11-11
這篇文章主要介紹了Winform里面的緩存使用，有需要的朋友可以參考一下2014-01-01
C#實現(xiàn)的文件操作封裝類完整實例【刪除,移動,復(fù)制,重命名】
這篇文章主要介紹了C#實現(xiàn)的文件操作封裝類,結(jié)合完整實例形式分析了C#封裝文件的刪除,移動,復(fù)制,重命名等操作相關(guān)實現(xiàn)技巧,需要的朋友可以參考下2017-03-03