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

1、第第3 3章章 串与文本编辑串与文本编辑3.1 3.1 串的类型定义串的类型定义3.2 3.2 串的存储表示串的存储表示3.3 3.3 串的方式匹配算法串的方式匹配算法3.4 3.4 文本编辑文本编辑3.5 3.5 小结小结 3.1 3.1 串的类型定义串的类型定义1. 1. 串的相关术语串的相关术语串是由零个或多个字符组成的有限序列，记串是由零个或多个字符组成的有限序列，记为：为：s= s1s2sn s= s1s2sn 。其中。其中s s是串名；双引号是串名；双引号内的字符序列内的字符序列s1s2sns1s2sn是串值；是串值；n(n=0)n(n=0)表表示串的长度。示串的长度。3.1 3.

2、1 串的类型定义串的类型定义例如：s1= “data structure /串，长度为14 串长度为零的串称为空串。例如：s= “ /空串，长度为0 组成串的字符均为空格的串称为空格串或空白串。例如：s= “ /空格串，长度为43.1 3.1 串的类型定义串的类型定义一个串中恣意个延续字符组成的子序列称为该串的子串。空串是任何串的子串。例如：s1 = “data structure s2= “data /s2是s1的子串 s3= “structure /s3是s1的子串 s4= “datastructure /s4不是s1的子串包含子串的串称为主串。上例中s1为主串。3.1 3.1 串的类型定

3、义串的类型定义子串的序号是该子串的第一个字符在主串中子串的序号是该子串的第一个字符在主串中的序号。在上例子串的序号。在上例子串s2s2在在s1s1中的序号为中的序号为1 1，s3s3在在s1s1中的序号为中的序号为6 6。S4S4不是不是s1s1的子串，也的子串，也可以说，可以说，s4s4在在s1s1中的序号为中的序号为0 0。当且仅当串的长度相等并且对应位置上的字当且仅当串的长度相等并且对应位置上的字符都一样时，称这两个字符串是相等的。符都一样时，称这两个字符串是相等的。例如：例如：s1= s1= “data structuredata structure s2= s2= “data str

4、ucturedata structure s3= s3= “datastructure datastructure /s1 /s1与与s2s2相等，相等，s3s3与与s1s1和和s2s2均不相等均不相等 3.1 3.1 串的类型定义串的类型定义按照串中字符的次序，逐一比较两个字符串中字符的大小，以确定两个串的大小关系的操作，称为串的比较。例如：s5=data，s6= DATA，那么有s5 s6的比较结果为1，s5 =0Structure:S=| ai-1,ai D, i=2,3,noPerations:ConstructString()/操作结果：创建一个空的串sDestructString(

5、)/操作条件：已有串s/操作结果：销毁当前串sStringLen() /操作条件：已有串s/操作结果：得到当前串s的实践长度3.1 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个字符开场，长度为le

6、n的子串/ 并由t前往被删除的子串3.1 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的子串，交换为tADT String;3.2 3.2 串的存储表示串的存储表示3.2.1 3.2.

7、1 串的顺序存储串的顺序存储将串所占用空间的大小称为串容量，实践存将串所占用空间的大小称为串容量，实践存在的元素个数称为串长，如图在的元素个数称为串长，如图3-13-1所示。所示。3.2 3.2 串的存储表示串的存储表示为了表示串的终了，可在串内容最后一个有效字符后，再多开辟一个存储空间，存放终了标志0 C/C+言语中的字符串就采用这种方法，如图3-2所示。3.2 3.2 串的存储表示串的存储表示借助于顺序存储时数组的0号下标存储串长，即有效地利用了空间，又使得串中字符的位序与其存放位置下标一致，如图3-3所示。3.2 3.2 串的存储表示串的存储表示定义顺序串：#define MAX 100

8、class SqStringpublic:char *base;/存储串的字符数组/base0表示串的实践长度,不另设终了标志int maxlen;/表示串的最大长度public:SqString();/构造函数SqString(char *s); /构造函数SqString(SqString &t); /构造函数SqString();/析构函数3.2 3.2 串的存储表示串的存储表示bool InsertString(int pos,SqString &t); /在串的指定位置pos插入一个子串tbool DelSubString(int pos,int len,SqString &t) ;

9、/删除当前串的子串,并由t前往void OutputString();/输出串中一切字符void ConnectString(SqString &t) ;/在当前串尾衔接串tbool SubString(int pos,int len,SqString &t);/求当前串从pos开场长度为len的子串int Indexof(SqString &t);/求方式串t在当前串中第一次出现的位置int Indexof_KMP(SqString &t);/KMP法求方式串t在当前串中第一次出现的位置void GetNext(int next);/KMP方式匹配算法辅助函数/其他操作;3.2 3.2 串的

