《算法与数据结构》第2章常用数据结构ppt.ppt

算法与数据结构,第2章 常用数据结构,第2章 常用数据结构,2.1 数据类型与数据结构 2.2 数组 2.3 串,2.1 数据类型与数据结构,2.1.1 数据、数据元素与数据类型 2.1.2 数据结构的基本概念 2.1.3 抽象数据类型,数据,计算机中的数据在计算机内的最原始形式仅是一组组二进制代码，程序设计语言以这种代码为基础建立起了所有的数据。 数据的概念不再只是那些用数字组合而成的各种数据了，如整数、小数、实数、虚数、复数、指数和对数等。 随着计算机科学技术的发展，数据的概念也相应地发生了一些重要的变化。,数据（续）,数据（Data）是信息的载体，是对自然界客观事物的符号表示。 在计算机科学与技术学科，数据泛指那些能够被计算机接收、识别、存储、加工和处理的对象的全体。 换句话说，数据是对那些能够有效地输入到计算机中并且能够被计算机程序所加工和处理的符号全体的总称。 只要是能被计算机识别、存储、加工和处理的都属于数据的范畴。,数据元素,数据的基本单位是数据元素（Data Element），有时也称作元素、结点、顶点、记录等。 一个数据元素也可以由若干个数据项（Data Item）组成。 数据项是具有独立含义的数据的不可再分割的最小标识单位。例如，一个单位的职工花名册中，每一位职工的信息就是一个数据元素；职工信息中包含有职工编号、姓名、性别、民族、年龄、政治面貌、参加工作时间、工资级别、职称、职务等项目，这每一个项目都是某个职工数据元素中的一个数据项。,数据组织的三个层次,数据组织的三个层次分别是数据、数据元素、数据项。 数据可以由若干个数据元素组成，数据元素又可以由若干个数据项组成。 数据项是对数据元素属性的描述，数据元素是对客观世界中某个独立个体的数据描述。 在C语言中，数据元素可以用结构体来描述，每个数据项则是结构体中的一个分量。,数据元素与数据对象,计算机中的数据可以按类型来划分，划分的结果就是数据对象。 所谓数据对象（Data Object），是指具有相同性质的数据元素的集合，是数据的一个子集。如整数数据对、字母字符数据对象。 在一个具体问题中，数据元素具有相同性质，属于同一数据对象，数据元素是数据对象的一个实例。如在前述的职工花名册中，所有的职工是一个数据对象，不同的职工的信息是不同的数据元素，它们都是职工数据对象的不同实例，其数据元素值是各数据项的一个具体描述。,数据类型,数据类型（Data Type）是对在计算机中表示的同一数据对象及其在该数据对象上的一组操作的总称。 如整数数据，在计算机中它是集合minintmaxint上的整数（其中minint和maxint分别是最小整数和最大整数，在不同的计算机中表示的值不同；且这个集合是有穷集合，是数学意义上的无穷集合的一个子集），在这个集合上可以进行的操作有加、减、乘、整除和求模等算术运算以及等于、不等于、大于、小于、大于等于和小于等于等关系运算。 数据对象整数以及在整数集合上的算术运算和关系运算等操作一起构成了整型这个数据类型。,数据类型（续）,数据类型有简单（或原子）数据类型和结构数据类型之分。 简单数据类型是由程序设计语言提供的一些基本类型。如整型、实型、布尔型和字符型等，其值不可再分解。 结构数据类型是由程序设计语言中提供的构造机制来定义的数据类型。如数组、文件、结构体、共用体等，其值可以再分解；它的构成成分可以是简单数据类型，也可以是结构数据类型。 数据类型的概念，是程序设计语言和程序设计过程中的一个非常重要的概念。,数据类型的特征,类型决定了变量或表达式所有可能取值的全体成员集合。 每一个值隶属于且仅隶属于某一类型。 任何常量、变量或表达式的类型，都可以从其形式上或所处的上下文关系中推断出来，无须了解在程序运行时计算出的具体值。 每一种操作都要求一定类型的操作数据，且得出一定类型的操作结果。 一种类型的值及其在该类型上规定的基本操作的性质可由一组公理来阐明。 高级程序设计语言使用类型信息去防止程序中出现无意义的结构，又由类型信息确定在计算机中的数据表示和数据处理方法。,2.1 数据类型与数据结构,2.1.1 数据、数据元素与数据类型 2.1.2 数据结构的基本概念 2.1.3 抽象数据类型,数据结构的基本概念,数据结构（Data Structure）是指计算机程序中所操作的对象数据以及数据元素之间的相互关系和运算。 在任何问题中，数据元素之间都不会是独立的，总是存在着这样或那样的关系，这种数据元素之间的关系也称作结构。 数据结构包含以下三个方面的内容： 数据的逻辑结构 数据的存储结构 数据的运算及实现,数据的逻辑结构,数据的逻辑结构是指数据元素之间的逻辑关系。 它只抽象地反映数据元素集合的结构，而不管其存储方式，可用一个二元组给出如下的形式定义： Data-Structure （D,R） 其中： D是数据元素的集合； R是D上关系的集合。 从结构的观点出发，一般可将数据结构分为两大类： 线性结构 如线性表、栈、队列、串、数组和文件等； 非线性结构 如树、图和集合等。,数据的存储结构,数据的存储结构是指数据及数据元素之间的关系在计算机内存中的表示，也称作数据的物理结构或存储映像。 主要的存储方式有顺序存储和链式存储两种，此外还有索引存储和散列存储等其它方式。 从逻辑结构到存储结构称之为映像。 同一逻辑结构采用不同的存储结构存储，就会得到不同的数据结构。这是因为映像变了，使结构有了改变，使得实现逻辑结构上所定义的运算的算法也随之改变了。,数据的运算及实现,数据的运算及实现。程序中的数据运算是定义在数据的逻辑结构上的运算，但运算的实现要在相应的存储结构上进行。 常用的运算有检索、插入、删除、更新、排序等。 在数据的逻辑结构上定义数据的运算时，只考虑这些运算是“做什么”，而不考虑它“如何做”，是抽象运算；只有在选定了某种数据结构的存储结构时，才去考虑如何具体实现这些运算，即运算的实现。 运算的实现依赖于所选取的存储结构，也依赖于所选用的程序设计语言。,线性结构,在线性结构中，D中数据元素之间存在着一对一的次序关系。 其逻辑特征为： 存在一个惟一被称作“第一个”的数据元素，它没有前趋只有一个直接后继；有时也称作开始结点； 存在一个惟一被称之为“最后一个”的数据元素，它没有后继只有一个直接前趋；有时也称作终端结点； 其它数据元素都有且仅有一个直接前趋（immediate predecessor），也有且仅有一个直接后继（immediate successor）。 如职工花名册、学生成绩表、向量、数组、购物时排的队等都是线性结构的例子。,非线性结构树型结构,在非线性结构中，D中数据元素之间不存在一对一的次序关系。 树型结构中的数据元素之间，存在着一对多的层次关系，在树型结构中： 没有直接前趋的结点称之为根结点； 除根结点外每个结点有且仅有一个直接前趋（称之为双亲结点）； 没有直接后继的结点称之为叶结点，除叶结点外每个结点都有一个或多个直接后继（称之为孩子结点）。 树的例子很多，如族谱中的家族树、政府机构中的行政树、计算机文件管理中的目录树、编译程序中用到的语法树等。,树型结构示意图,非线性结构图型结构,非线性结构中的图结构，其数据元素之间既不存在线性结构中的一对一次序关系，也不存在树型结构中的一对多层次关系。 在图型结构中，D中数据元素之间的关系是多对多的网状关系。 换句话说，图是一种网状结构，任意两个数据元素之间都可能相关；其中的每一个数据元素，既可以有多个直接前趋，也可以有多个直接后继。 如交通网络图，课程之间的先后修关系图，软件开发过程中所用到的程序图、控制流图、数据流图等都是图型结构的例子。,图型结构示意图,非线性结构集合结构,非线性结构中的集合结构，其D中数据元素之间的关系是“属于同一个集合”。 集合是数据元素关系极为松散的一种结构。通常是用其它结构来表示集合。,存储表示方式顺序存储,顺序存储方式，是在计算机内存储器中开辟一片地址连续的存储单元顺序存放数据中的各个元素；它把逻辑上相邻的数据元素存放在物理上相邻的存储单元中，利用物理上的邻接关系表示逻辑上的先后次序关系，这种存储表示方式称作顺序存储结构（Sequential Storage Structure）。 顺序存储结构是一种最基本的存储方法，通常借助于程序设计语言中的数组来实现。 主要用于线性数据结构的存储，对于非线性结构进行线性化处理后也可实现顺序存储。,存储表示方式链式存储,链式存储方式，是把数据元素和反映元素间关系（后继和/或前趋）的地址一块存储在计算机内；它不要求在内存储器中开辟的存储单元地址连续，数据元素可以存放在内存储器中的任意位置，借助指示数据元素存储地址的指针表示元素间的逻辑关系，这种存储表示方式称作链式存储结构（Linked Storage Structure）。 链式存储结构也是一种基本的存储表示方法，通常借助于程序设计语言中的指针来实现。 主要用于树型结构和图型结构数据的存储，为了某种特殊的需要也常用于一些线性结构的存储。,其他的存储表示方式,存储表示方式还有索引存储方式和散列存储方式，通常是为了检索的方便所采用的存储表示方法。 一般地说，这几种基本的存储表示方法，既可以单独使用，也可以组合起来使用。 选择何种存储结构要依具体问题的要求而定，既要考虑问题表示和运算的方便性，也还会考虑到实现算法的时间和空间效率要求。,数据的逻辑结构和存储结构,数据的逻辑结构和存储结构是密切相关的两个方面： 算法的设计都取决于所选定的数据的逻辑结构； 算法的实现则依赖于所采用的存储结构。 各种数据结构，分别提供了不同类型的数据在作为计算机程序数据时的组织、管理、存储、运算和处理的方法和技术。 有些数据结构，在程序设计语言中已经实现了或提供了定义数据类型的方法或手段。如各种基本类型，数组、字符串等 有些数据结构，在程序设计语言中没有实现，要靠程序设计人员利用语言中提供的某些设施去实现或模拟实现，如栈、队列、树、二叉树、图、网络等。 在程序设计语言中实现了的数据结构称之为数据类型。,2.1 数据类型与数据结构,2.1.1 数据、数据元素与数据类型 2.1.2 数据结构的基本概念 2.1.3 抽象数据类型,抽象数据类型,抽象的本质就是抽取反映问题本质的东西，忽略掉非本质的细节。 数据类型是对同一数据对象及其在该数据对象上的一组操作的抽象，抽象的结果是把用户不必了解的一切细节都封装在类型之中，对使用数据类型的用户来说是实现了信息隐藏（Information Hiding）。 用户在使用数据类型时，既不需要了解该数据类型在计算机内部是如何表示的，也不需要知道其操作是如何实现的，只须集中精力考虑所要求解的问题应该如何去解决。 抽象数据类型的概念，是我们熟知的数据类型概念的引伸和发展，是数据抽象和运算抽象紧密结合的产物。,抽象数据类型（续）,抽象数据类型（Abstract Data Type简记为ADT）是指一个数据模型以及定义在该数据模型上的一组操作。这里的数据模型，是要求解问题中的各种数据的总和；通常，把这些数据可以组织成为一个或多个数据结构。 当数据模型表现为一个数据结构时，抽象数据类型就是这个数据结构以及定义在这个数据结构上的一组运算；这种情况是我们讨论和学习抽象数据类型概念的基础，也是数据结构课程对抽象数据类型定义的根本要求。 当数据模型表现为多个数据结构时，我们可以先定义以单个数据结构为基础的各个抽象数据类型，然后在此基础上（需要的话）定义抽象级别更高的抽象数据类型，并利用它们构造最终的问题求解算法。,抽象数据类型的定义,抽象数据类型的定义，仅取决于它的一组逻辑特性，而与它在计算机内部如何表示和实现无关。 也就是说不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用；如同数据类型一样，是使用与实现分离、实行封装和信息隐藏。 抽象数据类型可以通过已有的数据类型来表示和实现，利用已有的数据类型来说明新的结构，利用已经实现了的操作来完成新的操作。,抽象数据类型自然数的ADT描述,ADT NaturalNumber Data Objects:D=xxNaturalNumber,0 xmaxint Data Relation:R=xNaturalNumber, 1xmaxint Elementary Operation: Zero( ) 返回0 IsZero(x) If(x=0) 返回True else 返回False Add(x,y) If(x+y=maxint) 返回x+y else 返回maxint Equal(x,y) If(x=y) 返回True else 返回False Successor(x) If(x=maxint) 返回x else 返回x+1 Subtract(x,y) If(xy) 返回0 else 返回x-y end ADT NaturalNumber;,抽象数据类型（续）,抽象数据类型是算法设计和程序设计中的重要概念，这个概念明确地把数据结构与作用在该结构上的运算紧密地联系起来。 数据结构上的运算依赖于其具体表示，有了数据结构的具体表示和运算的具体实现，运算的效率随之确定。 需要指出的是，基本数据类型已隐含着数据结构和定义在该结构上的运算的统一，只是当时尚未形成抽象数据类型的概念罢了。 每一种基本数据类型都连带着一组基本运算，只是由于这些基本数据类型中数据结构的具体表示和基本运算的具体实现都很规范，都通过内置而隐藏起来使人们看不到它们的封装，人们习惯于在算法与程序设计中使用基本数据类型名和相关的运算名而不问其究竟。,抽象数据类型（续）,抽象数据类型的设计和实现不可能象基本数据类型那样可以规范、内置和一劳永逸。 首先要根据问题的具体要求，定义该抽象数据类型需要包含哪些信息，并根据功能确定公共界面的服务，使用者可以使用公共界面中的服务对该抽象数据类型进行操作。 另一方面，把抽象数据类型的实现作为私有部分封装在其实现模块内，让使用者看不到，也不能直接操作该类型所存储的数据，只能通过界面中的服务来访问这些数据。,第2章 常用数据结构,2.1 数据类型与数据结构 2.2 数组 2.3 串,2.2 数组,数组（Arrays）是程序设计语言中最基本和最重要的数据结构，也是程序设计实践中最常用的数据结构。 在程序中引入数组的充分理由是： 为了求解问题有引入数组的必要性，如需要记住一组值等； 基于问题求解算法的效率考虑，引入数组可使算法效率更高； 基于概念上或运算处理上的自然、简单和方便性方面考虑需要引入数组。,2.2 数组,2.2.1 数组及其运算 2.2.2 数组的顺序存储结构 2.2.3 特殊矩阵的压缩存储,数组的概念和特点,把具有相同性质的一组元素组织在一起形成数组结构。 数组结构的特点是： 数组元素的个数固定，元素间的逻辑关系由数组元素的序号（即数组的下标）来体现。 每一个数组元素都具有相同的结构。 数组元素的下标具有上下界约束且下标有序，下标与数组元素的对应关系使得数组元素可以随机访问。 所以，可以说数组结构是一个线性的、均匀的、其元素可以随机访问的数据结构。也可以说数组是由数组元素和下标构成的有序对结构，结构中的每一个数据元素都与一组下标有关。,数组的运算,对于数组结构的运算操作，是对其数据元素的操作。通常只有赋值和读取数组元素两种操作： 赋值：给定一组下标，把指定值（如初始值、修改值、运算值等）存入相应的数组元素中； 读取：给定一组下标，读取相应的数组元素（通常是为了使用其值或打印输出等目的）。,数组,在程序设计语言中，与数组结构对应的数据类型是数组类型，即在程序中引入数组要用语言中提供的数组类型说明方法说明。 如在C语言中，int A8就说明了一个一维整型数组A；进而就可以对A施加不同的操作，一般方法是利用循环控制变量值的变化，从下标下界到上界之间（或相反次序）访问相应的数组元素，其一般格式是 for(i=0; i8; i+) 对A的第i个元素执行某个指定的操作 当数组的下标为一个时，称之为一维数组 当数组的下标为两个或两个以上时，称之为二维数组或多维数组。,2.2 数组,2.2.1 数组及其运算 2.2.2 数组的顺序存储结构 2.2.3 特殊矩阵的压缩存储,数组的顺序存储结构,顺序存储结构，是指在计算机内存中安排一片地址连续的空间存储数据。 数组的线性的、均匀的结构和计算机内存单元的一维结构，决定了对数组采用顺序存储结构是最佳选择。 对于一维数组，按下标顺序分配存储空间是很自然的。 对于二维数组和多维数组。就有一个把数组元素按照某种方式排成一个线性序列的问题，即次序约定问题。,二维数组的顺序存储结构举例,二维数组可以把它看作是由每一行元素作为一个元素构成的一维数组（行为主序）， 二维数组也可以看作是由每一列元素作为一个元素构成的一维数组（列为主序）。 一种约定，就可以得到二维数组所有元素的一个惟一的线性排列：a11a12a1na21a22a2nam1am2amn或a11a21am1a12a22am2a1na2namn。 若选定一种约定，则每个数组元素相对于存储区域起始地址的位置也就随之确定了。,行为主序的优先存储策略,行为主序的优先存储策略是将数组元素按行优先关系排列，第i+1行的元素紧跟在第i行中元素的后面；同一行中的元素以列下标次序排列。,列为主序的优先存储策略,列为主序的优先存储策略是将数组元素按列优先关系排列，第j+1列中的元素紧跟在第j列中元素的后面；同一列中的元素以行下标次序排列。,二维数组的元素存储地址计算公式,我们设每个数组元素需要e个存储单元存放；并记第一个数组元素的存储地址为loc(a11)，即存储区间的起始地址，也称作数组的基地址。 若以行为主序优先存储，考虑数组元素aij的地址计算公式。因为aij是第i行第j列的数组元素，其前面已经存放了i-1行共（i-1）*n个元素，在第j行中前面已经存放了j-1个元素，故在aij前面共存放了（i-1）*n+ j-1个元素；由每个元素占用空间e和基地址loc(a11)可得 loc(aij)= loc(a11)+(i-1)*n+j-1)*e 同理可推出以列为主序优先存储的地址计算公式为 loc(aij)= loc(a11)+(j-1)*m+i-1)*e,元素存储地址计算公式（续）,前面讨论的公式是假设了数组的下标下界均为1时的计算公式。 对于一般情况下的数组Ac1d1,c2d2 在行为主序之下aij的地址计算公式为 loc(aij)= loc(a11)+(i-c1)*(d2-c2+1)+j-c2)*e 在列为主序之下aij的地址计算公式为 loc(aij)= loc(a11)+(i-c2)*(d1-c1+1)+i-c1)*e,2.2 数组,2.2.1 数组及其运算 2.2.2 数组的顺序存储结构 2.2.3 特殊矩阵的压缩存储,特殊矩阵的压缩存储,在科学计算和工程应用中，常常要用到矩阵的概念。由于矩阵具有元素个数固定且下标有序排列的特点，使用二维数组表示既自然又可方便矩阵的各种运算。但是在有些情况下，如特殊矩阵和稀疏矩阵，采用二维数组的存储方式会浪费大量存储空间。为了节省空间，对这类矩阵可压缩存储。 所谓压缩存储，是指为多个值相同的元素只分配一个元素的存储空间，对零元素不分配存储空间。 所谓特殊矩阵是指矩阵中元素分布有一定规律，如对角矩阵、三对角矩阵、上三角矩阵、下三角矩阵、对称矩阵等。,1.对角矩阵的压缩存储,对角矩阵的特点是除了主对角线上的元素外其余元素都为零。 对于n阶方阵，只有n个非零元素，只需要n个元素空间顺序存储即可。其非零元素压缩存储位置k与矩阵下标的对应关系为k=i或k=j，通过这个关系可对矩阵中的非零元素随机存取。,压缩存储,2.三对角矩阵的压缩存储,三对角矩阵是除主对角线及主对角线上下各一个元素外，其余元素都为零的矩阵。 对三对角矩阵的压缩存储方法是，按行为主序优先存储方法把非零区的三对角元素依次顺序存储到一片连续的存储空间中。 其映像关系可以这样来分析：对处于三对角区的元素aij，它前面的i-1行中有非零元素3*(i-1)-1个，它处于本行中的第j-i+2个非零元素处，所以为第3*( i-1)-1+ j-i+2=2*( i-1)+ j个非零元素，此式也正好符合第一行的两个非零元素的情况。故有 k=2*( i-1)+ j,三对角矩阵的压缩存储图示,压缩存储,3.上三角矩阵的压缩存储,上三角矩阵是指矩阵的主对角线以下的所有元素均为同一常数c或零的n阶矩阵。 对上三角矩阵的压缩存储方法是，对处于下三角（不含主对角线）的常数c，在最后分配一个元素空间；对处于上三角（含主对角线）的每个元素按行为主序优先存储方法依次顺序存储分配空间，需要n*(n+1)/2个元素空间；共需要n*(n+1)/2+1个元素空间。 其映像关系为，若ij，aij处于下三角区，值必为常数c，存储分配在n*(n+1)/2+1处；若ij，aij处在上三角区，在前i-1行共存储的元素数为n+(n-1)+(n-i+2)=(i-1)*(2n-i+2)/2个，在第i行它是第j-i+1个，故aij为第(i-1)*(2n-i+2)/2+ j-i+1=(i-1)*(2n-i)/2+j个存储分配的元素。所以有,上三角矩阵的压缩存储图示,压缩存储,4.下三角矩阵的压缩存储,下三角矩阵与上三角矩阵对应，其常数在上三角区（不含主对角线），压缩存储方法也类似，以行为主序存储下三角部分。 处在下三角的元素aij，其前i-1行共有i*(i-1)/2个元素，在第i行它处于第j个位置，即aij处于存储分配区的第i*(i-1)/2+j个。于是我们有,下三角矩阵的压缩存储图示,压缩存储,5.对称矩阵的压缩存储,在n阶矩阵中，若元素满足aij=aji则称之为对称矩阵。 由于对称矩阵中元素关于主对角线对称，因此只需要存储其上三角中的元素或下三角中的元素，使对称元素共享同一存储空间。 假如只存储下三角中的元素，则需存储元素总数为n*(n+1)/2个，按行为主序顺序存储，其映像关系为 也可以给出一个统一的对应关系为 k= I*(I-1)/2+J 其中，I=max(i,j)，J=min(i,j)。,第2章 常用数据结构,2.1 数据类型与数据结构 2.2 数组 2.3 串,2.3 串,所谓串，就是我们在高级语言程序设计课程中学习和使用过的字符串，是大家熟知的概念。 串是许多软件系统的操作对象，如字符编辑系统、情报检索系统、词法分析系统、符号处理系统、语言翻译系统等，有着十分广泛的应用。 本节着重讨论串的存储结构以及主要运算的实现，如顺序存储分配的三种方式、堆式存储分配策略以及在“向量存储，定长结构”基础上几种串运算的实现算法，并简要介绍汉字串的概念。,2.3 串,2.3.1 串的基本概念 2.3.2 串的定长顺序存储及运算实现 2.3.3 模式匹配 2.3.4 串的堆式动态存储及运算实现 2.3.5 汉字串,串的基本概念,串（String）是由零个或多个字符组成的有限序列。 记作: s=“a1a2an” (n0) 其中：s是串名，用双引号括起来的字符序列是串的值（不含双引号）；ai（1in）是相应程序设计语言中允许使用的字符集中的任意字符；n为串中的字符个数，称作串的长度。 零个字符的串称作空串，它的长度为零，串内无任何字符。 要注意空串与空格串的区别，空格串中有一个或多个空格字符，串的长度大于零。,串的基本概念（续）,串中任意多个连续字符组成的子序列称作该串的子串（Substring），包含子串的串称作该子串的主串。字符在串中的序号称作该字符在串中的位置，子串在主串中的位置用子串的第一个字符在主串中的位置来表示。 两个串相等是指这两个串的值相等，即两个串长度相等且对应字符都相同时才相等。 串结构的形式化定义为 string=(D,R) 其中：D= aiaicharacter，i=1,2n，n0, R=ai-1,aiD，i=1,2n 。,串的基本运算（六种）,StrAssign(s,chars)：串赋值。把字符串常量chars的值赋给串变量s。 StrCopy(s,t)：串复制。把串变量t的值复制到串变量s中。 StrCompare(s,t)：串比较。若st返回值0，若s=t返回值=0，若st 返回值0。 StrLenth(s)：求串长。返回值为串s中字符的个数（串长）。 StrConcat(l,s,t)：串联接。把串t的值紧接着串s的值之后形成的新串值存入串变量l中返回。例如，若s=“baodao”，t=“taiwan”，则l=“baodaotaiwan”。 SubString(t,s,i,len)：求子串。把串s 中第i个字符开始的长度为len的字符序列存入串变量t中返回。该运算要求1iStrLength(s)+1且0lenStrLength(s)- i +1。,串的其它运算（四种）,其它的串运算都可以由这六种基本运算来实现。 下面四种其它的串运算都有着重要的应用： StrInsert(s,i,t)：串插入。运算的结果是把t串插入到s串中第i个字符之前得到的新串。其中，1iStrLength(s)+1。 StrDelete(s,i,len)：串删除。运算的结果是从s串中删去自第i个字符起的len 个字符后得到的新串。其中，1iStrLength(s)，0lenStrLength(s)- i +1。 StrIndex(s,t)：子串定位。若在主串s中存在等于t的子串，则返回t在s中首次出现的位置，否则返回值为-1。其中要求子串t为非空串。 StrReplace(s,t,v)：子串替换。运算的结果是以串v替换所有在串s中出现的和非空串t相等的不重叠的子串后得到的新串。,2.3 串,2.3.1 串的基本概念 2.3.2 串的定长顺序存储及运算实现 2.3.3 模式匹配 2.3.4 串的堆式动态存储及运算实现 2.3.5 汉字串,串的定长顺序存储,当一维数组的基类型是字符类型，形成的字符数组即字符串或串。 在高级程序设计语言中，大都为字符串设立了专门的数据类型。 在C语言中，有串常量和串变量的概念。用双引号括起来的字符序列为字符串常量，也可以用宏定义#define来定义字符串常量的标识符，如 #define CITY shanghai 对于字符串变量，C语言的说明为一维字符型数组，如 static char C100； 为字符串分配一个固定长度的一组地址连续的存储单元的存储分配方法称之为定长顺序存储分配。,定长顺序存储紧缩方式,计算机按字编址、每个单元存放四个字符。 如串s=“data structure 2.3”的紧缩存储如下： 其中字符串长度18存储在开始处，“ ”表示空格字符，共占用五个存储单元。 紧缩方式对串长是显式地直接存储，字符依次顺序放在连续的几个单元中。这种存储方式的优点是充分地利用了空间，然而四个字符一个地址运算不太方便。,定长顺序存储非紧缩方式,计算机按字编址，每个单元存放一个字符。串的长度不显式存储，由串中字符占存储单元的数目来隐式确定。 非紧缩存储方式方便了串运算，但存储空间没有得到有效利用。 例如对串s=“data structure 2.3”的非紧缩存储如右图所示。,定长顺序存储单字节存储方式,计算机按字节编址，每个字节存放一个字符。 每个地址对应一个字节，一个字节正好存放一个字符。这时的串长度也不必存储，由串占用的字节数隐式确定；也可用特殊字符作为串的结束标志，如用“0”作结束标志。 这种存储方式既不浪费空间，又使串中每个字符与惟一地址对应方便了运算，对于按字节编址的计算机而言是非常合适的。 例如对串s=“data structure 2.3”的单字节存储方式如右图所示。,定长顺序存储结构的运算实现,为了方便讨论，我们把串的类型说明改写成如下形式： #define STRINGLEN 81 struct string int len; static char chSTRINGLEN； typedef struct string STRING； 并假定串尾以“0”作结束标志。 由于串赋值和串复制在高级程序设计语言中是通过赋值语句来完成的，所以在这里只讨论其余四种基本运算，即串比较、求串长、串联接和求子串运算。,1.串比较,int StrCompare(s,t) /*串的比较，若st返回值0，若s=t返回值=0，否则返回值chi=t-chi) 该算法的主要时间开销在于两串相等时的逐个字符比较，比较次数为字符串的长度，所以在最坏情况下的时间复杂度为O(mins-len,t-len)；在最好情况下是当两串的第一个字符不等时，只需要O(1)的时间，与问题规模即串的长度无关。,2.求串长（1）,按假设的串类型说明，由于有串长域len故可直接返回其值即可。 算法描述如下： int StrLength(s)/*求串长即串s中字符的个数*/ STRING *s; return s-len; /*直接返回串长域的值即可*/,2.求串长（2）,在C语言中是没有设串长域的，需要对一维字符数组中的字符个数统计结果。 所以改写算法为： int StrLength(s) STRING *s; int i=0; /*初始化数组下标和串长域len*/ s-len=0; while(s-chi!=0) s-len+； return s-len； 该算法的主要时间开销在于逐个字符统计串长度的循环，其时间复杂度为O(s-len)。,3.串联接,在实现串的联接运算时，要注意两串s和t联接后的结果串L超过定长的问题，即：s-len+t-len=STRINGLEN时结果串超过定长STRINGLEN，此时算法中输出相应提示信息。 其算法描述如下： void StrConcat(l,s,t) STRING *l,*s,*t; int i,j; if(s-len+t-lenSTRINGLEN) printf(“结果串L的长度超过串的定长STRINGLEN!n”); else for(i=0;s-chi!=0;i+) l-chi=s-chi; for(j=0;t-chj!=0;j+) l-chi+j=t-cht; li+j=0; l-len=s-len+t-len; ,3.串联接（续）,该算法的时间开销主要在于复制两个串中字符到结果串中，其复制字符个数为两个串的长度之和，故其时间复杂度为O(s-len+t-len)。 串的联接运算不满足交换律，这一点由串联接的定义是显而易见的。 然而，串的联接运算是满足结合律的；在多个串联接时，只要位置次序不变，先联接哪两个都无所谓，最终结果都是一样的。,4.求子串,在设计求子串算法时要注意算法的健壮性要求，即要检查子串开始位置i和子串长度len的合法性。 当ilen时，子串开始位置非法； 当lens-len-i时，子串的长度非法。 对于这些非法的数据（参数），要给出相应的错误信息。 求子串的算法描述如下： void SubString(t,s,i,len) STRING *t,*s; int i,len; int j; if(i=s-len) printf(“子串的开始位置i越界错误n”);,4.求子串（续）,else if(lens-len-i) printf(“子串的长度len越过主串错误n”); else for(j=0;jchj=s-chi /*将所求子串存入t串中*/ t-chj=0; /*为子串t添加结束标志*/ t-len=len; /*设置子串长度*/ 该算法的主要时间开销在于从主串s中取出子串存于t中，而子串的最大长度等于主串，主串最长为预先定义好的定长STRINGLEN，所以其时间复杂度为O(STRINGLEN)。,2.3 串,2.3.1 串的基本概念 2.3.2 串的定长顺序存储及运算实现 2.3.3 模式匹配 2.3.4 串的堆式动态存储及运算实现 2.3.5 汉字串,模式匹配,子串的定位操作通常称作模式匹配，子串t称作模式，在主串s中确定t的位置的过程称作匹配过程。 模式匹配在文本编辑、文件检索和各种串处理系统中有着广泛的应用，因此它是最重要的串运算之一。然而模式匹配不是串的基本运算，它可以借用串的基本运算来实现。 利用串比较、求串长和求子串三种基本操作实现模式匹配的算法描述： int StrIndex(s,t) /*匹配成功返回子串位置，否则返回-1*/ STRING *s,*t; int n,m,i,bool; STRING *l; n=StrLength(s); /*求主串s的长度于n*/,模式匹配（续）,m=StrLength(t); /*求模式串t的长度于m*/ i=0; bool=-1; while(i0) return i; else return -1; ,简单的模式匹配算法,简单的模式匹配算法的思想是： 从主串s的第一个字符开始和模式t的第一个字符比较， 若相等则继续逐个比较后续字符， 若某一次对应字符不相等则从主串s 中的第二个字符起再重新和模式t的每个字符逐个比较。 依次类推，直到模式t中每个字符都和主串s中的一个连续字符序列对应相等则匹配成功，函数值为模式t中第一个字符所对应的字符在主串s中的序号； 若扫描完主串s后还未找到模式t 的出现则匹配失败，函数值为-1。,简单的模式匹配的过程描述,对于模式串t=“abcac”和主串s=“ababcabcacbab”使用算法Index(s,t)的匹配过程如下：,简单的模式匹配的过程描述(续),简单的模式匹配的算法（续）,算法Index(s,t)简单，算法思想自然，匹配过程容易理解。 在许多应用场合如文本编辑等，匹配效率也较高。 在这样一种较好的匹配情况下，即每趟中不成功的匹配都发生在第一对字符比较时，其时间复杂度为O(n+m)。 然而在最坏情况下，即每趟不成功的匹配都发生在模式串t中最后一个字符时，其时间复杂度为O(n*m)，算法效率很低。,一种改进的模式匹配算法,这种改进的模式匹配算法是D.E.Knuth与J.H.Morris和V.R.Pratt同时发现的，因此人们称它为克努特莫里斯普拉特算法，简称为KMP算法。 该算法可以在O(n+m)的时间数量级上完成串的模式匹配运算。 其改进思想是充分利用部分匹配的信息，不需回溯主串指示器变量i，而是在匹配过程中出现字符比较不等时，将模式串t尽可能远地向右滑动一段距离后继续进行比较。,一种改进的模式匹配算法（续）,回顾前述的匹配过程示例，在第三趟的匹配中当i=6、j=4比较字符不等时，又从i=3、j=0重新开始比较。仔细观察可以发现，在i=3和j=0、i=4和j=0、i=5和j=0这三次比较都是不必进行的；这是由于从第三趟部分匹配的结果就可以得出主串中的第4、5和6个字符（即i=3、4和5）和模式串中的第2、3和4个字符（即j=1、2和3）相同为b、c和a，而模式串中的第一个字符（即j=0）是a无需再和这三个字符进行比较，仅需将模式串向右滑动三个字符的位置进行i=6、j=1时的字符比较即可。同理，在第一趟匹配中出现字符不等时，仅需将模式串向右滑动两个字符位置进行i=2、j=0时的字符比较。,一种改进的模式匹配的匹配过程,值得注意的是在整个匹配过程中i指示器变量的值没有回溯。,改进的模式匹配的一般化思路,对于模式串t=“t0t1tm-1”和主串s=“s0s1sn-1”，当匹配过程中sitj产生失配时，模式串向右滑动多远距离？ 或者说失配时i指示器变量不回溯，主串中第i个字符应该与模式串中哪个字符再继续比较？ 设此时应该与模式串中第k(kj)个字符比较，则模式t中前k-1个字符的子串应该满足如下关系： “t0t1tk-2”=“si-k+1si-k+2si-1” 且不存在大于k的这样的关系式。而已得到的部分匹配结果可表示为： “tj-k+1tj-k+2tj-1”=“si-k+1si-k+2si-1” 由前面两式可以推出下式： “t0t1tk-2”=“tj-k+1tj-k+2tj-1”,改进的模式匹配的一般化思路,“t0t1tk-2”=“tj-k+1tj-k+2tj-1”等式说明，在某趟匹配过程中sitj失配时，如果模式串中前j-1个字符中存在首尾相同的最大子串长度为k-1，即模式t中前k-1个字符与tj前的k-1个字符对应相等时，模式t就可以向右滑动k个字符位置即si与tk继续比较了。 模式t中的每一个tj都对应一个k值，这个k值表示当在tj处失配时模式t应向右滑动的字符数，它仅依赖于模式t而与主串s无关。 令nextj=k，则可引出next函数的定义如下：,改进的模式匹配的一般化思路,由next函数的定义可推出模式“abaabcac”的next函数值为： 有了next函数之后，匹配过程可以这样进行：令指示器变量i和j的值都为0，若在匹配过程中si=tj；则i和j分别加1，否则i不变而j退到nextj的位置再比较；若相等i和j各加1，否则j退到下一个next值的位置，依此类推直到下面两种可能： 一是退到某next值（nextnextnextj）时字符比较相等，指示器变量值各加1后继续比较； 另一种是退到值为零（即模式的第一个字符失配），此时需将模式继续向右滑动一个位置，从主串的下一个字符si+1重新开始匹配。,改进的模式匹配的KMP算法描述,int index_KMP(s,t) STRING *s, *t; int i,j; if(t-len=0)|(s-lenlen) return -1; else i=0; j=0; while(ilen) ,运用算法index_KMP的匹配过程,求模式串t的next函数值的算法,void getnext(STRING *t, int next) /*求模式串t的next函数值并存入数组next中*/ int i,j; i=0; j=-1; nexti=0; /*初始化指示器变量并给next0赋零值*/ while(i len) if(j=0)|(t-chi=t-chj) i+; j+; nexti=j; else j=nextj; ,一种改进的模式匹配算法（续）,算法getnext的时间复杂度为O(m)。通常模式串的长度m要比主串的长度n小得多，因此对整个匹配算法KMP来说增加这点求next函数的时间是值得的。 需要说明的是，算法index的时间复杂度虽然是O(m*n)，但在一般情况下其实际执行时间近似于O(m+n)，所以至今仍被采用。 算法index_KMP仅当模式串与主串之间存在许多部分匹配的情况下才显得比算法index快得多。 index_KMP算法的最大特点是不需回溯主串的指示器变量i，整个匹配过程只需从头到尾扫描主串一遍，特别适用于从外设读入庞大文件边读入边匹配，无需回头重读。,2.3 串,2.3.1 串的基本概念 2.3.2 串的定长顺序存储及运算实现 2.3.3 模式匹配 2.3.4 串的堆式动态存储及运算实现 2.3.5 汉字串,串的堆式动态存储,在处理串的应用程序中，所处理的串的长度相差往往较大，处理过的串值长度变化往往也较大。 采用定长顺序存储在多数串的串长较小时其空间利用率低，且使某些运算如串联接和串置换等受到限制或产生错误结果。 因此，在许多实际应用的串处理系统中采用的是堆式动态存储分配策略。,堆式动态存储的思想,应用系统在内存中开辟一个容量很大且地址连续的一片存储空间，作为存放所有串值的可利用空间即堆空间。 例如一维数组store char storemaxsize 表示堆空间，其中maxsize表示这片连续存储空间的最大容量。 设整形变量free指示该空间中尚未分配区间的开始地址（初始值为1）。 每当产生一个串时，应用程序就在执行过程中动态地从free指示的位置为串值分配一个长度与串长相同的存储空间，并相应修改free的值； 同时建立该串的一个描述，指示串的长度和该串在store中的第一个字符位置。,串的堆式动态存储分配示意图,其中：length指示串值序列的长度， start指示串值序列在store中的开始地址。,串的存储映像,借助length和start在堆结构的串名与串值之间建立起一个对应关系，称作串名的存储映像。 所有的串名存储映像构成了一张为系统中所有串名和串值之间建立一一对应关系的映像表（或符号表）。,堆式动态存储的串的类型说明,#define MAXSIZE 10000 /*MAXSIZE为堆的最大容量*/ struct string /*定义串为结构体*/ int length; /*串长度*/ int start; /*串在堆中的开始位置*/ typedef struct string STRING; /*定义串类型标识符为STRING*/ char storeMAXSIZE; /*定义堆为一维数组store*/ int free; /*堆store中尚未分配区间的开始地址指示器变量*/,堆式动态存储的串赋值算法,该运算把存储于字符串数组chars中的字符串常量存入堆store中，并为s建立存储映像。在逻辑上即为串变量s赋一个字符串常量值。 其算法描述如下： void StrAssign(s,chars) STRING *s; char chars; int i,len; i=0; /*为统计字符串常量中的字符个数初始化*/ while(charsi!=0) /*统计chars中字符个数*/ i+; len=i;,堆式动态存储的串赋值算法(续),if(lenMAXSIZE) printf(“串常量为空串或堆的尚未分配区间空间不足n”)； else for(i=0;istart=free; /*建立存储映像*/ s-length=len; free=free+len; /*修改堆中的指示器变量free的值*/ ,堆式动态存储的串复制算法,该运算把堆中的串t复制到s中去。算法如下： void StrCopy(s,t) STRING *s,*t; int i; if(free-1+t-lengthMAXSIZE) printf(“堆中空间不足”)； else for(i=0;ilength;i+) /*逐字符复制* storefree+i=storet-start+i; s-length=t-length; /*建立存储映像*/ s-start=free; free=free+t-length; 串复制运算也可以共享堆中t的存储空间，只建立s的存储映像，但若对其中之一修改就会影响到另一个。,堆式动态存储的串联接算法,只要分别将s串和t串复制到store中为l开辟的存储区，并建立l的存储映像即可完成串联接运算。算法如下： void StrConcat(l,s,t) STRING *l,*s,*t; STRING *p; /*设一个内部串变量p*/ StrCopy(l,s); /*复制s到l中去*/ StrCopy(p,t); /*复制t到p中去*/ l-length=s-length+t-length; /*修改l的存储映像中的串长*/ 注意，为什么算法中没有修改l的开始位置？又为什么未见修改堆中指示器变量free的语句？这是因为第一个串复制语句已使l的开始位置到位，而第二个串复制语句已使free的值指向尚未分配区的开始位置，故只需修改串长即可。,堆式动态存储的求子串算法,和串复制运算一样，求子串运算也有复制和共享两种实现方法。这里给出共享实现算法如下： void SubString(t,s,i,len) /*将s中第i个字符开始的len个字符构成的子串送到t中*/ STRING *t,*s; int i,len; if(is-length-i) printf(“所给子串的位置或长度有错误n”); else t-length=len; /*建立子串t的存储映像*/ t-start=s-start+i; ,2.3 串,2.3.1 串的基本概念 2.3.2 串的定长顺序存储及运算实现 2.3.3 模式匹配 2.3.4 串的堆式动态存储及运算实现 2.3.5 汉字串,汉字串,汉字是一种拼形和表意文字。 无论是西文还是汉字，计算机系统均应具有输入、加工处理和输出的功能，并能在不同的系统之间进行信息交换。 对应于不同的功能，在计算机系统中用不同的代码来表示： 用户在输入设备上输入文字信息时，由输入设备产生相应的代码称作输入码或外部码； 在计算机内部存储和处理文字信息所采用的代码称作机内码； 为了表示文字字形，通常是设计表示不同字形的字模点阵，这种码称作字模点阵码； 在系统之间传输和交换信息的代码称作交换码。,汉字串（续）,对于西文来说，由于借助于拼音规则可只用少量字母拼成文字，因而其机内码、输入码和交换码等的数据结构都比较简单； 在设计这些代码时已尽可能做到相互一致，代码间的转换也非常简单。 目前大多数计算机均以ASCII码作为西文的机内码，也有用EBCDIC码作机内码的，它们都是按每个字节存放一个字符设计的。 当向计算机输入西文信息时，只要在键盘上按不同的键就可产生不同的输入代码，这些输入码集可以简单地等同于机内码集。 因此，当构成串的字符集限于西文字母、数字和其它字符时，往往不考虑它的机内码而直接讨论串值的存储结构。,汉字代码转换关系示意图,采用汉字串标识法的七位码方法,以ASCII码集或其子集作为基集，由两个或两相以上的ASCII字符构成一个汉字机内码。 例如，用电报码作为汉字机内码。电报码是以ASCII字符集的子集C=0,1,29为基集，由四个09的数字字符构成一个汉字机内码。为了与西文ASCII字符区分，可选用“（”来表示西文串的标记符而用“）”表示汉字串的标记符；这样使得括号以内的符号全部保留ASCII码集字符的意义，而括号以外的符号就是汉字串的机内码了。如下图 这种存储方法，对于顺序地从前向后逐个处理的运算操作是很适用的，但对于某些随机性的操作却不很方便。,采用代码标识法的八位码方法,以我国“信息交换用汉字编码字符集基本集GB2312-80”为基础，在每个汉字代码中设标志作为汉字机内码。 国标交换码规定由两个字节构成一个汉字交换码，每个字节都用七位，最高位均为0。 现将国标交换码每个字节的最高位均置1以形成八位码来作汉字机内码。以汉字“大”为例，其机内码如下图。,采用代码标识法的八位码方法(续),除了采用国标码外，还有使用国标区位码的方案。 区位码中，每个汉字对应四个十进制数字，前两位是区号共94个区，每区94位。 国标区位码和国标码之间可用计算公式相互转换。 区位码转换为国标码的方法是，先将十进制区位码转换成十六进制，然后在两个字节上分别加20（十六进制）就得到国标码。 在国标码的两个字节上各加80（十六进制）就转换为汉字机内码了。 目前应用较为广泛的是采用国标码和区位码进行代码标识，形成两字节汉字机内码。这种两字节的汉字机内码，可以很方便地从汉字的序数计算出该汉字在字符串中的存储位置。,汉字区位码转换为机内码的过程,以汉字“雹”为例的转换过程如下：,采用汉字标识法的多个字节代码,在每个汉字代码前增加一个标识字节，就形成所谓多字节的汉字机内码。例如将汉字国标码转换成字母和数字表示的三个字节，然后在这三个字节之前增加一个汉字标记字节，这种标记字节可用来适应各种不同的要求。但是这种机内码的编辑性较差，占用字节量大；一般用在要求较高的软件系统中或传输过程中作为系统