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

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

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

寫在前面

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

什么是鏈表結(jié)構(gòu)呢？

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

為什么要有鏈表結(jié)構(gòu)呢？

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

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

如何實現(xiàn)鏈表

首先我們需要聲明一種結(jié)構(gòu)

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

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

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

然后我們創(chuàng)建一個MyList先生，這位先生就使用Node去存放整形物品，而且使用了鏈表結(jié)構(gòu)哦！

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)點：可以存放任意多個元素！方便元素的插入和刪除。

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

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

namespace DounlyLinkedlist
{
  //定義雙向鏈表的結(jié)點
  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; 
    }

    //查找結(jié)點
    private Node Find(Object item)
    {
      Node Current = new Node();
      Current = Header;
      while (Current.Element != item)
      {
        Current = Current.FLink;
      }
      return Current;
    }

    //插入結(jié)點
    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;
      }
    }

    //刪除結(jié)點
    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;
      }
      
    }


    //查找雙向鏈表最后一個結(jié)點元素
    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;
      }
    }
  }
}

鏈表應(yīng)用場景

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

您可能感興趣的文章: