串

字符串是一种特殊的线性表，其特殊性在于线性表的数据元素限定为字符串；理。字符串一般简称为“串”，并具有自身的特征，通常把一个串作为一个整体来处理。

应用实例

例文本编辑软件

文本编辑程序是利用计算机进行文字加工的基本软件工具，实现对文本文件的插入、删除、修改等操作，甚至用于报刊和书籍的编辑排版。常用的简单文本编辑程序，1,和文字处理软件机VJ、机*1等，究其实质，都是修改字符数据的形式或格式。可用于文本编辑的程序很多，功能不同且强弱差别很大，但基本操作是一样的，一般都包含串的查找、插入和删除等基本

例如，对于下面的一段源程序，一个文本编辑软件首先必须解决的问题就是文本串在内存中如何存储，其次需要解决的问题是基于存储方式实现对文本串的实际操作

main{    int x,y,max;    scanf"%d%d",&x,&y;    ifx > y{        max = x;    } else {        max = y;    }        printf"max = %d", max;}

串及其运算

串（string）是由零个或多个字符组成的有限序列，一般记作 $S = "a_1 a_2 a_3 a_4 a_5 \cdots a_n"$

空串（null string）：长度为零的串，它不包含任何字符
空格串（blank string）: 仅由一个或多个空格组成的串，长度大于等于1
子串（sub string）：串中任意个连续字符组成的子序列称为该串的“子串”
主串（master string）：包含子串的串相应地称为“主串”。因此子串是主串的一部分
位置：通常将字符在串中的序号称为该字符在串中的“位置”
串相等：当且仅当两个串的值相等时，称这两个串是相等的。即只有当两个串的长度相等，并且每个对应位置的字符都相等时才相等
模式匹配：确定子串从主串的某个位置开始后，在主串中首次出现的位置的运算。在串的模式匹配中，一般将主串称为“目标串”，子串称为“模式串”

基本运算

串的基本操作中，则通常以“串的整体”或“串的一部分”作为操作对象，例如在串中查找某个子串，在某个位置上插入一个子串或删除一个子串等。

拷贝
获取长度
删除子串
插入子串
比较串
串拼接
查找子串
替换子串
串存在判断
清空串
销毁串

串的存储结构及其实现

串的实现方法有定长顺序串、堆串和块链串，分别介绍如下

顺序串

串的定长顺序存储结构，与前面线性表的顺序存储结构类似，是用一组地址连续的存储单元存储串的字符序列，也称为“静态存储分配的顺序串”。所谓定长顺序存储是直接使用定长的字符数组来定义，为每个定义的串变量分配一个固定长度的存储区，存储分配是在编译时完成的

存储结构

# define MAXLEN 50typedef struct {    char ch[MAXLEN + 1]; //存储字符串的一堆数组，每个分量存储一个字符，第0号单元不使用    int len;} SString;

串的实际长度可在预定义长度）5^{S，3的范围内随意变动，超过）5}S，3，串值被舍去，称为“截断”。

字符串的长度可以采用以上描述的定长顺序串类型定义中的成员&%+表示，此时的号单元不使用（浪费一个空间）；也可以在串值后设特殊标记，隐含串长，例如6语言中f的表示串的结束。

堆串

串的堆存储结构，与定长顺序串的存储结构类似，都是用一组地址连续的存储单元存储串的字符序列，不同的是堆串的存储空间是在程序执行过程中动态分配的。在系统中存在一个称为“堆”的自由存储区，每当建立一个新串时，可以通过动态分配函数从这个空间中分配一块实际串所需的存储空间，来存储新串的串值。只要存储空间能分配成功，则在操作的过程中就不会发生“截断”的情况

存储结构

typedef struct {    char *ch; //若是非空串，则指向串的起始地址否则ch是null    int len;} HString;

块链串

在串的链式存储结构中，链表的每个结点既可以存放一个字符，也可以存放多个字符。每个结点称为“块”，整个链表称为“块链结构

存储结构

# define BLOCK_SIZE 4typedef struct block{    char ch[BLOCK_SIZE];     struct block *next;} Block;typedef struct {    Block *head;    Block *tail;    int len;}LString

在一般情况下，对串进行操作时，只需要从头向尾顺序扫描即可，则对串值不必建立双向链表。但当进行串的连接操作时，就要在第一个串的尾部进行连接，因此在块链存储中设置尾指针可以便于其操作。在连接时需要注意处理第一个串的最后一个结点中的无效字符。

块大小是指块链表中结点存放字符的个数。假设链表结点的链域next所需的存储空间大小为?字节。在块链串的存储方式中，块大小直接影响到串处理的效率。这就要求考虑串值的存储密度。存储密度定义为
$$存储密度 = \frac{度法串值所占的存储位}{实际分配的存储位}$$

当BLOCK_SIZE大于1：由于串长不一定是块大小的整倍数，则链表中的最后一个结点不一定全被串值占满，此时通常补上“Z”或其他的非串值字符（通常“Z”不属于串的字符集，是一个特殊的符号）

当BLOCK_SIZE等于1：此时块链表结构同线性链表，插入、删除等处理方法和线性链表一样

串的模式匹配

原文地址