《VC编程教程 第4章 串.ppt》由会员分享，可在线阅读，更多相关《VC编程教程 第4章 串.ppt（44页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第4章 串本章主要介绍下列内容：l 串的定义、存储结构和基本运算退出退出本章学习要求掌握：串的基本概念和基本运算。掌握：串的顺序存储结构以及定长串的基本运算。了解：串的简单的模式匹配以及KMP模式匹配算法。了解：串的堆存储结构和基于堆结构的基本运算。掌握：串的链式存储结构表示。了解：串在文本编辑中处理方法。4.1 串的定义及其基本运算4.2 串的定长顺序存储及基本运算4.3 串的堆存储结构4.1.1串的定义v定义：串(string)是一种在数据元素的组成上具有一定约束条件的线性表，即要求组成线性表的所有数据元素都是字符，所以，人们经常又这样定义串：串是一个有穷字符序列，一般记为:4.1 串的定
2、义及其基本运算s=a1 a2 a3an说明:1)其中s是串名，用双引号括起来的字符序列是串的值。2)ai(1=i1.子串:字符串中任意个连续的字符构成的序列;母串:包含该子串的字符串;两串相等:两个字符串的长度相等且各对应位置上的字符都相同.字符的位置：从1开始子串的位置：该子串第一个字符的位置 例如，有下列几个串a，b，c，d，e，f：a=“Welcome to Beijing”b=“Welcome”c=“Bei”d=“welcometo”e=“Welcome”f=“welcome”4.1.2 串的基本运算1.求串的长度StrLength(s)；2.串赋值StrAssign(s1,s2);3
3、.两个串的连接StrConcat(s1,s2,s)或StrConcat(s1,s2)4.求某串的子串SubStr(s,i,len)；5.串比较StrCmp(s1,s2)；6.子串定位StrIndex(s,t);7.插入子串StrInsert(s,i,t)；8.删除子串StrDelete(s,i,len)；9.置换StrRep(s,t,r)。4.2 串的存储结构 1.顺序存储结构 串的顺序存储结构与线性表的顺序存储类似，用一组连续的存储单元依次存储串中的字符序列。(1)第一种是事先定义字符串的最大长度，字符串存储在一个定长的存储区中。类型定义如下所示：#define MAXSIZE 256typ
4、edef struct char dataMAXSIZE;int curlen;SeqString;第一种：abefi0256s.curlencdgh13478s.dataMAXSIZE-1 (2)第二种是在串尾存储一个不会在串中出现的特殊字符作为串的终结符，以此表示串的结尾。比如C语言中处理定长串的方法就是这样的，它是用0来表示串的结束。这种存储方法不能直接得到串的长度，是用判断当前字符是否是0来确定串是否结束，从而求得串的长度。第二种：#define MAXSIZE 256char sMAXSIZE;abefi0256cdgh1347809MAXSIZE-1 (3)设定长串存储空间：cha
5、r sMAXSIZE+1;用s0存放串的实际长度，串值存放在s1sMAXSIZE，字符的序号和存储位置一致，应用更为方便。第三种：#define MAXSIZE 256char sMAXSIZE+1;abefi0256cdgh1347899MAXSIZE 2、定长串的基本运算本小节主要讨论定长串联接、求子串、串比较算法，顺序串的插入和删除等运算基本与顺序表相同，在此不在赘述。设串结束用0来标识。（1）求串长int strLength(char s)int i=0;while(si!=0)i+;return (i);（2）串联接把两个串s1和s2首尾连接成一个新串s，即：sMAXSIZE-1)r
6、eturn 0;/*s长度不够*/j=0;while(s1j!=0)si=s1j;i+;j+;j=0;while(s2j!=0)si=s2j;i+;j+;si=0;return 1;（3）求子串int StrSub(char*t,char*s,int i,int len)/*用t返回串s中第个i字符开始的长度为len 的子串1i串长*/int slen;slen=StrLength(s);if(islen|lenslen-i+1)printf(参数不对);return 0;for(j=0;jc0表示）开始比较。在最坏的情况下，每趟比较都在最后出现不等，最多比较nm1趟，总比较次数为m*(nm1
7、)，由于在一般情况下mn，所以算法运行时间为O(m*n)。2.改进后的模式匹配算法（KMP算法）s：a c a b a a b a a b c a c a a b c t：a b a a b c a ci=8j=6 s：a c a b a a b a a b c a c a a b c t：a b a a b c a ci=8k=3（1）KMP算法思想：i不回溯，j也不是回溯到1，而是回溯到k，也就是模式t向右滑动到某个位置k。（2）k位置的确定next函数用next函数来确定k的值，即k=next（j）；j1 2 3 4 5 6 7 8模式串a b a a b c a cnext（j）例4-
8、1求模式串“abaabcac”的next函数值 next(j)=maxk|1=kj且”t1t2tk-1”=”tj-k+1tj-k+2tj-1”1 其他情况0 j=101122312 练习：求下列模式串的next函数值 AAAB AABAACAABABA ABRACADABRA ASSTACASTRA 例：主串S:“aabcbabcaabcaababc”模式串t:“abcaababc”j1 2 3 4 5 6 7 8 9模式串a b c a a b a b cnextj 0 11122323 s：a a b c b a b c a a b c a a b a b c t：a b c a a b
9、a b c i=1j=1i=2j=2 s：a a b c b a b c a a b c a a b a b c t：a b c a a b a b c i=2j=1i=3j=2i=4j=3i=5j=4j1 2 3 4 5 6 7 8 9模式串a b c a a b a b cnextj 0 11122323 s：a a b c b a b c a a b c a a b a b c t：a b c a a b a b c i=5j=1 s：a a b c b a b c a a b c a a b a b c t：a b c a a b a b c i=6j=1i=7j=2i=8j=3i=9
10、j=4i=10j=5i=11j=6i=12j=7 s：a a b c b a b c a a b c a a b a b c t：a b c a a b a b c i=12j=3i=13j=4i=14j=5i=15j=6i=16j=7i=17j=8i=18j=9i=19j=10（3）KMP算法实现循环条件？什么时候回溯？回溯时i、j如何计算？如何判断匹配是否成功？匹配成功时，返回的起始位置如何计算？见P102的算法4.5（4）如何求next函数next1=0;设nexti-1=k，如何求nexti？j1 2 3 4 5 6 7 8 9模式串a b c a b c d b cnextj0 i=
11、2j=1k=nextj=01next(j)=maxk|1=kj且”t1t2tk-1”=”tj-k+1tj-k+2tj-1”1 其他情况0 j=1第一种情况：k=0nexti=k+1；第二种情况:tk=tjj1 2 3 4 5 6 7 8 9模式串a b c a b c d b cnextj0 1 1 1 23i=6j=5nexti=k+1；k=2第三种情况：tk tj j1 2 3 4 5 6 7 8 9模式串a b a a b a b b a nextj0 1 1 2 2 3 4i=8j=73（1）回溯k=nextk直至tj=tkj1 2 3 4 5 6 7 8 9模式串a b c a b
12、c d b cnextj0 1 1 1 2 3 4i=8j=71（2）回溯k=nextk直至k=0 k=4k=2k=4k=1k=0 nexti=k+1；nexti=k+1；j1 2 3 4 5 6 7 8 9模式串a b c a a b a b cnextj 0 i=2：j=1，k=next 1=0next i=k+1=1 i=3：j=2，k=next 2=1，tk tj，k回溯111k=next 1=0next i=k+1=1 i=4：j=3，k=next 3=1，tk tj，k回溯k=next 1=0next 4=k+1=1求nexti：i=1next i=0i=5：j=4，k=next
13、4=1，tk=tjnext i=k+1=2 2 i=6：j=5，k=next 5=2，tk tj，k回溯23k=next 2=1，tk=tjnext i=k+1=2 i=7：j=6，k=next 6=2，tk=tjnext i=k+1=3 j1 2 3 4 5 6 7 8 9模式串a b c a a b a b cnextj 01112i=8：j=7，k=next 7=3，tk tj，k回溯k=next 3=1，tk=tjnext i=k+1=2 2i=9：j=8，k=next 8=2，tk=tjnext i=k+1=3 3算法实现：void GetNext(char t,int next)i
14、nt i=2,j,k;next1=0;j=i-1；k=nextj；while(i=t0)if(k=0|tk=tj)nexti=k+1;i+;j=i-1；k=nextj;else k=nextk;/*k回溯*/理解P104算法4.6 作业：根据NEXT算法求下列模式串的next函数值（写出过程）AAAB ABRACADABRA ASSTACASTRA 练习：根据NEXT算法求下列模式串的next函数值（写出过程）AABAACAABABA 4.3 串的堆存储结构4.3.1 串名的存储映像 1.带串长度的索引表typedef struct char nameMAXNAME;int length;ch
15、ar *stradr;LNode;2.带末尾指针的索引表typedef struct char nameMAXNAME;char *stradr，*enadr;ENode;3.带特征位的索引表typedef struct char nameMAXNAME;int tag;union char *stradr，char value4;uval;TNode;4.3.2 堆存储结构基本思想：v 在内存中开辟能存储足够多的串、地址连续的存储空间作为应用程序中所有串的可利用存储空间，称为堆空间。（未分配区域）（已分配区域）char storeSMAX+1;int free;typedef structi
16、nt length;int stradr;Hstring;5.文本编辑文本编辑串操作应用串操作应用 串的应用十分广泛，例如文本编辑程序、关键字检索程序等。下面用一串的应用十分广泛，例如文本编辑程序、关键字检索程序等。下面用一个实例说明字符串的存储及插入、删除等基本操作在文本编辑中的实际应用。个实例说明字符串的存储及插入、删除等基本操作在文本编辑中的实际应用。文本编辑程序是存储在计算机内的一个面向用户的系统服务程序，它广文本编辑程序是存储在计算机内的一个面向用户的系统服务程序，它广泛应用于源程序的输入和修改，甚至用于报刊和书籍的编辑排版以及办公室泛应用于源程序的输入和修改，甚至用于报刊和书籍的编
17、辑排版以及办公室的公文书信的起草和润色。这里，一个源程序或一篇文稿都可看成是有限字的公文书信的起草和润色。这里，一个源程序或一篇文稿都可看成是有限字符序列，我们称之为文本。文本编辑的实质就是利用串的基本操作，完成对符序列，我们称之为文本。文本编辑的实质就是利用串的基本操作，完成对文本的添加、删除和修改等操作，其实也就是修改字符数据的形式和格式。文本的添加、删除和修改等操作，其实也就是修改字符数据的形式和格式。虽然各种文本编辑程序的功能强弱不同，但是其基本操作是一致的，一般都虽然各种文本编辑程序的功能强弱不同，但是其基本操作是一致的，一般都包括串的查找、插入和删除等基本运算。因此，对用户来说若能
18、利用计算机包括串的查找、插入和删除等基本运算。因此，对用户来说若能利用计算机系统提供的文本编辑程序，则可以方便地完成各种修改工作。系统提供的文本编辑程序，则可以方便地完成各种修改工作。为了编辑的方便，用户可以利用换页符和换行符把文本划分为若干页，为了编辑的方便，用户可以利用换页符和换行符把文本划分为若干页，每页有若干行（当然，也可不分页而把文本直接划分成若干行）。每页有若干行（当然，也可不分页而把文本直接划分成若干行）。例如，有下面一段源程序：例如，有下面一段源程序：main()int a,b,c;scanf(“%d,%d”,&a,&b);c=(a+b)/2;printf(“%d”,c);我们
19、可以把这个程序看成是一个文本串，每行看成是一个子串，按顺序的方我们可以把这个程序看成是一个文本串，每行看成是一个子串，按顺序的方式存入计算机内，如图式存入计算机内，如图4.10所示。图中所示。图中“”为换行符。为换行符。201 /假定假定201为起始地址为起始地址ma in()in t a,b,c;s c a n f(“%d,%d“,&a&b);c=(a+b)/2;p r in t f(“%d“,c);图图4.10 文本格式示例文本格式示例在输入程序同时，由文本编辑程序自动建立一个页表和行表，即建立各子在输入程序同时，由文本编辑程序自动建立一个页表和行表，即建立各子串的存储映象。页表的每一项给
20、出了页号和该页的起始行号。而行表的每一串的存储映象。页表的每一项给出了页号和该页的起始行号。而行表的每一项则指示每一行的行号、起始地址和该行子串的长度。每输入一行，看作加项则指示每一行的行号、起始地址和该行子串的长度。每输入一行，看作加入一个新的字符串到文本中，串值存放于文本工作区。而行号、串值的存储入一个新的字符串到文本中，串值存放于文本工作区。而行号、串值的存储起始地址和该串的长度登记到行表中。由于使用了行表起始地址和该串的长度登记到行表中。由于使用了行表,新的一行可存放到新的一行可存放到文本工作区的任何一个自由区中。行表中的每一行信息，必须按行号递增的文本工作区的任何一个自由区中。行表中
21、的每一行信息，必须按行号递增的顺序排列，如图顺序排列，如图4.11所示。所示。行 号 起始地址 长 度 100 201 7 101 208 14 102 222 21 103 243 11 104 254 16 105 270 2 图图4.11 图图4.10所示文本串的行表及其信息排列所示文本串的行表及其信息排列下面我们来简单讨论文本的编辑。下面我们来简单讨论文本的编辑。1插插 入入插入一行时，一方面需要在文本的末尾的空闲工作区写入该行的串值，另插入一行时，一方面需要在文本的末尾的空闲工作区写入该行的串值，另一方面要在行表中建立该行的信息。为了维持行表由小到大的顺序，保证能一方面要在行表中建立
22、该行的信息。为了维持行表由小到大的顺序，保证能迅速地查找行号，一般要移动原有的有关信息迅速地查找行号，一般要移动原有的有关信息,以便插入新的行号。例如，若以便插入新的行号。例如，若插入行为插入行为99，则行表从，则行表从100开始的各行信息都必须往下平移一行。开始的各行信息都必须往下平移一行。2删删 除除 删除一行，只要在行表中删除该行的行号就等于从文本中抹去了这一行，删除一行，只要在行表中删除该行的行号就等于从文本中抹去了这一行，因为对文本的访问是通过行表实现的。比如，要删除上表中的第因为对文本的访问是通过行表实现的。比如，要删除上表中的第103行，则行，则行表中从行表中从103行起后面的各
23、行都应往上平移一行，以覆盖掉行号行起后面的各行都应往上平移一行，以覆盖掉行号103及其相应及其相应的信息。的信息。3修修 改改 修改文本时，应指明修改哪一行和哪些字符。编辑程序通过行表查到要修改文本时，应指明修改哪一行和哪些字符。编辑程序通过行表查到要修改行的起始地址，从而在文本存贮区检索到待修改的字符的位置，然后进修改行的起始地址，从而在文本存贮区检索到待修改的字符的位置，然后进行修改，通常有三种可能的情况：一是新的字符与原有的字符个数相等，这行修改，通常有三种可能的情况：一是新的字符与原有的字符个数相等，这时不必移动字符串，只要更改文本中的字符即可；二是新的字符个数比原有时不必移动字符串，
24、只要更改文本中的字符即可；二是新的字符个数比原有的要少，这时也不需移动字符串，只要修改行表中的长度值和文本中的字符的要少，这时也不需移动字符串，只要修改行表中的长度值和文本中的字符即可；三是新串的字符个数比原有的要多，这时应先检查本行与下一行之间即可；三是新串的字符个数比原有的要多，这时应先检查本行与下一行之间是否有足够大的空间（可能中间有一行或若干行已经删除了，但删除时并没是否有足够大的空间（可能中间有一行或若干行已经删除了，但删除时并没有回收这些空间），若有，则扩充此行，修改行表中的长度值和文本中的字有回收这些空间），若有，则扩充此行，修改行表中的长度值和文本中的字符；若无，则需要重新分配
25、空间，并修改行表中的起始地址和长度值。符；若无，则需要重新分配空间，并修改行表中的起始地址和长度值。以上简单概述了文本编辑程序中的基本操作，大家可以看到，文本编辑程以上简单概述了文本编辑程序中的基本操作，大家可以看到，文本编辑程序广泛地应用了串基本的运算。其具体的算法，读者可在学习本章之后自行序广泛地应用了串基本的运算。其具体的算法，读者可在学习本章之后自行编写。编写。小 结 串是特殊的线性表，是由字符作元素组成的。它和线性表一样有顺序存储和链式存储两种方式。串作为一种抽象数据类型，有它自己的操作，在对串处理时，要抓住它的特殊要求。模式匹配是一个比较复杂的串操作，是子串在主串中的定位操作。简单的模式匹配算法比较直观，易于理解；但无回溯的模式匹配算法的技巧性很强，读懂它需要费一定的时间，不过一旦真正弄懂了这个算法，将会极大地增强你的学习兴趣。