第5章串和数组.ppt
《第5章串和数组.ppt》由会员分享,可在线阅读,更多相关《第5章串和数组.ppt(54页珍藏版)》请在三一文库上搜索。
1、1,第5章 串和数组,串也可以看作是一种线性表,只是其操作通常是按成组的元素来进行的。数组可以认为是线性表在维数上的一种拓展。串和数组依然属于线性结构,但在存储结构的实现方面较线性表为复杂。 值得注意的是,串和数组是在高级语言层面已经实现的数据类型,在数据结构中再讨论它们是为了深入理解实现它们的基础技术。 讲授本章课程大约需4课时。,2,5.1 串的定义和操作 5.2 串的表示和实现 5.3 正文模式匹配 5.4 正文编辑串操作应用举例,3,5.1 串的定义和操作,4,串的定义:,串(String ),或称字符串是由零个或多个字符组成的有限序列。记作:,S = a0a1aian-1 (n0),
2、其中,ai属于字符集, n为串的长度,当n=0 时串为空串。,例如: a string 、 a+b 、 ,5,串的基本操作:,StrAssign (&T, chars),StrCopy (&T, S),DestroyString(&S),StrEmpty (S),StrCompare (S, T),StrLength(S),Concat (&T, S1, S2),6,SubString (&Sub, S, pos, len),Index (S, T, pos),Replace (&S, T, V),StrInsert (&S, pos, T),StrDelete (&S, pos, len),
3、ClearString (&S),7,StrAssign (&T, chars) 初始条件:chars 是字符串常量。 操作结果:把 chars 赋为 T 的值。,8,StrCopy (&T, S) 初始条件:串 S 存在。 操作结果:由串 S 复制得串 T。,9,DestroyString (&S) 初始条件:串 S 存在。 操作结果:串 S 被销毁。,10, 表示空串,空串的长度为零,StrEmpty (S) 初始条件:串S存在。 操作结果:若 S 为空串,则返回TRUE, 否则返回 FALSE。, 表示空格,长度为1的字符串,11,StrCompare (S, T) 初始条件:串 S 和
4、 T 存在。 操作结果:若S T,则返回值 0; 若S T,则返回值 0; 若S T,则返回值 0。,例如:StrCompare(data, state) 0,12,StrLength (S) 初始条件:串 S 存在。 操作结果:返回 S 的元素个数, 称为串的长度。,13,Concat (&T, S1, S2) 初始条件:串 S1 和 S2 存在。 操作结果:用 T 返回由 S1 和 S2 联接而成的新串。,例如: Concate( T, man, kind) 求得 T = mankind,14,SubString (&Sub, S, pos, len) 初始条件: 串 S 存在,0posS
5、trLength(S) 且0lenStrLength(S)-pos。 操作结果: 用 Sub 返回串 S 的位置为 pos 起 长度为 len 的子串。,15,例如: SubString( sub, commander, 3, 3) 求得 sub = man ; SubString( sub, commander, 0, 9) 求得 sub = commander ; SubString( sub, commander, 8, 1) 求得 sub = r ;,子串为“串”中的一个字符子序列,16,SubString(sub, commander, 4, 7) sub = ?,SubString
6、(sub, beijing, 7, 2) = ? sub = ?,SubString(student, 5, 0) = ,起始位置和子串长度之间存在约束关系,长度为 0 的子串为“合法”串,17,Index (S, T, pos) 初始条件:串S和T存在,T是非空串, 0posStrLength(S)-1。 操作结果: 若主串 S 中存在和串 T 值相同 的子串, 则返回它在主串 S 中第pos个 字符之后第一次出现的位置; 否则函数值为-1。,18,假设 S = abcaabcaaabca, T = bca,Index(S, T, 1) = 1;,Index(S, T, 3) = 5;,In
7、dex(S, T, 11) = -1;,“子串在主串中的位置”意指子串中的第一个字符在主串中的位序。,19,Replace (&S, T, V) 初始条件: 串S, T和 V 均已存在, 且 T 是非空串。 操作结果: 用V替换主串S中出现 的所有与(模式串)T 相等的不重叠的子串。,20,例如:,假设 S = abcaabcaaabca ,T = bca,若 V = x , 则经置换后得到 S = axaxaax,若 V = bc , 则经置换后得到 S = abcabcaabc,21,StrInsert (&S, pos, T) 初始条件:串S和T存在, 1posStrLength(S)。
8、 操作结果:在串S的第pos个字符之前 插入串T。,例如:S = chater ,T = rac , 则执行 StrInsert(S, 4, T)之后得到 S = character,22,StrDelete (&S, pos, len) 初始条件:串S存在 1posStrLength(S)-len。 操作结果:从串S中删除位置pos 起长度为len的子串。,23,ClearString (&S) 初始条件:串S存在。 操作结果:将S清为空串。,24,对于串的基本操作集可以有不同的定义方法,在使用高级程序设计语言中的串类型时,应以该语言的参考手册为准。,gets(str) 输入一个串; put
9、s(str) 输出一个串; strcat(str1, str2) 串联接函数; strcpy(str1, str2) 串复制函数; strcmp(str1, str2) 串比较函数; strlen(str) 求串长函数; char *strstr(char *s, char *sub) 如果找到子串,返回该位置的指针。如果找不到,则返回空指针。-C语言程序设计-附录C,例如:C语言函数库中提供下列串处理函数:,25,在上述串类型定义的13种操作中, 串赋值StrAssign、串复制Strcopy、 串比较StrCompare、求串长StrLength、 串联接Concat以及求子串SubStr
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数组
链接地址:https://www.31doc.com/p-2550701.html