《数据结构》课件第5章

第5章串5.1串的定义及基本操作5.2串的存储结构本章小结习题五实训5-1串的综合操作

【教学目标】本章主要介绍串的基本概念、串在计算机中的存储方法、串的基本运算及其在不同存储结构上的实现。通过对本章的学习，要求掌握串的基本概念和串的基本运算；了解串的静态存储结构和串的动态存储结构；掌握串的顺序存储中的连接、相等判断、取子串、插入、删除和简单的串的模式匹配等算法的实现。计算机上非数值处理的对象基本上是字符串数据。在较早的程序设计语言中，字符串仅作为输入和输出的常量出现。随着计算机应用的发展，在越来越多的程序设计语言中，字符串也可作为一种变量类型出现，并产生了一系列字符串的操作。在信息检索系统、文字编辑程序、自然语言翻译系统等应用中，都是以字符串数据作为处理对象的。字符串一般简称为串。5.1串的定义及基本操作串(String)是由零个或多个字符组成的有限序列。一般记为S = "a1a2…an"(n≥0)其中，S是串名，用单引号或双引号括起来的字符序列是串的值，ai(1≤i≤n)可以是字母、数字或其它字符。串中字符的数目n称为串的长度，长度为0的串称为空串。串中任意个连续的字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。通常把字符在序列中的序号称为该字符在串中的位置，子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。空串是任意串的子串，任意串是其自身的子串。例如，设A、B、C为三个串：A = "data"，B = "structure"，C = "data

structure"，则它们的长度分别是4、9、14，A和B都是C的子串，A在C中的位置是1，而B在C中的位置是6。当且仅当两个串的值相等时，称这两个串是相等的，即只有当两个串的长度相等，并且各个对应位置上的字符都相等时，才认为这两个串相等。空格作为字符集合中的一个元素，常常出现在串中。由一个或多个空格组成的串称为空格串。也就是说空格串中只有空格字符。为了清楚起见，用“

”表示空格字符。由于空格也是一个字符，因此它可以出现在其它字符串之间。计算串的长度时，这些空格符也要计算在内。如串S = "I

am

a

student."，该串的长度是15，而不是12。特别指出，空格串不是空串，空格串的长度不为零。串是一种特殊的线性表，它的特殊性在于：串中的每一个数据元素仅由一个字符组成。串值必须用一对单引号或双引号括起来，但引号本身不属于串。串的基本操作有下列九种。为了方便起见，在介绍这些操作的基本功能时，用大写字母表示串名，小写字母表示串中字符。

(1)赋值操作(=)。赋值号左边必须是串变量，右边可以是串变量、串常量或运算值是串值的表达式。例如S = "shang

hai"。

(2) EQUAL(S，T)。判断两串是否相等的函数。若S和T相等，则返回函数值“TRUE”或1，否则返回函数值“FALSE”或0。S和T可以是空串，也可以是非空串。

(3) STRLEN(S)。求串的长度的函数。函数值为串S中字符的个数。

(4) CONCAT(S,T1,T2)。联接操作。设S、T1、T2都是串变量，联接操作就是将串T1和串T2放入S中。S串中的前一段和串T1相等，S串中的后一段和串T2相等。如T1="a1a2…am"，T2="b1b2…bn"，则S="a1a2…amb1b2…bn"。由此定义可见CONCAT(S，T1，T2)与CONCAT(S，T2，T1)的结果不一样。联接操作还可推广至n个串变量。

(5) SUBSTR(S,i,j)。求子串函数。当1≤i≤STRLEN(S)且0≤j≤STRLEN(S)-i+1时，返回的函数值是S的一个子串，即从串S中第i个字符起，长度为j的字符序列；否则返回空值NULL。

(6) INDEX(S,T)。定位函数。若在主串S中存在和T相等的子串，则函数值返回在S中出现的第一个和T相等的子串在S中的位置，否则函数值为零。注意T不能是空串。

(7) REPLACE(S,T,V)。置换操作。操作结果是以串V替换所有在串S中出现的和串T相等的子串。例如，设S="bbabbabba"，T="ab"，V="c"，则REPLACE(S，T，V)的结果是S="bbcbcba"。如果上面的V="a"，则结果是S="bbababa"。

(8) INSERT(S,pos,T)。插入操作。当1≤pos≤STRLEN(S)+1时，在串S的第pos个字符之前插入串T。

