数据结构 第4章 串学习资料

14.1串的定义4.2串的表示和实现第4章串*串的模式匹配算法4.3

串的应用举例：简单的行编辑器4.4总结与提高24.1串的定义是由零个或多个字符组成的有限序列。

S=

a0a1a2…an-1

(n≥0)子串：第4章串串中任意个连续的字符组成的子序列。主串：包含子串的串相应地称为主串。位置：字符在序列中的序号。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。相等：两个串的长度相等，并且对应位置的字符都相等。空串与空白串34.1串的定义串的抽象数据类型的定义第4章串ADTString{

数据元素：D={ai|ai∈CharacterSet,记为V,i=1,2,…，n;n≥0}

数据关系：R＝｛<ai,ai+1>|ai,ai+1∈V，i=1,2,…,n-1;n-1≥0

｝

基本操作：

（1）StrAssign(S,chars)

（2）StrInsert(S,pos,T)

（3）StrDelete(S,pos,len)……}ADT

String

串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。

串的基本操作和线性表有很大差别：

在线性表的操作中，大多以“单个元素”作为操作对象；

在串的基本操作中，通常以“串的整体”作为操作对象。44.1串的定义基本操作：第4章串StrInsert(S,pos,T)初始条件：串S和T存在，1≤pos≤StrLength(S)+1。

操作结果：在串S的第pos个字符之前插入串T。StrInsert(S,pos,T)例如：S=

chater

，T=rac

，则执行StrInsert(S,4,T)之后S=

character

54.1串的定义基本操作：第4章串StrDelete(S,pos,len)初始条件：串S存在1≤pos≤StrLength(S)。

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

StrDelete(S,pos,len)例如：S=character，则执行StrDelete(S,4,3)之后S=chater64.1串的定义基本操作：第4章串StrCat(S,T)初始条件：串S和T存在。

操作结果：返回由S和T联接而成的新串。StrCat(S,T)例如：StrCat(man,kind)=mankind74.1串的定义基本操作：第4章串SubString(Sub,S,pos,len)初始条件：串S存在，1≤pos≤Length(S)

且0≤len≤Length(S)-pos+1。操作结果：用Sub返回串S的第pos个字符起长度为len的子串。SubString(Sub,S,pos,len)例如：SubString(sub1,commander,4,3)sub1=manSubString(sub2,

commander,4,7)sub2=?SubString(sub3,beijing,7,2)=?sub3=?起始位置和子串长度之间存在约束关系!84.1串的定义基本操作：第4章串StrIndex(S,pos,T)

初始条件：主串S和T存在，T是非空串操作结果：若主串S中存在和串T值相同的子串,则返回它在主串S中从第pos个字符开始第一次出现的位置；否则函数值为0。StrIndex(S,pos,T)例如：S=abcaabcaaabc,T=bcaStrIndex(S,1,T)=2StrIndex(S,4,T)=694.1串的定义基本操作：第4章串StrReplace(S,T,V)

初始条件：串S,T和V均已存在，且T是非空串。操作结果：用V替换主串S中出现的所有与（模式串）T相等的不重叠的子串。StrReplace(S,T,V)例如：S=abcaabcaaabca,T=bca,V=xS=axaxaax

10对于串的基本操作集可以有不同的定义方法，在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准。4.1串的定义基本操作第4章串

gets(str)输入一个串；

puts(str)

输出一个串；

strcat(str1,str2)串联接函数；

strcpy(str1,str2,k)串复制函数；

strcmp(str1,str2)串比较函数；

strlen(str)求串长函数；例如：C语言函数库（包含在库文件string.h中)提供下列串处理函数：返回114.2串的表示和实现第4章串定长顺序存储表示——用一组地址连续的存储单元存储串值的字符序列，属静态存储方式。堆分配存储表示——用一组地址连续的存储单元存储串值的字符序列,但存储空间是在程序执行过程中动态分配而得。串的块链存储表示——链式方式存储常用的实现方法：顺序存储链式存储12①定长顺序串4.2串的表示和实现常用的实现方法：第4章串存储表示：静态数组结构#defineMAXLEN255typedefstruct{charch[MAXLEN];intlen;}SString;

