欧博app:2. 背包,行列和栈

admin/2020-06-24/ 分类:科技/阅读:

  许多基础数据类型都和工具的聚集有关。数据类型的值就是一组工具的聚集,所有操作都是关于添加,删除或是接见聚集中的工具。背包(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. 剖析算法的性能

 

,

欧博allbet客户端

欢迎进入欧博allbet客户端(Allbet Game):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。

TAG:
阅读:
广告 330*360
广告 330*360
Sunbet_进入申博sunbet官网
微信二维码扫一扫
关注微信公众号
新闻自媒体 Copyright © 2002-2019 Sunbet 版权所有
二维码
意见反馈 二维码