C#模擬鏈表數(shù)據(jù)結構的實例解析

更新時間：2016年04月21日 15:03:19 作者：靈犀

這篇文章主要介紹了C#模擬鏈表數(shù)據(jù)結構的實例解析,包括隊雙向鏈表的模擬方法,例子中隊鏈表的操作也有很好的說明,需要的朋友可以參考下

寫在前面

模塊化編程是大多數(shù)初學者必經(jīng)之路，然后可能你走向了結構化編程，鏈表是一種典型結構模式，它的出現(xiàn)克服了數(shù)組必須預先知道大小的缺陷，聽不懂?你只需要記住，鏈表結構非常牛叉就可以了，學習這種結構對我們的邏輯思維有很大提升。

什么是鏈表結構呢？

鏈表是一種物理存儲單元上非連續(xù)、非順序的存儲結構。比如A->B->C，這種結構，我們可以理解為A連接著B，B連接C，像這種結構我們就叫做鏈表結構。對了，火車的車廂，其實就是鏈表的結構的最好說明

為什么要有鏈表結構呢？

學過計算機的都知道數(shù)組(Array),數(shù)組常用切好用，但也存在問題。首先，數(shù)組必須需要知道空間大?。╥nt[] age = new int[100], 必須聲明長度），其次，對于元素之間插入、刪除操作效率很低（如何在數(shù)組中間插入一個元素？）。

鏈表的出現(xiàn)，完美的解決了這些問題。

如何實現(xiàn)鏈表

首先我們需要聲明一種結構

//鏈表結構: 構造節(jié)點 - 連接節(jié)點
//Template
class Node
{
  public int num;
  //指向下一個元素
  public Node next;
}

//鏈表結構: 構造節(jié)點 - 連接節(jié)點
//Template
class Node
{
  public int num;
  //指向下一個元素
  public Node next;
}

我們可以把上面的這種結構看做是一個禮品盒,可以存放整形數(shù)值。

然后我們創(chuàng)建一個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了。它有兩個優(yōu)點：可以存放任意多個元素！方便元素的插入和刪除。

雙向鏈表的定義和簡單操作：

雙向鏈表其實是單鏈表的改進。當我們對單鏈表進行操作時，有時你要對某個結點的直接前驅(qū)進行操作時，又必須從表頭開始查找。這是由單鏈表結點的結構所限制的。因為單鏈表每個結點只有一個存儲直接后繼結點地址的鏈域，那么能不能定義一個既有存儲直接后繼結點地址的鏈域，又有存儲直接前驅(qū)結點地址的鏈域的這樣一個雙鏈域結點結構呢？這就是雙向鏈表。在雙向鏈表中，結點除含有數(shù)據(jù)域外，還有兩個鏈域，一個存儲直接后繼結點地址，一般稱之為右鏈域；一個存儲直接前驅(qū)結點地址，一般稱之為左鏈域。

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;
      }
    }
  }
}

鏈表應用場景

應用場景：集合（動態(tài)數(shù)組）、貪吃蛇、地圖的循環(huán)生成、老虎機效果等等,鏈表可以幫助我們完成很多事情。

您可能感興趣的文章: