沈阳工业大学信息科学与工程学院数据结构课件 第4章.ppt

第4章 串 串是字符串的简称，是一种特殊的线性表,它的每个数据元素由一个字符组成。 4．1 串的基本概念和抽象数据类型 4.1.1串的基本概念 串(string)：是由零个或多个字符组成的有限连续序列。串就是一串字符,一般记为 S =s1 s2 …sn 其中，S是串的名字，双引号括起来的字符序列s1 s2 …sn 是串的值，字符个数n称作串的长度 每个si , i称为字符ai在串中的位置。 空串(null string)：是由零个字符组成的串。空串中不包含任何字符，它的长度是0，记为S=。 空格串：是由一个或多个空格组成的串。它不等于空串，它的长度是串中包含的空格数。字符串中空格也算在串长度中。 子串：字符串中任意个连续的字符构成的子序列称为该字符串的子串。空串是任何串的子串。 主串：包含子串的字符串称为主串。 位置：一个字符在序列中的序号称为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。 两串相等：两个字符串的长度相等且各对应位置上的字符都相同。串也可以比较大小。 串变量：下面这个语句S=“abcde”是一个合法的赋值语句，其含义是把串值赋给串变量S，S是串变量名，字符序列abcde是串值。 例：串a=SHEN，b=YANG，c=SHENYANG，d=SHEN YANG,则a、b、c、d的串的长度分别为4、4、8、9。串a、b都是串c、d的子串，其在主串c中的位置分别为1和5，在主串d中的位置分别为1和6。 注意以下几点： (1)串值必须用双引号括起来，但双引号本身不属于串。双引号的作用只是为了避免字符串和变量名或数值常量混淆。 (2)空串和空格串的区别：不含任何字符的串称为空串，其长度为0。含有空格字符的串称为空格串。它的长度为串中空格符的个数。空串在串处理中可作为任意串的子串。 (3)值为单个字符的字符串不等同于单个字符，例如，字符串 a不等同于字符 a,在C++中的存储也不相同。 (4)两串相等包含两层含义：首先两个字符串的长度相等，其次，各对应位置上的字符都相同。 4.1.2 串的抽象数据类型 串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。 然而，串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以“单个元素”作为操作对象，例如在线性表中常用的查找某个元素、在某个位置上插入一个元素和删除一个元素等；而在串的基本操作中，通常以“串的整体”作为操作对象，例如在串中查找某个子串、在串的某个位置上插入一个子串以及删除一个子串等。 4．2 串的存储结构 串是线性表的一个特例，用于线性表的顺序和链式存储结构当然也适用于串。但是，串中数据元素全部为字符 串的存储可以有两种处理方式：一种是将串定义成字符型数组，称为串的静态存储结构 另一种是串的存储空间在程序运行时动态分配，这种方式称为串的动态存储。 串的静态存储结构即串的顺序存储结构，串的动态存储结构有两种方式：一种是链式存储结构，另一种是称为堆结构的存储方式 4．2．1 串的顺序存储结构 可以用一组连续的存储单元依次存储串中的各个字符,使得逻辑上相邻的字符，在物理上也是相邻的。在C++语言中，字符串的顺序存储可用一个字符型数组和一个整型变量表示，其中字符型数组存储串值，整型变量存储串的长度。下面是串的顺序存储结构的C++描述。 const int maxSize=maxLen； //maxLen 表示串的最大容量 struct SeqString { char ch[maxSize]； //存放串的值的一维数组 int len； //当前串的实际长度 }； 当计算机按字节(Byte)为单位编址时，一个存储单元恰好存放一个字符，串中相邻的字符顺序地存储在地址相邻的字节中； 当计算机按字(word)为单位编址时，一个存储单元由若干字节组成。这时，顺序存储结构有紧凑格式和非紧凑格式两种存储方式。 (1)紧凑格式 所谓紧凑格式就是在存储单元中尽量地多存储字符。例如，S=〞My China〞，按紧凑格式可以存放在两个存储单元中(假设计算机的字长为32位，即4 字节为一个存储单元)，如图4-1所示。 (2)非紧凑格式 非紧凑格式是一个存储单元(4 字节)只存放字符串的一个字符，存储中多余的空间置空不用。图4-2所示是S=〞My China〞按非紧凑格式存储的示意图。 紧凑格式存储的优点是空间利用率高，缺点是对串中字符的处理效率低。非紧凑格式的优缺点则恰好相反。 4．2．2 串的链式存储结构 串的链式存储结构是包含字符域和指针域的结点链接结构。其中字符域用来存放串