定长顺序串是将串设计成一种结构类型,串的存储分配是在编译时完成的。

串的实际长度可在预定义长度的范围内随意设定，超过预定义长度的串值则被舍去,称之为截断。13①定长顺序串4.2串的表示和实现常用的实现方法：第4章串基本操作：

插入、删除、复制、判空、比较、求串长、清空、连接、求子串。14串插入函数①定长顺序串4.2串的表示和实现常用的实现方法：第4章串StrInsert(SString*s,intpos,SStringt)/*pos为插入位置的下标*/0poss->len-10t.len-10pospos+t.lens->len+t.len-1M-1M-1M-1串插入函数StrInsert(SString*s,intpos,SStringt)/*pos为插入位置的下标*/{inti;if(pos<0||pos>s->len) return(0);

s->len=s->len+t.len;

if(s->len+t.len<=MAXLEN) {

for(i=s->len+t.len-1;i>=t.len+pos;i--)

s->ch[i]=s->ch[i-t.len];

for(i=0;i<t.len;i++) s->ch[i+pos]=t.ch[i]; }①定长顺序串4.2串的表示和实现常用的实现方法：第4章串

s->len=MAXLEN; else

if(pos+t.len<=MAXLEN) {

for(i=MAXLEN-1;i>=t.len+pos;i--)

s->ch[i]=s->ch[i-t.len];

for(i=0;i<t.len;i++)

s->ch[i+pos]=t.ch[i]; }

s->ch[i+pos]=t.ch[i];

s->len=MAXLEN;else

{for(i=0;i<MAXLEN-pos;i++) } return(1); }}

①定长顺序串4.2串的表示和实现常用的实现方法：第4章串串插入函数17①定长顺序串4.2串的表示和实现常用的实现方法：第4章串intStrDelete(SString*s;intpos,len)/*在串s中删除从序号pos起len个字符*/{inti;if(pos<0||pos>(s->len-len))return(0);for(i=pos+len;i<s->len;i++)s->ch[i-len]=s->ch[i];s->len=s->len-len;return(1);}串删除函数:18①定长顺序串4.2串的表示和实现常用的实现方法：第4章串串复制函数:voidStrCopy(SString*s,SStringt)/*将串t的值复制到串s中*/{inti;for(i=0;i<t.len;i++)s->ch[i]=t.ch[i];s->len=t.len;}19①定长顺序串4.2串的表示和实现常用的实现方法：第4章串串比较函数:intStrCompare(SStrings,SStringt)/*若串s和t相等,则返回0;若s>t,返回值大于0;若s<t返回值小于0.*/{inti;for(i=0;i<s.len&&i<t.len;i++)if(s.ch[i]!=t.ch[i])return(s.ch[i]-t.ch[i]);return(s.len-t.len);}

StrCat(SString*s,SStringt){inti,flag;if(s->len+t.len<=MAXLEN){for(i=s->len;i<s->len+t.len;i++)s->ch[i]=t.ch[i-s->len];s->len+=t.len;flag=1;}elseif(s->len<MAXLEN){for(i=s->len;i<MAXLEN;i++)s->ch[i]=t.ch[i-s->len];s->len=MAXLEN;flag=0;}elseflag=0;return(flag);}连接函数①定长顺序串4.2串的表示和实现常用的实现方法：第4章串SubString(SString*sub,SStrings,intpos,intlen)/*将串s中下标pos起len个字符复制到sub中*/{inti;if(pos<0||pos>s.len||len<1||len>s.len-pos){sub->len=0;return(0);}else{for(i=0;i<len;i++)sub->ch[i]=s.ch[i+pos];sub->len=len;return(1);}}求子串函数①定长顺序串4.2串的表示和实现常用的实现方法：第4章串StrIndex(SStrings,SStringt,intpos)/*求串t在串s中的位置*/{inti,j,start;if(t.len==0)return(0);start=pos;i=start;j=0;while(i<s.len&&j<t.len)if(s.ch[i]==t.ch[j]){i++;j++;}else{start++;i=start;j=0;}if(j>=t.len)return(start);elsereturn(-1);}定位函数（模式匹配）①定长顺序串4.2串的表示和实现常用的实现方法：第4章串23②堆串4.2串的表示和实现常用的实现方法：第4章串

