数据结构(C语言描述)第4章-串07课件

1、第4章 串学习要点 掌握串的基本操作以及串操作在存储结构下的实现。 理解串的模式匹配算法。4.1 串的基本概念 基本概念串：是由多个或零个字符组成的有限序列 ，记作 S = a1a2a3an (n=0)，其中 S是串名字，a1a2a3an是串值 ai是串中字符，n是串的长度，表示串中字符数目。空串：零个字符的串称为空串，记作 “”。空格串：由一个或多个空格组成的串。子串：串中任意个连续的字符组成的子序列。主串：包含子串的串。子串在串中的位置：子串的第一个字符在主串中的位置。串相等：串长度相等，且对应位置上字符相等。1. 空串和空格串的不同，例如 和 分别表示长度为1的空格串和长度为0的空串。2

2、. 空串是任意串的子串，任意串是其自身的子串。3. 串的逻辑结构与线性表相似，区别在于串的数据对象约束为字符集，但基本操作和线性表有很大差别。线性表大多以“单个元素”作为操作对象，而串通常以“串的整体”作为操作对象。 4.1.1 串的特性和定义串赋值 StrAssign (&T, chars)：把 chars 赋为 T 的值。串复制 StrCopy (&T, S) ：由串 S 复制得串 T。串判空 StrEmpty (S)：若 S 为空串，则返回 true，否则 返回false。串比较 StrCompare (S, T)：若S T，则返回值 0；若 ST，则返回值 0；若S T，则返回值 0。

3、求串长 StrLength(S)：返回 S 的元素个数。串清除 ClearString (&S)：将S清为空串。串联接 Concat (&T, S1, S2)：用 T 返回由 S1 和 S2联 接而成的新串。 4.1.2 串的抽象数据类型 串的基本操作 求子串 SubString (&Sub, S, pos, len) ：用 Sub 返回串 S 的第 pos 个字符起长度为 len 的子串。 串定位 Index (S, T, pos)：若主串 S 中存在和串 T 值相同的串，则返回它在主串 S 中第pos个字符之后第一次出现的位置。 串替换 Replace (&S, T, V)：用 V 替换主

4、串 S 中出现的所有与（模式串）T相等的不重叠的子串。 串插入 StrInsert (&S, pos, T)：在串S的第pos个字符之前插入串T。 串删除 StrDelete (&S, pos, len)：从串S中删除第pos个字符起长度为len的子串。 串销毁 DestroyString(&S)：串 S 被销毁。 例子例1：StrCompare(data, state) 0。例2：Concat ( T, man, kind)； 求得 T = mankind。例3：SubString( sub, commander , 4, 3)； 求得 sub = man 。例4：假设 S = abcaab

5、caaabc , T = bca ； 则 Index(S, T, 1) = 2; Index(S, T, 3) = 6。例5：假设 S = abcaabcaaabca, T = bca ； V = bc , 则经Replace (S, T, V)置换后得到S = abcabcaabc。例6：S = chater ，T = rac ； 则执行 StrInsert(S, 4, T) 之后得到 S = character 。 基本思想 在主串S中取从第i（i的初值为pos）个字符起、长度和串T相等的子串和串T比较，若相等，则求得函数值为i，否则i值增1至串S中不存在和串T相等的子串为止。 S 串 T

6、 串 T 串iposn-m+1 求串的定位Index(S,T,pos)void StrInsert(String &S,int pos,String T) 在串S的第pos个字符前插入T n=StrLength(S); i=pos; if(i=1 & i=n) 判断插入位置pos是否合法 SubString(sub1,S,1,i-1); SubString(sub2,S,i,n-i+1); Concat(sub3,sub1,T); Concat(S,sub3,sub2); 求串的定位Index(S,T,pos) 定长顺序存储表示 静态分配 每个串预先分配一个固定长度的存储区域 实际串长可在所分

7、配的固定长度区域内变动，超过予定义长度的串值则被舍去，称之为“截断” 用定长数组描述：#define MAXSIZE 100 字符串的最大存储长度 typedef char StringMAXSIZE+1; 使用0号单元存储长度 4.2 串的存储结构及其运算Status Concat(SString S1, SString S2, SString &T) if (S10+S20 = MAXSTRLEN) / 未截断 T1 . S10 = S11 . S10; TS10+1 . S10+S20 = S21 . S20; T0 = S10+S20; uncut = TRUE; else if (S

