客服电话
APP下载
迪恩网络APP
随时随地掌握行业动态
官方微信
扫描二维码
关注迪恩网络微信公众号
|
原文链接： http://blog.csdn.net/shanyongxu/article/details/47024865
链表 LinkedList<T>集合类没有非泛型类的版本,它是一个双向链表,他的元素指向元素的前一个与后一个元素. 链表的有点事:如果要插入一个元素到链表的中间位置,效率很高,因为如果插入一个元素,只需要修改上一个元素的Next与下一个元素的Previous的引用即可. 链表的缺点是,链表只能是一个接着一个访问,这样就要用更长的时间来查找定位位于链表中间的元素. LinkedListNode<T>被LinkedList<T>类包含,用LinkedListNode<T>类,可以获得元素的上一个与下一个元素的引用. LinkedList<T>的属性
LinkedList<T>的方法
案例:使用一个链表LinkedList<T>和一个列表List<T>,链表包含文档,与我们上一个队列的但文档有一个优先级,文档按优先级来排序,如查多个文档优先级相同.则按插入时间决定优先排序. 链表添加文档对象时,它们应放在优先级相同的最后一个文档后面,例如:要加一个文档,优先级数是3,那么,我们应放在3级文档组的最后一个,因为此时它是最晚插入的. using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks;
namespace 链表 { class Program { static void Main(string[] args) { PriorityDocumentManager man = new PriorityDocumentManager(); man.AddDocument(new Document("一", "nihao", 8)); man.AddDocument(new Document("二", "nihao", 3)); man.AddDocument(new Document("三", "nihao", 4)); man.AddDocument(new Document("四", "nihao", 8)); man.AddDocument(new Document("五", "nihao", 1)); man.AddDocument(new Document("六", "nihao", 9)); man.AddDocument(new Document("七", "nihao", 1)); man.AddDocument(new Document("八", "nihao", 1)); man.DispalyAllNodes(); Console.Read(); } } public class Document { private string title;
public string Title { get { return title; } set { title = value; } }
private string content;
public string Content { get { return content; } set { content = value; } } private int priority;
public int Priority { get { return priority; } set { priority = value; } } public Document(string title, string content, byte priority) { this.title = title; this.content = content; this.priority = priority; } } public class PriorityDocumentManager { //documentList包含所有的文档 private readonly LinkedList<Document> documentList; //priorityNodes包含最多10个元素的引用 private readonly List<LinkedListNode<Document>> priorityNodes;
public PriorityDocumentManager() { //初始化 documentList = new LinkedList<Document>(); priorityNodes = new List<LinkedListNode<Document>>(10);
for (int i = 0; i < 10; i++) { priorityNodes.Add(new LinkedListNode<Document>(null)); } } /// <summary> /// 添加文档 /// </summary> /// <param name="d">要添加的文档对象</param> public void AddDocument(Document d) { if (d==null) { //如果文档为空,抛出异常 throw new ArgumentNullException("d"); }
//调用添加方法 AddDocumentToPriorityNode(d, d.Priority); }
private void AddDocumentToPriorityNode(Document doc, int priority) { if (priority>9||priority<0) { throw new ArgumentException("优先级异常"); } if (this.priorityNodes[priority].Value==null) { priority--; if (priority>=0) { AddDocumentToPriorityNode(doc, priority); } else { this.documentList.AddLast(doc); this.priorityNodes[doc.Priority] = this.documentList.Last; } return; } else { LinkedListNode<Document> priorityNode=this.priorityNodes[priority]; if (priority==doc.Priority) { this.documentList.AddAfter(priorityNode, doc); this.priorityNodes[doc.Priority] = priorityNode.Next; } else { LinkedListNode<Document> firstPriorityNode = priorityNode; while (firstPriorityNode.Previous != null && firstPriorityNode.Previous.Value.Priority == priorityNode.Value.Priority) { firstPriorityNode = priorityNode.Previous; } this.documentList.AddBefore(firstPriorityNode, doc); priorityNodes[doc.Priority] = firstPriorityNode.Previous; } } } public void DispalyAllNodes() { foreach (Document doc in this.documentList) { Console.WriteLine("文档标题：{0} 文档内容:{1} 优先级：{2}", doc.Title, doc.Content, doc.Priority); } } } }
从上可以看出, 链表不仅能在列表中存储元素,还可以给每个元素存储下一个元素和上一个元素的信息.这就是LinkedList<T>包含LinkedListNode<T>类型的元素而定原因.使用LinkedListNode<T>类,可以获得列表中的下一个元素和上一个元素. 案例: using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks;
namespace 链表测试 { public struct test { public string name; public string num; } public struct test1 { public test st; public string name; } class Program { static void Main(string[] args) { LinkedList<test> t = new LinkedList<test>(); test t1, t2; test1 tt1, tt2; t1.name = "t1"; t2.name = "t2"; t1.num = "1"; t2.num = "2"; t.AddFirst(t1); t.AddFirst(t2);
tt1.st = t1; tt2.st = t2; tt1.name = "tt1"; tt2.name = "tt2"; LinkedList<test1> tt = new LinkedList<test1>(); tt.AddFirst(tt1); tt.AddFirst(tt2);
LinkedListNode<test1> current11 = tt.FindLast(tt1); test1 tr1 = current11.Value;
LinkedListNode<test> current1 = t.FindLast(t1); test tr = current1.Value; string[] words = { "the", "fox", "jumped", "over", "the", "dog" }; LinkedList<string> sentence = new LinkedList<string>(words); Display(sentence);
Console.WriteLine("sentence.Contain(\"jumped\")={0}", sentence.Contains("jumped"));
sentence.AddFirst("today"); Display(sentence);
LinkedListNode<string> mark1 = sentence.First; sentence.RemoveFirst(); sentence.AddLast(mark1); Display(sentence);
sentence.RemoveLast(); sentence.AddLast("yesterday"); Display(sentence);
mark1 = sentence.Last; sentence.RemoveLast(); sentence.AddFirst(mark1); Display(sentence);
sentence.RemoveFirst(); LinkedListNode<string> current = sentence.FindLast("the"); Display(sentence);
sentence.AddAfter(current, "old"); sentence.AddAfter(current, "lazy"); DIsplayNode(current);
current = sentence.Find("fox"); DIsplayNode(current);
sentence.AddBefore(current, "quick"); sentence.AddBefore(current, "brown"); DIsplayNode(current);
mark1 = current; LinkedListNode<string> mark2 = current.Previous; current = sentence.Find("dog"); DIsplayNode(current);
try { sentence.AddBefore(current, mark1); } catch (InvalidOperationException ex) { Console.WriteLine("Exception message: {0}", ex.Message); }
sentence.Remove(mark1); sentence.AddBefore(current, mark1); DIsplayNode(current);
sentence.Remove(current); DIsplayNode(current); sentence.AddAfter(mark2, current); DIsplayNode(current);
sentence.Remove("old"); Display(sentence);
sentence.RemoveLast(); ICollection<string> icoll = sentence; icoll.Add("rhinoceros"); Display(sentence);
Console.WriteLine("\nCopy the list to an array."); string[] sArray = new string[sentence.Count]; sentence.CopyTo(sArray, 0);
foreach (var item in sArray) { Console.WriteLine(item); } sentence.Clear(); } private static void Display(LinkedList<string> words) { foreach (var item in words) { Console.WriteLine(item + " "); } Console.WriteLine(); } private static void DIsplayNode(LinkedListNode<string> node) { if (node.List == null) { Console.WriteLine("Node \"{0}\" is not in a list.", node.Value); return; } StringBuilder result = new StringBuilder("(" + node.Value + ")"); LinkedListNode<string> nodeP = node.Previous;
while (nodeP != null) { result.Insert(0, nodeP.Value + " "); nodeP = nodeP.Previous; } node = node.Next;
while (node != null) { result.Append(" " + node.Value); node = node.Next; } Console.WriteLine(result); } } } 自定义链表: using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks;
namespace 自定义链表 { class Program { static void Main(string[] args) { } } public class Node<T> { public T data; public Node() { } public Node(T data) { this.data = data; } public Node<T> next = null; } public class Link<T> { //定义链表的头节点 private Node<T> head;
//链表初始化 public Link() { head = null; }
/// <summary> /// 链表的长度,遍历整个链表,知道链表结尾 /// </summary> /// <returns></returns> public int Count() { //定义一个节点 Node<T> p = head; int count = 0;//链表计数器
//遍历链表 while (p!=null) { count++; p = p.next;//移到下一个节点 } return count; }
/// <summary> /// 取链表的第i个节点的值 /// </summary> /// <param name="i">第i个节点</param> /// <returns></returns> public T GetElem(int i) { //定义一个节点 Node<T> p = head; int k = 0;//计数器
//如果i大于链表的长度或i小于0,则报出异常 if (i>=Count()||i<0) { throw new Exception("error"); }
//如果i大于0且小于链表长度,则遍历链表知道第i个节点为止
while (k<i) { k++; p = p.next; } return p.data; }
/// <summary> /// 在链表的第i个位置上插入新的节点 /// </summary> /// <param name="e">要插入节点的值</param> /// <param name="i">链表的第i个节点</param> public void Insert(T e, int i) { Node<T> p = new Node<T>(e);//要插入的节点
Node<T> q = head;
int k = 0;//计数器
//如果i大于链表的长度或i小于0,则抛出异常 if (i>=Count()||i<0) { Console.WriteLine("Error"); return; }
//如果再链表头插入,移动头指针 if (i==0) { p.next = head; head = p; return; }
//遍历链表直到i-1个节点为止 while (k<i-1) { k++; q = q.next; } //把新节点插入在第i以个点的位置 p.next = q.next; q.next = p; }
/// <summary> /// 删除第i个节点 /// </summary> /// <param name="i">链表的第i个节点</param> public void RemoveAt(int i) { Node<T> p = head; int k = 0;//计数器
// //如果i大于链表的长度或i小于0,则抛出异常 if (i >= Count() || i < 0) { Console.WriteLine("Error"); return; }
//如果删除链表头,移动头指针
if (i==0) { head.next = head.next.next; return; }
//遍历链表直到第i-1个节点为止 while (k<i-1) { k++; p = p.next; }
//删除第i个节点
p.next = p.next.next; }
/// <summary> /// 在链表尾加入一个新的节点 /// </summary> /// <param name="e">新的节点的值</param> public void Add(T e) { Node<T> p = new Node<T>(e);//创建一个新的节点
Node<T> q = new Node<T>();
//如果链表为空,则将新的节点作为头 if (head==null) { head = p; return; }
//如果链表不为空,则在链表尾加入新的节点
//从头指针开始遍历,直至链表尾 q = head;
while (q.next!=null) { q = q.next; }
//在链表尾插入新节点
q.next = q; }
/// <summary> /// 查找某个元素在立案表中第一次出现的位置 /// </summary> /// <param name="e">要查找的元素</param> /// <returns></returns> public int IndexOf(T e) { Node<T> p = head; int k = 0;//计数器
/* * 遍历整个链表,知道找到第一个节点的值 * 与钙元素相等退出,并返回相应的位置索引. * 如果没有找到,则返回-1 */
//从头指针开始遍历,找到退出,并返回相应的位置索引
while (p.next!=null) { if (p.data.Equals(e)) { return k; } k++; p = p.next; } if (!p.data.Equals(e)) { k++; }
//如果没有找到,则返回-1
return k >= Count() ? -1 : k; }
/// <summary> /// 查找某个元素在链表中最后一次出现的位置 /// </summary> /// <param name="e">要查找的元素</param> /// <returns>这个元素在链表中最后一次出现的位置的索引</returns> public int LastIndexOf(T e) { Node<T> p = head;
int index = -1;//最后一次出现的位置索引
int k = 0;//计数器
/* * 遍历整个链表,每发现相应节点的值与该元素相等 * 则将该节点的位置所以赋给index, * 这样index的值就是最后一次的值.如果没有,则返回-1 * */
while (p.next!=null) { if (p.data.Equals(e)) { index = k; } k++; p = p.next; } if (p.data.Equals(e)) { index = k; } return index; }
/// <summary> /// 判断链表是否为空 /// </summary> /// <returns></returns> public bool Empty() { return head == null ? true : false; }
/// <summary> /// 清空链表 /// </summary> public void Clear() { head = null; }
/// <summary> /// 将链表转成数组 /// </summary> /// <returns>转换后的数组</returns> public T[] ToArray() { T[] array = new T[Count()];//定义一个与链表长度相同的数组
/* * 遍历链表,将链表的每个节点的值放到相应的数组里 * */
Node<T> p = head;
int i = 0;//数组下标计数器
while (p.next!=null) { array[i++] = p.data; p = p.next; } array[Count() - 1] = p.data; return array; }
/// <summary> /// 将一个数组加到链表中 /// </summary> /// <param name="a">要加入链表的数组</param> public void AddRange(T[] a) { //遍历整个数组,将数组中的每个元素作为一个新的节点加入到链表中
for (int i = 0; i < a.Length; i++) { Add(a[i]); } }
/// <summary> /// 删除链表中值为某个元素的所有节点 /// </summary> /// <param name="e">要删除节点的值</param> public void Remove(T e) { //如果头指针的值等于这个元素,则删除这个元素,并将头指针后移 while (head.data.Equals(e)) { head = head.next; } //如果不是头指针,则删除该节点 Node<T> p = head; while (p.next.next!=null) { if (p.next.data.Equals(e)) { p.next = p.next.next; continue; } p = p.next; } if (p.next.data.Equals(e)) { p.next = null; } }
/// <summary> ///将链表中所有为某个值的节点替换为另一个值 /// </summary> /// <param name="first"></param> /// <param name="second"></param> public void Replace(T first, T second) { Node<T> p = head; while (p.next!=null) { if (p.data.Equals(first)) { p.data = second; } p = p.next; } if (p.data.Equals(first)) { p.data = second; } }
/// <summary> /// 链表反转 /// </summary> public void Reverse() { Node<T> p = head; Node<T> newhead = head; Node<T> q = p; p = p.next; newhead.next = null; while (p.next!=null) { q = p; p = p.next; q.next = newhead; newhead = q; } q = p; q.next = newhead; newhead = p; head = newhead; } }
}
|
2023-10-27
2022-08-15
2022-08-17
2022-09-23
2022-08-13
六六分期app的软件客服如何联系？不知道吗？加qq群【895510560】即可！标题：六六分期
今天小编告诉大家如何处理win10系统火狐flash插件总是崩溃的问题，可能很多用户都不知
今天小编告诉大家如何对win10系统删除桌面回收站图标进行设置，可能很多用户都不知道
今天小编告诉大家如何对win10系统电脑设置节能降温的设置方法，想必大家都遇到过需要
我们在使用xp系统的过程中,经常需要对xp系统无线网络安装向导设置进行设置，可能很多
今天小编告诉大家如何处理win7系统玩cf老是与主机连接不稳定的问题，可能很多用户都不
电脑对日常生活的重要性小编就不多说了，可是一旦碰到win7系统设置cf烟雾头的问题，很
我们在日常使用电脑的时候，有的小伙伴们可能在打开应用的时候会遇见提示应用程序无法
今天小编告诉大家如何对win7系统打开vcf文件进行设置，可能很多用户都不知道怎么对win
今天小编告诉大家如何对win10系统s4开启USB调试模式进行设置，可能很多用户都不知道怎
请发表评论