第四章 字符串

1、 第四章第四章 串串4.1 4.1 串类型的定义串类型的定义 4.2 4.2 串的表示和实现串的表示和实现4.3 4.3 应用举例应用举例教学目的：教学目的： （1）了解串的定义； （2）理解和领会串的存储方式； （3）掌握常用的串运算。教学重点：教学重点： （1）串的基本概念、基本运算； （2）串的两种存储方式。 （3）串的模式匹配算法。教学难点：教学难点： （1）串的模式匹配算法； （2）串的基本运算的综合应用学时安排：学时安排： 4学时（其中实验2学时） 串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。然而，串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以“

2、单个元素”作为操作对象，如：在线性表中查找某个元素、求取某个元素、在某个位置上插入一个元素和删除一个元素等；而在串的基本操作中，通常以“串的整体”作为操作对象，如：在串中查找某个子串、求取一个子串、在串的某个位置上插入一个子串以及删除一个子串等。4.1 4.1 串类型的定义串类型的定义 串串是字符串的简称。它是一种在数据元素的组成上具有一定约束条件的线性表，即要求组成线性表的所有数据元素都是字符，所以，人们经常又这样定义串：串是一个有穷字符序列。串一般记作： s= “a1a2.an” (n0) 其中，s是串的名称，用双引号（“”）括起来的字符序列是串的值；ai可以是字母、数字或其他字符；串中字

3、符的数目n被称作串的长度。 当n=0时，串中没有任何字符，其串的长度为0，通常被称为空串空串。 s1= “”s2= “ ” s1中没有字符，是一个空串；而s2中有两个空格字符，它的长度等于2，它是由空格字符组成的串，一般称此为空格串空格串。 子串、主串子串、主串：串中任意连续的字符组成的子序列被称为该串的子串。包含子串的串又被称为该子串的主串。例如，有下列四个串a，b，c，d： a= “Welcome to Beijing” b= “Welcome” c= “Bei” d= “welcome to” b，c，d都是a的子串。 子串的位置子串的位置：子串在主串中第一次出现的第一个字符的位置。 两

4、个串相等两个串相等：两个串的长度相等，并且各个对应的字符也都相同。 例如，有下列四个串a，b，c，d： a= “program” b= “Program” c= “pro” d= “program ”相等不等 对于串的基本操作集可以有不同的定义方法，读者在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准。在上述抽象数据类型定义的13种操作中：1、串赋值StrAssign2、串复制Strcopy3、串比较StrCompare4、求串长StrLength5、串联接Concat6、求子串SubString 这六种操作构成串类型的最小操作子集。即：这些操作不可能利用其他串操作来实现，反之，其

5、他串操作（除串清除ClearString和串销毁DestroyString外）可在这个最小操作子集上实现。int Index (String S, String T, int pos) if (pos 0) n = StrLength(S); m = StrLength(T); i = pos; while ( i = n-m+1) SubString (sub, S, i, m); if (StrCompare(sub,T) != 0) +i ; else return i ; / while / ifreturn 0; / Index例如，可利用判等、求串长和求子串等操作实现定位函数Ind

6、ex(S,T,pos)。 算法的基本思想为：在主串S中取从第i ( i的初值为pos)个字符起、长度和串T相等的子串和串T比较，若相等，则求得函数值为i，否则i值增1直至串S中不存在和串T相等的子串为止。4.2 4.2 串的表示和实现串的表示和实现 如果在程序设计语言中，串只是作为输入或输出的常量出现，则只需存储此串的串值，即字符序列即可。但在多数非数值处理的程序中，串也以变量的形式出现。串有3种机内表示方法。一、串的定长顺序存储表示一、串的定长顺序存储表示 #define MAXSTRLEN 255 / 用户可在255以内定义最大串长 typedef unsigned char SStrin