10、存储表示串的存储表示顺序串的构造与析构顺序串的构造与析构 串的构造有三种方法，分别是构造空串、串的构造有三种方法，分别是构造空串、由根本类型的字符串构造一个新串以及运用由根本类型的字符串构造一个新串以及运用串对象来构造串。下面给出三种方法构造串串对象来构造串。下面给出三种方法构造串的实现过程。的实现过程。1 1构造空的顺序串。构造空的顺序串。【算法【算法3-1-13-1-1】SqString:SqString()SqString:SqString()maxlen=MAX;maxlen=MAX;base=new charmaxlen+1;base=new charmaxlen+1;/0/0下标留

11、作记录长度下标留作记录长度base0=0;base0=0; 3.2 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;3.2 3.2 串的存储表示串的存储表示3运用串对象来构造串。【算法3-1-3】SqString:SqString(SqString& t) maxlen=t.maxlen;base=new charmaxlen+1;b

12、ase0=t.base0;for(int i=1;i=base0;i+)basei=t.basei;3.2 3.2 串的存储表示串的存储表示4析构函数【算法3-1-4】SqString:SqString()delete base;3.2 3.2 串的存储表示串的存储表示顺序串插入操作顺序串插入操作顺序串插入操作的功能是将一个指定的串插顺序串插入操作的功能是将一个指定的串插入到当前串中的指定位置之前，以入到当前串中的指定位置之前，以s s串和串和t t串串分别表示当前串和待插入串，那么插入前后分别表示当前串和待插入串，那么插入前后s s串与串与t t串的形状如图串的形状如图3-43-4a a和图

13、和图3-43-4b b所示。所示。3.2 3.2 串的存储表示串的存储表示3.2 3.2 串的存储表示串的存储表示顺序串插入操作实现算法为：检查插入位置的合法性，即当插入位置posbase0，或base0+t.base0 maxlen没有足够空间插入t时，提示错误信息，终止程序；从pos指向的位置开场，不断到最后的字符，每个字符都要向后挪动，挪动的长度为t串的长度；插入t串，修正s的串长，操作胜利，终了。3.2 3.2 串的存储表示串的存储表示【算法3-2】bool SqString:InsertString(int pos,SqString& t)if(posbase0+1|pos-1+t.

14、base0maxlen)cout插入失败=pos;i-)basei+t.base0=basei; /元素后移3.2 3.2 串的存储表示串的存储表示for(i=1;i=t.base0;i+)basepos-1+i=t.basei; /插入元素base0+=t.base0;return true;3.2 3.2 串的存储表示串的存储表示顺序串删除操作顺序串删除操作顺序串删除操作的功能是删除顺序串删除操作的功能是删除s s串中从第串中从第pospos个位置开场的长度为个位置开场的长度为lenlen的子串。如图的子串。如图3-53-5所所示。示。 3.2 3.2 串的存储表示串的存储表示3.2 3.

15、2 串的存储表示串的存储表示顺序串删除操作实现算法为： 检查参数的合法性，有两种不合法的操作条件：一是pos的值不在串s的长度范围内，即posbase0；二是从串s第pos个位置开场不存在长度为len的子串，即pos+len-1base0； 将待删除的子串复制给t； 在s中删除指定的子串，修正s的串长，操作胜利，终了。3.2 3.2 串的存储表示串的存储表示【算法3-3】bool SqString:DelSubString(int pos,int len,SqString& t) if(posbase0)|pos-1+lenbase0)cout删除失败endl;return false;els

16、efor(int i=pos;i=pos-1+len;i+)/删除的元素复制给tt.basei-pos+1=basei;t.base0=len;3.2 3.2 串的存储表示串的存储表示for(i=pos+len;i=base0;i+)/元素前移basei-len=basei;base0-=len;return true;3.2 3.2 串的存储表示串的存储表示输出顺序串操作输出顺序串操作顺序串输出操作的功能是将串中的字符全部顺序串输出操作的功能是将串中的字符全部输出。顺序串输出操作实现算法为：输出。顺序串输出操作实现算法为：检查串时否为空串，假设为空，输出空串检查串时否为空串，假设为空，输出空

