数据结构C++语言描述第4章串

1、第4章 串主要知识点串的基本概念、抽象数据类型和C+语言的串函数串的存储结构顺序串类串的模式匹配算法4.1 串的基本概念、抽象数据类型和C+语言的串函数1、串的基本概念1)串(又称字符串)是由n(n0)个字符组成的有限序列。（它是数据元素为单个字符的特殊线性表。）记为： s =“s0,s1, ,sn-1” (n0 ) 串名 串值（用“ ”括起来）)串长 串中字符的个数（n0）。)空串 串中字符的个数为0 时称为空串 。)空白串由一个或多个空格符组成的串。)子串 串S中任意个连续的字符序列叫S的子串; S叫主 串。)子串位置子串的第一个字符在主串中的序号。)字符位置字符在串中的序号。)串相等 串

2、长度相等，且对应位置上字符相等。（即两个串中的字符序列一一对应相等。）问：空串和空白串有无区别？答：有区别。空串(Null String)是指长度为零的串；而空白串(Blank String),是指包含一个或多个空白字符 (空格键)的字符串.注：串与字符的区别“a” 串，长度为的串。（它不仅要存储字符a，还要存储该串的长度数据）a字符a。(只存储字符a) 数据集合：串的数据集合可以表示为字符序列 s0,s1, ,sn-1，每个数据元素的数据类型为字符类型。操作集合：(1)初始化串Initiate(S)(2)赋值 Assign(S,T)(3)求串长度Length(S) (4)比较 Compare

3、(S,T) (5)插入 Insert(S,pos,T)(6)删除 Delete(S,pos,len)(7)取子串 SubString(S,pos,len) (8)查找子串Search(S,start,T)(9)替换子串Replace(S,start,T,V)2、串的抽象数据类型3、C+语言的串函数串长度：int strlen(char *str);串比较：int strcmp(char *str1,char *str2); 串拷贝：char * strcpy(char *str1,char *str2);串连接：char * strcat(char *str1,char *str2); 子串T

4、定位：char *strchr(char *str,char ch); 子串查找: char *strstr(char *s1,char *s2); 注：用C+处理字符串时，要调用标准库函数 #include 例:名和姓的对换问题。英国和美国人的姓名是名在前姓在后，但在有些情况下，需要把姓名写成姓在前名在后中间加一个逗号的形式。编写一个程序实现把名在前姓在后的姓名表示法转换成姓在前名在后中间加一个逗号的姓名表示法。 算法思想：因为C+语言自动在串末尾添加结束标记0,所以实现方法是:首先把把原姓名串name的空格改写为0(注意此时0后边，即指针p+1指示的是原字符串name的姓部分；此时的nam

5、e表示的是原name的名部分)，再把原name的姓、逗号和名逐步添加到newName中，最后再恢复name为开始时的状态。设计函数如下：void ReverseName(char *name, char *newName)char *p;p = strchr(name, ); /p指在空格 位置*p = NULL; /把空格换为NULL，因此name的长度只包括名strcpy(newName, p+1); /p+1是name的姓，因此newName等于name的姓strcat(newName, ,); / newName等于姓加逗号strcat(newName, name); / newNam

6、e等于姓加逗号加名*p = ; /恢复name为开始时的状态4.2 串的存储结构1、串的顺序存储结构 串的顺序存储结构就是用一个字符类型的数组存放串的所有字符，此时，表示串的长度的方法有两种：一种方法是设置一个串的长度参数，此种方法的优点是便于在算法中用长度参数控制循环过程另一种方法是在串值的末尾添加结束标记，此种方法的优点是便于系统自动实现。 而由于不同的内存分配方式定义的数组决定了串的顺序存储结构也有两种：(1)静态数组结构：用静态内存分配方法定义的数组。由于此时数组元素的个数是在编译是确定的，在运行时是不可改变的，所以也称为定长数组结构。其类成员变量包括：char strmaxSize;

7、int size;(2)动态数组结构：用动态内存分配方法定义的数组。此时数组元素的个数是在用户申请动态数组空间时才确定的,因此，动态数组结构体定义中要增加一个指出动态数组个数的域。其类成员变量包括：char *str;int size;int maxSize;其中，str指向动态数组的首地址，maxSize表示动态数组的最大个数，size表示串的当前长度，必须满足size maxSize2、串的链式存储结构(1)单字符结点链struct SCharNodechar str;struct SCharNode *next;(2)块链 struct NCharNode char strNumber;

