串类型的定义42串的表示和实现43串的模式匹配算法44串操作应用举例市公开课一等奖省赛课获奖课件

第四章串本章内容安排4.1串类型定义4.2串表示和实现4.3串模式匹配算法4.4串操作应用举例1串类型的定义42串的表示和实现43串的模式匹配算法44串操作应用举例第1页【学习目标】掌握串逻辑特征及惯用基本运算；掌握串各种存放表示方法，以及各种存放表示下各种算法实现；了解串匹配各种算法实现及串应用。2串类型的定义42串的表示和实现43串的模式匹配算法44串操作应用举例第2页【重点和难点】本章重点：串数据结构基本概念及定义；串抽象数据类型定义；串存放表示与算法实现；串数据结构基本应用。3串类型的定义42串的表示和实现43串的模式匹配算法44串操作应用举例第3页4.1串类型定义1.基本概念串（string）：由0个或多个字符组成有限序列，也称字符串。记为：s=’a1a2a3……an

’(n≥0)。串也能够表示为：s=（a1，a2，……，an），即串也是一个线性表，是一个数据类型受限制（仅为字符型）线性表。串长度：串中字符个数。空串：不含任何字符串，串长度=0，普通用Φ表示。空格串：仅由一个或多个空格字符组成串4串类型的定义42串的表示和实现43串的模式匹配算法44串操作应用举例第4页子串与主串：若一个串是另一个串中连续一段（字符序列），则这个串称为另一个串子串，而另一个串称为主串。比如：s1=‘datastructure’,s2=‘data’，则s2为s1子串，s1为s2主串。串相等：两个串长度相等且各对应位置字符都相同。注意：（1）串值必须用一对单引号括起来，但单引号不属于串。（2）串值大小是按词典次序（ASCII码）进行比较。比如：StrCompare(‘data’,’Stru’)<0

StrCompare(‘cat’,’case’)>0

StrCompare(‘data’,‘data’)=05串类型的定义42串的表示和实现43串的模式匹配算法44串操作应用举例第5页2.串抽象数据类型定义ADTString{

数据对象：D＝{ai|ai∈CharacterSet,i=1,2,...,n,n≥0}

数据关系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

基本操作：

StrAssign(&T,chars)

初始条件：chars是字符串常量。

操作结果：把chars赋为T值。

StrCopy(&T,S)

初始条件：串S存在。

操作结果：由串S复制得串T。6串类型的定义42串的表示和实现43串的模式匹配算法44串操作应用举例第6页

DestroyString(&S)

初始条件：串S存在。

操作结果：串S被销毁。

StrEmpty(S)

初始条件：串S存在。

操作结果：若S为空串，返回TRUE，不然返回FALSE。

StrCompare(S,T)

初始条件：串S和T存在。

操作结果：若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值=0。

StrLength(S)

初始条件：串S存在。

操作结果：返回S元素（字符）个数，称为串长度。7串类型的定义42串的表示和实现43串的模式匹配算法44串操作应用举例第7页

Concat(&T,S1,S2)

初始条件：串S1和S2存在。

操作结果：用T返回由S1和S2联接而成新串。

SubString(&Sub,S,pos,len)

初始条件：串S存在，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1。

操作结果：用Sub返回串S第pos个字符起长度为len子串。

Index(S,T,pos)

初始条件：串S和T存在，T是非空串，1≤pos≤StrLength(S)

操作结果：从主串S中第pos个字符起向后查找子串T，若存在，则返回第一次出现位置;不然，返回0。8串类型的定义42串的表示和实现43串的模式匹配算法44串操作应用举例第8页

Replace(&S,T,V)

初始条件：串S,T和V存在，T是非空串。

操作结果：用V替换主串S中出现全部与T相等不重叠子串。StrInsert(&S,pos,T)

初始条件：串S和T存在，1≤pos≤StrLength(S)＋1。

操作结果：在串S第pos个字符之前插入串T。StrDelete(&S,pos,len)

初始条件：串S存在，1≤len≤StrLength(S)-pos+1。

操作结果：从串S中删除第pos个字符起长度为len子串。ClearString(&S)

初始条件：串S存在。操作结果：将S清为空串。

}ADTString9串类型的定义42串的表示和实现43串的模式匹配算法44串操作应用举例第9页比如：StrCompare(“data”,“state”)<0SubString(sub,"commander",4,3)SubString(sub,"commander",1,9) SubString(sub,"commander",9,1) 10串类型的定义42串的表示和实现43串的模式匹配算法44串操作应用举例第10页比如：S="abcaabcaaabc",T="bca"Index(S,T,1)=2;Index(S,T,3)=6;Index(S,T,8)=0;11串类型的定义42串的表示和实现43串的模式匹配算法44串操作应用举例第11页比如：假设S="abcaabcaaabca",T="bca"若V="x",则经置换后得到S="axaxaax"若V="bc",则经置换后得到S="abcabcaabc“比如：S=“chater”，T=“rac”，则执行StrInsert(S,4,T)之后得到S="character"12串类型的定义42串的表示和实现43串的模式匹配算法44串操作应用举例第12页在以上操作中，串赋值StrAssign、串比较StrCompare、求串长StrLength、串联接Concat以及求子串SubString等五种操作组成串类型最小操作子集，即这些操作不可能利用其它串操作来实现。反之，其它一些操作能够使用这5个操作来实现。见算法4.1查找子串实现。13串类型的定义42串的表示和实现43串的模式匹配算法44串操作应用举例第13页思索：串和线性表区分是什么？1）串逻辑结构和线性表极为相同，区分仅在于串数据对象约束为字符集2）串基本操作和线性表有很大差异。在线性表基本操作中，大多以“单个元素”作为操作对象，如：在线性表中查找某个元素、求取某个元素、在某个位置上插入一个元素和删除一个元素等；而在串基本操作中，通常以“串整体”作为操作对象，如：在串中查找某个子串、求取一个子串、在串某个位置上插入一个子串以及删除一个子串等14串类型的定义42串的表示和实现43串的模式匹配算法44串操作应用举例第14页4.2串表示和实现串机内表示有三种方法，现分别介绍以下。1.定长次序存放表示用一组地址连续存放单元存放串值字符序列，类似于线性表次序存放结构。普通用定长数组表示：#defineMAXSTRLEN255//串长度不超出255typedefunsignedcharSString[MAXSTRLEN+1];

