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

数据结构----链表

一丶概念

          链表又称单链表、链式存储结构,用于存储逻辑关系为“一对一”的数据。
          和顺序表不同同,使用链表存储数据,不强制要求数据在内存中集中存储,各个元素可以分散存储在内存中。

二丶特点

         特点:内存不连续,通过指针进行连接
         解决: 长度固定的问题,插入删除麻烦的问题
         逻辑结构:线性结构

         存储结构:链式存储
         操作:增删改查
struct node
{int data;   //数据域:存储数据struct node *next;    //指针域:存储下一个节点的地址
};

三丶单向链表

1.分类

        有头链表:存在一个头节点,头节点数据域无效,指针域有效。
        无头链表:每一个节点的数据域和指针域都有效。

2.有头单向链表

        存在一个头节点,数据域无效,指针域有效

#include <stdio.h>
#include<stdlib.h>
typedef int datatype;
typedef struct node
{int data;//数据域struct node *next;//指针域
} node_t, *node_p;
int main(int argc, char const *argv[])
{node_t A={1,NULL};//输入数据node_t B={2,NULL};node_t C={3,NULL};node_t D={4,NULL};A.next=&B;B.next=&C;C.next=&D;node_p p;//头指针指向头节点node_t S = {'\0',&A};p=H.next;while(p!=NULL){printf("%d ",p->data);p=p->next;}printf("\n");return 0;
}

3.无头单向链表

所有节点的指针域和数据域都有效

#include <stdio.h>
#include <stdlib.h>
typedef char datatype;
typedef struct node
{datatype data;     //数据域用来存数据struct node *next; //指针域用来存下一个节点的地址
} node_t, *node_p;// node_t A; //等同于 struct node A;
// node_p p; //等同于 struct node *p;int main(int argc, char const *argv[])
{//1.定义4个节点node_t A = {'a', NULL};node_t B = {'b', NULL};node_t C = {'c', NULL};node_t D = {'d', NULL};//2.连接四个节点A.next = &B; //连接A和BB.next = &C;C.next = &D;//3.定义一个头指针指向第一个节点node_p p = &A;//4. 通过指针遍历无头单向链表while (p != NULL){printf("%c ", p->data); //打印节点中的数据域 a b c dp = p->next;            //让p指向下一个节点}printf("\n");return 0;
}

链表尾插法练习

写一个有头单向链表,用于保存输入的学生成绩,实现一输入学生成绩就创建一个新的节点,将成绩保存起来。再将该节点链接到链表的尾,直到输入-1结束。

要求:每个链表的节点由动态内存分配得到 , 也就是用malloc。

过程:

1.  malloc申请空间link_node_t大小作为头节点

2.  将新节点放到链表尾部

#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct node
{int data;//数据域存放数据struct node *next;//指针域记录下一个结点地址
} node_t, *node_p;
void ShowLinklist(node_p p)//打印数据
{while(p!=NULL){printf("%d ",p->data);p=p->next;}printf("\n");
}
int main(int argc, char const *argv[])
{int score = 0;// 创建一个头节点node_p p_head = (node_p)malloc(sizeof(node_t));if (NULL == p_head)//容错判断{printf("malloc err");return -1;}//让头指针的指针域置空p_head->next = NULL;//创建一个尾节点node_p p_tail = (node_p)malloc(sizeof(node_t));if (NULL == p_head){printf("p_tail malloc err");return -1;}p_tail = p_head;//让尾节点指向头节点while (1){//循环输入成绩scanf("%d", &score);//输入-1时停止结束循环if (score == -1)break;//新建一个节点p_newnode_p p_new = (node_p)malloc(sizeof(node_t));if (NULL == p_new)//容错判断{printf("p_new malloc err");return -1;}p_new->data = score; //将数据存入新的节点p_new->next = NULL;//让新的节点的指针域置空p_tail->next = p_new;//让尾节点连接到新的节点p_tail=p_new;//更新尾节点}node_p p = p_head->next;ShowLinklist(p);return 0;
}