(9) DELETE(S,pos,len)。删除操作。当1≤pos≤STRLEN(S)，且0≤len≤STRLEN(S)-pos + 1时，从串S中删去第pos字符起、长度为len的子串。上述(1)～(4)的串操作是构成串操作的最小操作子集。(6)～(9)及没有列出的串的其它操作可以利用已有的基本操作来实现。上述的九种操作频繁地用在串处理中，因此在很多引入串变量的高级语言中，都将上面的基本操作做为基本的内部函数或过程来提供。当然，基本操作种类和规定在各个语言中会有所不同。5.2串的存储结构对串的存储有两种处理方式：一种是将串定义成字符型数组，从串名可直接访问到串值，串的存储空间是在编译时分配的，程序运行过程中不能更改串空间的大小，这种方式称为串的静态存储；另一种方式是串的存储空间是在程序运行时动态分配的，称为串的动态存储。5.2.1串的静态存储串的静态存储采用顺序存储结构。串的顺序存储结构和顺序表一样，用一组地址连续的存储单元存储串的字符序列，构成串的顺序存储，简称为顺序串。由于一个字符只占1个字节，而大多数计算机的存储器地址采用的是字编址，一个字(即一个存储单元)占多个字节，因此，串的顺序存储结构方式又有两种：一种是紧凑格式，另一种是非紧凑格式。

(1)紧凑格式，即一个字节存储一个字符。这种存储方式可以在一个存储单元中存放多个字符，充分利用存储空间。但要分离某一部分字符时，操作就比较麻烦。通常系统在存储串值时自动在串值的最后添加一个特殊符号作为当前串值的结束标记，在C语言中用转义字符'\0'作为串的结束标记，也有的系统采用字符'@'或'#'作为结束标记。若一个存储单元由4个字节组成，则一个存储单元可存放4个字符，如图5.1所示，存放给定的串C="data

structure"只需4个存储单元。

(2)非紧凑格式，即每个存储单元仅存放一个字符。这种存储方式的空间利用率很低，但操作时不需要分离字符，因而程序处理字符的速度比较快。如图5.2所示，存放给定的串C="data

structure"则需要15个存储单元。图5.1串值的紧凑格式存储

图5.2串值的非紧凑格式存储顺序串的数据类型用C语言描述如下：

#defineMAXSIZE100typedefstruct{

charch[MAXSIZE];

intlen;}SeqString;串的静态存储有两个缺点：一是需要预先定义一个串的最大长度，这在程序运行前是很难估计的；二是限定了串的最大字符个数，使串的某些操作如置换、联接等受到很大限制。5.2.2串的动态存储在顺序串上进行插入、删除操作并不方便，需移动大量的字符。当操作出现串值序列的长度超过上界MAXSIZE时，只能用截尾法处理。若采用动态存储就可以克服这个弊病。串的动态存储有两种方式：一种是链式存储结构，另一种是堆存储结构。

1.串的链式存储结构和线性表的链式存储结构相类似，也可采用链表方式存储串值。每个结点有两个域：data域，存放字符；next域，存放链指针。由于串结构的特殊性——结构中的每个数据元素是一个字符，则用链表存储串值时，存在一个“结点大小”的问题，即每个结点可以存放一个字符，也可以存放多个字符。结点大小的选择直接影响着串处理的效率。串的链式存储结构对某些串操作，如联接操作等有一定方便之处，但总的来说，不如顺序存储结构灵活，它占用存储量大而且操作较复杂。图5.3是每个结点存放一个字符的串的单链表示意图，图5.4是每个结点存放4个字符的串的单链表示意图。一个结点存储多个字符的链式结构也称为块链结构。图5.3串的链式存储结构中每个结点存放1个字符图5.4串的链式存储结构中每个结点存放4个字符串的块链结构用C语言描述如下：typedefstructnode

{

charstr[4];/*每个结点存储4个字符*/

structnode*next;

}LinkString;

2.串的堆存储结构堆存储结构的特点是：仍以一组地址连续的存储单元存放串的字符序列，但其存储空间是在算法执行过程中动态分配得到的。在C语言中，由动态分配函数malloc()和动态回收函数free()来实现。利用函数malloc()为每一个新产生的串分配一块实际需要的存储空间，若分配成功，则返回一个指针，指向串的起始地址。串的堆存储结构用C语言描述如下：

typedefstruct{

char*ch;

intlen;}HString;由于堆存储结构的串既有顺序存储结构的特点，在操作中又没有串长的限制，显得很灵活，因此，在串处理的应用程序中常被选用。5.2.3串的基本操作的实现下面给出用C语言描述的部分串的基本操作所对应的算法。

1.在串的静态存储结构上实现求子串函数SUBSTR(S，i，j)此操作不会发生子串截断的情况。算法中，对给定的参数作合法性判断，当参数非法时，函数返回空串。SeqStringsubStr(SeqStrings,inti,intj)

/*返回s串中自第i个字符起长度为j的子串。*/

