第5部分串和数组

《第5部分串和数组》由会员分享，可在线阅读，更多相关《第5部分串和数组（54页珍藏版）》请在金锄头文库上搜索。

1、第5部分串和数组Stillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope。有生命必有希望。有生命必有希望v 5.1 串的定义和操作串的定义和操作v 5.2 串的表示和实现串的表示和实现v 5.3 正文模式匹配正文模式匹配v 5.4 正文编辑正文编辑串操作应用举例串操作应用举例25.1 串的定义和操作串的定义和操作3串串的定义：的定义： 串串（String ），或称字符串是由零个或多个字符组成的有限序列。记作：S = a0a1aian-1 （n0） 其中，ai属于字符集， n为串的长度，当n=0 时串为空串。例如: a st

2、ring 、 a+b 、 4串串的基本操作的基本操作： StrAssign (&T, chars) StrCopy (&T, S) DestroyString(&S) StrEmpty (S) StrCompare (S, T) StrLength(S) Concat (&T, S1, S2)5 SubString (&Sub, S, pos, len) Index (S, T, pos) Replace (&S, T, V) StrInsert (&S, pos, T) StrDelete (&S, pos, len) ClearString (&S)6 StrAssign (&T, cha

3、rs) 初始条件：chars 是字符串常量。 操作结果：把 chars 赋为 T 的值。 7 StrCopy (&T, S) 初始条件：串 S 存在。 操作结果：由串 S 复制得串 T。8 DestroyString (&S) 初始条件：串 S 存在。 操作结果：串 S 被销毁。9 表示空串，空串的长度为零 StrEmpty (S) 初始条件：串S存在。 操作结果：若 S 为空串，则返回TRUE， 否则返回 FALSE。 表示空格，长度为1的字符串10 StrCompare (S, T)初始条件：串 S 和 T 存在。操作结果：若S T，则返回值 0； 若S T，则返回值 0； 若S T，则返

4、回值 0。例如：例如：StrCompare(data, state) 011 StrLength (S) 初始条件：串 S 存在。 操作结果：返回 S 的元素个数， 称为串的长度。12 Concat (&T, S1, S2) 初始条件：串 S1 和 S2 存在。 操作结果：用 T 返回由 S1 和 S2 联接而成的新串。例如例如： Concate( T, man, kind) 求得 T = mankind13 SubString (&Sub, S, pos, len)初始条件： 串 S 存在，0posStrLength(S) 且0lenStrLength(S)-pos。操作结果： 用 Sub

5、返回串 S 的位置为 pos 起 长度为 len 的子串。14例如：例如： SubString( sub, commander, 3, 3) 求得 sub = man ； SubString( sub, commander, 0, 9)求得 sub = commander ； SubString( sub, commander, 8, 1)求得 sub = r ；子串子串为“串”中的一个字符子序列15SubString(sub, commander, 4, 7) sub = ? SubString(sub, beijing, 7, 2) = ? sub = ?SubString(student

6、, 5, 0) = 起始位置和子串长度之间存在约束关系长度为 0 的子串为“合法”串串16 Index (S, T, pos)初始条件：串S和T存在，T是非空串， 0posStrLength(S)-1。操作结果： 若主串 S 中存在和串 T 值相同 的子串, 则返回它在主串 S 中第pos个 字符之后第一次出现的位置； 否则函数值为-1。 17假设 S = abcaabcaaabca, T = bca Index(S, T, 1) = 1；Index(S, T, 3) = 5；Index(S, T, 11) = -1； “子串在主串中的位置子串在主串中的位置”意指子串中的第一个字符在主串中的位

7、序位序。18 Replace (&S, T, V) 初始条件： 串S, T和 V 均已存在， 且 T 是非空串。 操作结果： 用V替换主串S中出现 的所有与（模式串）T 相等的不重叠的子串。19例如：例如：假设 S = abcaabcaaabca ，T = bca若 V = x ， 则经置换后得到 S = axaxaax若 V = bc ， 则经置换后得到 S = abcabcaabc20 StrInsert (&S, pos, T)初始条件：串S和T存在， 1posStrLength(S)。操作结果：在串S的第pos个字符之前 插入串T。例如：例如：S = chater ，T = rac ，

