C#數據構造之雙向鏈表(DbLinkList)實例詳解。本站提示廣大學習愛好者:(C#數據構造之雙向鏈表(DbLinkList)實例詳解)文章只能為提供參考,不一定能成為您想要的結果。以下是C#數據構造之雙向鏈表(DbLinkList)實例詳解正文
本文實例講述了C#數據構造之雙向鏈表(DbLinkList)。分享給年夜家供年夜家參考,詳細以下:
這是繼上一篇《C#數據構造之單鏈表(LinkList)實例詳解》的持續,關於雙向鏈接,節點上除Next屬性外,還要有Prev屬性用來指向前一個節點,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; } } } }
雙鏈表的拔出操作要略微龐雜一點,表示圖以下:
異樣關於刪除操作,也要額定處置prev指向
完全完成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;//把本身設置為"頭" 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) //解釋是在最初節點拔出(即追加) { 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> /// 元素反轉 /// </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;//將原鏈表直接掛到"反轉後的鏈表"上 result = null;//顯式清空原鏈表的援用,以便讓GC能直接收受接管 } //獲得某個指定的節點(為了上面測試從後向前遍歷) 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
固然從下面的測試代碼中,仿佛其實不能看出雙鏈表的長處,雙鏈表的利益在於,假如須要在鏈表中,須要經由過程某個節點獲得它的先驅節點時,雙鏈表直接用prev屬性就可以找到;而單鏈表要做到這一點,必需再次從Head節點開端一個一個用Next向下找,如許時光龐雜度從O(n)降到O(1),明顯更有用率。
注:假如把雙鏈表再做一下改革,讓頭尾接起來,即Head的Prev屬性指向最初一個節點(就叫做Tail吧),同時把Tail節點的Next屬性指向Head節點,就構成了所謂的“輪回雙向鏈表”
固然,如許的構造可以在鏈表中再增長一個Tail節點屬性,在做元素拔出或刪除時,可以輪回究竟以更新尾節點Tail(固然如許會給拔出/刪除元素帶來一些額定的開支),然則卻可以給GetItemAt(int i)辦法帶來優化的空間,好比要查找的元素在前半段時,可以從Head開端用next向後找;反之,假如要找的元素在後半段,則可以從Tail節點用prev屬性向前找。
注:.Net中微軟曾經給出了一個內置的雙向鏈表System.Collections.Generic.LinkedList<T>,在懂得雙鏈表的道理後,建議年夜家直接體系內置的鏈表。
願望本文所述對年夜家C#法式設計有所贊助。