做原创视频网站,智慧团建注册pc端,重庆大学建设管理与房地产学院网站,网站建设最低多少钱目录 前置知识#xff1a;
一、链表中的结点类LinkedNode
1、申明字段节点类#xff1a;
2、申明属性节点类:
二、两种方式实现单向链表
①定框架#xff1a;
②增加元素的方法#xff1a;因为是单链表#xff0c;所以增加元素一定是只能在末尾添加元素#xff0c;…目录 前置知识
一、链表中的结点类LinkedNode
1、申明字段节点类
2、申明属性节点类:
二、两种方式实现单向链表
①定框架
②增加元素的方法因为是单链表所以增加元素一定是只能在末尾添加元素即在头结点后面添加元素
③删除元素的方法删除链表中第一个符合删除目标值的节点
④查找节点是否存在这个就很简单直接遍历一遍就好了。 ⑤更新某一个节点的数据
三、测试
测试接口
写一个测试函数
开始测试
测试结果 前置知识 数据结构 数据结构数据元素之间的相互关系 常用的数据结构 数组、链表、栈、队列、树、图堆散列表 线性表 线性表是一种数据结构是由n个具有相同特性的数据元素的有限序列 例如数组、链表、栈、队列ArrayList 顺序存储 数组、Stack、Queue、ArrayList-顺序存储 只是 数组、Stack、Queue、ArrayList的组织规则不同而已 顺序存储 用一组地址连续的存储单元依次存储线性表的各个元素数据元素之间的逻辑关系由存储单元的邻接关系来体现。内存地址连续一整片的内存 顺序存储和链式存储 是数据结构中的两种存储方式 链式存储 单向链表、双向链表、循环链表-链式存储 链式存储链接存储 用一组任意的存储单元存储线性表中的各个数据元素内存地址不连续跳跃式的。 如需了解更多可看这一篇文章
线性表的相关知识 好的回归主线今天咱们学习的重点是单向链表以及双向链表循环链表。
一、链表中的结点类LinkedNode 什么是LinkedNode呢他有什么作用呢他其实就是组成链表的基本单位链表就是一个个的LinkedNode串起来的只不过串的方式不太一样。下面代码示例中不一定使用的是LinkedNode这个名字使用的是其他的名字不过没关系学习而已。例如 在单向链表中每个链表结点有一个指向下一个链表结点的类似于C语言中的指针的东西就是说明了当前节点的下一个就是你二者建立了联系。对于单向链表中第一个结点我们称之为头结点因为他只能向后指不能朝前看所以每次寻找某一个元素需要进行遍历而且你永远找不到自己的上一个元素是什么。于是有了双向链表。 在双向链表中每个链表节点存有两个指针一个是指向当前结点的上一个结点一个是指向当前结点的下一个结点其余的和单向链表相同。 所谓循环链表就是在单链表中将最后一个结点的下一个指向第一个结点。
好的接下来我们实现这个节点类 单向链表的节点类
两种定义方式
1、申明字段节点类
/// summary
/// 单向链表节点定义字段版本
/// /summary
/// typeparam nameT泛型数据类型/typeparam
public class ListNode_FieldT
{// 节点存储的数据字段public T data;// 指向下一个节点的指针字段// ? 表示这是一个可空类型允许值为 nullpublic ListNode_FieldT? next;/// summary/// 构造函数/// /summary/// param nameval节点数据/parampublic ListNode_Field(T val){data val;next null;}
}
2、申明属性节点类:
/// summary
/// 单向链表节点定义属性版本
/// /summary
/// typeparam nameT泛型数据类型/typeparam
public class SingleListNodeT
{// 节点存储的数据属性public T Data { get; set; }// 指向下一个节点的指针属性// ? 表示这是一个可空类型允许值为 nullpublic SingleListNodeT? Next { get; set; }/// summary/// 构造函数/// /summary/// param namedata节点数据/parampublic SingleListNode(T data){Data data;Next null; // 初始化时指针置空}
}这两种方式任意选择一种进行申明即可推荐使用属性因为可以自己处理的手段更多。
二、两种方式实现单向链表 好的接下来我们实现一个单向链表因为有了这些基本节点类所以才会有下面的代码。同样我们会使用属性节点类和字段节点类进行说明。其实都差不多的。 总的设计思路 1、提供一个头结点 2、利用这个头结点进行增删改查 接下来我们一一实现下面是一个利用字段节点声明的单向链表
①定框架 public class SingleLinkedList_FieldT{//设置一个私有头结点private ListNode_FieldT? head;}
②增加元素的方法因为是单链表所以增加元素一定是只能在末尾添加元素即在头结点后面添加元素 步骤 1先申明一个新的节点 2判断头结点是否为空为空则添加的元素就是头结点元素反之遍历找到最后一个节点然后将最后一个结点的next指向当前新创造的节点 /// summary
/// 在链表尾部添加新节点
/// /summary
public void Add(T data)
{ListNode_FieldT newNode new ListNode_FieldT(data);if (head null){head newNode;return;}// 遍历链表找到最后一个节点ListNode_FieldT current head;while (current.next ! null){current current.next;}current.next newNode; // 直接操作字段
}当然这个添加元素你也可以想想怎么在中间插入一个元素思想是将上一个的next指向插入元素插入元素的next指向上一个元素的下一个
③删除元素的方法删除链表中第一个符合删除目标值的节点 步骤 1先看有没有头结点没有头结点删除个屁啊 2然后看删除的是不是头结点是的话直接将头结点的next指向下一个就好啦 3不是头结点的话就稍微有一点点麻烦需要先遍历和Add方法差不多的 /// summary
/// 删除第一个匹配的节点
/// /summary
public bool Remove(T data)
{if (head null) return false;// 处理头节点匹配的情况if (head.data ! null head.data.Equals(data)){head head.next; // 直接操作字段return true;}ListNode_FieldT current head;while (current.next ! null){if (current.next.data ! null current.next.data.Equals(data)){current.next current.next.next; // 直接操作字段return true;}current current.next;}return false;
}④查找节点是否存在这个就很简单直接遍历一遍就好了。
/// summary
/// 查找节点是否存在
/// /summary
public bool Contains(T data)
{ListNode_FieldT? current head;while (current ! null){if (current.data ! null current.data.Equals(data)){return true;}current current.next;}return false;
} ⑤更新某一个节点的数据 步骤 1找到该节点 2操作该节点的数据 /// summary
/// 更新第一个匹配的节点的值
/// /summary
public bool Update(T oldData, T newData)
{ListNode_FieldT? node FindNode(oldData);if (node null) return false;node.data newData; // 直接操作字段return true;
}/// summary
/// 辅助方法查找指定数据的节点
/// /summary
private ListNode_FieldT? FindNode(T data)
{ListNode_FieldT? current head;while (current ! null){if (current.data ! null current.data.Equals(data)){return current;}current current.next;}return null;
} 好的那么我们就完成了一个最简单的单向链表的数据结构
附上使用属性申明的单行链表是一样的 /// summary/// 单向链表实现属性版本/// /summary/// typeparam nameT泛型数据类型/typeparampublic class SingleLinkedList_PropertyT : ISingleLinkedListT{// 头节点私有属性private SingleListNodeT? head;/// summary/// 在链表尾部添加新节点/// /summary/// param namedata要添加的数据/parampublic void Add(T data){// 显式声明类型不使用 varSingleListNodeT newNode new SingleListNodeT(data);if (head null){head newNode; // 链表为空时新节点作为头节点return;}// 遍历链表找到最后一个节点SingleListNodeT current head;while (current.Next ! null){current current.Next;}current.Next newNode; // 将新节点链接到尾部}/// summary/// 删除第一个匹配的节点/// /summary/// param namedata要删除的数据/param/// returns是否删除成功/returnspublic bool Remove(T data){if (head null) return false;// 处理头节点匹配的情况if (head.Data ! null head.Data.Equals(data)){head head.Next; // 头节点指向下一个节点return true;}// 遍历链表查找匹配的节点SingleListNodeT current head;while (current.Next ! null){if (current.Next.Data ! null current.Next.Data.Equals(data)){current.Next current.Next.Next; // 跳过匹配的节点return true;}current current.Next;}return false;}/// summary/// 查找节点是否存在/// /summary/// param namedata要查找的数据/param/// returns是否存在/returnspublic bool Contains(T data){SingleListNodeT? current head;while (current ! null){if (current.Data ! null current.Data.Equals(data)){return true;}current current.Next;}return false;}/// summary/// 更新第一个匹配的节点的值/// /summary/// param nameoldData旧数据/param/// param namenewData新数据/param/// returns是否更新成功/returnspublic bool Update(T oldData, T newData){SingleListNodeT? node FindNode(oldData);if (node null) return false;node.Data newData; // 直接修改节点的数据return true;}/// summary/// 辅助方法查找指定数据的节点/// /summaryprivate SingleListNodeT? FindNode(T data){SingleListNodeT? current head;while (current ! null){if (current.Data ! null current.Data.Equals(data)){return current;}current current.Next;}return null;}}
三、测试 测试部分呢因为两种都差不多所以我们使用一个接口让他们都实现里面的方法然后统一测试
测试接口
/// summary
/// 统一接口便于测试不同版本的链表
/// /summary
public interface ISingleLinkedListT
{void Add(T data);bool Remove(T data);bool Contains(T data);bool Update(T oldData, T newData);
}两个链表只要继承了这个接口就好
写一个测试函数
static void TestLinkedListT(T list) where T : ISingleLinkedListint
{// 添加节点list.Add(1);list.Add(2);list.Add(3);Console.WriteLine(添加 1, 2, 3 后链表内容应为1 - 2 - 3);// 测试查找Console.WriteLine(查找 2: list.Contains(2)); // 应输出 TrueConsole.WriteLine(查找 4: list.Contains(4)); // 应输出 False// 测试删除list.Remove(2);Console.WriteLine(删除 2 后链表内容应为1 - 3);Console.WriteLine(查找 2: list.Contains(2)); // 应输出 False// 测试更新list.Update(3, 4);Console.WriteLine(更新 3 为 4 后链表内容应为1 - 4);Console.WriteLine(查找 4: list.Contains(4)); // 应输出 True
}开始测试 static void Main(string[] args){// 测试属性版本链表Console.WriteLine(测试属性版本链表);TestLinkedList(new SingleLinkedList_Propertyint());// 测试字段版本链表Console.WriteLine(\n测试字段版本链表);TestLinkedList(new SingleLinkedList_Fieldint());}测试结果 如果再讲双向链表和循环链表会显得很杂乱我们将会在下一篇文章讨论诸位共勉
附本文所有代码
namespace 单向链表
{/// summary/// 单向链表节点定义属性版本/// /summary/// typeparam nameT泛型数据类型/typeparampublic class SingleListNodeT{// 节点存储的数据属性public T Data { get; set; }// 指向下一个节点的指针属性// ? 表示这是一个可空类型允许值为 null解决 CS8618 警告public SingleListNodeT? Next { get; set; }/// summary/// 构造函数/// /summary/// param namedata节点数据/parampublic SingleListNode(T data){Data data;Next null; // 初始化时指针置空}}/// summary/// 单向链表节点定义字段版本/// /summary/// typeparam nameT泛型数据类型/typeparampublic class ListNode_FieldT{// 节点存储的数据字段public T data;// 指向下一个节点的指针字段// ? 表示这是一个可空类型允许值为 nullpublic ListNode_FieldT? next;/// summary/// 构造函数/// /summary/// param nameval节点数据/parampublic ListNode_Field(T val){data val;next null;}}internal class Program{static void Main(string[] args){// 测试属性版本链表Console.WriteLine(测试属性版本链表);TestLinkedList(new SingleLinkedList_Propertyint());// 测试字段版本链表Console.WriteLine(\n测试字段版本链表);TestLinkedList(new SingleLinkedList_Fieldint());}static void TestLinkedListT(T list) where T : ISingleLinkedListint{// 添加节点list.Add(1);list.Add(2);list.Add(3);Console.WriteLine(添加 1, 2, 3 后链表内容应为1 - 2 - 3);// 测试查找Console.WriteLine(查找 2: list.Contains(2)); // 应输出 TrueConsole.WriteLine(查找 4: list.Contains(4)); // 应输出 False// 测试删除list.Remove(2);Console.WriteLine(删除 2 后链表内容应为1 - 3);Console.WriteLine(查找 2: list.Contains(2)); // 应输出 False// 测试更新list.Update(3, 4);Console.WriteLine(更新 3 为 4 后链表内容应为1 - 4);Console.WriteLine(查找 4: list.Contains(4)); // 应输出 True}}/// summary/// 统一接口便于测试不同版本的链表/// /summarypublic interface ISingleLinkedListT{void Add(T data);bool Remove(T data);bool Contains(T data);bool Update(T oldData, T newData);}/// summary/// 单向链表实现属性版本/// /summary/// typeparam nameT泛型数据类型/typeparampublic class SingleLinkedList_PropertyT : ISingleLinkedListT{// 头节点私有属性private SingleListNodeT? head;/// summary/// 在链表尾部添加新节点/// /summary/// param namedata要添加的数据/parampublic void Add(T data){// 显式声明类型不使用 varSingleListNodeT newNode new SingleListNodeT(data);if (head null){head newNode; // 链表为空时新节点作为头节点return;}// 遍历链表找到最后一个节点SingleListNodeT current head;while (current.Next ! null){current current.Next;}current.Next newNode; // 将新节点链接到尾部}/// summary/// 删除第一个匹配的节点/// /summary/// param namedata要删除的数据/param/// returns是否删除成功/returnspublic bool Remove(T data){if (head null) return false;// 处理头节点匹配的情况if (head.Data ! null head.Data.Equals(data)){head head.Next; // 头节点指向下一个节点return true;}// 遍历链表查找匹配的节点SingleListNodeT current head;while (current.Next ! null){if (current.Next.Data ! null current.Next.Data.Equals(data)){current.Next current.Next.Next; // 跳过匹配的节点return true;}current current.Next;}return false;}/// summary/// 查找节点是否存在/// /summary/// param namedata要查找的数据/param/// returns是否存在/returnspublic bool Contains(T data){SingleListNodeT? current head;while (current ! null){if (current.Data ! null current.Data.Equals(data)){return true;}current current.Next;}return false;}/// summary/// 更新第一个匹配的节点的值/// /summary/// param nameoldData旧数据/param/// param namenewData新数据/param/// returns是否更新成功/returnspublic bool Update(T oldData, T newData){SingleListNodeT? node FindNode(oldData);if (node null) return false;node.Data newData; // 直接修改节点的数据return true;}/// summary/// 辅助方法查找指定数据的节点/// /summaryprivate SingleListNodeT? FindNode(T data){SingleListNodeT? current head;while (current ! null){if (current.Data ! null current.Data.Equals(data)){return current;}current current.Next;}return null;}}/// summary/// 单向链表实现字段版本/// /summary/// typeparam nameT泛型数据类型/typeparampublic class SingleLinkedList_FieldT :ISingleLinkedListT{// 头节点私有字段private ListNode_FieldT? head;/// summary/// 在链表尾部添加新节点/// /summarypublic void Add(T data){ListNode_FieldT newNode new ListNode_FieldT(data);if (head null){head newNode;return;}// 遍历链表找到最后一个节点ListNode_FieldT current head;while (current.next ! null){current current.next;}current.next newNode; // 直接操作字段}/// summary/// 删除第一个匹配的节点/// /summarypublic bool Remove(T data){if (head null) return false;// 处理头节点匹配的情况if (head.data ! null head.data.Equals(data)){head head.next; // 直接操作字段return true;}ListNode_FieldT current head;while (current.next ! null){if (current.next.data ! null current.next.data.Equals(data)){current.next current.next.next; // 直接操作字段return true;}current current.next;}return false;}/// summary/// 查找节点是否存在/// /summarypublic bool Contains(T data){ListNode_FieldT? current head;while (current ! null){if (current.data ! null current.data.Equals(data)){return true;}current current.next;}return false;}/// summary/// 更新第一个匹配的节点的值/// /summarypublic bool Update(T oldData, T newData){ListNode_FieldT? node FindNode(oldData);if (node null) return false;node.data newData; // 直接操作字段return true;}/// summary/// 辅助方法查找指定数据的节点/// /summaryprivate ListNode_FieldT? FindNode(T data){ListNode_FieldT? current head;while (current ! null){if (current.data ! null current.data.Equals(data)){return current;}current current.next;}return null;}}
}