很多实用的串处理系统中,采用堆结构,它的特点是:系统将一个很大的连续存储空间作为串的公用空间,每当建立新串时,系统从中分配一个和串长相同的连续空间存储串值,它们的地址是在程序执行中动态分配的.

系统中所有串名的存储映像构成一个符号表。其中len域指示串的长度,start域指示串的起始位置。借助此结构可以在串名和串值之间建立一个对应关系，称为串名的存储映像。24②堆串4.2串的表示和实现常用的实现方法：第4章串a='aprogram'，b='string'，c='process'，free=23。aprogramstringprocessHeap[MAXSIZE]free=23符号名lenstarta90b79c716符号表堆串的存储映象示例25②堆串4.2串的表示和实现常用的实现方法：第4章串存储表示：typedefstruct{char*ch;intlen;}HString;用C语言中的“堆”实现堆串,可用malloc()和free()完成动态存储管理。其定义为:其中len域指示串的长度，ch域指示串的起始地址。26堆串的基本操作

堆串操作实现的基本方法为：先为新生成的串分配一个存储空间，然后进行串值的复制。②堆串4.2串的表示和实现常用的实现方法：第4章串

赋值、插入、删除

。27②堆串4.2串的表示和实现常用的实现方法：第4章串StrCopy(HString*s，t)/*将串t的值复制到串s中*/{inti;s->ch=(char*)malloc(t.len);if(s->ch==NULL)return(0);for(i=0;i<t.len;i++)s->ch[i]=t.ch[i];s->len=t.len;return(1);}串复制函数

串赋值函数StrAssign(HString*s,char*tval)

/*将字符串常量tval的值赋给串s*/{intlen，i=0;if(s->ch!=NULL)free(s->ch);while(tval[i]!='\0')i++;len=i;if(len){s->ch=(char*)malloc(len);if(s->ch==NULL)return(0);for(i=0;i<len;i++)s->ch[i]=tval[i];}elses->ch=NULL;s->len=len;return(1);}②堆串4.2串的表示和实现常用的实现方法：第4章串StrInsert(HString*s,intpos,HString*t)/*在串s中下标为pos的字符之前插入串t*/{inti;char*temp;if(pos<0||pos>s->len||s->len==0)return(0);temp=(char*)malloc(s->len+t.len);if(temp==NULL)return(0);for(i=0;i<pos;i++)temp[i]=s->ch[i];for(i=0;i<t->len;i++)temp[i+pos]=t->ch[i];for(i=pos;i<s->len;i++)temp[i+t->len]=s->ch[i];s->len+=t->len;free(s->ch);s->ch=temp;return(1);}

串插入函数②堆串4.2串的表示和实现常用的实现方法：第4章串StrDelete(HString*s,intpos,intlen)/*在串s中删除从下标pos起len个字符*/{inti;char*temp;if(pos<0||pos>(s->len-len))return(0);temp=(char*)malloc(s->len-len);if(temp==NULL)return(0);for(i=0;i<pos;i++)temp[i]=s->ch[i];for(i=pos;i<s->len-len;i++)temp[i]=s->ch[i+len];s->len=s->len-len;free(s->ch);s->ch=temp;return(1);}

串删除函数②堆串4.2串的表示和实现常用的实现方法：第4章串31③块链串4.2串的表示和实现常用的实现方法：第4章串存储表示：可用链表来存储串值，由于串的数据元素是一个字符，它只有8位二进制数，因此用链表存储时，通常一个结点中存放的不是一个字符，而是一个定长子串,链表中最后一个结点不一定被占满。存储密度

=数据元素所占存储位实际分配的存储位abcdefghi###^32#defineBLOCK_SIZE4

typedefstructBlock

{charch[BLOCK_SIZE];

structBlock

*next;

}Block;

typedefstruct{

Block*head,*tail;

intcurlen;

}BLString;块链串的存储结构定义：实际应用时,可以根据问题所需来设置结点的大小。4.2串的表示和实现第4章串返回

