欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C#數(shù)據(jù)類型實(shí)現(xiàn)背包、隊(duì)列和棧

 更新時(shí)間：2022年04月15日 11:06:09   作者：Ruby_Lu  
本文詳細(xì)講解了C#數(shù)據(jù)結(jié)構(gòu)類型，并實(shí)現(xiàn)背包、隊(duì)列和棧的方法，文中通過示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下

基礎(chǔ)編程模型和數(shù)據(jù)抽象

把描述和實(shí)現(xiàn)算法所用到的語言特性，軟件庫和操作系統(tǒng)特性總稱為基礎(chǔ)編程模型。

編寫遞歸代碼注意的點(diǎn)：

  • 1. 遞歸總有一個(gè)最簡(jiǎn)單的情況 —— 方法的第一條語句總是包含 return 的條件語句。
  • 2. 遞歸調(diào)用總是嘗試解決一個(gè)規(guī)模更小的子問題，這樣遞歸才能收斂到最簡(jiǎn)單的情況。
  • 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ù)類型可以在不修改測(cè)試代碼的情況下用一種算法替換另一種算法。

數(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. 下壓棧

下壓棧（簡(jiǎn)稱棧）是一種基于后進(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ǎ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í)間和鏈表長(zhǎng)度無關(guān)。

3.從表頭刪除結(jié)點(diǎn)

只需將 first 指向 first.next 即可。first 原來指向的對(duì)象變成了一個(gè)孤兒，垃圾回收機(jī)制會(huì)將其回收。

同樣，該操作所需的時(shí)間和鏈表長(zhǎng)度無關(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í)間和鏈表的長(zhǎng)度成正比。想要實(shí)現(xiàn)任意插入和刪除結(jié)點(diǎn)需要使用雙向鏈表，其中每個(gè)結(jié)點(diǎn)都含有兩個(gè)鏈接，分別指向上一個(gè)和下一個(gè)結(jié)點(diǎn)。

6. 遍歷

簡(jiǎn)單實(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)用場(chǎ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)文章

最新評(píng)論