C#模拟链表数据结构的实例解析
写在前面
模块化编程是大多数初学者必经之路,然后可能你走向了结构化编程,链表是一种典型结构模式,它的出现克服了数组必须预先知道大小的缺陷,听不懂?你只需要记住,链表结构非常牛叉就可以了,学习这种结构对我们的逻辑思维有很大提升。
什么是链表结构呢?
链表是一种物理存储单元上非连续、非顺序的存储结构。比如a->b->c,这种结构,我们可以理解为a连接着b,b连接c,像这种结构我们就叫做链表结构。对了,火车的车厢,其实就是链表的结构的最好说明
为什么要有链表结构呢?
学过计算机的都知道数组(array),数组常用切好用,但也存在问题。首先,数组必须需要知道空间大小(int[] age = new int[100], 必须声明长度),其次,对于元素之间插入、删除操作效率很低(如何在数组中间插入一个元素?)。
链表的出现,完美的解决了这些问题。
如何实现链表
首先我们需要声明一种结构
//链表结构: 构造节点 - 连接节点 //template class node { public int num; //指向下一个元素 public node next; } //链表结构: 构造节点 - 连接节点 //template class node { public int num; //指向下一个元素 public node next; }
我们可以把上面的这种结构看做是一个礼品盒,可以存放整形数值。
然后我们创建一个mylist先生,这位先生就使用node去存放整形物品,而且使用了链表结构哦!
class mylist { public node currentnode; public node point; public mylist() { currentnode = new node(); } //存放物品 public void add(int value) { //第一次 if(point == null) { currentnode.num = value; point = currentnode; } else //2 3 4..... 次 { node temp = new node(); temp.num = value; point.next = temp; //更新指针 point = temp; } } } class mylist { public node currentnode; public node point; public mylist() { currentnode = new node(); } //存放物品 public void add(int value) { //第一次 if(point == null) { currentnode.num = value; point = currentnode; } else //2 3 4..... 次 { node temp = new node(); temp.num = value; point.next = temp; //更新指针 point = temp; } } }
然后,我们可以在客户端测试一下:
public static void main (string[] args) { mylist<int> mlist = new mylist<int>(); //添加元素 mlist.add(1); mlist.add(11); mlist.add(111); mlist.add(1111); while(mlist.currentnode != null) { console.writeline (mlist.currentnode.num); mlist.currentnode = mlist.currentnode.next; } } public static void main (string[] args) { mylist<int> mlist = new mylist<int>(); //添加元素 mlist.add(1); mlist.add(11); mlist.add(111); mlist.add(1111); while(mlist.currentnode != null) { console.writeline (mlist.currentnode.num); mlist.currentnode = mlist.currentnode.next; } }
我们自己定义的一个整形集合就这样ok了。它有两个优点:可以存放任意多个元素!方便元素的插入和删除。
双向链表的定义和简单操作:
双向链表其实是单链表的改进。当我们对单链表进行操作时,有时你要对某个结点的直接前驱进行操作时,又必须从表头开始查找。这是由单链表结点的结构所限制的。因为单链表每个结点只有一个存储直接后继结点地址的链域,那么能不能定义一个既有存储直接后继结点地址的链域,又有存储直接前驱结点地址的链域的这样一个双链域结点结构呢?这就是双向链表。在双向链表中,结点除含有数据域外,还有两个链域,一个存储直接后继结点地址,一般称之为右链域;一个存储直接前驱结点地址,一般称之为左链域。
namespace dounlylinkedlist { //定义双向链表的结点 public class node { public object element; public node flink; public node blink; public node() { element = null; flink = null; blink = null; } public node(object element) { element = element; flink = null; blink = null; } } //链表操作的类 public class linkedlist { public node header; public linkedlist() { header = new node("header"); header.flink = null; header.blink = null; } //查找结点 private node find(object item) { node current = new node(); current = header; while (current.element != item) { current = current.flink; } return current; } //插入结点 public void insertnode(object item,object postionitem) { node current = new node(); node newitem = new node(item); current = find(postionitem); if (current != null) { newitem.flink = current.flink; newitem.blink = current; current.flink = newitem; } } //删除结点 public void remove(object item) { node p = find(item); if (p.flink != null) { p.blink.flink = p.flink; p.flink.blink = p.blink; p.blink = null; p.flink = null; } } //查找双向链表最后一个结点元素 private node findlast() { node current = new node(); current = header; while (!(current.flink == null)) { current = current.flink; } return current; } //逆向打印双向链表 public void printreverse() { node current = new node(); current = findlast(); while (!(current.blink == null)) { console.writeline(current.element); current = current.blink; } } //打印双向链表 public void print() { node current = new node(); current = header; while (!(current.flink == null)) { console.writeline(current.flink.element); current = current.flink; } } } }
链表应用场景
应用场景:集合(动态数组)、贪吃蛇、地图的循环生成、*效果等等,链表可以帮助我们完成很多事情。
上一篇: python 读文件数据并画图
下一篇: 宝宝防暑降温八妙招 温水洗澡小毛巾垫背