c++按顺序查找⼀个字符串是否含有某个字符_数据结构基础（代码效率优化，线性表，栈，队列,。。。
作者：张⼈⼤
作者：
代码效率优化
复杂度 -- ⼀个关于输⼊数据量n的函数
时间复杂度 -- 昂贵
与代码的结构设计有着紧密关系
⼀个顺序结构的代码，时间复杂度是O(1), 即任务与算例个数 n ⽆关
空间复杂度 -- 廉价
与数据结构设计有关
数据结构 -- 考虑如何去组织计算机中⼀定量的数据。
数据结构连接时空，⽤空间换取时间。
数据处理 -- 了解问题，明确数据操作⽅法，设计出更加⾼效的数据结构类型
找到需要处理的数据，计算结果，再把结果保存下来
把结果存到新的内存空间中
把结果存到已使⽤的内存空间中
基本操作只有三个：增，删，查
增和删可以细分为数据结构的中间以及最后的增和删
查找可以细分为按照位置条件查找和数据数值特征查找
所有数据处理都是这些基本操着的组合和叠加
只有字典类型数据结构能在 O(1) 的时间复杂度内完成查找动作
回归问题本源，明确数据被处理的动作，来解决数据结构的问题
想了解更多，欢迎关注我的微信公众号：Renda_Zhang
想了解更多，欢迎关注我的微信公众号：Renda_Zhang
线性表
n 个具有相同特性的元素的有限序列，Linear List
数据元素之间的关系是⼀对⼀的关系
即除了头尾元素外，其它数据元素都是⾸尾相接的
这句话只适⽤⼤部分线性表，⽽不是全部
⽐如，循环链表尾的指针指向⾸位结点
实现⽅式
最常⽤的是链式表达，也叫线性链表或链表
每个结点包括具体的数据值和指向下⼀个结点的指针
五年级作文说明文单向链表，循环链表，双向链表，双向循环链表
新增和删除为 O(1) 时间复杂度，⽽查找为 O(n)
适合数据元素个数不确定，且经常进⾏新增和删除
链表的翻转，快慢指针的⽅法，是必须掌握的内容
使⽤数组实现，也叫顺序存储，顺序表
类别
⼀般线性表，可以⾃由的删除和添加结点
受限线性表，主要包含栈和队列
栈和队列是特殊的线性表，本质上他们都可以被看作是⼀类基本结构
线性表案例
链表的翻转
快慢指针
查找奇数个数的链表的中间位置结点的数值
做包子怎么发面判断链表是否有环
栈
后进先出的（限制后的）线性表，Last In First Out, Stack.
新增和删除操作只能在这个线性表的表尾进⾏，即在线性表基础上加了限制新增: 压栈 push, which adds an element to the collection
删除: 出栈 pop, which removes the most recently added element
功能上，数组或者链表可以代替栈，但它们灵活性过⾼，数据量⼤时有风险栈顶和栈底是⽤来表⽰这个栈的两个指针中国画图片
栈顶 (top) 是表尾，⽤来输⼊数据
栈底 (bottom) 是表头
栈有顺序表⽰和链式表⽰，分别称作顺序栈和链栈
顺序栈
可以借助数组来实现
数组的⾸元素存在栈底，尾元素放在栈顶
定义指针 top 来指⽰栈顶元素在数组的位置
栈中只有⼀个元素，则 top = 0
以 top 是否为 -1 来判定是否为空栈
栈顶 top 需⼩于栈的最⼤容量
我是XX生出栈操作，只需要 top - 1 即可
链式栈
⽤链表的⽅式实现
通常把栈顶放在单链表的头部
top 指针替换了链表原来的尾指针，去掉了头指针出栈操作，将 top 指针指向栈顶元素的 next 指针即可对⽐栈和⼀般线性表
相同点：
操作原理相似
时间复杂度⼀样
都依赖当前位置指针进⾏数据对象的操作
区别：栈只能新增和删除栈顶的数据结点
栈的案例
判断括号字符串是否合法
浏览器页⾯访问的后退和前进
队列
先进先出 (限制后的) 线性表, First In First Out, Queue 新增和删除操作只能分别在队尾和队头进⾏先进 - 队列的数据新增操作只能在末端进⾏, add
不允许在队列的中间某个结点后新增数据
先出 - 队列的数据删除操作只能在始端进⾏, remove
不允许在队列的中间某个结点后删除数据
队列适合⾯对数据处理顺序⾮常敏感的问题可以确定队列长度最⼤值, 建议使⽤循环队列
⽆法确定队列长度时, 应考虑使⽤链式队列
front 和 rear 两个指针
队头 (front), ⽤来删除数据
队尾 (rear), ⽤来增加数据
队列有两种存储⽅式, 即顺序队列和链式队列顺序队列
依赖数组来实现
数据在内存中也是顺序存储
进⾏新增插⼊操作时,
尾指针会向后移动
时间复杂度为 O(1)
如果只删除头的第⼀个元素时
每次删除都需要把整个数组前移
时间复杂度为 O(n)
使⽤循环队列
必须有⼀个固定的长度
实现删除的时间复杂度为 O(1)
使⽤ flag 来判断队列空或满
链式队列
依赖链表来实现
数据依赖每个结点的指针互联工龄
是离散存储线性结构
实际上就是尾进头出的单链线性表
在空间上更为灵活
通常会增加⼀个头结点
让 front 指针指向头结点
头结点不存储数据, 只是辅助标识
当进⾏数据删除时, 实际删除的是头结点的后继结点
队列为空时, 头尾指针都指向头结点
对⽐队列和⼀般线性表
队列继承了线性表的优点和不⾜
是加了限制的线性表
队列案例
约瑟夫环 - Jophus problem
数组
数组可以看成是线性表的⼀种推⼴，它属于另外⼀种基本的数据结构数组是数据结构中的最基本结构
⼏乎所有的程序设计语⾔都把数组类型设定为固定的基础变量类型。
可以把数组理解为⼀种容器，它可以⽤来存放若⼲个相同类型的数据元素。
例如：
存放的数据是整数型的数组，称作整型数组；
存放的数据是字符型的数组，则称作字符数组；
另外还有⼀类数组⽐较特殊，它是数组的数组，也可以叫作⼆维数组。
可以把普通的数组看成是⼀个向量，那么⼆维数组就是⼀个矩阵。
数组在内存中是连续存放的，数组内的数据，可以通过索引值直接取出得到。
数组的索引就是对应数组空间
在进⾏新增、删除、查询操作的时候，完全可以根据代表数组空间位置的索引值进⾏。
只要记录该数组头部的第⼀个数据位置，然后累加空间位置即可。
数组的基本操作
具有增删困难、查找容易的特点，可以在任意位置增删数据，所以数组的增删操作会更为多样。
新增操作
党内严重警告处分若插⼊数据在最后，则时间复杂度为 O(1)
如果中间某处插⼊数据，则时间复杂度为 O(n)
删除操作
在数组的最后删除⼀个数据元素，则时间复杂度是 O(1)
在这个数组的中间某个位置删除⼀条数据, 时间复杂度为 O(n)
也许英文
查找操作
如果只需根据索引值进⾏⼀次查找，时间复杂度是 O(1)
要在数组中查找⼀个数值满⾜指定条件的数据，则时间复杂度是 O(n)。
对⽐数组和链表
链表的长度是可变的，数组的长度是固定的，在申请数组的长度时就已经在内存中开辟了若⼲个空间。如果没有引⽤ ArrayList 时，数组申请的空间永远是我们在估计了数据的⼤⼩后才执⾏，所以在后期维护中也相当⿇烦。
链表不会根据有序位置存储，进⾏插⼊数据元素时，可以⽤指针来充分利⽤内存空间。数组是有序存储的，如果想充分利⽤内存的空间就只能选择顺序存储，⽽且需要在不取数据、不删除数据的情况下才能实现。
数组的案例
基于数组，计算平均值
字符串
由 n 个字符组成的⼀个有序整体（ n >= 0 ）
对⽐字符串和线性表
字符串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。
字符串的基本操作和线性表有很⼤差别：
在线性表的基本操作中，⼤多以“单个元素”作为操作对象；
在字符串的基本操作中，通常以“串的整体”作为操作对象；
字符串的增删操作和数组很像，复杂度也与之⼀样。但字符串的查找操作就复杂多了，它是参加⾯试、笔试常常被考察的内容。
特殊的字符串
空串，指含有零个字符的串。例如，s = ""，书⾯中也可以直接⽤ Ø 表⽰。
空格串，只包含空格的串。它和空串是不⼀样的，空格串中是有内容的，只不过包含的是空格，且空格串中可以包含多个空格。例如，s = " "，就是包含了 3 个空格的字符串。
⼦串，串中任意连续字符组成的字符串叫作该串的⼦串。
关于立志的名言警句
原串通常也称为主串。
