第四章数据结构-串.

第四章串本章主要介绍下列内容串类型的定义串的表示和实现串的模式匹配退出4.1串的类型定义4.1.1串的基本概念串是由零个或多个字符组成的有限序列。串值必须用一对单引号括起来。例如（1）string=‘string’(2)S=‘中南林业科技大学’（3）L=‘’(4)A=‘123456789’一般串可以写成如下形式：S=‘a1a2a3a4…….an’其中等号左边的称为串的名，等号右边用单引号括起来的字符序列称为串的值。一、基本概念串的长度：指字符串中包含的字符的个数。例如例如S=‘abcdef’,串S的长度为6。空串和空格串是有区别的，空串指串的长度为0的串。空格串指由一个或多个空格字符组成的串。串中任意个连续的字符组成的子序列称为该串的子串。同时包含子串的串称为主串。空串是任何串的子串。任意串都是本身的子串。在串中通常给字符以序号标记，按从左至右以阿拉伯数字‘1’开始依次递增标记，这些字符在序列中的序号称为该串在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中第一次出现的位置来表示。判断两个串是否相等，充要条件是当且仅当这两个串的值相等。从字符的定义来看，字符串属于成分类型为字符的线性表。因此，对线性表的一切运算都能够对字符串进行；从字符的表示来看，它是字符的紧密排列，是一个有机的整体，能够用它来描述事物的基本属性，如利用字符串描述职工的姓名、产品的名称、电话号码等。二、串的抽象数据类型串的抽象数据类型的定义包括数据对象、数据关系和基本操作的定义，其中数据对象为字符集。虽然串的逻辑结构和线性表的逻辑结构相似，是它们的基本操作有很大区别。对于线性表的基本操作大多以“单一元素”作为操作对象；而对串而言，通常以“串的整体”作为操作对象，例如在串的某个位置上进行插入或删除，操作对象是一个个子串。串的抽象数据类型定义如下：ADTSTRING{数据对象：D={ai|ai∈charset,i=1,2,3,4,n,n≧0}数据关系：R={ai-1,ai|ai-1,ai∈D,i=1,2,3,….,n}基本操作：1、串赋值：stringAssign(S1,S2)2、串连接：stringconcat(S1,S2)3、串比较：stringcompare(s1,s2)4、求串长：stringlength(s)5、取子串：substring(S,start,length)6、子串定位：stringIndex(S1,S2)7、插入子串：stringInsert(s1,start,s2)8、删除子串：stringDelte(S,start,length)上述前五种操作是最基本的，构成串类型的最小操作子集。其余的串操作一般可由这些基本操作组合而成。例如，定位函数strIndex(s1,s2,m)可由stringlength,取子串substring和串比较stringcompare等操作组合来实现。intstringIndex(strings1,strings2,intp){if(p0){m=stringlength(s1);n=stringlength(s2);i=p;while(im-n+1){k=substring(s1,i,n);if(strcompare(k,s2)!=0)++i;elsereturni;//返回串s2在串s1中的相对位置}}return0;//串s1中不存在与串s2相等的子串}例如置换函数stringreplace可由求串长stringlength、串赋值、串连接stringconcat、取子串substring和定位函数等组合来实现。算法的基本思想：（1）首先设一个临时串用于保存得到的新串（2）从串S的第一个字符起与串S1比较，当找到第一个相同的子串时，立刻把串S1在串S中的第一个位置前的子串与串S2联接并保存到临时串中；（3）然后又从串S置换后的剩余串重复做（2），直到串S不存在与串S1相同的子串时停止。statusstringreplace(strings,strings1,strings2){pos=1;k=stringindex(S,S1,pos);if(k!=0){stringAssign(temp,’ø’);//temp为置换后得到的新串n=stringlength(S1);m=stringlength(S);while(k!=0){stringassign(temp,stringconcat(temp,substring(S,1,k-1),S2))m=m-(k-1)-n;stringassign(S,substring(S,k+n,m));//串S为每次置换后的剩余串k=stringindex(S,S1,pos);}Stringassign(S,stringconcat(temp,S));}}4.2串的表示和实现串的存储结构与线性表的存储结构类似。在对串进行存储表示时，一方面考虑子串的访问效率，另一方面还要考虑子串的一些基本操作的便利。一、定长顺序存储表示1、存储表示用一组地址连续存储单元存储串值的字符序列。例如S=‘abcdefg’abcdefg0123456#definemaxstrlen256typedefcharsstring[maxstrlen];//0号单元存放中长sstrings;//S是一个容纳255个字符的顺序串串长有两种表示方法：（1）在串的尾部设置一个结束标志。（2）设置一个表示长度的域。typedefstruct{charch[maxstrlen];intlength;}sstring;2.串在定长顺序存储表示上基本操作的实现（1）取子串substring(sub,S,i,n)statussubstring(sstringsub,sstringS,inti,intn){if(i1||is[0]||n0||ns[0]-i+1)returnERROR;sub[1..n]=s[i..i+n-1];sub[0]=n;returnsub;}（2）串的联接stringconcat(S,S1,S2)其运算结果有三种情况：①S1[0]+S2[0]≦maxstrlen,串S的值正确；②S1[0]maxstrlen而S1[0]+S2[0]maxstrlen串S的值只包含串S2的一个子串；③S1[0]=maxstrlen,串S的值为串S1的值。算法如下：statusstringconcat(sstringS,sstringS1,sstringS2){if(S1[0]+S2[0])=maxstrlen){//未截断S[1..S1[0]]=S1[1..S1[0]];S[S1[0]+1..S1[0]+S2[0]]=S2[1..S2[0]];S[0]=S1[0]+S2[0];}elseif(S1[0]maxstrlen){//截断串S2一部分S[1..S1[0]]=S1[1..S1[0]];S[S1[0]+1..maxstrlen]=S2[1..maxstrlen-S1[0]];S[0]=maxstrlen;}else{//截断串S2S[0..maxstrlen]=S1[0..maxstrlen];}returnS;}(3)删除函数stringDelete(S,m,n)当1≦m≦stringlength(S)-n+1时，从串S中删除第m个字符起长度为n的子串。statusstringDelete(sstringS,intm,intn){if(m1||mstringlength(S)-n+1)returnERROR;for(k=m+n;kstringlength(S);k++)S[k-n]=S[k];S[0]=S[0]-n;returnS;}二、堆分配存储表示堆分配存储表示以一组地址连续的存储单元存放串值的字符序列，但它们的存储空间是在程序执行过程中动态分配而得。之所以称为堆分配存储是因为在C语言中，有一个称之为“堆”的自由存储区，并由C语言的动态分配函数malloc()和free()来管理函数malloc()有两大功能：一是为每个新产生的串分配一块实际串长所需的存储空间；二是返回一个指向起始地址的指针，作为串的基址。有两种方式：（1）typedefchar*string;(2)typedefstruct{char*ch;intlength;}hstring;例如串的联接statusstringconcat(hstringS,hstringS1,hstringS2){if(S.ch)free(S.ch);//释放旧空间if(!(S.ch=(char*)malloc((S1.length+S2.length)*sizeof(char))))exit(overflow);S.ch[0..S1.length-1]=S1[0..S1.length-1];S.length=S1.length+S2.length;S.ch[S1.length..S.length-1]=S2[0..S2.length-1];returnS;}三、串的链式存储表示我们仿照线性表的链式存储结构，采用单链表的方式来存储串值，串的这种链式存储结构简称为链串。在每个结点中可以存放一个字符或多个字符。abcefgh##^head结点大小为3的链串abcde^head结点大小为1的链串结点大小为1的存储结构：typedefstructnode{chardata;structnode*next;}lstring;结点大小为100个字符的存储结构：#definechlinksize100//可定义块的大小typedefstructchlink{charch[chlinksize];structchlink*next;}chlink;typedefstruct{chlink*head;*tail;//串的头和尾指针intcurlen;//串的当前长度}lstring;由于在一般情况下，对串进行操作时，只需从头向尾顺序扫描即可，则对串值不必建立双向链表。设尾指针的目的是为了便于进行联结操作，但应注意联结时需处理第一个串尾的无效字符。存储密度=串值所占的存储位实际分配的存储位4.3串的模式匹配算法假定给的两个串S1和S2，在串S1中找与S2相等的子串的过程称为串的模式匹配。其中串S1称为主串，串S2称为模式串。如果在串S1中找到等于S2的子串，则称匹配成功，否则称匹配失败。4.3.1串的模式匹配的古典算法一种简单直观的模式匹配算法最早由布鲁特-福斯提出的算法，简称BF算法。其算法如下：intstrindex_bf(sstrings1,sstrings2){i=1;j=1;while(i=s1[0]&&j=s2[0]){if(s1[i]==s2[j]){++i,++j;}//继续比较后面的字符else{i=i-j+2;j=1;}//指针后退重新开始比较}if(js2[0])returni-s2[0];elsereturn0;}例主串S1=‘ababcabcabaabcabc’模式串S2=‘abcabaa’第一趟匹配：ababcabcabaabcabcabci=3j=1第二趟匹配：ababcabcabaabcabcai=2j=3第三趟匹配：ababcabcabaabcabcabcabai=8j=6第四趟匹配：ababcabcabaabcabcai=4j=1第五趟匹配：ababcabcabaabcabcai=5j=1第六趟匹配：ababcabcabaabcabcabcabaai=13j=8此算法在最坏情况下的时间复杂度为O（m*n)例如：模式串为‘aaaa…ab’n个字符，n-1个a主串为‘aaaa….a’m个a,mn4.3.2串模式匹配的KMP算法这种改进算法是克努特、莫里斯和普拉特三人同时发现的，所以人们称之为KMP算法。它的改进之处在于匹配的过程中，出现字符比较不等时，指示主串的指针i不需回溯，而是利用已经得到的“部分匹配”的结果将模式串向右移动某一距离，然后继续进行比较。一、next函数和按next函数进行