研究分析数据结构第四章字符串.pptVIP

数据结构第四章 字符串 4.1 串的基本概念 串(String)的概念：是由零个或多个字符组成的有限序列。记作： S=＂a1 a2 … an＂ (n≥0) 其中S是串名，用双引号括起来的字符序列为串值，引号是界限符，ai(1≤i≤n)是一个任意字符(字母、数字或其他字符)，它称为串的元素，是构成串的基本单位，串中所包含的字符个数n称为串的长度，当n=0时，称为空串。 将串值括起来的双引号本身不属于串，它的作用是避免串与常数或与标识符混淆。例如，A=123是数字字符串，长度为3，它不同于整常数123。 常将仅由一个或多个空格组成的串称为空白串。注意空串和空白串的不同，例如 和分别表示长度为1的空白串和长度为0的空串。 4.1 串的基本概念 子串的概念：串中任意连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。 通常称字符在序列中的序号为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符首次出现在主串中的位置来表示。 例如，设有两个字符串C和D： C=＂This is a string.＂ D=＂is＂ 则它们的长度分别为17、2；D是C的子串，C为主串。D在C中出现了两次，其中首次出现所对应的主串位置是3。因此，称D在C中的序号(或位置)为3。 若两个串的长度相等且对应字符都相等，则称两个串是相等的。当两个串不相等时，可按“字典顺序”区分大小。 4.1 串的基本概念 串也是线性表的一种，因此串的逻辑结构和线性表极为相似，区别仅在于串的数据对象限定为字符集。 串的运算： 串赋值 StrAssign(s,chars)：已知串常量chars，生成一个值等于chars的串s。 求串长 StrLength(s)：已知串s，返回串s的长度。 串连接 StrConcat (s1,s2)：已知串s1,s2，在s1的后面连接s2的串值。 求子串 SubStr(s,i,len)：已知串s，返回从串s的第i个字符开始的长度为len的子串。 串比较 StrCmp(s1,s2)：已知串s1,s2，若s1==s2，操作返回值为0；若s1s2, 返回值小于0；若s1s2, 返回值大于0。 4.1 串的基本概念 子串定位 StrIndex(s,t)：已知串s,t，找子串t在主串s中首次出现的位置，即若t∈s，则操作返回t在s中首次出现的位置，否则返回值为－1。 串插入 StrInsert(s,i,t)：已知串s,t，将串t插入到串s 的第i个字符位置上。 串删除 StrDelete(s,i,len)：已知串s，删除串s 中从第i个字符开始的长度为len的子串。 串替换 StrRep(s,t,r)：已知串s,t,r，用串r 替换串s中出现的所有与串t相等的不重叠的子串。 销毁串 StrDestroy(s)：已知串s，销毁串s。 以上是串的一些基本操作。其中前５个操作是最为基本的，它们不能用其他的操作来合成，因此通常将这５个基本操作称为最小操作集，反之，其他操作可在这个最小操作集上实现。 4.2 串的存储结构 4.2.1 串的顺序存储 顺序串：串的顺序存储结构简称为顺序串。 与顺序表类似，顺序串是用一组地址连续的存储单元来存储串中的字符序列的。因此可用高级语言的字符数组来实现，按其存储分配的不同可将顺序串分为静态存储分配的顺序串和动态存储分配的顺序串两类。 4.2 串的存储结构 1. 静态存储分配的顺序串 所谓静态存储分配，是指按预定义的大小为每一个串变量分配一个固定长度的存储区，即串值空间的大小在编译时刻就已确定，是静态的。所以串空间最大值为MAXSIZE时，最多只能放MAXSIZE-1个字符。其类型描述如下： #define MAXSIZE 256 //该值依赖于应用，由用户定义 typedef struct { char ch[MAXSIZE]; //256个字符依次存储在ch[0]..ch[MAXSIZE－1]中 int len; } SString; //SString是顺序串类型，则串的最大长度不能超过255 SString s; //定义串变量s 4.2 串的存储结构 在直接使用定长的字符数组存放串内容外，一般可使用一个不会出现在串中的特殊字符放在串值的末尾来表示串的结束。例如，C语言中以字符\0表示串值的终结。 C语言中串的静态存储结构如下图所示： 4.2 串的存储结构 2. 动态存储分配的顺序串(堆串) 这种存储表示的特点是，仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分