程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> .NET網頁編程 >> C# >> C#入門知識 >> C#數據構造之單鏈表(LinkList)實例詳解

C#數據構造之單鏈表(LinkList)實例詳解

編輯:C#入門知識

C#數據構造之單鏈表(LinkList)實例詳解。本站提示廣大學習愛好者:(C#數據構造之單鏈表(LinkList)實例詳解)文章只能為提供參考,不一定能成為您想要的結果。以下是C#數據構造之單鏈表(LinkList)實例詳解正文


本文實例講述了C#數據構造之單鏈表(LinkList)完成辦法。分享給年夜家供年夜家參考,詳細以下:

這裡我們來看下“單鏈表(LinkList)”。在上一篇《C#數據構造之次序表(SeqList)實例詳解》的最初,我們指出了:次序表請求開拓一組持續的內存空間,並且拔出/刪除元素時,為了包管元素的次序性,必需對前面的元素停止挪動。假如你的運用中須要頻仍對元素停止拔出/刪除,那末開支會很年夜。

而鏈表構造正好相反,先來看下構造:

每一個元素至多具有二個屬性:data和next。data用來寄存數據,而next用來指出它前面的元素是誰(有點“指針”的意思)。

鏈表中的元素,平日也稱為節點Node,上面是泛型版本的Node.cs

namespace 線性表
{
  public class Node<T>
  {
    private T data;
    private Node<T> next;
    public Node(T val, Node<T> p) 
    {
      data = val;
      next = p;
    }
    public Node(Node<T> p) 
    {
      next = p;
    }
    public Node(T val) 
    {
      data = val;
      next = null;
    }
    public Node() 
    {
      data = default(T);
      next = null;
    }
    public T Data 
    {
      get { return data; }
      set { data = value; }
    }
    public Node<T> Next 
    {
      get { return next; }
      set { next = value; }
    }
  }
}

鏈表在存儲上其實不請求一切元素按次序存儲,由於用節點的next就可以找到下一個節點,這好象一根“用珠子串成的鏈子”,要找到個中的某一顆珠子,只需從第一顆節點(平日稱為Head節點)開端,赓續依據next指向找到下一個,直到找到須要的節點為止。

鏈表中須要有一個Head節點做為開端,這跟次序表有所分歧,上面是單鏈表的完成:

using System;
using System.Text;
namespace 線性表
{
  public class LinkList<T> : IListDS<T>
  {
    private Node<T> head;
    public Node<T> Head
    {
      get { return head; }
      set { head = value; }
    }
    public LinkList()
    {
      head = null;
    }
    /// <summary>
    /// 類索引器
    /// </summary>
    /// <param name="index"></param>
    /// <returns></returns>
    public T this[int index] 
    {
      get
      {
        return this.GetItemAt(index);
      }
    }
    /// <summary>
    /// 前往單鏈表的長度
    /// </summary>
    /// <returns></returns>
    public int Count()
    {
      Node<T> p = head;
      int len = 0;
      while (p != null)
      {
        len++;
        p = p.Next;
      }
      return len;
    }
    /// <summary>
    /// 清空
    /// </summary>
    public void Clear()
    {
      head = null;
    }
    /// <summary>
    /// 能否為空
    /// </summary>
    /// <returns></returns>
    public bool IsEmpty()
    {
      return head == null;
    }
    /// <summary>
    /// 在最初附加元素
    /// </summary>
    /// <param name="item"></param>
    public void Append(T item)
    {
      Node<T> d = new Node<T>(item);
      Node<T> n = new Node<T>();
      if (head == null)
      {
        head = d;
        return;
      }
      n = head;
      while (n.Next != null)
      {
        n = n.Next;
      }
      n.Next = d;
    }
    //前插
    public void InsertBefore(T item, int i)
    {
      if (IsEmpty() || i < 0)
      {
        Console.WriteLine("List is empty or Position is error!");
        return;
      }
      //在最開首拔出
      if (i == 0)
      {
        Node<T> q = new Node<T>(item);
        q.Next = Head;//把"頭"改成第二個元素
        head = q;//把本身設置為"頭"
        return;
      }
      Node<T> n = head;
      Node<T> d = new Node<T>();
      int j = 0;
      //找到地位i的前一個元素d
      while (n.Next != null && j < i)
      {
        d = n;
        n = n.Next;
        j++;
      }
      if (n.Next == null) //解釋是在最初節點拔出(即追加)
      {
        Node<T> q = new Node<T>(item);
        n.Next = q;
        q.Next = null;
      }
      else
      {
        if (j == i)
        {
          Node<T> q = new Node<T>(item);
          d.Next = q;
          q.Next = n;
        }
      }
    }
    /// <summary>
    /// 在地位i後拔出元素item
    /// </summary>
    /// <param name="item"></param>
    /// <param name="i"></param>
    public void InsertAfter(T item, int i)
    {
      if (IsEmpty() || i < 0)
      {
        Console.WriteLine("List is empty or Position is error!");
        return;
      }
      if (i == 0)
      {
        Node<T> q = new Node<T>(item);
        q.Next = head.Next;
        head.Next = q;
        return;
      }
      Node<T> p = head;
      int j = 0;
      while (p != null && j < i)
      {
        p = p.Next;
        j++;
      }
      if (j == i)
      {
        Node<T> q = new Node<T>(item);
        q.Next = p.Next;
        p.Next = q;
      }
      else
      {
        Console.WriteLine("Position is error!");
      }
    }
    /// <summary>
    /// 刪除地位i的元素
    /// </summary>
    /// <param name="i"></param>
    /// <returns></returns>
    public T RemoveAt(int i)
    {
      if (IsEmpty() || i < 0)
      {
        Console.WriteLine("Link is empty or Position is error!");
        return default(T);
      }
      Node<T> q = new Node<T>();
      if (i == 0)
      {
        q = head;
        head = head.Next;
        return q.Data;
      }
      Node<T> p = head;
      int j = 0;
      while (p.Next != null && j < i)
      {
        j++;
        q = p;
        p = p.Next;
      }
      if (j == i)
      {
        q.Next = p.Next;
        return p.Data;
      }
      else
      {
        Console.WriteLine("The node is not exist!");
        return default(T);
      }
    }
    /// <summary>
    /// 獲得指定地位的元素
    /// </summary>
    /// <param name="i"></param>
    /// <returns></returns>
    public T GetItemAt(int i)
    {
      if (IsEmpty())
      {
        Console.WriteLine("List is empty!");
        return default(T);
      }
      Node<T> p = new Node<T>();
      p = head;
      if (i == 0) 
      { 
        return p.Data; 
      }
      int j = 0;
      while (p.Next != null && j < i)
      {
        j++;
        p = p.Next;
      }
      if (j == i)
      {
        return p.Data;
      }
      else
      {
        Console.WriteLine("The node is not exist!");
        return default(T);
      }
    }
    //按元素值查找索引
    public int IndexOf(T value)
    {
      if (IsEmpty())
      {
        Console.WriteLine("List is Empty!");
        return -1;
      }
      Node<T> p = new Node<T>();
      p = head;
      int i = 0;
      while (!p.Data.Equals(value) && p.Next != null)
      {
        p = p.Next;
        i++;
      }
      return i;
    }
    /// <summary>
    /// 元素反轉
    /// </summary>
    public void Reverse()
    {
      LinkList<T> result = new LinkList<T>();
      Node<T> t = this.head;
      result.Head = new Node<T>(t.Data);
      t = t.Next;
      //(把以後鏈接的元素從head開端遍歷,逐一拔出到另外一個空鏈表中,如許獲得的新鏈表正好元素次序跟原鏈表是相反的)
      while (t!=null)
      {        
        result.InsertBefore(t.Data, 0);
        t = t.Next;
      }
      this.head = result.head;//將原鏈表直接掛到"反轉後的鏈表"上
      result = null;//顯式清空原鏈表的援用,以便讓GC能直接收受接管
    }
    public override string ToString()
    {
      StringBuilder sb = new StringBuilder();
      Node<T> n = this.head;
      sb.Append(n.Data.ToString() + ",");
      while (n.Next != null)
      {
        sb.Append(n.Next.Data.ToString() + ",");
        n = n.Next;
      }
      return sb.ToString().TrimEnd(',');
    }
  }
}