4.有头单向链表函数操作

插入的思想

1. 先遍历找到要插入节点的前一个节点,假设这个节点为A;A的下一个节点为B;将C插入A与B之间;
2.先让C的指针域指向B;
3.再让A的指针域指向C;

注意:顺序不可以调换

int InsertLinklist(node_p p, int post, int data) // 插入数据
{if (post < 0 || post > StrlenLinklist(p)){printf("Insert eerr");return -1;}for (int i = 0; i < post; i++) // 让p指向插入位置post的前一个节点p = p->next;node_p p_new = (node_p)malloc(sizeof(node_t)); // 创建一个新的节点if (NULL == p_new)                             // 容错判断{printf("p_new malloc err");return -1;}p_new->data = data;    // 让新节点的数据域等于新的数据p_new->next = p->next; // 指针域等于插入位置的地址p->next = p_new;       // 前一个节点的指针域等于新节点的地址return 0;
}

删除的思想

      1.先遍历找到要删除节点的前一个节点,假设为A;

      2、找一个临时指针指向要删除的节点;
      3、  将A的指针域指向删除节点的下一个节点;
      4、  释放被删除节点

int DeleteLinklist(node_p p, int post) // 删除函数
{if (post < 0 || post >= StrlenLinklist(p)){printf("Insert eerr");return -1;}for (int i = 0; i < post; i++) // 让p指向删除位置post的前一个节点p = p->next;                                 node_p p1 = p->next; // 新定义一个结构体指针用来存放删除位置的地址p->next = p1->next;  // 让被删除位置的前一个的指针域等于被删除位置后一个节点的地址free(p1);            // 将被删除指针释放,指针置空p1 = NULL;
}


转置的思想:

(1) 将头节点与当前链表断开,断开前保存下头节点的下一个节点,保证后面链表能找得到,定义一个q保存头节点的下一个节点,断开后前面相当于一个空的链表,后面是一个无头的单向链表
(2) 遍历无头链表的所有节点,将每一个节点当做新节点插入空链表头节点的下一个节点(每次插入的头节点的下一个节点位置)

