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

数据结构-串

news 来源：原创 2025/5/14 1:58:51

串的实现

在C语言中所使用的字符串就是串的数据类型的一种。

串的存储结构

定长顺序存储表示

类似于线性表的顺序存储结构，用一组连续的存储单元存储串值的字符序列。

#define MAXLEN 255 //预定义最大串长为255

typedef struct SString
{char ch[MAXLEN]; //每个分量存储一个字符int length;   //串的实际长度
}SString;

串的实际长度只能小于或等于MAXLEN，超过预定义长度的串值会被社区，称为截断。串长的表示由两种方法：一种是通过length存放串的长度；二是在串值后面加一个不计入串长的结束标记字符'\0'（C语言种字符串就是采用这种方法），此时串就根据'\0'来算长度。

堆分配存储表示

堆分配存储表示仍然以一组地址连续的存储单元存放串，但存储空间是动态分配获得。

typedef struct{char *ch;   //按串长分配存储区，ch指向串的首地址int length; //串的长度
}HString;

在C语言中，用malloc()为每个新产生的串分配一块串长所需的存储空间。

块链存储表示

类似于链式存储结构，也可采用链式方式存储串值。

//串的结点
typedef struct StringNode{char ch[4];  //每个结点存多个字符 提高存储密度struct StringNode* next; //指向下一个结点
};

串的基本操作

赋值操作

bool StrAssign(SString *T, char chars[])
{//获取要赋值字符串长度int charsLen = strlen(chars);
// 长度为零表示空字符串，退出循环if (!charsLen)return false;for (size_t i = 0; i < charsLen; i++){T->ch[i] = chars[i];}
T->length = charsLen;return true;
}

复制操作

bool StrCopy(SString *T, const SString S)
{if (!S.length)return false;
for (size_t i = 0; i < S.length; i++){T->ch[i] = S.ch[i];}
// 若要赋值的长度大于原先字符串长度就增长if (S.length > T->length){T->length = S.length;}
return true;
}

判空操作

bool StrEmpty(const SString *S)
{return S->length == 0;
}

比较操作

