《串的基本概念.ppt》由会员分享，可在线阅读，更多相关《串的基本概念.ppt（26页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、串的基本概念现在学习的是第1页，共26页串的抽象数据定义：P71对于串的基本操作集可以有不同的定义方法，读者在使用高级语言中的串类型时，应该以语言的参考手册为准。l 定位算法（P72） Index（S，T，pos）现在学习的是第2页，共26页4.2 4.2 串的表示和实现串的表示和实现对串的存储方式取决于我们对串所进行的运算，如果在程序设计语言中，串的运算只是作为输入或输出的常量出现，则此时只需存储该串的字符序列，这就是串值的存储。此外，一个字符序列还可赋给一个串变量，操作运算时通过串变量名访问串值。串的3种机内表示方式：v定长顺序存储表示v堆分配存储表示v串的块链存储表示现在学习的是第3页，
2、共26页4.2.1 4.2.1 定长顺序存储表示定长顺序存储表示实现：用一组地址连续的存储单元存储串值的字符序列。存储表示#define MAXSTRLEN 255Typedef unsigned char StringMAXSTRLEN+1v截断超过与定义长度的串值被舍去。v串长的两种表示：下标为0的分量存放串的实际长度，如：pascal在串尾加一个不计入串长的结束标记符。如：C中的0现在学习的是第4页，共26页l串连接算法Concat（&T，S1，S2）Status Concat(SString &T, SString S1,SString S2)/用T返回由S1和S2联接而成的新串。若未
3、截断，则返回TRUE，否则FALSE。S0/保存串的长度,有三种情况(1)S10+S20=MAXSTRLEN;(2)S10MAXSTRLEN;(3)S10=MAXSTRLENIf(S10+S20=MAXSTRLEN/未截断T1.S10=S11.S10;TS10+1.S10+S20=S21.S20;T0=S10+S20;uncut=TRUE;else if(S10MAXSTRLEN)/截断T1.S10=S11.S10;TS10+1.MAXSTRLEN=S21.MAXSTRLEN-S10;T0=MAXSTRLEN;uncut=FALSE;else/截断，仅取S1T0.MAXSTRLEN=S10.M
4、AXSTRLEN;uncut=FALSE;return uncut;现在学习的是第5页，共26页l求子串算法SubString（&Sub，S，pos，len）v串操作特点：l原操作为字符序列的复制l操作的时间复杂度基于复制序列的长度l截断处理Status SubString(SString &Sub,SString S,int pos,int len)/用Sub返回串的第pos个字符起长度为len的子串，其中/1=pos=StrLength(s)&0=len=StrLength(s)-pos+1if(posS0|lenS0-pos+1 return ERROR;Sub1.len=Spos.po
5、s+len-1;Sub0=len;return OK;现在学习的是第6页，共26页v串的动态存储结构串的动态存储结构串的各种运算与串的存储结构有着很大的关系，在随机取子串时，顺序存储方式操作起来比较方便，而对串进行插入、删除等操作时，就会变得很复杂。因此，有必要采用串的动态存储方式。串的动态存储方式采用堆存储结构和链式存储结构两种形式：4.2.24.2.2堆存储结构堆存储结构v特点l仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配的。l在C语言中，存在一个称为“堆”的自由空间，由动态分配函数malloc( )分配一块实际串长所需的存储空间，如果分配成功，则
6、返回这段空间的起始地址，作为串的基址。由free( )释放串不再需要的空间。l存储结构：typedef structchar *ch;/若是非空串，按串长分配空间，否则ch为NULLint length;/串长 HString;现在学习的是第7页，共26页基本算法（P76-77）举例：串插入操作Status StrAssign(HString &T,char* chars);/生成一个值等于串常量chars的串TInt StrLength(HString S);/返回串S的元素个数，称为串的长度Int StrCompare(HString S,HString T);/若ST，返回值0,若S=T
7、，返回值=0，若ST，返回值0Status ClearString(HString &S);/将S清为空串，并释放S所占空间Status Concat(HString &T,HString S1,HString H2);/用T返回S1和S2联接成的新串HString SubString(HString S, int pos, int len);/返回串S的第Pos个字符起长度为len的子串/1=pos=StrLength(S)&0=lenk满足 “p1p2pk-1”=“si-k+1si-k+2si-1”已经得到的“部分匹配”结果是 “pj-k+1pj-k+2pj-1”=“si-k+1si-k+
8、2si-1”所以 “p1p2pk-1”=“pj-k+1pj-k+2pj-1”现在学习的是第14页，共26页模式串的next函数Nextj表示当模式串中第j个字符与主串中相应字符失配时，在模式串中需要重新和主串中该字符进行比较的字符位置12k-1j-k 1j-10 j1Maxk|1kjjp pp pp 1 next当时且其它情况现在学习的是第15页，共26页J 1 2 3 4 5 6 7 8模式串 a b a a b c a cNextj 0 1 1 2 2 3 1 2如何求Nextj?现在学习的是第16页，共26页求next函数值的过程是一个递推过程，已知：next1 = 0；假设：nextj
9、 = k；即 “p1pk-1”=“pj-k+1pj-1”若 pj = pk则： nextj+1 = k+1=nextk+1若： pj pk则需往前回朔，检查 pj = p?，这实际上也是一个匹配的过程，不同在于：主串和模式串是同一个串现在学习的是第17页，共26页将模式串向右滑动至第nextk个字符与主串中第j个字符比较。若nextk=k且pj=pk，则nextj+1=k+1=nextk+1若pj pk，则以此类推现在学习的是第18页，共26页J 1 2 3 4 5 6 7 8模式 a b a a b c a c Nextj 0 1 1 2 2 312现在学习的是第19页，共26页next函数
10、的改进例如： S = aaabaaabaaabaaabaaab T = aaaabnextj=01234 Nextj=k,且模式中pj=pk时，当主串中si pj时，不需要再和pk比较，直接和pnextk比较nextvalj=00004现在学习的是第20页，共26页4.4 4.4 文本编辑文本编辑文本编辑是串的一个很典型的应用。它被广泛用于各种源程序的输入和修改，也被应用于信函、报刊、公文、书籍的输入、修改和排版。文本编辑的实质就是修改字符数据的形式或格式。在各种文本编辑程序中，它们把用户输入的所有文本都作为一个字符串。尽管各种文本编辑程序的功能可能有强有弱，但是它们的基本的操作都是一致的，一
11、般包括串的输入、查找、修改、删除、输出等。例如有下列一段源程序：main() float a,b,max; scanf(%f,%f,&a,&b); if ab max=a; else max=b;我们把这个源程序看成是一个文本，为了编辑的方便，总是利用换行符把文本划分为若干行，还可以利用换页符将文本组成若干页，这样整个文本就是一个字符串，简称为文本串，其中的页为文本串的子串，行又是页的子串。将它们按顺序方式存入计算机内存中，如表如表4-74-7所示所示（图中表回车符）。现在学习的是第21页，共26页现在学习的是第22页，共26页在输入程序的同时，文本编辑程序先为文本串建立相应的页表和行表，即建
12、立各子串的存储映象。串值存放在文本工作区，而将页号和该页中的起始行号存放在页表中，行号、串值的存储起始地址和串的长度记录在行表.现在学习的是第23页，共26页下面我们就来讨论文本的编辑。（1）插入一行时，首先在文本末尾的空闲工作区写入该行的串值，然后，在行表中建立该行的信息，插入后，必须保证行表中行号从小到大的顺序。（2）删除一行时，则只要在行表中删除该行的行号，后面的行号向前平移。若删除的行是页的起始行，则还要修改相应页的起始行号（改为下一行）。（3）修改文本时，在文本编辑程序中设立了页指针，行指针页指针，行指针和字符指针字符指针，分别指示当前操作的页、行和字符。若在当前行内插入或删除若干字
13、符，则要修改行表中当前行的长度。如果该行的长度超出了分配给它的存储空间，则应为该行重新分配存储空间，同时还要修改该行的起始位置。对页表的维护与行表类似，在此不再叙述。现在学习的是第24页，共26页本章小结本章小结本章主要介绍了如下一些基本概念：串：串：串（或字符串）（String）是由零个或多个字符组成的有限序列。主串和子串：主串和子串：一个串的任意个连续的字符组成的子序列称为该串的子串，包含该子串的串称为主串。串的静态存储结构：串的静态存储结构：类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列的存储方式称为串的顺序存储结构。堆存储结构：堆存储结构：用一组空间足够大的、地
14、址连续的存储单元存放串值字符序列，但其存储空间在程序执行过程中能动态分配的存储方式称为堆存储结构。串的链式存储结构：串的链式存储结构：类似于线性表的链式存储结构，采用链表方式存储串值字符序列的存储方式称为串的顺序存储结构。除上述基本概念以外，还应该了解串的基本运算（字符串拷贝（赋值、字符串的联接、求字符串的长度、子串的查询、字符串的比较）、串的静态存储结构的表示、串的链式存储结构的表示、串的堆存储结构的表示，能在各种存储结构方式中求字符串的长度、能在各种存储结构方式中利用C语言提供的串函数进行操作。现在学习的是第25页，共26页习习 题题 四四1简述空串与空格串、串变量与串常量、主串与子串、串
15、名与串值每对术语的区别？2两个字符串相等的充要条件是什么？3串有哪几种存储结构？4已知两个串：s1=”fg cdb cabcadr”, s2=”abc”, 试求两个串的长度，判断串s2是否是串s1的子串，并指出串s2在串s1中的位置。5已知：s1=Im a student，s2=student，s3=teacher，试求下列各运算的结果：Strlength(s1)；SubString(s1,8,5)；Index(s1,u)；Replace(s1,student,s3)；6试编写一个实现串的复制操作StrCopy（&T，S）算法。9试编写一个实现串的置换操作Replace（&S，T，V）算法。 现在学习的是第26页，共26页