《串类型的定义》PPT课件.ppt

《《串类型的定义》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《串类型的定义》PPT课件.ppt（27页珍藏版）》请在三一办公上搜索。

1、2023/8/3,第四章 串,1,第四章 串,4.1 串类型的定义4.2 串的表示和实现 4.2.1 定长顺序存储表示 4.2.2 堆分配存储表示 4.2.3 串的块链存储表示4.3 串的模式匹配算法4.4 串操作应用举例文本编辑,2023/8/3,第四章 串,2,4.1 串类型的定义,基本概念 串(String)是由零个或多个字符组成的有限序列。一般记作S=a1a2a3an，其中S 是串名，单引号括起来的字符序列是串值；ai(1in)可以是字母、数字或其它字符；串中所包含的字符个数称为该串的长度。空串(Empty String)：长度为零的串。它不包含任何字符。空格串(Blank Strin

2、g)：由一个或多个空格组成的串。注意：空串和空格串的不同。,2023/8/3,第四章 串,3,基本概念（续）,子串：串中任意个连续字符组成的子序列。主串：包含子串的串。通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为子串在主串中的序号（或位置）。例如，设A和B分别为 A=“This is a string”B=“is”则B是A的子串，A为主串。B在A中出现了两次，其中首次出现所对应的主串位置是3。因此，称B在A中的序号（或位置）为3。特别地，空串是任意串的子串，任意串是其自身的子串。,2023/8/3,第四章 串,4,基本概念（续）,通常在程序中使用的串可分为两种：串变量

3、和串常量。串常量和整常数、实常数一样，在程序中只能被引用但不能不能改变其值，即只能读不能写。通常串常量是由直接量来表示的，例如语句Error(“overflow”)中“overflow”是直接量。但有的语言允许对串常量命名，以使程序易读、易写。如C+中，可定义 const char path=“dir/bin/appl”;这里path是一个串常量，对它只能读不能写。串变量和其它类型的变量一样，其取值是可以改变的。,2023/8/3,第四章 串,5,串的抽象数据类型定义,串的抽象数据类型定义见教材P71 串的基本操作(13个)：StrAssign,Strcopy,StrEmpty,StrComp

4、are,StrLength,ClearString,Concat,SubString,Index,Replace,StrInsert,StrDelete,DestroyString 许多高级语言均提供了串基本操作相应的运算或标准库函数来实现。下面仅介绍几种在C语言中常用的串运算，其它的串操作见教材及参考书。,2023/8/3,第四章 串,6,串变量及基本操作：,char s120=“dirtreeformat”,s220=“file.mem”;char s330,*p;int result;求串长(length)int strlen(char s);/求串的长度 例如：coutstrlen(s

5、1);输出13,2023/8/3,第四章 串,7,基本操作（续）,（2）串复制(copy)char*strcopy(char to,char from);该函数将串from复制到串to中，并且返回一个指向串to的开始处的指针。例如：strcopy(s3,s1);/s3=“dirtreeformat”(3)联接(concatenation)char concat(char to,char from)该函数将串from复制到串to的末尾，并且返回一个指向串to的开始处的指针。,2023/8/3,第四章 串,8,基本操作（续）,例如：concat(s3,”/”)concat(s3,s2);/s3=“

6、dirtreeformat/file.mem”(4)串比较（compare)int strcompare(chars1,char s2);该函数比较串s1和串s2的大小，当返回值小于0，等于0或大于0时分别表示s1s2 例如：result=strcompare(“baker”,”Baker”)result0 result=strcompare(“12”,”12”);result=0 result=strcompare(“Joe”,”Joseph”);result0,2023/8/3,第四章 串,9,基本操作（续）,（5）字符定位(index)char strchr(char s,char c)

7、;该函数是找c在字符串中第一次出现的位置，若找到则返回该位置，否则返回NULL。例如：p=strchr(s2,”.”);p 指向“file”之后的位置 if(p)strcpy(p,”.cpp”);s2=“file.cpp”最小操作子集：串赋值StrAssign、串比较Strcompare、求串长StrLength、串联接concat和求子串SubString。串的其余操作可由这些基本操作组合而成。,2023/8/3,第四章 串,10,4.2 串的表示和实现,因为串是特殊的线性表，故其存储结构与线性表的存储结构类似。只不过由于组成串的结点是单个字符。串有三种机内表示方法，下面分别介绍。1 定长顺

8、序存储表示 定长顺序存储表示,也称为静态存储分配的顺序表。它是用一组连续的存储单元来存放串中的字符序列。所谓定长顺序存储结构，是直接使用定长的字符数组来定义，数组的上界预先给出：#define maxstrlen 255 typedef char sstringmaxstrlen+1;sstring s;/s是一个可容纳255个字符的顺序串。,2023/8/3,第四章 串,11,串的结束标记,一般可使用一个不会出现在串中的特殊字符在串值的尾部来表示串的结束。例如，C语言中以字符0表示串值的终结，这就是为什么在上述定义中，串空间最大值maxstrlen为256，但最多只能存放255个字符的原因，

9、因为必须留一个字节来存放0字符。若不设终结符，可用一个整数来表示串的长度，那么该长度减1的位置就是串值的最后一个字符的位置。,2023/8/3,第四章 串,12,顺序串的类型定义,顺序串的类型定义和顺序表类似：typedef struct char chmaxstrlen;int length;sstring;/其优点是涉及到串长操作时速度快。,2023/8/3,第四章 串,13,顺序存储时串操作的实现,串联接Concat(T,S1,S2)求子串SubString(sub,s,pos,len)注：串联接操作可能出现“截断”现象,2023/8/3,第四章 串,14,2 堆分配存储表示,这种存储表