8、 则执行 StrInsert(S, 4, T)之后得到 S = character21 StrDelete (&S, pos, len)初始条件：串S存在 1posStrLength(S)-len。操作结果：从串S中删除位置pos 起长度为len的子串。 22 ClearString (&S) 初始条件：串S存在。 操作结果：将S清为空串。23 对于串的基本操作集可以有不同的定义方法，在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准以该语言的参考手册为准。 gets(str) 输入一个串； puts(str) 输出一个串； strcat(str1, str2) 串联接函数； str

9、cpy(str1, str2) 串复制函数； strcmp(str1, str2) 串比较函数； strlen(str) 求串长函数； char *strstr(char *s, char *sub) 如果找到子串，返回该位置的指针。如果找不到，则返回空指针。-C语言程序设计-附录C例如：C语言函数库中提供下列串处理函数：24 在上述串类型定义的13种操作中， 串赋值串赋值StrAssign、串复制、串复制Strcopy、 串比较串比较StrCompare、求串长、求串长StrLength、 串联接串联接Concat以及求子串以及求子串SubString 等六种操作构成串类型的等六种操作构成串

10、类型的最小操作子集最小操作子集。 即：这些操作不可能利用其他串操作来实现， 反之，其他串操作（除串清除ClearString和串 销毁DestroyString外）可在这个最小操作子集 上实现。25 例如，可利用串比较、求串长和求子串等操作实现定位函数Index(S,T,pos)。 pos= i 0) n = StrLength(S); m = StrLength(T); i = pos; while ( i = n-m+1) SubString (sub, S, i, m); if (StrCompare(sub,T) != 0) +i ; else return i ; / S中的第一个与

11、T相等子串的位置 / while / if return -1; / S中不存在与T相等的子串 / Index27 串的逻辑结构和线性表极为相似，区别区别仅在于串的数据对象约束为字符集。 串的基本操作和线性表有很大差别。串的基本操作和线性表有很大差别。 在线性表的基本操作中，大多以大多以“单个单个元素元素”作为操作对象作为操作对象； 在串的基本操作中，通常以通常以“串的整体串的整体”作为操作对象作为操作对象。285.2 串的表示和实现串的表示和实现29 在程序设计语言中，串只是作为输入或输出的常量出现，则只需存储此串的串值，即字符序列即可。但在多数非数值处理的程序中，串也以变量的形式出现。30

12、一、串的定长顺序存储表示一、串的定长顺序存储表示二、串的堆分配存储表示二、串的堆分配存储表示三、串的块链存储表示三、串的块链存储表示（在存储结构的层面讨论串的操作）31一、串的定长顺序存储表示一、串的定长顺序存储表示 如果利用C语言的串类型描述算法，可用一组连续的存储单元存放串的字符序列 ，并以0为结束标志。使用C语言的字符数组来存储字符串。如， char s =abc; /字符串的长度为3 char a10; /字符串最大串长为9 32u 按这种串的表示方法实现的串的运算时，其基本操作为 “字符序列的复制复制”u串的实际长度可在这个预定义长度的范围内随意设定，超过预定义长度的串值则被舍去，称

13、之为“截断” 串的定长顺序存储操作串的定长顺序存储操作特点特点: :33void concat_sq(char s1 ,char s2 ,char t ) int j=0, k=0; while(s1j!=0) tk+=s1j+; /复制S1 j=0; while(s2j!=0) tk+=s2j+; /接着复制S2 tk=0; /增加结束符例如：串的联接操作例如：串的联接操作concat34void main( )char s1 =china;char s2 =beijing;char t113; / 顺序分配定长空间concat(s1,s2,t1);coutt1endl;定长分配定长分配体现

14、在调用程序35 typedef struct char *ch; / 若是非空串，则按串长分配存储区， / 否则ch为NULL int length; / 串长度 HString;二、串的堆分配存储表示二、串的堆分配存储表示 如果完全用伪码描述算法，可进行类型定义：36 如果直接用C语言描述算法，可通过函数new和delete为用户进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为“堆堆”。 本书采用这种方式。本书采用这种方式。 这类串操作实现的常用思路：先为新生成的串分配一个存储空间，然后进行串值的复制。37concat 操作操作substring 操作操作串的

