C#數(shù)據(jù)類型實(shí)現(xiàn)背包、隊(duì)列和棧
基礎(chǔ)編程模型和數(shù)據(jù)抽象
把描述和實(shí)現(xiàn)算法所用到的語言特性，軟件庫和操作系統(tǒng)特性總稱為基礎(chǔ)編程模型。
編寫遞歸代碼注意的點(diǎn)：
- 1. 遞歸總有一個(gè)最簡單的情況 —— 方法的第一條語句總是包含 return 的條件語句。
- 2. 遞歸調(diào)用總是嘗試解決一個(gè)規(guī)模更小的子問題，這樣遞歸才能收斂到最簡單的情況。
- 3. 遞歸調(diào)用的父問題和嘗試解決的子問題之間不應(yīng)該有交集。
數(shù)據(jù)類型指的是一組值和一組對(duì)這些值的操作的集合。抽象數(shù)據(jù)類型（ADT） 是一種能夠?qū)κ褂谜唠[藏?cái)?shù)據(jù)表示的數(shù)據(jù)類型。用高級(jí)語言的類來實(shí)現(xiàn)抽象數(shù)據(jù)類型和用一組靜態(tài)方法實(shí)現(xiàn)一個(gè)函數(shù)庫并沒有什么不同。抽象數(shù)據(jù)類型的主要不同之處在于它將數(shù)據(jù)和函數(shù)的實(shí)現(xiàn)關(guān)聯(lián)，并將數(shù)據(jù)的表示方式隱藏起來。在使用抽象數(shù)據(jù)類型時(shí)，我們的注意力集中在API 描述的操作上而不會(huì)去關(guān)心數(shù)據(jù)的表示；在實(shí)現(xiàn)抽象數(shù)據(jù)類型時(shí)，我們的注意力集中在數(shù)據(jù)本身并將實(shí)現(xiàn)對(duì)該數(shù)據(jù)的各種操作。
抽象數(shù)據(jù)之所以重要是因?yàn)樵诔绦蛟O(shè)計(jì)上支持封裝。
我們研究同一問題的不同算法的主要原因在于他們的性能特點(diǎn)不同。抽象數(shù)據(jù)類型可以在不修改測試代碼的情況下用一種算法替換另一種算法。
數(shù)據(jù)抽象中的一個(gè)基礎(chǔ)概念：對(duì)象是能夠承載數(shù)據(jù)類型的值的實(shí)體。所有的對(duì)象都有三大特性：狀態(tài)，標(biāo)識(shí)和行為。對(duì)象的狀態(tài)即數(shù)據(jù)類型中的值。對(duì)象的標(biāo)識(shí)就是它在內(nèi)存中的位置。對(duì)象的行為就是數(shù)據(jù)類型的操作。
許多基礎(chǔ)數(shù)據(jù)類型都和對(duì)象的集合有關(guān)。數(shù)據(jù)類型的值就是一組對(duì)象的集合，所有操作都是關(guān)于添加，刪除或是訪問集合中的對(duì)象。背包（Bag），隊(duì)列（Quene）和棧（Stack） 它們的不同之處在于刪除或者訪問對(duì)象的順序不同。
1. API
Stack 和 Quene 都含有一個(gè)能夠刪除集合中特定元素的方法。
實(shí)現(xiàn)上面API需要高級(jí)語言的特性：泛型，裝箱拆箱，可迭代（實(shí)現(xiàn)IEnumerable 接口）。
1. 背包
背包是一種不支持從中刪除元素的集合類型——它的目的就是幫助用例收集元素并迭代遍歷所有元素。用例也可以使用?；蛘哧?duì)列，但使用 Bag 可以說明元素的處理順序不重要。
2.先進(jìn)先出隊(duì)列
隊(duì)列是基于先進(jìn)先出（FIFO）策略的集合類型。
3. 下壓棧
下壓棧（簡稱棧）是一種基于后進(jìn)先出（LIFO）策略的集合類型。
應(yīng)用例子：計(jì)算輸入字符串 （1+（（2+3）*（4*5）））表達(dá)式的值。
使用雙棧解決：
- 1. 將操作數(shù)壓入操作數(shù)棧；
- 2. 將運(yùn)算符壓入運(yùn)算符棧；
- 3. 忽略做括號(hào)；
- 4. 在遇到右括號(hào)時(shí)，彈出一個(gè)運(yùn)算符，彈出所需數(shù)量的操作數(shù)，并將運(yùn)算符和操作數(shù)的運(yùn)算結(jié)果壓入操作數(shù)棧。
2.用數(shù)組實(shí)現(xiàn)
實(shí)現(xiàn)下壓棧：
//想要數(shù)據(jù)類型可迭代，需要實(shí)現(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); //避免對(duì)象游離
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ù)類型實(shí)現(xiàn)中表示數(shù)據(jù)的另一種基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)。
定義：鏈表是一種遞歸的數(shù)據(jù)結(jié)構(gòu)，它或者指向空，或者指向另一個(gè)節(jié)點(diǎn)的引用，該節(jié)點(diǎn)含有一個(gè)泛型元素和一個(gè)指向另一個(gè)鏈表的引用。
class Node<Item>
{
public Item item { get; set; }
public Node<Item> Next { get; set; }
}1.構(gòu)造鏈表
鏈表表示的是一列元素。
根據(jù)遞歸的定義，只需要一個(gè) Node 類型的變量就能表示一條鏈表，只要保證它的 Next 值是 null 或指向另一個(gè) Node 對(duì)象，該對(duì)象的 Next 指向另一條鏈表。
2.在表頭插入結(jié)點(diǎn)
在鏈表列表中插入新節(jié)點(diǎn)的最簡單位置是開始。要在首結(jié)點(diǎn)為 first 的給定鏈表開頭插入字符串 not ，先將 first 保存在 oldfirst 中，然后將一個(gè)新結(jié)點(diǎn)賦予 first ，并將 first 的 item 設(shè)為 not, Next 設(shè)置為 oldfirst 。
在鏈表開頭插入一個(gè)結(jié)點(diǎn)所需的時(shí)間和鏈表長度無關(guān)。
3.從表頭刪除結(jié)點(diǎn)
只需將 first 指向 first.next 即可。first 原來指向的對(duì)象變成了一個(gè)孤兒，垃圾回收機(jī)制會(huì)將其回收。
同樣，該操作所需的時(shí)間和鏈表長度無關(guān)。
4.在表尾插入結(jié)點(diǎn)
當(dāng)鏈表不止有一個(gè)結(jié)點(diǎn)時(shí)，需要一個(gè)指向鏈表最后結(jié)點(diǎn)的鏈接 oldlast，創(chuàng)建新的結(jié)點(diǎn)，last 指向新的最后結(jié)點(diǎn)。然后 oldlast.next 指向 last。
當(dāng)鏈表只有一個(gè)結(jié)點(diǎn)時(shí)，首結(jié)點(diǎn)又是尾結(jié)點(diǎn)。只需將 last 指向新的結(jié)點(diǎn)，然后 first.next 指向 last。
5.其他位置的插入和刪除操作
上述操作可以很容易的實(shí)現(xiàn)，但是下面的操作比較復(fù)雜：
- 1. 刪除指定的結(jié)點(diǎn)
- 2. 在指定結(jié)點(diǎn)前插入一個(gè)新結(jié)點(diǎn)
這些操作需要我們遍歷鏈表，它所需的時(shí)間和鏈表的長度成正比。想要實(shí)現(xiàn)任意插入和刪除結(jié)點(diǎn)需要使用雙向鏈表，其中每個(gè)結(jié)點(diǎn)都含有兩個(gè)鏈接，分別指向上一個(gè)和下一個(gè)結(jié)點(diǎn)。
6. 遍歷
簡單實(shí)現(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);
}實(shí)現(xiàn) IEnumerable 接口 實(shí)現(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. 用鏈表實(shí)現(xiàn)背包
見上述代碼。
5. 用鏈表實(shí)現(xiàn)棧
Stack API 中 Pop() 刪除一個(gè)元素，按照前面的從表頭刪除結(jié)點(diǎn)實(shí)現(xiàn)，Push() 添加一個(gè)元素，按照前面在表頭插入結(jié)點(diǎn)。
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();
}
}鏈表的使用達(dá)到了最優(yōu)設(shè)計(jì)目標(biāo)：
- 1. 可以處理任意類型的數(shù)據(jù)；
- 2. 所需的空間總是和集合的大小成正比；
- 3. 操作所需的時(shí)間總是和集合的大小無關(guān)；
6. 用鏈表實(shí)現(xiàn)隊(duì)列
需要兩個(gè)實(shí)例變量，first 指向隊(duì)列的開頭，last 指向隊(duì)列的表尾。添加一個(gè)元素 Enquene() ，將結(jié)點(diǎn)添加到表尾（鏈表為空時(shí)，first 和 last 都指向新結(jié)點(diǎn)）。刪除一個(gè)元素 Dequene() ，刪除表頭的結(jié)點(diǎn)（刪除后，當(dāng)隊(duì)列為空時(shí)，將 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)化存儲(chǔ)數(shù)據(jù)集時(shí)，鏈表是數(shù)組的一種重要的替代方式。
數(shù)組和鏈表這兩種數(shù)據(jù)類型為研究算法和更高級(jí)的數(shù)據(jù)結(jié)構(gòu)打下了基礎(chǔ)。
基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)：
| 數(shù)據(jù)結(jié)構(gòu) | 優(yōu)點(diǎn) | 缺點(diǎn) |
|---|---|---|
| 數(shù)組 | 通過索引可以直接訪問任意元素 | 在初始化時(shí)就需要知道元素的數(shù)量 |
| 鏈表 | 使用的空間大小和元素?cái)?shù)量成正比 | 需要通過引用訪問任意元素 |
在研究一個(gè)新的應(yīng)用領(lǐng)域時(shí)，可以按照以下步驟識(shí)別目標(biāo)，定義問題和使用數(shù)據(jù)抽象解決問題：
- 1. 定義 API
- 2. 根據(jù)特定的應(yīng)用場景開發(fā)用例代碼
- 3. 描述一種數(shù)據(jù)結(jié)構(gòu)（即一組值的表示），并在 API 的實(shí)現(xiàn)中根據(jù)它定義類的實(shí)例變量。
- 4. 描述算法，即實(shí)現(xiàn) API，并根據(jù)它應(yīng)用于用例
- 5. 分析算法的性能
到此這篇關(guān)于C#數(shù)據(jù)類型實(shí)現(xiàn)背包、隊(duì)列和棧的文章就介紹到這了。希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
Unity3D使用陀螺儀控制節(jié)點(diǎn)旋轉(zhuǎn)
這篇文章主要為大家詳細(xì)介紹了Unity3D使用陀螺儀控制節(jié)點(diǎn)旋轉(zhuǎn)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-11-11
輕松學(xué)習(xí)C#的屬性，對(duì)C#的屬性感興趣的朋友可以參考本篇文章，幫助大家更靈活的運(yùn)用C#的屬性2015-11-11
C#自定義序列化ISerializable的實(shí)現(xiàn)方法
這篇文章主要介紹了C#自定義序列化ISerializable的實(shí)現(xiàn)方法,涉及C#序列化的操作技巧,非常具有實(shí)用價(jià)值,需要的朋友可以參考下2015-04-04
C#幾種截取字符串的方法小結(jié)，需要的朋友可以參考一下2013-04-04
C#使用ADO.Net部件來訪問Access數(shù)據(jù)庫的方法
數(shù)據(jù)庫的訪問是所有編程語言中最重要的部分，C#提供了ADO.Net部件用于對(duì)數(shù)據(jù)庫進(jìn)行訪問。本文從最簡單易用的微軟Access數(shù)據(jù)庫入手討論在C#中對(duì)數(shù)據(jù)庫的訪問。2015-09-09
使用C#如何創(chuàng)建人名或其他物體隨機(jī)分組
文章描述了一個(gè)隨機(jī)分配人員到多個(gè)團(tuán)隊(duì)的代碼示例,包括將人員列表隨機(jī)化并根據(jù)組數(shù)分配到不同組,最后按組號(hào)排序顯示結(jié)果2025-01-01
Unity3D UGUI實(shí)現(xiàn)縮放循環(huán)拖動(dòng)卡牌展示效果
這篇文章主要為大家詳細(xì)介紹了Unity3D UGUI實(shí)現(xiàn)縮放循環(huán)拖動(dòng)展示卡牌效果，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-02-02
C#實(shí)現(xiàn)跨進(jìn)程條件變量的示例代碼
C#提供的多進(jìn)程同步對(duì)象有互斥鎖和信號(hào)量,但是并沒有條件變量,雖然信號(hào)量條件變量一定程度可以等效,但是具體的使用還是會(huì)有區(qū)別,本文提供了一種條件變量的實(shí)現(xiàn)方法,可以用于進(jìn)程間的同步控制,需要的朋友可以參考下2024-07-07
C#使用Lazy實(shí)現(xiàn)延遲加載的方法示例
在C#中,Lazy< T> 類是一個(gè)非常有用的工具,它可以用于延遲加載值,在本文中,我們將詳細(xì)介紹 Lazy< T> 的實(shí)現(xiàn)機(jī)制和用法,并提供一些示例來展示它的優(yōu)勢,文中通過代碼示例講解的非常詳細(xì),需要的朋友可以參考下2024-06-06
C#實(shí)現(xiàn)讀取二維數(shù)組集合并輸出到Word預(yù)設(shè)表格
這篇文章主要為大家詳細(xì)介紹了如何使用C#實(shí)現(xiàn)讀取二維數(shù)組集合并輸出到Word預(yù)設(shè)表格,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2024-03-03