8、struct NCharNode *next;NCharNode;它分为单字符结点和块链两种。4.3 顺序串类1、顺序串类的定义class Stringprivate:char *str; /串int size; /当前长度int maxSize; /最大字符个数void GetNext(const String& t,int next) const;int KMPFind(const String& t,int start,int next) const;public:String(char *s= ); /构造函数1String(int max); /构造函数2String(const S

9、tring &s); /拷贝构造函数String(vod); /析构函数void Insert(int pos,char *t); /插入void Delete(int pos,int length);/删除String SubStr(int pos,int length); /取子串char& operator(int n); /操作符重载String& operator=(const String& s); /操作符=重载1String& operator=(char *s) /操作符=重载2/操作符重载，定义为友元函数friend ostream& operator重载，定义为友元函数f

10、riend istream& operator(istream& istr,String& s); int operator=(const String& s)const; /操作符=重载1int operator=(char *s)const; /操作符=重载2 /操作符=重载3，定义为友元函数friend int operator=(char *strL,const String& strR);/Brute-Force算法的查找int FindSubstr(const String& t,int start)const;/KMP算法的查找int FindSubstr(const Strin

11、g& t,int start,int m)const;2、构造函数和析构函数String:String(char *s) /构造函数1,定义对象并赋初始串值 size = strlen(s);maxSize = size+1;str = new charmaxSize;strcpy(str, s); /C+的串拷贝函数调用String:String(int max) /构造函数2，定义对象并置最大字符个数 maxSize=max;size=0;str=new charmaxSize;String:String(const String &s) /拷贝构造函数,定义对象并拷贝赋值maxSize=

12、s.maxSize;size = s.size;str = new charmaxSize;for(int i = 0; i size)cout=maxSize-1)char *p=str;3、插入、删除和取子串成员函数 str=new charsize+length+1; /重新申请更大的内存空间 for(i=0;i=pos;i-)stri+length=stri;/从pos至pos+length逐位插入字符for(i=0;isize-1) return;if(lengthcharsLeft) length=charsLeft;/从pos至size逐位左移于删除长度为length的子字符串f

13、or(int i=pos;i= size-1) return temp; /返回空串if(length charsLeft) length = charsLeft;delete temp.str;temp.str = new charlength+1; /重新申请内存空间/保存取出的子字符串for(int i=0;ilength;i+) tempi=strpos+i;templength = NULL; /置结束标记符temp.size = length;return temp; /返回临时对象temp的值 4、常用操作符重载操作符重载既可以方便用户使用串，也方便顺序串类的调试char& St

14、ring:operator(int i) /数组元素操作符重载return stri;String& String:operator=(const String& s) /赋值操作符=重载1if(maxSizes.maxSize)delete str;str=new chars.maxSize;size=s.size;maxSize=s.maxSize;for(int i=0;i=size;i+)stri=s.stri;return *this;String& String:operator=(char *s) /赋值操作符=重载2int length=strlen(s);if(maxSize

15、length+1)delete str;str=new charlength+1;maxSize=length+1;size=length;strcpy(str,s);return *this;ostream& operator (ostream& ostr, const String& s)/输出流操作符重载couts.size=s.sizeendl;couts.maxSize=s.maxSizeendl;couts.str=s.str (istream& ostr, const String& s)/输入流操作符重载delete s.str;couts.size;s.maxSize=s.s