上面是單鏈表拔出和刪除的算法圖解:

可以看到:鏈表在元素拔出/刪除時,無需對前面的元素停止挪動,只須要修正本身和相鄰節點的next指向便可,所以拔出/刪除元素的開支要比次序表小很多。然則也應當留意到,其它操作好比:查找元素,反轉顛倒鏈表等,有能夠須要遍歷全部鏈表中的一切元素。

測試代碼片段:

Console.WriteLine("-------------------------------------");
Console.WriteLine("單鏈表測試開端...");
LinkList<string> link = new LinkList<string>();
link.Head = new Node<string>("x");
link.InsertBefore("w", 0);
link.InsertBefore("v", 0);
link.Append("y");
link.InsertBefore("z", link.Count());
Console.WriteLine(link.Count());//5
Console.WriteLine(link.ToString());//v,w,x,y,z
Console.WriteLine(link[1]);//w
Console.WriteLine(link[0]);//v
Console.WriteLine(link[4]);//z
Console.WriteLine(link.IndexOf("z"));//4
Console.WriteLine(link.RemoveAt(2));//x
Console.WriteLine(link.ToString());//v,w,y,z
link.InsertBefore("x", 2);
Console.WriteLine(link.ToString());//v,w,x,y,z
Console.WriteLine(link.GetItemAt(2));//x
link.Reverse();
Console.WriteLine(link.ToString());//z,y,x,w,v
link.InsertAfter("1", 0);
link.InsertAfter("2", 1);
link.InsertAfter("6", 5);
link.InsertAfter("8", 7);
link.InsertAfter("A", 10);//Position is error!
Console.WriteLine(link.ToString()); //z,1,2,y,x,w,6,v,8

至於詳細在現實運用中應當選用次序表 or 鏈表,重要是看:關於元素拔出/刪除的頻仍水平和關於內存分派的刻薄水平。 假如不請求一開端就分派一組持續的內存區域,可以依據元素的增長而主動加年夜內存的應用量,或許拔出/刪除的次數許多,那末建議應用鏈表,反之用次序表。

最初指出:可以給節點再添加一個prev元素,用於指出前一個節點是誰,即同時有next和prev二個指向,這類改良後的鏈表稱為“雙向鏈表”,它有助於某些情形下削減遍歷輪回的次數,本文中的這類唯一一個next指向的鏈表,稱為“單鏈表”。

願望本文所述對年夜家C#法式設計有所贊助。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved