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

串的基本操作--数据结构

目录

一、串的基本概述

二、串的存储结构

2.1定义属性存储结构

串长有两种表示方法: 

1、用一个额外的变量length来存放串的长度;

2、串值后面加一个不计入串长的结束标记字符“\0”,此时的串长为隐含值。 

2.2堆的顺序存储结构  

三、串的基本操作 

3.1在模式串中pos位置查找长度为len的子串

 3.2直接返回模式串的长度

 3.3比较两个字符串之间的大小长短

 3.4朴素模式匹配算法

原文 


一、串的基本概述

  • 串是由零个或多个字符组成的有限序列;
  • 串中任意个连续的字符组成的子序列称为该串的子串,包含子串的串相应地称为主串;
  • 子串在主串中的位置以子串的第一个字符在主串中的位置来表示;
  • 当两个串的长度相等且每个对应位置的字符都相等时,称这两个串是相等的;
  • 一个或多个空格(空格是特殊字符)组成的串称为空格串,其长度为串中空格字符的个数。


二、串的存储结构


存储结构:顺序存储与链式存储。考虑到存储效率和算法的方便性,串多采用顺序存储结构。

类似于线性表的顺序存储结构,用一组地址连续的存储单元存储串值的字符序列。在串的定长顺序存储结构中,为每个串变量分配一个固定长度的存储区,即定长数组。

2.1定义属性存储结构

串长有两种表示方法: 
1、用一个额外的变量length来存放串的长度;
2、串值后面加一个不计入串长的结束标记字符“\0”,此时的串长为隐含值。 

我们这里采用方法1

​#define MAX_SIZE 25  //预定义最大串长为255
typedef struct{char ch[MAX_SIZE];   //每个分盘存储一个字符int length;         //串的实际长度
}SString;

2.2堆的顺序存储结构  

// 堆的顺序存储结构
struct HString{char *ch;     //按串长分配存储区,ch指向串的基地址int length;   //串的长度
} ;

三、串的基本操作 

3.1在模式串中pos位置查找长度为len的子串

//求子串
bool SubString(SString& Sub, SString S, int pos, int len) {if (pos + len - 1 < S.length) {return false;}for (int i = pos; i < pos + len; i++) {Sub.date[i] = S.date[i];}Sub.length = len;
}

 3.2直接返回模式串的长度

//求字符串长度
int length(SString S) {return S.length;
}

 3.3比较两个字符串之间的大小长短

//比较操作
bool compare(SString a,SString b) {for (int i = 0; i < a.length & i < b.length; i++) {if (a.date[i] != b.date[i]) {return a.date[i] - b.date[i];}}return a.length - b.length;
}

 3.4朴素模式匹配算法

//定位操作
int index(SString a, SString b) {SString Sub;int i = 1;int n = length(a), m =length(b);while (i <= n - m + 1) {SubString(Sub, a, i, m);if (compare(Sub, b) == 0)return i;}return 0;
}

原文 

#include<bits/stdc++.h>
using namespace std;
#define MAX_SIZE  23
struct SString {char date[MAX_SIZE];int length;
};
//求子串
bool SubString(SString& Sub, SString S, int pos, int len) {if (pos + len - 1 < S.length) {return false;}for (int i = pos; i < pos + len; i++) {Sub.date[i] = S.date[i];}Sub.length = len;
}
//比较操作
bool compare(SString a,SString b) {for (int i = 0; i < a.length & i < b.length; i++) {if (a.date[i] != b.date[i]) {return a.date[i] - b.date[i];}}return a.length - b.length;
}
//求字符串长度
int length(SString S) {return S.length;
}
//定位操作
int index(SString a, SString b) {SString Sub;int i = 1;int n = length(a), m =length(b);while (i <= n - m + 1) {SubString(Sub, a, i, m);if (compare(Sub, b) == 0)return i;}return 0;
}
//在主串里面查找模式串
int index2(SString a, SString b) {int i, j = 1;while (i <= length(a) && j <= length(b)) {if (a.date[i] == b.date[j]) {i++;j++;}else {i = i - j + 2;j = 1;}}if (j > length(b))return i-length(b);else return 0;
}

相关文章:

串的基本操作--数据结构

目录 一、串的基本概述 二、串的存储结构 2.1定义属性存储结构 串长有两种表示方法: 1、用一个额外的变量length来存放串的长度&#xff1b; 2、串值后面加一个不计入串长的结束标记字符“\0”&#xff0c;此时的串长为隐含值。 2.2堆的顺序存储结构 三、串的基本操…...

Unity 命令行设置运行在指定的显卡上

设置运行在指定的显卡上 -force-device-index...

Dest1ny漏洞库: 美团代付微信小程序系统任意文件读取漏洞

大家好&#xff0c;今天是Dest1ny漏洞库的专题&#xff01;&#xff01; 会时不时发送新的漏洞资讯&#xff01;&#xff01; 大家多多关注&#xff0c;多多点赞&#xff01;&#xff01;&#xff01; 0x01 产品简介 美团代付微信小程序系统是美团点评旗下的一款基于微信小程…...

设计模式:状态模式

状态机有3个要素&#xff1a;状态&#xff0c;事件&#xff0c;动作。 假如一个对象有3个状态:S1、S2、S3。影响状态的事件有3个&#xff1a;E1、E2、E3。每个状态下收到对应事件的时候&#xff0c;对象的动作为AXY。那么该对象的状态机就可以用如下表格来表示。S1收到事件E1的…...

【故障处理】- 执行命令crsctl query crs xxx一直hang

【故障处理】- 执行命令crsctl query crs xxx一直hang 一、概述二、故障处理三、解决方法 一、概述 Oracle RAC环境中&#xff0c;遇到执行crsctl query crs xxx等相关命令不返回任何结果&#xff0c;一直hang在那里。系统下执行命令ps -ef |grep crsctl query crs softwarever…...

Zabbix——监控Nginx

背景 在项目中使用Nginx之后&#xff0c;有时候我们需要知道Nginx具体的工作情况&#xff0c;这时候就需要使用zabbix进行Nginx的相关监控 这边我们有两种方法 使用普通的http请求的方式获取基本信息如果使用了Nginx Plus&#xff0c;就可以通过Nginx Plus的接口获取更多的信…...

开源工具推荐--思维导图、流程图等绘制

1. 前言 在工作中&#xff0c;经常要用到各种不同的工具&#xff0c;随着系统的升级&#xff0c;有些工具也在不断更新升级。这里收集整理一些好用的开源工具推荐&#xff0c;遵循以下一些基本原则&#xff1a;开源免费&#xff0c;商业工具的有效平替&#xff0c;轻量级&…...

【论文笔记】Transformer^2: 自适应大型语言模型

Code repo: https://github.com/SakanaAI/self-adaptive-llms 摘要 自适应大型语言模型&#xff08;LLMs&#xff09;旨在解决传统微调方法的挑战&#xff0c;这些方法通常计算密集且难以处理多样化的任务。本文介绍了Transformer&#xff08;Transformer-Squared&#xff09;…...

FFmpeg源码:av_strlcpy函数分析

一、引言 在C/C编程中经常会用到strcpy这个字符串复制函数。strcpy是C/C中的一个标准函数&#xff0c;可以把含有\0结束符的字符串复制到另一个地址空间。但是strcpy不会检查目标数组dst的大小是否足以容纳源字符串src&#xff0c;如果目标数组太小&#xff0c;将会导致缓冲区…...

Unity Shader学习6:多盏平行光+点光源 ( 逐像素 ) 前向渲染 (Built-In)

0 、分析 在前向渲染中&#xff0c;对于逐像素光源来说&#xff0c;①ForwardBase中只计算一个平行光&#xff0c;其他的光都是在FowardAdd中计算的&#xff0c;所以为了能够渲染出其他的光照&#xff0c;需要在第二个Pass中再来一遍光照计算。 而有所区别的操作是&#xff0…...

docker批量pull/save/load/tag/push镜像shell脚本

目录 注意&#xff1a; 脚本内容 执行效果 注意&#xff1a; 以下脚本为shell脚本通过docker/nerdctl进行镜像独立打包镜像的相关操作脚本内仓库信息和镜像存取路径需自行更改需自行创建images.txt并填写值&#xff0c;并且与脚本位于同级目录下 [rootmaster01 sulibao]# l…...

五十天精通硬件设计第32天-S参数

系列文章传送门 50天精通硬件设计第一天-总体规划-CSDN博客 目录 1. S参数基础 2. S参数在信号完整性中的作用 3. 单端 vs. 差分S参数 4. S参数的关键特性 5. S参数的获取与使用 6. S参数分析中的常见问题 7. 实际案例:PCIe通道分析 8. 工具推荐 总结 信号完整性中…...

6.2.4 基本的数据模型

文章目录 基本的数据模型 基本的数据模型 基本的数据模型包含层次模型&#xff0c;网状模型和关系模型。 层次模型&#xff1a;使用树型结构表示数据间联系。记录间的联系用指针实现&#xff0c;简单高效。但是只能表示1:n的联系&#xff0c;且对插入、删除的限制多。网状模型…...

DeepSeek ,银行营销会被 AIGC 颠覆吗?

