数据结构chapter4串

1、1第第4 4章章 串（串（StringString）4.1 串的基本概念串的基本概念4.2 串的表示和实现串的表示和实现 2第第4章章 串（串（String） 字符串（简称串）对大家来说并不陌生。在解决实际问题时，经常字符串（简称串）对大家来说并不陌生。在解决实际问题时，经常会用到串操作。会用到串操作。一般地说，不同问题中所遇到的字符串具有不同特点。例如，在某一般地说，不同问题中所遇到的字符串具有不同特点。例如，在某些问题中，字符串都是些问题中，字符串都是100来个字符，比较均匀；而在有些问题中，一部来个字符，比较均匀；而在有些问题中，一部分字符串很长，另一部分字符串很短，起伏较大。分字符串很

2、长，另一部分字符串很短，起伏较大。显而易见，在处理不同特点的字符串时，应采用不同的存储结构，显而易见，在处理不同特点的字符串时，应采用不同的存储结构，只有这样，才能获得较高的效率。只有这样，才能获得较高的效率。在本章中，我们将讨论串的几种存储结构和一些基本操作。在本章中，我们将讨论串的几种存储结构和一些基本操作。 3第第4章章 串（串（String） 4.1 4.1 串类型的定义串类型的定义 一、串的定义一、串的定义 串是由串是由n（n0）个字符组成的序列，常记为）个字符组成的序列，常记为s=a1a2an 其中，其中， s为串的为串的名字名字 。 a1a2an称称为串的为串的值值。为了不至于与

3、变量名或常量混淆，串的值一定。为了不至于与变量名或常量混淆，串的值一定要用单引号括起来，但单引号本身不属于串。要用单引号括起来，但单引号本身不属于串。 串中字符的数目串中字符的数目n称为串的称为串的长度长度。长度为。长度为0的串称为的串称为空串空串，记为，记为 。 串中任意个连续的字符组成的子序列称为该串的串中任意个连续的字符组成的子序列称为该串的子串子串，原串称为，原串称为主串主串. 通常把字符在序列中的序号称为该字符在串中的通常把字符在序列中的序号称为该字符在串中的位置位置（从（从1开始）。开始）。 子串在主串中的位置子串在主串中的位置指的是子串的第一个字符在主串中的位置。指的是子串的第一

4、个字符在主串中的位置。 称两个串称两个串相等相等当且仅当串的值相等，即串的长度相等，而且对应位当且仅当串的值相等，即串的长度相等，而且对应位置上的字符相等。置上的字符相等。 4一、串的定义一、串的定义 可以看出，串和线性表都是有限的序列，逻辑结构很相似。但是，他可以看出，串和线性表都是有限的序列，逻辑结构很相似。但是，他们有两点区别：们有两点区别： 串的每个数据元素为单个字符，数据对象是某个字符集。串的每个数据元素为单个字符，数据对象是某个字符集。 串的基本操作和线性表的基本操作差别较大。串的基本操作和线性表的基本操作差别较大。 线性表的基本操作大多以线性表的基本操作大多以“单个元素单个元素”

5、为操作对象，例如，获取一为操作对象，例如，获取一个数据元素、插入一个元素以及删除一个元素等。个数据元素、插入一个元素以及删除一个元素等。 串的基本操作很少以单个字符为操作对象，而大多以串的基本操作很少以单个字符为操作对象，而大多以“串的整体串的整体”为操作对象，例如，在串中取一个子串、在串中插入为操作对象，例如，在串中取一个子串、在串中插入/删除一个子串等。删除一个子串等。 5二、串的抽象数据类型二、串的抽象数据类型 P71用抽象数据类型用抽象数据类型 String 描述了串及其基本操作。描述了串及其基本操作。 ADT String 数据对象：数据对象：D=ai|aiCharacterSet,

6、 i=1, ,n, n0 数据关系：数据关系：R1=|ai-1,aiD, i=2, ,n 基本操作：基本操作： StrAssign(&T, chars) 初始条件：初始条件：chars是字符串常量是字符串常量 操作结果：生成一个值为操作结果：生成一个值为chars的串的串T。 StrCopy(&T, S) 初始条件：串初始条件：串S已经存在。已经存在。 操作结果：由串操作结果：由串S复制得到串复制得到串T。 ADT String6三、串的基本操作三、串的基本操作 StrAssign(&S, chars)初始条件：初始条件： chars是字符串常量是字符串常量操作结果操作