8、10 MAXSTRLEN) / 截断 T1 . S10 = S11.S10; TS10+1 . MAXSTRLEN =S21 . MAXSTRLEN-S10; T0 = MAXSTRLEN; uncut = FALSE; else T0 . MAXSTRLEN = S10 . MAXSTRLEN; uncut = FALSE; return uncut; 4.2.1 串的静态存储及其实现Status SubString(SString &sub, SString S, int pos, int len ) if(posS0 | lenS0-pos+1) return ERROR; /pos不合

9、法则告警 Sub1len=Spos pos+len-1; Sub0=len; return OK; 串的顺序存储的有关操作特点：1. 实现串的操作有原操作为“字符序列的复制”；2. 在操作中出现串值序列的长度超过上界时，约定用截尾法处理。 求子串函数SubString 以一组地址连续的存储单元存放串值字符序列； 存储空间动态分配，用malloc( )和free( )来管理。为每一个新产生的串分配一个存储区，称串值共享的存储空间为“堆”。 堆分配存储结构有顺序顺序存储结构的特点，处理方便，且操作中对串长没有限制。 串操作的实现：也是基于字符序列的复制。 用堆描述： typedef struct

10、char *ch; / 若非空串，按串长分配空间，否则 ch = NULL int length; /串长度 Hstring 4.2.2 串的动态存储及其实现Status StrInsert ( HString &S, int pos, HString T ) if (posS.length+1) return ERROR; /pos不合法 if(T.length) /T不空，就需要重新分配S空间，以便插入T if (!（S.ch=(char*)realloc(S.ch, (S.length+T.length)*sizeof(char) exit(OVERFLOW); for ( i=S.le

11、ngth-1; i=pos-1; -i ) /为插入T而腾出pos之后的位置 S.chi+T.length = S.chi; /从S的pos位置起全部字符均后移 S.chpos-1pos+T.length-2 = T.ch0T.length-1; /插入T S.length + = T.length; /刷新S串长度 return OK; /StrInsert 用“堆”实现串插入操作ABCDEF S.ch012345678重新分配空间，移动字符在S串的第5个字符之前插入字符串T。（S.length=6，T.lengh=3）T.chXYZ插入前012ABCDEF012345S.chposABCD

12、XY Z E FS.ch012345678插入后FE 串插入操作示意图 串的链式存储方式 结点大小：一个或多个字符 存储密度=串值所占的存储位 / 实际分配的存储位 实际应用时，可以根据问题所需来设置结点的大小 串操作的实现：串值在链式存储结构时操作的实现和线性表类似，对连接操作方便。ABCIheadheadABCDEFGHI# 4.2.3 串的链式存储及其实现#define CHUNKSIZE 80 /可由用户定义的块大小typedef struct Chunk /首先定义结点类型 char ch CHUNKSIZE ; /结点中的数据域 struct Chunk * next ; /结点中

13、的指针域Chunk;typedef struct /其次定义用链式存储的串类型 Chunk *head; /头指针 Chunk *tail; /尾指针 int curLen; /结点个数 Lstring; 串的块链存储方式的描述 求子串位置的定位函数模式匹配：即子串定位运算（Index函数），即如何实现 Index(S,T,pos)函数，也就是在串中寻找子串（第一个字符）在串中的位置。 初始条件：串S和T存在，T是非空串，1posStrLength(s)操作结果：若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置；否则函数值为0。注：S称为被匹配的串（或称主

14、串），T称为模式串。若S包含串T，则称“匹配成功”。否则称 “匹配不成功” 。4.3 串的模式匹配算法1. 将主串的第pos个字符和模式的第1个字符比较： 若相等，继续逐个比较后续字符； 若不等，从主串的下一字符（pos+1）起，重新与第一个字符比较。 2. 直到主串的一个连续子串字符序列与模式相等 。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。否则，匹配失败，返回值 0 。 注：该算法又称为朴素的串匹配算法。4.3.1 朴素的模式匹配算法 匹配过程（已知S是主串，T是模式串，从pos=5的位置开始实现）：第1趟 S a b c d a b b a b a a b a b a b

15、 T a b a第2趟 S a b c d a b b a b a a b a b a b T a b a 第3趟 S a b c d a b b a b a a b a b a b T a b a第4趟 S a b c d a b b a b a a b a b a b T a b a 匹配过程Pos=5int Index(SString S，SString T，int pos) i=pos; j=1; while (i=S0 & jT0) return i-T0; else return 0; 指针i回溯语句i=i-j+2，可以这样理解： 在本趟匹配中，有SiTj，但前面的字符都匹配， 即有Si-1=Tj-1，Si-2=Tj-2，Si-j+1=T1，因此，下一趟匹配时，i应从i-j+1的下一位置开始，即有i=i-j+1+1。 匹配算法 最好的情况时间复杂度为O(n+m