7、gMAXSTRLEN + 1; /同C语言,最后一个单元中存字符串结束符 串的实际长度可在这个予定义长度的范围内随意设定，超过予定义长度的串值则被舍去，称之为“截断” 。按这种串的表示方法实现的串的运算时，其基本操作为“字符序列的复制”。1、串的联接concat（&t，s1，s2）void concat(sstring &T,sstring S1,sstring S2) int i,n,m; n=strlen(S1);m=strlen(S2); if(n+m=255) strcpy(T,S1); for(i=0;im;i+) Tn+i=S2i; Tn+m=0; else if(n255) st

8、rcpy(T,S1); for(i=0;i0&i0&m=n-i+1) for(j=i-1;j0&pos=strlen(S) n=strlen(S);m=strlen(T);i=pos;while(i=n-m+1) substring(sub,S,i,m); if(strcmp(sub,T)=0)return i; i+;return 0; 二、串的堆分配存储表示二、串的堆分配存储表示 基本思想：“按需分配”。 当字符串有效内容的长度发生变化，原来的空间就会释放掉，同时重新开辟一个和新内容长度一样的字符数组来存储新的字符串。 typedef structchar *ch; / 若是非空串，则按串

9、长分配存储区，否 则ch为NULLint length; / 串长度HString; 通常，C语言中提供的串类型就是以这种存储方式实现的。系统利用函数malloc( )和free( )进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为“堆”。C语言中的串以一个空字符为结束符，串长是一个隐含值。1 1、插入、插入void StrInsert(hstring &S1,int i,hstring S2) int j,n; n=S1.length+S2.length; if(iS1.length+1) exit(-2); if(S2.length)S1.ch=(char

10、*)realloc(S1.ch,n*sizeof(char); if(!S1.ch) exit(-2); for(j=S1.length-1;j=i-1;j-) S1.chj+S2.length=S1.chj; for(j=0;jS2.length;j+) S1.chi-1+j=S2.chj;S1.length=S1.length+S2.length;2 2、复制、复制void concpy(hstring &S1,hstring S2) int i; /*if(S1.ch) free(S1.ch);*/ S1.ch=(char *)malloc(S2.length*sizeof(char);

11、 if(!S1.ch ) exit(-2); S1.length=S2.length; for(i=0;iS2.length;i+) S1.chi=S2.chi; 3 3、字符串比较、字符串比较int concmp(hstring S1,hstring S2)int i;for(i=0;iS1.length&iS2.length;i+) if(S1.chi!=S2.chi) return S1.chi-S2.chi;return S1.length-S2.length;4 4、连接、连接void concat(hstring &T,hstring S1,hstring S2) int i; i

12、f(T.ch) free(T.ch); T.ch=(char *)malloc(S1.length+S2.length)*sizeof(char); T.length=S1.length+S2.length; for(i=0;iS1.length;i+) T.chi=S1.chi; for(i=0;i0&i0&m=S.length-i+1) if(sub.ch) free(sub.ch);sub.ch=(char *)malloc(m*sizeof(char);sub.length=m;for(j=i-1;ji+m-1;j+) sub.chj-i+1=S.chj; 三、串的块链存储表示三、串的

13、块链存储表示 由于串结构中每个数据元素为一个字符，所以最直接的链式存储结构是每个结点的数据域存放一个字符。 优点是操作方便；不足之处是存储密度较低。所谓存储密度为：存储密度= 若要将多个字符存放在一个结点中，就可以缓解这个问题。串值所占的存储单元实际分配的存储单元string head 由于串中的字符个数不一定是每个结点存放字符个数的整倍数，所以，需要在最后一个结点的空缺位置上填充特殊的字符。 这种存储形式优点是存储密度高于结点大小为1 的存储形式；不足之处是做插入、删除字符的操作时，可能会引起结点之间字符的移动，算法实现起来比较复杂。s t r in g head上机实验作业：上机实验作业：已知一个由字母组成的长度为n的字符串，其存储结构为带头结点的单链表，头指针为L，结点的数据类型为：（1）设计一个删除函数void DeleteX(linklsi