文本编辑程序用于源程序的输入和修改、公文书信、报刊和书籍的编辑排版等。常用的文本编辑程序有Edit，WPS，Word等。

可将文本看成是一个大的字符串，文本编辑就相当于对字符串的处理。

为编辑方便，可将文本用分页符和分行符分成若干页，每页若干行。

可采用堆串结构存储文本，同时建立页表和行表，存储每页、每行的起始位置和长度。并设立页指针、行指针和字符指针，分别指示当前页、行和字符，4.3串的应用举例:简单的行编辑器第4章串例现有funcmax(x,y:integer):integer;pascalvarz:integer;

程序：beginifx>ythenz:=x;elsez:=y;return(z);

其堆串：

end;funcmax(x,y:lnteger):integer;↙varz:integer;↙begin↙

if

x>ythenz:=x;↙elsez:=y;↙return(z)↙end;↙4.3串的应用举例:简单的行编辑器第4章串

页表：行表：

页号起始位置长度行号起始位置长度

10104103123115插入、删除就要引起页表、

3466行表的修改。

4522057213685147995返回funcmax(x,y:lnteger):integer;↙varz:integer;↙begin↙

if

x>ythenz:=x;↙elsez:=y;↙return(z)↙end;↙主要知识点：1.串是一种特定的线性表，其特殊性就在于组成线性表的每个元素就是一个单字符。2.串常用的存储方式有三种：顺序串，堆串和块链串。3.顺序串以一维数组作为存储结构，运算实现类同顺序表。块链串以链表作为存储结构，运算实现类同链表。4.串的模式匹配算法是本章的重点，简单的模式匹配算法处理思路简单，由于进行了带回溯的处理，时间复杂度较高。改进的KMP模式匹配算法计算滑支位置，因而失配后无回溯，匹配速度较高。4.4总结与提高第4章串返回

算法思路:每当一趟匹配过程出现s[i]<>t[j]时,不需回溯i指针,而是利用已经得到的匹配结果将模式向右滑动尽可能远,再继续比较。

根据模式串字符间的规律构造一个next(j)函数,表示第j个字符与主串失配时,在模式中需重新比较的字符的位置。

KMP算法的时间复杂度可以达到O(m+n)*模式匹配KMP算法第4章串j-k+1j-1失配时若有：则模式串向右滑动,k对应到j即可,next(j)=k。'pp…p'='p…p'

01k-1

Next[j]=k的含义:在模式串的子串P0…Pj中,头串与尾串相等的最大长度为k。

Next[j]=k的作用:

在Pj与主串比较失配时，无需回溯主串比较指针i，而是让i保持不变，继续与模式串中的Pk比较即可。定义：模式串的next函数ijk

模式串P

主串

模式串Pkjj-kj-1其它情况0max{k|1<k<j且当j=0时-1[j]='pp…p'='pp'}01k-1…

nextj01234567模式串abaabcacnext[j]-10011201intStrIndex_KMP(SStrings,intpos,SStringt)

/*利用next函数，求主串s中pos位置起,串t第一次出现的位置*/

{inti,j;

if(t.len==0)return(0);/*空串是任意字符串的子串*/

i=pos;j=0;

while(i<s.len&&j<t.len)

if(j==-1||s.ch[i]==t.ch[j])/*对应字符相等,继续比较下一字符*/

{i++;j++;}

elsej=next[j];/*字符失配,则用next函数值更新j值,而i值不变*/if(j>=t.len)return(i-j);/*成功,返回主串的当前起始匹配位置*/

elsereturn(-1);

}j=-1表示此前比较的是首字符且不匹配应从主串后继字符起从头比较基本操作:

比较操作时间复杂度:O(n+m)acabaabaabcacaabcabaabcaci=7j=2abaabcaci=7j=5abaabcaci=2j=0abaabcaci=1j=0abaabcaci=1j=1abaabcaci=0j=0abaabcaci=13j=8while(i<s.len&&j<t.len)

if(j==-1||s.ch[i]==t.ch[j])

{i++;j++;}{继续比较后继字符