《数据结构(严蔚敏)课件第4章》由会员分享，可在线阅读，更多相关《数据结构(严蔚敏)课件第4章（90页珍藏版）》请在金锄头文库上搜索。
1、第四章 串,【课前思考】,从数据结构的观点来说，串是一种特殊的线性表;但就数据类型而言，串不是线性表。,希望你带着这个问题开始这一章的学习，并能在学完这一章的内容之后能得出正确的结论。,【学习目标】,1. 理解“串”类型定义中各基本操作的特点，并能正确利用它们进行串的其它操作。 2. 理解串类型的各种存储表示方法。 3. 理解串匹配的各种算法。,【重点和难点】,相对于其它各个知识点而言，本章非整个课程的重点，鉴于串已是多数高级语言中已经实现的数据类型，因此本章重点仅在于了解串类型定义中各基本操作的定义以及串的实现方法，并学会利用这些基本操作来实现串的其它操作。本章的难点是理解实现串匹配的KMP
2、算法的思想，但它不属本章学习的基本要求，更不是重点学习内容。,【知识点】,串的类型定义、串的存储表示、串匹配、KMP算法,【学习指南】,虽然目前各常用的高级语言中都已经实现了串类型，但由于它是通过软件实现的，因此作为一个软件工作者还是应该了解串的实现方法。本章没有必须完成的算法设计题，如果有兴趣可以试试以下几个题:4.10，4.11，4.13，4.17，4.18，4.23，4.28,4.30。其中前6个是练习串的基本操作的应用，后2个是和KMP算法相关的练习。,4.1 串类型的定义,4.2 串的表示和实现,4.3 串的模式匹配算法,4.1串的类型定义,一、 基本概念,1串的定义 串( stri
3、ng) 是由零个或多个字符组成的有限序列，记作s=a1a2an，其中s为串的名字，用成对的单引号括起来的字符序列为串的值，但两边的引号不算串值，不包含在串中。ai(1in)可以是字母、数字或其它字符。 n为串中字符的个数，称为串的长度。,2空串 不含任何字符的串称为空串，它的长度n=0，记为s=。,3空格串 含有一个或多个空格的串，称为空格串，它的长度n为空格的个数，一般用符号“ ”表示空串。,串是有限长的字符序列，由一对单引号相括，如: a string,4子串、主串 通常将字符在串中的序号称为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。 若一个串是另一个
4、串中连续的一段，则这个串称为另一个串的子串，而另一个串相对于该串称为主串。例如,串s1=“abcdefg”，s2=“fabcdefghxyz”，则s1为s2的子串，s2相对于s1为主串。,另外，空串是任意串的子串，任意串是自身的子串。若一个串的长度为n，则它的子串数目为 +1，真子串个数为 (除串本身以外的子串都称为真子串)。 当且仅当两个串的值相等时,称这两个串是相等的，即只有当两个串的长度相等, 并且每个对应位置的字符都相等时才相等。,二、串的抽象数据类型的定义如下：,ADT String ,数据对象：,D ai |aiCharacterSet, i=1,2,.,n, n0 ,数据关系：,
5、R1 | ai-1, ai D, i=2,.,n ,基本操作：,StrAssign (&T, chars),StrCopy (&T, S),DestroyString(&S),StrEmpty (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,StrA
6、ssign (&T, chars) 初始条件：chars 是字符串常量。 操作结果：把 chars 赋为 T 的值。,StrCopy (&T, S) 初始条件：串 S 存在。 操作结果：由串 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。
7、,例如：StrCompare(data, state) 0,StrLength(S) 初始条件：串 S 存在。 操作结果：返回 S 的元素个数， 称为串的长度。,Concat(&T,S1,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 个
8、字符起 长度为 len 的子串。,例如： SubString( sub, commander, 4, 3) 求得 sub = man ； SubString( sub, commander, 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) = ,起始位置和子
9、串长度之间存在约束关系,长度为 0 的子串为“合法”串,Index(S,T,pos) 初始条件：串S和T存在，T是非空串， 1posStrLength(S)。 操作结果： 若主串 S 中存在和串 T 值相同 的子串, 则返回它在主串 S 中第pos个字符之后第一次出现的位置；否则函数值为0。,假设 S = abcaabcaaabc, T = bca,Index(S, T, 1) = 2；,Index(S, T, 2) = 6；,Index(S, T, 8) = 0；,“子串在主串中的位置”意指子串 中的第一个字符在主串中的位序。,Replace(&S,T,V) 初始条件：串S, T和 V 均已
10、存在， 且 T 是非空串。 操作结果：用V替换主串S中出现 的所有与（模式串）T 相等的不重叠的子串。,例如：,假设 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
11、 (&S, pos, len) 初始条件：串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) 串比较函数； strlen(str)
12、求串长函数；,例如：C语言函数库中提供下列串处理函数：,在上述抽象数据类型定义的13种操作中， 串赋值StrAssign、串复制Strcopy、 串比较StrCompare、求串长StrLength、 串联接Concat以及求子串SubString 等六种操作构成串类型的最小操作子集。 即：这些操作不可能利用其他串操作来实现， 反之，其他串操作（除串清除ClearString和串 销毁DestroyString外）可在这个最小操作子 集上实现。,例如，可利用串比较、求串长和求子串等操作实现定位函数Index(S,T,pos)。,StrCompare(SubString(S, i, StrLen
13、gth(T),T ) ? 0,S 串,T 串,T 串,i,pos,n-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, S, i, m); if (StrCompare(sub,T) != 0) +i ; else return i ; / w
14、hile / if return 0; / S中不存在与T相等的子串 / Index,又如串的置换函数： Replace(&S,T,V),S 串,T 串,V 串,V 串,pos,pos,sub,i,news 串,sub,串的逻辑结构和线性表极为相似，区别 仅在于串的数据对象约束为字符集。,串的基本操作和线性表有很大差别。,在线性表的基本操作中，大多以“单个元素”作为操作对象； 在串的基本操作中，通常以“串的整体”作为操作对象。,在程序设计语言中，串只是作为输入或输出的常量出现，则只需存储此串的串值，即字符序列即可。但在多数非数值处理的程序中，串也以变量的形式出现。,4.2 串的表示和实现,一、
15、串的定长顺序存储表示,二、串的堆分配存储表示,三、串的块链存储表示,一、串的定长顺序存储表示,与前面所讲的线性表的顺序存储结构类似, 用一组地址连续的存储单元存储串的字符序列。常常将定长顺序串设计成一种结构类型, 串的存储分配是在编译时完成的。,#define MAXSTRLEN 255 / 用户可在255以内定义最大串长 typedef unsigned char Sstring MAXSTRLEN + 1; / 0号单元存放串的长度,或： typedef struct /* 串结构定义 */ char chMAXLEN; int len; SString;,按这种串的表示方法实现的串的运算时，其基本操作为 “字符序列的复制”。,串的实际长度可在这个予定义长度的范围内随意设定，超过予定义长度的串值则被舍去，称之为 “截断” 。,特点:,Status Concat(SString S1, SString S2, SString / Concat,例如：串的联接算法中需分三种情况处理：,T1S10 = S11S10; TS10+1S10+S20 = S
