大家好 这一讲我们开始
数据结构与算法第四章
字符串的学习
今天我们首先介绍
字符串的相关概念
经常在输入输出的时候
会有一些提示
一些信息
这就是字符串的一些实例
字符串它其实是一种特殊的线性结构
它也是一个字符所组成的
有限序列
我们把这个字符串c0到cn-1
记为s
s就是它的串名
而c0到cn-1
就是它的串值
其中每一个元素ci呢
就是里面的字符
这个字符串的元素个数
就是它的串长
串长也是比较重要的
知道了这个串长呢
我们可以在申请空间的时候
预留相应的空间
如果串长是0
那就是空串
空串它跟这样的双引号表示的
中间空了一些空格的
这种字符串呢
它是不一样的
空串是里面没有任何的有效字符
直接就是一个结束的符号
字符串它跟普通的线性结构
主要有哪些区别呢
首先就是普通的线性结构
它的元素呢
没有特别的限制
你是什么样的类型都可以
而字符串
它必须是字符作为这里面的元素
在操作上呢
普通的线性表
它并没有特别的操作的限制
想从中间读
或者是从两边都没关系
读几个也没有特别的限制
但是在字符串里面
经常是用里面的
一个整体的子串
也就是我们对连续的若干个字符呢
一起来操作
字符串作为线性表的
一种特殊的形式呢
在它的存储实现的时候
其实跟普通的线性结构
是可以类似的实现的
但是有一点要注意呢
因为字符串它的基本元素是字符
如果你用链接的形式来实现的话
它有很大的指针
这样的结构性开销
它的存储效率是比较低的
而且相关的运算也不见得
有什么高效的改进
因此呢
字符串的存储
更多的是采用了顺序存储的方法
在字符串里面
我们首先来看一下
哪些东西可以是字符
其实跟你的应用是相关的
如果是对二进制组成的代码
那我们基本的字符集就是0 1
如果是对于DNA序列
这样的字符串
我们的字符集就是A C G T
不同的应用它有不同的
这种基础字符集
而且我们知道了这样的基础字符集
在某些算法里面
可以利用这些特性
来改进我们算法的效率
字符编码
我们最常用的就是ASCII码
它可以对常见的一些字符进行编码
在C和C++里面
它都是采用ASCII码来编码的
但是呢对于一些复杂的语言
像中文这样的东方语言
如果是只用这种8个位
也就是一个字节的编码来编
肯定是编不完的
那就必须是双字节来编码
双字节编码呢
也有各种不同的编码体系
像中国国内制定的国标码
以及随着internet的普及
国际标准的UNICODE
它不光是中文编码
对于这种复杂语言
像日韩 阿拉伯语言
也都囊括在UNICODE的
编码体系里面
编码了以后
怎么来判断两个字符
甚至是两个字符串的大小
那就是由字符的编码顺序
来决定的
这个编码顺序呢
我们往往是跟字典序相关
有些情况呢
可能也按照特殊的一些要求
比如说在中文里面
你也许是按照笔划序来编码的
字符串它的数据类型
在不同的语言里面呢
也是有不同的观点
在一些早期的语言系统里面
会觉得字符串
它应该是一个复杂的结构
它不是一个简单的基础结构
在现在呢
字符串是非常重要的基础的
数据类型了
所以我们也可以把它看作是
简单的类型
字符串呢
我们有一些常量
还有一些可以当做变量
像我们在C和C++里面
我如果是用双引号把它引起来
中间的这些字符呢
就形成了这样的一个字符串的常量
我们可以定义不同的变量
然后对字符串进行一些更灵活的
运算和操作
我们在字符串里面
有一个特别重要的概念
就是子串
我如果有一个串s1
它是从a0到an-1的
另外一个串呢是s2
它是从b0到bm-1
中间对于s1
我们取中间的某一个子串
从下标iv开始
ai对应到b0
a的i+j对应到bj
如果是这些相应位置上的字符
都逐个相等
一直从b0到bm-1
都能够正好匹配到
s1里面的相应的ai到ai+m-1
我们就可以说
这个s2呢
是s1的子串
而s1呢
就是s2的祖串
空串是任何串的子串
另外呢任何串本身
也是它自己的子串
还有一个概念是真子串
这个真子串就是
如果一个祖串
它里面有一个子串
那这个子串呢
既不是空串
也不是这个组串本身
那就是一个真子串
我们来看一下
字符串的一些基本运算
因为C++
它继承了C的标准函数库的
很多内容
对于字符串来说呢
这些运算呢
都是一些非常基础的运算
如果是只用到C
那我们需要include
这些运算里面
有很多是对子串操作的
像复制 拼接
另外像求子串
然后串的比较
都是可以说对整个串进行的
还有是在串里面
定位某一个字符的
这样的操作
另外求整个串的串长
特别注意串比较
这样的一个操作
对于两个串s1和s2
如果s1是大于s2
这个strcmp
它是返回大于0的值
如果s1是小于s2呢
是返回小于0的值
只有在它s1和s2相应位置上
都逐个相等
才能够等于0
这个串的比较
也是按照字典序来比的
我们来看一下
定位函数在这个串s里面
找字符o的第一次出现
我们是从字符串的起始位置
第0位开始往右边找
然后找到它的第一次出现
是下标4的位置
那我们返回4
还有一个相应的
是反向查找
也就是说从右边往左边开始找
如果是我们调用
这个反向查找的函数
我们就会得到
在这个串里面呢
下标为7的这个位置
在C++标准字符串类库里面呢
它还有很多的函数
我们要引用它
首先要include
然后呢要再声明一下
我使用std这样的命名空间
对于C++字符串来说
我们是适用于变长的字符串的情况
我们采用的是动态的存储分配方案
我们来看C++类库的
一些函数定义
可以看到很多的操作
其实都是对子串进行的
像拷贝 交换
复制 插入 拼接
替换 清除
当然还有找子串的
这么一个操作
都是在子串的意义下
进行的操作
另外呢
有这个统计
就是看它的这个串的长度
还有它能够容纳多大的空间
这个是这么一些相关的操作
特别是这个查询操作
是一个非常重要的运算
在一个组串里面
我指定一个子序列
你返回这个子序列
在组串里面的起始的位置
这个就是跟我们后面要讲的
模式匹配算法相关
字符串中
定位操作也是一种重要的运算
我们可以根据它的下标来进行定位
这里我们重载了下标运算符
[]
我对这样的一个字符串
我可以指定它的下标位置i
然后s[i]呢
就返回在数组的第i个下标位置
相应的字符
还可以指定字符串里面的起始位置
然后从起始位置
往右边一直到这个字符串的末尾
来查找字符C的
第一次出现的位置
反向查找就是从指定的
某一个位置开始
从字符串的末尾
往字符串开始的方向
也就是我们从右往左来查找
字符c的第一次出现的位置
最后给大家留几个思考题
我们判断一下
下面哪一些串呢
是software
这个字符串的子串
第二个思考题呢
就是对于software这个字符串
它的子串的数目为多少
谢谢大家