串(即字符串)是一种特殊的线性表.docVIP

PAGE PAGE 75第四章 串 串（即字符串）是一种特殊的线性表，它的数据元素仅由一个字符组成，计算机非数值处理的对象经常是字符串数据，如在汇编和高级语言的编译程序中，源程序和目标程序都是字符串数据；在事物处理程序中，顾客的姓名、地址、货物的产地、名称等，一般也是作为字符串处理的。另外串还具有自身的特性，常常把一个串作为一个整体来处理，因此，在这一章我们把串作为独立结构的概念加以研究，介绍串的串的存储结构及基本运算。4.1 串及其基本运算4.1.1 串的基本概念１．串的定义串是由零个或多个任意字符组成的字符序列。一般记作：s=＂s1 s2 … sn＂＂其中s 是串名；在本书中，用双引号作为串的定界符，引号引起来的字符序列为串值，引号本身不属于串的内容；ai(1=i=n)是一个任意字符，它称为串的元素，是构成串的基本单位，i是它在整个串中的序号; n为串的长度，表示串中所包含的字符个数，当n=0时，称为空串，通常记为Ф。 ２．几个术语子串与主串：串中任意连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。子串的位置：子串的第一个字符在主串中的序号称为子串的位置。串相等：称两个串是相等的，是指两个串的长度相等且对应字符都相等。4.1.2 串的基本运算 串的运算有很多，下面介绍部分基本运算：求串长StrLength(s)操作条件：串s存在操作结果：求出串s的长度。串赋值StrAssign(s1,s2)操作条件： s1是一个串变量，s2或者是一个串常量，或者是一个串变量（通常s2 是一个串常量时称为串赋值，是一个串变量称为串拷贝）。操作结果：将s2的串值赋值给s1， s1原来的值被覆盖掉。连接操作 ：StrConcat (s1,s2,s) 或StrConcat (s1,s2) 操作条件：串s1,s2存在。 操作结果：两个串的联接就是将一个串的串值紧接着放在另一个串的后面，连接成一 个串。前者是产生新串s，s1和s2不改变; 后者是在s1的后面联接s2的串值，s1改变， s2不改变。例如： s1=＂he＂，s2=＂ bei＂，前者操作结果是s=＂he bei＂；后者操作结果是s1=＂he bei＂。求子串SubStr (s,i,len)： 操作条件：串s存在，1≤i≤StrLength(s)，0≤len≤StrLength(s)-i+1。操作结果：返回从串s的第i个字符开始的长度为 len 的子串。len=0得到的是空串。 例如：SubStr(＂abcdefghi＂,3,4)= ＂cdef＂串比较 StrCmp(s1,s2)操作条件：串s1,s2存在。操作结果：若s1==s2，操作返回值为0；若s1s2, 返回值0；若s1s2, 返回值0。子串定位 StrIndex(s,t)：找子串t在主串s中首次出现的位置操作条件：串s,t存在。操作结果：若t∈s，则操作返回t在s中首次出现的位置，否则返回值为-1。如：StrIndex(＂abcdebda＂,＂bc＂)=2 StrIndex(＂abcdebda＂,＂ba＂)=-1串插入 StrInsert(s,i,t)操作条件：串s,t存在，1≤i≤StrLength(s)+1。操作结果：将串t插入到串s 的第i个字符位置上，s的串值发生改变。串删除 StrDelete(s,i,len)操作条件：串s存在，1≤i≤StrLength(s)，0≤len≤StrLength(s)-i+1。操作结果：删除串s 中从第i个字符开始的长度为len的子串，s的串值改变。串替换　StrRep(s,t,r)操作条件：串s,t,r存在，t不为空。操作结果：用串r 替换串s中出现的所有与串t相等的不重叠的子串，s的串值改变。以上是串的几个基本操作。其中前５个操作是最为基本的，它们不能用其他的操作来合成，因此通常将这５个基本操作称为最小操作集。4.2 串的定长顺序存储及基本运算因为串是数据元素类型为字符型的线性表，所以线性表的存储方式仍适用于串，也因为字符的特殊性和字符串经常作为一个整体来处理的特点，串在存储时还有一些与一般线性表不同之处。4.2.1 串的定长顺序存储类似于顺序表，用一组地址连续的存储单元存储串值中的字符序列，所谓定长是指按预定义的大小，为每一个串变量分配一个固定长度的存储区，如：#define MAXSIZE 256 char s[MAXSIZE]; 则串的最大长度不能超过256。 如何标识实际长度？1. 类似顺序表，用一个指针来指向最后一个字符，这样表示的串描述如下：typedef struct { char data[MAXSIZE];int curlen;} SeqString;定义一个串变量：SeqStr