数据结构---第四章ppt课件

.,1,第四章串,4.1串的概念和基本操作4.2串的存储结构4.3串基本操作的实现4.4串应用示例文本编辑,.,2,4.1串的概念和基本操作,4.1.1串的概念串是特殊的线性表，数据元素是单个字符。串(字符串)是由零个或多个字符组成的有限序列。记作：s=a1a2an(n0)串长串中字符的个数n。子串和主串串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串称为主串。两个串相等的条件：两个串长度相等，且对应位置的字符都相等。空串和空白串空串不包含任何字符,表示为；空白串由一个或多个空格组成，如。,.,3,4.1.2串的基本操作,(1)用串常量赋值StrAssign(2)串复制StrCopy(3)求串长StrLength(4)串连接Concat(5)求子串SubString(6)子串定位Index(7)串比较StrCompare(8)子串置换Replace(9)串插入StrInsert(10)子串删除StrDelete线性表的操作通常以“数据元素”为操作对象；串的操作主要以“串的整体”为操作对象。,.,4,例,设s=Iamastudent.t=OK!p=studentq=nurser=good(1)l=concat(s,t)l=Iamastudent.OK!(2)replace(s=Iamanurse.(3)insert(/C语言中设置串终止符“0”intlength;/串长度SeqString;,WelcometoBeijing!0,SeqStrings;,s.ch,0,1000,s.length=19,.,6,(2)动态存储分配（堆）,利用C语言的动态分配函数malloc和free实现,typedefstructchar*ch;/若串非空，则按实际串长分配/存储区，否则ch为NULLintlength;/串长HString;,HStrings1；,if(!s1.ch=(char*)malloc(12*sizeof(char)error(“overflow”);elses1.ch=“ok!”;s1.length=3;,例,.,7,4.2.2块链存储结构,defineChunkSize80/由用户定义块大小typedefstructchunkcharchChunkSize;structchunk*next;Chunk;typedefstructChunk*head;/串的头指针intlength;/串的长度LinkString;,ABO,OK#,s.head,LinkStrings；,s.length=6,块(chunksize值)大小的讨论:过大，存储密度增大，但一些操作(如插入、删除、替换等)有不便之处，可能会造成大量字符的移动。过小(最小为1)，存储密度下降，便于插入和删除等操作。,f,r,i,d,.,8,4.3串基本操作的实现,高级语言程序设计中的串存储结构通常选择顺序串静态顺序存储约定：串值长度上溢时，用截尾法进行处理动态顺序存储（堆）操作中没有对串长的限制，更为实用(1)voidStrAssign(HString*s,char*str)/用串常量str给串*s赋值if(s-ch)free(s-ch);/释放s原有空间for(len=0;strlen0;len+);/求str串长lenif(len=0)s-ch=NULL;s-length=0;elseif(!(s-ch=(char*)malloc(len*sizeof(char)error(“overflow”);s-ch0.len-1=str0.len-1;s-length=len;/StrAssign,.,9,(2)voidStrCopy(HString*s,HStringt)/将串t的值复制给串*sif(s-ch)free(s-ch);/释放s原有空间if(t.length=0)s-ch=NULL;s-length=0;elseif(!(s-ch=(char*)malloc(t.length*sizeof(char)error(“overflow”);s-ch0.t.length-1=t.ch0.t.length-1;s-length=t.length;/StrCopy,.,10,(3)intStrLength(HStrings)/求s的串长return(s.length);/StrLength(4)intStrCompare(HStrings1,HStrings2)/s1s2,返回值0；s1=s2，返回0；s1s2，返回值ch=NULL;sub-length=0;elseif(!(sub-ch=(char*)malloc(len*sizeof(char)error(“overflow”);sub-ch0.len-1=s.chpos-1.pos+len-2;sub-length=len;elseerror(“no”);/SubString,pos-1,len,0,s.length-1,.,13,(7)intIndex(HStrings,HStringt,intpos)/返回子串t在主串s中从第pos个字符开始的位置。/若不存在，返回值为0。if(poss.length)return(0);i=pos;j=1;/设定主串、子串字符开始比较的位置while(it.length)return(i-t.length);/匹配成功elsereturn(0)/Index,.,14,i,模式匹配的概念：即子串的定位操作。例：s=abcabcdefabcdmnt=efapq匹配失败t=bcd匹配成功，有效位移=5,主串s,子串t,pos,n(s.length),1,m(t.length),i,s,t,pos,n,1,n-m+1,m,j,i-j+1,.,15,4.4串应用示例文本编辑,分析操作对象文本串（行是文本串的子串）基本操作查找插入删除,轻轻的我走了，正如我轻轻的来；我轻轻的招手，作别西天的云彩。那河畔的金柳，是夕阳中的新娘波光里的艳影，在我的心头荡漾。软泥上的青荇，油油的在水底招摇；在康河的柔波里，我甘心做一条水草那树荫下的一潭，不是清泉，是天上虹揉碎在浮藻间，沉淀着彩虹似的梦。寻梦？撑一支长篙，向