孙丽云数据结构串第讲市公开课一等奖省赛课获奖课件

4.1串及其运算4.1.1串定义串（或字符串）是由零个或多个字符组成有限序列。普通记作：s=〃c0c1c2…cn-1〃(n≥0)其中：s为串名，用双引号括起来字符序列是串值；ci(0≤i≤n-1)能够是字母、数字或其它字符；双引号为串值定界符，不是串一部分；字符串字符数目n称为串长度。例：s=“computer”分别指出其串名、串值及串长度。串是一个特殊线性表，它数据对象是字符集合。1孙丽云数据结构串第讲第1页注意1、空串和空格串区分：零个字符串称为空串，通常以两个相邻双引号来表示空串。如：s=“”，它长度为零；仅由空格组成串称为空格串。如：s=〃〃，它长度为空格个数。2、若串中含有空格，在计算串长时，空格应计入串长度中如：s=“I’mastudent〃长度为13。4.1.1串定义2孙丽云数据结构串第讲第2页两个串相等条件：（1）两个串长度相等；（2）各对应位置上字符都相同。串中任意个连续字符组成序列称为该串子串。包含子串串被称为主串。如，“com”、“om”、“a”和“man”都是“commander”子串。4.1.1串定义尤其：空串是任意串子串，任意串是其本身子串。判断：长度相等且包含相同字符两个字符串必定相等。（）×3孙丽云数据结构串第讲第3页子串在主串中位置是指子串在主串中首次出现时该子串首字符对应主串中序号。比如：（1）子串“man”在主串“commander”中位置为4。（2）设A和B分别为A=“Thisisastring”B=“is”求子串在主串中位置。4.1.1串定义34孙丽云数据结构串第讲第4页串是一个简单数据结构，它逻辑结构与线性表十分相同，区分仅在于串数据对象是字符集。串基本运算与线性表基本运算有很大差异。通常在串基本运算中，以“串整体”作为操作对象；而在线性表基本运算中，大多以“单个元素”作为操作对象。4.1.1串定义5孙丽云数据结构串第讲第5页4.1.2串基本运算1．Strassign(s,chars)功效：赋值运算。将串常量chars值赋给串变量s。比如：执行strassign(s，“abcd”)运算之后，s值为“abcd”。2．Assign(s,t)功效：赋值运算。将串变量t值赋给串变量s。比如：t="abcd"，则执行Assign(s,t)运算之后，s值为"abcd"。6孙丽云数据结构串第讲第6页4.1.2串基本运算3．Equal(s,t)功效：判相等运算。若s与t值相等则运算结果为1，不然为0。4．Length(s)

功效：求串长运算。求串s序列中字符个数，即串长度。5．Concat(s,t)功效：联接运算。将串t第一个字符紧接在串s最终一个字符之后，联接得到一个新串。比如s="man",t="kind"，则执行Concat(s,t)运算后得到新串为"mankind"。7孙丽云数据结构串第讲第7页6．Insert(s,pos,t)功效：插入运算，当1≤pos≤Length(s)+1时，在串s第pos个字符之前插入串t。7．Delete(s,pos,len)功效：删除运算。当1≤pos≤Length(s)且0≤len≤Length(s)-pos+1时，从串s中删去从第pos个字符起长度为len子串。

8．Replace(s,pos,len,t)功效：置换运算。当1≤pos≤Length(s)且0≤len≤Length(s)-pos+1时，用串t替换串s中从第pos个字符起长度为len子串。4.1.2串基本运算8孙丽云数据结构串第讲第8页例:已知s=“(xyz)+*”,t=“(x+z)*y”。试利用联接、求子串和置换等基本运算，将s转换为t。voidtrans(){ chara[10]=“(xyz)+*”; strings,t,s1,s2,s3,s4,s5; Strassign(s,a); s1=SubStr(s,3,1); s2=SubStr(s,6,1); s3=SubStr(s,7,1); s4=SubStr(Replace(s,3,1,s2),1,5); s5=concat(s4,s3); t=concat(s5,s1);}s1=“y”s2=“+”s3=“*”9孙丽云数据结构串第讲第9页练习设S1=“DataStructureCourse”，S2=“Structure”，S3=“Base”，求：

（1）Length(S1)；（2）Insert(S1,5,S3)；

（3）Delete(S1,6,9)；