15、堆分配存储表示实现串的堆分配存储表示实现38void concat(char *s1, char *s2, char *&t) int i=0, j=0; t=new charstrlen(s1)+strlen(s2)+1; / 为t t分配堆空间 while(ti=s1i)!=0) i+; while(ti=s2j)!=0) i+; j+; 39void main( ) char *s1=china; char *s2=beijing; char *t1; /仅说明类型而不申请空间 concat(s1,s2,t1); coutt1endl;调用程序无需预先申请空间40 void substr

16、ing(char *&sub, char *s, int pos, int len) char *p; int k, slen=strlength(s); if (posslen-1|lenslen-pos) ERRORMESSAGE(“参数不合法”); sub=new charlen+1; /为sub分配堆空间 p=s+pos-1; k=len; while(k) *sub+=*p+; k-; *sub=0; sub=sub-len; 415.3 正文模式匹配正文模式匹配42 先前，曾介绍过串匹配(查找)的操作 INDEX (S, T, pos) 在实际应用中，串的匹配查找操作使用的机会很多

17、，现专门讨论该算法。 使用串的有关操作实现了INDEX，但在效率上仍有改进的余地。43 简单算法简单算法（简单的正文模式匹配算法） 以定长顺序结构表示串a b a a ca b a b a a c b c a a b a b a a c b aa b a a ca b a a cST演示模型：匹配成功！匹配成功！44int Index_BF(char S, char T, int pos) / 返回子串T在主串S中第pos个字符之后的位置。若不存在， / 则函数值为-1。其中，T非空，0posStrLength(S)-1。 i = pos; j = 0; while ( Si+j!=0 & T

18、j!=0) if (Si+j = Tj) j+; / 继续比较后继字符 else i +; j = 0; / 重新开始新一轮的匹配 if ( Tj!=0) return i; else return -1; / Index_BF45u 若找到S中所有和模式串T匹配的子串，只需多次调用Index_BF(char S, char T, int pos) 匹配成功后,下一次的匹配起始位置为i+Strlength(T) u Index_BF不是最精巧的模式匹配算法，但比较好理解，适合于一般的使用。465.4 正文编辑正文编辑 串操作应用举例串操作应用举例47 word 和 WPS 都是常用到的正文编辑

19、工具，可以完成查找、插入、删除和修改等基本操作。 整个文本可以作为一个正文串，每行视为一个子串，文本的基本操作可由字符串的操作来实现。 为方便确定操作的位置，对正文的每一行，建一种索引信息，称为行表行表。48 main() float a,b,max; scanf(%f,%f,&a,&b); if ab max=a; else max=b; ;例如：一段C的源程序正文：以字符串的形式配合行表来存储49行号起始地址长度1002008101208171022252410324917104266151052813200 ; ;b=xamesle ;a=xambafi ;)b&,a&, f%,f% (

20、fnacs ;xam,b,ataolf )(niam201 202正文字符串行表20850 在行内插入或删除若干字符：在行内插入或删除若干字符： 如果没有超出行表中该行的长度，则修改正文的存储区及行表； 如果超出行分配给该行的存储空间，则需要为该行重新分配正文串的存储空间，并修改行表。如要插入或删除整行：如要插入或删除整行：则需对行表进行相应的插入或删除。 51本本次课次课学习要点学习要点52 1. 熟悉熟悉串的基本操作基本操作的定义，并能利用这些基本操作来实现串的其它各种操作串的其它各种操作的方法。 2. 熟练掌握熟练掌握在串的定长顺序存储结构定长顺序存储结构上实现串的各种操作的方法。 3. 了解了解串的堆存储结构堆存储结构以及在其上实现串操作的基本方法。 4. 了解了解串操作的应用方法和特点。 53 第12次上机作业实现串的求长度、复制、连接、求字串、模式匹配函数，并用菜单调用。不能使用系统函数。 54