数据结构串与文本编辑

会计学1数据结构串与文本编辑3.1串的类型定义1.串的相关术语串是由零个或多个字符组成的有限序列，记为：s=s1s2…sn。其中s是串名；双引号内的字符序列s1s2…sn是串值；n(n>=0)表示串的长度。2第1页/共71页3.1串的类型定义例如：s1=“datastructure”//串，长度为14串长度为零的串称为空串。例如：s=“”//空串，长度为0组成串的字符均为空格的串称为空格串或空白串。例如：s=“”//空格串，长度为43第2页/共71页3.1串的类型定义一个串中任意个连续字符组成的子序列称为该串的子串。空串是任何串的子串。例如：s1=“datastructure”s2=“data”//s2是s1的子串s3=“structure”//s3是s1的子串s4=“datastructure”//s4不是s1的子串包含子串的串称为主串。上例中s1为主串。4第3页/共71页3.1串的类型定义子串的序号是该子串的第一个字符在主串中的序号。在上例子串s2在s1中的序号为1，s3在s1中的序号为6。S4不是s1的子串，也可以说，s4在s1中的序号为0。当且仅当串的长度相等并且对应位置上的字符都相同时，称这两个字符串是相等的。例如：s1=“datastructure”s2=“datastructure”s3=“datastructure”//s1与s2相等，s3与s1和s2均不相等5第4页/共71页3.1串的类型定义按照串中字符的次序，逐一比较两个字符串中字符的大小，以确定两个串的大小关系的操作，称为串的比较。例如：s5=data，s6=DATA，则有s5>s6的比较结果为1，s5<s6的比较结果为0。6第5页/共71页3.1串的类型定义2.串的ADT定义在引入串的ADT定义前我们先来看一个字符串应用的例子。【例3-1】有一个字符串“liveonnoevil”，检查它是否为“回文”。当一个字符串顺读和逆读都一样，就可以称这个字符串是回文。7第6页/共71页3.1串的类型定义英文中的回文具有广义和狭义之分，广义的回文是指串中的空格字符不计入内，比如串“tenanimalsIslaminanet”去掉空格字符后是一个回文。狭义的回文是指将空格字符计入在内，比如题目中的“Liveonnoevil.”不过滤掉空格就是回文字符串。单个英文单词的回文符合狭义回文。例如：eye、mum、refer、level等。8第7页/共71页3.1串的类型定义判断一个字符串s是否为回文（狭义的），需要进行如下操作：（1）存储串s，并以相反顺序存储为串t；（2）比较s与t；（3）得出字符串s是否为回文串的判断；（4）输出回文串s例3-1是一个串的实际应用问题，为解决问题所需要的有关串的操作，即串类型应该提供的应用接口都是以串为单位，而不是串中的单个字符为单位。下面给出串的ADT定义：9第8页/共71页3.1串的类型定义ADTString{Data:D={ai｜aiElemSet,i=1,2,...,n,n>=0}Structure:S={<ai-1,ai>|ai-1,aiD,i=2,3,…,n}oPerations:ConstructString()//操作结果：创建一个空的串sDestructString()//操作条件：已有串s//操作结果：销毁当前串sStringLen()//操作条件：已有串s//操作结果：得到当前串s的实际长度10第9页/共71页3.1串的类型定义StringCpy(t)//操作条件：已有串s和参数串t//操作结果：将t复制到当前串s中OutputString()//操作条件：已有串s//操作结果：输出当前串sSubString(pos,len,&t)//操作条件：已有串s//操作结果：取串s中从第pos个字符开始的，长度为len的子串，由t返回DelSubString(pos,len,&t)//操作条件：已有串s和一个参数串t//操作结果：删除当前串从第pos个字符开始，长度为len的子串//并由t返回被删除的子串11第10页/共71页3.1串的类型定义InsertSubString(pos,t)//操作条件：已有串s和参数串t//操作结果：将t插入到当前串第pos个位置前ConnectString(t)//操作条件：已有串s和参数串t//操作结果：将t连接到当前串s之后ClearString()//操作条件：已有串s//操作结果：将当前串s清空ReplaceString(pos,len,t)//操作条件：已有串s和参数串t//操作结果：将当前串s中第pos个字符开始的长度为len的子串，替换为t}ADTString;12第11页/共71页3.2串的存储表示3.2.1串的顺序存储将串所占用空间的大小称为串容量，实际存在的元素个数称为串长，如图3-1所示。13第12页/共71页3.2串的存储表示为了表示串的结束，可在串内容最后一个有效字符后，再多开辟一个存储空间，存放结束标志’\0’（C/C++语言中的字符串就采用这种方法），如图3-2所示。14第13页/共71页3.2串的存储表示借助于顺序存储时数组的0号下标存储串长，即有效地利用了空间，又使得串中字符的位序与其存放位置（下标）一致，如图3-3所示。15第14页/共71页3.2串的存储表示定义顺序串：#defineMAX100classSqString{public:char*base;//存储串的字符数组//base[0]表示串的实际长度,不另设结束标志intmaxlen;//表示串的最大长度public:SqString();//构造函数①SqString(char*s);//构造函数②SqString(SqString&t);//构造函数③~SqString();//析构函数16第15页/共71页3.2串的存储表示boolInsertString(intpos,SqString&t);//在串的指定位置pos插入一个子串tboolDelSubString(intpos,intlen,SqString&t);//删除当前串的子串,并由t返回voidOutputString();//输出串中所有字符voidConnectString(SqString&t);//在当前串尾连接串tboolSubString(intpos,intlen,SqString&t);//求当前串从pos开始长度为len的子串intIndexof(SqString&t);//求模式串t在当前串中第一次出现的位置intIndexof_KMP(SqString&t);//KMP法求模式串t在当前串中第一次出现的位置voidGetNext(intnext[]);//KMP模式匹配算法辅助函数//其他操作};17第16页/共71页3.2串的存储表示顺序串的构造与析构串的构造有三种方法，分别是构造空串、由基本类型的字符串构造一个新串以及使用串对象来构造串。下面给出三种方法构造串的实现过程。（1）构造空的顺序串。【算法3-1-1】SqString::SqString(){maxlen=MAX;base=newchar[maxlen+1];//0下标留作记录长度base[0]=0;}18第17页/共71页3.2串的存储表示（2）由基本字符串构造一个新串。【算法3-1-2】SqString::SqString(char*s)//由机内标准串构造{maxlen=MAX;base=newchar[maxlen+1];base[0]=strlen(s);for(inti=0;s[i]!='\0';i++)base[i+1]=s[i];}19第18页/共71页3.2串的存储表示（3）使用串对象来构造串。【算法3-1-3】SqString::SqString(SqString&t){maxlen=t.maxlen;base=newchar[maxlen+1];base[0]=t.base[0];for(inti=1;i<=base[0];i++)base[i]=t.base[i];}20第19页/共71页3.2串的存储表示（4）析构函数【算法3-1-4】SqString::~SqString(){delete[]base;}21第20页/共71页3.2串的存储表示顺序串插入操作顺序串插入操作的功能是将一个指定的串插入到当前串中的指定位置之前，以s串和t串分别表示当前串和待插入串，则插入前后s串与t串的状态如图3-4（a）和图3-4（b）所示。22第21页/共71页3.2串的存储表示23第22页/共71页3.2串的存储表示顺序串插入操作实现算法为：①检查插入位置的合法性，即当插入位置pos<1或pos>base[0]，或base[0]+t.base[0]>maxlen（没有足够空间插入t）时，提示错误信息，终止程序；②从pos指向的位置开始，一直到最后的字符，每个字符都要向后移动，移动的长度为t串的长度；③插入t串，修改s的串长，操作成功，结束。24第23页/共71页3.2串的存储表示【算法3-2】boolSqString::InsertString(intpos,SqString&t){if(pos<1||pos>base[0]+1||pos-1+t.base[0]>maxlen){cout<<"插入失败"<<endl;returnfalse;}else{for(inti=base[0];i>=pos;i--)base[i+t.base[0]]=base[i];//元素后移25第24页/共71页3.2串的存储表示for(i=1;i<=t.base[0];i++)base[pos-1+i]=t.base[i];//插入元素base[0]+=t.base[0];returntrue;}}26第25页/共71页3.2串的存储表示顺序串删除操作顺序串删除操作的功能是删除s串中从第pos个位置开始的长度为len的子串。如图3-5所示。 27第26页/共71页3.2串的存储表示28第27页/共71页3.2串的存储表示顺序串删除操作实现算法为：①检查参数的合法性，有两种不合法的操作条件：一是pos的值不在串s的长度范围内，即pos<1或pos>base[0]；二是从串s第pos个位置开始不存在长度为len的子串，即pos+len-1>base[0]；②将待删除的子串复制给t；③在s中删除指定的子串，修改s的串长，操作成功，结束。29第28页/共71页3.2串的存储表示【算法3-3】boolSqString::DelSubString(intpos,intlen,SqString&t){if((pos<1)||(pos>base[0])||pos-1+len>base[0]){cout<<"删除失败"<<endl;returnfalse;}else{for(inti=pos;i<=pos-1+len;i++)//删除的元素复制给tt.base[i-pos+1]=base[i];t.base[0]=len;30第29页/共71页3.2串的存储表示for(i=pos+len;i<=base[0];i++)//元素前移{base[i-len]=base[i];}base[0]-=len;returntrue;}}31第30页/共71页3.2串的存储表示输出顺序串操作顺序串输出操作的功能是将串中的字符全部输出。顺序串输出操作实现算法为：①检查串时否为空串，若为空，输出空串信息；②若串非空，则利用循环输出串的内容；③操作成功，结束。32第31页/共71页3.2串的存储表示【算法3-4】voidSqString::OutputString(){if(base[0]==0)//判断串是否为空串cout<<"空串"<<endl;else{for(inti=1;i<=base[0];i++)cout<<base[i];cout<<endl;}}33第32页/共71页3.2串的存储表示串的连接串的连接，顾名思义，是指将两个已有的串连接成为一个串。例如，有两个串s和t都是类SqString的对象，那么两个串连接后为s=s+t，如图3-6所示。34第33页/共71页3.2串的存储表示顺序串连接操作实现算法为：①计算连接后的串长，如果超出顺序串的maxlen，重新分配空间；②否则，从当前串的第base[0]+1个位置起，依次将t串中每一个字符复制到s；③更新当前串长，操作成功，返回。35第34页/共71页3.2串的存储表示【算法3-5】voidSqString::ConnectString(SqString&t){if(base[0]+t.base[0]>maxlen){char*p=newchar[base[0]+t.base[0]];for(inti=1;i<=base[0];i++)p[i]=base[i];delete[]base;base=p;maxlen=base[0]+t.base[0];}for(inti=1;i<=t.base[0];i++)base[base[0]+i]=t.base[i];base[0]+=t.base[0];}36第35页/共71页3.2串的存储表示6.求子串（非空子串）求子串的定义为将串s中的第pos个字符开始长度为len的子串，复制到串t中。如图3-7所示。37第36页/共71页3.2串的存储表示顺序串中求子串的实现算法为：①检查参数的合法性，当pos<1或pos>base[0]，或len<1或pos+len-1>base[0]时，操作失败；②将当前串从pos指向位置开始的长度为len的子串复制到串t中；③操作成功，结束。38第37页/共71页3.2串的存储表示【算法3-6】boolSqString::SubString(intpos,intlen,SqString&t){if((pos<1)||(pos>base[0])||pos-1+len>base[0]){cout<<"操作失败"<<endl;returnfalse;}else{for(inti=pos;i<=len;i++)t.base[i-pos+1]=base[i];t.base[0]=len;returntrue;}}39第38页/共71页3.2串的存储表示3.2.2串的链式存储串的顺序存储方式节约了系统开销，但是如果需要经常对串执行插入、删除子串等操作，就需要频繁移动串中的字符，因此，我们引入串的另一种存储方式——链式存储，又称动态存储。这样就可以避免频繁的插入、删除操作带来的效率低下等问题。40第39页/共71页3.2串的存储表示在链式存储结构下，存储空间被分成一系列大小相同的结点，每个结点包含两个域：字符域data和指针域next。其中，字符域用来存放字符，指针域则用来存放指向下一个结点的指针。一个串可用一个单链表来存储。链表中的结点数目等于串的长度。例如，一个字符串s=“ABCDEFGHI”，那么它的单链表存储方式如图3-8所示。41第40页/共71页3.2串的存储表示42为了提高串的链式存储的存储密度，节省空间，可以将链串的结点大小设置为4。那么串s=“ABCDEFGHI”在结点大小为4的链串存储结构如图3-9所示。第41页/共71页3.2串的存储表示链串的存储结构可定义如下：#defineN4structLStringNode{chardata[N];structLStringNode*next;};classLinkString{LStringNode*head;intlength;43第42页/共71页3.2串的存储表示public:LinkString();LinkString(char*t);LinkString(LinkString&t);~LinkString();boolInsertString(intpos,LinkString&t);boolDelSubString(intpos,intlen,LinkString&t);voidOutputString();//其他操作};44第43页/共71页3.2串的存储表示链串的插入操作与单链表的插入过程相似，但又有明显的区别，单链表中每一个结点都是一个单独的元素，而块链式的串中每一块有若干个独立的元素，如图3-10（a）所示，当插入位置不是刚好位于每一块的起始处时，插入子串的处理相对要复杂。为尽量减少插入时字符的移动，可采用牺牲一定存储空间的办法，将插入点所在块的串拆分成两个块，无效字符的位置用“#”填充，如图3-10（b）所示，这样，待插入的串就可以直接进行链接。45第44页/共71页3.2串的存储表示46第45页/共71页3.2串的存储表示链串插入操作实现算法为：①判断插入位置是否有效，无效立即结束；否则继续；②找到插入位置，以指针p指向pos所在块或其前一块；若pos对块长取余不为0，p指向pos所在块，生成新结点，对该块进行拆分；否则，p指向pos所在块的前一块；③将t串链接到s串中；④操作成功，结束。【算法3-7】47第46页/共71页3.3串的模式匹配算法设s和t是给定的两个串，其长度分别为n和m，且有n≥m，在串s中找到等于子串t的过程称为模式匹配，其中，串s称为主串，t称为模式。如果在s中找到等于t的子串，则称匹配成功，函数返回t在s中的首次出现的存储位置(或序号)，否则匹配失败，返回0。48第47页/共71页3.3串的模式匹配算法Brute-Force算法简称为BF算法，亦称简单匹配算法，设主串s="s1…sn"，模式串t="t1…tm"，其基本思想是：1.从主串s的第一个字符s1开始和模式串t="t1…tm"中的第一个字符t1比较；2.若相等，则继续逐个比较后续字符，s2和t2；3.若不相等，从主串s的第二个字符s2开始重新与模式串t的第一个字符t1进行比较。4.重复上述过程，如果在主串s中找到一个与串t相同的子串，则匹配成功，返回模式串t在主串s主的序号；如果比较完主串s的所有字符序列，没有和模式串t相等的子串，则匹配失败返回0。49第48页/共71页3.3串的模式匹配算法设主串s= “ababcabcacba”模式串t= “abcac”。s的长度为n(n=12)，t的长度为m（m=5）。指针i、j分别为主串s、模式串t当前比较字符的下标。模式匹配的过程如图3-11所示。50第49页/共71页3.3串的模式匹配算法51第50页/共71页3.3串的模式匹配算法52第51页/共71页3.3串的模式匹配算法上述匹配过程中，可以得出以下结果：（1）若在前k-1(k≥1)次比较过程中未匹配成功，则第k次比较是从s串的第k个字符sk开始和t中的第一个字符t1比较；（2）设某次匹配有si≠tj，其中1≤i≤n，1≤j≤m，i≥j，则应有si-1=tj-1，...si-j+1=t1。再由（1）可知，下一次匹配串t右移一个位置，使得与字符t1对应的s的开始位置是i-j+2，即主串的字符si-j+2与模式串的第一个字符t1进行比较。如图3-12所示。53第52页/共71页3.3串的模式匹配算法54第53页/共71页3.3串的模式匹配算法【算法3-8】intSqString::Indexof(SqString&t){if((base[0]==0)||(t.base[0]==0))//为空return0;inti=1,j=1;while(i<=base[0]&&j<=t.base[0]){if(base[i]==t.base[j]){i++;j++;}55第54页/共71页3.3串的模式匹配算法else{i=i-j+2;j=1;}}if(j>t.base[0])returni-t.base[0];//扫描完毕，匹配成功elsereturn0;//匹配失败}56第55页/共71页3.3串的模式匹配算法57第56页/共71页3.3串的模式匹配算法限于篇幅，不再分析图3-13所示的串在后续阶段的匹配过程，可按KMP算法的思想继续推导。【算法3-9】58第57页/共71页3.4文本编辑3.4.1问题描述与算法分析文本编辑是指利用计算机进行编辑工作，修改字符数据的形式或格式，包括串的查找、插入、删除等基本操作。在进行文本编辑时，我们把整个文本看成是一个字符串，称为文本串，为了便于处理，进一步地将文本串拆分成若干子串，即页是文本串的子串，行又是页的子串。59第58页/共71页3.4文本编辑例如有下列一段英文：Night-SongintheJungleNowRanntheKitebringshomethenightThatMangtheBatsetsfreeTheherdsareshutinbarnandhutForloosedtilldawnarewe把这首小诗看成是一个文本串，输入到内存后如图3-14所示。60第59页/共71页3.4文本编辑61第60页/共71页3.4文本编辑其相应的行表如表3-1所示，每一个行表项包含行号、该行的起始地址、长度。62第61页/共71页3.4文本编辑为实现文本编辑问题的求解，我们定义一个文本编辑类Editer如下（其中串的存储类型采用3.2.1节的顺序串SqString）：#defineMAX50typedefstructText_Row_Table{//行表元素结构定义intiRow;SqString*iStartAddress;intiLength;}Text_Row_Table;classEditer{//文本编辑类的定义Text_Row_TableRTable[MAX];//行表intRow_Count;//行数63第62页/共71页3.4文本编辑public:Editer(){Row_Count=0;}voidInputText();//“输入文本”处理函数voidSearchText();//“查找文本”处理函数//其他功能，略};64第63页/共71页3.4文本编辑3.4.2算法实现1.输入文本由于各行的文本子串以行表项为标识，因此输入阶段的处理，主要完成的就是每输入一行文本子串就为其建立一个行表项，记录行号、起始地址与行内串长度。如算法3-10所示。65第64页/共71页3.4文本编辑【算法3-10】voidEditer::InputText(){charin_str[MAX];while(cin.getline(in_str,MAX,'\n')&&in_str[0]!='\\'){//约定以'\n'为换行，'\\'为文本串输入完毕SqString*pstr=newSqString(in_str);RTable[Row_Count].iRow=Row_Count+1;RTable[Row_Count].iLength=pstr->base[0];RTable[Row_Count].iStartAddress=pstr;Row_Count++;}}66第65页/共71页3.4文本编辑2.查找文本【算法3-11】voidEditer::SearchText(){cout<<"请输入要查找的文本串"<<endl;charstr[MAX];cin>>str;SqStrings(str);for(inti=0,j;i<Row_Count;i++){SqString*p=RTable[i].iStartAddress;if(j=p->Indexof_KMP(s))67第66页/共71页3.4文本编辑{cout<<"找到了，行号"<<RTable[i].iRow<<"位置"<<j<<endl;break;}}if(i>=Row_Count)cout<<"未找到！"<<endl;}68第67页/共71页3.4文本编辑3.主程序与测试#include"iostream"usingnamespacestd;voidmain(){Editert1;t1.InputText();t1.SearchText();}69第68页/共71页运行结果：Night-SongintheJungle↙NowRanntheKitebringshomethenight↙ThatMangtheBatsetsfree↙\↙请输入要查找的文本串Kitebrings↙找到了，行号2位置1470第69页/共71页3.5小结串是一种数据类型受到限制的特殊线性表，规定表中的每一个元素类型只能为字符型。串虽然是线性表，但又有它特殊的地方，即表中元素为单个字符，但串结构通常不是单个处理某一个字符元素，通常是整串进行讨论。串的存储方式与线性表类似，也具有顺序存储和链式存储两种方式。串的插入、删除等操作较线性表上的操作要复杂一些。在顺序串中给出了串的构造、插入、删除、串的输出和串的连接等算法。在链式串中给出了串的插入、删除等算法。71第70页/共71页