第5部分串和数组.ppt

1,第5章 串和数组,串也可以看作是一种线性表，只是其操作通常是按成组的元素来进行的。数组可以认为是线性表在维数上的一种拓展。串和数组依然属于线性结构，但在存储结构的实现方面较线性表为复杂。 值得注意的是，串和数组是在高级语言层面已经实现的数据类型，在数据结构中再讨论它们是为了深入理解实现它们的基础技术。 讲授本章课程大约需4课时。,2,5.1 串的定义和操作 5.2 串的表示和实现 5.3 正文模式匹配 5.4 正文编辑串操作应用举例,3,5.1 串的定义和操作,4,串的定义：,串（String ），或称字符串是由零个或多个字符组成的有限序列。记作：,S = a0a1aian-1 （n0）,其中，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),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 和 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 存在，0posStrLength(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(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；,Index(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)。 操作结果：在串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) 输入一个串； puts(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以及求子串SubString 等六种操作构成串类型的最小操作子集。 即：这些操作不可能利用其他串操作来实现， 反之，其他串操作（除串清除ClearString和串 销毁DestroyString外）可在这个最小操作子集 上实现。,26,例如，可利用串比较、求串长和求子串等操作实现定位函数Index(S,T,pos)。,pos= i=n-m SubString(sub, S, i, StrLength(T) StrCompare(sub,T ) ? 0,S 串,T 串,T 串,i,pos,n-m,算法的基本思想为：,27,int Index (String S, String T, int pos) / T为非空串。若主串S中第pos个字符之后存在与 T相等的子串，则返回第一个 这样的子串在S中的位置，否则返回0 if (pos 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中的第一个与T相等子串的位置 / while / if return -1; / S中不存在与T相等的子串 / Index,28,串的逻辑结构和线性表极为相似，区别 仅在于串的数据对象约束为字符集。,串的基本操作和线性表有很大差别。,在线性表的基本操作中，大多以“单个元素”作为操作对象； 在串的基本操作中，通常以“串的整体”作为操作对象。,29,5.2 串的表示和实现,30,在程序设计语言中，串只是作为输入或输出的常量出现，则只需存储此串的串值，即字符序列即可。但在多数非数值处理的程序中，串也以变量的形式出现。,31,一、串的定长顺序存储表示,二、串的堆分配存储表示,三、串的块链存储表示,（在存储结构的层面讨论串的操作）,32,一、串的定长顺序存储表示,如果利用C语言的串类型描述算法，可用一组连续的存储单元存放串的字符序列 ，并以0为结束标志。使用C语言的字符数组来存储字符串。如， char s =“abc“; /字符串的长度为3 char a10; /字符串最大串长为9,33,按这种串的表示方法实现的串的运算时，其基本操作为 “字符序列的复制”,串的实际长度可在这个预定义长度的范围内随意设定，超过预定义长度的串值则被舍去，称之为“截断”,串的定长顺序存储操作特点:,34,void 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' /增加结束符 ,例如：串的联接操作concat,35,void main( ) char s1 =“china“; char s2 =“beijing“; char t113; / 顺序分配定长空间 concat(s1,s2,t1); coutt1endl; ,定长分配体现在调用程序,36,typedef struct char *ch; / 若是非空串，则按串长分配存储区， / 否则ch为NULL int length; / 串长度 HString;,二、串的堆分配存储表示,如果完全用伪码描述算法，可进行类型定义：,37,如果直接用C语言描述算法，可通过函数new和delete为用户进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为“堆”。 本书采用这种方式。,这类串操作实现的常用思路： 先为新生成的串分配一个存储空间，然后进行串值的复制。,38,concat 操作,substring 操作,串的堆分配存储表示实现,39,void concat(char *s1, char *s2, char * ,40,void main( ) char *s1=“china“; char *s2=“beijing“; char *t1; /仅说明类型而不申请空间 concat(s1,s2,t1); coutt1endl; ,调用程序无需预先申请空间,41,void substring(char * ,42,5.3 正文模式匹配,43,先前，曾介绍过串匹配(查找)的操作,INDEX (S, T, pos),在实际应用中，串的匹配查找操作使用的机会很多，现专门讨论该算法。,使用串的有关操作实现了INDEX，但在效率上仍有改进的余地。,44,简单算法（简单的正文模式匹配算法） 以定长顺序结构表示串,演示模型：,匹配成功！,45,int Index_BF(char S, char T, int pos) / 返回子串T在主串S中第pos个字符之后的位置。若不存在， / 则函数值为-1。其中，T非空，0posStrLength(S)-1。 i = pos; j = 0; while ( Si+j!=0 / Index_BF,46,若找到S中所有和模式串T匹配的子串，只需多次调用 Index_BF(char S, char T, int pos) 匹配成功后,下一次的匹配起始位置为i+Strlength(T),Index_BF不是最精巧的模式匹配算法，但比较好理解，适合于一般的使用。,47,5.4 正文编辑 串操作应用举例,48,word 和 WPS 都是常用到的正文编辑工具，可以完成查找、插入、删除和修改等基本操作。,整个文本可以作为一个正文串，每行视为一个子串，文本的基本操作可由字符串的操作来实现。,为方便确定操作的位置，对正文的每一行，建一种索引信息，称为行表。,49,main() float a,b,max; scanf(%f,%f,例如：一段C的源程序正文：,以字符串的形式配合行表来存储,50,200,201,202,正文字符串,行表,208,51,在行内插入或删除若干字符： 如果没有超出行表中该行的长度， 则修改正文的存储区及行表； 如果超出行分配给该行的存储空间， 则需要为该行重新分配正文串的存储空间，并修改行表。,如要插入或删除整行： 则需对行表进行相应的插入或删除。,52,本次课学习要点,53,1. 熟悉串的基本操作的定义，并能利用这些基本操作来实现串的其它各种操作的方法。 2. 熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法。 3. 了解串的堆存储结构以及在其上实现串操作的基本方法。 4. 了解串操作的应用方法和特点。,54,第12次上机作业 实现串的求长度、复制、连接、求字串、模式匹配函数，并用菜单调用。不能使用系统函数。,