文档介绍：第4章串
串类型的定义
串的表示和实现
串的模式匹配算法
串类型的定义
1. 基本概念
串(字符串) String:是零个或多个字符组成的有限序列。一般记为:S=‘a1a2...an’(n≥0)
栈、队列:操作受限的线性表。
串:取值范围受限的线性表,数据对象约束为字符集。
其中S是串的名字, 用单引号括起来的字符序列是串的值,ai(1≤i≤n)可以是字母、数字或其它字符。
串的长度:串中字符的个数n。
空串(Null String): n=0时的串称为空串,用符号“”表示。
子串:串中任意个连续的字符组成的子序列称为该串的子串。“”为任意串的子串。
主串:包含子串的串相应地称为主串。
位置:字符在串中的序号称为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。
A=‘China Beijing’, B=‘Beijing’, C=‘China’, 则它们的长度分别为13、7和5。B和C是A的子串, B在A中的位置是7, C在A中的位置是1。
串相等:当且仅当两个串的值相等时,称这两个串是相等的,即只有当两个串的长度相等, 并且每个对应位置的字符都相等时才相等。
空格串:由一个或多个空格组成的串。与空串不同。
串的基本操作和线性表区别很大。
线性表: 大多以“单个元素”为操作对象
串: 通常以“串的整体”为操作对象
例,查找某个元素;插入某个元素;删除某个元素
例,查找某个子串;截取某个子串;
在某个位置插入、删除某个子串
串的逻辑结构和线性表相似,故看作一种线性表。
s = ‘a1a2 an’( n≥0)
…
2. 串的基本运算:
串赋值StrAssign(&T, chars)
初始条件: chars是字符串常量。
操作结果: 生成一个值等于chars的串T。
pare(S, T)
初始条件: 串S和T存在。
操作结果: 若S>T, 则返回值>0;如S=T, 则返回值=0;
若S<T, 则返回值<0。
求串长StrLength(S)
初始条件: 串S存在。
操作结果: 返回串S的长度, 即串S中的元素个数。
串联接Concat(&T, S1, S2)
初始条件: 串S1和S2存在。
操作结果: 将T返回由S1和S2联接而成的新串。
求子串SubString(&Sub, S, pos, len)
初始条件: 串S存在, 1≤pos≤StrLength(S)且
1≤len≤StrLength(S)-pos+1。
操作结果: 用Sub返回串S的第pos个字符起长度为len的
子串。
串的表示和实现
定长顺序存储表示——顺序存储
堆分配存储表示——顺序存储
块链存储表示——链式存储
1. 定长顺序存储表示(定长顺序串)
#define MAXSTRLEN 255
typedef unsigned char SString[MAXSTRLEN+1];
定长顺序串的存储分配是在编译时完成的。与前面所讲的线性表的顺序存储结构类似, 用一组地址连续的存储单元存储串的字符序列。
超出予定义长度的串值被舍去,称之为“截断”。
0
1
2
255
串长的表示:
①以下标为0的数组分量存放串的实际长度;
②串值后加入一个不计入串长的结束标记字符,C中“\0”表串值的终结,其ASCⅡ码值为0。