《数据结构》--第四章-串.ppt

第4章串学习目的要求:*第4章串串的基本概念和串的基本运算。串的顺序存储结构、串的链式存储结构和串的索引存储结构。串的顺序存储中的连接、相等判断、取子串、插入、删除和子串查找算法的实现。4.1串的基本概念4.2串的存储结构4.3串的基本运算4.4串的应用举例第4章串4.1串的基本概念串是一种特殊的线性表，它的数据对象是字符集合，它的每一个元素都是一个字符，一系列相连的字符就组成了一个字符串。字符串简称串记作:s=a1a2a3…an（n≥0）其中，S是串的名字，用双引号括起来的字符序列是串的值。ai（1≤i≤n）可以是字母、数字或其他字符。4.1串的基本概念串的长度:串中字符的数目（n）。空串:不含任何字符的串，它的长度n=0，记为s=。空格串:仅由空格组成的串，串的长度为空格的个数。【注意】空串与空格串的区别。例如，和分别表示长度为0的空串和长度为1的空格串。4.1串的基本概念子串:串中任意个连续字符构成该串的子串，而包含该子串的串称为母串。子串在母串中首次出现时，该子串的首字符在母串中的位置称为子串在母串中的位置。两串相等:两个串的长度相等，且相同位置上的字符相同。4.2串的存储结构对串的存储一般有两种处理方式：将串定义成字符型数组，由串名可以直接访问到串值。串的存储空间是在编译时分配完成的，其空间大小不能更改。这种存储方式称为串的静态存储结构（采用顺序存储）。串的存储空间是在程序运行时动态分配的，并可根据需要随时进行再次分配与释放，从而动态地改变其空间的大小，这种方式称为串的动态存储结构（采用链式存储或索引存储）。4.2.1串的静态存储结构串的静态存储结构采用顺序存储结构，简称为顺序串。在计算机中，一个字符只占一个字节，所以串中的字符是顺序存放在相邻字节中的。串的顺序存储可用一个字符型数组和一个整型变量来表示，其中字符型数组存放串值，整型变量存放串的长度。4.2串的存储结构4.2.1串的静态存储结构当计算机按字节（byte）单位编码时，一个机器字，即一个存储单元刚好存放一个字符，串中相邻的字符顺序的存放在地址相邻的字节中。例如，给定串s=“goodmornig”，则顺序串的存储结构如下图所示。4.2串的存储结构当计算机按字（word）单位编址时，一个字（即一个存储单元）由若干个字节组成。这时串的顺序存储结构有非紧缩存储和紧缩存储两种方式。4.2串的存储结构1.串的非紧缩存储一个存储单元仅存放一个字符。优点：对串中的字符处理效率高。缺点：对存储空间的利用率低。4.2串的存储结构2.串的紧缩存储根据计算机中字的长度，尽可能将多个字符存放在一个字中。优点：对存储空间的利用率高。缺点：对串的单个字符操作很不方便，需要花较多的处理时间。4.2.2串的链式存储结构串的链式存储结构也称为链串，结构与链表类似，链串中每个结点有两个域，一个是值域（data），用于存放字符串中的字符，另一个是指针域（next），用于存放后继结点的地址。一个链串一般是由头指针唯一确定的。4.2串的存储结构优点：插入、删除运算很方便。存储密度=串值所占的存储位/实际分配的存储位为了提高存储密度，可让每个结点的值域存放多个字符。这种结构也叫做大结点结构。如串s=“goodmorning!”的存储结构如下图所示。4.2串的存储结构用特殊字符来填充最后一个结点，以表明串的结束。大结点结构节约了存储空间，但是对字符串进行插入或删除运算时，会引起大量的字符移动。4.2串的存储结构4.2.3串的索引存储结构串的索引存储结构的构造方法：首先开辟一块地址连续的存储空间，用于存放各串本身的值。再另外建立一个索引表。在索引表的项目中存放一个串的名称、长度和在存储空间中的起始地址。4.2串的存储结构4.2.3串的索引存储结构例如:a=youb=arec=ad=student4.2串的存储结构索引表存放串值的连续存储空间4.3串的基本运算1、串连接: connect(s1，s2)将串s2连接在s1的尾部，形成一个新串。2、两串相等判断: equal(s1，s2)