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#法式設計有所贊助。