《数据结构：第3章串与文本编辑.ppt》由会员分享，可在线阅读，更多相关《数据结构：第3章串与文本编辑.ppt（71页珍藏版）》请在三一办公上搜索。
1、第3章 串与文本编辑,3.1 串的类型定义3.2 串的存储表示3.3 串的模式匹配算法3.4 文本编辑3.5 小结,0,数据结构与算法,3.1 串的类型定义,1.串的相关术语串是由零个或多个字符组成的有限序列，记为：s=s1s2sn。其中s是串名；双引号内的字符序列s1s2sn是串值；n(n=0)表示串的长度。,1,数据结构与算法,3.1 串的类型定义,例如：s1=“data structure”/串，长度为14 串长度为零的串称为空串。例如：s=“”/空串，长度为0 组成串的字符均为空格的串称为空格串或空白串。例如：s=“”/空格串，长度为4,2,数据结构与算法,3.1 串的类型定义,一个串
2、中任意个连续字符组成的子序列称为该串的子串。空串是任何串的子串。例如：s1=“data structure”s2=“data”/s2是s1的子串 s3=“structure”/s3是s1的子串 s4=“datastructure”/s4不是s1的子串包含子串的串称为主串。上例中s1为主串。,3,数据结构与算法,3.1 串的类型定义,子串的序号是该子串的第一个字符在主串中的序号。在上例子串s2在s1中的序号为1，s3在s1中的序号为6。S4不是s1的子串，也可以说，s4在s1中的序号为0。当且仅当串的长度相等并且对应位置上的字符都相同时，称这两个字符串是相等的。例如：s1=“data struc
3、ture”s2=“data structure”s3=“datastructure”/s1与s2相等，s3与s1和s2均不相等,4,数据结构与算法,3.1 串的类型定义,按照串中字符的次序，逐一比较两个字符串中字符的大小，以确定两个串的大小关系的操作，称为串的比较。例如：s5=data，s6=DATA，则有s5 s6的比较结果为1，s5 s6的比较结果为0。,5,数据结构与算法,3.1 串的类型定义,2.串的ADT定义在引入串的ADT定义前我们先来看一个字符串应用的例子。【例3-1】有一个字符串“live on no evil”，检查它是否为“回文”。当一个字符串顺读和逆读都一样，就可以称这个
4、字符串是回文。,6,数据结构与算法,3.1 串的类型定义,英文中的回文具有广义和狭义之分，广义的回文是指串中的空格字符不计入内，比如串“ten animals I slam in a net”去掉空格字符后是一个回文。狭义的回文是指将空格字符计入在内，比如题目中的“Live on no evil.”不过滤掉空格就是回文字符串。单个英文单词的回文符合狭义回文。例如：eye、mum、refer、level等。,7,数据结构与算法,3.1 串的类型定义,判断一个字符串s是否为回文（狭义的），需要进行如下操作：（1）存储串s，并以相反顺序存储为串t；（2）比较s与t；（3）得出字符串s是否为回文串的判
5、断；（4）输出回文串s例3-1是一个串的实际应用问题，为解决问题所需要的有关串的操作，即串类型应该提供的应用接口都是以串为单位，而不是串中的单个字符为单位。下面给出串的ADT定义：,8,数据结构与算法,3.1 串的类型定义,ADT StringData:D=ai ai ElemSet,i=1,2,.,n,n=0Structure:S=|ai-1,ai D,i=2,3,noPerations:ConstructString()/操作结果：创建一个空的串sDestructString()/操作条件：已有串s/操作结果：销毁当前串sStringLen()/操作条件：已有串s/操作结果：得到当前串s的
6、实际长度,9,数据结构与算法,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返回被删除的子串,10,数据结构与算法,3.1 串的类型定义,InsertSubString(pos,t
7、)/操作条件：已有串s和参数串t/操作结果：将t插入到当前串第pos个位置前ConnectString(t)/操作条件：已有串s和参数串t/操作结果：将t连接到当前串s之后ClearString()/操作条件：已有串s/操作结果：将当前串s清空ReplaceString(pos,len,t)/操作条件：已有串s和参数串t/操作结果：将当前串s中第pos个字符开始的长度为len的子串，替换为tADT String;,11,数据结构与算法,3.2 串的存储表示,3.2.1 串的顺序存储将串所占用空间的大小称为串容量，实际存在的元素个数称为串长，如图3-1所示。,12,数据结构与算法,3.2 串的存
8、储表示,为了表示串的结束，可在串内容最后一个有效字符后，再多开辟一个存储空间，存放结束标志0（C/C+语言中的字符串就采用这种方法），如图3-2所示。,13,数据结构与算法,3.2 串的存储表示,借助于顺序存储时数组的0号下标存储串长，即有效地利用了空间，又使得串中字符的位序与其存放位置（下标）一致，如图3-3所示。,14,数据结构与算法,3.2 串的存储表示,定义顺序串：#define MAX 100class SqStringpublic:char*base;/存储串的字符数组/base0表示串的实际长度,不另设结束标志int maxlen;/表示串的最大长度public:SqString
9、();/构造函数SqString(char*s);/构造函数SqString(SqString/析构函数,15,数据结构与算法,3.2 串的存储表示,bool InsertString(int pos,SqString,16,数据结构与算法,3.2 串的存储表示,顺序串的构造与析构 串的构造有三种方法，分别是构造空串、由基本类型的字符串构造一个新串以及使用串对象来构造串。下面给出三种方法构造串的实现过程。（1）构造空的顺序串。【算法3-1-1】SqString:SqString()maxlen=MAX;base=new charmaxlen+1;/0下标留作记录长度base0=0;,17,数据
10、结构与算法,3.2 串的存储表示,（2）由基本字符串构造一个新串。【算法3-1-2】SqString:SqString(char*s)/由机内标准串构造maxlen=MAX;base=new charmaxlen+1;base0=strlen(s);for(int i=0;si!=0;i+)basei+1=si;,18,数据结构与算法,3.2 串的存储表示,（3）使用串对象来构造串。【算法3-1-3】SqString:SqString(SqString,19,数据结构与算法,3.2 串的存储表示,（4）析构函数【算法3-1-4】SqString:SqString()delete base;,2
11、0,数据结构与算法,3.2 串的存储表示,顺序串插入操作顺序串插入操作的功能是将一个指定的串插入到当前串中的指定位置之前，以s串和t串分别表示当前串和待插入串，则插入前后s串与t串的状态如图3-4（a）和图3-4（b）所示。,21,数据结构与算法,3.2 串的存储表示,22,数据结构与算法,3.2 串的存储表示,顺序串插入操作实现算法为：检查插入位置的合法性，即当插入位置posbase0，或base0+t.base0 maxlen（没有足够空间插入t）时，提示错误信息，终止程序；从pos指向的位置开始，一直到最后的字符，每个字符都要向后移动，移动的长度为t串的长度；插入t串，修改s的串长，操作
12、成功，结束。,23,数据结构与算法,3.2 串的存储表示,【算法3-2】bool SqString:InsertString(int pos,SqString/元素后移,24,数据结构与算法,3.2 串的存储表示,for(i=1;i=t.base0;i+)basepos-1+i=t.basei;/插入元素base0+=t.base0;return true;,25,数据结构与算法,3.2 串的存储表示,顺序串删除操作顺序串删除操作的功能是删除s串中从第pos个位置开始的长度为len的子串。如图3-5所示。,26,数据结构与算法,3.2 串的存储表示,27,数据结构与算法,3.2 串的存储表示,
13、顺序串删除操作实现算法为：检查参数的合法性，有两种不合法的操作条件：一是pos的值不在串s的长度范围内，即posbase0；二是从串s第pos个位置开始不存在长度为len的子串，即pos+len-1base0；将待删除的子串复制给t；在s中删除指定的子串，修改s的串长，操作成功，结束。,28,数据结构与算法,3.2 串的存储表示,【算法3-3】bool SqString:DelSubString(int pos,int len,SqString,29,数据结构与算法,3.2 串的存储表示,for(i=pos+len;i=base0;i+)/元素前移basei-len=basei;base0-=
14、len;return true;,30,数据结构与算法,3.2 串的存储表示,输出顺序串操作顺序串输出操作的功能是将串中的字符全部输出。顺序串输出操作实现算法为：检查串时否为空串，若为空，输出空串信息；若串非空，则利用循环输出串的内容；操作成功，结束。,31,数据结构与算法,3.2 串的存储表示,【算法3-4】void SqString:OutputString()if(base0=0)/判断串是否为空串cout空串endl;elsefor(int i=1;i=base0;i+)coutbasei;coutendl;,32,数据结构与算法,3.2 串的存储表示,串的连接串的连接，顾名思义，是指
15、将两个已有的串连接成为一个串。例如，有两个串s和t都是类SqString的对象，那么两个串连接后为s=s+t，如图3-6所示。,33,数据结构与算法,3.2 串的存储表示,顺序串连接操作实现算法为：计算连接后的串长，如果超出顺序串的maxlen，重新分配空间；否则，从当前串的第base0+1个位置起，依次将t串中每一个字符复制到s；更新当前串长，操作成功，返回。,34,数据结构与算法,3.2 串的存储表示,【算法3-5】void SqString:ConnectString(SqString,35,数据结构与算法,3.2 串的存储表示,6.求子串（非空子串）求子串的定义为将串s中的第pos个字
16、符开始长度为len的子串，复制到串t中。如图3-7所示。,36,数据结构与算法,3.2 串的存储表示,顺序串中求子串的实现算法为：检查参数的合法性，当posbase0，或lenbase0时，操作失败；将当前串从pos指向位置开始的长度为len的子串复制到串t中；操作成功，结束。,37,数据结构与算法,3.2 串的存储表示,【算法3-6】bool SqString:SubString(int pos,int len,SqString,38,数据结构与算法,3.2 串的存储表示,3.2.2 串的链式存储串的顺序存储方式节约了系统开销，但是如果需要经常对串执行插入、删除子串等操作，就需要频繁移动串中
17、的字符，因此，我们引入串的另一种存储方式链式存储，又称动态存储。这样就可以避免频繁的插入、删除操作带来的效率低下等问题。,39,数据结构与算法,3.2 串的存储表示,在链式存储结构下，存储空间被分成一系列大小相同的结点，每个结点包含两个域：字符域data和指针域next。其中，字符域用来存放字符，指针域则用来存放指向下一个结点的指针。一个串可用一个单链表来存储。链表中的结点数目等于串的长度。例如，一个字符串s=“ABCDEFGHI”，那么它的单链表存储方式如图3-8所示。,40,数据结构与算法,3.2 串的存储表示,41,数据结构与算法,为了提高串的链式存储的存储密度，节省空间，可以将链串的结
18、点大小设置为4。那么串s=“ABCDEFGHI”在结点大小为4的链串存储结构如图3-9所示。,3.2 串的存储表示,链串的存储结构可定义如下：#define N 4struct LStringNodechar dataN;struct LStringNode*next;class LinkStringLStringNode*head;int length;,42,数据结构与算法,3.2 串的存储表示,public:LinkString();LinkString(char*t);LinkString(LinkString,43,数据结构与算法,3.2 串的存储表示,链串的插入操作与单链表的插入过
19、程相似，但又有明显的区别，单链表中每一个结点都是一个单独的元素，而块链式的串中每一块有若干个独立的元素，如图3-10（a）所示，当插入位置不是刚好位于每一块的起始处时，插入子串的处理相对要复杂。为尽量减少插入时字符的移动，可采用牺牲一定存储空间的办法，将插入点所在块的串拆分成两个块，无效字符的位置用“#”填充，如图3-10（b）所示，这样，待插入的串就可以直接进行链接。,44,数据结构与算法,3.2 串的存储表示,45,数据结构与算法,3.2 串的存储表示,链串插入操作实现算法为：判断插入位置是否有效，无效立即结束；否则继续；找到插入位置，以指针p指向pos所在块或其前一块；若pos对块长取余
20、不为0，p指向pos所在块，生成新结点，对该块进行拆分；否则，p指向pos所在块的前一块；将t串链接到s串中；操作成功，结束。【算法3-7】,46,数据结构与算法,3.3 串的模式匹配算法,设s和t是给定的两个串，其长度分别为n和m，且有nm，在串s中找到等于子串t的过程称为模式匹配，其中，串s称为主串，t称为模式。如果在s中找到等于t的子串，则称匹配成功，函数返回t在s中的首次出现的存储位置(或序号)，否则匹配失败，返回0。,47,数据结构与算法,3.3 串的模式匹配算法,Brute-Force算法简称为BF算法，亦称简单匹配算法，设主串s=s1sn，模式串t=t1tm，其基本思想是：1.从
21、主串s的第一个字符s1开始和模式串t=t1tm中的第一个字符t1比较；2.若相等，则继续逐个比较后续字符，s2和t2；3.若不相等，从主串s的第二个字符s2开始重新与模式串t的第一个字符t1进行比较。4.重复上述过程，如果在主串s中找到一个与串t相同的子串，则匹配成功，返回模式串t在主串s主的序号；如果比较完主串s的所有字符序列，没有和模式串t相等的子串，则匹配失败返回0。,48,数据结构与算法,3.3 串的模式匹配算法,设主串s=“ababcabcacba”模式串t=“abcac”。s的长度为n(n=12)，t的长度为m（m=5）。指针i、j分别为主串s、模式串t当前比较字符的下标。模式匹配
22、的过程如图3-11所示。,49,数据结构与算法,3.3 串的模式匹配算法,50,数据结构与算法,3.3 串的模式匹配算法,51,数据结构与算法,3.3 串的模式匹配算法,上述匹配过程中，可以得出以下结果：（1）若在前k-1(k1)次比较过程中未匹配成功，则第k次比较是从s串的第k个字符sk开始和t中的第一个字符t1比较；（2）设某次匹配有sitj，其中1in，1jm，ij，则应有si-1=tj-1，.si-j+1=t1。再由（1）可知，下一次匹配串t右移一个位置，使得与字符t1对应的s的开始位置是i-j+2，即主串的字符si-j+2与模式串的第一个字符t1进行比较。如图3-12所示。,52,数
23、据结构与算法,3.3 串的模式匹配算法,53,数据结构与算法,3.3 串的模式匹配算法,【算法3-8】int SqString:Indexof(SqString,54,数据结构与算法,3.3 串的模式匹配算法,elsei=i-j+2;j=1;if(jt.base0)return i-t.base0;/扫描完毕，匹配成功elsereturn 0;/匹配失败,55,数据结构与算法,3.3 串的模式匹配算法,56,数据结构与算法,3.3 串的模式匹配算法,限于篇幅，不再分析图3-13所示的串在后续阶段的匹配过程，可按KMP算法的思想继续推导。【算法3-9】,57,数据结构与算法,3.4 文本编辑,3
24、.4.1 问题描述与算法分析文本编辑是指利用计算机进行编辑工作，修改字符数据的形式或格式，包括串的查找、插入、删除等基本操作。在进行文本编辑时，我们把整个文本看成是一个字符串，称为文本串，为了便于处理，进一步地将文本串拆分成若干子串，即页是文本串的子串，行又是页的子串。,58,数据结构与算法,3.4 文本编辑,例如有下列一段英文：Night-Song in the JungleNow Rann the Kite brings home the nightThat Mang the Bat sets freeThe herds are shut in barn and hutFor loosed
25、 till dawn are we把这首小诗看成是一个文本串，输入到内存后如图3-14所示。,59,数据结构与算法,3.4 文本编辑,60,数据结构与算法,3.4 文本编辑,其相应的行表如表3-1所示，每一个行表项包含行号、该行的起始地址、长度。,61,数据结构与算法,3.4 文本编辑,为实现文本编辑问题的求解，我们定义一个文本编辑类Editer如下（其中串的存储类型采用节的顺序串SqString）：#define MAX 50typedef struct Text_Row_Table/行表元素结构定义int iRow;SqString*iStartAddress;int iLength;Te
26、xt_Row_Table;class Editer/文本编辑类的定义Text_Row_Table RTableMAX;/行表int Row_Count;/行数,62,数据结构与算法,3.4 文本编辑,public:Editer()Row_Count=0;void InputText();/“输入文本”处理函数void SearchText();/“查找文本”处理函数/其他功能，略;,63,数据结构与算法,3.4 文本编辑,3.4.2 算法实现1.输入文本由于各行的文本子串以行表项为标识，因此输入阶段的处理，主要完成的就是每输入一行文本子串就为其建立一个行表项，记录行号、起始地址与行内串长度。如
27、算法3-10所示。,64,数据结构与算法,3.4 文本编辑,【算法3-10】void Editer:InputText()char in_strMAX;while(cin.getline(in_str,MAX,n),65,数据结构与算法,3.4 文本编辑,2.查找文本【算法3-11】void Editer:SearchText()coutstr;SqString s(str);for(int i=0,j;iIndexof_KMP(s),66,数据结构与算法,3.4 文本编辑,cout=Row_Count)cout未找到！endl;,67,数据结构与算法,3.4 文本编辑,3.主程序与测试#in
28、clude iostreamusing namespace std;void main()Editer t1;t1.InputText();t1.SearchText();,68,数据结构与算法,运行结果：Night-Song in the JungleNow Rann the Kite brings home the nightThat Mang the Bat sets free请输入要查找的文本串Kite brings找到了，行号2 位置14,69,数据结构与算法,3.5 小结,串是一种数据类型受到限制的特殊线性表，规定表中的每一个元素类型只能为字符型。串虽然是线性表，但又有它特殊的地方，即表中元素为单个字符，但串结构通常不是单个处理某一个字符元素，通常是整串进行讨论。串的存储方式与线性表类似，也具有顺序存储和链式存储两种方式。串的插入、删除等操作较线性表上的操作要复杂一些。在顺序串中给出了串的构造、插入、删除、串的输出和串的连接等算法。在链式串中给出了串的插入、删除等算法。,70,数据结构与算法,
