《数据结构》串》ppt课件

《《数据结构》串》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章串4.1串及其操作4.2串的存储结构4.3串的基本运算实现4.4串的模式匹配运算习题在非数值处理的应用领域中，字符串的应用非常广泛。如编辑器(Edit、Word本质上是字符串处理)、信息检索(字符串比较)等。实际上，编写数值计算程序的机会很有限。从发明计算机的思路来说，其目的是为了模拟人类的对信息的逻辑处理方法，而数值计算仅仅是一种逻辑思路的标准化。现今我们使用的计算机的硬件结构主要反映数值计算的需要的，因此，在处理字符串数据时比处理整数和浮点数要复杂的多。而且，在不同类型的应用中，所处理的字符串具有不同的特点，要有效地实现字符串的处理，就必须根据具体

2、情况使用合适的存储结构。下面将讨论字符串的一些处理方法和字符串的几种不同的存储结构。4.1串及其操作4.1.1串的逻辑结构定义：串(字符串)，是由零个或多个字符组成的有限序列。一般记作：s=″a0a1…an-2an-1″(n≥0)s是串的名。双引号括起来是是串的值。n为串的长度。空串为零个字符，n=0。子串为串中任意个连续的字符组成的子序列。位置为字符在序列中的序号。为字符在串中的称作。子串位置以子串的第一个字符在主串中的位置来表示。举例：a=″Thisisastring″串长=16b=″string″串长=6，是a的子串，在a串的位置是10c=″″串长=2，的

3、空格串，它不是a和b的子串。串的集合定义：设string=(D，R)是一个数据结构，其中D={a0，a1，…，an-1}为字符元素的集合，i=0，…，n-1，并且n≥0。R={

4、ai-1，ai∈D，i=1，2，…，n-1}R为上元素的关系集合则称string是一个字符串。字符串与线性表的区别是它的数据对象为字符集。4.1.2串的基本运算(1)赋值操作assign(s，t)。将t的值赋给s。(2)串相等判断equal(s，t)函数。若s串与t串相等，则函数返回1，否则函数将返回0。(3)串的联接操作concat(s，t)函数。将s串和t串联接成一

5、个串，新生成的串是s串在前，而t串紧接s串的尾部。例如，设a=″data″,b=″structure″,执行concat(a,b),新生成的串是″datastructure″。串的联接不满足交换律:concat(s,t)!=concat(t,s);串的联接满足结合律:concat(s1，concat(s2，s3))=concat(s1，s2，s3)其运算结果是将这3个串的值依次首尾相接得到一个新串。(4)求长度length(s)函数。其函数值为串s中字符的个数。(5)求子串sub(s，start，len，t)。若0≤start

6、ength(s)-start则t中值为从串s中第start个字符起，长度为len的字符序列，并且函数返回值为1；否则函数返回值为0。例如，s=″datastructure″,sub(s，5，5，t),则t=″struc″。(6)子串定位index(s,t)函数。若在主串s中存在和t相等的子串，则函数值为s中第一个这样的子串在主串s中的位置，否则函数值为-1。注意，在此t不能是个空串。例如，s=″datastructure″，t=″ru″,则index(s,t)=7。(7)替换replace(s,t,v)。操作结果是以串v替换串s中出现的所有和非空子串t相同的不

7、重叠子串。4.2串的存储结构在程序执行的过程中，串的值可变。所以，与在程序出现的其他类型的变量一样，给要处理的串赋一个变量名，这样在对串进行操作时，可以通过变量名访其值。串的存储结构有两种形式：一种是将串设计成一种结构类型，串是字符型的数组，从串名可直接访问到串值，串值的存储分配是在编译时完成；一种是串值的存储分配是在程序运行时完成，在串名和串值之间需要建立一个对照表，这个对照表称之为串名的存储映像。4.2.1顺序存储结构用一组地址连续的存储单元存储串字符序列。唯一确定一个串，需要二个数据：串的起始地址，串的长度。在C语言中，对字符串处理两个要素是：数组名，结束

8、标记符号，如图4.1所示chdatastructure…01234567891011121314…n-1图4.1串的顺序存储结构说明：ch是一个数组，存放串”datastructure”，判断串的结束标志为字符’’，在它前面的字符组成串。在这种表示方法中，访问子串方便，但插入、删除麻烦，需要大量移动字符。例如，要取子串sub(s,5,4,t)，只要将数组ch[5]到ch[8]赋给t，便可实现求子串运算。顺序存储结构又分为非紧缩格式和紧缩格式。a.非紧缩格式一个存储单元存放一个字符。若计算机的存储单元是按字编址，并且计算机字长大于八位二进制数，这样，在一个

9、存储单元仅仅存放一个字符