//0号单元存放串长度，但C语言以’\0’结束标志。串实际长度可在这个预定义长度范围内随意设定，超出预定义长度串值部分则被舍去，称之为“截断”。15串类型的定义42串的表示和实现43串的模式匹配算法44串操作应用举例第15页1.定长次序存放时串操作串联结Contcat（&T,S1,S2）

算法描述：StatusConcat(SString&T,SStringS1,SStringS2){//用T返回由S1和S2联接而成新串。若未截断，则返回TRUE，不然FALSE。

if(S1[0]+S2[0]<=MAXSTRLEN){//未截断

T[1..S1[0]]=S1[1..S1[0]];T[S1[0]+1..S1[0]+S2[0]]=S2[1..S2[0]];

T[0]=S1[0]+S2[0];uncut=TRUE;}

elseif(S1[0]<MAXSTRLEN){//截断16串类型的定义42串的表示和实现43串的模式匹配算法44串操作应用举例第16页

T[1..S1[0]]=S1[1..S1[0]];

T[S1[0]+1..MAXSTRLEN]=S2[1..MAXSTRLEN-S1[0]];

T[0]=MAXSTRLEN;uncut=FALSE;}

else{//截断(仅取S1)

T[0..MAXSTRLEN]=S1[0..MAXSTRLEN];

//T[0]==S1[0]==MAXSTRLEN

uncut=FALSE;}

returnuncut;}//Concat17串类型的定义42串的表示和实现43串的模式匹配算法44串操作应用举例第17页（2）求子串SubString(&Sub,S,pos,len)

StatusSubString(SString&Sub,SStringS,intpos,intlen){

//用Sub返回串S第pos个字符起长度为len子串。

//其中1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1

if(pos<1||pos>S[0]||len<0||len>S[0]-pos+1)

returnERROR;

Sub[1…len]=S[pos…pos+len-1]；

Sub[0]=len；

returnOK;

}//SubString例：SubString(&Sub,“commander”,4,3)得到结果是：Sub="man"。18串类型的定义42串的表示和实现43串的模式匹配算法44串操作应用举例第18页串定长（数组）次序表示特点定长数组缺点：串联结、插入、替换等操作，因为存放空间不足，经常引发“截断”发生。19串类型的定义42串的表示和实现43串的模式匹配算法44串操作应用举例第19页

