《数据结构：第3章串与文本编辑.ppt》由会员分享，可在线阅读，更多相关《数据结构：第3章串与文本编辑.ppt（71页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第3 3章章 串与文本编辑串与文本编辑3.1 3.1 串的类型定义串的类型定义3.2 3.2 串的存储表示串的存储表示3.3 3.3 串的模式匹配算法串的模式匹配算法3.4 3.4 文本编辑文本编辑3.5 3.5 小结小结 0 0数据结构与算法3.1 3.1 串的类型定义串的类型定义1.1.串的相关术语串的相关术语串串是由零个或多个字符组成的有限序列，记为：s=s1s2sn。其中s是串名；双引号内的字符序列s1s2sn是串值；n(n=0)表示串的长度。1 1数据结构与算法3.1 3.1 串的类型定义串的类型定义例如：s1=“data structure”/串，长度为14 串长度为零的串称为空
2、串空串。例如：s=“”/空串，长度为0 组成串的字符均为空格的串称为空格串空格串或空白串。例如：s=“”/空格串，长度为42 2数据结构与算法3.1 3.1 串的类型定义串的类型定义一个串中任意个连续字符组成的子序列称为该串的子串子串。空串是任何串的子串空串是任何串的子串。例如：s1=“data structure”s2=“data”/s2是s1的子串 s3=“structure”/s3是s1的子串 s4=“datastructure”/s4不是s1的子串包含子串的串称为主串主串。上例中s1为主串。3 3数据结构与算法3.1 3.1 串的类型定义串的类型定义子串的序号子串的序号是该子串的第一个
3、字符在主串中的序号。在上例子串s2在s1中的序号为1，s3在s1中的序号为6。S4不是s1的子串，也可以说，s4在s1中的序号为0。当且仅当串的长度相等并且对应位置上的字符都相同时，称这两个字符串是相等的字符串是相等的。例如：s1=“data structure”s2=“data structure”s3=“datastructure”/s1与s2相等，s3与s1和s2均不相等 4 4数据结构与算法3.1 3.1 串的类型定义串的类型定义按照串中字符的次序，逐一比较两个字符串中字符的大小，以确定两个串的大小关系的操作，称为串的比较串的比较。例如：s5=data，s6=DATA，则有s5 s6的
4、比较结果为1，s5=0Structure:S=|ai-1,ai D,i=2,3,noPerations:ConstructString()/操作结果：创建一个空的串sDestructString()/操作条件：已有串s/操作结果：销毁当前串sStringLen()/操作条件：已有串s/操作结果：得到当前串s的实际长度9 9数据结构与算法3.1 3.1 串的类型定义串的类型定义StringCpy(t)/操作条件：已有串s和参数串t/操作结果：将t复制到当前串s中OutputString()/操作条件：已有串s/操作结果：输出当前串sSubString(pos,len,&t)/操作条件：已有串s/
5、操作结果：取串s中从第pos个字符开始的，长度为len的子串，由t返回DelSubString(pos,len,&t)/操作条件：已有串s和一个参数串t/操作结果：删除当前串从第pos个字符开始，长度为len的子串/并由t返回被删除的子串 1010数据结构与算法3.1 3.1 串的类型定义串的类型定义InsertSubString(pos,t)/操作条件：已有串s和参数串t/操作结果：将t插入到当前串第pos个位置前ConnectString(t)/操作条件：已有串s和参数串t/操作结果：将t连接到当前串s之后ClearString()/操作条件：已有串s/操作结果：将当前串s清空Replac
6、eString(pos,len,t)/操作条件：已有串s和参数串t/操作结果：将当前串s中第pos个字符开始的长度为len的子串，替换为tADT String;1111数据结构与算法3.2 3.2 串的存储表示串的存储表示3.2.1 3.2.1 串的顺序存储串的顺序存储将串所占用空间的大小称为串容量，实际存在的元素个数称为串长，如图3-1所示。1212数据结构与算法3.2 3.2 串的存储表示串的存储表示为了表示串的结束，可在串内容最后一个有效字符后，再多开辟一个存储空间，存放结束标志0（C/C+语言中的字符串就采用这种方法），如图3-2所示。1313数据结构与算法3.2 3.2 串的存储表示
7、串的存储表示借助于顺序存储时数组的0号下标存储串长，即有效地利用了空间，又使得串中字符的位序与其存放位置（下标）一致，如图3-3所示。1414数据结构与算法3.2 3.2 串的存储表示串的存储表示定义顺序串：#define MAX 100class SqStringpublic:char*base;/存储串的字符数组/base0表示串的实际长度,不另设结束标志int maxlen;/表示串的最大长度public:SqString();/构造函数SqString(char*s);/构造函数SqString(SqString&t);/构造函数SqString();/析构函数1515数据结构与算法3
8、.2 3.2 串的存储表示串的存储表示bool InsertString(int pos,SqString&t);/在串的指定位置pos插入一个子串tbool DelSubString(int pos,int len,SqString&t);/删除当前串的子串,并由t返回void OutputString();/输出串中所有字符void ConnectString(SqString&t);/在当前串尾连接串tbool SubString(int pos,int len,SqString&t);/求当前串从pos开始长度为len的子串int Indexof(SqString&t);/求模式串t在
9、当前串中第一次出现的位置int Indexof_KMP(SqString&t);/KMP法求模式串t在当前串中第一次出现的位置void GetNext(int next);/KMP模式匹配算法辅助函数/其他操作;1616数据结构与算法3.2 3.2 串的存储表示串的存储表示顺序串的构造与析构顺序串的构造与析构 串的构造有三种方法，分别是构造空串、由基本类型的字符串构造一个新串以及使用串对象来构造串。下面给出三种方法构造串的实现过程。（1）构造空的顺序串。【算法3-1-1】SqString:SqString()maxlen=MAX;base=new charmaxlen+1;/0下标留作记录长度
10、base0=0;1717数据结构与算法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;1818数据结构与算法3.2 3.2 串的存储表示串的存储表示（3）使用串对象来构造串。【算法3-1-3】SqString:SqString(SqString&t)maxlen=t.maxlen;base=new charmaxlen+1;b
11、ase0=t.base0;for(int i=1;i=base0;i+)basei=t.basei;1919数据结构与算法3.2 3.2 串的存储表示串的存储表示（4）析构函数【算法3-1-4】SqString:SqString()delete base;2020数据结构与算法3.2 3.2 串的存储表示串的存储表示顺序串插入操作顺序串插入操作顺序串插入操作的功能是将一个指定的串插入到当前串中的指定位置之前，以s串和t串分别表示当前串和待插入串，则插入前后s串与t串的状态如图3-4（a）和图3-4（b）所示。2121数据结构与算法3.2 3.2 串的存储表示串的存储表示2222数据结构与算法3
12、.2 3.2 串的存储表示串的存储表示顺序串插入操作实现算法为：检查插入位置的合法性，即当插入位置posbase0，或base0+t.base0 maxlen（没有足够空间插入t）时，提示错误信息，终止程序；从pos指向的位置开始，一直到最后的字符，每个字符都要向后移动，移动的长度为t串的长度；插入t串，修改s的串长，操作成功，结束。2323数据结构与算法3.2 3.2 串的存储表示串的存储表示【算法3-2】bool SqString:InsertString(int pos,SqString&t)if(posbase0+1|pos-1+t.base0maxlen)cout插入失败=pos;i
13、-)basei+t.base0=basei;/元素后移2424数据结构与算法3.2 3.2 串的存储表示串的存储表示for(i=1;i=t.base0;i+)basepos-1+i=t.basei;/插入元素base0+=t.base0;return true;2525数据结构与算法3.2 3.2 串的存储表示串的存储表示顺序串删除操作顺序串删除操作顺序串删除操作的功能是删除s串中从第pos个位置开始的长度为len的子串。如图3-5所示。2626数据结构与算法3.2 3.2 串的存储表示串的存储表示2727数据结构与算法3.2 3.2 串的存储表示串的存储表示顺序串删除操作实现算法为：检查参数
14、的合法性，有两种不合法的操作条件：一是pos的值不在串s的长度范围内，即posbase0；二是从串s第pos个位置开始不存在长度为len的子串，即pos+len-1base0；将待删除的子串复制给t；在s中删除指定的子串，修改s的串长，操作成功，结束。2828数据结构与算法3.2 3.2 串的存储表示串的存储表示【算法3-3】bool SqString:DelSubString(int pos,int len,SqString&t)if(posbase0)|pos-1+lenbase0)cout删除失败endl;return false;elsefor(int i=pos;i=pos-1+le
15、n;i+)/删除的元素复制给tt.basei-pos+1=basei;t.base0=len;2929数据结构与算法3.2 3.2 串的存储表示串的存储表示for(i=pos+len;i=base0;i+)/元素前移basei-len=basei;base0-=len;return true;3030数据结构与算法3.2 3.2 串的存储表示串的存储表示输出顺序串操作输出顺序串操作顺序串输出操作的功能是将串中的字符全部输出。顺序串输出操作实现算法为：检查串时否为空串，若为空，输出空串信息；若串非空，则利用循环输出串的内容；操作成功，结束。3131数据结构与算法3.2 3.2 串的存储表示串的存
16、储表示【算法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;for(int i=1;i=t.base0;i+)basebase0+i=t.basei;base0+=t.base0;3535数据结构与算法3.2 3.2 串的存
17、储表示串的存储表示6.6.求子串（非空子串）求子串（非空子串）求子串的定义为将串s中的第pos个字符开始长度为len的子串，复制到串t中。如图3-7所示。3636数据结构与算法3.2 3.2 串的存储表示串的存储表示顺序串中求子串的实现算法为：检查参数的合法性，当posbase0，或lenbase0时，操作失败；将当前串从pos指向位置开始的长度为len的子串复制到串t中；操作成功，结束。3737数据结构与算法3.2 3.2 串的存储表示串的存储表示【算法3-6】bool SqString:SubString(int pos,int len,SqString&t)if(posbase0)|po
18、s-1+lenbase0)cout操作失败endl;return false;elsefor(int i=pos;i=len;i+)t.basei-pos+1=basei;t.base0=len;return true;3838数据结构与算法3.2 3.2 串的存储表示串的存储表示3.2.2 3.2.2 串的链式存储串的链式存储串的顺序存储方式节约了系统开销，但是如果需要经常对串执行插入、删除子串等操作，就需要频繁移动串中的字符，因此，我们引入串的另一种存储方式链式存储，又称动态存储。这样就可以避免频繁的插入、删除操作带来的效率低下等问题。3939数据结构与算法3.2 3.2 串的存储表示串的
19、存储表示在链式存储结构下，存储空间被分成一系列大小相同的结点，每个结点包含两个域：字符域data和指针域next。其中，字符域用来存放字符，指针域则用来存放指向下一个结点的指针。一个串可用一个单链表来存储。链表中的结点数目等于串的长度。例如，一个字符串s=“ABCDEFGHI”，那么它的单链表存储方式如图3-8所示。4040数据结构与算法3.2 3.2 串的存储表示串的存储表示4141数据结构与算法为了提高串的链式存储的存储密度，节省空间，可以将链串的结点大小设置为4。那么串s=“ABCDEFGHI”在结点大小为4的链串存储结构如图3-9所示。3.2 3.2 串的存储表示串的存储表示链串的存储
20、结构可定义如下：#define N 4struct LStringNodechar dataN;struct LStringNode*next;class LinkStringLStringNode*head;int length;4242数据结构与算法3.2 3.2 串的存储表示串的存储表示public:LinkString();LinkString(char*t);LinkString(LinkString&t);LinkString();bool InsertString(int pos,LinkString&t);bool DelSubString(int pos,int len,Li
21、nkString&t);void OutputString();/其他操作;4343数据结构与算法3.2 3.2 串的存储表示串的存储表示链串的插入操作与单链表的插入过程相似，但又有明显的区别，单链表中每一个结点都是一个单独的元素，而块链式的串中每一块有若干个独立的元素，如图3-10（a）所示，当插入位置不是刚好位于每一块的起始处时，插入子串的处理相对要复杂。为尽量减少插入时字符的移动，可采用牺牲一定存储空间的办法，将插入点所在块的串拆分成两个块，无效字符的位置用“#”填充，如图3-10（b）所示，这样，待插入的串就可以直接进行链接。4444数据结构与算法3.2 3.2 串的存储表示串的存储表
22、示4545数据结构与算法3.2 3.2 串的存储表示串的存储表示链串插入操作实现算法为：判断插入位置是否有效，无效立即结束；否则继续；找到插入位置，以指针p指向pos所在块或其前一块；若pos对块长取余不为0，p指向pos所在块，生成新结点，对该块进行拆分；否则，p指向pos所在块的前一块；将t串链接到s串中；操作成功，结束。【算法3-7】4646数据结构与算法3.3 3.3 串的模式匹配算法串的模式匹配算法设s和t是给定的两个串，其长度分别为n和m，且有nm，在串s中找到等于子串t的过程称为模式匹配模式匹配，其中，串s称为主串，t称为模式。如果在s中找到等于t的子串，则称匹配成功，函数返回t
23、在s中的首次出现的存储位置(或序号)，否则匹配失败，返回0。4747数据结构与算法3.3 3.3 串的模式匹配算法串的模式匹配算法Brute-Force算法简称为BF算法，亦称简单匹配算法，设主串s=s1sn，模式串t=t1tm，其基本思想是：1.从主串s的第一个字符s1开始和模式串t=t1tm中的第一个字符t1比较；2.若相等，则继续逐个比较后续字符，s2和t2；3.若不相等，从主串s的第二个字符s2开始重新与模式串t的第一个字符t1进行比较。4.重复上述过程，如果在主串s中找到一个与串t相同的子串，则匹配成功，返回模式串t在主串s主的序号；如果比较完主串s的所有字符序列，没有和模式串t相等
24、的子串，则匹配失败返回0。4848数据结构与算法3.3 3.3 串的模式匹配算法串的模式匹配算法设主串s=“ababcabcacba”模式串t=“abcac”。s的长度为n(n=12)，t的长度为m（m=5）。指针i、j分别为主串s、模式串t当前比较字符的下标。模式匹配的过程如图3-11所示。4949数据结构与算法3.3 3.3 串的模式匹配算法串的模式匹配算法5050数据结构与算法3.3 3.3 串的模式匹配算法串的模式匹配算法5151数据结构与算法3.3 3.3 串的模式匹配算法串的模式匹配算法上述匹配过程中，可以得出以下结果：（1）若在前k-1(k1)次比较过程中未匹配成功，则第k次比较
25、是从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所示。5252数据结构与算法3.3 3.3 串的模式匹配算法串的模式匹配算法5353数据结构与算法3.3 3.3 串的模式匹配算法串的模式匹配算法【算法3-8】int SqString:Indexof(SqString&t)if(base0=0)|(t.base0=0)/为空ret
26、urn 0;int i=1,j=1;while(i=base0&jt.base0)return i-t.base0;/扫描完毕，匹配成功elsereturn 0;/匹配失败5555数据结构与算法3.3 3.3 串的模式匹配算法串的模式匹配算法5656数据结构与算法3.3 3.3 串的模式匹配算法串的模式匹配算法限于篇幅，不再分析图3-13所示的串在后续阶段的匹配过程，可按KMP算法的思想继续推导。【算法3-9】5757数据结构与算法3.4 3.4 文本编辑文本编辑3.4.1 3.4.1 问题描述与算法分析问题描述与算法分析文本编辑是指利用计算机进行编辑工作，修改字符数据的形式或格式，包括串的查
27、找、插入、删除等基本操作。在进行文本编辑时，我们把整个文本看成是一个字符串，称为文本串，为了便于处理，进一步地将文本串拆分成若干子串，即页是文本串的子串，行又是页的子串。5858数据结构与算法3.4 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 till dawn are we把这首小诗看成是一个文本串，输入到内存后如图3-14所
28、示。5959数据结构与算法3.4 3.4 文本编辑文本编辑6060数据结构与算法3.4 3.4 文本编辑文本编辑其相应的行表如表3-1所示，每一个行表项包含行号、该行的起始地址、长度。6161数据结构与算法3.4 3.4 文本编辑文本编辑为实现文本编辑问题的求解，我们定义一个文本编辑类Editer如下（其中串的存储类型采用3.2.1节的顺序串SqString）：#define MAX 50typedef struct Text_Row_Table/行表元素结构定义int iRow;SqString*iStartAddress;int iLength;Text_Row_Table;class E
29、diter/文本编辑类的定义Text_Row_Table RTableMAX;/行表int Row_Count;/行数6262数据结构与算法3.4 3.4 文本编辑文本编辑public:Editer()Row_Count=0;void InputText();/“输入文本”处理函数void SearchText();/“查找文本”处理函数/其他功能，略;6363数据结构与算法3.4 3.4 文本编辑文本编辑3.4.2 3.4.2 算法实现算法实现1.1.输入文本输入文本由于各行的文本子串以行表项为标识，因此输入阶段的处理，主要完成的就是每输入一行文本子串就为其建立一个行表项，记录行号、起始地址
30、与行内串长度。如算法3-10所示。6464数据结构与算法3.4 3.4 文本编辑文本编辑【算法3-10】void Editer:InputText()char in_strMAX;while(cin.getline(in_str,MAX,n)&in_str0!=)/约定以n为换行，为文本串输入完毕SqString*pstr=new SqString(in_str);RTableRow_Count.iRow=Row_Count+1;RTableRow_Count.iLength=pstr-base0;RTableRow_Count.iStartAddress=pstr;Row_Count+;65
31、65数据结构与算法3.4 3.4 文本编辑文本编辑2.2.查找文本查找文本【算法3-11】void Editer:SearchText()cout请输入要查找的文本串str;SqString s(str);for(int i=0,j;iIndexof_KMP(s)6666数据结构与算法3.4 3.4 文本编辑文本编辑cout找到了，行号RTablei.iRow 位置j=Row_Count)cout未找到！endl;6767数据结构与算法3.4 3.4 文本编辑文本编辑3.3.主程序与测试主程序与测试#include iostreamusing namespace std;void main()
32、Editer t1;t1.InputText();t1.SearchText();6868数据结构与算法运行结果：Night-Song in the JungleNow Rann the Kite brings home the nightThat Mang the Bat sets free请输入要查找的文本串Kite brings找到了，行号2 位置146969数据结构与算法3.5 3.5 小结小结串是一种数据类型受到限制的特殊线性表，规定表中的每一个元素类型只能为字符型。串虽然是线性表，但又有它特殊的地方，即表中元素为单个字符，但串结构通常不是单个处理某一个字符元素，通常是整串进行讨论。串的存储方式与线性表类似，也具有顺序存储和链式存储两种方式。串的插入、删除等操作较线性表上的操作要复杂一些。在顺序串中给出了串的构造、插入、删除、串的输出和串的连接等算法。在链式串中给出了串的插入、删除等算法。7070数据结构与算法