串、多维数组与广义表

《串、多维数组与广义表》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章串、多维数组与广义表4.1串串又称字符串，是一种特殊的线性表，它的每个元素仅由一个字符组成。计算机上非数值处理的对象基本上是字符串数据。在较早的程序设计语言中，字符串仅作为输入和输出的常量出现。随着计算机应用的发展，在越来越多的程序设计语言中，字符串也可作为一种变量类型出现，并产生了一系列字符串的操作。在信息检索系统、文字编辑程序、自然语言翻译系统等等应用中，都是以字符串数据作为处理对象的。4.1.1串的定义串(string)(或字符串)是由零个或多个字符组成的有限序列，一般记为：S="a

2、1a2……an"(n≥0)串名：串的名字S。串值：用双引号括起来的字符串序列，ai(1≤i≤n)可以是字母、数字或其他字符。串的长度：串中字符的个数n称为串的长度。串相等：只有当两个串的长度相等，并且各个对应位置上的字符都相等时，才能称为串相等。4.1.1串的定义子串：串中任意个连续的字符组成的子序列称为该串的子串。主串：包含子串的串称为该子串的主串。例如：S1＝"anhui"，S2="huaibei"，S＝"anhuihuaibei"，其中S1、S2都是S的子串。S为S1、S2的主串。空格串：

3、由一个或多个空格组成的串称为空格串，空格串的长度不为零。空串：长度为0的串称为空串，通常用来表示，在C程序中表示成"",它是任意串的子串。模式匹配：求子串在主串中的起始位置称为子串定位或模式匹配。例如：S1在S中的位置是1，而S2在S中的位置是7。4.1.1串的定义ADTString{数据对象D：D={ai

4、ai∈ElemSet，i=1,2,…,n,n≥0}数据关系R：R={

5、ai-1,ai∈D，i=2,3,…,n}基本操作P：串赋值StrAssign(&S,chars)：S是

6、一个串变量，chars是一个串常量。将chars的值赋给串S；串比较StrCompare(S,T)：若串变量S>串变量T，则返回值>0；若S=T，则返回值为0；若S

7、T,S,pos,len)：1≤pos≤StrLength(S)，0≤len≤StrLength(S)-pos+1，用T返回S中的第pos个字符起长度为len的子串；4.1.1串的定义判断空串StrEmpty(S)：若S为空串，则返回TRUE，否则返回FALSE；串复制StrCopy(&T,S)：将串S复制到串T；串清空ClearString(S)：将S置空串；串定位StrIndex(S,T,pos)：串S和T存在，T是非空串，1≤pos≤StrLength(S)，若T是S的子串，返回T在S中第一

8、次出现的位置，否则返回0；串置换Replace(&S,T,V)：串S，T和V存在，T是非空串，用V替换主串S中出现的所有与T相等的不重叠的子串。例如：设S＝"bbabbabba"，T＝"ab"，V＝"a"，则Replace(&S,T,V)的结果是S＝"bbababa"；串插入StrInsert(&S,pos,T)：1≤pos≤StrLength(S)+1，在串S的第pos个字符之前插入串T；串删除StrDelete(&S,pos,len)：1≤pos≤StrLength(S)-len+1，从串S

9、中删去第pos字符起长度为len的子串；串销毁DestroyString(&S)：串S被销毁，并回收串空间；}ADTString4.1.1串的定义以上定义的13种操作，其中前五个操作是最基本的，被称为最小操作集。其他操作（串清空、串销毁除外）均可在这个最小操作集上实现。4.1.1串的定义例如：用求串长、求子串和串比较实现串定位，算法描述如下：intStrIndex(StringS,StringT,intpos){intn,m,i;Stringsub;if(pos>0){n=StrLength(S

10、);m=StrLength(T);i=pos;while(i<=n-m+1){SubString(sub,S,i,m);if(StrCompare(sub,T) !=0)++i;elsereturni;//返回子串在主串中的位置}//while}//ifreturn0;//S中不存在与T相等的子串}//StrIndex4.1.2串的表示和实现串的表示有三种方式：顺序串、堆串和链串4.1.2串的表示(串的定长顺序存储表示)方法一：#defineMAXSIZE100typedefstruct{cha