数据结构串总结.pptVIP

第四章串

在计算机的各方面应用中,非数值处理问题的应用越来

越多。在早期的程序设计语言中,串仅作为输入和输出

的常量出现。随着计算机应用的扩展,需要在程序中进

行对串的操作,如在事务处理系统中,用户的姓名和

地址及货物的名称、规格等也是字符串数据

字符串一般简称为串,可以将它看作是一种特殊的线性

表,这种线性表的数据元素的类型总是字符型的,字符

串的数据对象约束为字符集。在一般线性表的基本操作

中,大多以“单个元素”作为操作对象,而在串中,则

是以“串的整体”或一部分作为操作对象。因此,一般

线性表和串的操作有很大的不同。本章主要讨论串的基

本概念、存储结构和一些基本的串处理操作

【知识点】串的类型定义、串的存储表示、串匹配

4.1串的基本概念42串的存储结构

4.3串的基本运算及其实现44模式匹配

4.5串的应用46小结47练习

41串的基本概念

串的定义

串(string,或称字符串)是n个字符的有限序列。通常

记作s=‘a1a2a3,…an(n≥0)

其中,S是串的名字;用单引号括起来的字符序列是

串的值;a(1s≤n)可以是字母、数字或其它字符;单弓

号为串值的定界符,不是串的一部分,它的作用是为了

避免与变量名或数值常量混淆;串中字符的数目n称为串

的长度。含零个字符的串称为空串(nullstring),它的长

度为零,通常以两个相邻的引号来表示空串。

如:s

它的长度为零

在各种应用中,空格通常是串的字符集合中的一个元素

可以出现在其他字符之间。如:s=“是仅由空格组成

的的串称为空格串。若串中含有空格,在计算串长时,

空格应计入串的长度中,如:s=Iamastudent的长度

为

主串和子串

个串的任意个连续的字符组成的子序列称为该串的子

串,包含该子串的串称为主串。称一个字符在串序列中

的序号为该字符在串中的位置,子串在主串中的位置是

以子串的第一个字符在主串中的位置来表示的。当一个

字符在串中多次出现时,以该字符第一次在主串中出现

的位置为该字符在串中的位置。两个字符串的长度相等

且各对应位置上的字符都相同,则两串相等

例如:s1、s2、s3为如下的三个串:s1=Iama

student’;s2=student’;s3=“teacher

则它们的长度分别为14、7、7;串s2是s1的子串,子串

s2在s1中的位置为8,也可以说s1是s2的主串;串s3不是

s1的子串,串s2和s3不相等。

42串的存储结构

对串的存储方式取决于我们对串所进行的运算,如果在

程序设计语言中,串的运算只是作为输入或输出的常量

出现,则此时只需存储该串的字符序列,这就是串值的

存储。此外,一个字符序列还可赋给一个串变量,操作

运算时通过串变量名访问串值。

对于串的存储可以有两种处理方式:一是可以将串定义

为字符型数组,数组名就是串名,串的存储空间分配在

编译时完成,程序运行时不能更改。这种方式为串的静

态存储结构。另一种是定义字符指针变量,存储串值的

首地址,通过字符指针变量名访问串值,串的存储空间

分配是在程序运行时动态分配的,这种方式称为串的动

态存储结构。

静态存储采用顺序存储结构,动态存储采用的是链式存

储和堆存储结构。

串的静态存储结构(加存储结构)

类似于线性表的顺序存储结构,用一组地址连续的存储

单元存储串值的字符序列。由于一个字符只占1个字节,

而现在大多数计算机的存储器地址是采用的字编址,

个字(即一个存储单元)占多个字节,因此顺序存储结

构方式有两种

(1)紧缩格式:即一个字节存储一个字符。这种存储方

式可以在一个存储单元中存放多个字符,充分地利用

存储空间。但在串的操作运算时,若要分离某一部分字

符时,则变得非常麻烦。

右图所示是以4个字节为

L

个存储单元的存储结构,每

个存储单元可以存放4个字

符。对于给定的串s=Love

China。串s的串值的长度共

10,只需3个存储单元。

(2)非紧缩格式:这种方式是以一个存储单元

为单位,每个存储单元仅存放一个字符。这种存

储方式的空间利用率较低,如一个存储单元有4

个字节,则空间利用率仅为25%。但这种存储方

式中不需要分离字符,因而程序处理字符的速度

高。下图即为这种结构的示意图。

由上述讨论可知,串的顺序存储

结构有两大不足之处:一是需事

先预定义串的最大长度,这在程

序运行前是很难估计的。二是由

于定义了串的最大长度,使得串

的某些操作受限,如串的联接运

算等

二、串的动态存储结构

我们知道,串的各种运算与串的存储结构有着很

大的关系,在随机取子串时,顺序存储方式操作

起来比较方便,而对串进行插入、删除等操作时

,就会变得很复杂。因此,有必要采用串的动态

存储方式。

动态存储与顺序存储的区别是动态存储的存储空

间是在程序执行