数据结构与算法第三章

1、第3章，字符串，3.1字符串抽象数据类型，3.2字符串存储结构和类定义，3.3字符串运算算法实现，3.4字符串模式匹配，3.1字符串抽象数据类型，3.1.1基本概念，3.1.2字符串抽象数据类型，3.1.1基本概念，字符串:它由0个或0个以上按顺序排列的字符组成。空字符串:不包含任何字符内容的零长度字符串。3.1.1.1字符串常量和变量，例如，n个字符串变量，3.1.1.2字符，char:字符串的基本单位。在C和C语言中，128个符号(字符集)用ASCII码在一个字节(8位)中编码，字符的编码序列是3.1.1.3。为了便于字符串之间的比较和计算，字符编码表通常遵循习惯的“部分序列编码规则”。字

2、符偏序:根据字符的自然含义，有些字符可以每两个按顺序进行比较。事实上，在大多数情况下，字典排序的中文字符串有一些特殊情况，如“笔画”顺序、3.1.1.4 C标准字符串、标准字符串:使用C的函数库作为字符串数据类型的方案。例如:char SM字符串的结束标记:0 0是ASCII码中8位的全零，也称为空字符。3.1.1.4 C标准字符串(续)，1。字符串长度函数int strlen(char * s)；2.字符串副本char * str copy(char * S1，char * S2)；3串拼接字符*strcat(字符*s1，字符* S2)；比较4个字符串中的int strcmp(char *s

3、1，char * S2)；3.1.1.4 C标准字符串(续)，5个输入和输出函数，6个定位函数char * strcher (char * s，char C)；7右定位功能char * strrhr(char * s，char c)；3.1.2标准字符串(续)，3.1.2字符串抽象数据类型，类string:采用动态可变存储结构代替字符SM。String类/String类/其存储结构和实现方法使用c标准字符串(简称为标准字符串)。/为了区分，由类字符串创建的实例对象简称为这个字符串，或称实例字符串。/在程序开始时，#include和#include以及/和#include是必需的。和#inclu

4、de /1。字符串:/string s的数据表示通常是按顺序存储的，在数组s中，元素类型是char /string是可变长度的，使用可变大小来记录字符串/2的当前长度。使用变量访问字符串:/字符串变量可以参与操作。例如，S1S2的意思是两根弦首尾相连。/字符串存储在数组字符串中，stri可以在内部访问字符串的第个字符。/3 .字符串类的操作集:请参考以下成员函数，private: char * str/私有指针变量，用于指向存储向量strsize1int大小；/此字符串的当前实际长度是public : String(char * s=)；/创建空字符串字符串；/创建一个新字符串，并将标准字符串