7、结果：生成一个值为生成一个值为chars的串的串S。1.1.串赋值操作串赋值操作 StrCopy(&T, S)初始条件：串初始条件：串S已经存在。已经存在。操作结果：由串操作结果：由串S复制得到串复制得到串T。2.2.串复制操作串复制操作 StrEmpty(S)初始条件：串初始条件：串S已存在。已存在。操作结果：若操作结果：若S为空串，则返回为空串，则返回TRUE，否则，否则FALSE。3.3.判空操作判空操作7三、串的基本操作三、串的基本操作 StrCompare(S, T)初始条件：串初始条件：串S、T已存在。已存在。操作结果：若操作结果：若ST，则返回值，则返回值0; 若若S=T

8、，则返回值，则返回值=0; 若若ST，则返回值，则返回值0。4.4.串比较操作串比较操作 Concat(&T, S1, S2)初始条件：串初始条件：串S1、S2已存在。已存在。操作结果：用操作结果：用T返回由返回由S1与与S2连接而成的新串。连接而成的新串。6.6.串连接操作串连接操作 StrLength(S)初始条件：串初始条件：串S已存在。已存在。操作结果：返回串操作结果：返回串S中的字符个数。中的字符个数。5.5.求长度操作求长度操作8三、串的基本操作三、串的基本操作 SubString(&Sub, S, pos, len)初始条件：串初始条件：串S已存在，且已存在，且1

9、posStrLength(S), 0 len StrLength(S)-pos+1操作结果：用操作结果：用Sub返回返回S中从第中从第pos个字符起长度为个字符起长度为len 的子串。的子串。7.7.取子串操作取子串操作 Index(S, T, pos)初始条件：串初始条件：串S、T已存在，且已存在，且1posStrLength(S)。操作结果：操作结果：返回返回S中从第中从第pos个字符起子串个字符起子串T首次出现的首次出现的 位置。位置。8.8.求子串位置操作求子串位置操作 StrInsert(&S, pos, T)初始条件：串初始条件：串S、T已存在，已存在，1posStrLen

10、gth(S)+1.操作结果：在操作结果：在S的第的第pos个字符前插入串个字符前插入串T。9.9.串插入操作串插入操作9三、串的基本操作三、串的基本操作 StrDelete(&S, pos, len)初始条件：串初始条件：串S已存在，已存在，1posStrLength(S)-len+1.操作结果：删除操作结果：删除S中从第中从第pos个字符起长度为个字符起长度为len的子串的子串.10.10.串删除操作串删除操作 应当注意，在不同的高级语言中，对串操作的定义可能应当注意，在不同的高级语言中，对串操作的定义可能有差异。有差异。 10四、串的基本操作举例四、串的基本操作举例 例一、例一、若

11、执行以下程序，会输出怎样的结果若执行以下程序，会输出怎样的结果？ void main()StrAssign(S1,This); StrAssign(S2,is); Concat(S,S1,S2);x=Index(S,S2,2); printf(x); SubString(W,S,2,3); StrDelete(S,3,2);StrInsert(S,2,S2);printf(S);/S1=This/S2=is/S=Thisis/x=3/W=his/S=This/S=Tishis114.2 串的表示和实现串的表示和实现串的存储表示分为两大类共串的存储表示分为两大类共3 3种：种：一、定长顺序存储表

12、示一、定长顺序存储表示定长顺序存储表示就是用固定长度的数组来存储每一个串。其中，第定长顺序存储表示就是用固定长度的数组来存储每一个串。其中，第0分量用来存放串的长度，从第分量用来存放串的长度，从第1分量起依次存放串值的字符序列。分量起依次存放串值的字符序列。 顺序存储表示顺序存储表示链式存储表示：链式存储表示： 块链存储表示块链存储表示定长顺序存储表示定长顺序存储表示 堆分配存储表示堆分配存储表示 0123456串长度串长度串值区域串值区域12一、定长顺序存储表示一、定长顺序存储表示例如，对于例如，对于s1=USAs1=USA和和s2=I am a student.s2=I am a stud