AI 让银行营销更智能&#xff0c;但更重要的是“懂客户” AI 在银行营销中的应用已经不仅仅局限于文案生成&#xff0c;而是渗透到了整个营销流程。 据悉&#xff0c;中国银行已经开始利用 AI 大模型构建智能营销助手系统&#xff0c;结合知识图谱和 AI 技术&#xff0c;实现…...

第150场双周赛:好数字之和、分割正方形 Ⅰ、分割正方形 Ⅱ、最短匹配字符串

Q1、好数字之和 1、题目描述 给定一个整数数组 nums 和一个整数 k&#xff0c;如果元素 nums[i] 严格 大于下标 i - k 和 i k 处的元素&#xff08;如果这些元素存在&#xff09;&#xff0c;则该元素 nums[i] 被认为是 好 的。如果这两个下标都不存在&#xff0c;那么 nums…...

HDFS是如何存储和管理大数据

HDFS&#xff08;Hadoop Distributed File System&#xff0c;Hadoop分布式文件系统&#xff09;是专为大数据处理而设计的分布式文件系统&#xff0c;具有高吞吐量、高容错性等特点&#xff0c;适用于大规模数据存储和管理。以下是HDFS存储和管理大数据的详细机制&#xff1a;…...

进阶——第十六届蓝桥杯嵌入式熟练度练习(开发板捕获频率和占空比)

单通道捕获频率 HAL_TIM_IC_Start_IT(&htim2,TIM_CHANNEL_1);HAL_TIM_IC_Start_IT(&htim3,TIM_CHANNEL_1); void HAL_TIM_IC_CaptureCallback(TIM_HandleTypeDef *htim) {if(htim->InstanceTIM2) {cap1HAL_TIM_ReadCapturedValue(&htim2,TIM_CHANNEL_1);TIM2-&…...

智能协同:数据集成平台与DeepSeek驱动的数据分析与智能调度革新

前言 企业面临着海量数据的挑战与机遇。如何高效地整合多源数据、精准分析并智能决策&#xff0c;成为企业提升竞争力的关键。本文解析轻易云数据集成平台与DeepSeek技术结合在数据分析和智能调度方面的创新应用&#xff0c;揭示其为企业带来的高效、智能与精准的业务价值。 …...

Mybatis高级(动态SQL)

目录 一、动态SQL 1.1 数据准备&#xff1a; 1.2 <if>标签 1.3<trim> 标签 1.4<where>标签 1.5<set>标签 1.6 <foreach>标签 1.7<include> 标签 一、动态SQL 动态SQL是Mybatis的强⼤特性之⼀&#xff0c;能够完成不同条件下不同…...

申论对策建议类【2022江苏B卷第一题“如何开展网络直播”】

材料&#xff1a; 近年来&#xff0c;公安交管部门通过网络直播&#xff0c;将执法过程和执法细节以视频形式呈现在公众面前&#xff0c;吸引“围观”、组织点评&#xff0c;让执法过程变成一堂生动的法治公开课。 “各位网友&#xff0c;大家好&#xff01;这里是‘全国交通…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

el-switch文字内置

el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

深度学习水论文:mamba+图像增强

&#x1f9c0;当前视觉领域对高效长序列建模需求激增&#xff0c;对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模&#xff0c;以及动态计算优势&#xff0c;在图像质量提升和细节恢复方面有难以替代的作用。 &#x1f9c0;因此短时间内&#xff0c;就有不…...

Chromium 136 编译指南 Windows篇:depot_tools 配置与源码获取(二)

引言 工欲善其事&#xff0c;必先利其器。在完成了 Visual Studio 2022 和 Windows SDK 的安装后&#xff0c;我们即将接触到 Chromium 开发生态中最核心的工具——depot_tools。这个由 Google 精心打造的工具集&#xff0c;就像是连接开发者与 Chromium 庞大代码库的智能桥梁…...

OD 算法题 B卷【正整数到Excel编号之间的转换】

文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的&#xff1a;a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...

Ubuntu系统多网卡多相机IP设置方法

目录 1、硬件情况 2、如何设置网卡和相机IP 2.1 万兆网卡连接交换机&#xff0c;交换机再连相机 2.1.1 网卡设置 2.1.2 相机设置 2.3 万兆网卡直连相机 1、硬件情况 2个网卡n个相机 电脑系统信息&#xff0c;系统版本&#xff1a;Ubuntu22.04.5 LTS&#xff1b;内核版本…...

Python实现简单音频数据压缩与解压算法

Python实现简单音频数据压缩与解压算法 引言 在音频数据处理中&#xff0c;压缩算法是降低存储成本和传输效率的关键技术。Python作为一门灵活且功能强大的编程语言&#xff0c;提供了丰富的库和工具来实现音频数据的压缩与解压。本文将通过一个简单的音频数据压缩与解压算法…...