综述

串/字符串：零个或多个字符组成的有限序列

• 文本串：字母、数字、特殊符号构成
• 位串：0、1构成
• 基因序列：可以使用字符串模型表示，其字母表只包括4个 字母{A, C, G, T}

• $s$：串名，其后单引号括起是串的值
• $a_i$：字母、数字等字符
• $n$：串中字符的数目，串长度，零个字符的串称为空串

• 串的逻辑结构和线性表相似，只是串的数据对象约束为字符集
• 串的基本操作和线性表有很大差别
  • 线性表基本操作大多以“单个元素”作为操作对象
  • 串的基本操作通常以“串的整体”作为操作对象

串的存储表示

• 串只作为输入、输出常量出现，则只需要存储串的串值字符序列
• 在非数值处理中，串也以变量形式出现

定长顺序存储

• 类似线性表的顺序存储结构
• 按照预定义大小，为每个定义的串变量分配固定长度的存储区， 存储字符序列

1

typedef unsigned char SString[MAXSTRLEN+1]

• 串实际长度在预定义范围内随意，超过预定义长度的串值则被 舍去（截断）
• 串实际长度存储方式
  • 以下标为0的数组分量存放：Pascal
  • 在串值后面加入不计串长的结束标记字符：C以\0标记， 此时串长为隐含值，不利于某些操作
• 串操作的原操作为“字符序列的复制”，操作的时间复杂度基于 复制的字符序列长度

堆分配存储

• 仍然以地址连续的存储单元存储串字符序列，但存储空间是在 程序执行过程中动态分配得到

1
2
3
4

typdef struct{
	char *ch;
	int length;
}

• length：串长

• 既有顺序存储结构的特点，处理方便，对串长又没有任何限制
• 此存储结构的串操作仍是基于“字符序列的复制”进行

块链存储

• 使用链表的方式存储串值
• 但是串结构特殊的，需要设置节点大小

1
2
3
4
5
6
7
8

typedef struct Chunk{
	char ch[CHUNKSIZE];
	struct CHUNK * next;
}Chunk;
typedef struct{
	Chunk *head, *tail;
	int curlen;
}

• CHUNKSIZE：节点大小，每个节点中最大存储字符数量
• curlen：当前串长度

• 节点大小不为1时，链表最后一个节点不一定全被串值占满， 此时通常补上非串值字符
• 一般情况下，对串进行操作时，只需要从头到尾扫描即可
  • 对串值不必简历双向链表
  • 设尾指针是为了方便进行联结操作（联结操作需要注意 串尾无效字符）
• 节点大小选择影响串处理效率
  • 存储效率 = 串值所占存储位/实际分配存储位
  • 存储密度小，运算处理方便，存储量占用大
• 块链结构对某些串操作有一定方便，但是总的来说不如另外两种 存储结构灵活，存储量大、操作复杂

串的模式匹配

模式匹配：子串定位操作