C#实现单链表(线性表)完整实例

时间:2021-05-20

本文实例讲述了C#实现单链表(线性表)的方法。分享给大家供大家参考,具体如下:

顺序表由连续内存构成,链表则不同。顺序表的优势在于查找,链表的优势在于插入元素等操作。顺序表的例子:

要注意的是,单链表的Add()方法最好不要频繁调用,尤其是链表长度较长的时候,因为每次Add,都会从头节点到尾节点进行遍历,这个缺点的优化方法是将节点添加到头部,但顺序是颠倒的。

所以,在下面的例子中,执行Purge(清洗重复元素)的时候,没有使用Add()方法去添加元素,而是定义一个节点,让它始终指向目标单链表的最后一个节点,这样就不用每次都从头到尾遍历。

此外,链表还可以做成循环链表,即最后一个结点的next属性等于head,主要操作与单链表相似,判断最后一个结点,不是等于null,而是等于head

using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace LinearList{ //定义线性表的行为,可供顺序表类和单链表类继承 public interface IListDS<T> { int GetLength(); void Insert(T item, int i); void Add(T item); bool IsEmpty(); T GetElement(int i); void Delete(int i); void Clear(); int LocateElement(T item); void Reverse(); } //链表节点类 class Node<T> { private T tData; private Node<T> nNext; public T Data { get { return this.tData; } set { this.tData = value; } } public Node<T> Next { get { return this.nNext; } set { this.nNext = value; } } public Node() { this.tData = default(T); this.nNext = null; } public Node(T t) { this.tData = t; this.nNext = null; } public Node(T t,Node<T> node) { this.tData = t; this.nNext = node; } } //该枚举表示单链表Add元素的位置,分头部和尾部两种 enum AddPosition {Head,Tail}; //单链表类 class LinkedList<T>:IListDS<T> { private Node<T> tHead;//单链表的表头 public Node<T> Head { get { return this.tHead; } set { this.tHead = value; } } public LinkedList() { this.tHead = null; } public LinkedList(Node<T> node) { this.tHead = node; } public void Add(T item,AddPosition p)//选择添加位置 { if (p == AddPosition.Tail) { this.Add(item);//默认添加在末尾 } else//从头部添加会节省查找的开销,时间复杂度为O(1)不必每次都循环到尾部,这恰好是顺序表的优点 { Node<T> node = this.Head; Node<T> nodeTmp = new Node<T>(item); if (node == null) { this.Head = nodeTmp; } else { nodeTmp.Next = node; this.tHead = nodeTmp; } } } #region IListDS<T> 成员 public int GetLength() { Node<T> node = new Node<T>(); int count = 0; node = this.tHead; while (node != null) { count++; node = node.Next; } return count; } public void Insert(T item, int i)//i最小从1开始 { Node<T> insertNode = new Node<T>(item, null);//实例化待添加的Node if (this.tHead == null && i == 1) { this.tHead = insertNode; return; } if (i < 1 || i > this.GetLength() || (this.tHead == null && i != 1)) { Console.WriteLine("There are no elements in this linked list!"); return; } int j = 1; Node<T> node = this.tHead; Node<T> nodeTmp; while (node != null && j < i)//循环结束时,保证node为第i个node { node = node.Next; j++; } nodeTmp = node.Next;//原来的单链表的第i+1个node node.Next = insertNode;//第i个node后的node修改为待插入的node insertNode.Next = nodeTmp;//待插入的node插入后,其后继node为原来链表的第i+1个node } public void Add(T item)//添加至尾部,时间复杂度为O(n),如果添加至头部,则会节省循环的开销 { Node<T> LastNode = new Node<T>(item, null);//实例化待添加的Node if (this.tHead == null) { this.tHead = LastNode; } else { Node<T> node = this.tHead; while (node.Next != null) { node = node.Next; } node.Next = LastNode; } } public bool IsEmpty() { return this.tHead == null; } public T GetElement(int i)//设i最小从1开始 { if (i < 1 || i > this.GetLength()) { Console.WriteLine("The location is not right!"); return default(T); } else { if (i == 1) { return this.tHead.Data; } else { Node<T> node = this.tHead; int j = 1; while (j < i) { node = node.Next; j++; } return node.Data; } } } public void Delete(int i)//设i最小从1开始 { if (i < 1 || i > this.GetLength()) { Console.WriteLine("The location is not right!"); } else { if (i == 1) { Node<T> node = this.tHead; this.tHead = node.Next; } else { Node<T> node = this.tHead; int j = 1; while (j < i-1) { node = node.Next; j++; } node.Next = node.Next.Next; } } } public void Clear() { this.tHead = null;//讲thead设为null后,则所有后继结点由于失去引用,等待GC自动回收 } public int LocateElement(T item)//返回值最小从1开始 { if (this.tHead == null) { Console.WriteLine("There are no elements in this linked list!"); return -1; } Node<T> node = this.tHead; int i = 0; while (node != null) { i++; if (node.Data.Equals(item))//如果Data是自定义类型,则其Equals函数必须override { return i; } node = node.Next; } Console.WriteLine("No found!"); return -1; } public void Reverse() { if (this.tHead == null) { Console.WriteLine("There are no elements in this linked list!"); } else { Node<T> node = this.tHead; if (node.Next == null)//如果只有头节点,则不作任何改动 { } else { Node<T> node1 = node.Next; Node<T> node2; while (node1 != null) { node2 = node.Next.Next; node.Next = node2;//可以发现node始终未变,始终是原来的那个头节点 node1.Next = this.tHead; this.tHead = node1; node1 = node2; } } } } #endregion } class Program { static void Main(string[] args) { } }}

更多关于C#相关内容感兴趣的读者可查看本站专题:《C#数据结构与算法教程》、《C#遍历算法与技巧总结》、《C#程序设计之线程使用技巧总结》、《C#操作Excel技巧总结》、《C#中XML文件操作技巧汇总》、《C#常见控件用法教程》、《WinForm控件用法总结》、《C#数组操作技巧总结》及《C#面向对象程序设计入门教程》

希望本文所述对大家C#程序设计有所帮助。

声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。

相关文章