《数据结构中的串.pptx》由会员分享，可在线阅读，更多相关《数据结构中的串.pptx（40页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第4 4章 串4.1 串的定义和操作4.2 串的表示和实现定长顺序存储表示堆分配存储表示块链存储表示4.3 正文模式匹配*4.4 正文编辑-串操作应用举例44第1页/共40页第4 4章 串字符串数据是计算机非数值处理的主要对象之一。在早期字符串字符串作为输入输出的常量出现，现已发展成为字符串类型，可以进行一系列的操作。字符串一般简称为串。在汇编和编译程序中，源程序是字符串数据。在事务处理程序中，顾客的姓名和地址及货物的名称、产地等也是字符串。此外，如信息检索系统、文字编辑程序、自然语言翻译系统等都是以字符串为处理对象。然而，目前的计算机硬件结构主要是面向数值计算的需要，基本上没有提供处理字符串
2、数据操作的指令，需要用软件来实现字符串类型。由于各种应用具有不同的特点，要有效的实现字处理，必须根据具体情况使用合适的存储结构。第2页/共40页4.1 串的定义和操作串(String),或称字符串是由零个或多个字符组成的有限序列。一般记为：S=“a0a1an-1”(n 0)其中，S是串的名称，用双号括起来的字符序列是串的值；ai(0in-1)可以是字母、数字或其它字符（字符的序号从0开始，与C、C+、JAVA等语言的习惯一致）；串中字符的数目n称为串的长度。零个字符的串称为空串(null string)，它的长度为零。串中任意个连续的字符组成的子序列称为该串的子串。包含子串的的串相应地称为主串
3、。通常称字符在序列中的序列号为该字符在串中的位置。子串在主串中的位置则以子串第0个字符在主串的位置来表示。第3页/共40页4.1 串的定义和操作例如：下面a，b，c，d都是串a=“BEI”长度为3b=“JING”长度为4c=“BEIJING”长度为7d=“BEI JING”长度为8串的逻辑结构和线性表极为相似，区别仅仅在于串的数据对象约束为字符集。但是串的基本操作和线性表有很大的差别。在线性表的操作中大多数以“单个元素”为操作对象，而在串的操作中大多数以“串的整体”为操作对象。第4页/共40页4.1 串的定义和操作两个串之间可以进行比较。称两个串相等，当且仅当这两个串的值相等，包括两个串的长度
4、相等，并且各个对应位置的字符都相等。当两个串不相等时，可按“字典顺序”分大小。令s=“s0s1sm-1”(m0)t=“t0t1tn-1”(n0)假设，两者最大有前k个子序列相等（最大相等前缀子串），s和t的大小由sk和tk的大小来决定。在C语言中字符的大小按ASCII码的大小为准第5页/共40页4.1 串的定义和操作串值必须用一对双引号括起来，但双引号不属于串，它的作用只是为了避免与变量或常量混淆。例如：x=“123”;其中，X是一个串变量名，赋给它的值是字符序列123,而不是整数123。之间可以进行比较。aString=“aString”;左边的aString是一个串变量名，而右边的字符序列
5、aString是赋给它的值在各种应用中，空格通常是串的字符集合中的一个元素，可以出现在其它字符之间，由一个或多个空格组成的串称为空格串“”；和“”；都是空格串。为了清楚起见我们以后用来表示空串第6页/共40页串的基本操作（1）ADT String 数据对象:D=ai|aiCharacterSet,i=1,2,.,n,n0 数据关系:R1=|ai-1,aiD,i=2,.,n 基本操作：StrAssing(&T,chars):chars是字符串常量，生成一个值等于chars的串T StrCopy(&T,S):串S存在，由串S复制得串T StrEmpty(S):如果串S为空，返回TRUE，否则返回F
6、ALSE StrCompare(S,T):若ST 返回0;若S=T 返回=0;若ST 返回=0)n=StrLength(S);m=StrLength(T);i=pos;while(i=n-m)SubString(sub,S,i,m);/返回S中从i起长度为m的子串 if(SubCompare(sub,T)!=0)i+;else return i;/while /ifreturn-1;/Index第10页/共40页4.2 串的表示和实现如果在程序设计语言中，串只是作为输入输出的常量出现，则只需存储这个串常量值，即字符序列即可。但在多数非数值处理情况的程序中，串也以变量的形式出现。因此需要根据串的
7、操作的特点，合理地选择和设计串值的存储结构及其维护方式。1 定长顺序存储表示2 堆分配存储表示3 块链存储表示第11页/共40页串的顺序存储类似于线性表的顺序存储表示方法，可用一组地址连续的存储单元存储串值的字符序列。例如，在C语言中，字符串的一种处理方法就是将字符串作为字符数组来处理。假设：char str10;/固定长为10的存储区在C语言中，字符串的结束标志为0，同时我们应注意到0也占一个字符的空间。第12页/共40页串的顺序存储void Concat_Sq(char S1,char S2,char T)/用T返回S1和S2联接而成的新串 k=0;j=0;while(S1j!=0)Tk+
8、=S1j+;j=0;while(S2j!=0)Tk+=S2j+;Tk=0;/Concat_Sq 算法4.2第13页/共40页串的顺序存储void SubString_Sq(char Sub,char S,int pos,int len)/用Sub返回串S的第pos个字符起长度为len的字符,其中,/0=posStrLength(S)且0=len=StrLength(S)-posslen=StrLength_Sq(S);if(posslen-1|lenslen-pos)ERRORMSG(“参数不合法”);return;for(j=0;jlen;j+)Subj=Spos+j;Sublen=0;/S
9、ubString_Sq 算法4.3第14页/共40页串的顺序存储通过前面的例子我们可以看到，用字符数组表示字符串时，串的操作比较容易，并且允许用数组名进行串的输入和输出。同时我们还应该注意到，在这里我们使用的C语言的静态数组，使串的长度受到一定的限制。有可能会出现数组越界的情况，越界的情况一旦出现可能会导致“非法错误”，也可能会导致修改其他数据，即使有的C语言允许数组适当越界，也要占有额外的系统资源。从数据结构的严谨性和良好的编程习惯上来讲，应避免越界。由此可见，这种串的定长顺序表示有其先天的不足，适应范围有一定的局限性。第15页/共40页堆分配存储表示由于在多数情况下串的操作是以串的整体形式
10、参与，在应用程序中，参与运算的串变量之间的长度相差很大，并且在操作中，串值长度的变化也很大，因此将串变量设定为固定长的数组不尽合理。以堆分配存储表示串的特点：串变量的存储空间是在程序执行过程中动态分配而得，程序中出现的所有串变量可用的存储空间是一个称为“堆”的共享空间。例如，在C语言中的串类型就是以这种方式实现的，利用new为新生成的串分配一个实际串长所需的存储空间，如成功则返回串的基地址。第16页/共40页堆分配存储表示在采用堆分配存储表示时，串的操作仍然基于“字符序列的复制”进行。例如，串复制操作StrCopy(&T,S)的实现算法是，若串S为空串，则串T为一空指针；否则，首先为串T分配大
11、小和串S长度相等的存储空间，然后将串S的值复制到串T中；又如，串插入操作StrInsert(&S,pos,T)的实现算法是，为串S重新分配大小等于串S和串T长度之和的存储空间，然后进行串复制。第17页/共40页堆分配存储表示void StrInsert_HSq(char*S,int pos,char*T)/在串S的第pos个字符之前插入串Tslen=StrLength_HSq(S);tlen=StrLength_HSq(T);char S1slen+1;/辅存空间、暂存S/+LYG ERRORif(posslen)ERRORMSG(插入位置不合法);if(tlen0)i=0;while(S1i
12、=Si)!=0)i+;delete S;S=new charslen+tlen+1;for(i=0,k=0;ipos-1;i+)Sk+=S1i;j=0;while(Tj!=0)Sk+=Tj+;while(S1i!=0)Sk+=S1i+;SK=0;/if/StrInsert_HSq 算法4.4(主要操作全部自己实现)第18页/共40页堆分配存储表示void StrInsert(char*S,int pos,char*T)/在串S的第pos个字符之前插入串Tchar *S1,*Sub;/辅存空间slen=strlen(S);tlen=strlen(T);if(posslen)ERRORMSG(插入
13、位置不合法);if(tlen0)S1=strdup(S);S=new charslen+tlen+1;strncpy(S,S1,pos);Spos=0;strcat(S,T);Sub=S1+pos;strcat(S,Sub);delete S1;/if/StrInsert_HSq 算法4.4(使用C语言库函数实现 string.h)第19页/共40页块链存储表示和线性表的链式存储类似，串值也可以用链表来存储。但由于串结构的特殊性，存在着“一个结点大小”的问题。另外，在一般情况下，串的操作都是从前往后进行的，因此链表通常不设双链，但为了方便诸如串的联接等操作，链表中还是附设尾指针，同时还需要设定
14、一个指示串长的域。1.结构定义：const CHUNKSIZE=80;/可由用户定义的块（节点）大小typedef struct Chunk/节点结构 char chCHUNKSIZE；struct Chunk*next;Chunk;typedef struct/串的链表结构 Chunk*head,*tail;/头尾指针 intcurlen;/串的当前长度Lstring；第20页/共40页块链存储表示在以链表存储串值时，节点大小的选择将直接影响串处理的效率。定义串的存储密度=串值所占的存储空间/实际分配的存储空间；显然存储密度小，操作方便，但存储占用量大。通常情况下，以块链作存储结构时实现串的
15、操作比较麻烦，如：在串中插入一个子串时可能需要分割节点，联接两个串时，若第一个串的最后一个节点没有添满，还需要填充其他字符。但是，在实际应用中可将串的链表存储和定长结构结合使用。例如在正文编辑系统中，可将正文看成一个串，将一行看成一个子串，构成一个节点（80个字符）。行与行之间可用指针相联接。第21页/共40页4.3 正文模式匹配在计算机所处理的各类数据中，有很大一部分是正文数据，也常称为文本型数据。文本型数据是在任何平台和系统都可以接受的数据形式，在计算机行业有很长的历史。在最初的应用中，这些文字材料仅由可打印字符组成，首先由字符组成行，然后再由行构成整个正文。我们注意到，在已有的正文编辑软
16、件中，都提供“查找”功能，这种操作就是为串定位的工作，通常称为正文模式匹配第22页/共40页4.3 正文模式匹配例子：若 S=“concatenation”,T=“cat”我们的目的是在串S中查找有没有串T，及T在S中的位置。在这里我们称主串S中存在和模式串T相同的子串，起始位置为3，即Index(S,T,0)=3;正文模式匹配有多种算法，为了简单起见，采用C语言中定长表示描述算法。其实算法4.1就是这样的算法，只是在算法4.1中利用了串的其他操作，下面我们给出不依赖其他串操作的算法4.6第23页/共40页4.3 正文模式匹配我们应注意到，算法我们应注意到，算法4.6可以实现可以实现从任意位置
17、起的查询，其方法是从任意位置起的查询，其方法是起始起始pos=i+Strlength(T)int Index(char S,char T,int pos)/若串S中，从第pos个字符起存在和串T相同的子串，则称匹 /配成功，返回第一个这样的子串在串S中的位置，否则返回-1 i=pos;j=0;while(Si+j!=0&Tj!=0)if(Si+j=Tj)j+;/继续比较后一字符 else i+;j=0;/重新开始新的一轮比较 if(Tj=0)return i;/匹配成功 else return-1;/S中(第pos个字符起)不存在和T相同的子串/Index 算法 4.6第24页/共40页4.3
18、 正文模式匹配书上算法int Index(SString S,SString T,int pos)/返回子串T中在主串S中第pos个字符之后的位置.不存在为0i=pos;j=1;while(i=S0&j T0)return i-T0;else return 0;/Index第25页/共40页4.3 正文模式匹配小的改进int Index(SString S,SString T,int pos)/返回子串T中在主串S中第pos个字符之后的位置.不存在为0i=pos;while(i=S0-T0+1)j=1;while(j T0)return i;else i+;return 0;/Index第26
19、页/共40页4.3 正文模式匹配v前面的算法统称串匹配的平凡算法v如果以单个字符之间的比较为基本操作，算法Index的最坏情形时间复杂度应为O(nm)阶。v串匹配问题的平凡算法是可以改进的。T：ABABC，m=5S：ABABABCAC，n=9算法的执行过程相当于在n-m+1=5个长度为m的单词中检索单词T。这5个单词为：ABABA，BABAB，*ABABC，BABCA，ABCAC第27页/共40页4.3 正文模式匹配由于样本T与字典中的第三个单词相同，故返回值为 i=3。不难发现这里的字典有其特殊性，即相邻的两个单词有 m-1=4个字符是重复的，当算法用样本T=ABABC与第一个单词即S15=
20、ABABA比较时，虽然未能匹配，但二者的相等部分，即T14=S14却已经告诉我们下一个单词S26中的前三个字符与P24是相同的！利用这一特征，算法可以进一步改进。第28页/共40页4.3 正文模式匹配vKMP(Knuth-Morris-Pratt)算法v由于串匹配问题的特征，样本T1m在文本S1n上进行两次相邻匹配操作时，进行比较的对象Si-1i+m-2和Sii+m-1有m-1个字符相同，因此，从Si-1开始的匹配比较结果可能决定了T1m从Si开始的匹配操作是否必要。v仍用前面的实例说明：S19=ABABABCAC，T15=ABABC。从S1=A开始的匹配操作结果是T14=S14但T5S5，因
21、此T应向右移。v但由于T13=ABA，T24(=S24)=BAB，二者是不等的。因此从S2开始的匹配肯定会失败，所以样本T1m不必右移一位，至少可以右移两位。第29页/共40页4.3 正文模式匹配v一般情况下，当T1m在文本S的某一位置匹配失败后，它可以向右移动的位数只与样本T1m和匹配失败的字符位置j有关，样本P可以向右移动的距离，可以根据样本T1m的字符组成计算出来。v如所示，T1m移动到文本S的某一位置进行匹配时，假设前j-1个字符相等，第j个字符不等，因而匹配失败。这时根据T1m计算出函数next(j)(j 1,m)，可令样本T1m右移=j-next(j)位，匹配比较从Tnext(j)
22、开始。第30页/共40页4.3 正文模式匹配v从中不难看出，函数next(j)的值应为字符串T1j-1从两端计算的最大可匹配的长度再加上1，它可以表示为：next(j)=MAX k|T1.k-1=Tj-(k-1).j-1 kj vKMP算法KMP算法分为两部分，首先计算next()函数，然后进行串匹配。KmpNext算法描述如下：Input：样本T1.m，m为样本长度；Output：数组next1m，即next函数值。第31页/共40页4.3 正文模式匹配void KmpNext(char T,int m,int next)/计算 next1.m int j=1;i=0;next1=0;whi
23、le(j=m)if(i=0)|(Tj=Ti)j+;i+;nextj=i;else i=nexti;next(j)=MAX k|T1.k-1=Tj-(k-1).j-1 kj 第32页/共40页4.3 正文模式匹配 T=a b a a b c a c j=1 2 3 4 5 6 7 8nextj=i=next(j)=MAX k|T1.k-1=Tj-(k-1).j-1 kj if(i=0)|(Tj=Ti)j+;i+;nextj=i;else i=nexti;0110 1 0 1 221 22332 1 01122第33页/共40页4.3 正文模式匹配int KMP(SString S,SString
24、 T,int pos)/返回子串T中在主串S中第pos个字符之后的位置.不存在为0i=pos;j=1;while(i=S0&j T0)return i-T0;else return 0;/KMP第34页/共40页4.4 正文编辑-串操作应用举例正文编辑的实质是修改字符数据的形式或格式。基本操作包括串的查找、插入和删除等基本操作。处理文本的思路：利用换页符和换行符把文本划分成若干页，每页有若干行将文本看成是一个字符串，称为文本串页为文本串的子串，行又是页的子串第35页/共40页m am a i i n ()n ()f f l l o o a t a ,b ,a t a ,b ,m a x ;s
25、c a n fm a x ;s c a n f (“%f ,%f%f ,%f ”,&a ,&b );i f a b m a,&a ,&b );i f a b m ax =a ;e l s e m a x =b ;x =a ;e l s e m a x =b ;2012014.4 正文编辑-串操作应用举例例：有如下源程序清单main()float a,b,max;scanf(“%f,%f”,&a,&b);if ab max=a;else max=b;存入内存后形式如下：起始地址第36页/共40页m am a i i n ()n ()f f l l o o a t a t a ,b ,a ,b ,
26、m a x ;m a x ;s c a n f s c a n f (“%f ,%f%f ,%f ”,&a ,&b );,&a ,&b );i f i f a b a b m am ax =a ;x =a ;e l s e e l s e m a x =b ;m a x =b ;201201209209226226240240266266280280284284建立线性表：行号 开始地址 长度 1 201 7 1 201 7 2 209 16 2 209 16 3 226 23 3 226 23 4 240 14 4 240 14 4 266 13 4 266 13 6 280 4 6 280
27、 4线性表中的元素第37页/共40页如将第二行由 float a,b,max;float a,b,max;改为 float a,b,m;float a,b,m;或 float a,b,maxelem;float a,b,maxelem;新行长度原行长度：按对照表指出的第二行开始位置，变更相应的字符，并修改相应长度,新行长度原行长度：重新为该行分配存储空间,即生成一个新的结点(包括该行的行号、开始地址和长度)删除原结点,对照表变为:行号 开始地址 长度 1 201 7 1 201 7 3 226 23 3 226 23 4 240 14 4 240 14 4 266 13 4 266 13 6
28、280 4 6 280 4 2 284 20 2 284 20行号 开始地址 长度 1 201 7 1 201 7 2 284 20 2 284 20 3 226 23 3 226 23 4 240 14 4 240 14 4 266 13 4 266 13 6 280 4 6 280 4即结点的指针链保持不变 修改开始地址及长度删除若干字符:同上,变更相应字节内容和行长度插入若干字符:分插入后长度是否超长处理插入行:在线性表中增加新的结点 删除行:在线性表中删除结点 第38页/共40页信息检索中的词索引表1.1.信息检索的常见方式按书名：内容相似的书籍书名互不相同按分类号:从分类号中无法了解
29、图书的主要内容按作者名:2.2.信息检索方式的改进例:已知某图书数据库保存如下图书目录书号 书 名004 Computer Data Structures004 Computer Data Structures010 Introduction to Data Structures010 Introduction to Data Structures023 Fundamentals of Data Structures023 Fundamentals of Data Structures034 The Design and Analysis of Computer 034 The Design
30、and Analysis of Computer AlgorithmsAlgorithms040 Introduction to Numerical Analysis040 Introduction to Numerical Analysis067 Numerical Analysis067 Numerical Analysis关键词 书号索引Algorithms 034Algorithms 034analysis 034,040,067analysis 034,040,067computer 004,034computer 004,034data 004,010,023data 004,010,023design 034design 034fundamentals 023fundamentals 023introduction 010,040introduction 010,040numerical 040,067numerical 040,067structures 004,010,023structures 004,010,023关键词索引表第39页/共40页感谢您的观看！第40页/共40页