《数据结构C语言版》----第04章

第4章串主要知识点串的基本概念和C语言的串函数串的存储结构动态数组实现的顺序串串的模式匹配算法——BF算法4.1串1、串的基本概念1)串(又称字符串)是由n(n≥0)个字符组成的有限序列。（它是数据元素为单个字符的特殊线性表。）记为：s=“s0,s1,……,sn-1”(n≥0)串名串值（用“”括起来）２)串长串中字符的个数（n≥0）。３)空串串中字符的个数为0时称为空串。４)空白串由一个或多个空格符组成的串。５)子串串S中任意个连续的字符序列叫S的子串;S叫主串。６)子串位置子串的第一个字符在主串中的序号。７)字符位置字符在串中的序号。８)串相等串长度相等，且对应位置上字符相等。（即两个串中的字符序列一一对应相等。）问：空串和空白串有无区别？答：有区别。空串(NullString)是指长度为零的串；而空白串(BlankString),是指包含一个或多个空白字符‘’(空格键)的字符串.注：串与字符的区别“a”串，长度为１的串。（它不仅要存储字符‘a’，还要存储该串的长度数据１）‘a’字符a。(只存储字符‘a’)数据集合：串的数据集合可以表示为字符序列s0,s1,……,sn-1，每个数据元素的数据类型为字符类型。操作集合：(1)初始化串Initiate(S)(2)赋值Assign(S,T)(3)求串长度Length(S)2、串的抽象数据类型(4)比较Compare(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)相同之处：都是线性结构不如之处：（1）线性表的数据元素类型为任意类型；而串的数据元素类型为字符类型（2）线性表的插入和删除操作都是只对一个实践元素；而串的插入和删除操作都是对一个子串进行的（3）串还有一些不同于线性表的其他操作因此，专门设计串为一个专门的数据结构。现有的所有高级程序设计语言，如C++，Java等，都提供了专门的串操作函数或串类。3、串和线性表的比较3、C语言的串函数串长度：intstrlen(char*str);串拷贝：char*strcpy(char*str1,char*str2);串比较：intstrcmp(char*str1,char*str2);字符定位：char*strchr(char*str,charch);子串查找:char*strstr(char*s1,char*s2);串连接：char*strcat(char*str1,char*str2);……注：用C语言处理字符串时，要调用标准库函数#includestring.h例:名和姓的对换问题。英国和美国人的姓名是名在前姓在后，但在有些情况下，需要把姓名写成姓在前名在后中间加一个逗号的形式。编写一个程序实现把名在前姓在后的姓名表示法转换成姓在前名在后中间加一个逗号的姓名表示法。算法思想：因为C语言自动在串末尾添加结束标记‘\0‘,所以实现方法是:首先把把原姓名串name的空格改写为‘\0‘(注意此时‘\0‘后边，即指针p+1指示的是原字符串name的姓部分；此时的name表示的是原name的名部分)，再把原name的姓、逗号和名逐步添加到newName中，最后再恢复name为开始时的状态。设计函数如下：voidReverseName(char*name,char*newName){char*p;p=strchr(name,'');//p指在空格''位置*p=NULL;//把空格换为NULL，因此name的长度只包括名strcpy(newName,p+1);//newName等于name的姓strcat(newName,,);//newName等于姓加逗号strcat(newName,name);//newName等于姓加逗号加名*p='';//恢复name为开始时的状态}4.2串的存储结构1、串的顺序存储结构串的顺序存储结构就是用一个字符类型的数组存放串的所有字符，此时，表示串的长度的方法有两种：一种方法是设置一个串的长度参数，此种方法的优点是便于在算法中用长度参数控制循环过程另一种方法是在串值的末尾添加结束标记，此种方法的优点是便于系统自动实现。(1)静态数组结构：用静态内存分配方法定义的数组。由于此时数组元素的个数是在编译是确定的，在运行时是不可改变的，所以也称为定长数组结构。其类成员变量包括：typedefstruct{charstr[MaxSize];intlength;}String;而由于不同的内存分配方式定义的数组决定了串的顺序存储结构也有两种：(2)动态数组结构：用动态内存分配方法定义的数组。此时数组元素的个数是在用户申请动态数组空间时才确定的,因此，动态数组结构体定义中要增加一个指出动态数组个数的域。typedefstruct{char*str;intmaxLength;intlength;}DString;其中，str指向动态数组的首地址，maxLength表示动态数组的最大个数，length表示串的当前长度，必须满足length≤maxLength2、串的链式存储结构(1)单字符结点链typedefstructNode{charstr;structNode*next;}SCharNode;它分为单字符结点和块链两种。(2)块链typedefstructNode{charstr[Number];structNode*next;}NCharNode;结论：实际应用中仅动态数组方法应用较多，其他方法基本不用讨论：为什么？4.3串操作的实现串的动态数组结构体定义为：typedefstruct{char*str;intmaxLength;intlength;}DString;（1）初始化操作voidInitiate(DString*S,intmax,char*string){inti,m;S-length=strlen(string);if(S-lengthmax)m=S-length;elsem=max;S-maxLength=m;S-str=(char*)malloc(sizeof(char)*m);for(i=0;iS-length;i++)S-str[i]=string[i];}方法二：typedefstruct{char*str;intlength;}DString;voidInitiate(DString*S,char*string){inti;S-length=strlen(string);S-str=(char*)malloc(sizeof(char)*S-length);for(i=0;iS-length;i++)S-str[i]=string[i];}（2）插入子串操作intInsert(DString*S,intpos,DStringT){inti;char*p;if(pos0){printf(参数pos出错！);return0;}else{if(S-length+T.lengthS-maxLength)p=(char*)realloc(S-str,(S-length+T.length)*sizeof(char));for(i=S-length-1;i=pos;i--)S-str[i+T.length]=S-str[i];for(i=0;iT.length;i++)S-str[pos+i]=T.str[i];S-length=S-length+T.length;return1;}}（3）删除子串操作intDelete(DString*S,intpos,intlen){inti;if(S-length=0){printf(数组中未存放字符无元素可删!\n);return0;}elseif(pos0||len0||pos+lenS-length){printf(“参数pos和len不合法”);return0;}else{for(i=pos+len;i=S-length-1;i++)S-str[i-len]=S-str[i];S-length=S-length-len;return1;}}（4）取子串操作intSubString(DString*S,intpos,intlen,DString*T){inti;if(pos0||len0||pos+lenS-length){printf(参数pos和len出错！);return0;}else{for(i=0;ilen;i++)T-str[i]=S-str[pos+i];T-length=len;return1;}}（5）撤消操作voidDestroy(DString*S){free(S-str);S-maxLength=0;S-length=0;}例4-3编写一个程序测试上述动态数组存储结构下串操作函数的正确性。#includestdio.h#includemalloc.h#includestring.h#includeDString.hvoidmain(void){DStringmyString1,myString2,myString3;inti,max1=1,max2=1,max3=1;/*测试初始化函数*/Initiate(&myString1,max1,Data);Initiate(&myString2,max2,Structure);Initiate(&myString3,max3,);/*测试插入函数*/Insert(&myString2,0,myString1);for(i=0;imyString2.length;i++)printf(%c,myString2.str[i]);printf(\n);/*测试删除函数*/Delete(&myString2,0,5);for(i=0;imyString2.length;i++)printf(%c,myString2.str[i]);printf(\n);Destroy(&myString1);Destroy(&myString2);Destroy(&myString3);}程序运行输出为：DataStructureStructure注意：（1）max1、max2、max3都很小，但程序初始化时能根据当前需要的字符串长度申请空间（2）插入子串时，原先长度不够，程序可以根据实际需要的字符个数重新申请内存空间4.3串的模式匹配算法串的查找操作也称做串的模式匹配操作，其中Brute-Force算法和KMP算法是两种最经常使用的顺序存储结构下的串的模式匹配算法。(1)Brute-Force算法的设计思想：将主串S的第一个字符和模式T的第1个字符比较，若相等，继续逐个比较后续字符；若不等，从主串S的下一字符起，重新与T第一个字符比较。直到主串S的一个连续子串字符序列与模式T相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。否则，匹配失败，返回值–1。1、Brute-Force算法(2)Brute-Force算法的实现intBFIndex(DStringS,intstart,DStringT){inti=start,j=0,v;while(iS.length&&jT.length){if(S.str[i]==T.str[j]){i++;j++;}else{i=i-j+1;j=0;}}if(j==T.length)v=i-T.length;elsev=-1;returnv;}(3)BF算法的时间复杂度若n为主串长度，m为子串长度，则串的BF匹配算法最坏的情况下需要比较字符的总次数为(n-m+1)*m＝O(n*m)最好的情况是：一配就中！主串的前m个字符刚好等于模式串的m个字符，只比较了m次，时间复杂度为O(m)。