数据结构ppt：第3章串与文本编辑.ppt

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,数据结构与算

2、法,3.1 串的类型定义,一个串中任意个连续字符组成的子序列称为该串的子串。空串是任何串的子串。 例如：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。 当且仅当串的长度相等并且对应位置上的字符都相同时，称这

3、两个字符串是相等的。 例如：s1= “data structure” 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

4、 evil”，检查它是否为“回文”。当一个字符串顺读和逆读都一样，就可以称这个字符串是回文,6,数据结构与算法,3.1 串的类型定义,英文中的回文具有广义和狭义之分，广义的回文是指串中的空格字符不计入内，比如串“ten animals I slam in a net”去掉空格字符后是一个回文。狭义的回文是指将空格字符计入在内，比如题目中的“Live on no evil.”不过滤掉空格就是回文字符串。单个英文单词的回文符合狭义回文。例如：eye、mum、refer、level等,7,数据结构与算法,3.1 串的类型定义,判断一个字符串s是否为回文（狭义的），需要进行如下操作： （1）存储串s，

5、并以相反顺序存储为串t； （2）比较s与t； （3）得出字符串s是否为回文串的判断； （4）输出回文串s 例3-1是一个串的实际应用问题，为解决问题所需要的有关串的操作，即串类型应该提供的应用接口都是以串为单位，而不是串中的单个字符为单位。下面给出串的ADT定义,8,数据结构与算法,3.1 串的类型定义,ADT String Data: D=ai ai ElemSet, i=1,2,.,n,n=0 Structure: S=| ai-1,ai D, i=2,3,n oPerations: ConstructString() /操作结果：创建一个空的串s DestructString() /操作

