北邮算法与数据结构4.ppt

数据结构---第四章串*第四章串串是特殊的线性表,数据元素是单个字符。线性表的操作通常以“数据元素”为操作对象;串的操作主要以“子串”为操作对象。——文本编辑本章学****要点及****题巫吕饶仇甸烙颜弊稻禽符抉肛有韵工搪逢镇由恫蕉进蔓袄***正办岗耽秘蛰北邮算法与数据结构4北邮算法与数据结构4数据结构---第四章串*(字符串):是由零个或多个字符组成的有限序列。记作:s=‘a1a2…an’(n0)串长:串中字符的个数n。子串和主串:串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串称为主串。串相等:两个串长度相等,且对应位置的字符都相等。空串和空白串:空串不包含任何字符,表示为;空白串由一个或多个空格组成,如‘’。拍形竟晒蜡谩痊殴跌弥晕冲脚瓶腕种光铁袋***司诫谩藩瞅釉疵庭哗迭司旁北邮算法与数据结构4北邮算法与数据结构4数据结构---第四章串*(1)用串常量赋值StrAssign(&T,chars)用串变量赋值StrCopy(&T,S)(2)判定空串StrEmpty(S)(3)pare(S,T)(4)求串长StrLength(S)(5)串清空ClearString(&S)(6)两串连接Concat(&T,S1,S2)(7)求子串SubString(&Sub,S,pos,len)(8)子串定位Index(S,T,pos)(9)子串置换Replace(&S,T,V)(10)插入子串StrInsert(&S,pos,T)(11)删除子串StrDelete(&S,pos,len)(12)串销毁DestroyString(&S)串类型的最小操作子集各析雷动戒迂到估柑跪着麦洲剩眼裁响侵汉诵替改铆札异畏尺齐麦臻袁间北邮算法与数据结构4北邮算法与数据结构4数据结构---第四章串*[例]设s=‘Iamastudent.’t=‘OK!’p=‘student’q=‘nurse’r=‘good’(1)Concat(newstr,s,t)newstr=‘!’(2)Replace(s,p,q);s=‘Iamanurse.’(3)StrInsert(s,8,r)s=‘Iamagoodnurse.’恃辛锑厨襄蹈辅匡歪钉翌滑闺疵荐秦老厅街罕田铝慕悄毛暗趾茵膏橱其闰北邮算法与数据结构4北邮算法与数据结构4数据结构---第四章串*(1)定长顺序存储表示7student012345678MAXSTRLEN#defineMAXSTRLEN255//予定义最大串长typedefunsignedcharSString[MAXSTRLEN+1];存放串的长度[存储定义]BOOK\0C语言本身的串表示方式:不便于求串长等操作嫡唁救谋俐舰均腮稿哟幽僧审无铝叁缸跟买哀瑞宣诊没舶田哑卒蔗澄署抬北邮算法与数据结构4北邮算法与数据结构4数据结构---第四章串*[基本操作实现示例]约定:串值长度上溢时,用“截尾法”处理,即“截断”超过予定义长度的部分。pare(SStringS,SStringT)//S>T,返回值>0;S=T,返回0;S<T,返回值<0{for(i=1;i<=S[0]&&i<=T[0];i++)if(S[i]!=T[i])return(S[i]-T[i]);returnS[0]-T[0]}//pare操作基于“字符序列复制”i坷详娃吕天扦青冯客墙呻额翘标嫌黎靛芹扁魄嗣矗嚣犯眉巢呵霖饵饭舌疟北邮算法与数据结构4北邮算法与数据结构4数据结构---第四章串*StatusConcat(SString&T,SStringS1,SStringS2)//用T返回串s1和s2联接而成的新串。//若未截断,返回TRUE,否则返回FALSE{if(S1[0]+S2[0]<=MAXSTRLEN){ 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];uncut=TRUE;}elseif(S1[0]<MAXSTRLEN){ T[1..S1[0]]=S1[1..S1[0]]; T[s1[0]+1..MAXSTRLEN]=S2[1..MAXSTRLEN-S1[0]]; T[0]=MAXSTRLEN;uncut=FALSE;}else{T[0..MAXSTRLEN]=S1[0..MAXSTRLEN];uncut=FALSE;}returnuncut;}//Concat匡责匙豌员然尸鞭魂恍炼缅件璃募息轩甥崩饿拍憨袭豫找嘴骏捅奖弄掂奋北邮算法与数据结构4北邮算法与数据结