串市公开课一等奖省赛课获奖课件

第四章串串第1页第四章串学习关键点

1了解串基本操作，了解利用这些基本操作实现串其它操作方法；

2掌握在串堆分配存放结构下，串基本操作算法；

串也叫字符串，它是由零个或多个字符组成字符序列。基本内容

1串相关概念串基本操作

2串定长次序存放结构，堆分配存放结构；

3串基本操作算法；

串第2页一、串定义

1什么是串

串是一个特殊线性表，它是由零个或多个字符组成有限序列，普通记作s=“a1,a2,a3,...an”其中s----串名，a1,a2,a3,...an----串值串应用非常广泛，许多高级语言中都把串作为基本数据类型。在事务处理程序中，用户姓名、地址货物名称、产地可作为字符串处理，文本文件中每一行字符等也可作为字符串处理。4.1串类型定义串第3页下面是一些串例子：

（1）a=‘LIMING’

（2）b=‘PEJINGUNIUERCITY’

（3）c=‘DATASTRUCTURE’

（4）d=‘’

（5）e=‘’

说明：1)串中包含字符个数，称为串长度。

长度为0串称为空串，它不包含任何字符，上面（4）中串d是空串，(5)中e是包含一个空格符空格串；

2）串中所包含字符能够是字母、数字或其它字符，这依赖于详细计算机所允许字符集。串第4页2串相关术语1）子串

串中任意连续字符组成子序列称为该串子串

例：c=‘DATASTRUCTURE’，f=‘DATA’f是c子串2）子串位置子串T在主串S中位置是指主串S中第一个与T相同子串首字母在主串中位置。例：S=‘ababcabcac’,T=‘abc’子串T在主串S中位置为33）串相等

两个串相等，当且仅当两个串长度相同，而且各个对应位置字符都相同；串第5页3串基本操作

串逻辑结构与线性表一样，都是线性结构。主要区分在于串数据对象约束为字符集。但因为串应用与线性表不一样，串基本操作与线性表有很大差异。1）串赋值操作StrAssign(&T,chars)

功效：将串常量char值赋给串变量T；2）复制串操作

StrCopy(&T,S)

功效：由串变量S复制得到串变量T；3）判空操作

StrEmpty(S)功效：若为空串，则返回TRUE，不然返回FALSE4）串比较操作StrCompare(S,T)

功效若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<05）串置空操作ClearString(&S)

功效：将S清为空串串第6页6）求串长操作

StrLenght(&S)

功效：求串S长度7）串连接操作

Concat(&T,S1,S2)

功效：由S1和S2连接组成新串，用T返回新串；

8）求子串操作SubString(&Sub,S,pos,len)

功效：用Sub返回串S第pos个字符起长度len为子串；

9）求子串位置操作Index(S,T,pos)

功效：返回S中第pos个字符之后与T相同子串位置，若不存在返回010)串插入操作

StrInsert(&S,pos,T)

功效：将串T插入到串S第pos字符之前11）串删除操作

StrDelete(&S,pos,len)

功效：从串S中删除第pos个字符起长度为len子串串第7页4.2串表示和实现一、串存放（三种）1定长次序存放结构

定长次序存放结构类似于C语言字符数组，以一组地址连续存放单元存放串值字符序列，其类型说明以下：

#defineMAXSTRLEN255TypedefunsignedcharSString[MAXSTRLEN+1]

//0号单元存放串长度2、堆分配存放

堆分配存放类似于线性表次序存放结构，以一组地址连续存放单元存放串值字符序列，其存放空间是在程序执行过程中动态分配。在C语言中，存在一个称之为“堆”自由存放区，并由C语言动态分配函数管理。利用函数malloc()为每个新产生串分配一块实际串长所需存放空间，若分配成功，则返回一个指向起始地址指针，作为串基址，同时，为了以后处理方便，将串长也作为存放结构一部分。串这种存放结构本教材中称为堆分配存放

串第8页

在这种存放结构下，串操作仍是基于“字符序列复制”进行。比如，如串插入操作StrInsert(S,pos,T)（将串T插入到串S第pos字符之前）算法是，为串S重新分配大小等于串S和串T长度之和存放空间，然后进行将S和T串值复制到新分配存放空间中算法4.4。

以上两种存放表示通常为高级程序设计语言所采取。因为堆分配存放结构串现有次序存放结构特点，处理方便，操作中对串长又没有任何限制，更显灵活，所以在串处理应用程序中常被采取。

