当前位置: 首页 > news >正文

综合服务门户网站建设/百度反馈中心

综合服务门户网站建设,百度反馈中心,带网站的图片素材,wordpress cron原理当我们学完顺序表的时候,我们发现了好多问题如下: 中间/头部的插入删除,时间复杂度为O(N)增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当…

当我们学完顺序表的时候,我们发现了好多问题如下:

  1. 中间/头部的插入删除,时间复杂度为O(N)
  2. 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。
  3. 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到200,我们
    再继续插入了5个数据,后面没有数据插入了,那么就浪费了95个数据空间。

如何解决上面的问题呢??今天就跟着小张一起学习单链表吧!!

链表的概念及结构

概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
在这里插入图片描述
在这里插入图片描述

注意:1.链式结构在逻辑上是连续的,但是在物理上不一定连续
2.结点一般都是在堆上申请出来的(malloc)
3.从堆上申请的空间,是按照一定策略来分配的,两次申请的空间可能连续,也可能不连续

单链表

在这里插入图片描述

单链表的接口实现

void  printdata(info* phead)//打印单链表
info* BuySListNode(int x)//创建新结点
void pushback(info** pphead, int x)//尾插
void pushFront(info** pphead, int x)//头插
void popFront(info** pphead)//头删
void popBack(info** pphead)//尾删
info* SListFind(info* pphead, int x)//单链表查找
SeqListInsert(info** pphead,info* pos,int x)//pos指针指向结点的地址的前一个位置前插插入
void SeqListErase(info** pphead, info* pos)//删除pos位置的值
void SListInsertAfter(info* pos, int x)//单链表在pos位置之后插入x
void SListEraseAfter(info* pos)//删除pos的后一个位置

0.结构体定义单个结点

