大家好
数据结构与算法
这一讲我们继续学习第四章字符串
今天我们介绍字符串的存储结构
以及基本运算的实现
对于串长变化不大的情况呢
有几种比较经典的实现方案
首先我们要考虑的是
字符串的长度
因为字符串它还是一个相对比较
动态变化的数据结构
它的长度一会儿大一会儿小
我们怎么样把这个值给保存下来
在Pascal里面呢
它就是用s0来记录它的长度
但是它的缺陷呢就是
我们只有一个字节的
这样的长度来存串长值
因此这个字符串整体的长度
就不能够超过256个
我是不是可以把这个串长
这样的一个值
存在另外一个变量里面
但是这种方法呢
我们字符串它的动态的实现
就不是能够很好的支持
在C和C++里面
它用的是一个特殊的结束符
\0来表示字符串的结束符
这个\0呢
实际上它的值就是0
也等价于我们常用的NULL
这样的一个常量
字符串类可以更方便的
来支持字符串的表达
这里是一个字符串的数组
我们字符串数组str
以及串的长度size
都是私有的成员
不能够直接的访问
我们可以通过一些函数的定义
来间接的访问这两个值
在C和C++里面
常用的有这些基础的运算
像求串长
以及对串进行复制
还有串的拼接和串的比较
我们来看求串长的这个函数
因为我们有这么一个\0
它作为串结束的一个表示
其实它就相当于
我们在链表运算里面
那个结束的next域
它指向NULL
我们在对这个串
来判断它的长度的时候
我们首先设置下标值i
它的起始值是0
然后我们从0一直往下面挨个找
如果是第i它等于\0了
那就结束
那我们这个计数的结果呢
就是我们的串长值
字符串复制呢
我们其实不能够直接的等于
这样的给它拷贝过去
因为对于这两个字符串来说呢
它都有独立的存储的空间
我们必须是把这个原串s
里面的字符呢
挨个的去拷到目标串d里面去
如果你直接让d=s
那结果就是把s的这个存储地址
给它拷贝到了d里面
d它所保留的那个字符串的空间
就消失了
拷贝的过程呢
其实我们也是从下标0位开始
然后在原串s
它还没有达到\0之前
然后我们就挨个的
让d[i]=s[i]
然后我们下标位i再++
最后呢
我们要手工的去把d[i]那个位置
把它赋为\0
这就使得我们这个串呢
是一个正常的串
字符串的比较操作
在很多运算里面也是非常重要的
这个比较的运算呢
我们是采用的字典序来进行的
我们把数组的下标变量i
先设为0
然后我从这个s1和s2
它相应的i位置
逐个的往后面比
如果它们两都还没有结束的时候
我看当前位置s1[i]
是不是大于s2[i]
如果大我返回1
如果是s1[i]小于s2[i]
我返回-1
如果它们相等
那我就继续比较下一个位置
那个字符值
除了这个循环
我们有几种情况
首先就是s1[i]呢
它是等于\0
就是它结束了
那s2[i]它还没有结束
这种情况呢就是s1小于s2
返回-1
如果s2结束
而s1没有结束
这种情况呢
s1大于s2
返回+1
否则呢就是s1[i]和s2[i]呢
它们都是\0
它前面的这些字符值都是相等的
而最后它们的结束符
也是在相同的位置截止
所以它们是完全相等的
然后我们就返回0
比较字符串大小的运算呢
我们还有一个更简洁的版本
这个版本它就是把\0本身
当做一个特殊的符号
来直接参与了运算
首先我们设置下标i变量
从0开始往后面比
如果是s1[i]跟s2[i]
在这个位置相等
那我们就在这个循环里面继续操作
我们判断一下
当前这个s1[i]和s2[i]
它是不是都同时等于\0
如果是那就表示它们
恰好在相同的位置
都相应相等
而且在相同的位置是\0结束
所以它们是相等的
如果是不等的情况下
把s1[i]-s2[i]
而且再除以它们差值的绝对值
如果s1[i]大于s2[i]呢
就返回了+1
如果s1[i]小于s2[i]呢
就返回了-1
它们会不会在这里相等
那是不会的
因为我们前面这个循环语句
就保证了它相等的时候
就不会跳出这个循环
或者是说有一种特殊情况
它们相等了
但是都等于\0
那就整个跳出这个函数返回0
所以呢
我们也保证了它的分母
是不会等于0的
字符串类的一些基本运算
首先是构造函数
如果我传入了字符串s
作为它的初始值
那我们首先获得s
它的长度size
然后我申请一个size+1的
这么一个存储空间
这个+1就是预留给\0的
我们必须要保证
我申请的存储空间是有效的
如果在特殊的情况下
我们分配不到存储空间的时候呢
要进行异常处理
而且退出这个程序
获得了有效的存储空间以后
我就调用前面的字符串拷贝的函数
把这个初始值s呢
给它拷贝到我们新申请的
空间str里面
字符串的析构函数
主要是把我们申请的这个空间呢
释放掉
我们再介绍字符串的赋值运算
这个等于号呢
是对运算符等于的一个重载
使得我们在写
字符串的相关运算的时候呢
非常的方便
首先我们是要判断一下
我当前这个字符串它的长度
是不是跟我们要复制的
这个目标串的长度呢
是相等的
如果不是呢
我把当前串的
原来的存储空间给它释放掉
再申请一个目标串s的长度+1
这样的一个大小的空间
也要保证当前的这个空间
是有效的
然后我把当前这个字符串的长度
设为跟s的长度一样
然后我再调用strcpy这个函数
把我的目标串
它设置为我的原串的
那个字符串的值
然后我们要返回这个实例
就是return *this 这个指针
然后呢返回以后
这样我们就可以支持
连续的赋值操作
也就是连续的几个等号
都是可以支持的
给大家留一下思考
首先就是对String
抽取子串的这么一个运算
就是Substr这个方法的实现
我们传入的参数呢
是这个Substr里面的起始下标
index
这里是等于6
然后呢是我要连续拷贝几个字符
这里是5
我们大家来实现一下
这个函数
要注意一些边界的处理
然后呢 再看一下这两个思考题
就是对于s1和s2
这两个字符串
如果我
这个+呢
是对String cate
这样的拼接运算的一个重载
我们要使得s1+s2==s2+s1
应该是满足哪些条件
对于一个字符串来说
我怎么样来对它
进行一个逆值的操作
而且我不能够采用新的存储空间
只能是在原来的这个存储空间上
来实现
例如我对于一个字符串abcde
然后把它变为edcba
谢谢大家