13、ent., ,会用相同长度的会用相同长度的数组来存放。数组来存放。 01234563U SA012345615Iamastudent.T1T2 教材中规定，每个数组的长度为教材中规定，每个数组的长度为MAXSTRLEN+1，其中，其中，#define MAXSTRLEN255于是，数组最后分量的下标为于是，数组最后分量的下标为MAXSTRLEN。 另外，为便于定义长度为另外，为便于定义长度为MAXSTRLEN+1的数组，还用的数组，还用typedef unsigned char SStringMAXSTRLEN+1;定义了新的数据类型定义了新的数据类型SString。MAXSTRLENMAXS

14、TRLEN 这样一来，我们可以定义这样一来，我们可以定义 SString T1，T2；来分别存放来分别存放s1、s2。 13一、定长顺序存储表示一、定长顺序存储表示 再来看一个例子，对于再来看一个例子，对于s3如何用定长顺序存储方法来表示呢？如何用定长顺序存储方法来表示呢？s3=88888888888888888 8888888888888 由此可以看出，如果用由此可以看出，如果用SString类型的变量来表示一个长度超过类型的变量来表示一个长度超过MAXSTRLEN的串，则串值的超出部分将被截断舍去。因此，定长顺序的串，则串值的超出部分将被截断舍去。因此，定长顺序存储表示只能正确地存储长度在

15、存储表示只能正确地存储长度在0MAXSTRLEN之间的串。之间的串。 总之，定长顺序存储表示适用于所有的串长度均小于某一定数的应总之，定长顺序存储表示适用于所有的串长度均小于某一定数的应用场合。用场合。 当然，可以定义当然，可以定义SString T3；来存放来存放s3。当用。当用T3存放存放s3时，会出现什么情况呢？时，会出现什么情况呢？10000个个0123456T3MAXSTRLEN 由于由于s3的长度超过了的长度超过了T3的容量，串值的超出部分将被截断舍去。的容量，串值的超出部分将被截断舍去。8888888888888 88825514一、定长顺序存储表示一、定长顺序存储表示 下面基于

16、定长顺序存储表示，来讨论串的基本操作的实现算法。先下面基于定长顺序存储表示，来讨论串的基本操作的实现算法。先来了解一下来了解一下 am.m+k=bn.n+k; 的含义。的含义。 1.1.串连接操作串连接操作- Concat(SString &T, SString S1, SString S2) 其功能是用其功能是用T返回由返回由S1和和S2连接而成的新串。连接而成的新串。 具体地说就是，假设具体地说就是，假设这是这是S1、S2、T，01l 1l 1buS1MAXSTRLEN01l 2l 2CWS2MAXSTRLEN01TMAXSTRLENbuCW串连接操作就是先把串连接操作就是先把S1

17、的串值复制到的串值复制到T中，接着再把中，接着再把S2的串值复制到的串值复制到T中，中，并设置结果串的长度并设置结果串的长度T0。 但是，由于可能出现截断现象，所以我们分三种情况来讨论。但是，由于可能出现截断现象，所以我们分三种情况来讨论。15串连接操作的实现算法串连接操作的实现算法 S10=MAXSTRLEN01buS1MAXSTRLEN01l 2l 2CWS2MAXSTRLEN01TMAXSTRLENbuS1直接复制，直接复制，S2全部舍去。全部舍去。该过程用语句表示如下：该过程用语句表示如下：T1S10=S11S10;T0=S10; l 1l 116串连接操作的实现算法串连接操作的实现算

18、法 S10 MAXSTRLEN01l 1l 1buS1MAXSTRLEN01l 2l 2CVXWS2MAXSTRLEN01TMAXSTRLENS1直接复制，直接复制，S2的超出部分截断舍去。的超出部分截断舍去。用语句表示如下：用语句表示如下：T1S10=S11S10;TS10+1MAXSTRLEN=S21MAXSTRLEN-S10; T0=MAXSTRLEN; buCVl 1l 117串连接操作的实现算法串连接操作的实现算法 S10+S20 MAXSTRLEN) T1S10=S11S10; TS10+1MAXSTRLEN=S21MAXSTRLEN-S10; T0=MAXSTRLEN; else

