- 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的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
我目前正在尝试基于哈希表构建字典。逻辑是:有一个名为 HashTable 的结构,其中包含以下内容: HashFunc HashFunc; PrintFunc PrintEntry; CompareF
如果我有一个指向结构/对象的指针,并且该结构/对象包含另外两个指向其他对象的指针,并且我想删除“包含这两个指针的对象而不破坏它所持有的指针”——我该怎么做这样做吗? 指向对象 A 的指针(包含指向对象
像这样的代码 package main import "fmt" type Hello struct { ID int Raw string } type World []*Hell
我有一个采用以下格式的 CSV: Module, Topic, Sub-topic 它需要能够导入到具有以下格式的 MySQL 数据库中: CREATE TABLE `modules` ( `id
通常我使用类似的东西 copy((uint8_t*)&POD, (uint8_t*)(&POD + 1 ), back_inserter(rawData)); copy((uint8_t*)&PODV
错误 : 联合只能在具有兼容列类型的表上执行。 结构(层:字符串,skyward_number:字符串,skyward_points:字符串)<> 结构(skyward_number:字符串,层:字符
我有一个指向结构的指针数组,我正在尝试使用它们进行 while 循环。我对如何准确初始化它并不完全有信心,但我一直这样做: Entry *newEntry = malloc(sizeof(Entry)
我正在学习 C,我的问题可能很愚蠢,但我很困惑。在这样的函数中: int afunction(somevariables) { if (someconditions)
我现在正在做一项编程作业,我并没有真正完全掌握链接,因为我们还没有涉及它。但是我觉得我需要它来做我想做的事情,因为数组还不够 我创建了一个结构,如下 struct node { float coef;
给定以下代码片段: #include #include #define MAX_SIZE 15 typedef struct{ int touchdowns; int intercepti
struct contact list[3]; int checknullarray() { for(int x=0;x<10;x++) { if(strlen(con
这个问题在这里已经有了答案: 关闭 11 年前。 Possible Duplicate: Empty “for” loop in Facebook ajax what does AJAX call
我刚刚在反射器中浏览了一个文件,并在结构构造函数中看到了这个: this = new Binder.SyntaxNodeOrToken(); 我以前从未见过该术语。有人能解释一下这个赋值在 C# 中的
我经常使用字符串常量,例如: DICT_KEY1 = 'DICT_KEY1' DICT_KEY2 = 'DICT_KEY2' ... 很多时候我不介意实际的文字是什么,只要它们是独一无二的并且对人类读
我是 C 的新手,我不明白为什么下面的代码不起作用: typedef struct{ uint8_t a; uint8_t* b; } test_struct; test_struct
您能否制作一个行为类似于内置类之一的结构,您可以在其中直接分配值而无需调用属性? 前任: RoundedDouble count; count = 5; 而不是使用 RoundedDouble cou
这是我的代码: #include typedef struct { const char *description; float value; int age; } swag
在创建嵌套列表时,我认为 R 具有对列表元素有用的命名结构。我有一个列表列表,并希望应用包含在任何列表中的每个向量的函数。 lapply这样做但随后剥离了列表的命名结构。我该怎么办 lapply嵌套列
我正在做一个用于学习目的的个人组织者,我从来没有使用过 XML,所以我不确定我的解决方案是否是最好的。这是我附带的 XML 文件的基本结构:
我是新来的 nosql概念,所以当我开始学习时 PouchDB ,我找到了这个转换表。我的困惑是,如何PouchDB如果可以说我有多个表,是否意味着我需要创建多个数据库?因为根据我在 pouchdb
我是一名优秀的程序员,十分优秀!