数据结构授课教案-第4章

山东轻工业学院教师授课教案课程名称：数据结构（计科）课程代码：0301306学分：4.5课程类别：必修开课单位:信息科学与技术学院授课班级：授课教师：杨春花山东轻工业学院教务处制授课时间年月日星期第节年月日星期第节年月日星期第节授课内容概要第四章串第一节串类型的定义串、串长、子串、空格串等概念和串的基本运算。第二节串的表示和实现串的定长存储表示及实现，串的堆分配表示和块链存储表示。第三节串的模式匹配算法串的模式匹配算法（KMP算法）。目的要求目的：理解串的定义、基本运算和实现，理解模式匹配算法。基本要求：了解串的存储结构和基本操作、串的KMP模式匹配方法；理解串的概念和基本操作。重点串的基本概念和基本操作。难点KMP模式匹配方法。作业布置习题4参考书1.数据结构题集(C语言版),严蔚敏，清华大学出版社，2002。3.数据结构、算法与应用－C++语言描述，(美)SartajSahni著，汪诗林等译，机械工业出版社，2002。课型理论课学时分配复习分钟主要教具投影、黑板讲授分钟教学方法讲解、提问、示例指导分钟教学手段板书、课件总结分钟备注共2学时注：课型一栏填写理论课、实验课、习题课等授课内容备注第四章串4.1串类型的定义一、串的基本概念串(String)是零个或多个字符组成的有限序列。一般记为：S=‘a1a2…an’(n≥0)其中S为串名，用单引号括起来的为串值，n为串的长度。空串(NullString)：n=0时的串为空串空格串(Blankstring)：由一个或多个称为空格的特殊字符组成的串。请注意空串(NullString)和空格串(Blankstring)的区别。子串：串中任意个连续的字符组成的子序列称为该串的子串。主串：包含子串的串相应地称为主串。通常将字符在串中的序号称为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。假如有串A=‘ChinaBeijing’,B=‘Beijing’,C=‘China’,则它们的长度分别为13、7和5。B和C是A的子串,B在A中的位置是7,C在A中的位置是1。当且仅当两个串的值相等时,称这两个串是相等的。即只有当两个串的长度相等,并且每个对应位置的字符都相等时才相等。需要特别指出的是,串值必须用一对单引号括起来(C语言中是双引号),但单引号是界限符,它不属于串,其作用是避免与变量名或常量混淆。二、串的基本操作(1)求串长StrLength(S)(2)复制StrCopy(S,T)(3)串联接ConCat(S,T)(4)串比较StrCompare(S,T)(5)求子串SubString(S,pos,len)举例4.2串的表示和实现4.2.1定长顺序存储表示用一组地址连续的存储单元存储串值的字符序列。可用定长数组描述。#definemaxstrlen256typedefcharSString[maxstrlen];sstrings;//s是一个可容纳255个字符的顺序串。串长的表示方法：1、用一个不会出现在串中的特殊字符在串值的尾部来表示串的结束。例如，C语言中以字符‵\0′表示串值的终结。2、用s[0]存放串的实际长度，串值存放在s[1]~s[MAXSIZE]。3、类似顺序表，另设一个整数表示串长：typedefstruct{charch[maxstrlen];intlength;}sstring;例：串联接statusconcat(SString&t,SStrings1,SStrings2){if(s1[0]+s2[0]=MAXSIZE){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];}elseif(s1[0]MAXSIZE){T[1..s1[0]]=s1[1..s1[0]];T[s1[0]+1..MAXSIZE]=s2[1..MAXSIZE-S1[0]];T[0]=MAXSIZE;}elseT[0..MAXSIZE]=s1[0..MAXSIZE];}求子串：StatusSubString(SString&Sub,SStrings,intpos,intlen){if(pos1||poss[0]||len0||lens[0]-pos+1)returnERROR;else{sub[1..len]=s[pos..pos+len-1];s[0]=len;}}4.2.2堆分配存储表示这种存储表示的特点是，仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得。所以也称为动态存储分配的顺序表。typedefstruct{char*ch;intlength;}hsring;例：Statusconcat(hstringt,hstrings1,hstrings2){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];}Statussubstr(hstringsub,hstrings,intpos,intlen){if(pos1||poss.length||len0||lens.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[pos-1..pos+len-2];s.length=len;}}4.2.3串的链式存储结构顺序串上的插入和删除操作不方便，需要移动大量的字符。因此，我们可用单链表方式来存储串值，串的这种链式存储结构简称为链串。typedefstructnode{chardata;structnode*next;}lstring;一个链串由头指针唯一确定。这种结构便于进行插入和删除运算，但存储空间利用率太低。为了提高存储密度，可使每个结点存放多个字符。通常将结点数据域存放的字符个数定义为结点的大小，显然，当结点大小大于1时，串的长度不一定正好是结点的整数倍，因此要用特殊字符来填充最后一个结点，以表示串的终结。对于结点大小不为1的链串，其类型定为义只需对上述的结点类型做简单的修改即可。#definenodesize80typedefstructnode{chardata[nodesize];structnode*next;}lstring;4.3串的模式匹配算法串的模式匹配(PatternMatching)即子串定位是一种重要的串运算。设s和t是给定的两个串，在主串s中找到等于子串t的过程称为模式匹配，如果在s中找到等于t的子串，则称匹配成功，函数返回t在s中的首次出现的存储位置(或序号)，否则匹配失败，返回-1。t也称为模式。１．简单的模式匹配算法是布鲁特（Brute）-福斯（Force）算法，简称BF算法。intStrIndex_BF(char*s,char*t)/*从串s的第一个字符开始找首次与串t相等的子串*/{inti=1,j=1;while(i=s[0]&&j=t[0])/*都没遇到结束符*/if(s[i]==t[j]){i++;j++;}/*继续*/else{i=i-j+2;j=1;}/*回溯*/if(jt[0])return(i-t[0]);/*匹配成功，返回存储位置*/elsereturn–1;｝例：设主串s=“ababcabcacbab”，模式t=“abcac”，匹配过程下图所示。最坏情况下的时间复杂度是O(n*m)。２．改进后的模式匹配算法一种对BF算法做了很大改进的模式匹配算法是克努特(Knuth)，莫里斯(Morris)和普拉特(Pratt)同时设计的，简称KMP算法。(1)KMP算法的思想(2)next函数(3)KMP算法intStrIndex_KMP(char*s,char*t,intpos)/*从串s的第pos个字符开始找首次与串t相等的子串*/{inti=pos,j=1,slen,tlen;while(i=s[0]&&j=t[0])/*都没遇到结束符*/if(j==0||s[i]==t[j]){i++;j++;}elsej=next[j];/*回溯*/if(jt[0])returni-t[0];/*匹配成功，返回存储位置*/elsereturn–1;}