{

SeqStringsub;

intn;if(i<1||i>s.len||j<0||j>s.len-i+1)

sub.len=0;

else

{for(n=1;n<=j;n++)sub.ch[n]=s.ch[i+n-1];

sub.len=j;

}

returnsub;}

2.在串的堆存储结构上实现求子串函数SUBSTR(S，i，j)前面讨论了在串的静态存储结构上实现SUBSTR(S,i,j)函数的算法。下面是在串的堆存储结构上实现SUBSTR(S,i,j)函数的算法。此算法中，对给定的参数需作合法性判断，当参数非法时，函数返回空串。读者可和上面的算法作比较，进一步掌握串的两种存储结构。HStringsubStr_h(HStrings,inti,intj)/*返回s串中自第i个字符起长度为j的子串*/{HStringsub;intn;if(i<1||i>s.len||j<0||j>s.len-i+1){sub.ch=NULL;sub.len=0;}else{sub.ch=(char*)malloc(j*sizeof(char));

for(n=1;n<=j;n++)sub.ch[n]=s.ch[n+i-1];

sub.len=j;}returnsub;}

3.在串的静态存储结构上实现CONCAT(S，T1，T2)操作在操作时需考虑可能出现的三种情况：

(1)串T1和串T2的长度之和小于MAXSIZE，即两串联接得到的S串是串T1和串T2联接的正常结果，S串的长度等于串T1和串T2的长度之和。串T1的长度小于MAXSIZE，而串T1和串T2的长度之和大于MAXSIZE，则两串联接得到的S串是串T1和串T2的一个子串的联接，串T2的后面部分被截断，S串的长度等于MAXSIZE。串T1的长度等于MAXSIZE，则两串联接得到的S串实际上只是串T1的拷贝，串T2全部被截断，S串的长度等于MAXSIZE。用C语言实现的具体算法如下：SeqStringconcat(SeqStringt1,SeqStringt2)/*由串t1和串t2联接而成的新串存放在串s中，以返回值形式带回。若长度超过规定的长度，则截断*/{SeqStrings;inti,n=MAXSIZE-1;if(t1.len+t2.len<=n){

for(i=1;i<=t1.len;i++)s.ch[i]=t1.ch[i];for(i=1;i<=t2.len;i++)s.ch[i+t1.len]=t2.ch[i];s.len=t1.len+t2.len;

}elseif(t1.len<n){

for(i=1;i<=t1.len;i++)s.ch[i]=t1.ch[i];for(i=1;i+t1.len<=n;i++)s.ch[i+t1.len]=t2.ch[i];s.len=n;}else{

for(i=1;i<=n;i++)s.ch[i]=t1.ch[i];s.len=n;} returns;}

4.在串的堆存储结构上实现CONCAT(S，T1，T2)操作前面已讨论了在串的静态存储结构上实现CONCAT(S，T1，T2)操作的算法。下面给出的是在串的堆存储结构上实现CONCAT(S，T1，T2)操作的算法。和上面的算法作一比较，进一步掌握串的两种存储结构。HStringconcat_h(HStringt1,HStringt2)/*由串t1和串t2联接而成的新串存放在s中，以返回值形式带回*/{HStrings;inti;s.ch=(char*)malloc((t1.len+t2.len)*sizeof(char));for(i=1;i<=t1.len;i++)s.ch[i]=t1.ch[i];for(i=1;i<=t2.len;i++)s.ch[i+t1.len]=t2.ch[i];s.len=t1.len+t2.len; returns;}

5.在串的静态存储结构上实现子串的定位操作INDEX(S,T)子串的定位操作通常称做串的模式匹配(其中T称为模式)，是各种串处理系统中最重要的操作之一。下面的算法是利用判等、求子串等操作来实现定位函数INDEX(S，T)的。算法的思路是：在主串S中从i = l开始取一长度和串T长度相等的子串与串T进行比较，若相等，则函数返回i；否则i增加1，从i=2开始取一长度和串T长度相等的子串与串T进行比较，重复上述的过程，直至确定在串S中取不到和串T长度相等的子串为止，函数返回0。或在S中取到一个和串T相等的子串，函数返回i。操作过程见图5.5。图5.5定位函数INDEX(S，T)操作示意图从图中可以看出，i的取值范围是1到S.len-T.len+l。用C语言描述的算法具体实现如下：intindex(SeqStrings,SeqStringt)

{inti,n,m,flag;n=s.len;

m=t.len;flag=0;i=1;while(i<=n-m+1&&(!flag)){

if(equal(subStr(s,i,m),t))flag=1;elsei++;}if(flag)returni;elsereturn0;}如不调用其它的串操作函数，算法如下：