int StrCompare(const SString S, const SString T)
{int i = 0;while (i != S.length || i != T.length){if (S.ch[i] == T.ch[i]){i++;}else{//若S>T 返回大于0的数 若S<T 返回小于0的数return S.ch[i] - T.ch[i];}}//若结束循环没有比较出结果说明必有一个长度要更长return S.length - T.length;

}

求子串

// 求字串 Sub来返回串S的第pos个字符起长度为len的字串
bool SubString(SString *Sub, SString S, char pos, int len)
{if (S.length == 0)return false;int index = 0;for (size_t i = 0; i < S.length; i++){if (S.ch[i] == pos){// 记录pos字符在S中的起始位置index = i;break;}}// 判断len是否要长于S字符串中pos开始后的长度if (len > S.length - index)return false;for (size_t i = 0; i < len; i++){Sub->ch[i] = S.ch[index];index++;Sub->length++;}return true;
}

串联结

// 用T返回由S1和S2拼接而成的新串，S2拼接在S1前
bool Concat(SString *T, SString S1, SString S2)
{for (size_t i = 0; i < S1.length; i++){T->ch[i] = S1.ch[i];T->length++;}int index = 0;for (size_t i = S1.length; i < S1.length + S2.length; i++){T->ch[i] = S2.ch[index];index++;T->length++;}
return true;
}

定位操作（简单的模式匹配算法）

// 定位操作 若主串S中存在与串T值相同的字串，则返回它在S中第一次出现的位置，否则为0
int Index(SString S, SString T)
{// i和j分别为S和T的计数指针int i = 0, j = 0;if (S.length == 0 || T.length == 0)return i;while (i < S.length && j < T.length){if (S.ch[i] == T.ch[j]){i++;j++;}else{// S的指针跳到下一个字符位置i = i - j + 1;j = 0;}}//若T的指针j扫描到最后一个元素说明都匹配上就返回第一个匹配上的地址if (j == T.length)return i - j;elsereturn 0;
}

串的模式匹配算法—KMP算法

上方的暴力匹配算法中有许多重复的趟数会导致花不必要的时间来跑已经知道的结果，KMP算法就是用于解决这个问题，在KMP算法中，会采用一个next数组来记录子串是在主串第几个元素匹配失败的，下次可以通过next来直接重匹配失败的位置重新开始匹配。在KMP算法中，最主要的就是next数组的计算。

//S和T数组下标由1开始
// KMP算法 若主串S中存在与串T值相同的字串，则返回它在S中第一次出现的位置，否则为0
int Index_KMP(SString S, SString T, int next[])
{// i和j分别为S和T的计数指针int i = 1, j = 1;if (S.length == 0 || T.length == 0)return 0;while (i <= S.length && j <= T.length){if (S.ch[i] == T.ch[j] || j == 0){i++;j++;}else{// KMP算法只需根据计算出的next数组对j的值进行修改j = next[j];}}// 若T的指针j扫描到最后一个元素说明都匹配上就返回第一个匹配上的地址if (j > T.length)return i - T.length;elsereturn 0;
}

// 求next数组
void get_next(SString T, int next[])
{int i = 1, j = 0;next[0] = 0;while (i < T.length){if (j == 0 || T.ch[i] == T.ch[j]){++i;++j;next[i] = j;}elsej = next[j];}
}

数据结构-串

串的实现在C语言中所使用的字符串就是串的数据类型的一种。串的存储结构定长顺序存储表示类似于线性表的顺序存储结构，用一组连续的存储单元存储串值的字符序列。 #define MAXLEN 255 //预定义最大串长为255 typedef struct SString {char ch[MAXLEN]; …...

编程日记 2025/5/14 1:58:51

C#，图论与图算法，有向图（Direct Graph）广度优先遍历（BFS，Breadth First Search）算法与源程序

1 图的广度优先遍历图的广度优先遍历（或搜索）类似于树的广度优先遍历（参见本文的方法2）。这里唯一需要注意的是，与树不同，图可能包含循环，因此我们可能再次来到同一个节点。为了避免多次处理节…...

编程日记 2025/5/7 21:57:00

使用ElasticSearch查询

从一个query body开始 {"query": {"bool": {"disable_coord": true,"must": [{"match": {"enabled": "1"}},{"range": {"effectTime": {"lt": "2017-06-13 13:33:…...

编程日记 2025/5/9 5:11:27

PyCharm+RobotFramework框架实现UDS自动化测试——（一）python-can 库的安装与环境配置

从0开始学习CANoe使用从0开始学习车载测试相信时间的力量星光不负赶路者，时光不负有心人。文章目录 1. 概述2.安装 python-can 库—基于pycharm在对应的工程下3. 在任意盘中安装环境4. 导入 can 模块语法5. 配置 CAN 接口6.CANoe设备连接语法 1. 概述本专栏主…...

编程日记 2025/5/12 22:12:48

C# 值类型和引用类型详解

简介在 C# 中，值类型和引用类型是两个基础的数据类型类别，它们的主要区别在于存储位置和赋值方式。值类型值类型存储的是数据本身，分配在栈 (Stack) 中。当一个值类型变量被赋值给另一个变量时，会复制值。值类型的特点…...

编程日记 2025/5/12 13:38:20

计算机网络 —— 网络编程（TCP）

计算机网络 —— 网络编程（TCP） TCP和UDP的区别TCP (Transmission Control Protocol)UDP (User Datagram Protocol) 前期准备listen （服务端）函数原型返回值使用示例注意事项 accpect （服务端）函数原型返回…...

编程日记 2025/5/13 1:31:54

[Unity Shader] Shader基础光照3：环境光与自发光

在Unity中，光照是场景渲染的关键组成部分。正确使用环境光和自发光能够大大提高场景的真实感和视觉效果。本篇文章将详细介绍Unity中的环境光和自发光的基本概念，以及如何在编辑器和Shader中进行操作和实现。 1. 环境光（Ambient Light） 1.1 环境光的定义环境光是场景中…...

编程日记 2025/5/6 11:31:56

云原生安全风险分析

一、什么是云原生安全云原生安全包含两层含义： 面向云原生环境的安全具有云原生特征的安全 0x1：面向云原生环境的安全面向云原生环境的安全的目标是防护云原生环境中基础设施、编排系统和微服务等系统的安全。这类安全机制不一定具备云原生的特性…...

编程日记 2025/5/11 4:05:16

Redis 安装与配置指南

Redis 安装与配置指南目录安装说明 Linux 安装 Redis 3.0 压缩包上传服务器编译和安装修改配置启动 Redis关闭 Redis 卸载 RedisRedis 集群配置 Master 主库配置启动 Master 节点的 Redis 和 Sentinel客户登录验证Slave 从库配置查看集群数据验证安装说明 Linux 安装 R…...

编程日记 2025/5/13 23:09:50

C语言Day13（c程序设计小红书+pta）

目录 （一）用函数调用实现，把最小的数字放在最前面，把最大的放在最后边 （二）使数字向后移m位 （三）用户自定义数据类型： （四）候选人计票数 &am…...

编程日记 2025/5/10 17:26:13

C++二十三种设计模式之迭代器模式

C二十三种设计模式之迭代器模式一、组成二、特点三、目的四、缺点五、示例代码一、组成抽象聚合类：存储集合元素，声明管理集合元素接口。具体聚合类：实现管理集合元素接口。抽象迭代器类：声明访问和遍历聚合类元素的接口。 …...

编程日记 2025/5/13 13:40:54

【AI游戏】使用强化学习玩 Flappy Bird：从零实现 Q-Learning 算法（附完整资源）

1. 引言 Flappy Bird 是一款经典的休闲游戏，玩家需要控制小鸟穿过管道，避免碰撞。虽然游戏规则简单，但实现一个 AI 来自动玩 Flappy Bird 却是一个有趣的挑战。本文将介绍如何使用 Q-Learning 强化学习算法来训练一个 AI，使其能够…...

编程日记 2025/5/14 5:20:18

VSCode 中的 launch.json 配置使用

VSCode 中的 launch.json 配置使用在 VSCode 中，launch.json 文件用于配置调试设置，特别是用来定义如何启动和调试你的应用。它允许你配置不同的调试模式、运行参数和调试选项。基本结构 launch.json 文件位于 .vscode 文件夹内，可以通过…...

编程日记 2025/5/10 2:31:20

深度学习算法：开启智能时代的钥匙

引言深度学习作为机器学习的一个分支，近年来在图像识别、自然语言处理、语音识别等多个领域取得了革命性的进展。它的核心在于构建多层的神经网络，通过模仿人脑处理信息的方式，让机器能够从数据中学习复杂的模式。深度学习算法的基本原理…...

编程日记 2025/5/14 8:19:20

Clojure语言的并发编程

Clojure语言的并发编程引言在现代软件开发中，并发编程成为了处理多个任务、提高应用效率和响应速度的重要手段。尤其是在多核处理器逐渐成为主流的今天，如何高效利用这些计算资源是每个开发者面临的挑战。Clojure作为一种函数式编程语言，…...

编程日记 2025/5/12 9:19:11

MySQL学习记录1【DQL和DCL】

SQL学习记录该笔记从DQL处开始记录 DQL之前值得注意的点字段 BETWEEN min AND max 可以查询区间[min, max]的数值如果同一个字段需要满足多个OR条件，可以采取字段 IN(数值1, 数值2, 数值3....)LIKE语句字段 LIKE ___%%% 表示模糊匹配，_匹配一个字段…...

编程日记 2025/5/12 22:21:51

EasyExcel的应用

一、简单使用引入依赖： 这里我们可以使用最新的4.0.2版本，也可以选择之前的稳定版本，3.1.x以后的版本API大致相同，新的版本也会向前兼容（3.1.x之前的版本，部分API可能在高版本被废弃）&…...

编程日记 2025/5/13 22:02:29

JS控制对应数据隐藏

首先需要获得到所有的input框，并声明一个空对象来存放，遍历所有的复选框，将他们中选中的放入对象，并设置键值为true，然后执行checkFalseValues(result)函数 function hideItem() {let checkboxes $(.setting_box inp…...

编程日记 2025/5/11 2:30:20

【剑指Offer刷题系列】数据流中的中位数

目录问题描述示例示例 1： 思路解析方法一：使用两个堆（最大堆和最小堆）核心思路详细步骤示例分析优势适用场景代码实现Python 实现（方法一：使用两个堆） 测试代码复杂度分析方法一：使…...

编程日记 2025/5/13 5:23:10

RabbitMQ高级篇之MQ可靠性数据持久化

文章目录消息丢失的原因分析内存存储的缺陷如何确保 RabbitMQ 的消息可靠性？数据持久化的三个方面持久化对性能的影响持久化实验验证性能对比Spring AMQP 默认持久化总结消息丢失的原因分析 RabbitMQ 默认使用内存存储消息，但这种方式带来了两个主要问…...

编程日记 2025/5/12 7:34:11

C 语言奇幻之旅 - 第16篇：C 语言项目实战

目录引言1. 项目规划1.1 需求分析与设计1.1.1 项目目标1.1.2 功能需求1.1.3 技术实现方案 2. 代码实现2.1 模块化编程2.1.1 学生信息模块2.1.2 成绩管理模块 2.2 调试与测试2.2.1 调试2.2.2 测试2.2.4 测试结果 3. 项目总结3.1 代码优化与重构3.1.1 代码优化3.1.2 代码重构 3.…...

编程日记 2025/5/13 17:21:30

[笔记] 使用 Jenkins 实现 CI/CD ：从 GitLab 拉取 Java 项目并部署至 Windows Server

随着软件开发节奏的加快，持续集成（CI）和持续部署（CD）已经成为确保软件质量和加速产品发布的不可或缺的部分。Jenkins作为一款广泛使用的开源自动化服务器，为开发者提供了一个强大的平台来实施这些实践。然而…...

编程日记 2025/5/6 8:02:19

Git最便捷的迁移方式

#当公司要求git需要迁移时，你是不是感觉到束手无策。今天带来给大家最快，最便捷的迁移方式这个命令是用于重命名git仓库中的远程仓库名。在这个命令中，我们将远程仓库的名字从"origin"改为"old-origin"。 git remote …...

编程日记 2025/5/13 2:59:45

【颜色分类--荷兰国旗问题】

问题给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ， 原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。必须在不使用库内置的 sort 函数的情况下…...

编程日记 2025/5/9 14:31:51

错误核查首先使用命令vim ~/.xsession-errors，当里面的报错信息为WARNING **: Could not make bus activated clients aware of XDG_CURRENT_DESKTOPGNOME environment variable:Failed to execute child process “dbus-launch” (No such file or directory)&am…...

编程日记 2025/5/12 6:13:18

KubeVirt 进阶：设置超卖比、CPU/MEM 升降配、在线磁盘扩容

前两篇文章，我们分别介绍 Kubevirt 的安装、基本使用以及将 oVirt 虚拟机迁移到 KubeVirt，我们留了两个ToDo，一个是本地磁盘的动态分配，一个是固定 IP 的需求，本期我们先解决第一个，本地磁盘的动态分配。…...

编程日记 2025/5/6 23:00:21

（回溯法）leetcode39组合总和

第一个2开头，下面的子节点的集合元素均为2,5,3 但是在5开头，下面的子节点集合元素均为5,3 带着这个图的思路确定i和index的传递值 backtracking(i, nums,8,sum);用的是i而不是i1 // ConsoleApplication3.cpp : 此文件包含 "main" 函数。程序…...

编程日记 2025/5/11 21:36:33

【数据结构】二叉搜索树

目录 1. 二叉搜索树的概念 2. 二叉搜索树的性能分析 3.二叉搜索树的实现 3. 1.二叉搜索树的插入 3.2. 二叉搜索树的查找 3.3. 二叉搜索树的删除 3.4. 二叉搜索树的实现代码 4. 二叉搜索树key和key/value两种使用场景 4.1 key搜索场景： 4.2 key/value搜索场…...

编程日记 2025/5/9 5:41:50

高可用虚拟IP-keepalived

个人觉得华为云这个文档十分详细：使用虚拟IP和Keepalived搭建高可用Web集群_弹性云服务器 ECS_华为云应用场景：虚拟IP技术。虚拟IP，就是一个未分配给真实主机的IP，也就是说对外提供数据库服务器的主机除了有一个真实IP外还有一个…...

编程日记 2025/5/9 3:02:28

CSS语言的多线程编程

CSS语言的多线程编程引言在现代Web开发中，CSS（层叠样式表）被广泛用于给网页添加样式。然而，CSS本身是一种声明性语言，在设计上并没有直接支持多线程编程的功能。实际上，CSS的解析和应用是由浏览器的渲染…...

编程日记 2025/5/9 23:15:41

电脑之一键备份系统(One Click Backup System for Computer)

电脑之一键备份系统相信使用电脑的的人都遇到过，电脑系统崩溃，开机蓝屏等原因，这个时候你急着用电脑办公，电脑却给你罢工是多么气人了，其实可以给电脑做一个系统备份。最近每天都有系统蓝屏崩溃，这个实难…...

编程日记 2025/5/13 3:34:42

R语言的正则表达式

R语言中的正则表达式深度解析正则表达式（Regular Expressions，简称Regex）是一种用于描述字符串匹配规则的工具，广泛应用于数据处理、文本分析、数据清洗等多个领域。在R语言中，正则表达式被广泛应用于字符串的处理和…...

编程日记 2025/5/9 15:36:00

解决el-table表格数据量过大导致页面卡顿问题又名《umy-ui---虚拟表格仅渲染可视区域dom的神》

后台管理系统的某个页面需要展示多个列表数据量过多页面渲染dom卡顿经调研发现两个组件 pl-table和umy-ui （也就是u-table） 最终决定使用umy-ui 它是专门基于 Vue 2.0 的桌面端组件库流畅渲染表格万级数据而且他是对element-ui的表格做了二次优化…...

编程日记 2025/5/13 9:18:46

《机器学习》——贝叶斯算法

贝叶斯简介贝叶斯公式，又称贝叶斯定理、贝叶斯法则，最初是用来描述两个事件的条件概率间的关系的公式，后来被人们发现具有很深刻的实际意义和应用价值。该公式的实际内涵是，支持某项属性的事件发生得愈多，则该属性成…...

编程日记 2025/5/10 23:05:30

零基础监控数据可视化 Spring Boot 2.x(Actuator + Prometheus + Grafana手把手) （上）

一、安装Prometheus Releases prometheus/prometheus GitHubhttps://github.com/prometheus/prometheus/releases 或 https://prometheus.io/download/https://prometheus.io/download/ 1. 下载适用于 Windows 的二进制文件： 找到最新版本的发布页面&#xf…...

编程日记 2025/5/13 20:18:59

4.STM32F407ZGT6-独立看门狗

参考： 1.正点原子前言： 看门狗是一个项目或者产品中肯定需要的功能部分，必须会。常见的两种看门狗类型，独立看门狗和窗口看门狗，各有使用的场景。总结记录独立看门狗一些知识点： 1.独立看门狗的概念。&am…...

编程日记 2025/5/11 14:22:02

RHCE实验-nfs及autofs

本次实验的目的：实现服务端的网络文件共享（配置nfs）,且实现客户端的自动挂载（配置autofs） 服务端配置： 关闭防火墙和selinux: 安装软件 [rootlocalhost ~]# yum install nfs-utils -y 创建需要被挂载的目…...

编程日记 2025/5/8 4:29:02

docker代理设置

最近遇到国内镜像无法下载的问题，因此需要配置docker代理来使其能够下载镜像代理设置方法如下： 编辑 /etc/docker/daemon.json 文件： 配置 HTTP 和 HTTPS 代理： {"proxies": {"http-proxy": "http:/…...

编程日记 2025/5/4 12:28:26

死信交换机

什么是死信？什么是死信交换机？ 在MQ中未能成功被消费的消息就被称之为死信，而死信交换机就用于存放死信消息。消息转变成死信消息的原因： 消息被消费者拒绝或者需要重发（nack、reject） nack：消…...

编程日记 2025/4/29 17:47:41

cat命令详解

🏝️专栏：https://blog.csdn.net/2301_81831423/category_12872319.html 🌅主页：猫咪-9527-CSDN博客 “欲穷千里目，更上一层楼。会当凌绝顶，一览众山小。” cat 是 Linux/Unix 中的一个非常常用的命令&…...

编程日记 2025/5/12 4:05:41

路由器的转发表

【4-24】已知路由器R₁ 的转发表如表T-4-24 所示。表T-4-24 习题4-24中路由器R₁的转发表前缀匹配下一跳地址路由器接口 140.5.12.64/26 180.15.2.5 m2 130.5.8/24 190.16.6.2 ml 110.71/16 ----- m0 180.15/16 ----- m2 190.16/16 ----- ml 默认 11…...

编程日记 2025/5/14 2:31:01

腾讯云AI代码助手编程挑战赛-古诗词学习

一、作品介绍在科技与文化深度交融的当下，“腾讯云 AI 代码助手编程挑战赛 - 每日古诗词” 宛如一颗璀璨的新星，闪耀登场。它绝非一场普通的赛事，而是一座连接编程智慧与古典诗词韵味的桥梁。这项挑战赛以独特的视角，将每日古…...

编程日记 2025/5/8 4:30:05

积分系统的设计

1. 目的学习是需要正反馈的，这样学员才能有源源不断的动力去继续学习。为了激励学员，我们需要设定一个学习积分的排行榜系统。优秀的学员给予一定的奖励，比如奖励优惠券。大家互相比拼的，刺激学员持续学习，互相卷起…...

编程日记 2025/5/12 17:58:56

功能篇：spring事务配置

在 Java 应用程序中配置事务管理通常涉及使用 Spring 框架，因为 Spring 提供了强大的事务管理抽象，可以简化事务的配置和管理。Spring 支持两种类型的事务管理：编程式事务管理和声明式事务管理。编程式事务管理编程式事务管理是通过编写代…...

编程日记 2025/5/6 11:09:51

单元测试概述入门

引入什么是测试？测试的阶段划分？ 测试方法有哪些？ 1.什么是单元测试？ 单元测试：就是针对最小的功能单元（方法），编写测试代码对其正确性进行测试。 2.为什么要引入单元测试&#x…...

编程日记 2025/5/5 3:46:52

PySpark学习笔记2-RDD算子，RDD持久化

RDD定义 RDD是弹性分布式数据集，是spark中的最基本的数据抽象，里面的元素可以并行计算 RDD的五大特性 RDD是有分区的，它的分区是数据存储的最小单位 RDD的方法会作用在所有分区上 RDD之间是有依赖关系的 KV型的RDD可以有分区器 RDD的分区会尽…...

编程日记 2025/5/13 14:43:32

windows10下安装Microsoft SQL Server 2016

一、下载安装包网站：MSDN, 我告诉你 - 做一个安静的工具站选择需要的版本，点击详细信息，复制ed2k链接，打开eMule或迅雷，新建下载，粘贴链接，开始下载。下载好的文件是一个.iso镜像文件。二、…...

编程日记 2025/5/9 18:14:45

开关不一定是开关灯用 - 命令模式（Command Pattern）

命令模式（Command Pattern） 命令模式（Command Pattern）命令设计模式命令设计模式结构图命令设计模式涉及的角色 talk is cheap， show you my code总结命令模式（Command Pattern） 命令模式&…...

编程日记 2025/5/11 13:36:35

急速了解什么是GPU服务器

GPU服务器是一种专门配置了高性能图形处理器（GPU）的服务器，旨在提供高性能计算、深度学习、科学计算等多种场景的计算服务。与传统的CPU服务器相比，GPU服务器在处理并行密集型计算任务时具有显著优势。本文将详细介绍GPU服务器的定…...

编程日记 2025/5/5 20:01:28

word论文排版常见问题汇总

word论文排版常见问题汇总常用快捷键： Alt F9 正常模式与域代码模式切换 Ctrl F9 插入域代码 F9 刷新域代码显示，要注意选定后刷新才会有效果 word中在当前列表的基础上修改列表在使用word时，我们会定义一个列表，并将其链接…...

编程日记 2025/5/11 6:18:32