2.堆分配存放表示（动态次序存放）以一组地址连续存放单元存放串值字符序列，但它们存放空间是在程序执行过程中动态分配而得。串堆分配存放表示：

typedefstruct{

char*ch;//若非空串，则按串长分配存放区；不然，为NULL

intlength;//串长度

}HString;20串类型的定义42串的表示和实现43串的模式匹配算法44串操作应用举例第20页注：1、C语言中提供串类型就是以这种存放方式实现。2、系统利用函数malloc()和free()进行串值空间动态管理，为每一个新产生串分配一个存放区，称串值共享存放空间为“堆”。3、C语言中串以一个空字符\0为结束符，串长是一个隐含值。21串类型的定义42串的表示和实现43串的模式匹配算法44串操作应用举例第21页堆分配存放表示串操作实现（1）给串赋值StatusStrAssign(HString&T,char*chars){//生成一个其值等于串常量chars串T。if(T.ch)free(T.ch);//释放T原有空间for(i=0,c=chars;*c;++i,++c);//求串长度iif(!i){T.ch=NULL;T.length=0;}//若i为0，则置空串Telse{//若i非0，则生成串Tif(!(T.ch=(char*)malloc(i*sizeof(char))))exit(OVERFLOW)T.ch[0..i-1]=chars[0..i-1];T.length=i;}returnOK;}//StrAssign22串类型的定义42串的表示和实现43串的模式匹配算法44串操作应用举例第22页（2）串比较IntStrCompare(HstringS,HstringT){

//串S和T从第一个字符开始比较，直到出现第一个不相等字符：假如//S[i]>T[i]，则S>T，返回值>0；假如S[i]<T[i]，则S<T，返回值<0；//串S和T长度相等，全部字符相等时，即S=T，返回值=0。

for(i=0;i<S.length&&i<T.length;++i)//C语言数组特征

if(S.ch[i]!=T.ch[i])returnS.ch[i]-T.ch[i];

returnS.length-T.length；}//StrCompare23串类型的定义42串的表示和实现43串的模式匹配算法44串操作应用举例第23页（3）串联接StatusConcat(Hstring&T,HStringS1,HstringS2){

//用T返回由S1和S2联接而成新串

if(T.ch)free(T.ch);//释放旧空间

if(!(T.ch=(char*)malloc((S1.length+S2.length)*sizeof(char))))

exit(Overflow);

T.ch[0…S1.length-1]=S1.ch[0…S1.length-1];

T.length=S1.length+S2.length;

T.ch[S1.length…T.length-1]=S2.ch[0…S2.length-1];

returnOK;

}//Concat24串类型的定义42串的表示和实现43串的模式匹配算法44串操作应用举例第24页（4）取子串StatusSubString(HString&Sub,HStringS,intpos,intlen){

//用Sub返回串S第pos个字符起长度为len子串。

//其中1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1

if(pos<1||pos>S.length||len<0||len>S.length-pos+1)

returnERROR;

if(Sub.ch)free(Sub.ch);//释放旧空间

if(!len){Sub.ch=NULL;Sub.length=0;}//空子串

else{//完整子串

Sub.ch=(char*)malloc(len*sizeof(char));

Sub.ch[0…len-1]=S.ch[pos-1…pos+len-2]；Sub.length=len；}

returnOK;

}//SubString25串类型的定义42串的表示和实现43串的模式匹配算法44串操作应用举例第25页3.串块链存放表示串值也可用链表来存放，和线性表链式存放类似，不一样是一个结点中存放不一定是一个字符，能够是一个子串，当串长不是结点大小整数倍时，最终一个结点用其它字符补上（如：#）。实例:在文本编辑系统中，整个文本编辑区可看成是一个串，每一行是一个子串，组成一个结点(80个字符),行和行之间用指针相联接。26串类型的定义42串的表示和实现43串的模式匹配算法44串操作应用举例第26页块链结构：为了便于进行串操作，当以链表存放串值时，除头指针外还能够附设一个尾指针指示链表中最终一个结点，并给出当前串长度。#defineCHUNKSIZE80//可由用户定义块大小

typedefstructChunk{//结点结构

charch[CHUNKSIZE];

structChunk*next;

}Chunk;

