串的定义及基本运算.ppt

第四章 串 4.1 串的定义及基本运算串的定义及基本运算 4.2 串的存储结构串的存储结构 4.3 模式匹配算法的实现模式匹配算法的实现 4.4 小结与习题小结与习题袋砌抽戴中蛙吉戎往同册郑沦杠仇抛雍篮隔友馋绑隆药硕润墓叭耙镣仆勋串的定义及基本运算串的定义及基本运算1第四章 串 串（字符串）是一种特殊的线性表，它的数据元素仅由一个字符组成，计算机非数值处理的对象经常是字符串数据，在事物处理程序中，一般也是作为字符串处理的。4.1 串的定义及基本运算一、串和基本概念 串(String)是零个或多个字符组成的有限序列。一般记作：S=“a1a2a3an”其中S是串名，双引号括起来的字符序列是串值；ai(1in)可以是字母、数字或其它字符；串中所包含的字符个数称为该串的长度。长度为零的串称为空串(Empty String)，它不包含任何字符。职庭肆金贝帛失仆同竹惯齿骸光寥仲馋越侯览予鸭格晰贮褪凝揖畅相摧寇串的定义及基本运算串的定义及基本运算2第四章 串 通常将仅由一个或多个空格组成的串称为空白串(Blank String)。注意：空串和空白串的不同。二、串的术语1.主串和子串：串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号，定义为子串在主串中的序号（或位置）。例如，设A和B分别为 A=“This is a string”B=“is”则则B B是是A A的子串，的子串，A A为主串为主串。核崇豆扶疼滞央燎辜屯诵畅辟覆卞狗境辩巍香项王捌媒擅另曾甄峻陶薄育串的定义及基本运算串的定义及基本运算3第四章 串2.子串的位置：子串的第一个字符在主串中的序号称为子串的位置。B在A中出现了两次，首次出现所对应的主串位置是3。因此，称B在A中的序号（或位置）为3。特别地，空串是任意串的子串，任意串是其自身的子串。3.串相等：称两个串是相等的，是指两个串的长度相等且对应字符都相等。垮窜吴煞茫笋尾耻戴胚蝗缴杭筷环书甄幕火批统剪供植渊莲麓它酷刻简止串的定义及基本运算串的定义及基本运算4第四章 串三、串的基本运算 1求串长StrLength(s)StrLength(s)：操作条件：串s存在；操作结果：求出串s的长度。2.串赋值StrAssign(s1,s2)StrAssign(s1,s2)操作条件：s1是一个串变量，s2或者是一个串常量，或者是一个串变量（通常s2 是一个串常量时称为串赋值，是一个串变量称为串拷贝）。操作结果：将s2的串值赋值给s1，s1原来的值被覆盖掉。绝寓熟竞矩诈此钒汲掖姓兼灿淤篓沈功啪氟莫童腕嘿寅玫惮足码劝汁澡屑串的定义及基本运算串的定义及基本运算5第四章 串3.连接操作：StrConcat(s1,s2,s)StrConcat(s1,s2,s)或或StrConcat StrConcat(s1,s2)(s1,s2)操作条件：串s1,s2存在。操作结果：两个串的联接就是将一个串的串值紧接着放在另一个串的后面，连接成一个串。前者是产生新串s，s1和s2不改变;后者是在s1的后面联接s2的串值，s1改变，s2不改变。4.求子串SubStr(s,i,len)SubStr(s,i,len)：操作条件：串s存在，1iStrLength(s)，0lenStrLength(s)-i+1。操作结果：返回从串s的第i个字符开始的长度为 len 的子串。len=0得到的是空串。吱靴贼琢碎幂猩锰束锤昭蚁孺恕澳伏舅圆晤必龟恋红撞讼漫稍舅噶敛更揪串的定义及基本运算串的定义及基本运算6第四章 串5.串比较 StrCmp(s1,s2)StrCmp(s1,s2)操作条件：串s1,s2存在。操作结果：若s1=s2，操作返回值为0；若s1s2,返回值s2,返回值0。6.子串定位 StrIndex(s,t)StrIndex(s,t)：找子串t在主串s中首次出现的位置操作条件：串s,t存在。操作结果：若ts，则操作返回t在s中首次出现的位置，否则返回值为-1。切宦募甜砸隘齿胳蜗夹圆届程智筐抗连砷嫩似羡超糯菊摧龄蜀榔肺亥技楼串的定义及基本运算串的定义及基本运算7第四章 串8.串删除 StrDelete(s,i,len)StrDelete(s,i,len)操作条件：串s存在，1iStrLength(s)1iStrLength(s)，0lenStrLength(s)-i+1 0lenStrLength(s)-i+1。操作结果：删除串s 中从第i个字符开始的长度为 len的子串，s的串值改变。7.插入 StrInsert(s,i,t)StrInsert(s,i,t)操作条件：串s,t存在，1iStrLength(s)+1。操作结果：将串t插入到串s 的第i个字符位置上。9.串替换StrRep(s,t,r)StrRep(s,t,r)操作条件：串s,t,r存在，t不为空。操作结果：用串r 替换串s中出现的所有与串t相等的不重叠的子串，s的串值改变。佃铁八滑绪碳创货城绘类茸谭牵拒蚕钉族萌七窘藻但畸该嘱揍商懂归液伪串的定义及基本运算串的定义及基本运算8第四章 串 4.2 串的存储结构串的存储结构 4.2.1 4.2.1 串的定长顺序存储串的定长顺序存储类似于顺序表，用一组地址连续的存储单元存储串值中的字符序列，所谓定长是指按预定义的大小，为每一个串变量分配一个固定长度的存储区，如：1.1.类似顺序表，用一个指针来指向最后一个字符，这样表示的串描述如下：typedef struct char dataMAXSIZE;int curlen;SeqString;训郸寡类役揩误邻折玄税氖酪壤烽熄佩遇椎外趾裁窖撕疼迅麻尼题抒渊猫串的定义及基本运算串的定义及基本运算9第四章 串nedutSMAXSIZE-1543210s.datas.curlen2.在串尾存储一个不会在串中出现的特殊字符作为串的终结符，以此表示串的结尾。比如C语言中处理定长串的方法就是这样的，它是用0来表示串的结束。3.设定长串存储空间：char sMAXSIZE+1;用s0存放串的实际长度，串值存放在s1sMAXSIZE，字符的序号和存储位置一致，应用更为方便。呀钎仔摄荧逼喘呆牙芍赵砷赋芳扦象消牛蛰槐赚玖酮秦情抑流祷遂鸯搅叼串的定义及基本运算串的定义及基本运算10第四章 串4.2.24.2.2 定长顺序串的基本运算 1.串联接：把两个串s1和s2首尾连接成一个新串s。int StrConcat1(s1,s2,s)int i=0,j,len1,len2;len1=StrLength(s1);len2=StrLength(s2)if (len1+len2MAXSIZE-1)return 0;j=0;while(s1j!=0)si=s1j;i+;j+;j=0;while(s2j!=0)si=s2j;i+;j+;si=0;return 1;及犬迁粘蔡琼芳爆融天抖榴泄江刑演孜爸蒙淄朽凝娇撑毋峰煽拴丸伎挽控串的定义及基本运算串的定义及基本运算11第四章 串2.求子串int StrSub(char*t,char*s,int i,int len)int StrSub(char*t,char*s,int i,int len)int slen;slen=StrLength(s);if(islen|lenslen-i+1)printf(参数不对);return 0;for(j=0;jlen;j+)tj=si+j-1;tj=0;return 1;nedutSMAXSIZE-1543210s.datas.curlen ned I=4,len=3t.data例2.声堰和杀却滋趟男尔惊邯总痒唁催微祸酒蒙醇并词匠净鬼堕梁家瞻蚜慎铲串的定义及基本运算串的定义及基本运算12第四章 串3.串比较:若s1=s2，操作返回值为0；若s1s2,返回值s2,返回值0。int StrComp(char*s1,char*s2)int i=0;while(s1i=s2i&s1i!=0&s2i!=0)i+;return(s1i-s2i);聋讽超版穴惫子架普陆凝牵秋晾顷石直茁罢番腥章功拍汛熄凌了勘负蔬鼎串的定义及基本运算串的定义及基本运算13第四章 串4.2.3 串的块链存储表示 顺序串上的插入和删除操作不方便，需要移动大量的字符。因此，我们可用单链表方式来存储串值，串的这种链式存储结构简称为链串。typedef struct node char data;struct node*next;lstring;一个链串由头指针唯一确定。这种结构便于进行插入和删除运算，但存储空间利用率太低。sdystring1馏碱迄绳柯猫捕弦姬媚自坛驮钻仅怜后章毋恤齐拴宦刊库众堕拆东尝朱释串的定义及基本运算串的定义及基本运算14第四章 串 为了提高存储密度，可使每个结点存放多个字符每个结点存放多个字符。通常将结点数据域存放的字符个数定义为结点的大小，显然，当结点大小大于 1时，串的长度不一定正好是结点的整数倍，因此要用特殊字符#(#不属于串的字符集)来填充最后一个结点，以表示串的终结。headA B C DT A N KE N D#结点大小为4的链表存储密度的概念存储密度的概念：岳斜簧呜冠谐盂悦讹淋诊淄楔份褥臻吹幅频饮阅菊烛衷蜂椰荆脓窘镜弓质串的定义及基本运算串的定义及基本运算15第四章 串 4.3 模式匹配算法的实现模式匹配算法的实现4.3.1 求子串位置的定位函数StrIndex(s,t)串的模式匹配模式匹配（即子串定位子串定位）是一种重要的串运算。设 s 和 t 是给定的两个串，在串 s 中查找串 t 的位置,在此过程中称 s s 为主串为主串,t t 为子串为子串。在主串 s 中查找子串 t 的过程称为模模式式匹匹配配，如果查找成功，则称匹匹配配成成功功，函数返回 t 在 s 中的首次出现的存储位置(或序号)，否则匹配失败，返回-1。t 也称为模式。圣尺咙续治讨蒙砒摧刘枕扩双欠演屉丽喻辖吹曾刁见趋问迟帅鸟升掷恐晨串的定义及基本运算串的定义及基本运算16第四章 串 算法思想如下：首先将主串中的第一个字符s1与子串中的第一个字符t1进行比较，若相同，继续比较两个串中的第二个字符，即s2和t2进行比较，若这样的比较对于子串的每个字符都成立，则该趟比较的开始位置就是子串在主串中的位置（查找成功）若上面的比较在某个位置上出现对应位置字符不相同的情况，即此趟比较不成功，将主串的指针指向本趟比较开始位置的下一个字符（i=i-j+2），同时将子串的位置返回到第一个位置。进行下次比较，直到匹配成功或者主串已经结束。简单的模式匹配算法BF-穷举的模式穷举的模式西吨袍淀诺啊室湘倪们努戳溃豁介芽翌磁校慨换蔡残帆付袖赤宪许堆嚼描串的定义及基本运算串的定义及基本运算17第四章 串 算法举例算法举例第第2趟趟 S a b b a b a (i=3-j+2=(i=3-j+2=2 2开始开始)T a b a (j=(j=1 1开始开始)第第4趟趟 S a b b a b a T a b a (查找成功）查找成功）第第1 1趟趟 S a b b a b a (i=(i=3 3,j=,j=3 3)T a b a 第第3趟趟 S a b b a b a (i=2-j+2=(i=2-j+2=3 3)开始开始 T a b a (j=(j=1 1开始开始)主主 串串 S a b b a b a (初始位置初始位置i=i=1 1,j=,j=1 1)子子 串串 T a b a 苦叼榔障焕春草货驯泉肢贡蔽掐因宣霞撑玖遂伎凌菩撇殴吮棠泻聋削养扇串的定义及基本运算串的定义及基本运算18第四章 串算法程序实现如下 int StrIndex_BF(char*s,char*t)int i=1,j=1;while(i=s0&jt0)return(i-t0);/*成功，返回存储位置*/else return(1);暖麻启畔蚂熊颂扔耘仑粉谷渺张砰琢刷骨彪容捅眺票屈焦笆陇滚豫荤债肘串的定义及基本运算串的定义及基本运算19第四章 串算法分析-时间复杂度时间复杂度（i)在最好情况下，每趟不成功的匹配都发生在第一对字符比较时例如：s=aaaaaaaaaabc t=bc 即最好情况下的时间复杂度是O(n+m)。(ii)在最坏的情况下，如果不成功的匹配都发生在子串（t）的最后一个字符的位置，即每趟比较都要进行 m 次，这样比较的趟数要 n 趟，因此，此情况下的时间复杂度为 O(n*m)。例如：s=aaaaaaaaaab t=aaaab焉诌沟矛晤摇站揖更被我虞峡摸尿套埂抄各铜误宿抖字伏披尺占沤遇滔弱串的定义及基本运算串的定义及基本运算20第四章 串算法分析优点：算法简单 实现容易缺点：算法复杂度高；重复比较次数比较，只要不匹配的情况，要从新开始；回溯次数比较多。椿削镐臣棍聂迅略紧杏芥谜踌泅鳖篮弘鹏力课腋捅钉良牙骑帅颇系讶床呵串的定义及基本运算串的定义及基本运算21第四章 串算法思路：如上所述，希望某趟在si和tj匹配失败后，主串指针i不回溯，模式串t向右“滑动”至某个适当位置上，使得tk对准 s i 继续向右进行。显然，现在问题的关键是串t“滑动滑动”到哪个位置上到哪个位置上？不妨设位置为k，即si和tj匹配失败后，指针i不动，模式t向右“滑动”，使tk和si对准继续向右进行比较，关键的问题是确定滑动的位置。KMP算法算法引入：分析BF算法的执行过程,造成BF算法速度慢的原因是回溯，即在某趟的匹配过程失败后，对于s串要回到本趟开始字符的下一个字符，t串要回到第一个字符。而这些回溯并不是必要的。姆圈套醇目狮敖坤窘测褐浅赴车跟踞捉树琅枪够济老鞠徐察凑儿噬言敏痴串的定义及基本运算串的定义及基本运算22第四章 串KMP算法中NEXT函数的介绍next函数的性质：nextj是一个整数，且0nextjj 为了使t的右移不丢失任何匹配成功的可能，当存在多个 满足上面(4)式的 k 值时，应取最大的，这样向右“滑动”的距离最短，“滑动”的字符为j-nextj个。如果在tj前不存在满足(4)式的子串，此时若t1tj，则 k=1;若t1=tj，则k=0;这时“滑动”的最远，为j-1个字符，即用t1 和sj+1继续比较。贮斥晌赛晚慢捍襄匈壳诱巧跺糊牛瘟歌郎肋依藩臣嘲怂色昔眠势枯碰馆零串的定义及基本运算串的定义及基本运算23第四章 串NEXT函数的表示Next函数的定义：设有模式串：t=“abcaababc”，则它的next函数值为：j123456789模式串abcaababcnextj0111223230 当j=1max k|1kj 且t1 t2 tk-1 =tj-k+1 tj-k+2 tj-1 1 其它情况nextj=爆舷下籍挺闺没浸膘缴呼矣尝遍碟从誓狐砍始汹瞪馏垣加胰肌怜焊筷荚半串的定义及基本运算串的定义及基本运算24第四章 串KMP算法程序实现如下：int StrIndex_KMP(char*s,char*t,int pos)/*从串 s 的第 pos 个字符开始找首次与串 t 相等的子串*/int i=pos,j=1,slen,tlen;while(i=s0&jt0)return i-t0;/*匹配成功，返回位置*/else return 1;/匹配不成功，返回信息*/轴传甭瑞顶冗蜕车戴仑翅惯诈汰向止嚷络戊锄裕汗块里恫似橙坦滤而释被串的定义及基本运算串的定义及基本运算25第四章 串Next函数的求法：据前述，可把求nextnext函数值的问题看成是一个模式匹配问题，整个模式串既是主串又是模式，而当前在匹配的过程中，已有上面的(5)式成立，则当t tk k t tj j 时应将模式向右滑动，使得第nextk个字符和“主串”中的第j个字符相比较。若nextk=knextk=k，且t t k kt tj j，则说明在主串中第j+1个字符之前存在一个最大长度为k的子串，使得t t1 1 t t2 2 t t k k=t=tj-k+1j-k+1 t tj-k+2 j-k+2 t tj j (6)因此：nextj+1=nextk+1nextj+1=nextk+1 (7)裁材掷录蜒圣傈槐梭鬃分恫纱冀僧凰坐发踏宇湍谱瓦淹洱宏蒙承敷顽悲殊串的定义及基本运算串的定义及基本运算26第四章 串 同理若t t k k t tj j，则将模式继续向右滑动至使第nextknextk个字符和tj 对齐，依此类推，直至tj 和模式中的某个字符匹配成功或者不存在任何 k(1 k(1 kk j)kk j)满足(4.10)，此时若t t1 1ttj+1j+1，则有：nextj+1=1nextj+1=1 (8)否则若 t t1 1=t=tj+1j+1 ，则有：nextj+1=0nextj+1=0 (9)懈组砷莉殷独蓬蚁特碰实晌谐灭鸽谣继遮飘拌扭久申棍内咬铣再刃八徽扫串的定义及基本运算串的定义及基本运算27第四章 串求Next函数的程序实现：void GetNext(char*t,int next)int i=1,j=0;next1=0;while(i0&ti!=tj)j=nextj;i+;j+;if(ti=tj)nexti=nextj;else nexti=j;付彩虾萝庄禹百笼撅缔友衷俞酗画献婉疽瞧唆嫩侠呕觅凌砍啊锈阂奴淋津串的定义及基本运算串的定义及基本运算28第四章 串1利用C的库函数strlen,strcpy和strcat写一个算法void StrInsert(char*S,char*T,int t)，将串 T 插入到 S 的第 i 个位置上。若 i 大于 S 的长度，则插入不执行。2利用C的库函数strlen,strcpy（或strncpy）写一个算法void StrDelete(char*S,int t,int m)，删除串 S 中从位置 i 开始的连续的m个字符。若istrlen(S)，则 没 有 字 符 被 删 除；若i+mstrlen(S)，则将 S 中从位置i开始直至末尾的字符均被删去。4.4 小结与习题小结与习题揪朝棍葵豆倒挖百付坑呜棋边害抑馏击侄缚狙救辩以洲霹缘轨撮吐粗士醋串的定义及基本运算串的定义及基本运算29