《《数据结构(C／C++描述)》-阮宏一-电子教案 第4章 串》由会员分享，可在线阅读，更多相关《《数据结构(C／C++描述)》-阮宏一-电子教案 第4章 串（64页珍藏版）》请在金锄头文库上搜索。
1、,第 4 章 串,4.1 串的定义,4.2 串的存储及基本运算,4.3 串的模式匹配算法,4.4 串的应用,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),StrEmpty (S),StrCompare (S, T),StrLength(S),Concat (
2、&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,1. 串赋值 StrAssign (&T, chars) 初始条件：chars 是字符串常量。 操作结果：把 chars的值赋给 T 。,2. 串复制 StrCopy (&T, S) 初始条件：串 S 存在。 操作结果：由串 S 复制得串 T。,3. 销毁串 DestroyString
3、(&S) 初始条件：串 S 存在。 操作结果：串 S 被释放。,4. 判串是否空 StrEmpty (S) 初始条件：串S 存在。 操作结果：若 S 为空串， 则返回 true， 否则返回 false。, 表示空串，空串的长度为零。,5. 串比较StrCompare (S, T) 初始条件：串 S 和 T 存在。 操作结果：若S T，则返回值 0； 若S T，则返回值 0； 若S T，则返回值 0。,例如：StrCompare(data, state) 0,6. 求串长 StrLength (S) 初始条件：串 S 存在。 操作结果：返回 S 的元素个数， 称为串的长度。,7. 串替换Repl
4、ace (&S, T, V) 初始条件：串S, T 和 V 均已存在， 且 T 是非空串。 操作结果：用 V 替换主串 S 中出现 的所有与（模式串）T 相等的不重叠的子串。,例如：,假设 S = abcaabcaaabca, T = bca ,若 V = x , 则经置换后得到 S = axaxaax ,若 V = bc , 则经置换后得到 S = abcabcaabc,bca,bca,bca,8. 串删除 StrDelete (&S, pos, len) 初始条件：串 S 存在 1posStrLength(S)-len+1。 操作结果：从串 S 中删除第pos个字符 起长度为len的子串。
5、,9. 清空串 ClearString (&S) 初始条件：串 S 存在。 操作结果：将 S 清为空串。,串赋值 StrAssign 串复制 Strcopy 串比较 StrCompare 求串长StrLength 串联接 Concat 求子串 SubString 这 6 种操作构成串类型的最小操作子集。,在上述抽象数据类型定义的 13 种操作中，,即： 这些操作不可能利用其他串操作来实现， 反之，其他串操作（除串清除ClearString和串 销毁DestroyString外）可在这个最小操作子集 上实现。,例如串定位函数： Index ( S, T, pos ) 可利用串比较、求串长和求子串
6、等操作实现。,10. 子串定位 Index (S, T, pos) 初始条件：串S 和 T 存在，T 是非空串， 1posStrLength(S)。 操作结果： 若主串 S 中存在和串 T 值相同 的子串, 则返回它在主串 S 中第pos个 字符之后第 1 次出现的位置 ( 序号 ); 否则函数值为0。,假设 S = abcaabcaaabc , T = bca ,Index(S, T, 1) = 2;,Index(S, T, 3) = 6;,Index(S, T, 8) = 0;,“子串在主串中的位置”意指子串 中的第1个字符在主串中的位序。,利用串比较、求串长和求子串等操作实现串定位函数
7、Index( S, T, pos )。,StrCompare(SubString(S, i, StrLength(T), T ),S 串,T 串,T 串,i,pos,n-m+1,算法的基本思想为：,? 0,i 的最大值,串的逻辑结构和线性表极为相似，区 别仅在于串的数据对象约束为字符集。,串的基本操作和线性表有很大差别。 在线性表的基本操作中，大多以“单个元素”作为操作对象； 在串的基本操作中，通常以“串的整体”作为操作对象。,在程序设计语言中，串只是作为输入或输出的常量出现，则只需存储 此串的串值，即字符序列即可。 但在多数非数值处理的程序中，串也以变量的形式出现。,4.2 串的表示和实现,
8、4.2.1 串的定长顺序存储表示,4.2.2 串的堆分配存储表示,4.2.3 串的块链存储表示,#define MAXSTRLEN 255 / 用户可在255以内定义最大串长 typedef unsigned char SStringMAXSTRLEN + 1; / 0号单元存放串的长度,4.2.1 串的定长顺序存储表示,按这种串的表示方法实现串的运算时，其基本操作为 “字符序列的复制”,串的实际长度可在这个预定义长度的范围内随意设定，超过预定义长度的串值则被舍去，称之为 “截断” 。,特点:,11. 串联接Concat (&T, S1, S2) 初始条件：串 S1 和 S2 存在。 操作结果
9、：用 T 返回由 S1 和 S2 联接而成的新串。,例如： Concate( T, man, kind) 求得 T = mankind,typedef struct char *ch; / 若是非空串，则按串实际长度 / 分配存储区，否则 ch 为NULL int length; / 串长度 HString;,4.2.2 串的堆分配存储表示 动态存储分配,通常，C 语言中提供的串类型就是以这种存储方式实现的。 系统利用函数malloc( ) 和 free( ) 进行串值空间的动态管理，为每一个新产生的串分配一个存储区。 称串值共享的存储空间为“堆”。,C 语言中的串以一个空字符：0为结束符,
10、串长是一个隐含值。,这类串操作实现的算法为: 先为新生成的串分配一个存储空间，然后进行串值的复制。,串S1,串S2,进行串的合并,堆串连接算法图示,Status Concat(HString / ConcatP.94,12. 求子串 SubString (&Sub, S, pos, len) 初始条件： 操作结果： 用 Sub 返回串 S 的第 pos 个字符起 长度为 len 的子串。,串 S 存在，1posStrLength(S) 且 0lenStrLength(S)-pos+1。,例如： SubString( sub, commander , 4, 3),子串为“串”中的一个字符子序列,
11、求得 sub = man ;,SubString( sub, commander , 1, 9),SubString( sub, commander , 9, 1),求得 sub = r ,求得 sub = commander ,SubString(sub, commander , 4, 7) sub = ?,SubString(sub, beijing , 7, 2) = ? sub = ?,SubString(sub,student, 5, 0) = ,起始位置和子串长度之间存在约束关系,长度为 0 的子串为“合法”串,动态分配存储空间,求子串图示,Status SubString(HSt
12、ring , ,if (!(Sub.ch = new charlen) / 按长度分配 return ERROR; for ( i=0; ilen; i+ ) Sub.ch i = S.chpos+i-1; Sub.length = len;,13. 串插入 StrInsert (&S, pos, T) 初始条件：串 S 和 T 存在， 1posStrLength(S)1。 操作结果：在串S 的第pos 个字符之前 插入串 T。,例如：S = chater ，T = rac ， 则执行 StrInsert( S, 4, T ) 之后得到 S = character ,为串S重新分配存储空间,并
13、将S复制到新空间,将S的第pos个字符及后面的字符后移，为插入 T 腾出位置,插入T,修改串长,串插入图示,Status StrInsert ( HString ,void StrInsert (HString / 暂存 S if (tlen0) / T 非空，则为S重新分配空间并插入T ,S.ch = new charslen + tlen ; / 为 S 重新分配空间 for ( i=0, k=0; ipos-1; i+) S.chk+ = S1.chi; / 保留插入位置之前的子串 for ( i=0; itlen; i+) S.ch k+ = T.chi; / 插入T for ( i=
14、pos-1; islen; i+ ) S.chk+ = S1.ch i ; / 复制插入位置之后的子串 S.length = slen+tlen; delete S1.ch;,也可用链表来存储串值。由于串的数据元素是一个字符，它只有 8 位二进制数，因此用链表存储时，通常一个结点中存放的不是一个字符，而是一个子串。,存储密度 =,数据元素所占存储位,实际分配的存储位,4.2.3 串的块链存储表示,讨论：法1存储密度为 ；法2存储密度为 。,块链结构表示串（串的链式存储）示意：,方法1：链表结点（数据域）大小取 1,方法2：链表结点（数据域）大小取 n( 例如 n=4 ),1/2,9/15=3/5,#define CHUNKSIZE 80 / 可由用户定义的块大小 typedef struct Chunk / 结点结构 char chCHUNKSIZE; struct Chunk *next; Chunk; typedef struct / 串的链表结构 Chunk *head, *tail; / 串的头和尾指针 int curlen; / 串的当前长度 LString;,串的块链结构定义,例如: 在编辑系统中，整个文本编辑区可以看成是一个串，每一行是一个子串，构成一个结点。即: 同一行的串用定长结构（80个字符）, 行和行之间用指针联接（块链结构）。,实际应用时，可以根据问题所