intindex_b(SeqStrings,SeqStringt){inti=1,j=1;while(i<=s.len&&j<=t.len)if(s.ch[i]==t.ch[j]){i++;j++;}else{

i=i-(j-1)+1;

/*i与j同步回退j-1，再前进1步*/j=1;}if(j>t.len)returni-t.len;elsereturn0;}本章小结串是一种数据类型受到限制的特殊线性表，它的数据对象是字符集合，每个元素都由一个字符组成，一系列相连的字符组成一个字符串。串虽然是线性表，但又有其自己的特点，不是作为单个字符进行讨论，而是作为一个整体(即字符串)进行讨论。串的存储结构有两种：一种是静态存储，另一种是动态存储。静态存储又分为紧凑格式和非紧凑格式两种方式，动态存储又分为链式存储结构和堆存储结构。静态存储结构的存储空间是在编译时分配的，其大小是固定不变的，而动态存储结构的存储空间是在程序运行时由malloc()函数动态分配的。串的基本运算有串联接、两串相等判断、取子串、插入子串、删除子串、子串定位等。习题五一、简答题

1.设S ="IAMASTUDENT"，

T ="GOOD"，

Q ="WORKER"。求：STRLEN(s)，STRLEN(t)，SUBSTR(s，8，7)，SUBSTR(t，2，1)，INDEX(s，"A")，INDEX(s，t)，REPLACT(s，"STUDENT"，q)。

2.已知下列字串：

A = "THIS"，f ="SAMPLE"，c ="GOOD"，d ="NE"，b ="

"，g ="IS"

S =CONCAT(a，CONCAT(CONCAT(b，SUBSTR(a，3，2))，SUBSTR(f，2，6)))

T =REPLACE(f，SUBSTR(f，3，5)，c)

U =CONCAT(SUBSTR(c，3，1)，d)

V =CONCAT(s，CONCAT(b，CONCAT(t，CONCAT(b，u))))问s，t，v，STRLEN(s)，INDEX(v,g)，INDEX(u,g)各是什么？

3.简述下列每对术语的区别：空串和空格串；串变量和串常量；主串和子串。

4.两个字符串相等的充要条件是什么？

5.设已知两个串为：

S1 = “bccadcabcadf”；

S2 = “abc”。试求两个串长度，并判断S2串是否是S1的子串。如果S2是S1的子串，指出S2在S1中的起始位置。

二、算法设计题编写算法，在顺序串上实现串的判等操作EQUAL(S，T)。设两个串分别为S =“Beijing”，T =“China”，调用函数EQUAL(S，T)判断后，如果S = T，则返回1，否则返回0。实训5-1串的综合操作【实训目的】

1.加深对串的存储结构的理解。

2.掌握在不同存储结构上串操作的实现。【实训内容】建立顺序串和堆串，分别在两种存储结构上实现求子串和串联接操作，并在顺序串上实现子串定位操作。【实训要求】

1.要求设计一个程序来完成上述功能，要求串从键盘动态输入。

2.分别用顺序串和堆串实现。【算法分析】在前文介绍的5个串操作函数基础上，再分别设计顺序串和堆串的生成函数，以循环方式从键盘接收字符并生成相应形式的串，同时分别设计两种串的输出函数。【程序清单】#include<stdio.h>#include<string.h>#include<stdlib.h>#defineMAXSIZE100typedefstruct{charch[MAXSIZE];intlen;}SeqString;typedefstruct{char*ch;intlen;}HString;/*以下5个函数此处只列出函数头，定义见前文，请读者自己添加*/SeqStringsubStr(SeqStrings,inti,intj);HStringsubStr_h(HStrings,inti,intj);SeqStringconcat(SeqStringt1,SeqStringt2);HStringconcat_h(HStringt1,HStringt2);intindex_b(SeqStrings,SeqStringt);SeqStringcreatSeqString() /*建立顺序串*/{SeqStrings;charch;inti;ch=getchar();i=1;while(ch!='\n'){

s.ch[i]=ch;/*串从s.ch的下标1开始存放*/i++;ch=getchar();}s.ch[i]='\0';s.len=i-1;returns;}HStringcreatHString() /*建立堆串*/{HStrings;charch;inti,n;printf("输入堆串最大长度:\n");scanf("%d",&n);printf("输入串,按回车键结束：\n");s.ch=(char*)malloc((n+1)*sizeof(char));ch=getchar();ch=getchar();i=1;while(ch!='\n'&&i<=n){s.ch[i]=ch; /*串从s.ch的下标1开始存放*/i++;ch=getchar();}s.ch[i]='\0';s.len=i-1;returns;}voidprintSeqS(SeqStrings)

/*输出顺序串*/{inti;for(i=1;i<=s.len;i++)printf("%c"