欧美大屁股bbbbxxxx,狼人大香伊蕉国产www亚洲,男ji大巴进入女人的视频小说,男人把ji大巴放进女人免费视频,免费情侣作爱视频

歡迎來到入門教程網(wǎng)！

C#教程

當前位置：主頁 > 軟件編程 > C#教程 >

C#數(shù)據(jù)結(jié)構(gòu)之雙向鏈表(DbLinkList)實例詳解

來源：本站原創(chuàng)|時間：2020-01-10|欄目：C#教程|點擊： 次

本文實例講述了C#數(shù)據(jù)結(jié)構(gòu)之雙向鏈表(DbLinkList)。分享給大家供大家參考，具體如下：

這是繼上一篇《C#數(shù)據(jù)結(jié)構(gòu)之單鏈表(LinkList)實例詳解》的繼續(xù)，對于雙向鏈接，節(jié)點上除了Next屬性外，還要有Prev屬性用來指向前一個節(jié)點，DbNode定義如下：

namespace 線性表
{
  public class DbNode<T>
  {
    private T data;
    private DbNode<T> prev;
    private DbNode<T> next;
    public DbNode(T data, DbNode<T> next,DbNode<T> prev)
    {
      this.data = data;
      this.next = next;
      this.prev = prev;
    }
    public DbNode(T data, DbNode<T> next) 
    {
      this.data = data;
      this.next = next;
      this.prev = null;
    }
    public DbNode(DbNode<T> next) 
    {
      this.data = default(T);
      this.next = next;
      this.prev = null;
    }
    public DbNode(T data) 
    {
      this.data = data;
      this.next = null;
      this.prev = null;
    }
    public DbNode() 
    {
      data = default(T);
      next = null;
      prev = null;
    }
    public T Data 
    {
      set { this.data = value; }
      get { return this.data; }
    }
    public DbNode<T> Prev 
    {
      get { return prev; }
      set { prev = value; }
    }
    public DbNode<T> Next 
    {
      get { return next; }
      set { next = value; }
    }
  }
}

雙鏈表的插入操作要稍微復(fù)雜一點，示意圖如下：

同樣對于刪除操作，也要額外處理prev指向

完整實現(xiàn)DbLinkList<T>：

using System;
using System.Text;
namespace 線性表
{
  public class DbLinkList<T> : IListDS<T>
  {
    private DbNode<T> head;
    public DbNode<T> Head
    {
      get { return head; }
      set { head = value; }
    }
    public DbLinkList()
    {
      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()
    {
      DbNode<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)
    {
      DbNode<T> d = new DbNode<T>(item);
      DbNode<T> n = new DbNode<T>();
      if (head == null)
      {
        head = d;
        return;
      }
      n = head;
      while (n.Next != null)
      {
        n = n.Next;
      }
      n.Next = d;
      d.Prev = n;
    }
    //前插
    public void InsertBefore(T item, int i)
    {
      if (IsEmpty() || i < 0)
      {
        Console.WriteLine("List is empty or Position is error!");
        return;
      }
      //在最開頭插入
      if (i == 0)
      {
        DbNode<T> q = new DbNode<T>(item);
        q.Next = head;//把"頭"改成第二個元素
        head.Prev = q;
        head = q;//把自己設(shè)置為"頭"
        return;
      }
      DbNode<T> n = head;
      DbNode<T> d = new DbNode<T>();
      int j = 0;
      //找到位置i的前一個元素d
      while (n.Next != null && j < i)
      {
        d = n;
        n = n.Next;
        j++;
      }
      if (n.Next == null) //說明是在最后節(jié)點插入(即追加)
      {
        DbNode<T> q = new DbNode<T>(item);
        n.Next = q;
        q.Prev = n;
        q.Next = null;
      }
      else
      {
        if (j == i)
        {
          DbNode<T> q = new DbNode<T>(item);
          d.Next = q;
          q.Prev = d;
          q.Next = n;
          n.Prev = q;
        }
      }
    }
    /// <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)
      {
        DbNode<T> q = new DbNode<T>(item);
        q.Next = head.Next;
        head.Next.Prev = q;
        head.Next = q;
        q.Prev = head;
        return;
      }
      DbNode<T> p = head;
      int j = 0;
      while (p != null && j < i)
      {
        p = p.Next;
        j++;
      }
      if (j == i)
      {
        DbNode<T> q = new DbNode<T>(item);
        q.Next = p.Next;
        if (p.Next != null)
        {
          p.Next.Prev = q;
        }
        p.Next = q;
        q.Prev = p;
      }
      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);
      }
      DbNode<T> q = new DbNode<T>();
      if (i == 0)
      {
        q = head;
        head = head.Next;
        head.Prev = null;
        return q.Data;
      }
      DbNode<T> p = head;
      int j = 0;
      while (p.Next != null && j < i)
      {
        j++;
        q = p;
        p = p.Next;
      }
      if (j == i)
      {
        p.Next.Prev = q;
        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);
      }
      DbNode<T> p = new DbNode<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;
      }
      DbNode<T> p = new DbNode<T>();
      p = head;
      int i = 0;
      while (!p.Data.Equals(value) && p.Next != null)
      {
        p = p.Next;
        i++;
      }
      return i;
    }
    /// <summary>
    /// 元素反轉(zhuǎn)
    /// </summary>
    public void Reverse()
    {
      DbLinkList<T> result = new DbLinkList<T>();
      DbNode<T> t = this.head;
      result.Head = new DbNode<T>(t.Data);
      t = t.Next;
      //(把當前鏈接的元素從head開始遍歷，逐個插入到另一個空鏈表中，這樣得到的新鏈表正好元素順序跟原鏈表是相反的)
      while (t!=null)
      {        
        result.InsertBefore(t.Data, 0);
        t = t.Next;
      }
      this.head = result.head;//將原鏈表直接掛到"反轉(zhuǎn)后的鏈表"上
      result = null;//顯式清空原鏈表的引用，以便讓GC能直接回收
    }
    //得到某個指定的節(jié)點(為了下面測試從后向前遍歷)
    private DbNode<T> GetNodeAt(int i){
      if (IsEmpty())
      {
        Console.WriteLine("List is empty!");
        return null;
      }
      DbNode<T> p = new DbNode<T>();
      p = head;
      if (i == 0)
      {
        return p;
      }
      int j = 0;
      while (p.Next != null && j < i)
      {
        j++;
        p = p.Next;
      }
      if (j == i)
      {
        return p;
      }
      else
      {
        Console.WriteLine("The node is not exist!");
        return null;
      }
    }
    /// <summary>
    /// 測試用prev屬性從后面開始遍歷
    /// </summary>
    /// <returns></returns>
    public string TestPrevErgodic() 
    {
      DbNode<T> tail = GetNodeAt(Count() - 1);
      StringBuilder sb = new StringBuilder();
      sb.Append(tail.Data.ToString() + ",");
      while (tail.Prev != null)
      {
        sb.Append(tail.Prev.Data.ToString() + ",");
        tail = tail.Prev;
      }
      return sb.ToString().TrimEnd(',');      
    }
    public override string ToString()
    {
      StringBuilder sb = new StringBuilder();
      DbNode<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(',');
    }
  }
}

