工学第三章串.pptx
《工学第三章串.pptx》由会员分享,可在线阅读,更多相关《工学第三章串.pptx(41页珍藏版)》请在咨信网上搜索。
1、第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表栈、队列和串栈、队列和串栈、队列和串栈、队列和串本章的基本内容是:本章的基本内容是:栈和队列的定义及操作特性;栈和队列的定义及操作特性;栈和队列的两种存储方法和基本运栈和队列的两种存储方法和基本运算的实现;算的实现;串的基本概念和操作;串的基本概念和操作;串的常用存储方法;串的常用存储方法;串的模式匹配算法。串的模式匹配算法。第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串3.3.1 串的逻辑结构串的逻辑结构1.串的定义串的定义串是零个或多个字符组成的有限序列串是零个或多个字符组成的有限序列。空格串空格串:
2、只包含空格的串。:只包含空格的串。串的长度串的长度:串中所包含的字符个数。:串中所包含的字符个数。空串空串:长度为:长度为0的串。的串。空串记作空串记作“”;非空串通常记作非空串通常记作:S=“s1 s2 sn”其其中中:S是是串串名名;双双引引号号是是定定界界符符;双双引引号号引引起起来来的部分是串的部分是串值值。si(1in)是一个任意字符是一个任意字符。第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串子串:子串:串中任意个连续的字符组成的子序列。串中任意个连续的字符组成的子序列。主串:包主串:包含子串的串含子串的串。子串在主串中的位置:子串的第一个字符在主串子串在
3、主串中的位置:子串的第一个字符在主串中的序号中的序号。S1=ab12cd S2=“ab12 S3=S4=“”串的长度?串的长度?第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串理解串的定义有以下要点:理解串的定义有以下要点:(1)s(1)si i(1in)(1in)是一个抽象符号,代表任意字符。是一个抽象符号,代表任意字符。(2)s(2)si i在串中出现的序号在串中出现的序号i i称为该字符在串中的位置称为该字符在串中的位置(3)(3)有限性:组成串的字符个数是有限的。有限性:组成串的字符个数是有限的。(4)(4)顺序性:相邻字符之间具有前驱后继关系。顺序性:相邻字符
4、之间具有前驱后继关系。(5)(5)元元素素的的特特殊殊性性:数数据据元元素素是是字字符符。注注意意不不是是符符号,串的数据元素均取自某个字符集。号,串的数据元素均取自某个字符集。第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串串的数据对象约束为某个字符集。串的数据对象约束为某个字符集。微机上常用的字符集是标准微机上常用的字符集是标准ASCII码,由码,由 7 位二进制数表位二进制数表示一个字符,总共可以表示示一个字符,总共可以表示 128 个字符。扩展个字符。扩展ASCII码由码由 8 位二进制数表示一个字符,总共可以表示位二进制数表示一个字符,总共可以表示 256 个
5、字符,个字符,足够表示英语和一些特殊符号,但无法满足国际需要。足够表示英语和一些特殊符号,但无法满足国际需要。Unicode由由 16 位二进制数表示一个字符,总共可以表示位二进制数表示一个字符,总共可以表示 216个字符,即个字符,即6万万5千多个字符,能够表示世界上所有语千多个字符,能够表示世界上所有语言的所有字符,包括亚洲国家的表意字符。为了保持兼言的所有字符,包括亚洲国家的表意字符。为了保持兼容性,容性,Unicode字符集中的前字符集中的前256个字符与扩展个字符与扩展ASCII码完码完全相同。全相同。第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串2.串的比
6、较串的比较 串的比较是通过组成串的串的比较是通过组成串的字符字符之间的比较来进行的。之间的比较来进行的。给定两个串:给定两个串:X=x1x2xn Y=y1y2ym则当则当n=m且且x1=y1,xn=ym时,称时,称X=Y;当下列条件之一成立时,称当下列条件之一成立时,称XY:nm,且且xi=yi(i=1,2,n););存存在在某某个个kmin(m,n),使使得得xi=yi(i=1,2,k-1),),xkyk。在在计计算算机机中中,字字符符编编码码通通常常用用ASCII码码,字字符符的的比比较较就就是是ASCII码之间的比较。码之间的比较。3.串的抽象数据类型定义串的抽象数据类型定义串的基本操作
7、通常以串的基本操作通常以“串的整体串的整体”作为操作对象。作为操作对象。第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串 StrLength(s):求串求串s的长度。的长度。StrAssign(s1,s2):串串赋赋值值,将将s2的的串串值值赋赋值值给给串串s1。StrConcat(s1,s2,s):串串的的连连接接,将将串串s2放放在在串串s1的后面连接成一个新串的后面连接成一个新串s。SubStr(s,i,len):求求子子串串,返返回回从从串串s的的第第i个个字符开始取长为字符开始取长为 len 的子串。的子串。第第第第3 3章章章章 特殊线性表特殊线性表特殊线性
8、表特殊线性表串串串串 StrCmp(s1,s2):串串比比较较,若若s1=s2,返返回回0;若若s1s2,返回返回1。StrIndex(s,t):子子串串定定位位,返返回回子子串串t在在主主串串s中中首次出现的位置。若首次出现的位置。若t不是不是s的子串,则返回的子串,则返回0。StrInsert(s,i,t):串串插插入入,将将串串t插插入入到到串串s的的第第i个位置。个位置。StrDelete(s,i,len):串串删删除除,删删除除串串s中中从从第第i个个字符开始连续字符开始连续len个字符。个字符。StrRep(s,t,r):串串替替换换,在在串串s中中用用串串r替替换换所所有与串有与
9、串t相等的子串。相等的子串。第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串SubStr(s,i,len)求子串求子串算法示例算法示例i n f i n i t yi=3,len=3f i ni n f i n i t yi=6,len=4i t y超出超出从串从串s中第中第i 个字符起连续取个字符起连续取 长为长为len 个字符个字符,形成子形成子串并返回。串并返回。第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串3.3.2 串的存储结构串的存储结构 1.串的顺序存储结构串的顺序存储结构定义定义:串的顺序存储结构是用数组来存储串中的串的顺序存储
10、结构是用数组来存储串中的字符序列。字符序列。在在串串的的顺顺序序存存储储中中,如如何何标标识识一一个个串串的的实实际际长度?长度?用数组来存放串,其存储结构与顺序表相同,但串的操作是用数组来存放串,其存储结构与顺序表相同,但串的操作是把串作为一个整体,从而有其与顺序表不同的操作特性。把串作为一个整体,从而有其与顺序表不同的操作特性。0 1 2 3 4 5 6 7 8 MaxSize-1a b c d e f g h i 空空 闲闲 9串的顺序存储方式串的顺序存储方式1第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串用一个变量来表示串的实际长度用一个变量来表示串的实际长度
11、 方案一在在串串尾尾存存储储一一个个不不会会在在串串中中出出现现的的特特殊殊字符作为串的终结符,字符作为串的终结符,表示串的结尾。表示串的结尾。方案二用用数数组组的的0号号单单元元存存放放串串的的长长度度,串串值值从从1号单元开始存放。号单元开始存放。方案三0 1 2 3 4 5 6 7 8 9 MaxSize-1a b c d e f g h i 0 空空 闲闲串的顺序存储方式串的顺序存储方式20 1 2 3 4 5 6 7 8 9 MaxSize-19 a b c d e f g h i 空空 闲闲串的顺序存储方式串的顺序存储方式3第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊
12、线性表串串串串2.串的链接存储结构串的链接存储结构(1 1)非压缩形式。)非压缩形式。(2)压缩形式。)压缩形式。一个结点只存储一个字符。一个结点只存储一个字符。令一个结点存储多个令一个结点存储多个字符。字符。优缺点?优缺点?非压缩形式:操作方便,但存储率低;非压缩形式:操作方便,但存储率低;压压缩缩形形式式:存存储储率率高高,但但操操作作复复杂杂。因因为为它它是是一一种种顺顺序序和和链链接接相相结结合合的的结结构构,实实质质上上是是将将字字符符序序列列分分成成若若干干等等长长的的组组,每每个个组组占占用用一一个个结结点点,当当要要改改变变串串长长的的时时候候,可能涉及到结点的增加和删除问题。
13、可能涉及到结点的增加和删除问题。a b c d e f ga eb fc gd第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串3.3.3 3.3.3 模式匹配模式匹配 定义:给定两个串定义:给定两个串S=“s1s2sn”和和T=“t1t2tm”,在主在主串串S中寻找子串中寻找子串T的过程称的过程称为为模式匹配模式匹配。T称为模式称为模式。如果匹配成功,返回如果匹配成功,返回T在在S中的位置,如果匹配失败,中的位置,如果匹配失败,返回返回0。假设串采用顺序存储结构,串的长度存放在数组的假设串采用顺序存储结构,串的长度存放在数组的0号单元,串值从号单元,串值从1号单元开始存
14、放。下面我们介绍号单元开始存放。下面我们介绍两种串的模式匹配算法。两种串的模式匹配算法。第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串朴素的模式匹配算法朴素的模式匹配算法 该算法简称该算法简称BF算法。算法。基本思想基本思想是:从主串是:从主串S的第一个字符开始和模式的第一个字符开始和模式T的第一个的第一个字符进行比较,若相等,则继续比较两者的后续字符;否字符进行比较,若相等,则继续比较两者的后续字符;否则,从主串则,从主串S的第二个字符开始和模式的第二个字符开始和模式T的第一个字符进行的第一个字符进行比较,重复上述过程,若比较,重复上述过程,若T中的字符全部比较完毕
15、,则说明中的字符全部比较完毕,则说明本趟匹配成功;否则匹配失败。本趟匹配成功;否则匹配失败。模式匹配问题的特点:模式匹配问题的特点:算法的一次执行时间不容忽视:问题规模通常很算法的一次执行时间不容忽视:问题规模通常很大,常常需要在大量信息中进行匹配;大,常常需要在大量信息中进行匹配;算法改进所取得的积累效益不容忽视:模式匹配算法改进所取得的积累效益不容忽视:模式匹配操作经常被调用,执行频率高。操作经常被调用,执行频率高。si si tj模式模式T主串主串Sij 回溯回溯i 回溯回溯jBF算法的基本思想图解算法的基本思想图解本趟匹配开始位置本趟匹配开始位置第第第第3 3章章章章 特殊线性表特殊线
16、性表特殊线性表特殊线性表串串串串 si 主串主串S模式模式Tji tjBF算法的基本思想图解算法的基本思想图解第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串 si 主串主串Si tj模式模式Tj tjBF算法的基本思想图解算法的基本思想图解第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串1.在串在串S和串和串T中设比较的起始下标中设比较的起始下标i和和j;2.循循环环直直到到S中中所所剩剩字字符符个个数数小小于于T的的长长度度或或T的的所所有字符均比较完有字符均比较完 2.
17、1 如如果果Si=Tj,继继续续比比较较S和和T的的下下一一个个字字符符;否则否则 2.2 将将i和和j回溯,准备下一趟比较;回溯,准备下一趟比较;3.如如果果T中中所所有有字字符符均均比比较较完完,则则匹匹配配成成功功,返返回回匹匹配配的的起起始始比比较较下下标标;否否则则,匹匹配配失失败败,返返回回0;BF算法用伪代码算法用伪代码:第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串int BF(char S,char T)i=1;j=1;/设置比较的起始下标设置比较的起始下标 while(i=S0)&(jT0)return(i-j+1);/返回本趟匹配返回本趟匹配 e
18、lse return 0;/的起始下标的起始下标 /S0、T0分别存放串分别存放串S和串和串T的长度的长度BF C+算算法法int BF(char S,char T)i=1;j=1;start=1;while(i=S0&jT0)return start;else return 0;第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串设设主主串串s=“ababcabcacbab”,模模式式t=“abcac”,BF算算法的匹配过程如图法的匹配过程如图:a b a b c a b c a c b a ba b
19、 c 结结论论:i=3,j=3失失败败;i回溯到回溯到2,j回溯到回溯到1第第1趟趟ijijijij第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串a b a b c a b c a c b a baijij第第2趟趟i=2,j=1失败失败i回溯到回溯到3,j回溯到回溯到1第第3趟趟a b a b c a b c a c b a ba b c a ci=7,j=5失败失败i回溯到回溯到4,j回溯到回溯到1ijijijijijji第第第第3 3章章章章 特殊线性表特殊线性表特殊线性表特殊线性表串串串串第第4趟趟a b a b c a b c a c b a baiji=4
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 工学 第三
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【胜****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【胜****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。