（4）SubStr(S1,6,9)；(5)Index(S1,S2);21DataBaseStructureCourseDataCourseStructure6中间有两个空格10孙丽云数据结构串第讲第10页C语言中字符串处理函数●字符串输出函数puts（string）charstring[];●字符串输入函数gets（string）charstring[];●字符串连接函数strcat（string1,string2）charstring1[];charstring2[];将string1与string2连接，结果放在string1中。●字符串拷贝函数strcpy（string1,string2）charstring1[];charstring2[];将string2中字符拷贝到string1中。●测试字符串长度函数strlen(string）charstring[];测试字符串长度,函数值为字符串长度值。11孙丽云数据结构串第讲第11页C语言中字符串处理函数●字符比较函数strcmp（string1,string2）charstring1[];charstring2[];将string1与string2字符从左至右逐一相比较,比较结果由函数值带回。string1=string2,函数值为0；string1>string2,函数值为一正整数；string1<string2,函数值为一负整数。●字符串字符大写转换成小写函数strlwr（string）charstring[];将string中字符转换成小写。●字符串字符小写转换成大写函数strupr（string）charstring[];将string中字符转换成大写。12孙丽云数据结构串第讲第12页4.2串存放结构串是一个特殊线性表，其存放结构与线性表存放结构类似。串有3种存放结构：1、次序存放结构；2、链式存放结构；3、堆分配存放结构。13孙丽云数据结构串第讲第13页4.2.1串次序存放结构串次序存放结构是采取与其逻辑结构相对应存放结构，将串中各个字符按次序依次存放在一组地址连续存放单元里，逻辑上相邻字符在内存中也相邻。这是一个静态存放结构，串值存放分配是在编译时完成。所以，需要预先定义串存放空间大小。假如定义空间过大，则会造成空间浪费；假如定义空间过小，则会限制串一些运算，如联接、置换运算等。14孙丽云数据结构串第讲第14页4.2.1串次序存放结构在次序存放结构中，串类型定义描述以下：#defineMaxLen<最大串长>;//定义能处理最大串长度typedefstruct{charstr[MaxLen];//定义可容纳MaxLen个字符字符数组intcurlen;//定义当前实际串长度}string;15孙丽云数据结构串第讲第15页4.2.2串链式存放结构用单链表存放串，若每个结点仅存放一个字符，即使运算轻易实现，运算速度快，但每个结点指针域所占空间比字符域所占空间要大得多。为了提升空间利用率，能够使每个结点存放多个字符，称为块链结构。这种存放方式空间利用率高，但运算速度要慢。用特殊字符补全16孙丽云数据结构串第讲第16页堆存放结构特点：仍以一组空间足够大、地址连续存放单元存放串值字符序列，但它们存放空间是在程序执行过程中动态分配。所以也称为动态存放分配次序表。每当产生一个新串时，系统就从剩下空间起始处为串值分配一个长度和串值长度相等存放空间。在C语言中，存在一个称为“堆”自由空间，由动态分配函数malloc()分配一块实际串长所需存放空间，假如分配成功，则返回这段空间起始地址，作为串基址。由free()释放串不再需要空间。

4.2.3串堆分配存放结构17孙丽云数据结构串第讲第17页4.3串模式匹配模式匹配：子串定位运算称为模式匹配。模式匹配成功是指在目标串s中找到一个模式串t；模式匹配不成功则指目标串s中不存在模式串t。Index(s,t)功效：定位运算。若主串s中存在和串t相同子串，则运算结果为该子串在主串s中第一次出现位置；不然运算结果为0。注意:t是非空串。例：word中“查找”功效，就是模式匹配。18孙丽云数据结构串第讲第18页4.3.1Brute-Force算法假设s=“cddcdc”，t=“cdc”，则模式匹配过程以下：19孙丽云数据结构串第讲第19页Brute-Force算法C语言描述以下：intIndex(strings,stringt){inti,j;i=0;//指向串s第1个字符j=0;//指向串t第1个字符while((i<s.curlen)&&(j<t.curlen))if(s.str[i]==t.str[j])//比较两个子串是否相等 {++i;//继续比较后继字符 ++j;}else {i=i-j+1;//串s指针回溯重新开始寻找串t

j=0;}if(j>=t.curlen)

return(i-t.curlen+1);elsereturn0;//匹配失败返回0}

“==”也能够20孙丽云数据结构串第讲第20页在有些情况下，该算法效率很低。如当s="aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab"，t=“aaaaaab“KMP算法对该算法进行改进。4.3.1Brute-Force算法21孙丽云数据结构串第讲第21页KMP算法消除了Brute-Force算法中串s指针回溯。4.3.2KMP算法假设s=“abacabab”，t=“abab”，第一次匹配过程以下：下次能够直接进行第三次匹配，即i=3，j=0。由此可见，在KMP算法中当s.str[i]和t.str[j]比较不相等时，串s指针i无须回溯。

22孙丽云数据结构串第讲第22页目标串S:ababcabcaabcbaabc模式串T:ababcabdbabc引例分别求next[j]值23孙丽云数据结构串第讲第23页KMP算法基本思想设目标串为s，模式串为t

i、j分别为指示s和t指针，i、j初值均为0。若有si=tj，则i和j分别增1；不然，i不变，j退回至j=next[j]位置；比较si和tj。若相等则指针各增1；不然j再退回到下一个j=next[j]位置，再比较si和tj。依次类推，直到以下两种情况之一：1)j退回到某个j=next[j]时有si=tj，则指针各增1，继续匹配；2)j退回至j=-1，此时令指针各增l，即下一次比较si+1和t0

。

关键P89(一定要会求)模式串next值只与模式串本身相关,与目标串无关.例:求abaabcacnext值24孙丽云数据结构串第讲第24页#defineMaxLen<最大串长度>//定义最大串存放空间intIndex_KPM(strings,stringt){inti,j,next[MaxLen];GetNext(t，next);//先求得模式串next函数值i=0;//指向串s第1个字符j