typedefstruct{//串链表结构

Chunk*head,*tail;//串头和尾指针

intcurlen;//串当前长度

}Lstring；27串类型的定义42串的表示和实现43串的模式匹配算法44串操作应用举例第27页S.headS.crulenS.tailThisastring^is28串类型的定义42串的表示和实现43串的模式匹配算法44串操作应用举例第28页4.3串模式匹配算法1.求子串位置定位操作算法intIndex(SStringS，SStringT，intpos)模式匹配：在主串中寻找给定子串（非空）定位操作称作串模式匹配，给定子串称为模式串。若找着子串，匹配成功；不然，匹配不成功。算法思想：从主串S第pos个字符起和模式第一个字符比较，若相同，则继续逐一比较后续字符；若出现不一样，则从主串下一个字符起再重新和模式字符比较之。依这类推，直到模式串中每个字符与主串中一个连续字符序列相等，则称匹配成功。不然，称为匹配不成功。29串类型的定义42串的表示和实现43串的模式匹配算法44串操作应用举例第29页S13ababcabcacbab012345678910111213T5abcac012345ijijijiiiiiiijjji30串类型的定义42串的表示和实现43串的模式匹配算法44串操作应用举例第30页定长次序存放结构模式匹配算法intIndex(SStringS,SStringT,intpos){

//从主串S第pos个字符起向后查找子串T，若存在，返回第一次匹配成功//位置；不然，则返回0。其中，T非空，1≤pos≤StrLength(S)。

i=pos;j=1;

while(i<=S[0]&&j<=T[0]){

if(S[i]==T[j]){++i;++j;}//继续比较后继字符

else{i=i-j+2;j=1;}//指针后退重新开始匹配

}

if(j>T[0])returni-T[0];

elsereturn0;

}//Index

31串类型的定义42串的表示和实现43串的模式匹配算法44串操作应用举例第31页朴素匹配算法效率较低abbacabcacbababcacabcacabcacabcacabcacabcacabcacTS总共进行了六趟匹配:-<32串类型的定义42串的表示和实现43串的模式匹配算法44串操作应用举例第32页算法分析普通情况下，该算法实际执行效率是比较高，所以在多数实际应用场所下被应用。但在一些特殊情况下，比如：S=‘000000000000000000000000000000001’T=‘000000001’。最坏情况下时间复杂度为：O(n*m)，其中n和m分别为S串和T串长度。因为模式串中部分匹配，引发主串定位指针i屡次回溯。

算法缺点：有时效率低，回溯指针次数多。33串类型的定义42串的表示和实现43串的模式匹配算法44串操作应用举例第33页字符串操作应用举例文本编辑建立词索引表34串类型的定义42串的表示和实现43串的模式匹配算法44串操作应用举例第34页4.4串操作应用举例——文本编辑器

文本编辑：实质是修改字符数据形式或格式，包含串查找、插入、删除等基本操作。

思绪：能够利用换行符和换页符将文本划分成若干页，每页包含若干行。页是文本串子串，行是页子串。在编辑程序中，先为文本串建立对应页表和行表，即建立各子串存放映象，在程序中设置页指针、行指针和字符指针，分别指向当前操作页、行和字符。进行文本编辑过程，就是一个对行表、页表进行查找、插入或删除过程。35串类型的定义42串的表示和实现43串的模式匹配算法44串操作应用举例第35页

假设有以下一段C源程序

main(){

floata,b,max;

scanf(“%f,%f”,&a,&b);

ifa>bmax=a;

elsemax=b;

};

我们将此源程序看成是一个正文串，输入内存后如图所表示，图中“↙”为换行符。main(){↙floata,b,max;↙scanf("%f,%f",&a,&b);↙ifa>bmax=a;↙elsemax=b;↙};↙20036串类型的定义42串的表示和实现43串的模式匹配算法44串操作应用举例第36页假如在某行内插入或删除若干字符，则要修改行表中该行长度，若该行长度因插入而超出了原分配给它存放空间，则要为该行重新分配存放空间，并修改该行起始位置。37串类型的定义42串的表示和实现43串的模式匹配算法44串操作应用举例第37页建立词索引表建立词索引表能够加速信息检索数据库建立索引程序索引表用户接口用户请求检索结果检索程序38串类型的定义42串的表示和实现43串的模式匹配算法44串操作应用举例第38页书目检索举例

(建立书目关键词索引表)书号0050230