首页 > 代码库 > 字符串
字符串
1、串的基本概念
从逻辑结构来看，串是一种特殊的线性表，即串可以看成是每个数据元素仅有一个字符组成的线性表。
l 长度为0的串称为空串；
l 包含一个及以上的空白字符的串称为空白串；
l 串中任意个连续的字符组成的子序列称为该串的子串；
l 包含子串的串称为该子串的主串；
l 串相等是指两个串的长度相等，并且各个对应位置的字符相同。
2、串的抽象数据类型描述
与线性表的不同之处在于，其每个数据元素的类型一定为字符型，而不能为其他类型
串的基本操作：
- 串的置空操作clear()：将一个已经存在串置成空串
- 串判空操作isEmpty()：判断当前串是否为空，若为空，则返回true；否则返回false
- 求串长度操作length()：返回串中字符的个数
- 取字符操作charAt(index)：读取并返回串中的第index个字符值
- 截取子串操作subString(begain, end)：返回当前串中序号从begain到end-1为止的子串
- 插入操作insert(offset, str)：在当前串的第offset个字符之前插入串str；0=<offset<=length
- 删除操作delete(begain, end)：删除当前串从序号begain到end-1为止的子串
- 串的连接操作concat(str)：把str串连接到当前串的后面
- 串的比较操作compareTo(str)：将当前串与目标串str进行比较。若
10. 子串定位操作indexOf(str, begain)：在当前串中从begain位置开始搜索与str相等的子串，若搜索成功，则返回子串的位置，否则返回-1；注意子串不能为空串
3、串的存储结构
3.1串的顺序存储结构
采用一组地址连续的存储单元来存储串字符序列
在Java中，可以使用字符数组实现串的存储，还需要设置一个串的长度参数，用来记录串中字符的个数。
3.2串的链式存储结构
采用单链表来存储串值，串的这种链式存储结构称为链串。
由于串结构的特殊性，采用链表存储串值时，每个结点存放的字符数可以是一个字符，也可以是多个字符。
若每个结点只存放一个字符，则这种链表称为单字符链表（插入、删除方便，但是存储效率太低）；否则称为块链表（提高了存储效率，但是插入、删除不方便）
顺序串的实现
串既可以对单个字符操作，又可以对整个串操作，还可以对连续的一组字符操作
4、串的基本操作实现
4.1求子串操作
SubString(int begain, int end)
0=<Begain<=length-1,1=<end<=lenth
主要步骤：
l 首先检查参数的合法性，若不合法就抛出异常；
l 若要截取整个串，则返回原串；否则截取从begain到end-1之间的子串
4.2 insert(int offset, IString str)
0<=offset<=length
主要步骤：
l 当插入位置超出合法位置，即offset<0或者offset>length，抛出异常
l 若插入时存储空间不足，则调用allocate(newCount)，重新分配存储空间
l 将strValue中从offset开始的字符往后移动str.length个位置
l 将str串插入strValue中从offset处的位置
4.3 delete(int begin, int end)
主要步骤：
l 检查参数的合法性，即begin<0，或者end>curLen，或者begin>end
l 将strValue中从end开始到串尾的子串向前移动begin的位置
l 将当前串长度减去end-begin
4.4 compareTo(SeqString str)
主要步骤：
l 求出当前串与待比较串的长度，并把较小值赋值到n
l 从下标0到n-1依次取出两个串中对应的字符进行比较，若不等，则返回第一个不相等的字符的数值差
l 若下标从0到n对应的字符均相等，则返回两个串长度的差
5、串的模式匹配操作
串的查找定位操作：在当前串（主串）中寻找子串（模式串）的过程。若在主串中找到了一个和模式串相同的子串，则查找成功；若在主串中找不到与模式串相同的子串，则查找失败。当模式匹配成功时，函数返回值为模式串的首字符在主串中的位序号；当匹配失败时，函数的返回值为-1.
5.1 Brute-Force算法
实现方法：
设s为主串。T为模式串；i为主串当前比较字符的下标；j为模式串当前比较字符的下标。令i的初值为start，j的初值为0.当主串的第start个字符起和模式串的第一个字符（j=0）比较，若相等，则继续逐个比较后续字符，否则从主串的第二个字符起重新和模式串比较，依次类推，直至模式串t中每一个字符依次和主串s的一个连续的字符序列相等，则称匹配成功，函数返回模式串t的第一个字符在主串s中的位置；否则称匹配失败，函数返回-1。
优点：简单易懂
缺点：时间效率非常低，最坏的时间复杂度为o（m*n）
5.2 KMP模式匹配算法分析
主要思想：每当某趟匹配失败时，i指针不回退，而是利用已经得到的部分匹配结果，将模式向右滑动尽可能远的一段距离后，继续进行比较
字符串