C# 数据结构--单链表
2023-09-11 14:17:05 时间
这两天看到很多有关单链表的面试题,对单链表都不知道是啥的我。经过学习和整理来分享一下啥是单链表和单链表的一些基本使用方法。最后看些网上有关单链表的面试题代码实例。
啥是单链表?
单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。这组存储单元既可以是连续的,也可以是不连续的。
链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。
链表的结点结构:
┌───┬───┐
│data│next│
└───┴───┘
data域--存放结点值的数据域[元素]
next域--存放结点的直接后继的地址(位置)的指针域(链域)[指针]
用张图来说明一下上面的定义:
在VS中看到单链表的结构如下图:
实例代码
单键表结点类-泛型
public class Node<T> { public T Data { set; get; } //数据域,当前结点数据 public Node<T> Next { set; get; } //位置域,下一个结点地址 public Node(T item) { this.Data = item; this.Next = null; } public Node() { this.Data = default(T); this.Next = null; } }
public class LinkList<T> { public Node<T> Head { set; get; } //单链表头 //构造 public LinkList() { Head=null; } /// <summary> /// 增加新元素到单链表末尾 /// </summary> public void Append(T item) { Node<T> foot = new Node<T>(item); Node<T> A = new Node<T>(); if (Head == null) { Head = foot; return; } A = Head; while (A.Next != null) { A = A.Next; } A.Next = foot; } }
1.如果增加的是头结点。直接把数据域(Data)给Head,Next为空。因为只有一个头结点,没有对应的下结点。
2.单链表是”不走回头路“,所以每次增加都要从单链表的头开始找到单链表最后一个结点(最后一个结点就是Next为NULL),然后把最后一个结点的Next设置成需增加的结点,这时要需增加的结点变身为最后一结点,他的Next为NULL。
public class LinkList<T> { public Node<T> Head { set; get; } //单链表头 //构造 public LinkList() { Head=null; }
public void Delete(int i) { Node<T> A = new Node<T>(); if (i == 1) //删除头 { A = Head; Head = Head.Next; return; } Node<T> B = new Node<T>(); B = Head; int j = 1; while (B.Next != null && j < i) { A = B; B = B.Next; j++; } if (j == i) { A.Next = B.Next; } } }
1.如果删除的是头结点,那现在的头结点就应该是头结点的下一结点。
2.删除结点如果不是头结点。从单链表头开始查询要删除结点的位置。并记录删除的前一结点值A和所要删除的结点B。因为结点B被删除了,所以结点A的Next就应该为B的Next。把结点A的Next设置为结点B的Next。
单链表类
public class LinkList<T> { public Node<T> Head { set; get; } //单链表头 //构造 public LinkList() { Clear(); } /// <summary> /// 求单链表的长度 /// </summary> /// <returns></returns> public int GetLength() { Node<T> p = Head; int length = 0; while (p != null) { p = p.Next; length++; } return length; } /// <summary> /// 判断单键表是否为空 /// </summary> /// <returns></returns> public bool IsEmpty() { if (Head == null) return true; else return false; } /// <summary> /// 清空单链表 /// </summary> public void Clear() { Head = null; } /// <summary> /// 获得当前位置单链表中结点的值 /// </summary> /// <param name="i">结点位置</param> /// <returns></returns> public T GetNodeValue(int i) { if (IsEmpty() || i<1 || i>GetLength()) { Console.WriteLine("单链表为空或结点位置有误!"); return default(T); } Node<T> A = new Node<T>(); A = Head; int j = 1; while (A.Next!=null && j<i) { A = A.Next; j++; } return A.Data; } /// <summary> /// 增加新元素到单链表末尾 /// </summary> public void Append(T item) { Node<T> foot = new Node<T>(item); Node<T> A = new Node<T>(); if (Head == null) { Head = foot; return; } A = Head; while (A.Next != null) { A = A.Next; } A.Next = foot; } /// <summary> /// 增加单链表插入的位置 /// </summary> /// <param name="item">结点内容</param> /// <param name="n">结点插入的位置</param> public void Insert(T item, int n) { if (IsEmpty() || n < 1 || n > GetLength()) { Console.WriteLine("单链表为空或结点位置有误!"); return; } if (n == 1) //增加到头部 { Node<T> H = new Node<T>(item); H.Next = Head; Head = H; return; } Node<T> A = new Node<T>(); Node<T> B = new Node<T>(); B = Head; int j = 1; while (B.Next != null && j < n) { A = B; B = B.Next; j++; } if (j==n) { Node<T> C = new Node<T>(item); A.Next = C; C.Next = B; } } /// <summary> /// 删除单链表结点 /// </summary> /// <param name="i">删除结点位置</param> /// <returns></returns> public void Delete(int i) { if (IsEmpty() || i < 1 || i > GetLength()) { Console.WriteLine("单链表为空或结点位置有误!"); return; } Node<T> A = new Node<T>(); if (i == 1) //删除头 { A = Head; Head = Head.Next; return; } Node<T> B = new Node<T>(); B = Head; int j = 1; while (B.Next != null && j < i) { A = B; B = B.Next; j++; } if (j == i) { A.Next = B.Next; } } /// <summary> /// 显示单链表 /// </summary> public void Dispaly() { Node<T> A = new Node<T>(); A = Head; while (A != null) { Console.WriteLine(A.Data); A = A.Next; } } #region 面试题 /// <summary> /// 单链表反转 /// </summary> public void Reverse() { if (GetLength()==1 || Head==null) { return; } Node<T> NewNode = null; Node<T> CurrentNode = Head; Node<T> TempNode = new Node<T>(); while (CurrentNode!=null) { TempNode = CurrentNode.Next; CurrentNode.Next = NewNode; NewNode = CurrentNode; CurrentNode = TempNode; } Head = NewNode; Dispaly(); } /// <summary> /// 获得单链表中间值 /// 思路:使用两个指针,第一个每次走一步,第二个每次走两步: /// </summary> public void GetMiddleValue() { Node<T> A = Head; Node<T> B = Head; while (B!=null && B.Next!=null) { A = A.Next; B = B.Next.Next; } if (B != null) //奇数 { Console.WriteLine("奇数:中间值为:{0}", A.Data); } else //偶数 { Console.WriteLine("偶数:中间值为:{0}和{1}", A.Data, A.Next.Data); } } #endregion }
调用实例
static void Main(string[] args) { LinkList<string> link = new LinkList<string>(); link.Append("A"); link.Append("B"); link.Append("C"); link.Append("D"); link.Append("E"); link.Insert("Head", 1); Console.WriteLine("单链表内容:"); link.Dispaly(); link.Delete(5); Console.WriteLine("已完成删除单链表中第5行记录数"); link.Dispaly(); Console.WriteLine("查询单链表中第1:{0}.第3:{1}", link.GetNodeValue(1), link.GetNodeValue(3)); Console.WriteLine("面试题-->单链表反转"); link.Reverse(); Console.WriteLine("面试题-->获得单链表中间值"); link.GetMiddleValue(); }
输出结果:
相关文章
- C#-string生成图片
- c#代码 天气接口 一分钟搞懂你的博客为什么没人看 看完python这段爬虫代码,java流泪了c#沉默了 图片二进制转换与存入数据库相关 C#7.0--引用返回值和引用局部变量 JS直接调用C#后台方法(ajax调用) Linq To Json SqlServer 递归查询
- 程序猿修仙之路--数据结构之你是否真的懂数组? c#socket TCP同步网络通信 用lambda表达式树替代反射 ASP.NET MVC如何做一个简单的非法登录拦截
- 利用反射快速给Model实体赋值 使用 Task 简化异步编程 Guid ToString 格式知多少?(GUID 格式) Parallel Programming-实现并行操作的流水线(生产者、消费者) c# 无损高质量压缩图片代码 8种主要排序算法的C#实现 (一) 8种主要排序算法的C#实现 (二)
- 史上最全的CSS hack方式一览 jQuery 图片轮播的代码分离 JQuery中的动画 C#中Trim()、TrimStart()、TrimEnd()的用法 marquee 标签的使用详情 js鼠标事件 js添加遮罩层 页面上通过地址栏传值时出现乱码的两种解决方法 ref和out的区别在c#中 总结
- C#中泛型方法与泛型接口 C#泛型接口 List<IAll> arssr = new List<IAll>(); interface IPerson<T> c# List<接口>小技巧 泛型接口协变逆变的几个问题
- C# 字符串拼接性能探索 c#中+、string.Concat、string.Format、StringBuilder.Append四种方式进行字符串拼接时的性能
- 【卷土重来之C#学习笔记】(二)c#编程概述
- Word控件Spire.Doc 【图像形状】教程(7): 如何使用 C# 在 Word 中替换图像
- Word处理控件Aspose.Words功能演示:使用 C# 将 Word 文档转换为 HTML
- C#,图像二值化(18)——全局阈值的模糊集理论算法(Huang Thresholding)与源程序
- C# 正则表达式
- C#程序集系列02,使用记事本查看可执行程序集的IL代码
- C#+MapServer相关代码
- 《C#零基础入门之百识百例》(四十三)类的构造和析构函数 -- 模拟用户注册
- 《C#零基础入门之百识百例》(六十三)结构体类型数组 -- 学生数据存储
- C# 解决约瑟夫环问题
- C# 线程中调用控件
- C# 文件流读写方法汇总
- C#-【可空类型Nullable】-OK
- c#类的定义,c#中的关健字,C#标识符
- C# 4 中的 Dynamic 关键字