17、串信息；信息；假设串非空，那么利用循环输出串的内容；假设串非空，那么利用循环输出串的内容；操作胜利，终了。操作胜利，终了。3.2 3.2 串的存储表示串的存储表示【算法3-4】void SqString:OutputString()if(base0=0) /判别串能否为空串cout空串endl;elsefor(int i=1;i=base0;i+)coutbasei;coutmaxlen)char *p=new charbase0+t.base0;for(int i=1;i=base0;i+)pi=basei;delete base;base=p;maxlen=base0+t.base0;fo

18、r(int i=1;i=t.base0;i+)basebase0+i=t.basei;base0+=t.base0; 3.2 3.2 串的存储表示串的存储表示6. 6. 求子串非空子串求子串非空子串求子串的定义为将串求子串的定义为将串s s中的第中的第pospos个字符开场个字符开场长度为长度为lenlen的子串，复制到串的子串，复制到串t t中。如图中。如图3-73-7所示。所示。3.2 3.2 串的存储表示串的存储表示顺序串中求子串的实现算法为：检查参数的合法性，当posbase0，或lenbase0时，操作失败；将当前串从pos指向位置开场的长度为len的子串复制到串t中；操作胜利，终了

19、。3.2 3.2 串的存储表示串的存储表示【算法3-6】bool SqString:SubString(int pos,int len,SqString &t) if(posbase0)|pos-1+lenbase0)cout操作失败endl;return false;elsefor(int i=pos;i=len;i+)t.basei-pos+1=basei;t.base0=len;return true;3.2 3.2 串的存储表示串的存储表示3.2.2 3.2.2 串的链式存储串的链式存储串的顺序存储方式节约了系统开销，但是假串的顺序存储方式节约了系统开销，但是假设需求经常对串执行插入、

20、删除子串等操作，设需求经常对串执行插入、删除子串等操作，就需求频繁挪动串中的字符，因此，我们引就需求频繁挪动串中的字符，因此，我们引入串的另一种存储方式入串的另一种存储方式链式存储，又称链式存储，又称动态存储。这样就可以防止频繁的插入、删动态存储。这样就可以防止频繁的插入、删除操作带来的效率低下等问题。除操作带来的效率低下等问题。3.2 3.2 串的存储表示串的存储表示在链式存储构造下，存储空间被分成一系列大小一样的结点，每个结点包含两个域：字符域data和指针域next。其中，字符域用来存放字符，指针域那么用来存放指向下一个结点的指针。一个串可用一个单链表来存储。链表中的结点数目等于串的长度

21、。例如，一个字符串s=“ABCDEFGHI，那么它的单链表存储方式如图3-8所示。3.2 3.2 串的存储表示串的存储表示为了提高串的链式存储的存储密度，节省空间，可以将链串的结点大小设置为4。那么串s=“ABCDEFGHI在结点大小为4的链串存储构造如图3-9所示。3.2 3.2 串的存储表示串的存储表示链串的存储构造可定义如下：#define N 4struct LStringNodechar dataN;struct LStringNode *next;class LinkStringLStringNode *head;int length;3.2 3.2 串的存储表示串的存储表示pub

22、lic:LinkString();LinkString(char *t);LinkString(LinkString &t);LinkString();bool InsertString(int pos,LinkString &t); bool DelSubString(int pos,int len,LinkString &t) ;void OutputString();/其他操作;3.2 3.2 串的存储表示串的存储表示链串的插入操作与单链表的插入过程类似，但又有明显的区别，单链表中每一个结点都是一个单独的元素，而块链式的串中每一块有假设干个独立的元素，如图3-10a所示，当插入位置不是刚

23、好位于每一块的起始处时，插入子串的处置相对要复杂。为尽量减少插入时字符的挪动，可采用牺牲一定存储空间的方法，将插入点所在块的串拆分成两个块，无效字符的位置用“#填充，如图3-10b所示，这样，待插入的串就可以直接进展链接。3.2 3.2 串的存储表示串的存储表示3.2 3.2 串的存储表示串的存储表示链串插入操作实现算法为：判别插入位置能否有效，无效立刻终了；否那么继续；找到插入位置，以指针p指向pos所在块或其前一块；假设pos对块长取余不为0，p指向pos所在块，生成新结点，对该块进展拆分；否那么，p指向pos所在块的前一块；将t串链接到s串中；操作胜利，终了。【算法3-7】3.3 3.3

