欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C#模拟链表数据结构的实例解析

程序员文章站 2022-06-11 14:37:52
写在前面 模块化编程是大多数初学者必经之路,然后可能你走向了结构化编程,链表是一种典型结构模式,它的出现克服了数组必须预先知道大小的缺陷,听不懂?你只需要记住,链...

写在前面

模块化编程是大多数初学者必经之路,然后可能你走向了结构化编程,链表是一种典型结构模式,它的出现克服了数组必须预先知道大小的缺陷,听不懂?你只需要记住,链表结构非常牛叉就可以了,学习这种结构对我们的逻辑思维有很大提升。

什么是链表结构呢?

链表是一种物理存储单元上非连续、非顺序的存储结构。比如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;
      }
    }
  }
}

链表应用场景

应用场景:集合(动态数组)、贪吃蛇、地图的循环生成、*效果等等,链表可以帮助我们完成很多事情。