c#数据类型怎么实现背包、队列和栈-mile米乐体育

3.链表

链表是在集合类的抽象数据类型实现中表示数据的另一种基础数据结构。

定义：链表是一种递归的数据结构，它或者指向空，或者指向另一个节点的引用，该节点含有一个泛型元素和一个指向另一个链表的引用。

classnode{publicitemitem{get;set;}publicnodenext{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. 遍历

简单实现：

publicclassbag{privatenodefirst;publicvoidadd(itemitem){nodeoldfirst=first;first=newnode(){item=item,next=oldfirst};}}

bagbags=newbag();for(vari=0;i<10;i ){bags.add(i);}for(varx=bags.first;x!=null;x=x.next){console.writeline(x.item);}

实现 ienumerable 接口 实现遍历：

publicclassbag:ienumerable{publicnodefirst;publicvoidadd(itemitem){nodeoldfirst=first;first=newnode(){item=item,next=oldfirst};}publicienumeratorgetenumerator(){returnnewlineenumerator(first);}ienumeratorienumerable.getenumerator(){returnnewlineenumerator(first);}}publicclasslineenumerator:ienumerator{publicnodefirst;publiclineenumerator(node_first){first=_first;}publicitemcurrent{get{varoldfirst=first;first=first.next;returnoldfirst.item;}}objectienumerator.current=>first;publicvoiddispose(){return;}publicboolmovenext(){if(first!=null)returntrue;returnfalse;}publicvoidreset(){thrownewnotimplementedexception();}}

publicstaticvoidlinetest(){bagbags=newbag();for(vari=0;i<10;i ){bags.add(i);}foreach(varbaginbags){console.writeline(bag);}}

4. 用链表实现背包

见上述代码。

5. 用链表实现栈

stack api 中 pop() 删除一个元素，按照前面的从表头删除结点实现，push() 添加一个元素，按照前面在表头插入结点。

publicclassstack:ienumerable{publicnodefirst;privateintn;publicboolisempty(){returnfirst==null;//或n==0}publicintsize(){returnn;}publicvoidpush(itemitem){nodeoldfirst=first;first=newnode(){item=item,next=oldfirst};n ;}publicitempop(){itemitem=first.item;first=first.next;n--;returnitem;}publicienumeratorgetenumerator(){returnnewstacklineienumerator(first);}ienumeratorienumerable.getenumerator(){returnnewstacklineienumerator(first);}}publicclassstacklineienumerator:ienumerator{privatenodefirst;publicstacklineienumerator(node_first){first=_first;}publicitemcurrent{get{varoldfirst=first;first=first.next;returnoldfirst.item;}}objectienumerator.current=>thrownewnotimplementedexception();publicvoiddispose(){return;}publicboolmovenext(){returnfirst!=null;}publicvoidreset(){thrownewnotimplementedexception();}}

链表的使用达到了最优设计目标：

• 1. 可以处理任意类型的数据；

• 2. 所需的空间总是和集合的大小成正比；

• 3. 操作所需的时间总是和集合的大小无关；

6. 用链表实现队列

需要两个实例变量，first 指向队列的开头，last 指向队列的表尾。添加一个元素 enquene() ，将结点添加到表尾（链表为空时，first 和 last 都指向新结点）。删除一个元素 dequene() ，删除表头的结点（删除后，当队列为空时，将 last 更新为 null）。

publicclassquene:ienumerable{publicnodefirst;publicnodelast;privateintn;publicboolisempty(){returnfirst==null;}publicintsize(){returnn;}publicvoidenquene(itemitem){varoldlast=last;last=newnode(){item=item,next=null};if(isempty())first=last;elseoldlast.next=last;n ;}publicitemdequene(){if(isempty())thrownewexception();itemitem=first.item;first=first.next;if(isempty())last=null;n--;returnitem;}publicienumeratorgetenumerator(){returnnewquenelineenumerator(first);}ienumeratorienumerable.getenumerator(){returnnewquenelineenumerator(first);}}publicclassquenelineenumerator:ienumerator{privatenodefirst;publicquenelineenumerator(node_first){first=_first;}publicitemcurrent{get{varoldfirst=first;first=first.next;returnoldfirst.item;}}objectienumerator.current=>thrownewnotimplementedexception();publicvoiddispose(){return;}publicboolmovenext(){returnfirst!=null;}publicvoidreset(){thrownewnotimplementedexception();}}

7. 总结

在结构化存储数据集时，链表是数组的一种重要的替代方式。

数组和链表这两种数据类型为研究算法和更高级的数据结构打下了基础。

基础数据结构：

在研究一个新的应用领域时，可以按照以下步骤识别目标，定义问题和使用数据抽象解决问题：

• 1. 定义 api

• 2. 根据特定的应用场景开发用例代码

• 3. 描述一种数据结构（即一组值的表示），并在 api 的实现中根据它定义类的实例变量。

• 4. 描述算法，即实现 api，并根据它应用于用例

• 5. 分析算法的性能

读到这里，这篇“c#数据类型怎么实现背包、队列和栈”文章已经介绍完毕，想要掌握这篇文章的知识点还需要大家自己动手实践使用过才能领会，如果想了解更多相关内容的文章，欢迎关注恰卡编程网行业资讯频道。