24、 串的方式匹配算法串的方式匹配算法设s和t是给定的两个串，其长度分别为n和m，且有nm，在串s中找到等于子串t的过程称为方式匹配，其中，串s称为主串，t称为方式。假设在s中找到等于t的子串，那么称匹配胜利，函数前往t在s中的初次出现的存储位置(或序号)，否那么匹配失败，前往0。3.3 3.3 串的方式匹配算法串的方式匹配算法Brute-Force算法简称为BF算法，亦称简单匹配算法，设主串s=s1sn，方式串t=t1tm，其根本思想是：1. 从主串s的第一个字符s1开场和方式串t=t1tm中的第一个字符t1比较；2. 假设相等，那么继续逐个比较后续字符，s2和t2；3. 假设不相等，从主串s的

25、第二个字符s2开场重新与方式串t的第一个字符t1进展比较。4. 反复上述过程，假设在主串s中找到一个与串t一样的子串，那么匹配胜利，前往方式串t在主串s主的序号；假设比较完主串s的一切字符序列，没有和方式串t相等的子串，那么匹配失败前往0。3.3 3.3 串的方式匹配算法串的方式匹配算法设主串s=“ababcabcacba方式串t=“abcac。s的长度为n(n=12)，t的长度为mm=5。指针i、j分别为主串s、方式串t当前比较字符的下标。方式匹配的过程如图3-11所示。3.3 3.3 串的方式匹配算法串的方式匹配算法3.3 3.3 串的方式匹配算法串的方式匹配算法3.3 3.3 串的方式匹

26、配算法串的方式匹配算法上述匹配过程中，可以得出以下结果：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所示。3.3 3.3 串的方式匹配算法串的方式匹配算法3.3 3.3 串的方式匹配算法串的方式匹配算法【算法3-8】int SqString:Indexof(SqStr

27、ing &t)if(base0=0)|(t.base0=0) /为空return 0;int i=1,j=1 ;while(i=base0 & jt.base0)return i-t.base0;/扫描终了，匹配胜利elsereturn 0;/匹配失败3.3 3.3 串的方式匹配算法串的方式匹配算法3.3 3.3 串的方式匹配算法串的方式匹配算法限于篇幅，不再分析图3-13所示的串在后续阶段的匹配过程，可按KMP算法的思想继续推导。【算法3-9】3.4 3.4 文本编辑文本编辑3.4.1 3.4.1 问题描画与算法分析问题描画与算法分析文本编辑是指利用计算机进展编辑任务，修文本编辑是指利用计算

28、机进展编辑任务，修正字符数据的方式或格式，包括串的查找、正字符数据的方式或格式，包括串的查找、插入、删除等根本操作。插入、删除等根本操作。在进展文本编辑时，我们把整个文本看成是在进展文本编辑时，我们把整个文本看成是一个字符串，称为文本串，为了便于处置，一个字符串，称为文本串，为了便于处置，进一步地将文本串拆分成假设干子串，即页进一步地将文本串拆分成假设干子串，即页是文本串的子串，行又是页的子串。是文本串的子串，行又是页的子串。3.4 3.4 文本编辑文本编辑例如有以下一段英文： Night-Song in the JungleNow Rann the Kite brings home the

29、nightThat Mang the Bat sets freeThe herds are shut in barn and hutFor loosed till dawn are we把这首小诗看成是一个文本串，输入到内存后如图3-14所示。3.4 3.4 文本编辑文本编辑3.4 3.4 文本编辑文本编辑其相应的行表如表3-1所示，每一个行表项包含行号、该行的起始地址、长度。3.4 3.4 文本编辑文本编辑为实现文本编辑问题的求解，我们定义一个文本编辑类Editer如下其中串的存储类型采用3.2.1节的顺序串SqString：#define MAX 50typedef struct Text

30、_Row_Table/行表元素构造定义int iRow;SqString *iStartAddress;int iLength;Text_Row_Table;class Editer/文本编辑类的定义Text_Row_Table RTableMAX;/行表int Row_Count;/行数3.4 3.4 文本编辑文本编辑public:Editer()Row_Count=0;void InputText();/“输入文本处置函数void SearchText();/“查找文本处置函数/其他功能，略;3.4 3.4 文本编辑文本编辑3.4.2 3.4.2 算法实现算法实现1. 1. 输入文本输入文本由于各行的文本子串以行表项为标识，因此由于各行的文本子串以行表项为标识，因此输入阶段的处置，主要完成的就是每输入一输入阶段的处置，主要完成的就是每输入一行文本子串就为其建立一个行表项，记录行行文本子串就为其建立一个行表项，记录行号、起始地址与行内串长度。如算法号、起始地址与行内串长度。如算法3-103-10所所示。示。3.4 3.4 文本编辑文本编辑【算法3-10】void Editer:InputText()char in_strMAX;while(cin.getline(in_str,MAX,n)&in_str0!=)/商定以n为换