19、 T1S10=S11S10; TS10+1S10+S20=S21S20; T0=S10+S20; /Concat19一、定长顺序存储表示一、定长顺序存储表示 从串连接操作的分析不难想象，在进行插入子串等操作时，也有可从串连接操作的分析不难想象，在进行插入子串等操作时，也有可能出现截断舍去现象，因此在使用定长顺序存储表示时要特别注意这一能出现截断舍去现象，因此在使用定长顺序存储表示时要特别注意这一点点. 定长顺序存储表示之所以会出现截断现象，是因为它预先限定了串定长顺序存储表示之所以会出现截断现象，是因为它预先限定了串的最大长度。要想克服这种弊病，就不应该为串长度设置上限，应该按的最大长度。要想

20、克服这种弊病，就不应该为串长度设置上限，应该按需为串值分配空间。我们要介绍的堆分配存储表示就是这样做的。需为串值分配空间。我们要介绍的堆分配存储表示就是这样做的。二、堆分配存储表示二、堆分配存储表示 堆分配存储表示也是用一组地址连续的存储单元来依次存放串值的堆分配存储表示也是用一组地址连续的存储单元来依次存放串值的字符序列。但是，这些存储单元是在程序执行过程中，根据串的长度动字符序列。但是，这些存储单元是在程序执行过程中，根据串的长度动态分配的。态分配的。 这种存储表示的类型定义如下：这种存储表示的类型定义如下：typedef structchar *ch;/串值的基地址串值的基地址int l

21、ength;/串的长度串的长度HString;如果定义如果定义 HString S；则则S有两个成员有两个成员ch、length。20二、堆分配存储表示二、堆分配存储表示 我们知道，在定长顺序存储表示中，当用我们知道，在定长顺序存储表示中，当用 SString T; 定义变量定义变量T的时候，系统已经分配好了存储串值的存储区域。的时候，系统已经分配好了存储串值的存储区域。 但是，当用但是，当用 HString S; 定义变量定义变量S的时候，系统并没有分配存储串的时候，系统并没有分配存储串值的存储区域。值的存储区域。01TMAXSTRLEN 存储串值的存储区域是在程序执行存储串值的存储区域是在