typedef struct info {int data;//data存数据struct info* next;//info*next存放下一个结点的地址}info;

1.创建新结点

info* BuySListNode(int x)
{info* newnode = (info*)malloc(sizeof(info));//空间申请assert(newnode);//断言,新结点是否申请到了newnode->data = x;//数据赋值newnode->next = NULL;//指向的地址赋值return newnode;//将申请好的空间首地址返回回去}

在这里插入图片描述

断言,如果没申请到空间,mallo返回空指针,断言newnode就会报错

为什么要用二级指针传参在尾插,头插,尾删,头删中

分析:在这里插入图片描述

2.尾插

void pushback(info** pphead, int x)//尾插
{info* newnode = BuySListNode(x);//将创建好的新结点的地址保存在newnode变量中if (*pphead == NULL)//链表无结点{*pphead = newnode;// 将创建好的头节点的地址给给*pphead,作为新头节点的地址}else{info* tail = *pphead;//定义一个指针,先指向头结点的地址while (tail->next != NULL)//循环遍历找尾结点{tail = tail->next;//指针指向下一个结点}tail->next = newnode;//找到尾结点,将尾结点的next存放新接结点的地址}}

分析:
在这里插入图片描述

文字解释:大体上就是直接将最后一个结点的next存入新结点的地址,然后将新结点的next存入空(NULL)。
申请新的结点,如果pphead为空地址,链表还没有结点,将新结点的地址传给pphead,新结点的地址就是头结点的地址,如果该链表中已经存在结点,定义一个指针先存放头节点的地址,然后遍历整个链表,循环寻找哪个结点的next为NULL,不是的话就将tail指向下一个结点,对应操作为tail = tail->next;结点的next为NULL,那个结点就是尾结点,找到尾结点之后将尾结点的next存入要插入新结点的地址,新结点的next已经在 BuySListNode(int x)置为空地址

3.打印链表

void  printdata(info* phead)
{info* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL");}

分析在这里插入图片描述
文字描述:定义一个指针cur指向头结点,使用这个指针循环遍历,这个指针指向的不为空的话就继续循环,在循环中打印cur->data,对应的操作是printf(“%d->”, cur->data);打印%d后面加->是为了方便观察;然后将cur指针移动到下一个结点的位置对应操作是cur = cur->next;,继续打印。

4.头插

void pushFront(info** pphead, int x)//头插
{info* newnode = BuySListNode(x);//创建新结点,将新结点的地址存放在newnode指针变量中newnode->next = *pphead;//新结点的下一个结点应该为旧头结点的地址*pphead = newnode;//新头结点的地址更新为newnode指针所指向的地址}

分析
在这里插入图片描述

文字描述:将创建的新结点的地址存放在newnode指针变量中,pphead为原先头结点的地址,头插一个新结点后,应该将新结点的next存放原先头结点的地址,对应操作为newnode->next = pphead;然后保存在pphead应该为新的头结点的地址,也就是newnode所指向的地址,对应操作为pphead = newnode;

5.头删

void popFront(info** pphead)
{info* p =(*pphead)->next;//定义指针存放头结点的下一个结点的地址free(*pphead);//释放头结点*pphead = p;//头结点地址更新为原先头结点的下一个结点的地址
}

分析:
在这里插入图片描述

6.尾删

void popBack(info** pphead)
{info* tailprev = NULL;info* tail = *pphead;if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{while (tail->next != NULL){tailprev = tail;tail = tail->next;}free(tail);tailprev->next = NULL;}
}

分析:在这里插入图片描述

7.修改

info* SListFind(info* pphead, int x)
{info* cur = pphead;//cur指针保存pphead指针接收的地址while (cur){if (cur->data == x){  //cur->data==y可以将查找出来的值修改为y,不用单独写修改函数,传参也要多一个yreturn cur;//找到的话返回该结点的地址}cur = cur->next;//cur指向下一个结点的地址}return NULL;}

分析:
在这里插入图片描述

8.pos指针指向结点的地址的前一个位置前插插入(随便插)

SeqListInsert(info** pphead,info* pos,int x)//pos指针指向结点的地址的前一个位置前插插入
{assert(pphead);//头结点地址不能为空if (pos == *pphead)//pos指针指向结点的地址为头结点,相当于头插{pushFront(*pphead, x);//调用头插函数}else{info* prev = *pphead;//定义一个prev指针,先让他保存头结点的地址while (prev->next != pos)//循环遍历找pos指针指向结点的前一个结点{prev = prev->next;}info* newnode=BuySListNode(x);//申请新结点,将申请好的结点地址存放在newnode指针变量里面prev->next = newnode;//使之前pos指针指向的结点的前一个结点的next存入插入新结点的地址,newnode->next = pos;//然后新结点的next存入pos指向结点的地址
}
}

分析:在这里插入图片描述

9.删除pos位置的值

void SeqListErase(info** pphead, info* pos)
{if (pos == *pphead)//删除结点是否为头结点{popFront(*pphead);//头删}else{info* prev = *pphead;//定义一个prev指针,先让他存放头结点的地址while (prev->next != pos)//循环遍历寻找哪个结点的next存放的是pos指针指向的结点的地址{prev = prev->next;//prev指针指向下一个结点}prev->next = pos->next;//pos指针指向的结点的上一个结点的next存放pos指针指向的结点的下一个结点的地址free(pos);//释放掉pos指针指向的那块空间}
}

分析:在这里插入图片描述

10.单链表在pos位置之后插入x

void SListInsertAfter(info* pos, int x)
{assert(pos);//防止在空指针info* newnode=BuySListNode(x);//申请新结点newnode->next = pos->next;pos->next = newnode;}

分析:在这里插入图片描述
那么1,2是否可以反过来

	pos->next = newnode;newnode->next = pos->next;

不行,d3的地址会丢失
出现下图的情况:在这里插入图片描述

11.删除pos的后一个位置

void SListEraseAfter(info* pos)
{assert(pos);//防止pos指向空地址if (pos->next == NULL)//如果pos指针指向最后一个结点return;//直接退出,不往下执行info* del = pos->next;//保存pos指针指向结点的下一个结点的地址pos->next = del->next;//更新pos指针指向的结点的下一个结点为pos指针指向结点下下一个结点的地址free(del);//释放掉保存pos指针指向结点的下一个结点的地址的空间。}

分析:在这里插入图片描述

12.完整源码

#include<stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef struct info {int data;struct info* next;}info;
void  printdata(info* phead)
{info* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL");}
info* BuySListNode(int x)
{info* newnode = (info*)malloc(sizeof(info));assert(newnode);newnode->data = x;newnode->next = NULL;return newnode;}
void pushback(info** pphead, int x)//尾插
{info* newnode = BuySListNode(x);if (*pphead == NULL){*pphead = newnode;}else{info* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}}
void pushFront(info** pphead, int x)//头插
{info* newnode = BuySListNode(x);newnode->next = *pphead;*pphead = newnode;}
void popFront(info** pphead)//头删
{info* p =(*pphead)->next;free(*pphead);*pphead = p;}
void popBack(info** pphead)//尾删
{info* tailprev = NULL;info* tail = *pphead;if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{while (tail->next != NULL){tailprev = tail;tail = tail->next;}free(tail);tailprev->next = NULL;}
}
info* SListFind(info* pphead, int x)//查找
{info* cur = pphead;while (cur){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}
SeqListInsert(info** pphead,info* pos,int x)//pos指针指向结点的地址的前一个位置前插插入
{assert(*pphead);if (pos == *pphead){pushFront(*pphead, x);}else{info* prev = *pphead;while (prev->next != pos){prev = prev->next;}info* newnode=BuySListNode(x);prev->next = newnode;newnode->next = pos;}}
void SeqListErase(info** pphead, info* pos)
{if (pos == *pphead){popFront(*pphead);}else{info* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);}}
void SListInsertAfter(info* pos, int x)
{assert(pos);info* newnode=BuySListNode(x);newnode->next = pos->next;pos->next = newnode;
}
void SListEraseAfter(info* pos)
{assert(pos);if (pos->next == NULL)return;info* del = pos->next;pos->next = del->next;free(del);}int main()
{info* n1 = (info*)malloc(sizeof(info));info* n2 = (info*)malloc(sizeof(info));info* n3 = (info*)malloc(sizeof(info));info* n4 = (info*)malloc(sizeof(info));assert(n1 && n2 && n3 && n4);n1->data = 1;n2->data = 2;n3->data = 3;n4->data = 4;n1->next = n2;n2->next = n3;n3->next = n4;n4->next = NULL;printf("原链表:");printdata(n1);printf("\n");printf("尾插:");pushback(&n1, 5);pushback(&n1, 6);pushback(&n1, 7);pushback(&n1, 8);printdata(n1);printf("\n");printf("头插:");pushFront(&n1, 10);pushFront(&n1, 20);printdata(n1);printf("\n");printf("头删:");popFront(&n1);printdata(n1);printf("\n");printf("尾删:");popBack(&n1);popBack(&n1);printdata(n1);printf("\n");printf("查找到并修改:");SListFind(n1, 3)->data = 80;printdata(n1);printf("\n");printf("pos指针指向结点的地址的前一个位置前插插入:");SeqListInsert(&n1, n4, 100);printdata(n1);printf("\n");printf("删除pos位置的值:");SeqListErase(&n1, n4);printdata(n1);printf("\n");printf("单链表在pos位置之后插入x:");SListInsertAfter(n2, 1000);printdata(n1);printf("\n");printf("删除pos的后一个位置:");SListEraseAfter(n1);printdata(n1);printf("\n");}

13.代码编译运行

在这里插入图片描述

相关文章:

【数据结构】单链表详解

当我们学完顺序表的时候&#xff0c;我们发现了好多问题如下&#xff1a; 中间/头部的插入删除&#xff0c;时间复杂度为O(N)增容需要申请新空间&#xff0c;拷贝数据&#xff0c;释放旧空间。会有不小的消耗。增容一般是呈2倍的增长&#xff0c;势必会有一定的空间浪费。例如当…...

dql的执行顺序

在 SQL 查询语言中&#xff0c;DQL&#xff08;Data Query Language&#xff09;是用于从数据库中检索数据的部分。SQL 查询的执行顺序通常按照以下步骤进行&#xff1a; FROM 子句&#xff1a;查询首先确定要从哪些表中检索数据。在 FROM 子句中列出的表格被称为源表&#xff…...

java的动态代理如何实现

一. JdkProxy jdkproxy动态代理必须基于接口(interface)实现 接口UserInterface.java public interface UserService {String getUserName(String userCde); }原始实现类&#xff1a;UseServiceImpl.java public class UserServiceImpl implements UserSerice {Overridepub…...

Java--日志管理

日志管理 作用&#xff1a; 设置日志级别&#xff0c;决定什么日志信息应该被输出、什么日志信息应该被忽略。 基本工具 见的日志管理用具有:JDK logging&#xff08;配置文件&#xff1a;logging.properties&#xff09; 和log4j(配置文件&#xff1a;log4j.properties) 。…...

Pygame中Sprite类的使用2

4 让僵尸动起来 让僵尸能够动起来&#xff0c;也就是让僵尸从屏幕右边走到屏幕左边&#xff0c;此时只需要使用while循环&#xff0c;改变僵尸图片的x轴坐标即可&#xff0c;代码如下所示。 while True:screen.fill((255,255,255))z1.rect.x - 5z1.draw(screen)z1.update()if…...

排队时延与流量强度

流量强度 设R为传输速率&#xff0c;a表示分组到达队列的平均速率&#xff0c;假定所有分组都是由L比特组成的&#xff0c;则比特到达队列的平均速率为La。比率 L a R \frac{La}{R} RLa​被成为流量强度。 根据流量强度的定义&#xff0c;我们可以很直观的得出以下结论&#x…...

mysql:如何设计互相关注业务场景

目录 业务场景 业务问题&#xff1a; 数据库表设计&#xff1a; like&#xff08;关注表&#xff09;&#xff1a; friend&#xff08;朋友表&#xff09; 并发场景下&#xff0c;SQL语句执行逻辑 比较 A 和 B 的大小&#xff0c;如果 A执行下面的逻辑&#xff1a;<&…...

AI伦理:科技发展中的人性之声

文章目录 AI伦理的关键问题1. 隐私问题2. 公平性问题3. 自主性问题4. 伦理教育问题 隐私问题的拓展分析数据收集和滥用隐私泄露和数据安全 公平性问题的拓展分析历史偏见和算法模型可解释性 自主性问题的拓展分析自主AI决策伦理框架 伦理教育的拓展分析伦理培训 结论 &#x1f…...

Direct3D光照

光照的组成 环境光&#xff1a;这种类型的光经其他表面反射到达物体表面&#xff0c;并照亮整个场景&#xff0c;要想以较低代价粗略模拟这类反射光&#xff0c;环境光是一个很好的选择 漫射光&#xff1a;这种类型光沿着特定的方向传播。当它到达某一表面时&#xff0c;将沿…...

编程语言排行榜

以下是2023年的编程语言排行榜&#xff08;按照流行度排序&#xff09;&#xff1a; Python&#xff1a;Python一直以来都是非常受欢迎的编程语言&#xff0c;它简洁、易读且功能强大。在数据科学、机器学习、人工智能等领域有广泛应用。 JavaScript&#xff1a;作为前端开发…...

基于语雀编辑器的在线文档编辑与查看

概述 语雀是一个非常优秀的文档和知识库工具&#xff0c;其编辑器更是非常好用&#xff0c;虽无开源版本&#xff0c;但有编译好的可以使用。本文基于语雀编辑器实现在线文档的编辑与文章的预览。 实现效果 实现 参考语雀编辑器官方文档&#xff0c;其实现需要引入以下文件&…...

开箱报告,Simulink Toolbox库模块使用指南(六)——S-Fuction模块(TLC)

文章目录 前言 Target Language Compiler&#xff08;TLC&#xff09; C MEX S-Function模块 编写TLC文件 生成代码 Tips 分析和应用 总结 前言 见《开箱报告&#xff0c;Simulink Toolbox库模块使用指南&#xff08;一&#xff09;——powergui模块》 见《开箱报告&am…...

Kafka详解

目录 一、消息系统 1、点对点的消息系统 2、发布-订阅消息系统 二、Apache Kafka 简介 三、Apache Kafka基本原理 3.1 分布式和分区&#xff08;distributed、partitioned&#xff09; 3.2 副本&#xff08;replicated &#xff09; 3.3 整体数据流程 3.4 消息传送机制…...

rabbitmq+springboot实现幂等性操作

文章目录 1.场景描述 1.1 场景11.2 场景2 2.原理3.实战开发 3.1 建表3.2 集成mybatis-plus3.3 集成RabbitMq 3.3.1 安装mq3.3.2 springBoot集成mq 3.4 具体实现 3.4.1 mq配置类3.4.2 生产者3.4.3 消费者 1.场景描述 消息中间件是分布式系统常用的组件&#xff0c;无论是异…...

ubuntu server 更改时区:上海

1. 打开终端&#xff0c;在命令行中以超级用户或具有sudo权限的用户身份运行以下命令&#xff1a; sudo dpkg-reconfigure tzdata 这会打开一个对话框&#xff0c;用于选择系统的时区设置。 2. 在对话框中&#xff0c;使用上下箭头键在地区列表中选择"Asia"&#x…...

java 整合 swagger-ui 步骤

1.在xml 中添加Swagger 相关依赖 <!-- springfox-swagger2 --><dependency><groupId>io.springfox</groupId><artifactId>springfox-swagger2</artifactId><version>2.9.2</version></dependency><!-- springfox-swa…...

介绍两款生成神经网络架构示意图的工具:NN-SVG和PlotNeuralNet

对于神经网络架构的可视化是很有意义的&#xff0c;可以在很大程度上帮助到我们清晰直观地了解到整个架构&#xff0c;我们在前面的 PyTorch的ONNX结合MNIST手写数字数据集的应用(.pth和.onnx的转换与onnx运行时) 有介绍&#xff0c;可以将模型架构文件(常见的格式都可以)在线上…...

iOS IdiotAVplayer实现视频分片缓存

文章目录 IdiotAVplayer 实现视频切片缓存一 iOS视频边下边播原理一 分片下载的实现1 分片下载的思路2 IdiotAVplayer 实现架构 三 IdiotAVplayer 代码解析IdiotPlayerIdiotResourceLoaderIdiotDownLoader IdiotAVplayer 实现视频切片缓存 一 iOS视频边下边播原理 初始化AVUR…...

SpringBootWeb请求-响应

HTTP请求 前后端分离 在这种模式下&#xff0c;前端技术人员基于"接口文档"&#xff0c;开发前端程序&#xff1b;后端技术人员也基于"接口文档"&#xff0c;开发后端程序。 由于前后端分离&#xff0c;对我们后端技术人员来讲&#xff0c;在开发过程中&a…...

List集合详解

目录 1、集合是什么&#xff1f; 1.1、集合与集合之间的关系 2、List集合的特点 3、遍历集合的三种方式 3.1、foreach(增强佛如循环遍历) 3.2、for循环遍历 3.3、迭代器遍历 4、LinkedList和ArrayList的区别 4.1、为什么ArrayList查询会快一些&#xff1f; 4.2、为什么LinkedLi…...

投稿指南【NO.12_8】【极易投中】核心期刊投稿(组合机床与自动化加工技术)

近期有不少同学咨询投稿期刊的问题&#xff0c;大部分院校的研究生都有发学术论文的要求&#xff0c;少部分要求高的甚至需要SCI或者多篇核心期刊论文才可以毕业&#xff0c;但是核心期刊要求论文质量高且审稿周期长&#xff0c;所以本博客梳理一些计算机特别是人工智能相关的期…...

解决git无法上传大文件(50MB)

解决方法 使用LFS解决GitHub无法上传大于50MB的文件 LFS简介 Git LFS&#xff08;Large File Storage&#xff09;是 Git 的一个扩展&#xff0c;用于管理大型文件&#xff0c;如二进制文件、图像、音频和视频文件等。它的主要目的是解决 Git 对大型二进制文件的版本控制和存…...

用递归实现字符串逆序(不使用库函数)

文章目录 前言一、题目要求二、解题步骤1.大概框架2.如何反向排列&#xff1f;3.模拟实现strlen4.实现反向排列5.递归实现反向排列 总结 前言 嗨&#xff0c;亲爱的读者们&#xff01;我是艾老虎尤&#xff0c;今天&#xff0c;我们将探索一个题目&#xff0c;这个题目对新手非…...

初学python(一)

一、python的背景和前景 二、 python的一些小事项 1、在Java、C中&#xff0c;2 / 3 0&#xff0c;也就是整数 / 整数 整数&#xff0c;会把小数部分舍掉。而在python中2 / 3 0.66666.... 不会舍掉小数部分。 在编程语言中&#xff0c;浮点数遵循IEEE754标准&#xff0c;不…...

Excel VSTO开发8 -相关控件

版权声明&#xff1a;本文为博主原创文章&#xff0c;转载请在显著位置标明本文出处以及作者网名&#xff0c;未经作者允许不得用于商业目的。 8 相关控件 在VSTO开发中&#xff0c;Ribbon&#xff08;或称为Ribbon UI&#xff09;是指Office应用程序中的那个位于顶部的带有选…...

华为数据管理——《华为数据之道》

数据分析与开发 元数据是描述数据的数据&#xff0c;用于打破业务和IT之间的语言障碍&#xff0c;帮助业务更好地理解数据。 元数据是数据中台的重要的基础设施&#xff0c;元数据治理贯彻数据产生、加工、消费的全过程&#xff0c;沉淀了数据资产&#xff0c;搭建了技术和业务…...

Flink CDC 菜鸟教程 -环境篇

本教程将介绍如何使用 Flink CDC 来实现这个需求, 在 Flink SQL CLI 中进行,只涉及 SQL,无需一行 Java/Scala 代码,也无需安装 IDE。 系统的整体架构如下图所示: 环境篇 1、 准备一台Linux 2、准备教程所需要的组件 下载 flink-1.13.2 并将其解压至目录 flink-1.13.2 …...

【线上问题】linux部署docker应用docker-compose启动报端口占用问题(感觉上没有被占用)

目录 一、问题说明二、排查过程 一、问题说明 1.linux服务器使用的不是root用户权限 2.docker应用服务没有关闭的情况下&#xff0c;做了些重装docker&#xff0c;重启docker等操作 3.docker-compose up -d然后docker logs查看日志报端口被占用 4.netstat -ntpl | grep 端口 也…...

解决虚拟机克隆后IP和命名冲突问题

目录 解决IP冲突问题 解决命名冲突 解决IP冲突问题 克隆后的虚拟机和硬件地址和ip和我们原虚拟机的相同&#xff0c;我们需要重新生成硬件地址和定义ip&#xff0c;步骤如下&#xff1a; &#xff08;1&#xff09;进入 /etc/sysconfig/network-scripts/ifcfg-ens33 配置文件…...

分享一个python基于数据可视化的智慧社区服务平台源码

&#x1f495;&#x1f495;作者&#xff1a;计算机源码社 &#x1f495;&#x1f495;个人简介&#xff1a;本人七年开发经验&#xff0c;擅长Java、Python、PHP、.NET、Node.js、微信小程序、爬虫、大数据等&#xff0c;大家有这一块的问题可以一起交流&#xff01; &#x1…...