- VisualStudio2022插件的安装及使用-编程手把手系列文章
- pprof-在现网场景怎么用
- C#实现的下拉多选框,下拉多选树,多级节点
- 【学习笔记】基础数据结构:猫树
今天我们将开始第二个数据类型-链表的学习,同样我们还是用最原始的方式,自己申请内存管理内存来实现一个链表.
什么是链表?链表在物理存储结构上表现为非顺序性和非连续性,因此链表的数据元素物理存储位置是随机的,动态分配的;而在逻辑结构上表现为线性结构的特点,即元素一个连着一个元素串起来像一条线 .
节点:其中链表元素又叫节点,一个节点主要包含数据域和指针域,其中数据域主要存放数据元素,而指针域主要存放下一个节点存储位置地址.
头指针:一个表示链表第一个节点位置的普通指针,并且永远指向第一个节点位置,方便后面使用链表.
头节点:通常表示链表的第一个节点,并且节点内数据域为空,因此也叫空节点,其作用主要用于解决一些特殊问题,因此也可以省略.
首元节点:由于头节点数据域为空,因此链表的第一个数据域不为空的节点叫首元节点,只是一个名称,并没有什么实际意义.
链表有两种分类方法,其一可以分为静态链表和动态链表,其二可以分为单向链表、双向链表以及循环链表.
单链表只有一个方向,每个节点包含数据域和指向下一个节点的指针域.
双向链表有两个方向,即每个节点包含数据域以及同时指向上一个节点和下一个节点的指针域.
循环链表指链表首尾相连,即最后一个节点的指针域指向第一个节点。循环链表也分单向循环链表和双向循环链表,原理都一样.
下面我们一起使用最原始的方式,自己申请内存空间,自己维护,完成链表的实现.
我们首先来定义链表的ADT(单链表).
ADT LinkedList{ 。
数据对象:D 是一个非空的元素集合,D = {a1, a2, ..., an},其中 ai 表示一个元素即节点,一个节点存储着数据和指向下一个节点的指针。
数据关系:D中的节点通过指针进行连接,每一个节点都包含一个指向下一个节点的指针。
基本操作:[
Init(n) :初始化一个空链表,即声明一个头指针,如有必要也可以声明一个头节点。
Length:返回链表长度。
HeadNode:返回头节点。
Find(v):返回数据域v对应的节点。
Update(n,v):更新n节点的数据域。
InsertAfter(n,v):在n节点后面添加数据域为v的新节点。
Remove(n):移除n节点。
Destroy():销毁链表。
] 。
} 。
定义好链表ADT,下面我们就可以开始自己实现一个数据域为string类型的链表.
首先我们需要定义节点,其中包含两个字段一个是存放数据、一个是存放指针,代码如下.
public struct MyselfLinkedListNode
{
//数据域
public string Data { get; set; }
//指针域
public IntPtr Next { get; set; }
}
然后再定义链表实现类MyselfLinkedList,用来实现链表的相关操作.
因为我们直接管理内存,所以需要一个维护内存的指针字段; 。
因为我们直接获取链表长度,所以需要一个存储链表长度字段; 。
因此我们的MyselfLinkedList类初步是这样的:
public sealed class MyselfLinkedList : IDisposable
{
//申请内存起始位置指针
private IntPtr _head;
//链表长度
private int _length;
}
初始化结构主要做几件事.
a.分配内存空间; 。
b.什么头指针; 。
c.创建头节点; 。
d.维护链表长度属性; 。
具体实现代码如下:
//初始化链表,声明头指针,并创建头节点
public MyselfLinkedListNode Init()
{
//计算节点的大小
var size = Marshal.SizeOf(typeof(MyselfLinkedListNode));
//分配指定字节数的内存空间
_head = Marshal.AllocHGlobal(size);
//创建头节点
var node = new MyselfLinkedListNode
{
Data = null,
Next = IntPtr.Zero
};
//将节点实例写入分配的内存
Marshal.StructureToPtr(node, _head, false);
//链表长度加1
_length++;
//返回头节点
return node;
}
这个比较简单直接把链表长度私有字段返回即可.
//链表长度
public int Length
{
get
{
return _length;
}
}
获取头节点主要是为了方便数据处理,可以通过头指针直接读取内存地址获取。具体代码如下:
//头节点
public MyselfLinkedListNode? HeadNode
{
get
{
if (_head == IntPtr.Zero)
{
return null;
}
return GetNode(_head);
}
}
//获取节点
private MyselfLinkedListNode GetNode(IntPtr pointer)
{
// 从分配的内存读取实例
return Marshal.PtrToStructure<MyselfLinkedListNode>(pointer);
}
同样我们也可以定义一个尾节点属性,可以方便使用,原理都差不多,这里就不赘述了.
通过前面对链表结构的了解,要想再两个节点之间加入一个新节点,只需要把两者之间的线剪断,即前一个节点的指针域需要重新指向新节点,并且新节点的指针域要指向后一个节点,其他保持不变,如下图:
业务逻辑清楚了,我们再来梳理代码逻辑,要想实现这个功能我们大致需要一下几步:
a.获取指定节点的指针; 。
b.创建一个新的节点; 。
c.重新调整指定节点及新节点指针域; 。
d.把指定节点和新节点指针调整后数据更新到内存中; 。
e.更新链表长度属性; 。
具体实现如下:
//在指定节点后插入新节点
public MyselfLinkedListNode InsertAfter(MyselfLinkedListNode node, string value)
{
//获指定取节点对应指针
var pointer = GetPointer(node);
//如果指针不为空才处理
if (pointer != IntPtr.Zero)
{
//以新值创建一个节点
var (newPointer, newNode) = CreateNode(value);
//把新节点的下一个节点指针指向指定节点的下一个节点
newNode.Next = node.Next;
//把指定节点的下一个节点指针指向新节点
node.Next = newPointer;
//更新修改后的节点
Marshal.StructureToPtr(newNode, newPointer, false);
Marshal.StructureToPtr(node, pointer, false);
//链表长度加1
_length++;
return newNode;
}
return default;
}
//获取节点对应指针
private IntPtr GetPointer(MyselfLinkedListNode node)
{
//从头指针开始查找
var currentPointer = _head;
//如果当前指针为空则停止查找
while (currentPointer != IntPtr.Zero)
{
//获取当前指针对应的节点
var currentNode = GetNode(currentPointer);
//如果当前节点数据域和指针域与要查找的节点相同则返回当前节点指针
if (currentNode.Data == node.Data && currentNode.Next == node.Next)
{
return currentPointer;
}
//否则查找下一个节点
currentPointer = currentNode.Next;
}
return IntPtr.Zero;
}
//创建节点
private (IntPtr Pointer, MyselfLinkedListNode Node) CreateNode(string value)
{
//计算大小
var size = Marshal.SizeOf(typeof(MyselfLinkedListNode));
//分配指定字节数的内存空间
var pointer = Marshal.AllocHGlobal(size);
//创建实例并设置值
var node = new MyselfLinkedListNode
{
Data = value,
Next = IntPtr.Zero
};
//将实例写入分配的内存
Marshal.StructureToPtr(node, pointer, false);
//返回节点指针和节点
return (pointer, node);
}
这里只实现了一个在指定节点后插入节点,我们还可以实现在指定节点前插入,在首元节点前插入,在尾节点后添加,都是可以的,感兴趣的可以自己实现试试.
在链表中对查找是不友好的,因为查找一个值,需要从链表头一个一个往后查找,实现逻辑到不复杂,具体实现代码如下:
//根据数据查找节点
public MyselfLinkedListNode Find(string value)
{
//从头指针开始查找
var pointer = _head;
//如果当前指针为空则停止查找
while (pointer != IntPtr.Zero)
{
//获取当前指针对应的节点
var node = GetNode(pointer);
//如果当前节点数据域和要查找值相同则返回当前节点
if (node.Data == value)
{
return node;
}
//否则查找下一个节点
pointer = node.Next;
}
return default;
}
这个方法逻辑也比较简单,只需要找到节点指针,然后把节点更新,最后把更新后的数据写入内存即可.
//更新节点数据
public void Update(MyselfLinkedListNode node, string value)
{
//获取节点对应指针
var pointer = GetPointer(node);
//当指针不为空,则更新节点数据
if (pointer != IntPtr.Zero)
{
//修改数据
node.Data = value;
//将数据写入分配的内存,完成数据更新
Marshal.StructureToPtr(node, pointer, false);
}
}
如果要想移除一个节点,则需要把指定节点与前后节点的连接删除,然后把前后两个节点建立起连接,同时需要手动释放被删除节点内存。如下图.
具体代码实现如下:
//移除节点
public void Remove(MyselfLinkedListNode node)
{
//从头指针开始查找
var currentPointer = _head;
//获取当前节点
var currentNode = GetNode(_head);
//查找节点对应的指针
var pointer = GetPointer(node);
while (true)
{
if (currentNode.Next == IntPtr.Zero)
{
//指针为空则返回
return;
}
else if (currentNode.Next == pointer)
{
//把要删除节点的上一个节点对应的下一个节点指向要删除节点的下一个节点
currentNode.Next = node.Next;
//手动释放被删除节点对应的内存
Marshal.FreeHGlobal(pointer);
//更新要删除节点的上一个节点
Marshal.StructureToPtr(currentNode, currentPointer, false);
//链表长度减1
_length--;
break;
}
else
{
//查找下一个节点
currentPointer = currentNode.Next;
currentNode = GetNode(currentPointer);
}
}
}
销毁链表主要是使用因为是我们自己手动管理内存,用完后要及时清理,放在内存泄漏等意外情况出现。代码也很简单,循环把每个节点内存释放即可,如下代码:
//销毁链表
public void Destroy()
{
var pointer = _head;
while (pointer != IntPtr.Zero)
{
var value = GetNode(pointer);
Marshal.FreeHGlobal(pointer);
_length--;
pointer = value.Next;
}
_head = IntPtr.Zero;
}
因为我们实现了IDisposable接口,所有需要实现Dispose方法,只需要在Dispose方法中调用上面销毁链表Destroy方法即可.
注:测试方法代码以及示例源码都已经上传至代码库,有兴趣的可以看看。https://gitee.com/hugogoos/Planner 。
最后此篇关于数据结构-链表的文章就讲到这里了,如果你想了解更多关于数据结构-链表的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
初学者 android 问题。好的,我已经成功写入文件。例如。 //获取文件名 String filename = getResources().getString(R.string.filename
我已经将相同的图像保存到/data/data/mypackage/img/中,现在我想显示这个全屏,我曾尝试使用 ACTION_VIEW 来显示 android 标准程序,但它不是从/data/dat
我正在使用Xcode 9,Swift 4。 我正在尝试使用以下代码从URL在ImageView中显示图像: func getImageFromUrl(sourceUrl: String) -> UII
我的 Ubuntu 安装 genymotion 有问题。主要是我无法调试我的数据库,因为通过 eclipse 中的 DBMS 和 shell 中的 adb 我无法查看/data/文件夹的内容。没有显示
我正在尝试用 PHP 发布一些 JSON 数据。但是出了点问题。 这是我的 html -- {% for x in sets %}
我观察到两种方法的结果不同。为什么是这样?我知道 lm 上发生了什么,但无法弄清楚 tslm 上发生了什么。 > library(forecast) > set.seed(2) > tts lm(t
我不确定为什么会这样!我有一个由 spring data elasticsearch 和 spring data jpa 使用的类,但是当我尝试运行我的应用程序时出现错误。 Error creatin
在 this vega 图表,如果我下载并转换 flare-dependencies.json使用以下 jq 到 csv命令, jq -r '(map(keys) | add | unique) as
我正在提交一个项目,我必须在其中创建一个带有表的 mysql 数据库。一切都在我这边进行,所以我只想检查如何将我所有的压缩文件发送给使用不同计算机的人。基本上,我如何为另一台计算机创建我的数据库文件,
我有一个应用程序可以将文本文件写入内部存储。我想仔细看看我的电脑。 我运行了 Toast.makeText 来显示路径,它说:/数据/数据/我的包 但是当我转到 Android Studio 的 An
我喜欢使用 Genymotion 模拟器以如此出色的速度加载 Android。它有非常好的速度,但仍然有一些不稳定的性能。 如何从 Eclipse 中的文件资源管理器访问 Genymotion 模拟器
我需要更改 Silverlight 中文本框的格式。数据通过 MVVM 绑定(bind)。 例如,有一个 int 属性,我将 1 添加到 setter 中的值并调用 OnPropertyChanged
我想向 Youtube Data API 提出请求,但我不需要访问任何用户信息。我只想浏览公共(public)视频并根据搜索词显示视频。 我可以在未经授权的情况下这样做吗? 最佳答案 YouTube
我已经设置了一个 Twilio 应用程序,我想向人们发送更新,但我不想回复单个文本。我只是想让他们在有问题时打电话。我一切正常,但我想在发送文本时显示传入文本,以确保我不会错过任何问题。我正在使用 p
我有一个带有表单的网站(目前它是纯 HTML,但我们正在切换到 JQuery)。流程是这样的: 接受用户的输入 --- 5 个整数 通过 REST 调用网络服务 在服务器端运行一些计算...并生成一个
假设我们有一个名为 configuration.js 的文件,当我们查看内部时,我们会看到: 'use strict'; var profile = { "project": "%Projec
这部分是对 Previous Question 的扩展我的: 我现在可以从我的 CI Controller 成功返回 JSON 数据,它返回: {"results":[{"id":"1","Sourc
有什么有效的方法可以删除 ios 中 CBL 的所有文档存储?我对此有疑问,或者,如果有人知道如何从本质上使该应用程序像刚刚安装一样,那也会非常有帮助。我们正在努力确保我们的注销实际上将应用程序设置为
我有一个 Rails 应用程序,它与其他 Rails 应用程序通信以进行数据插入。我使用 jQuery $.post 方法进行数据插入。对于插入,我的其他 Rails 应用程序显示 200 OK。但在
我正在为服务于发布请求的 API 调用运行单元测试。我正在传递请求正文,并且必须将响应作为帐户数据返回。但我只收到断言错误 注意:数据是从 Azure 中获取的 spec.js const accou
我是一名优秀的程序员,十分优秀!