22、程序执行过程中，根据当时需要，在确定了串的过程中，根据当时需要，在确定了串的长度即长度即 S.length 后，用语句后，用语句Slengthch10S.ch=(char*)malloc(S.length*sizeof(char);为为S分配的，并且串值的字符序列从分配的，并且串值的字符序列从第第0分量分量起存放。起存放。 另外，由于另外，由于malloc和和free函数管理的是函数管理的是C语言中称为语言中称为“堆堆”的存储区，的存储区，所以上述表示法被称为所以上述表示法被称为堆分配存储表示堆分配存储表示。 21二、堆分配存储表示二、堆分配存储表示 下面来看串连接操作下面来看串连接操作Con

23、cat(&T，S1，S2)在堆分配存储表示时如何在堆分配存储表示时如何实现。实现。 S2lengthchWe1x0S1lengthchQh1t0Tlengthch10确定确定T的长度，的长度，T.length=S1.length+S2.length; 依次复制依次复制S1、S2的串值至的串值至T中。中。QhtWex分配串值的存储区域。分配串值的存储区域。22串连接操作的实现算法串连接操作的实现算法Status Concat(HString &T，HString S1，HString S2) T.length=S1.length+S2.length; T.ch=(char*)ma

24、lloc(T.length*sizeof(char); if(!T.ch)return ERROR; T.ch0S1.length-1=S1.ch0S1.length-1; T.chS1.lengthT.length-1=S2.ch0S2.length-1; return OK; /Concat 由于用堆分配存储表示的串既有顺序存储结构处理方便的特点，又在由于用堆分配存储表示的串既有顺序存储结构处理方便的特点，又在操作中对串长无限制，因此，常在应用中用来表示串。操作中对串长无限制，因此，常在应用中用来表示串。 23串插入操作的实现算法串插入操作的实现算法Status StrInsert(HSt

25、ring &S，int pos，HString T) if(posS.length+1) return ERROR; if(T.length) if(!(S.ch=(char*)realloc(S.ch , (S.length+T.length)*sizeof(char) exit(OVERFLOW); for(i=S.length-1;i=pos-1;-i) S.chi+T.length=S.chi; S.chpos-1pos+T.length-2=T.ch0T.length-1; S.length+=T.length; return OK;24三、块链存储表示三、块链存储表示 与线

26、性表类似，我们也可以用单链表来表示串与线性表类似，我们也可以用单链表来表示串。例如，对于。例如，对于 S=CHINA可以表示为可以表示为实际已分配的字节数串值所占字节数存储密度 显然这种表示存在显然这种表示存在存储密度低、存储效率不高存储密度低、存储效率不高的问题。的问题。 为此，人们提出了改进方案：为此，人们提出了改进方案： 用一个结点表示多个字符。用一个结点表示多个字符。CHINA#head注意：链表的尾结点不一定被串值充满，通常用非字符集字符注意：链表的尾结点不一定被串值充满，通常用非字符集字符 # 填充。填充。CheadHINA 为了便于进行串连接等操作，设置串的尾指针和长度域。为了便

27、于进行串连接等操作，设置串的尾指针和长度域。 tail串的这种存储表示方法称为串的这种存储表示方法称为块链存储表示块链存储表示 。25三、块链存储表示三、块链存储表示 CHINA#headtail 块链存储表示的类型定义如下：块链存储表示的类型定义如下： #define CHUNKSIZE 80/块大小块大小typedef struct Chunkchar chCHUNKSIZE;struct Chunk *next;Chunk;typedef structChunk *head, *tail;/串的头、尾指针串的头、尾指针int length;/串长度串长度LString; 一般地说，由于块

28、链存储表示占用存储空间大，而且操作复杂，所以一般地说，由于块链存储表示占用存储空间大，而且操作复杂，所以常用另外两种存储表示来表示串。常用另外两种存储表示来表示串。 26串运算实例串运算实例 文本编辑程序用于源程序的输入和修改，公文书信、报刊文本编辑程序用于源程序的输入和修改，公文书信、报刊和书籍的编辑排版等。常用的文本编辑程序有和书籍的编辑排版等。常用的文本编辑程序有Word、WPS等。等。文本编辑的实质是修改字符数据的形式和格式，虽然各个文本文本编辑的实质是修改字符数据的形式和格式，虽然各个文本编辑程序的功能强弱不同，但基本操作是一样的，都包括串的编辑程序的功能强弱不同，但基本操作是一样的

29、，都包括串的查找、插入和删除等操作。查找、插入和删除等操作。 这一节我们来实现一个简单的文本编辑操作演示程序，包这一节我们来实现一个简单的文本编辑操作演示程序，包括字符串的部分基本运算：赋值、比较、连接、插入、删除和括字符串的部分基本运算：赋值、比较、连接、插入、删除和清除运算。字符串采用动态存储结构清除运算。字符串采用动态存储结构(即堆分配即堆分配)存储。存储。27#define NULL 0typedef struct char *ch; int len; HString;int StrAssign(HString *s,char *chars) int i=0,slen; if(s-ch

30、!=NULL) free(s-ch); while(charsi!=0) i+; slen=i; if(slen)28 s-ch=(char *)malloc(slen*sizeof(char); if(s-ch=NULL) return(0); for(i=0;ichi=charsi; else s-ch=NULL; s-len=slen; return(1);int StrCompare(HString s,HString t) int i; for(i=0;is.len&it.chi) return(1); else return(-1);StrCat(HString *s,HS

31、tring t) /*参见算法参见算法4.4*/StrInsert(HString *s, int pos, HString t) /*参见算法参见算法4.3*/StrDelete(HString *s, int pos,int len) int i; char *temp; if(poss-len-len) return(0); if(len)30 temp=(char*)malloc(s-len-len)*sizeof(char); if(temp=NULL) return(0); for(i=0;ichi; for(i=pos;ilen-len;i+) tempi=s-chi+len;

32、s-len-=len; free(s-ch); s-ch=temp; return(1); 31int ClearString(HString *s) if(s-ch) free(s-ch); s-ch=NULL; s-len=0; return(0);main() int inp,flag=1; char *s,*t; HString s1,s2;32 int pos,len,ret; printf(1-StrAssingn); printf(2-StrComparen); printf(3-StrCatn); printf(4-StrInsertn); printf(5-StrDelete

33、n); printf(6-ClearStringn); printf(7-Exit); printf(please input 1-7nn); while(flag) scanf(%d,&inp); switch(inp) case 1:33 scanf(%s,s); ret=StrAssign(&s1,s); if(ret!=0) printf(the string is:%sn,s1); else printf(errorn); break; case 2: printf(s=); scanf(%s,s); StrAssign(&s1,s); printf(t=); scanf(%s,t); StrAssign(&s2,t); r