《数据结构课件：串》由会员分享，可在线阅读，更多相关《数据结构课件：串（50页珍藏版）》请在金锄头文库上搜索。
1、第第 四四 章章 串串内容提要：内容提要：理解串的逻辑结构及定义理解串的逻辑结构及定义理解串的存储结构及操作的虚拟实现理解串的存储结构及操作的虚拟实现理解串的模式匹配算法理解串的模式匹配算法第第 四四 章章 串串本章学习另一种本章学习另一种特殊的特殊的线性表，它特殊在：线性表，它特殊在：1 数据元素都是来自字符集！数据元素都是来自字符集！2 由于数据元素特殊，它的操作有些不同与由于数据元素特殊，它的操作有些不同与 一般线性表，一般线性表，例如：操作的对象一般是对子串（即一组数据元例如：操作的对象一般是对子串（即一组数据元素）素）,而不是单个数据元素而不是单个数据元素!有些高级语言已经把串有些高
2、级语言已经把串ADT 物理实现了，所物理实现了，所以，我们这里只是简单讨论一下串的逻辑特性、以，我们这里只是简单讨论一下串的逻辑特性、存储结构及一些操作的实现。存储结构及一些操作的实现。4.1 串的逻辑结构及定义串的逻辑结构及定义一一 串的逻辑结构串的逻辑结构1 、串（、串（String）：简单说，它是有限字符集中的零个）：简单说，它是有限字符集中的零个或多个字符组成的有限序列。或多个字符组成的有限序列。按数据结构来定义：它是一种特殊的线性表（数据元素按数据结构来定义：它是一种特殊的线性表（数据元素之间的关系是线性关系），特殊在其数据元素来自于之间的关系是线性关系），特殊在其数据元素来自于字符
3、集这个数据对象。定义为：字符集这个数据对象。定义为：String (D,R)D = ci|ci DO DO = CHARACTER i = 1，2, n n=0 R NN = | ci-1 , ci D0 i = 2，3, ，n 4.1 串的逻辑结构及定义串的逻辑结构及定义一一 串的逻辑结构串的逻辑结构 一个串一般记作：一个串一般记作：S = c1c2cn 2 、串结构的特点：、串结构的特点：数据元索都是字符，它的数据元索都是字符，它的操作的对象一般不再是单个数据元素，而是一操作的对象一般不再是单个数据元素，而是一组数据元索。组数据元索。3 、串的一些术语：、串的一些术语：空串：长度为零的字符
4、串，空串：长度为零的字符串，n = O空格串：数据元素都是空格的字符串；空格串：数据元素都是空格的字符串；子串：串中连续的任意个字符组成的子子串：串中连续的任意个字符组成的子序列，称为该串的子串；序列，称为该串的子串；主串：包含子串的串；主串：包含子串的串；c = DATA STRUCTURE，f=DATA f是是c的子串的子串下面是一些串的例子：下面是一些串的例子：(1) a = LIMING(2) b = BEJING UNIUERCITY(3) c = DATA STRUCTURE(4) d = (5) e = 说明：说明：1) 串中包含的字符个数，称为串中包含的字符个数，称为串的长度。
5、长度为串的长度。长度为0的串称为的串称为空串，它不包括任何字符，上空串，它不包括任何字符，上面（面（4）中的串）中的串d是空串是空串,，(5)中的中的e 是是包含一个空格符的空包含一个空格符的空格串；格串；2）串中所包含的字符可以是串中所包含的字符可以是字母、数字或其他字符，这依字母、数字或其他字符，这依赖于具体计算机所允许的字符赖于具体计算机所允许的字符集。集。4.1 串的逻辑结构及定义串的逻辑结构及定义 一一 串的逻辑结构串的逻辑结构4.1 串的逻辑结构及定义串的逻辑结构及定义一一 串的逻辑结构串的逻辑结构字符在串中的位置：字符在串中的序号（即第字符在串中的位置：字符在串中的序号（即第几个
6、数据元素）几个数据元素）; 子串在串中的位置：子串的第一个字符在主串子串在串中的位置：子串的第一个字符在主串中的位置；中的位置；串相等：两个串的长度相等，且各对应位置处串相等：两个串的长度相等，且各对应位置处的字符都相等；的字符都相等；S=ababcabcac , T=abc 子串子串T 在主串在主串S中的位置为中的位置为3例如例如: :a,b,c,da,b,c,d 四个字符串为四个字符串为a=a=BEIBEI , b= , b=JINGJINGc=c=BEIJINGBEIJING , d= , d=BEI JINGBEI JING它们的长度分别为它们的长度分别为 3,4,7,83,4,7,8
7、a a和和b b都是都是c c和和d d的子串的子串a a在在c c和和d d中的位置都是中的位置都是1 1b b在在c c中的位置是中的位置是4,4,而而b b在在d d中的位置是中的位置是5 5注意注意: :单引号是为字符串区别于变量名而设单引号是为字符串区别于变量名而设, ,它不它不是字符串的内容是字符串的内容4 串的基本操作串的基本操作 串的逻辑结构与线性表一样，都是线性结构。但串的逻辑结构与线性表一样，都是线性结构。但由于串的应用与线性表不同，串的基本操作与线性表由于串的应用与线性表不同，串的基本操作与线性表有很大差别。有很大差别。1）串赋值操作）串赋值操作StrAssign( &T
8、, chars) 功能：将串常量功能：将串常量chars的值赋给串变量的值赋给串变量T；2）复制串操作复制串操作 StrCopy(&T,S) 功能：由串变量功能：由串变量S复制得到串变量复制得到串变量T；4.1 串的逻辑结构及定义 一 串的逻辑结构4.1 串的逻辑结构及定义 一 串的逻辑结构3）判空操作判空操作 StrEmpty(S) 功能：若为空串，则返回功能：若为空串，则返回TRUE，否则返回否则返回FALSE4） 串比较操作串比较操作 StrCompare( S, T) 功能功能:若若ST，则返回值则返回值0；若；若S=T，则返回值则返回值=0； 若若ST，则返回值则返回值05）串置空操
9、作）串置空操作 ClearString( &S) 功能：将功能：将S清为空串清为空串6 6） 求串长操作求串长操作 StrLenght( &S) 功能：返回功能：返回S的元素个数的元素个数,成为串的长度成为串的长度;7） 串连接操作串连接操作 Concat( &T, S1, S2) 功能：由功能：由S1和和S2连接组成的新串，用连接组成的新串，用T返回新串；返回新串；8） 求子串操作求子串操作SubString( &Sub, S, pos, len) 功能：用功能：用Sub返回串返回串S的第的第pos个字符起长度个字符起长度len 为为 子串；子串； 4.1 串的逻辑结构及定义 一 串的逻辑结
10、构4.1 串的逻辑结构及定义串的逻辑结构及定义 一一 串的逻辑结构串的逻辑结构9） 求子串位置操作求子串位置操作Index( S, T, pos ) 功能：返回功能：返回S中第中第pos个字符之后与个字符之后与T相同的子相同的子串的位置，若不存在返回串的位置，若不存在返回010) 串插入操作串插入操作 StrInsert( &S, pos , T) 功能：将串功能：将串T插入到串插入到串S的第的第pos字符之前字符之前11）串删除操作）串删除操作 StrDelete( &S, pos , len) 功能：从串功能：从串S中删除第中删除第pos个字符起长度个字符起长度len 为子串为子串可以看出
11、可以看出:串的操作有一个特点串的操作有一个特点,即对即对一组数据元素一组数据元素进行操作进行操作!4.1 串的逻辑结构及定义 二 串的ADT描述StrAssign( &T, chars)StrCopy(&T,S)StrEmpty(S)StrCompare( S, T)ClearString( &S)StrLenght( &S)Concat( &T, S1, S2)Index( S, T, pos ) 等 4.1 串的逻辑结构及定义串的逻辑结构及定义 二二 串的串的ADT应用举例应用举例上述上述11种基本操作中种基本操作中,下面下面5种操作构成最小操作子集种操作构成最小操作子集:串赋值串赋值 S
12、trAssign; 串比较串比较 StrCompare; 求串长求串长 StrLength; 串联结串联结 Concat; 求子串求子串 Substring; 其它操作可以用其实现其它操作可以用其实现4.1 串的逻辑结构及定义串的逻辑结构及定义 二二 串的串的ADT应用举例应用举例例例1:利用判断串相等利用判断串相等,求串长度求串长度,求子串操作实现定位操作求子串操作实现定位操作.4.1 串的逻辑结构及定义 二 串的ADT应用举例4.2串的表示及实现串的表示及实现 4.2.1串的顺序存储结构及操作虚拟实现串的顺序存储结构及操作虚拟实现一、串的顺序存储结构（串的静态存储结构）一、串的顺序存储结构
13、（串的静态存储结构）1 、存储方式：同一般线性表的顺序存储结构完、存储方式：同一般线性表的顺序存储结构完全相同。用一组地址连续的存储单元存储串的全相同。用一组地址连续的存储单元存储串的字符序列，据预定义的大小，为每个定义的串字符序列，据预定义的大小，为每个定义的串变量分配一个固定长度的存储区变量分配一个固定长度的存储区2 、特点：简单、方便，但空间效率低，插入、特点：简单、方便，但空间效率低，插入、删除要移动字符，时间效率低。删除要移动字符，时间效率低。4.2串的表示及实现串的表示及实现 4.2.1串的顺序存储结构及操作虚拟实现串的顺序存储结构及操作虚拟实现3 虚拟实现虚拟实现注意注意:1 定
14、义了最大串长，则当实际串长超过预定义定义了最大串长，则当实际串长超过预定义长度时，多余部分被舍去，称为截断长度时，多余部分被舍去，称为截断 2 下标为下标为0 的数组分量存放串的实际长度，便的数组分量存放串的实际长度，便于某些操作于某些操作PASCAL 语言用此方式语言用此方式4.2串的表示及实现串的表示及实现 4.2.1串的顺序存储结构及操作虚拟实现串的顺序存储结构及操作虚拟实现此外，还可以用另一种方式表示串长，即以此外，还可以用另一种方式表示串长，即以0 字符作为串的结束标志串长隐含其中（字符作为串的结束标志串长隐含其中（C 语语言的字符串是以这种方式实现）言的字符串是以这种方式实现）.
15、实际的串值存实际的串值存放在下标为放在下标为O-MAXSTRLEN -1 的单元中，而的单元中，而下标为下标为MAXSTRLEN 的单元存放的单元存放 O 字符字符4.2串的表示及实现串的表示及实现 4.2.1串的顺序存储结构及操作虚拟实现串的顺序存储结构及操作虚拟实现4 串的连接操作串的连接操作Concat(&T,S1,S2)的算法示意图的算法示意图S1S2T0 maxstrlen0 maxstrlenS10+S20 MAXSTRLEN 时时截断部分截断部分4.2串的表示及实现串的表示及实现 4.2.1串的顺序存储结构及操作虚拟实现串的顺序存储结构及操作虚拟实现4.2串的表示及实现串的表示及
16、实现 4.2.1串的顺序存储结构及操作虚拟实现串的顺序存储结构及操作虚拟实现5 取子串取子串 有两种求法：其一：已知子串起点和长度；有两种求法：其一：已知子串起点和长度； 其二：已知子串起点和终点；其二：已知子串起点和终点；SSub1 poslen4.2串的表示及实现串的表示及实现 4.2.1串的顺序存储结构及操作虚拟实现串的顺序存储结构及操作虚拟实现6 、子串定位、子串定位模式匹配：在一个主串中，查找子串是否存在，存在返模式匹配：在一个主串中，查找子串是否存在，存在返回子串的位置；不存在返回回子串的位置；不存在返回O 。子串称为。子串称为模式。模式。这个操作用的非常多，如：字处理软件中的这个
17、操作用的非常多，如：字处理软件中的“查找查找”/ “替换替换”实现它的方法也很多，我们介绍思想最简单的一种实现它的方法也很多，我们介绍思想最简单的一种 模式匹配模式匹配的的BF 算法算法基本思想：基本思想：从主串的第从主串的第i 个位置开始，与子串的每个字个位置开始，与子串的每个字符逐个比较，若均相等，则找到；否则，即出现了不符逐个比较，若均相等，则找到；否则，即出现了不等，则说明从该起点不是模式串，换下一个起点，重等，则说明从该起点不是模式串，换下一个起点，重新开始！新开始！第一趟匹配第一趟匹配 a b a b c a b c a c b a bi=3 a b cj=3第二趟匹配第二趟匹配
18、a b a b c a b c a c b a bi=2 a j=1第三趟匹配第三趟匹配 a b a b c a b c a c b a bi=7 a b c a cj=5例例 S=ababcabcac T=abc pos=1 index(S,T,pos)返回值为返回值为64.2串的表示及实现串的表示及实现 4.2.1串的顺序存储结构及操作虚拟实现串的顺序存储结构及操作虚拟实现第四趟匹配第四趟匹配 a b a b c a b c a c b a bi=4 a j=1第五趟匹配第五趟匹配 a b a b c a b c a c b a bi=5 aj=1第六趟匹配第六趟匹配 a b a b c
19、a b c a c b a bi=11 a b c a cj=6匹配成功匹配成功BF算法若不匹配时算法若不匹配时,主串主串回到上一次起始的下一位回到上一次起始的下一位置置,模式串回到起始的第一模式串回到起始的第一个字符个字符!4.2串的表示及实现串的表示及实现 4.2.1串的顺序存储结构及操作虚拟实现串的顺序存储结构及操作虚拟实现int Index(SString S, SString T, int pos ) /返回在主串返回在主串S第第pos个字符后子串个字符后子串T的位置。若不存在，则的位置。若不存在，则函数值为函数值为0。其中，。其中，T非空，非空，1posStLength(S)。 i
20、=pos; j=1; /i=pos,主串匹配的起始位置主串匹配的起始位置 while (i=S0& jT0) return i-T0; /匹配成功，返回子串匹配成功，返回子串T的位置的位置 else return 0; /Index4.2串的表示及实现串的表示及实现 4.2.1串的顺序存储结构及操作虚拟实现串的顺序存储结构及操作虚拟实现算法效率：设主串长度为算法效率：设主串长度为m ，模式串长度为，模式串长度为n ; 找到模式串找到模式串(无回溯无回溯): 最好：开始就是模式串，最好：开始就是模式串，O (n) aaaaabbbbbb aaa 最坏：最后是模式串，最坏：最后是模式串，O ( m
21、 ) cbbbcbcbaaa aaa 找不到模式串找不到模式串(无回溯无回溯):O(m) aaaaaaaaaaaa xyz 4.2串的表示及实现串的表示及实现 4.2.1串的顺序存储结构及操作虚拟实现串的顺序存储结构及操作虚拟实现找到模式串找到模式串(有回溯有回溯):最好：回溯很少，或没回溯最好：回溯很少，或没回溯O( m+n ) abcabcabcaab aab 最坏：回溯很多，或每次都有回溯最坏：回溯很多，或每次都有回溯 O( m* n ) aaaaaaaaaaab aaab 找不到模式串找不到模式串(有回溯有回溯)：O(m*n)aaaaaaaaaaaa aaac4.2串的表示及实现串的表
22、示及实现 4.2.1串的顺序存储结构及操作虚拟实现串的顺序存储结构及操作虚拟实现a 、时间复杂性最坏为（、时间复杂性最坏为（m * n ) ，但一般情况下，但一般情况下为为O( m + n ) ，所以还是一个常用算法。，所以还是一个常用算法。b 、由于有回溯，所以主串输入后必须保存。、由于有回溯，所以主串输入后必须保存。BF 算法的特点算法的特点:4.2串的表示及实现串的表示及实现 4.2.2串的链式存储结构及操作虚拟实现串的链式存储结构及操作虚拟实现一、串的链存储结构（块链式）一、串的链存储结构（块链式）1 、存储方式：同一般线性表的单链存储结构、存储方式：同一般线性表的单链存储结构完全相同
23、。但是，一个结点存储几个数据元素完全相同。但是，一个结点存储几个数据元素有差异！由于串结构中每个数据元素为一个字有差异！由于串结构中每个数据元素为一个字符，所以最直接的链式存储结构是每个结点的符，所以最直接的链式存储结构是每个结点的数据域存放一个字符。举例：数据域存放一个字符。举例：s t r i n g S 2.优点是操作方便；不足之处是存储密度较低。优点是操作方便；不足之处是存储密度较低。所谓存储密度为：所谓存储密度为： 若要将多个字符存放在一个结点中，就可以缓若要将多个字符存放在一个结点中，就可以缓解这个问题。举例：解这个问题。举例：S s t r i n g # # # # 4.2串的
24、表示及实现串的表示及实现 4.2.2串的链式存储结构及操作虚拟实现串的链式存储结构及操作虚拟实现说明说明: (1) 由于串中的字符个数不一定是每个结点由于串中的字符个数不一定是每个结点存放字符个数的整倍数，所以，需要在最后一个结存放字符个数的整倍数，所以，需要在最后一个结点的空缺位置上填充特殊的字符。点的空缺位置上填充特殊的字符。 (2) 这种存储形式这种存储形式优点优点是存储密度高于结点大小是存储密度高于结点大小为为1 的存储形式；的存储形式；不足之处不足之处是做插入、删除字符的是做插入、删除字符的操作时，可能会引起结点之间字符的移动，算法实操作时，可能会引起结点之间字符的移动，算法实现起来
25、比较复杂。现起来比较复杂。 (3)存储密度小存储密度小,运算处理方便运算处理方便,但占用存储量大但占用存储量大; 存储密度大存储密度大,运算处理困难运算处理困难,但占用存储量小但占用存储量小.4.2串的表示及实现串的表示及实现 4.2.1串的顺序存储结构及操作虚拟实现串的顺序存储结构及操作虚拟实现4.2串的表示及实现串的表示及实现 4.2.3串的堆式存储结构及操作虚拟实现串的堆式存储结构及操作虚拟实现一一 串的堆分配存储串的堆分配存储 堆分配存储类似于线性表的顺序存储结构，以一组堆分配存储类似于线性表的顺序存储结构，以一组地址连续的存储单元存放串值字符序列，其存储空间地址连续的存储单元存放串值
26、字符序列，其存储空间是在程序执行过程中动态分配的。是在程序执行过程中动态分配的。maxlen 在这种存储结构下，串操作仍是基于在这种存储结构下，串操作仍是基于“字符序列字符序列的复制的复制”进行的。例如，如串插入操作进行的。例如，如串插入操作StrInsert(S,pos ,T)（将串将串T插入到串插入到串S的第的第pos字符之前）的算法是，为字符之前）的算法是，为串串S重新分配大小等于串重新分配大小等于串S和串和串T长度之和的存储空间，长度之和的存储空间，然后进行将然后进行将S和和T串值复制到新分配存储空间中。串值复制到新分配存储空间中。Typedef struct char *ch; /指
27、针域，指向存放串值的存储空间基址指针域，指向存放串值的存储空间基址 int length; / 整型域：存放串长整型域：存放串长 Hstring;4.2串的表示及实现串的表示及实现 4.2.3串的堆式存储结构及操作虚拟实现串的堆式存储结构及操作虚拟实现堆分配存储的虚拟实现堆分配存储的虚拟实现串赋值算法串赋值算法 Status StrAssign(HString &T, char * chars) /生成一个其值等于串常量生成一个其值等于串常量chars 的串的串T if (T.ch) free(T.ch); /若若T.ch非空，释放非空，释放T.ch所指向的存储空间所指向的存储空间 for (
28、i=0, c=chars; c; +i, +c); /求求chars 的长度的长度i if (!i) T.ch =NULL; T.length=0; /若若i=0,生成空串生成空串T else if (!(T.ch=(char * )malloc(i * sizeof(char) exit (OVERFLOW); T.ch0.i-1=chars0.i-1; T.length=i; return OK; /StrAssign4.2串的表示及实现 4.2.3串的堆式存储结构及操作虚拟实现串常量串常量根据串常量的长度动态分配存储空间根据串常量的长度动态分配存储空间a1 a2anchars0 1 n-
29、1传传递递数数据据T.chT.length0 1 n-1a1 a2 an串赋值操作图示串赋值操作图示n4.2串的表示及实现串的表示及实现 4.2.3串的堆式存储结构及操作虚拟实现串的堆式存储结构及操作虚拟实现int StrCompare(HString S, HString T)/若若ST，则返回值则返回值0；若；若S=T，则返回值则返回值=0；若；若ST，则返回值则返回值0for (i=0; iS.length & iT. length; +i) if (S.chi!=T.chi) return S.chi-T.chi; return S. length-T. length; /StrCom
30、pare 串比较算法串比较算法 4.2串的表示及实现串的表示及实现 4.2.3串的堆式存储结构及操作虚拟实现串的堆式存储结构及操作虚拟实现Status ClearString(HString &S) /将将S清为空串。清为空串。 if (S.ch) free(S.ch); S.ch=NULL; /若若S.ch非空，释放非空，释放S.ch所指向的存储空间，所指向的存储空间，S.ch=null S.length = 0; return OK; /ClearString 串置空算法串置空算法 4.2串的表示及实现串的表示及实现 4.2.3串的堆式存储结构及操作虚拟实现串的堆式存储结构及操作虚拟实现S
31、tatus Concat(HString &T, Hstring S1, HString S2) /用用T返回由返回由S1和和S2连接而成的新串。连接而成的新串。 if (T.ch) free(T.ch); /若若T.ch非空，释放非空，释放T.ch所指向的存储空间所指向的存储空间 if (!(T.ch=(char * )malloc(S1. Length+S2.length ） * sizeof (char) exit (OVERFLOW); T.ch0.S1.length-1=S1.ch0.S1.length-1; T.length=S1.length+S2.length; T.chS1.
32、length.T.length-1=S2.ch0.S2.length-1; return OK; /Concat 串连接算法串连接算法 4.2串的表示及实现串的表示及实现 4.2.3串的堆式存储结构及操作虚拟实现串的堆式存储结构及操作虚拟实现s1.ch0 1 n1-1s1.lengthn1s2.ch0 1 n2-1s2.lengthn2串串s1串串s2进行串的合并进行串的合并s.ch0 1 n1-1 n1 n1+n2-1 s.lengthn1+n2 串连接图示串连接图示 4.2串的表示及实现串的表示及实现 4.2.3串的堆式存储结构及操作虚拟实现串的堆式存储结构及操作虚拟实现求子串算法求子串算
33、法Status SubString(HString &Sub, HString S, int pos, int len) /用用Sub返回串返回串S的第的第pos个字符起长度为个字符起长度为 len的子串。其中，的子串。其中，/1posStrLength(S)posStrLength(S)且且00lenStrLength(S)-pos+1lenStrLength(S)-pos+1。 if (pos S.length | lenS.length-pos+1) return ERROR; /参数不合法参数不合法 if (Sub.ch) free (Sub.ch); / 若若Sub.ch非空，释放非
34、空，释放Sub.ch所指向存储空间所指向存储空间 if (!len) Sub.ch=NULL; Sub.length=0; /若若len=0,Sub为空子串为空子串 else /复制子串复制子串 Sub.ch=(char * ) malloc (len * sizeof(char); Sub.ch0.len-1 =S.chpos-1.pos+len-2; Sub.length=len; return OK; SubString 0 1 Sub.chLen-1Sub.lengthlen动态分配存储空间动态分配存储空间 0 1 pos-1n-1S.lengthnS.ch 0 1 Sub.chLen
35、-1Sub.lengthlen 4.2串的表示及实现串的表示及实现 4.2.3串的堆式存储结构及操作虚拟实现串的堆式存储结构及操作虚拟实现串插入算法串插入算法StrInsert(HString &S,int pos ,HString T) /为串为串S重新分配大小等于串重新分配大小等于串S和串和串T长度之和的存储空间，将长度之和的存储空间，将S和和T串值复制到新分配存储空间中串值复制到新分配存储空间中; if (pos S.length+1) return ERROR; /参数不合法参数不合法 if (T.length) / 若若T非空，为串非空，为串S重新分配存储空间重新分配存储空间,并插入
36、并插入T if (!(S.ch=(char * ) realloc (S.ch, ( S.length+T.length) * sizeof(char) exit(OVERFLOW); /将将S的第的第pos个字符及后面的字符后移，为插入个字符及后面的字符后移，为插入T腾出位置腾出位置for(i=S.length-1;i=pos-1; -i) S.chi+T.length=S.chi; S.chpos-1.pos+T.length-2=T.ch0.T.length-1; /插入插入T S.length+=T.length; return OK; SubStringS.length nS.ch
37、0 1 pos-1 n-1 n+m-1 S.length n+mS.lengthn 0 1 pos-1 n-1 S.chT.chT.lengthm 0 0 1 1 m-1 m-1 为串为串S重新重新分配存储空分配存储空间间,并将并将S复复制到新空间制到新空间将将S的第的第pos个字个字符及后面的字符符及后面的字符后移，为插入后移，为插入T腾出位置腾出位置插入插入T修改串长修改串长 4.2串的表示及实现串的表示及实现 4.2.3串的堆式存储结构及操作虚拟实现串的堆式存储结构及操作虚拟实现本章主要介绍了如下一些基本概念：本章主要介绍了如下一些基本概念：串：串：串（或字符串）（串（或字符串）（Str
38、ing）是由零个或多个字符）是由零个或多个字符组成的有限序列。组成的有限序列。空格串空格串:是由一个或多个空格组成是由一个或多个空格组成,它的长度为串中空它的长度为串中空格字符的个数格字符的个数.空串空串:是零个字符组成的串是零个字符组成的串,其长度等于零其长度等于零.主串和子串：主串和子串：一个串的任意个连续的字符组成的子序一个串的任意个连续的字符组成的子序列称为该串的子串，包含该子串的串称为主串。列称为该串的子串，包含该子串的串称为主串。串的静态存储结构串的静态存储结构：类似于线性表的顺序存储结构，：类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列的用一组地址连续的存
39、储单元存储串值的字符序列的存储方式称为串的顺序存储结构。存储方式称为串的顺序存储结构。本章小结本章小结堆存储结构：堆存储结构：用一组空间足够大的、地址连续的存储用一组空间足够大的、地址连续的存储单元存放串值字符序列，但其存储空间在程序执行单元存放串值字符序列，但其存储空间在程序执行过程中能动态分配的存储方式称为堆存储结构。过程中能动态分配的存储方式称为堆存储结构。串的链式存储结构：串的链式存储结构：类似于线性表的链式存储结构，类似于线性表的链式存储结构，采用链表方式存储串值字符序列的存储方式称为串采用链表方式存储串值字符序列的存储方式称为串的顺序存储结构。的顺序存储结构。除上述基本概念以外，学
40、生还应该了解串的基本运算除上述基本概念以外，学生还应该了解串的基本运算（字符串拷贝（赋值、字符串的联接、求字符串的（字符串拷贝（赋值、字符串的联接、求字符串的长度、子串的查询、字符串的比较）、串的静态存长度、子串的查询、字符串的比较）、串的静态存储结构的表示、串的链式存储结构的表示、串的堆储结构的表示、串的链式存储结构的表示、串的堆存储结构的表示，能在各种存储结构方式中求字符存储结构的表示，能在各种存储结构方式中求字符串的长度、能在各种存储结构方式中利用串的长度、能在各种存储结构方式中利用C语言提语言提供的串函数进行操作。供的串函数进行操作。课堂练习课堂练习一一.单项选择题单项选择题: 1.空
41、串与空格串是相同的空串与空格串是相同的,这种说法这种说法_A. 正确正确 B.不正确不正确2.串是一种特殊的线性表串是一种特殊的线性表,其特殊性体现在其特殊性体现在_A.可以顺序存储可以顺序存储 B.数据元素是一个字符数据元素是一个字符C.可以链接存储可以链接存储 D.数据元素可以是多个字符数据元素可以是多个字符3.设有两个串设有两个串p和和q,求求q在在p中首次出现的位置的中首次出现的位置的运算称作运算称作_A.连接连接 B.模式匹配模式匹配C.求子串求子串 D,求串长求串长4.设串设串s1=ABCDEFG,s2=PQRST,函数函数con(x,y)返返回回x和和y串的连接串串的连接串,su
42、bs(s,i,j)返回串返回串s的从序号的从序号i的的字符开始的字符开始的j个字符组成的子串个字符组成的子串,len(s)返回串返回串s的长的长度度,则则con(subs(s1,2,len(s2),subs(s1,len(s2),2)的结果串是的结果串是_A. BCDEF B. BCDEFGC. BCPQRST D. BCDEFEF二二.填空题填空题1.串的两种最基本的存储方式是串的两种最基本的存储方式是_2.两个串相等地充分必要条件是两个串相等地充分必要条件是_3.空串是空串是_,其长度等于其长度等于_4.空格串是空格串是_,其长度等于其长度等于_5.设设s=I AM A TEACHER,其长度是其长度是_6.设设s1=GOOD,s2= ,s3=BYE!,则则s1,s2和和s3连接连接后的结果是后的结果是_