void ReverseLinkList(node_p p)
{node_p temp = NULL;//临时保存q下一个节点的地址//断开前,保存头节点的下一个节点的地址node_p q = p->next;//指向头节点的下一个节点(相当于无头单向链表的头指针)//1.断头,断开链表p->next = NULL;//2.遍历无头单向链表while (q != NULL){//暂时存放q的下一个节点,防止链表丢失temp = q->next;//头插到有头单向链表头节点的后面q->next = p->next;p->next = q;//将q重新指向之前的无头单向链表,指向此时的第一个节点q=temp;}

完整的单链表操作

#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct node
{int data;          // 数据域存放数据struct node *next; // 指针域记录下一个结点地址
} node_t, *node_p;
node_p CreateEpLinkist() // 创建一个空的有头单向链表
{node_p p = (node_p)malloc(sizeof(node_t)); // 开辟节点空间大小if (NULL == p){printf("CreatEpLinklist err");return NULL;}p->next = NULL; // 初始化头结点return p;
}
int StrlenLinklist(node_p p)//计算单链表长度
{int len = 0;while (p->next != NULL){p = p->next;len++;}return len;
}
int InsertLinklist(node_p p, int post, int data) // 插入数据
{if (post < 0 || post > StrlenLinklist(p)){printf("Insert eerr");return -1;}for (int i = 0; i < post; i++) // 让p指向插入位置post的前一个节点p = p->next;node_p p_new = (node_p)malloc(sizeof(node_t)); // 创建一个新的节点if (NULL == p_new)                             // 容错判断{printf("p_new malloc err");return -1;}p_new->data = data;    // 让新节点的数据域等于新的数据p_new->next = p->next; // 指针域等于插入位置的地址p->next = p_new;       // 前一个节点的指针域等于新节点的地址return 0;
}
int DeleteLinklist(node_p p, int post) // 删除函数
{if (post < 0 || post >= StrlenLinklist(p)){printf("Insert eerr");return -1;}for (int i = 0; i < post; i++) // 让p指向删除位置post的前一个节点p = p->next;                                 node_p p1 = p->next; // 新定义一个结构体指针用来存放删除位置的地址p->next = p1->next;  // 让被删除位置的前一个的指针域等于被删除位置后一个节点的地址free(p1);            // 将被删除指针释放,指针置空p1 = NULL;
}
void ModifyLinklist(node_p p, int post, int data) // 修改函数
{for (int i = 0; i <= post; i++) // 让指针指向要修改的节点位置p = p->next;p->data = data; // 指针域等于新的数据
}
void SearchLinklist(node_p p, int data)//查找数据
{int i = 0;p = p->next;while (p != NULL){if (p->data == data){printf("%d\n", i);//打印第一个相同数据的下标break;}p = p->next;i++;}
}
void ClearLinklist(node_p p)//清空链表
{while(StrlenLinklist(p)!=0){DeleteLinklist(p,0);//删除第一个节点}
}
void ShowLinklist(node_p p)// 打印数据
{while (p->next)// 当指针p的指针域为空时停止循环{p = p->next;printf("%d ", p->data);}printf("\n");
}
void ReverseLinkList(node_p p)//链表转置
{node_p temp = NULL;//临时保存q下一个节点的地址//断开前,保存头节点的下一个节点的地址node_p q = p->next;//指向头节点的下一个节点(相当于无头单向链表的头指针)//1.断头,断开链表p->next = NULL;//2.遍历无头单向链表while (q != NULL){//暂时存放q的下一个节点,防止链表丢失temp = q->next;//头插到有头单向链表头节点的后面q->next = p->next;p->next = q;//将q重新指向之前的无头单向链表,指向此时的第一个节点q=temp;}}
int IsEpLinklist(node_p p)
{return p->next == NULL;
}
int main(int argc, char const *argv[])
{node_p p = CreateEpLinkist(); // 创建一个空的有头单向链表InsertLinklist(p, 0, 1);// 进行插入数据InsertLinklist(p, 1, 2);InsertLinklist(p, 2, 3);InsertLinklist(p, 3, 4);InsertLinklist(p, 4, 5);InsertLinklist(p, 5, 6);ShowLinklist(p);// 打印数据DeleteLinklist(p, 0);// 删除数据ShowLinklist(p);// 打印数据ModifyLinklist(p, 0, 0); // 修改数据ShowLinklist(p);// 打印数据SearchLinklist(p, 2);ReverseLinkList(p);ShowLinklist(p);// 打印数据ClearLinklist(p);if(IsEpLinklist(p))printf("IsEpLinkList\n");free(p);p =NULL;return 0;return 0;
}

5.单向循环链表

四丶总结:

顺序表和单向链表比较:
             (1).顺序表在内存当中连续存储的(数组),但是链表在内存当中是不连续存储的,通过指针将数据链接在一起
            (2).顺序表的长度是固定的,但是链表长度不固定
            (3).顺序表查找方便,但是插入和删除麻烦,链表,插入和删除方便,查找麻烦

相关文章:

数据结构----链表

一丶概念 链表又称单链表、链式存储结构&#xff0c;用于存储逻辑关系为“一对一”的数据。 和顺序表不同同&#xff0c;使用链表存储数据&#xff0c;不强制要求数据在内存中集中存储&#xff0c;各个元素可以分散存储在内存中。 二丶特点 特点&#xff1a;内存不连续…...

【Qt】内置对话框

一.Qt内置对话框 Qt 提供了多种可复⽤的对话框类型&#xff0c;即 Qt 标准对话框。Qt标准对话框全部继承于QDialog类。常⽤标准对话框如下&#xff1a; 二.内置对话框分类 1.消息对话框 QMessageBox 1.1 概念 消息对话框是应⽤程序中最常⽤的界⾯元素。消息对话框主要⽤于为…...

excel常规操作

一、去重 IF(COUNTIF($D$1:D2,D2)>1,"",C2) —— D是去重的列 二、不同列匹配 VLOOKUP(A1,E:F,2,0) vlookup(查找值, 查找区域, 返回查找区域的第几列数据, 精确查找输入参数"0"or"false" 或 模糊查找输入参数"1"or"true…...

uniapp webview子页面向父页面发送数据和触发事件,重点在第3条!!!

1、众所周知H5中iframe可以用过postmessage进行&#xff0c;从H5子页面向H5父页面进行通信。方法如下&#xff1a; // 子页面 window.parent.postMessage({ data: 你的消息 }, *);// 父页面 <iframe src"xxxxxxxxxxx"></iframe> window.addEventListene…...

【STM32实物】基于STM32+ESP32+手机APP设计的智能宠物喂食系统实物源码原理图PCB设计文档演示视频——(文末工程资料下载)

基于STM32+ESP32+手机APP设计的智能宠物喂食系统 演示视频 基于STM32+ESP32+手机APP设计的智能宠物喂食系统 摘 要 近年来,宠物在人们生活中越来越不可或缺,给人们带来的陪伴和快乐。然而,由于种种原因,主人不能时刻照顾宠物的饮食,所以宠物喂食装置变得尤为重要。传…...

EMC学习笔记5——辐射骚扰发射

辐射骚扰发射是基本的实验项目&#xff0c;目的是检验设备在工作时有没有产生意外的过强电磁辐射。 例如发电机&#xff0c;在工作时会产生意外的电磁波辐射&#xff0c;因为电子设备中隐藏了一些天线&#xff0c;这些隐藏的天线在辐射电磁波。 一、两种基本的天线结构 如前面…...

深入理解浏览器解析机制和XSS向量编码

基础部分 1.<a href"%6a%61%76%61%73%63%72%69%70%74:%61%6c%65%72%74%28%31%29">aaa</a> <a>标签可以识别&#xff0c;但是解析不了&#xff0c; 是在协议的编码顺序上&#xff0c;先认协议 URL 编码 "javascript:alert(1)" 2.<a …...

winform 大头针实现方法——把窗口钉在最上层

平时我们再使用成熟的软件的时候&#xff0c;会发现有个大头针的功能挺不错的。就是点一下大头针&#xff0c;窗口就会钉住&#xff0c;一直保持在最上面一层&#xff0c;这样可以一边设置参数&#xff0c;一边观察这个窗口里面的变化&#xff0c;比较方便。下面我就来简单实现…...

中间件|day1.Redis

Redis 定义 Redis 是一个开源&#xff08;BSD许可&#xff09;的&#xff0c;内存中的数据结构存储系统&#xff0c;它可以用作数据库、缓存和消息中间件。 它支持多种类型的数据结构&#xff0c;如 字符串&#xff08;strings&#xff09;&#xff0c; 散列&#xff08;hash…...

PMP到底有什么用?

PMP 就是项目管理证书&#xff0c;全称是项目管理专业人士资格认证&#xff0c;对于一个在项目管理岗位混迹五年的老油条来说&#xff0c;PMP 证书是敲开项目管理岗位的第一块砖&#xff0c;每年考 PMP 的人都很多&#xff0c;要是 PMP 证书没有价值&#xff0c;还会有那么多人…...

apache huidi 时间旅行Time Travel)机制

Apache Hudi(Hadoop Upserts Deletes and Incrementals)是一个数据管理框架,它帮助你高效地管理存储在分布式存储系统(如HDFS或云存储)上的大型数据集。其一个关键特性是“时间旅行”,这允许你在特定时间点查询数据的历史版本。 什么是Apache Hudi中的时间旅行? Apach…...

Python 数据可视化,怎么选出合适数据的图表

数据可视化最佳实践 1. 引言&#xff1a;为什么数据可视化最佳实践很重要 数据可视化是数据分析和决策过程中不可或缺的一部分。通过有效的可视化&#xff0c;复杂的数据可以转化为易于理解的信息&#xff0c;从而帮助观众快速做出正确的判断。然而&#xff0c;糟糕的可视化可…...

c# 元组

文章目录 元组的定义元组的使用示例使用场景创建一个列表 在 C# 中&#xff0c;元组&#xff08;Tuple&#xff09;是一种用于存储多个值的数据结构&#xff0c;它可以方便地将不同类型的多个值打包在一起。元组在 C# 7.0 及更高版本中得到了增强&#xff0c;允许更方便地创建和…...

自定义注解

目录 使用注解定义分布式锁 Aop例子 retention 表示在什么时候可以用&#xff0c;runtime表示在运行期可以用 target表示可以用在哪些上面 inherited表示可以被继承 切点和切面类 重点是 pjp.proceed(args) 这个就是执行目标方法&#xff0c;下面的这一段没啥意思 也可…...

报错:Can‘t find Python executable “python“, you can set the PYTHON env variable

将项目导入vscode,执行npm install命令后&#xff0c;报错了&#xff0c;报错的信息是node-sass安装失败&#xff0c;同时提示需要python环境的错误信息&#xff0c;这是因为安装node-sass失败了&#xff0c;而node-sass依赖于Python环境。 1.报错&#xff1a;Cant find Python…...

C++中的错误处理机制

异常的引出 如过你写过不少的程序的话&#xff0c;相信你应该遇到过一些程序所不能处理的错误而导致程序崩溃的问题吧&#xff0c;比如说&#xff1a;操作野指针&#xff0c;访问空指针&#xff0c;函数的除零错误&#xff0c;数组越界&#xff0c;在栈上开辟空间过大导致栈溢…...

【杂乱笔记】图论

图论 文章目录 图论图的存储与深度、广度遍历基础定义代码实现其他补充 并查集基础定义代码实现 最小生成树基础定义代码实现**Kruskal算法**prim算法 拓扑排序基础定义思路分析代码实现 最短路径基础定义代码实现Dijkstra算法Bellman-Ford算法Floyd算法 图的存储与深度、广度遍…...

pdf文件密码忘记,有办法可以打开pdf文件吗?

为确保PDF文件的重要信息不轻易外泄&#xff0c;我们一般会给pdf文件设置打开密码&#xff0c;确保pdf文件的隐私与安全&#xff0c;但随着时间的推移&#xff0c;让我们遗忘了原本设置的密码&#xff0c;这时我们该怎么办呢&#xff1f; 当大家遇到这种情况时&#xff0c;可能…...

git , nvm 快速下载安装包链接

为了记录地址 &#xff0c; 都是复制大神的 &#xff0c; 可以用&#xff01;&#xff01;&#xff01; nvm 包管理工具 和 git安装包 1. nvm https://www.jianshu.com/p/13c0b3ca7c71 https://blog.csdn.net/i_for/article/details/135060019 https://www.cnblogs.com/Fooo/p…...

TongHttpServer安装部署

TongHttpServer安装部署 毫无背景不是你堕落的理由&#xff0c;而更应该是你前进的动力。你该花时间思考&#xff0c;如何打好一副烂牌&#xff1b;而不是抱怨命运&#xff0c;或者干脆撕牌。 部署环境 TongHttpServer V6.0是一款轻量级负载均衡软件&#xff0c;支持 0SI 四层…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南

精益数据分析&#xff08;97/126&#xff09;&#xff1a;邮件营销与用户参与度的关键指标优化指南 在数字化营销时代&#xff0c;邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天&#xff0c;我们将深入解析邮件打开率、网站可用性、页面参与时…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...