16、ize+1;s.str=new chars.maxSize;cout输入字符串:;for(int i=0;is.stri;s.strs.size=NULL;return istr;5、逻辑操作符重载逻辑等于操作符重载的设计代码如下，若逻辑等于则返回1，否则返回0int String:operator= (const String& s)const /逻辑等于操作符重载1/ String串类和String串类return (strcmp(str, s.str) = 0);int String:operator= (char *s)const /逻辑等于操作符重载2 / String串类和C+字符

17、串return (strcmp(str, s) = 0); int operator= (char *strL, const String& strR) /逻辑等于操作符重载3 /C+字符串和String串类return (strcmp(strL, strR.str) = 0); 6、顺序串类的测试#include #include #include #include String.h /包含顺序表类void main(void)String str1(Data Structure),str2(Learning); /用构造函数1String str3; /用构造函数1，取默认值String

18、str4(20); /用构造函数2String str5(str1); /用拷贝构造函数char str=Data Structure;cout拷贝构造函数测试:endlstr5;str2.Insert(9,st);cout插入测试:endlstr2;str2.Delete(0,9);cout删除测试:endlstr2;str3=str1.SubStr(5,9);cout取子串和对象赋值测试:endlstr3;str4=st;cout字符串赋值测试:endlstr4;cout输入流重载测试:str3;coutstr3;cout逻辑等于测试1:;if(str1=str5)coutString=S

19、tringendl;String str6(Structure);cout逻辑等于测试2:;if(str6=Structure) coutString=C+ stringendl;cout逻辑等于测试3:;if(Structure=str6) coutC+ string=Stringendl;4.3 串的模式匹配算法 串的查找操作也称做串的模式匹配操作，其中Brute-Force算法和KMP算法是两种最经常使用的顺序存储结构下的串的模式匹配算法。1、 Brute-Force算法(1)Brute-Force算法的设计思想： 将主串S的第一个字符和模式T的第1个字符比较， 若相等，继续逐个比较后续

20、字符； 若不等，从主串S的下一字符起，重新与T第一个字符比较。 直到主串S的一个连续子串字符序列与模式T相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。 否则，匹配失败，返回值 1。(2) Brute-Force算法的实现 int String:Find Substr(const String& t, int start)constint i = start, j = 0, v;while(i size & j = t.size-1) v = i-t.size+1;else v = -1;return v; (3)BF算法的时间复杂度若n为主串长度，m为子串长度，则串的BF匹配

21、算法最坏的情况下需要比较字符的总次数为(n-m+1)*mO(n*m)最好的情况是：一配就中！主串的前m个字符刚好等于模式串的 m个字符，只比较了m次，时间复杂度为O(m)。最恶劣情况是：模式串的前m-1个字符序列与主串的相应字符序列比较总是相等，但模式串的第m个字符和主串的相应字符比较总是不等，此时模式串的m个字符序列必须和主串的相应字符序列块一共比较n-m+1，所以总次数为:m*(n-m+1),因此其时间复杂度为O(nm)。2、KMP算法 KMP算法是在BruteForce算法的基础上的模式匹配的改进算法。KMP算法的特点主要是消除了Brute-Force算法的如下缺点： 主串下标i在若干个

22、字符序列比较相等后，只要有一个字符比较不相等便需要把下标i的值回退。分两种情况分析Brute-Force算法的匹配过程：第一种情况是模式串中无真子串， 如下图的主串s=“cddcdc”、模式串t=“cdc”的模式匹配过程。当s0=t0，s1=t1，s2t2时，算法中取i=1,j=0，使主串下标i值回退，然后比较s1和t0。但是因t1t0，所以一定有s1t0，实际上接下来就可直接比较s2和t0。第一次匹配stcddcdccdci2j2失败第二次匹配stcddcdccdcij失败第三次匹配stcddcdccdci2j失败第四次匹配stcddcdccdci5j2成功第二种情况是模式串中有真子串。设主

23、串s=“abacabab”、模式串t=“abab”。 第一次匹配过程如下图所示。此时, 因t0t1，s1=t1，必有s1t0；又因t0=t2，s2=t2，必有s2=t2， 因此接下来可直接比较s3和t1。stabacababai3j3失败abb 总结以上两种情况可以发现，一旦si和tj比较不相等，主串的si（或si+1）可直接与模式串的tk（0kj）比较，k的确定与主串s并无关系，而只与模式串t本身的构成有关，即从模式串本身就可求出k的值。 一般情况下，设s=s0s1.sn-1，t=t0t1.tm-1，当sitj（0in,0jm）时，存在 si-jsi-j+1si-1 = t0t1tj-1“此

24、时若模式串中存在可相互重叠的真子串，满足 t0t1.tk-1 = tj-ktj-k+1tj-1 （0kj） 则说明模式串中的子串“t0t1tk-1”已和主串“si-ksi-k+1si-1”匹配。下一次可直接比较si和tk； 此时若模式串中不存在可相互重叠的真子串，则说明在模式串t0t1tj-1”中不存在任何以t0为首字符的字符串与“si-jsi-j+1si-1”中以si-1为末字符的字符串匹配，下一次可直接比较si和t0。 关于模式串中的真子串问题。我们把模式串中从第一个字符开始到任一个字符为止的模式串中的真子串定义为nextj函数，则nextj函数定义为next j -1 当j0时max k | 0kj 且t0 t1 tk-1=tj-k tj-k+1tj-1 0 其他情况 当模式串t中的tj与主串s的si比较不相等时，模式串t中需重新与主串s的si比较的字符下标为k，即下一次开始比较si和tk； 若模式串t中不存在如上所说的真子串，有nextj=0，则下一次开始比较si和t0；当j=0时令nextj=-1。KMP算法的思想: 设s为主串，t为模式串，设i为主串s当前比较字符的下标，