目录
单链表是一种简单的链表表示,也叫做线性链表。用它来表示线性表时,用指针表示结点间的逻辑关系。因此单链表的一个存储结点包含两部分内容:
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;
}
文章浏览阅读2w次,点赞7次,收藏51次。四个步骤1.创建C++ Win32项目动态库dll 2.在Win32项目动态库中添加 外部依赖项 lib头文件和lib库3.导出C接口4.c#调用c++动态库开始你的表演...①创建一个空白的解决方案,在解决方案中添加 Visual C++ , Win32 项目空白解决方案的创建:添加Visual C++ , Win32 项目这......_c#调用lib
文章浏览阅读4.6k次。苹方字体是苹果系统上的黑体,挺好看的。注重颜值的网站都会使用,例如知乎:font-family: -apple-system, BlinkMacSystemFont, Helvetica Neue, PingFang SC, Microsoft YaHei, Source Han Sans SC, Noto Sans CJK SC, W..._ubuntu pingfang
文章浏览阅读159次。表单表单概述表单标签表单域按钮控件demo表单标签表单标签基本语法结构<form action="处理数据程序的url地址“ method=”get|post“ name="表单名称”></form><!--action,当提交表单时,向何处发送表单中的数据,地址可以是相对地址也可以是绝对地址--><!--method将表单中的数据传送给服务器处理,get方式直接显示在url地址中,数据可以被缓存,且长度有限制;而post方式数据隐藏传输,_html表单的处理程序有那些
文章浏览阅读1.2k次。使用说明:开启Google的登陆二步验证(即Google Authenticator服务)后用户登陆时需要输入额外由手机客户端生成的一次性密码。实现Google Authenticator功能需要服务器端和客户端的支持。服务器端负责密钥的生成、验证一次性密码是否正确。客户端记录密钥后生成一次性密码。下载谷歌验证类库文件放到项目合适位置(我这边放在项目Vender下面)https://github.com/PHPGangsta/GoogleAuthenticatorPHP代码示例://引入谷_php otp 验证器
文章浏览阅读4.3k次,点赞5次,收藏11次。matplotlib.plot画图横坐标混乱及间隔处理_matplotlib更改横轴间距
文章浏览阅读2.2k次。①Storage driver 处理各镜像层及容器层的处理细节,实现了多层数据的堆叠,为用户 提供了多层数据合并后的统一视图②所有 Storage driver 都使用可堆叠图像层和写时复制(CoW)策略③docker info 命令可查看当系统上的 storage driver主要用于测试目的,不建议用于生成环境。_docker 保存容器
文章浏览阅读834次,点赞27次,收藏13次。网络拓扑结构是指计算机网络中各组件(如计算机、服务器、打印机、路由器、交换机等设备)及其连接线路在物理布局或逻辑构型上的排列形式。这种布局不仅描述了设备间的实际物理连接方式,也决定了数据在网络中流动的路径和方式。不同的网络拓扑结构影响着网络的性能、可靠性、可扩展性及管理维护的难易程度。_网络拓扑csdn
文章浏览阅读1.8k次,点赞5次,收藏8次。IOS系统Date的坑要创建一个指定时间的new Date对象时,通常的做法是:new Date("2020-09-21 11:11:00")这行代码在 PC 端和安卓端都是正常的,而在 iOS 端则会提示 Invalid Date 无效日期。在IOS年月日中间的横岗许换成斜杠,也就是new Date("2020/09/21 11:11:00")通常为了兼容IOS的这个坑,需要做一些额外的特殊处理,笔者在开发的时候经常会忘了兼容IOS系统。所以就想试着重写Date函数,一劳永逸,避免每次ne_date.prototype 将所有 ios
文章浏览阅读5.3k次。方法一:用PLSQL Developer工具。 1 在PLSQL Developer的sql window里输入select * from test for update; 2 按F8执行 3 打开锁, 再按一下加号. 鼠标点到第一列的列头,使全列成选中状态,然后粘贴,最后commit提交即可。(前提..._excel导入pl/sql
文章浏览阅读83次。Git常用命令速查手册1、初始化仓库git init2、将文件添加到仓库git add 文件名 # 将工作区的某个文件添加到暂存区 git add -u # 添加所有被tracked文件中被修改或删除的文件信息到暂存区,不处理untracked的文件git add -A # 添加所有被tracked文件中被修改或删除的文件信息到暂存区,包括untracked的文件...
文章浏览阅读202次。分享119个ASP.NET源码总有一个是你想要的_千博二手车源码v2023 build 1120
文章浏览阅读1.8k次。版权声明:转载请注明出处 http://blog.csdn.net/irean_lau。目录(?)[+]1、缺省构造函数。2、缺省拷贝构造函数。3、 缺省析构函数。4、缺省赋值运算符。5、缺省取址运算符。6、 缺省取址运算符 const。[cpp] view plain copy_空类默认产生哪些类成员函数