10、示的特点是，仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得。所以也称为动态存储分配的顺序表。在C语言中，利用动态存储管理函数，来根据实际需要动态分配和释放字符数组空间。typedef struct char*ch;/若是非空串，则按串长分配存储区，否则ch为null int length;/串长度 hsring;,2023/8/3,第四章 串,15,3 串的链式存储结构,顺序串上的插入和删除操作不方便，需要移动大量的字符。因此，我们可用单链表方式来存储串值，串的这种链式存储结构简称为链串。typedef struct node char data;s

11、truct node*next;lstring;一个链串由头指针唯一确定。这种结构便于进行插入和删除运算，但存储空间利用率太低。,2023/8/3,第四章 串,16,结点的大小,由于串结构的特殊性，可使每个结点存放多个字符。通常将结点数据域存放的字符个数定义为结点的大小，显然，当结点大小大于 1时，串的长度不一定正好是结点的整数倍，因此要用特殊字符来填充最后一个结点，以表示串的终结。,head,A,B,C,I,B,C,D,E,F,G,H,I,#,#,#,head,A,2023/8/3,第四章 串,17,块链结构（设头、尾指针）,对于结点大小不为1的链串，其类型定义只需对上述的结点类型做简单的修

12、改即可。#define nodesize 80 typedef struct node char datanodesize;struct node*next;node;typedef struct lstring node*head,*tail;int curlen;lstring;,2023/8/3,第四章 串,18,存储密度的概念,存储密度小，运算处理方便，存储占用量大；存储密度大，情况则相反。串的链式存储结构队某些串操作（如联接等）有一定的方便，但总的说来不如另外两种存储结构灵活。,存储密度,=,串值所占的存储位,实际分配的存储位,2023/8/3,第四章 串,19,4.3 串的模式匹配

13、算法,子串定位运算又称为模式匹配(Pattern Matching)或串匹配(String Matching)，此运算的应用非常广泛。在文本编辑程序中，我们经常要查找某一特定单词在文本中出现的位置。显然，解此问题的有效算法能极大地提高文本编辑程序的响应性能。在串匹配中，一般将主串称为目标串，子串称之为模式串。,2023/8/3,第四章 串,20,模式匹配（续）,设S为目标串，T为模式串，且不妨设：S=“s0s1s2sn-1”T=“t0t1tm-1”串的匹配实际上是对于合法的位置0in-m依次将目标串中的子串si.i+m-1和模式串t0.m-1进行比较，若si.i+m-1=t0.m-1，则称从位

14、置i开始的匹配成功，亦称模式t在目标s中出现.,2023/8/3,第四章 串,21,模式匹配（续）,若si.i+m-1 t0.m-1，则称从位置i开始的匹配失败。上述的位置i又称为位移，当si.i+m-1=t0.m-1时，i称为有效位移；当si.i+m-1 t0.m-1时，i称为无效位移。这样，串匹配问题可简化为是找出某给定模式T在一给定目标T中首次出现的有效位移。,2023/8/3,第四章 串,22,模式匹配算法,串匹配的算法很多，这里我们只讨论一种最简单的称为朴素的串匹配算法。其基本思想是用一个循环来依次检查n-m+1个合法的位移i(0I n-m)是否为有效位移，其算法段为：for(i=0

15、;i=n-m;i+)if(Si.i+m-1=T0.m-1)return i;,2023/8/3,第四章 串,23,模式匹配算法匹配过程,设目标串为a b a b c a b c a c b a b，模式串为a b c a c第一趟 a b a b c a b c a c b a b a b c第二趟 a b a b c a b c a c b a b a第三趟 a b a b c a b c a c b a b a b c a c,第四趟 a b a b c a b c a c b a b a第五趟 a b a b c a b c a c b a b a第六趟 a b a b c a b c

16、a c b a b a b c a c,2023/8/3,第四章 串,24,KMP算法模式匹配的改进算法,算法是由、和同时发现，因而得名。改进在于：利用已经得到的部分匹配结果将模式向右“滑动”尽可能远的一段距离。算法可以在O(n+m)的时间数量级上完成。第一趟 a b a b c a b c a c b a b a b c第二趟 a b a b c a b c a c b a b a b c a c第三趟 a b a b c a b c a c b a b a b c a c,2023/8/3,第四章 串,25,线性结构复习,线性表n个数据元素的有限序列抽象数据类型定义（12个基本操作）存储结

17、构：顺序存储顺序表；链式存储线性链表，循环链表和双向链表；其它。栈和队列操作受限的线性表抽象数据类型定义（分别为9个操作）存储结构：顺序存储顺序栈和循环队列；链式存储链栈和链队列串由零个或多个字符组成的有限序列抽象数据类型定义（13个基本操作）存储结构：定长顺序存储；堆分配存储和块链存储,2023/8/3,第四章 串,26,作业题,1(P27 4.3)设s=I AM A STUDENT,t=GOOD,q=WORKER.求：strlenth(s),strlength(t),substring(s,8,7),substring(t,2,1),index(s,A),index(s,t),concat(substring(s,6,2),concat(t,substring(s,7,7).2(P29 4.12)编写一个实现串的置换操作replace(&S,T,V)的算法.注：操作replace的意义见串的类型定义P72,2023/8/3,第四章 串,27,思考题,1.了解C+中的字符串函数2.用BP算法求解具体问题3.全面复习线性结构(二、三、四章)，包括基本概念和算法。,