《【教学课件】第4章串(字符串)》由会员分享，可在线阅读，更多相关《【教学课件】第4章串(字符串)（12页珍藏版）》请在装配图网上搜索。
1、第4章 串（字符串）n4.1 串的基本概念 n4.2 串的表示和实现 n4.3 串的模式匹配n4.4 串操作应用举例14.1 串的基本概念n串string（或字符串），是由零个或多个字符组成的有限序列。一般记为：ns=a1a2.an(n=0)串名 串长 空串 主串，子串：串中任意个连续字符组成的子序列2串的例子S1=“ab123”/长度为5的串S2=“100”/长度为3的串S3=/含两个空格字符的串长度为2S4=“”/空串长度为0a=BEI,b=JING,c=BEIJING,d=BEI JINGn串长分别为3,4,7,8,且a,b都是c,d的子串。3na=称为空格串。它的长度为1。由于空格串本
2、身是一个字符，因此它可以出现在其它字符中间，例如“bei jing”。na=称为空串。它的长度为0。空串中无任何字符 称两个串是相等的，当且仅当这两个串的值相等。长度和对应字符 串的操作以“串的整体”作为操作对象13种 操作 5种 最小操作子集4nADT Stringn数据对象：D=ai|ai(-CharacterSet,i=1,2,.,n,n=0n数据关系：R1=|ai-1,ai(-D,i=2,.,nn13种 操作 5种 最小操作子集串的抽象数据类型的定义5n基本操作：nStrAssign(&T,chars)nStrCopy(&T,S)nStrEmpty(S)nStrCompare(S,T)
3、nStrLength(S)nClearString(&S)nConcat(&T,S1,S2)nSubString(&Sub,S,pos,len)nIndex(S,T,pos)nReplace(&S,T,V)nStrInsert(&S,pos,T)nStrDelete(&S,pos,len)nDestroyString(&S)64.2 串的表示及实现n用一组地址连续的存储单元存储串值的字符序列.n#define MAXSTRLEN 255ntypedef unsigned char SStringMAXSTRLEN+1/0号单元存放串长1.定长顺序存储表示7n超过予定义长度的串值则被舍去n串长可
4、用下标为0的数组元素存储,也可在串值后设特殊标记8串联接的实现Concat(&T,S1,S2)n假设S1,S2和T都是SString型的串变量,且串T是由串S1联结串S2得到的,即串T的值的前一段和串S1的值相等,串T的值的后一段和串S2的值相等,则只要进行相应的串值复制操作即可,对超长部分实施截断操作n以下是串联接可能出现的三种情况:nS1,S2串长和小于最大值nS1,S2串长和超过最大串长nS1串长已等于最大串长求子串92.串的堆分配存储表示 C 动态分配一组连续的存储单元malloc 和 free 算法 4.4 串插入 P75 最小操作实现103.串的块链存储表示n可利用空间划分成大小一样的结点(比如说划分成大小为4的结点)，每一个结点有两个域：data域放4个字符，link域放下一个结点的指针。例如,s=abcdefghk存储密度11 4.3 模式匹配4.4 串操作举例12
【教学课件】第4章串(字符串)
