引言
当今计算机的硬件结构主要是反映数值计算的需要，在处理字符串的数据时比处理整数和浮点数要复杂，不同类型的应用对字符串的处理的需求不同，要有效处理字符串，就必须根据具体的情况使用合适的存储结构。
串定义
串或字符串由0个或多个字符串组成的有限序列。其中串值必须用单引号括起来，但是单引号不属于串，它的作用只是为了避免与变量名或数的常量混淆。
串可以用二元数组的形式（D,R）来定义，串的逻辑结构和线性表极为相似，区别在D的定义上，串的数据对象是字符集
串的基本操作
1.赋值操作
2.判等操作
3.求长度的操作
4.连接的操作
5.求子串的操作
6.替换的操作
7.插入的操作
8.删除的操作
9.定位的操作
串的存储结构
如果在程序语言中，串只是作为输入和输出的常量出现，则只需要作为一个字符的序列存储即可，但在多数非数值的处理程序中，串也是操做的对象，在程序的执行过程中，其值可变，这和程序中出现的其他的类型的变量一样，在对串进行操作时通过变量名访问其值。
两种处理方式：
静态存储结构
1、将串设计成一种结构类型，串是字符的数组，从串名可以直接访问串值，串值的存储分配是在编译时完成的。（用一组地址连续的存储单元存储串的字符序列）
非紧缩格式：一个字存储单元存放一个字符（计算机的存储器采用的是字编址结构）
紧缩格式：即在一个字存储单元中存放多个字符
[图片上传失败...(image-48e05c-1513232902433)]
动态的存储结构
2串值的存储分配是在程序运行时完成的，在串值和串名之间建立一个对照表，称之为存储映像。
和线性表的链式存储结构相似，用链表的方式存储串值。要设有头指针和尾指针（指向链表的最后一个节点）给出串的长度称此种串存储的结构为块链结构
两种存储结构的对比
一、使用顺序方式存储串值，由于预先就定义可一个串的最大长度，当串小时空间的利用率低，另一方便在串操作链接置换等受到了限制
二、使用链表进行储存时链表比较灵活，长度不受限制，但是会影响到存储密度的制约，链块表使得串的操作复杂化，存在节点大小取多大比较合适的问题。
串操作的实现
静态结构存储串的操作
1.串的联结
2.求子串
3.求子串位置的定位函数
模式匹配的一种改进算法
kmp算法(在模式匹配的基础之上进行优化，返回上次在未匹配的索引)
堆结构存储串时的操作
1、赋值操作联结运算
2、求子串
3、置换操作
串操作的应用
1.文本编辑
在文本编辑的程序中设立页指针，行指针和字符指针，分别指示当前操作的页行和字符。
2.建立词索引表
信息检索是计算机应用的重要领域，为了提高信息检索的效率，需要建立一个号的索引系统。例如图书馆的“书名关键字索引”
查找步骤：
1、从书录文件中读入一个书名串
2、从书录串中提取所有的关键字插入词表
3、对词表中的每一个关键字，在索引表中进行查找并作出相应的插入操作。
如图a书录文件
如图b关键词索引表
词表为线性表，是中间变量非常驻内存，采用顺序存储结构。
索引表为有序表，虽是动态生成的，在生成的过程之中需要频繁的进行插入操作，因为索引表主要的功能还是进行查找，为提高查找的效率，所以采用顺序的存储结构。包涵两个内容：关键词、书号索引。因为常驻内存，因考虑节省存储空间。采用链式存储结构（书号是长度是不等变化的）。