以下我们给出在堆分配存放结构下，串部分基本操作算法。堆分配存放类型说明Typedefstruct{char*ch;//指针域，指向存放串值存放空间基址intlength;//整型域：存放串长}Hstring;串第9页串插入算法

StrInsert(HString&S,intpos,HStringT){//为串S重新分配大小等于串S和串T长度之和存放空间，将S和//T串值复制到新分配存放空间中;在串S第pos个字符前插入串Tif(pos<1||pos>S.length+1)returnERROR;//参数不正当if(T.lenght){//若T非空，为串S重新分配存放空间,并插入Tif(!(S.ch=(char*)realloc((S.ch,S.length+T.length)*sizeof(char))));exit(OVERFLOW);for(i=S.length-1;i>=pos-1;--i)//将S第pos个字符及后面字符后

S.ch[i+T.length]=S.ch[i];//移，为插入T腾出T.length位置S.ch[pos-1..pos+T.length-2]=T.ch[0..T.length-1];//插入TS.length+=T.length;//修改串长为S与T长之和}returnOK;}SubString

算法4.4

串第10页S.lengthnS.ch01pos-1n-1n+m-1S.lengthn+mS.lengthn01pos-1n-1S.chT.chT.lengthm0

1m-1为串S重新分配存放空间,并将S复制到新空间将S第pos个字符及后面字符后移，为插入T腾出位置插入T修改串长串第11页二串基本操作算法串赋值算法StatusStrAssign(HString&T,char*chars){//生成一个其值等于串常量chars串Tif(T.ch)free(T.ch);//若原T.ch非空，释放T.ch所指向旧存放空间for(i=0,c=chars;c;++i,++c);//求chars长度iif(!i){T.ch=NULL;T.length=0;}//若i=0,生成空串Telse{if(!(T.ch=(char*)malloc(i*sizeof(char))))//分配存放空间exit(OVERFLOW);T.ch[0..i-1]=chars[0..i-1];T.length=i;}returnOK;}//StrAssign串第12页串常量依据串常量长度动态分配存放空间a1a2anchars01n-1传递数据T.chT.length01n-1a1a2an串赋值操作图示n串第13页串比较算法intStrCompare(HStringS,HStringT){//若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<0for(i=0;i<S.length&&i<T.length;++i)if(S.ch[i]!=T.ch[i])returnS.ch[i]-T.ch[i];returnS.length-T.length;}//StrCompare

串置空算法StatusClearString(HString&S){//将S清为空串。if(S.ch){free(S.ch);S.ch=NULL;}//若S.ch非空，释放S.ch所指向

//存放空间，而且S.ch=nullS.length=0;returnOK;}//ClearString

串第14页串连接算法StatusConcat(HString&T,HstringS1,HStringS2){//用T返回由S1和S2连接而成新串。if(T.ch)free(T.ch);//若T.ch非空，释放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];//先复制S1串数据T.length=S1.length+S2.length;T.ch[S1.length..T.length-1]=S2.ch[0..S2.length-1];//接着复制S2串数据returnOK;}//Concat

串第15页s1.ch01n1-1s1.lengthn1s2.ch01n2-1s2.lengthn2串s1串s2进行串合并s.ch01n1-1n1n1+n2-1

s.lengthn1+n2

串连接图示串第16页求子串算法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);//若Sub.ch非空，释放Sub.ch所指向存放空间if(!len){Sub.ch=NULL;Sub.length=0;}//若len=0，Sub为空子串else{//复制子串Sub.ch=(char*)malloc(len*sizeof(char));Sub.ch[0..len-1]=S[pos-1..pos+len-2];Sub.length=len;}returnOK;}SubString串第17页01Sub.chLen-1Sub.lengthlen动态分配存放空间01pos-1n-1S.lengthnS.ch01Sub.chLen-1Sub.lengthlen串第18页三串其它操作能够利用串基本操作实现串其它操作，参见P72算法4.1,实现定位函数Index(S,T,pos),算法:在主串S中取从第i(i初值为pos)个字符起、长度和串T相等子串和串T比较,若相等,则求得函数值i,不然i值增1直到串S中不存在和串T相等子串为止。串第19页4.2.3串块链式存放结构

次序串上插入和删除操作不方便，需要移动大量字符。所以，我们可用单链表方式来存放串值，串这种链式存放结构简称为链串。

typedefstructChunk{chardata;structChunk*next;}Chunk;

一个链串由头指针唯一确定。

这种结构便于进行插入和删除运算，但存放空间利用率太低。串第20页

为了提升存放密度，可使每个结点存放多个字符。通常将结点数据域存放字符个数定义为结点大小，显然，当结点大小大于1时，串长度不一定恰好是结点整数倍，所以要用特殊字符来填充最终一个结点，以表示串终止。还可设一尾指针,并给出当前串长度,此串存放结构为块链结构,对于结点大小不为1链串，其类型定为义只需对上述结点类型做简单修改即可。#defineCHUNKSIZE80//可由用户定义块大小

typedefstructChunk{chardata[CHUNKSIZE];structChunk*next;}Chunktypedefstruct{Chunk*head,*tail;//串头和尾指针intcurlen;//串当前长度}LString串第21页4.3串模式匹配算法

求子串位置定位函数

子串定位操作通常称作串模式匹配（其中T被称为模式串），是各种串处理系统中最主要操作之一。下面给出一个模式匹配算法，在本算法中，串采取定长次序存放结构，其类型说明以下：

#defineMAXSTRLEN255TypedefunsignedcharSstring[MAXSTRLEN+1]

本算法中，分别利用计数指针i和j指示主串S和模式串T中当前正待比较字符位置。算法基本思想是：从主串S第一个字符起和模式第一个字符比较之，若相等，则继续逐一比较后续字符，不然从主串下一个字符起再重新和模式字符比较之。依次类推，直至模式T中每个字符依次和主串S中一个连续字符序列相等，则称匹配成功，函数值为模式T中第一个了符相等字符在主串S中序号，不然称匹配不成功，函数值为零。图4.3展示了模式和主串S匹配过程。串第22页intIndex(SStringS,SStringT,int