5、复制为初始值字符串(常量字符串/拼接操作符，该字符串与标准字符串的字符串操作符拼接(字符串S2=s1.substr (2，3)；上述声明中涉及的存储形式如下页所示。3.2.2字符串类string的存储结构(续)，微软VC的CString类引入了自动动态存储管理，字符串的最大长度不超过2GB。容器类型不需要使用新建和删除。特征:该变量声明了集合s6(x，6)；/s6=xxxxxx市=费城；/字符串常量作为初始值赋值语句S1=S2=hitt here；变量比较if(s1=s2)方法调用s1。make upper()；内部字符比较if(s20=h)，3.3字符串运算的算法实现，1 .字符串长度函数i

6、nt strlen(char * s)；2.字符串副本char * str copy(char * S1，char * S2)；3串拼接字符*strcat(字符*s1，字符* S2)；比较4个字符串中的int strcmp(char *s1，char * S2)；3.3.1 C标准字符串运算，3.3.2字符串运算，3.3.1 C标准字符串运算，算法3-1字符串复制字符*字符串复制(字符*d，字符*s) /这个程序的问题是，如果字符串s比字符串d长，/。/可能导致d超出界限，int I=0；而(si！=0)di=si；I .di=0；返回d；实现3.3.1标准字符串操作(续)，算法3-2字符串比

7、较整数(字符*d，字符*s)整数I=0；而(si！=0，I；实现if(di=0，3.3.1 C标准字符串运算(续)，算法3-3求字符串长度整数(字符d)整数I=0；而(di！=0)I；返回I；3.3.1 C标准字符串操作的实现(续)，算法3- 4查找字符字符字符(字符* d，字符ch)/根据数组指针d按顺序查找字符ch，/如果找到ch，则返回指针位置，/如果没有找到ch，则返回0。I=0；/跳过那些不是ch而(di！=0，3.3.1 C标准字符串运算的实现(续)，算法3-5反向搜索字符char * strrh(char * d，char ch)/根据数组指针d，从其尾部反向搜索字符ch，/如果

8、找到ch，则返回指针位置，/如果没有找到ch，则返回0。I=0；/在(di！=0)I；/跳过那些不在循环中的字符(I=0，3.3.2，字符串操作的实现(续)，算法3-7，创建构造函数string :3360 string(char * s)/首先，确定新创建的字符串所需的实际存储空间，s的类/类型为(char确定/的长度，并使用标准字符串函数strlen计算长度大小=strlen。/然后，在动态存储区中打开一个空间，用于存储/初始值s，并包括结束字符串new char size1，/当打开空间不成功时，运行异常，退出断言！=0)；/使用标准字符串函数strcpy将s/完全复制到指针str所指向

9、的存储空间strcpy(str，s)中；复制构造函数，string:3360string(常量字符串，3.3.2string字符串操作实现(续)，算法3-8析构函数string :3360 string()/必须释放动态存储空间deletesr，3.3.2字符串操作的实现(续)，算法3-9拼接运算符字符串33603360运算符(字符串，/如果未成功打开动态存储空间，则退出断言(临时字符串！=0)；temp.size=len/字符串str(以0结尾)保存到temp strcpy(temp.str，str)；/然后将本例中的参数s和字符串拼接成一个长的strcat(temp.str，s . str

10、)；返回温度；3.3.2字符串操作的实现(续)，算法3-10赋值运算符常量字符串，/如果动态存储空间的创建失败，则正常操作断言(字符串！=0)；size=s.sizestrcpy(str，s . str)；/将此实例作为字符串类的实例返回* this、boolstring :运算符(string、friendistream或char temp1000istrtemp删除s.strs.size=strlen(温度)；s . str=new chars . size 1；assert(s.str！=0)；strcpy(s.str，temp)；返回istr，3.3.2字符串操作的实现(续)，算法3-

11、11提取子串函数StringString 33603360 substr(int index，int count)/取出一个子串并返回，从下标index开始，长度为int count I；/此字符串从下标索引开始到字符串结束从右开始计数，其长度为左整数左=大小索引；字符串温度。char * p *，q；/如果下标索引值太大，超过了该字符串的实际字符串长度，则返回空字符串if(index=size)返回temp，/如果计数超过从索引开始的实际子串长度，/如果(计数左)计数=左，则使计数变小；/释放原始存储空间删除临时字符串；/如果打开动态存储空间失败，则退出temp.str=新字符计数1；ass

12、ert(temp.str！=0)；/p的内容是一个指针，/指向当前没有内容的字符数组的第一个字符，p=临时字符串；/q是一个指针，/指向该实例字符串的字符串数组的下标索引字符Q=3 . 3 . 2字符串操作的实现(续)，算法3-12查找字符串中的字符int 33603360 Find(char c，int start)/查找该实例字符串中的字符c，如果找到了，/放它参数start就是下标。/从开始的下标开始搜索C。如果start为/0，则查找int i=从头开始。断言(I大小)；/循环跳过那些不是c while (stri！=0，char，3.4模式匹配目标对象s(字符串)，模式P(字符串)任

13、务：使用给定的模板P，在目标字符串s中搜索与模板P相同的子字符串，并在s中找到与P相同的第一个子字符串(缩写为“匹配字符串”)，然后，S= ABBCABCACBAB T= ABCAC ，简单模式匹配：例如，将模式与目标逐一比较(从第一个位置开始)，直到遇到不匹配的字符(模式向右移动一位，再次开始匹配)。该算法可以在第一次匹配或目标结束时停止。朴素模式匹配(蛮力)，3.4.1模式匹配的原始算法(续)_BF算法，算法3-13模式匹配的原始算法(I) #包括# include int find pat _ 1(字符串s，字符串p，int startindex)/从s的末尾开始的最后一个模板长度位置是int last index=s . strlen()-p . strlen/开始匹配位置的start index值太大，如果(最后一个索引start index)返回(-1)，则匹配不能成功；/g是s的光标，将其与模板p和s的g位置的子字符串进行比较，并继续循环(int g=startindexg=LastIndexg)如果(P=S.Substr(g，P.strlen()返回g；