測試代碼片段：

Console.WriteLine("-------------------------------------");
Console.WriteLine("雙鏈表測試開始...");
DbLinkList<string> dblink = new DbLinkList<string>();
dblink.Head = new DbNode<string>("x");
dblink.InsertBefore("w", 0);
dblink.InsertBefore("v", 0);
dblink.Append("y");
dblink.InsertBefore("z", dblink.Count());
Console.WriteLine(dblink.Count());//5
Console.WriteLine(dblink.ToString());//v,w,x,y,z
Console.WriteLine(dblink[1]);//w
Console.WriteLine(dblink[0]);//v
Console.WriteLine(dblink[4]);//z
Console.WriteLine(dblink.IndexOf("z"));//4
Console.WriteLine(dblink.RemoveAt(2));//x
Console.WriteLine(dblink.ToString());//v,w,y,z
dblink.InsertBefore("x", 2);
Console.WriteLine(dblink.ToString());//v,w,x,y,z
Console.WriteLine(dblink.GetItemAt(2));//x
dblink.Reverse();
Console.WriteLine(dblink.ToString());//z,y,x,w,v
dblink.InsertAfter("1", 0);
dblink.InsertAfter("2", 1);
dblink.InsertAfter("6", 5);
dblink.InsertAfter("8", 7);
dblink.InsertAfter("A", 10);//Position is error!
Console.WriteLine(dblink.ToString()); //z,1,2,y,x,w,6,v,8 
string _tail = dblink.GetItemAt(dblink.Count()-1);
Console.WriteLine(_tail);
Console.WriteLine(dblink.TestPrevErgodic());//8
Console.ReadKey(); //8,v,6,w,x,y,2,1,z

當然從上面的測試代碼中，似乎并不能看出雙鏈表的優(yōu)點，雙鏈表的好處在于，如果需要在鏈表中，需要通過某個節(jié)點得到它的前驅(qū)節(jié)點時，雙鏈表直接用prev屬性就能找到；而單鏈表要做到這一點，必須再次從Head節(jié)點開始一個一個用Next向下找，這樣時間復(fù)雜度從O(n)降到O(1)，顯然更有效率。

注：如果把雙鏈表再做一下改造，讓頭尾接起來，即Head的Prev屬性指向最后一個節(jié)點(就叫做Tail吧)，同時把Tail節(jié)點的Next屬性指向Head節(jié)點，就形成了所謂的“循環(huán)雙向鏈表”

當然，這樣的結(jié)構(gòu)可以在鏈表中再增加一個Tail節(jié)點屬性，在做元素插入或刪除時，可以循環(huán)到底以更新尾節(jié)點Tail(當然這樣會給插入/刪除元素帶來一些額外的開銷)，但是卻可以給GetItemAt(int i)方法帶來優(yōu)化的空間，比如要查找的元素在前半段時，可以從Head開始用next向后找；反之，如果要找的元素在后半段，則可以從Tail節(jié)點用prev屬性向前找。

注：.Net中微軟已經(jīng)給出了一個內(nèi)置的雙向鏈表System.Collections.Generic.LinkedList<T>，在了解雙鏈表的原理后，建議大家直接系統(tǒng)內(nèi)置的鏈表。

希望本文所述對大家C#程序設(shè)計有所幫助。

網(wǎng)頁制作CMS教程網(wǎng)絡(luò)編程軟件編程腳本語言數(shù)據(jù)庫服務(wù)器

如果侵犯了您的權(quán)利，請與我們聯(lián)系，我們將在24小時內(nèi)進行處理、任何非本站因素導(dǎo)致的法律后果，本站均不負任何責任。

聯(lián)系QQ：835971066 | 郵箱：835971066#qq.com(#換成@)

Copyright © 2002-2020 腳本教程網(wǎng) 版權(quán)所有