6、条件：已有串s /操作结果：销毁当前串s StringLen() /操作条件：已有串s /操作结果：得到当前串s的实际长度,9,数据结构与算法,3.1 串的类型定义,StringCpy(t) /操作条件：已有串s和参数串t /操作结果：将t复制到当前串s中 OutputString() /操作条件：已有串s /操作结果：输出当前串s SubString(pos, len, /存储串的字符数组 /base0表示串的实际长度,不另设结束标志 int maxlen;/表示串的最大长度 public: SqString();/构造函数 SqString(char *s); /构造函数 SqString

7、(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,数据结构与算法,3.2 串的存储表示,2）由基本字符串构造一个新串

8、。 【算法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;,20,数据结构与算法,3.2 串的存储表示

9、,顺序串插入操作 顺序串插入操作的功能是将一个指定的串插入到当前串中的指定位置之前，以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的串长，操作成功，结束,23,数据结构与算法,

10、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 串的存储表示,顺序串删除操作实现算法为：

11、 检查参数的合法性，有两种不合法的操作条件：一是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-=len; retu

12、rn true;,30,数据结构与算法,3.2 串的存储表示,输出顺序串操作 顺序串输出操作的功能是将串中的字符全部输出。顺序串输出操作实现算法为： 检查串时否为空串，若为空，输出空串信息； 若串非空，则利用循环输出串的内容； 操作成功，结束,31,数据结构与算法,3.2 串的存储表示,算法3-4】 void SqString:OutputString() if(base0=0) /判断串是否为空串 cout空串endl; else for(int i=1;i=base0;i+) coutbasei; coutendl;,32,数据结构与算法,3.2 串的存储表示,串的连接 串的连接，顾名思义

13、，是指将两个已有的串连接成为一个串。例如，有两个串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中的

14、第pos个字符开始长度为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 串的链式存储 串的顺序存储方式节约了系统开销，但是如果需要经常对串执行插入、删除子串等操作，就

15、需要频繁移动串中的字符，因此，我们引入串的另一种存储方式链式存储，又称动态存储。这样就可以避免频繁的插入、删除操作带来的效率低下等问题,39,数据结构与算法,3.2 串的存储表示,在链式存储结构下，存储空间被分成一系列大小相同的结点，每个结点包含两个域：字符域data和指针域next。其中，字符域用来存放字符，指针域则用来存放指向下一个结点的指针。 一个串可用一个单链表来存储。链表中的结点数目等于串的长度。例如，一个字符串s=“ABCDEFGHI”，那么它的单链表存储方式如图3-8所示,40,数据结构与算法,3.2 串的存储表示,41,数据结构与算法,为了提高串的链式存储的存储密度，节省空间，

16、可以将链串的结点大小设置为4。那么串s=“ABCDEFGHI”在结点大小为4的链串存储结构如图3-9所示,3.2 串的存储表示,链串的存储结构可定义如下： #define N 4 struct LStringNode char dataN; struct LStringNode *next; ; class LinkString LStringNode *head; int length,42,数据结构与算法,3.2 串的存储表示,public: LinkString(); LinkString(char *t); LinkString(LinkString,43,数据结构与算法,3.2 串的

17、存储表示,链串的插入操作与单链表的插入过程相似，但又有明显的区别，单链表中每一个结点都是一个单独的元素，而块链式的串中每一块有若干个独立的元素，如图3-10（a）所示，当插入位置不是刚好位于每一块的起始处时，插入子串的处理相对要复杂。为尽量减少插入时字符的移动，可采用牺牲一定存储空间的办法，将插入点所在块的串拆分成两个块，无效字符的位置用“#”填充，如图3-10（b）所示，这样，待插入的串就可以直接进行链接,44,数据结构与算法,3.2 串的存储表示,45,数据结构与算法,3.2 串的存储表示,链串插入操作实现算法为： 判断插入位置是否有效，无效立即结束；否则继续； 找到插入位置，以指针p指向

18、pos所在块或其前一块；若pos对块长取余不为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=s1s

19、n，模式串t=t1tm，其基本思想是： 1. 从主串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）。指

20、针i、j分别为主串s、模式串t当前比较字符的下标。模式匹配的过程如图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

21、与模式串的第一个字符t1进行比较。如图3-12所示,52,数据结构与算法,3.3 串的模式匹配算法,53,数据结构与算法,3.3 串的模式匹配算法,算法3-8】 int SqString:Indexof(SqString,54,数据结构与算法,3.3 串的模式匹配算法,else i=i-j+2; j=1; if(jt.base0) return i-t.base0;/扫描完毕，匹配成功 else return 0;/匹配失败,55,数据结构与算法,3.3 串的模式匹配算法,56,数据结构与算法,3.3 串的模式匹配算法,限于篇幅，不再分析图3-13所示的串在后续阶段的匹配过程，可按KMP算法的

22、思想继续推导。 【算法3-9,57,数据结构与算法,3.4 文本编辑,3.4.1 问题描述与算法分析 文本编辑是指利用计算机进行编辑工作，修改字符数据的形式或格式，包括串的查找、插入、删除等基本操作。 在进行文本编辑时，我们把整个文本看成是一个字符串，称为文本串，为了便于处理，进一步地将文本串拆分成若干子串，即页是文本串的子串，行又是页的子串,58,数据结构与算法,3.4 文本编辑,例如有下列一段英文： Night-Song in the Jungle Now Rann the Kite brings home the night That Mang the Bat sets free The

23、 herds are shut in barn and hut For loosed till dawn are we 把这首小诗看成是一个文本串，输入到内存后如图3-14所示,59,数据结构与算法,3.4 文本编辑,60,数据结构与算法,3.4 文本编辑,其相应的行表如表3-1所示，每一个行表项包含行号、该行的起始地址、长度,61,数据结构与算法,3.4 文本编辑,为实现文本编辑问题的求解，我们定义一个文本编辑类Editer如下（其中串的存储类型采用3.2.1节的顺序串SqString）： #define MAX 50 typedef struct Text_Row_Table /行表元素结

24、构定义 int iRow; SqString *iStartAddress; int iLength; Text_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. 输入文本 由于各行的文本子串以行表项为标识，因此输入阶段的处理，主要完成的就是每输入一行文本子串就为