《第四讲串的表示和实现ppt课件》由会员分享，可在线阅读，更多相关《第四讲串的表示和实现ppt课件（57页珍藏版）》请在金锄头文库上搜索。
1、4.1 串的串的笼统笼统数据数据类类型的定型的定义义4.2 串的表示和串的表示和实现实现4.3 串的方式匹配算法串的方式匹配算法4.1 串的笼统数据类型的定义如下：串的笼统数据类型的定义如下：ADT String 数据对象：D ai |aiCharacterSet, i=1,2,.,n, n0 数据关系：数据关系：R1 | ai-1, ai D, i=2,.,n 串是有限串是有限长的字符序的字符序列，由一列，由一对单引号相引号相括，如括，如: a string 根本操作： StrAssign (&T, chars) StrCopy (&T, S) DestroyString(&S) StrEm
2、pty (S) StrCompare (S, T) StrLength(S) Concat (&T, S1, S2)SubString (&Sub, S, pos, len) Index (S, T, pos) Replace (&S, T, V)StrInsert (&S, pos, T) StrDelete (&S, pos, len) ClearString (&S) ADT String StrAssign (&T, chars) 初始条件：chars 是字符串常量。 操作结果：把 chars 赋为 T 的值。 StrCopy (&T, S) 初始条件：串 S 存在。 操作结果：由串
3、S 复制得串 T。 DestroyString (&S) 初始条件：串 S 存在。 操作结果：串 S 被销毁。 StrEmpty(S)初始条件：串S存在。操作结果：假设 S 为空串，那么前往TRUE， 否那么前往 FALSE。 表示空串，空串的长度为零。 StrCompare(S,T)初始条件：串 S 和 T 存在。操作结果：假设S T，那么前往值 0； 假设S T，那么前往值 0； 假设S T，那么前往值 0。例如：例如：StrCompare(data, state) 0 StrLength(S) 初始条件：串S存在。 操作结果：前往 S 的元素个数 称为串的长度。 Concat(&T,S1
4、,S2) 初始条件：串 S1 和 S2 存在。 操作结果：用 T 前往由 S1 和 S2 联接而成的新串。例如：例如： Concate( T, man, kind) 求得求得 T = mankind SubString (&Sub, S, pos, len)初始条件： 串 S 存在，1posStrLength(S) 且0lenStrLength(S)-pos+1。操作结果： 用 Sub 前往串 S 的第 pos 个字符起 长度为 len 的子串。例如：例如： SubString( sub, commander , 4, 3) 求得求得 sub = man ； SubString( sub, c
5、ommander , 1, 9)求得求得 sub = commander ； SubString( sub, commander , 9, 1)求得求得 sub = r ；子串子串为“串串 中的一个字符子序列中的一个字符子序列SubString(sub, commander, 4, 7) sub = ? SubString(sub, beijing, 7, 2) = ? sub = ?SubString(student, 5, 0) = 起始位置和子串起始位置和子串长度之度之间存在存在约束关系束关系长度度为 0 的子串的子串为“合法串合法串 Index(S,T,pos)初始条件：串S和T存在，
6、T是非空串， 1posStrLength(S)。操作结果： 假设主串 S 中存在和串 T 值一样 的子串, 那么前往它在主串 S 中第pos个 字符之后第一次出现的位置； 否那么函数值为0。 假设 S = abcaabcaaabc, T = bca Index(S, T, 1) = 2；Index(S, T, 3) = 6；Index(S, T, 8) = 0； “子串在主串中的位置意指子串中的第一个字符在主串中的位序。 Replace(&S,T,V) 初始条件：串S, T和 V 均已存在 ， 且 T 是非空串。 操作结果：用V交换主串S中出现 的一切与方式串T 相等的不重叠的子串。例如：假设
7、 S = abcaabcaaabca，T = bca假设 V = x， 那么经置换后得到 S = axaxaax假设 V = bc， 那么经置换后得到 S = abcabcaabc StrInsert (&S, pos, T)初始条件：串初始条件：串S和和T存在，存在， 1posStrLength(S)1。操作操作结结果：在串果：在串S的第的第pos个字个字符之前符之前 插入串插入串T。例如：例如：S = chater，T = rac， 那么那么执行行 StrInsert(S, 4, T)之后得到之后得到 S = character StrDelete (&S, pos, len)初始条件：串
8、初始条件：串S存在存在 1posStrLength(S)-len+1。操作操作结结果：从串果：从串S中中删删除第除第pos个字符个字符 起起长长度度为为len的子串。的子串。 ClearString(&S) 初 始 条 件 ： 串 S存 在 。 操作结果：将S清为空串。 对于串的根本操作集可以有不同的定义方法，在运用高级程序设计言语中的串类型时，应以该言语的参考手册为准。 gets(str) 输入一个串； puts(str) 输出一个串； strcat(str1, str2) 串联接函数； strcpy(str1, str2, k) 串复制函数； strcmp(str1, str2) 串比较函
9、数； strlen(str) 求串长函数；例如：C言语函数库中提供以下串处置函数：在上述笼统数据类型定义的13种操作中， 串赋值StrAssign、串复制Strcopy、 串比较StrCompare、求串长StrLength、 串联接Concat以及求子串SubString 等六种操作构成串类型的最小操作子集。 即：这些操作不能够利用其他串操作来实现， 反之，其他串操作除串去除ClearString和串 销毁DestroyString外可在这个最小操作子 集上实现。 例如，可利用串比较、求串长和求子串等操作实现定位函数Index(S,T,pos)。 StrCompare(SubString(S
10、, i, StrLength(T),T ) ? 0 S 串 T 串 T 串iposn-m+1算法的根本思想算法的根本思想为：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
11、, S, i, m); if (StrCompare(sub,T) != 0) +i ; else return i ; / while / if return 0; / S中不存在与中不存在与T相等的子串相等的子串 / Index又如串的置换函数： S 串 T 串 V 串 V 串pospos subinews 串sub 串的逻辑构造和线性表极为类似，区别仅在于串的数据对象约束为字符集。 串的根本操作和线性表有很大差别。 在线性表的根本操作中，大多以“单个元素作为操作对象； 在串的根本操作中，通常以“串的整体作为操作对象。 在程序设计言语中，串只是作为输入或输出的常量出现，那么只需存储此串的串
12、值，即字符序列即可。但在多数非数值处置的程序中，串也以变量的方式出现。4.2 串的表示和实现串的表示和实现一、串的定一、串的定长顺序存序存储表示表示二、串的堆分配存二、串的堆分配存储表示表示三、串的三、串的块链存存储表示表示 #define MAXSTRLEN 255 / 用用户户可在可在255以内定以内定义义最大串最大串长长 typedef unsigned char Sstring MAXSTRLEN + 1; / 0号号单单元存放串的元存放串的长长度度一、串的定长顺序存储表示一、串的定长顺序存储表示 按这种串的表示方法实现的串的运算时，其根本操作为 “字符序列的复制。 串的串的实实践践长
13、长度可在度可在这这个予定个予定义长义长度的范度的范围围内随意内随意设设定，超越予定定，超越予定义义长长度的串度的串值值那么被舍去，称之那么被舍去，称之为为“截断截断 。特点特点: Status Concat(SString S1, SString S2, SString &T) / 用用T前往由前往由S1和和S2联联接而成的新串。假接而成的新串。假设设未截未截断断, 那么前往那么前往TRUE，否那么，否那么FALSE。 return uncut; / Concat例如：串的联接算法中需分三种情况处置：例如：串的联接算法中需分三种情况处置： T1.S10 = S11.S10; TS10+1.S1
14、0+S20 = S21.S20; T0 = S10+S20; uncut = TRUE; if (S10+S20 = MAXSTRLEN) / 未截断未截断 else if (S10 MAXSTRSIZE) / 截断截断 else / 截断截断(仅仅取取S1)T1.S10 = S11.S10;TS10+1.MAXSTRLEN = S21.MAXSTRLENS10;T0 = MAXSTRLEN; uncut = FALSE; T0.MAXSTRLEN = S10.MAXSTRLEN; / T0 = S10 = MAXSTRLEN uncut = FALSE; typedef struct cha
15、r *ch; / 假假设设是非空串，那么按串是非空串，那么按串长长分配存分配存储储区，区， / 否那么否那么ch为为NULL int length; / 串串长长度度 HString;二、串的堆分配存储表示二、串的堆分配存储表示 通常，C言语中提供的串类型就是以这种存储方式实现的。系统利用函数malloc( )和free( )进展串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为“堆。 C言语中的串以0为终了符， 串长是一个隐含值。 串衔接操作实现的算法为： 先为新生成的串分配一个存储空间，然后 进展串的复制。Status Concat(HString &T, HSt
16、ring S1, HString S2) / 用用T前往由前往由S1和和S2联接而成的新串联接而成的新串 if (T.ch) free(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.length.T.length-1 = S2.ch0.S2.length-1; return OK;
17、/ Concat Status SubString(HString &Sub, HString S, int pos, int len) / 用Sub前往串S的第pos个字符起长度为len的子串 if (pos S.length | len S.length-pos+1) return ERROR; if (Sub.ch) free (Sub.ch); / 释放旧空间 if (!len) Sub.ch = NULL; Sub.length = 0; / 空子串 else / 完好子串 return OK; / SubString Sub.ch = (char *)malloc(len*size
18、of(char); Sub.ch0.len-1 = Spos-1.pos+len-2; Sub.length = len;三、串的块链存储表示三、串的块链存储表示 用链表来存储串值，由于串的数据元素是一个字符，它只需 8 位二进制数，因此用链表存储时，通常一个结点中存放的不是一个字符，而是一个子串。存存储密度密度 = 数据元素所占存储位实践分配的存储位 #define CHUNKSIZE 80 / 可由用户定义的块大小 typedef struct Chunk / 结点构造 char chCUNKSIZE; struct Chunk *next; Chunk; typedef struct /
19、 串的链表构造 Chunk *head, *tail; / 串的头和尾指针 int curlen; / 串的当前长度 LString; 例如: 在文本编辑程序中，整个文本编辑区可以看成是一个串，每一行是一个子串，构成一个结点。即: 同一行的串用定长构造(80个字符), 行和行之间用指针相联接。实践运用时，可以根据问题所需来设置结点的大小。 这是串的一种重要操作，很多 软件，假设有“编辑菜单项的话， 那么其中必有“查找子菜单项。4.3串的方式匹配算法串的方式匹配算法初始条件：串S和T存在，T是非空串， 1posStrLength(S)。操作结果：假设主串S中存在和串T值相 同的子串前往它在主串S
20、中 第pos个字符之后第一次出 现的位置；否那么函数 值为0。 首先，回想一下串匹配(查找)的定义:INDEX (S, T, pos) 下面讨论以定长顺序构造表示串时的几种算法。一、一、简单算法算法二、首尾匹配算法三、三、KMP(D.E.Knuth, V.R.Pratt,KMP(D.E.Knuth, V.R.Pratt, J.H.Morris) J.H.Morris) 算法算法第一趟匹配第一趟匹配 a b a b c a b c a c b a bi=1 t = a b c a cSubch!=t 第二趟匹配第二趟匹配 a b a b c a b c a c b a bi=2第三趟匹配第三趟匹
21、配 a b a b c a b c a c b a bi=3第四趟匹配第四趟匹配 a b a b c a b c a c b a bi=4第五趟匹配第五趟匹配 a b a b c a b c a c b a bi=5第六趟匹配第六趟匹配 a b a b c a b c a c b a bi=6 t = a b c a c匹配胜利Subch!=t t = a b c a c t = a b c a cSubch!=t Subch!=t Subch!=t t = a b c a c t = a b c a cint Index(SString S, SString T, int pos) / 前往
22、子串前往子串T在主串在主串S中第中第pos个字符之后的位置。个字符之后的位置。假假设设不存在，不存在， / 那么函数那么函数值为值为0。其中，。其中，T非空，非空，1posStrLength(S)。 i = pos; j = 1; while (i = S0 & j T0) return i-T0; else return 0; / Index一、一、简单算法算法 先比较方式串的第一个字符， 再比较方式串的最后一个字符， 最后比较方式串中从第二个到 第n-1个字符。二、首尾匹配算法 int Index_FL(SString S, SString T, int pos) sLength = S0
23、; tLength = T0; i = pos; patStartChar = T1; patEndChar = TtLength; while (i = sLength tLength + 1) if (Si != patStartChar) +i; /重新重新查查找匹配起始点找匹配起始点 else if (Si+tLength-1 != patEndChar) +i; / 方式串的方式串的“尾字符不匹配尾字符不匹配 else return 0; / 检查检查中中间间字符的匹配情况字符的匹配情况 k = 1; j = 2; while ( j tLength & Si+k = Tj) +k;
24、 +j; if ( j = tLength ) return i; else +i; / 重新开场下一次的匹配检测KMP算法的时间复杂度可以到达O(m+n) 当当 Si Tj 时时， 曾曾经经得到的得到的结结果：果： Si-j+1.i-1 = T1.j-1 假假设设知知 T1.k-1 = Tj-k+1.j-1 那么有那么有 Si-k+1.i-1 = T1.k-1三、三、KMP(D.E.Knuth, V.R.Pratt,KMP(D.E.Knuth, V.R.Pratt, J.H.Morris) J.H.Morris) 算法算法定定义：方式串的：方式串的next函数函数 int Index_KMP
25、(SString S, SString T, int pos) / 1posStrLength(S) i = pos; j = 1; while (i = S0 & j T0) return i-T0; / 匹配匹配胜胜利利 else return 0; / Index_KMP这实践上也是一个匹配的过程，不同在于：主串和方式串是同一个串求next函数值的过程是一个递推过程，分析如下:知：next1 = 0；假设：nextj = k；又 Tj = Tk那么： nextj+1 = k+1假设： Tj Tk那么需往前回朔，检查 Tj = T ？ void get_next(SString &T, i
26、nt &next ) / 求方式串求方式串T的的next函数函数值值并存入数并存入数组组next i = 1; next1 = 0; j = 0; while (i T0) if (j = =0 | Ti = Tj) +i; +j; nexti = j; else j = nextj; / get_next还有一种特殊情况需求思索：例如： S = aaabaaabaaabaaabaaab T = aaaabnextvalj=00004nextj=01234 void get_nextval(SString &T, int &nextval) i = 1; nextval1 = 0; j = 0
27、; while (i T0) if (j = 0 | Ti = Tj) +i; +j; if (Ti != Tj) nexti = j; else nextvali = nextvalj; else j = nextvalj; / get_nextval 1. 1. 熟习串的七种根本操作的定义，熟习串的七种根本操作的定义，并能利用这些根本操作来实现串的并能利用这些根本操作来实现串的其它各种操作的方法。其它各种操作的方法。 2. 2. 熟练掌握在串的定长顺序存储熟练掌握在串的定长顺序存储构造上实现串的各种操作的方法。构造上实现串的各种操作的方法。 3. 3. 了解串的堆存储构造以及在其了解串的堆存储构造以及在其上实现串操作的根本方法。上实现串操作的根本方法。本章学习要点本章学习要点 4. 4. 了解串匹配的了解串匹配的KMPKMP算法，熟习算法，熟习NEXTNEXT函数的定义，学会手工计算给定函数的定义，学会手工计算给定方式串的方式串的NEXTNEXT函数值和改良的函数值和改良的NEXTNEXT函函数值。数值。5. 5. 了解串操作的运用方法和特点。了解串操作的运用方法和特点。
