目录
单链表是一种简单的链表表示,也叫做线性链表。用它来表示线性表时,用指针表示结点间的逻辑关系。因此单链表的一个存储结点包含两部分内容:
data 部分称为数据域,用于存储线性表的一个数据元素;next 部分称为指针域,用于存放一个指针,该指针是该链表下一个结点的开始存储地址。下面对单链表的逻辑结构和物理逻辑进行分析。
单链表逻辑结构:
逻辑结构: 想象出来的,形象,方便理解。结构图如下:
单链表物理结构:
物理结构:在内存中实实在在如何存储的。物理结构图如下:
上面对逻辑结构和物理结构进行了分析需要注意如下几点:
(1)从上图看出,链式结构在逻辑上是连续的,但是在物理上不一定连续。
(2)现实中的结点一般都是从堆上申请出来的。
(3)从堆上申请的空间,是按照一定的策略来分配的,两次申请的空间可能连续,也可能不连续。
单链表的第 1个结点,也称为首节点,它的地址可以通过链表的头指针 head 找到,其他节点的地址通过前结点的 next 域找到,链表的最后一个结点没有后继,则在 next 域放一个空指针NULL。
线性表中的数据元素的顺序与其链表表示中的物理顺序可能不一致,一般是通过单链表的指针将各个数据元素按照线性表的逻辑顺序链接起来。当 head 为空时,则单链表为空表,否则为非空表。
链表是一种动态的数据结构,在程序中需要使用 malloc() 或者使用动态内存开辟的其他函数创建链表。为了有效地存储结点数据,并且实现链表的链式功能,可建立 SListNode 结构体。代码如下:
typedef int SLTDataType;//使用 STDataType 代替 int
typedef struct SListNode
{
SLTDataType data;//数据域
struct ListNode* pnext;//指针域
}SListNode;
1.链表结点的创建
// 动态申请一个结点
SListNode* BuySListNode(SLTDataType x)
{
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));//定义一个结构体指针变量,该指针变量在使用前必须分配存储空间。
newnode->data = x;//然后输入值初始化结点数据
newnode->pnext = NULL;//同时初始化该结点指向的下一个结点为空。
return newnode;
}
分析:运行上面的结构的声明后,SListNode 就成为一个动态指针结构。建立了结点的结构后,接下来定义一个结构体指针变量,该指针变量在使用前必须分配存储空间,然后输入值初始化结点数据,同时初始化该结点指向的下一个结点为空。
2.链表尾插
分析:尾插是什么意思呢?尾插的意思就是把新创建好的链表插放到该链表的尾部。如下图:
那我们该怎么做呢?其实很简单,就是让 结点 4 指针域的指针存储着新结点的地址就可以了。如下图:
// 链表尾插
void SListPushBack(SListNode** head, SLTDataType x)
{
SListNode* newnode = BuySListNode(x);
if (*head == NULL)//判断链表是不是为空
{
*head = newnode;
}
else
{
SListNode* tail = *head;
while (tail->pnext != NULL)//如果head不为空,那么我们就要找到尾结点,找到尾结点才能尾插。
{
tail = tail->pnext;
}
tail->pnext = newnode;
}
}
看了代码之后有的人就觉得和上面说的不一样了。其实不然,我们在尾插的时候需要考虑链表 head 是不是空的链表,如果是空的,那么新结点 newnode 就作为头结点。如下图:
head 为什么是二级指针呢?我们都知道通过指针去改变指向空间的内容,传一级指针;改变指针的指向,传二级指针,因为 head 指向的是一个空,我们要改变指针的指向就要传指针 head 的地址,用二级指针存储一级指针的地址,只有拿到地址后,我们才能通过地址去改变 head 指针的指向。
如果 head 不为空,那么我们就要找到尾结点,通过遍历,找到尾结点后进行尾插。
3.链表头插
头插是什么意思?头插就是在原链表的头结点前面插入一个 newnode,如下图:
把 newnode 指针域的指针指向 结点1 的存储地址,然后更新一下头指针,这个时候 newnode 就成为新的头指针。如下图:
即使 head 为空亦如此,如下图:
// 链表的头插
void SListPushFront(SListNode** head, SLTDataType x)
{
SListNode* newnode = BuySListNode(x);
newnode->pnext = *head;
*head = newnode;
}
4.链表尾删
//链表尾删
void SListPopBack(SListNode** head)
{
assert(*head);//判断是不是空链表,是空的链表就删不了。
if ((*head)->pnext==NULL)//判断是不是只有一个结点
{
free(*head);//释放内存空间
*head = NULL;//将头结点置空
}
else
{
SListNode* tail = *head;
SListNode* previous = NULL;
while (tail->pnext!= NULL)//找尾结点
{
previous = tail;//记录上一个结点
tail = tail->pnext;
}
free(tail);//释放该内存空间-->也就是删除
tail = NULL;
previous->pnext = NULL;//将新的尾结点置ko
}
}
链表尾删就是把链表的最后一个结点删除掉,就达到尾删的效果了。首先判断链表是不是空链表,空链表就删不了。随后判断是不是只有一个结点,如果链表只有一个结点(头结点),那就对头结点进行释放,然后对指向头结点的头指针置空。如下图:
第三种情况就是对非空,非一个结点的链表进行操作。尾删之前,得先找到尾结点才能对该结点进行删除。找到尾结点了,删除之前我们还要找到尾结点的上一个结点的地址。因为尾删之后,尾结点的上一个结点就成为尾结点了,尾结点指针域的指针要置空,否则会造成非法访问。操作如下图:
5.链表头删
头删就是把头结点删除,然后指针 head 指向第二个结点,此时,也就是成为头结点。
// 链表头删
void SListPopFront(SListNode** head)
{
assert(*head);
SListNode* temp = *head;
*head = (*head)->pnext;
free(temp);
temp = NULL;
}
头删之前先检查链表是不是为空链表,如果为空链表,就会报错,终止程序。这里我是用断言对链表是否为空进行检查,对头结点删除的操作如下图:
6.链表查找
链表查找意思是对链表中的数据进行查找,若找到了返回该数据的地址(也就是该数据结点的地址),若找不到则返回空指针;查找之前先用断言判断该链表是否为空链表,查找的方式是对该链表进行遍历。
// 链表查找
SListNode* SListFind(SListNode* head, SLTDataType x)
{
assert(head);
SListNode* current = head;
while (current != NULL)
{
if (current->data == x)
{
return current;
}
current = current->pnext;
}
return NULL;
}
7.在 pos 位置之前插入一个数据
//在pos位置之前插入x
void SListInsertBefore(SListNode** head,SListNode* pos, SLTDataType x)
{
assert(*head);//如果是空链表,则不进行操作。
SListNode* newnode = BuySListNode(x);
if (*head == pos)
{
newnode->pnext = *head;
*head = newnode;
}
else
{
SListNode* previous = *head;
while (previous->pnext != pos)
{
previous = previous->pnext;
}
previous->pnext = newnode;
newnode->pnext = pos;
}
}
第一种情况:判断 pos 是不是头结点,如果是头结点,那么就进行头插。第二种情况:如果 pos 不是头结点,那么就要先找到 pos 的前一个结点的位置。找到 pos 的前一个结点的位置,使 pos 前一个结点指针域的指针储存插入的结点 newnode,然后再将 newnode 指针域的指针储存 pos。如下图:
7.在 pos 位置之后插入一个数据
// 在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
SListNode* newnode = BuySListNode(x);
SListNode* temp = pos->pnext;
pos->pnext = newnode;
newnode->pnext = temp;
}
相对于在 pos 位置之前插入一个数据,在 pos 位置之后插入一个数据更加简单。 使用一个指针变量 temp 储存 pos 下一个位置的地址,然后将 pos 指针域的指针储存 newnode,newnode 指针域的指针储存 temp 的地址,就达到 pos 之后插入一个数据了。如下图:
8.删除 pos 位置之前的值
// 链表删除pos位置之前的值
void SListEraseBefore(SListNode** head, SListNode* pos)
{
assert(*head&&pos);//判断链表和pos是否为空
if (*head ==pos)
{
return;
}
else
{
SListNode* previous = NULL;
SListNode* current = *head;
if (current->pnext == pos)
{
free(*head);
*head = pos;
}
else
{
while (current->pnext != pos)
{
previous = current;
current = current->pnext;
}
free(current);
current = NULL;
previous->pnext = pos;
}
}
}
第一种情况:如果pos为头结点,直接return;第二种情况:pos不为头结点,先判断pos是不是第二个结点,如果是第二个结点,那就属于头删。如果pos不是第二节点,要对pos的前一个结点进行删除,那就要找到 pos 的前一个结点,和 pos 前前一个结点。再将 pos 的前一个结点删除,再把 pos 的前前一个结点的指针域的指针指向 pos。如下图:
9.删除pos位置之后的值
// 删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
//if (pos->pnext == NULL)
//{
// return;
//}
assert(pos);//判断pos是否为空
SListNode* posafter = pos->pnext;//pos的下一个结点
SListNode* posafterafter = posafter->pnext;//pos的下下一个结点
pos->pnext = posafterafter;
free(posafter);
posafter = NULL;
//②
//SListNode* next = pos->pnext;
//pos->pnext = next->pnext;
//free(next);
//next = NULL;
}
删除pos之后的值,需要找到 pos 的下一个结点和 pos 的下下一个结点。然后再将 pos 的下一个删除,最后再将 pos 指针域的指针指向 pos 的下下一个结点的地址。如下图:
10.删除 pos 的位置的值
//删除 pos 位置的结点
void SListErase(SListNode** head, SListNode* pos)
{
assert(*head&&pos);//判断head和pos是否为空
if (pos == *head)
{
/*SListNode* temp = *pplist;
*pplist = (*pplist)->pnext;
free(temp);
temp = NULL;*/
*head = pos->pnext;
free(pos);
}
else
{
SListNode* current = *head;
SListNode* posafter = pos->pnext;
while (current->pnext != pos)
{
current = current->pnext;
}
free(pos);
pos = NULL;
current->pnext = posafter;
}
}
第一种情况:如果 pos 等于 head ,那就相当于头删;第二种情况:pos 不等于 head ,想要删除 pos 位置的结点,那么就要先找出 pos 前一个结点和 pos 后一个结点。后一个容易找,就是 pos 指针域的指针存储的地址。那么 pos 的前一个结点就需要靠遍历链表找到的,当找到 pos 前一个结点时,就把 pos 前一个结点指针域的指针指向 pos 的下一个结点的地址。如下图:
11.释放链表的所有结点
//释放链表的所有结点
void SListDestroy(SListNode** head)
{
SListNode* current = *head;
while (current)
{
SListNode* next = current->pnext;
free(current);
current = next;
}
*head = NULL;
}
释放链表,就是将链表中的所有结点进行释放,释放的方法是:遍历链表,记住当前结点的下一个结点的地址,然后释放当前的结点,再把 当前结点的下一个结点的地址 赋值给当前结点,直到释放完全部链表的结点。最后,将 head 指针置空。
12.链表打印
// 打印链表中的数据
void SListPrint(SListNode* head)
{
SListNode* current = head;
while (current!= NULL)
{
printf("%d->", current->data);
current = current->pnext;
}
printf("NULL");
printf("\n");
}
从头结点到尾结点开始遍历,将一个一个结点的数据打印出来。
SList.h
#pragma
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;//使用 STDataType 代替 int
typedef struct SListNode
{
SLTDataType data;//数据域
struct ListNode* pnext;//指针域
}SListNode;
// 动态申请一个结点
SListNode* BuySListNode(SLTDataType x);
// 单链表打印
void SListPrint(SListNode* head);
// 单链表尾插
void SListPushBack(SListNode** head, SLTDataType x);
// 单链表的头插
void SListPushFront(SListNode** head, SLTDataType x);
// 单链表的尾删
void SListPopBack(SListNode** head);
// 单链表头删
void SListPopFront(SListNode** head);
// 单链表查找
SListNode* SListFind(SListNode* head, SLTDataType x);
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDataType x);
//在pos位置之前插入x
void SListInsertBefore(SListNode** head, SListNode* pos, SLTDataType x);
// 单链表删除pos位置之后的值
void SListEraseBefore(SListNode** head, SListNode* pos);
// 单链表删除pos位置之前的值
void SListEraseAfter(SListNode* pos);
//删除掉当前的位置
void SListErase(SListNode** head, SListNode* pos);
//释放链表
void SListDestroy(SListNode** head);
SList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
// 动态申请一个结点
SListNode* BuySListNode(SLTDataType x)
{
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
newnode->data = x;
newnode->pnext = NULL;
return newnode;
}
// 打印链表中的数据
void SListPrint(SListNode* head)
{
SListNode* current = head;
while (current!= NULL)
{
printf("%d->", current->data);
current = current->pnext;
}
printf("NULL");
printf("\n");
}
// 单链表尾插
void SListPushBack(SListNode** head, SLTDataType x)
{
SListNode* newnode = BuySListNode(x);
if (*head == NULL)
{
*head = newnode;
}
else
{
SListNode* tail = *head;
while (tail->pnext != NULL)
{
tail = tail->pnext;
}
tail->pnext = newnode;
}
}
// 单链表的头插
void SListPushFront(SListNode** head, SLTDataType x)
{
SListNode* newnode = BuySListNode(x);
newnode->pnext = *head;
*head = newnode;
}
// 单链表的尾删
void SListPopBack(SListNode** head)
{
assert(*head);
if ((*head)->pnext==NULL)
{
free(*head);
*head = NULL;
}
else
{
SListNode* tail = *head;
SListNode* previous = NULL;
while (tail->pnext!= NULL)
{
previous = tail;
tail = tail->pnext;
}
free(tail);
tail = NULL;
previous->pnext = NULL;
}
}
// 单链表头删
void SListPopFront(SListNode** head)
{
assert(*head);
SListNode* temp = *head;
*head = (*head)->pnext;
free(temp);
temp = NULL;
}
// 单链表查找
SListNode* SListFind(SListNode* head, SLTDataType x)
{
assert(head);
SListNode* current = head;
while (current != NULL)
{
if (current->data == x)
{
return current;
}
current = current->pnext;
}
return NULL;
}
//在pos位置之前插入x
void SListInsertBefore(SListNode** head,SListNode* pos, SLTDataType x)
{
assert(*head);
SListNode* newnode = BuySListNode(x);
if (*head == pos)
{
newnode->pnext = *head;
*head = newnode;
}
else
{
SListNode* previous = *head;
while (previous->pnext != pos)
{
previous = previous->pnext;
}
previous->pnext = newnode;
newnode->pnext = pos;
}
}
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
SListNode* newnode = BuySListNode(x);
SListNode* temp = pos->pnext;
pos->pnext = newnode;
newnode->pnext = temp;
}
// 单链表删除pos位置之前的值
void SListEraseBefore(SListNode** head, SListNode* pos)
{
assert(*head&&pos);
if (*head ==pos)
{
return;
}
else
{
SListNode* previous = NULL;
SListNode* current = *head;
if (current->pnext == pos)
{
free(*head);
*head = pos;
}
else
{
while (current->pnext != pos)
{
previous = current;
current = current->pnext;
}
free(current);
current = NULL;
previous->pnext = pos;
}
}
}
// 单链表删除pos位置之后的值
void SListEraseAfter(SListNode* pos)
{
//if (pos->pnext == NULL)
//{
// return;
//}
assert(pos);
SListNode* posafter = pos->pnext;
SListNode* posafterafter = posafter->pnext;
pos->pnext = posafterafter;
free(posafter);
posafter = NULL;
//②
//SListNode* next = pos->pnext;
//pos->pnext = next->pnext;
//free(next);
//next = NULL;
}
//删除 pos 位置的结点
void SListErase(SListNode** head, SListNode* pos)
{
assert(*head &&pos);
if (pos == *head)
{
/*SListNode* temp = *pplist;
*pplist = (*pplist)->pnext;
free(temp);
temp = NULL;*/
*head = pos->pnext;
free(pos);
}
else
{
SListNode* current = *head;
SListNode* posafter = pos->pnext;
while (current->pnext != pos)
{
current = current->pnext;
}
free(pos);
pos = NULL;
current->pnext = posafter;
}
}
//释放链表的所有结点
void SListDestroy(SListNode** head)
{
SListNode* current = *head;
while (current)
{
SListNode* next = current->pnext;
free(current);
current = next;
}
*head = NULL;
}
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"
void test()
{
SListNode* head = NULL;
printf("尾插:> ");
SListPushBack(&head, 1);//尾插
SListPushBack(&head, 2);
SListPushBack(&head, 3);
SListPushBack(&head, 4);
SListPrint(head);//链表打印
printf("头插:> ");
SListPushFront(&head, 4); //头插
SListPushFront(&head, 3);
SListPushFront(&head, 2);
SListPushFront(&head, 1);
SListPrint(head);
printf("尾删:> ");
SListPopBack(&head);//尾删
SListPopBack(&head);
SListPrint(head);
printf("头删:> ");
SListPopFront(&head);//头删
SListPopFront(&head);
SListPrint(head);
printf("在 pos 位置之前插入一个数据 10 :> ");
SListNode* pos = SListFind(head, 1);//查找
SListInsertBefore(&head,pos, 10);//在 pos 位置之前插入一个数据
SListPrint(head);
printf("在 pos 位置之后插入一个数据 40 :> ");
pos = SListFind(head, 4);//查找
SListInsertAfter(pos, 40);//在 pos 位置之后插入一个数据
SListPrint(head);
printf("删除 pos 位置之前的值:> ");
pos = SListFind(head, 1);//查找
SListEraseBefore (&head,pos);//删除 pos 位置之前的值
SListPrint(head);
printf("删除 pos 位置之后的值:> ");
pos = SListFind(head, 4);//查找
SListEraseAfter(pos);//删除 pos 位置之后的值
SListPrint(head);
printf("删除 pos 位置的值:> ");
pos = SListFind(head, 4);//查找
SListErase(&head,pos);//删除 pos 位置的值
SListPrint(head);
SListDestroy(&head);//释放链表
}
int main()
{
test();
return 0;
}
文章浏览阅读288次。遥感图像方面的人工智能数据集数据集类别常用数据集目标检测数据集DSTL 卫星图像数据集;RSOD-Dataset 数据集;NWPUVHR-10地理遥感数据集图像分割数据集Inria AerialImage Labeling Dataset 遥感图像数据集遥感图像分类数据集UCMerced Land-Use Data Set 土地遥感数据集_群智感知 图像数据集
文章浏览阅读2.9k次,点赞3次,收藏11次。如何在pycharm中安装opencv_opencv_python安装镜像
文章浏览阅读595次,点赞2次,收藏8次。我的小站SSM项目需要用来管理依赖,所以我们需要先配置好,配置很容易,我就不演示了。首先,我们新建项目,勾选,选择模板,然后创建。这里耐心等待下载完成。可以看到,这里没用相关的文件夹。我们直接在文件夹上右键新建文件夹,下面会显示一个,直接创建就可以。此时,我们按照规范来,创建一个包。项目结构多种多样,比如三层架构啥的,按照你的需求来。我这里就稍微演示一下。这里这些结构都是可以自己按照规范命名,结构也有很多,分层架构方法也有很多,这里权当借鉴一下。我这里整合了一份依赖,如需使用可按照自己需求和对于版本进_idea创建ssm web项目
文章浏览阅读3.2k次。2022年-2023年中职网络安全web渗透任务整理合集_server2280 中职组
文章浏览阅读645次。这个肯定是末尾的IDAT了,因为IDAT必须要满了才会开始一下个IDAT,这个明显就是末尾的IDAT了。,对应下面的create_head()代码。,对应下面的create_tail()代码。不要考虑爆破,我已经试了一下,太多情况了。题目来源:UNCTF。_攻防世界困难模式攻略图文
文章浏览阅读2.9k次,点赞3次,收藏10次。偶尔会用到,记录、分享。1. 数据库导出1.1 切换到dmdba用户su - dmdba1.2 进入达梦数据库安装路径的bin目录,执行导库操作 导出语句:./dexp cwy_init/[email protected]:5236 file=cwy_init.dmp log=cwy_init_exp.log 注释: cwy_init/init_123..._达梦数据库导入导出
文章浏览阅读2.1k次,点赞24次,收藏47次。Apache Jmeter常用插件下载及安装_jmeter插件下载
文章浏览阅读5.9k次,点赞6次,收藏18次。实际上Mybatis的整合过程像极了我们程序员的一生。在SpringBoot 整合Mybatis之前,我们回忆回忆以前 MyBatis 单独使用时,myBatis 核心配置文件要配置数据源、事务、连接数据库账号、密码....是的全是这货一个人干,都要亲力亲为。这就是我们的低谷期myBatis 与 spring 整合的时候,配置数据源、事务、连接数据库的账号什么的都交由 spring 管理就行,就不用什么都自己管理自己去干。这就是我们春风得意的时候,事业有着落...再后来,Spring_springboot2.1.5整合mybatis不需要配置mapper-locations
文章浏览阅读162次。原标题:颤抖吧 iOS, Android 8.0正式发布!如果现在选一个最好用的手机操作系统,多数人还是认为 iOS。不过最近几年,苹果和安卓的竞争越来越激烈,苹果的优势也越来越小。眼看 Android 8.0 就要来了,下面就让我们扒一扒 Android 8.0 到底有哪些更新? 后台限制机制,从此告别卡顿安卓手机比较坑爹的一个地方就是后台越多应用,就会越卡顿,导致用户需要偶尔清理后台,一定程度..._苹果刷安卓8
文章浏览阅读344次。如果不使用halcon引擎,直接调用lines_gauss虽然内存会飙升,但是属于图片占用的内存还是会立刻被释放,但是如果在halcon引擎中,这个就会释放很慢,如果连续处理图片,你的内存就会“爆炸”!一个6M的图片通过halcon进行加载,大约会消耗200M的内存,如果等待GC回收,而你又在不停的读取图片,你的内存占用,将在短时间内飙升。目前给我的感觉是,如果我封装了一个算子,然后通过halcon引擎调用,然后这个算子需要传入图片参数,这个图片传入引擎后,过很久才会被释放掉。_halcon 读二维码占内存
文章浏览阅读304次。Thinkpad X250笔记本电脑,装的是FreeBSD,进入BIOS修改虚拟化配置(其后可能是误设置了安全开机),保存退出后系统无法启动,显示:secure boot failed ,把自己惊出一身冷汗,因为这台笔记本刚好还没开始做备份.....根据错误提示,到bios里面去找相关配置,在Security里面找到了Secure Boot选项,发现果然被设置为Enabled,将其修改为Disabled ,再开机,终于正常启动了。_安装完系统提示secureboot failure
文章浏览阅读10w+次,点赞93次,收藏352次。1、用strtok函数进行字符串分割原型: char *strtok(char *str, const char *delim);功能:分解字符串为一组字符串。参数说明:str为要分解的字符串,delim为分隔符字符串。返回值:从str开头开始的一个个被分割的串。当没有被分割的串时则返回NULL。其它:strtok函数线程不安全,可以使用strtok_r替代。示例://借助strtok实现split#include <string.h>#include <stdio.h&_c++ 字符串分割