第四章-串ppt课件

.,第4章串,.,学习目的要求:,串的基本概念和串的基本运算。串的顺序存储结构、串的链式存储结构和串的索引存储结构。串的顺序存储中的连接、相等判断、取子串、插入、删除和子串查找算法的实现。,第4章串,.,4.1串的基本概念,4.2串的存储结构,4.3串的基本运算,4.4串的应用举例,第4章串,.,4.1串的基本概念,串是一种特殊的线性表，它的数据对象是字符集合，它的每个元素都是一个字符，一系列相连的字符就组成了一个字符串。字符串简称串。记作:s=a1a2a3an（n0）,串的长度:串中字符的数目n称为串的长度。空串:不含任何字符的串称为空串，它的长度n=0，记为s=。子串:串中任意个连续字符构成的序列称为该串的子串，而包含该子串的串称为母串。两串相等:只有当两个串的长度相等，并且各对应位置上的字符都相同时，两个串才相等。,.,4.2串的存储结构,线性表的顺序存储结构和链式存储结构对于串来说都是适用的。,对串的存储一般有两种处理方式：一是将串定义成字符型数组，由串名可以直接访问到串值。串的存储空间是在编译时分配完成的，其空间大小不能更改。这种存储方式称为串的静态存储结构。二是串的存储空间是在程序运行时动态分配的，并可根据需要随时进行再次分配与释放，从而动态地改变其空间的大小，这种方式称为串的动态存储结构。,.,4.2.1串的静态存储结构,串的静态存储结构采用顺序存储结构，简称为顺序串。,串的顺序存储可用一个字符型数组和一个整型变量来表示，其中字符型数组存放串值，整型变量存放串的长度。,typedefstructstring/*定义串顺序存储结构*/charchMAXLEN;intlen;STRING;,4.2串的存储结构,.,当计算机按字（word）单位编址时，一个存储单元由若干个字节组成。这时串的顺序存储结构有非紧缩存储和紧缩存储两种方式。,1.串的非紧缩存储,2.串的紧缩存储,4.2串的存储结构,.,4.2.2串的链式存储结构,串的链式存储结构也称为链串，结构与链表类似，链串中每个结点有两个域，一个是值域（data），用于存放字符串中的字符，另一个是指针域（next），用于存放后继结点的地址。,typedefstructchainnodechardata;structchainnode*next;CHAINNODE;,串的链式存储结构的优点是插入删除运算很方便。,4.2串的存储结构,.,在串的链式存储中，我们常常会考虑串的存储密度。,存储密度=串值所占的存储位/实际分配的存储位,为了提高存储密度，可让每个结点的值域存放多个字符。这种结构也叫做大结点结构。,大结点结构对字符串进行插入或删除运算时，会引起大量的字符移动。,4.2串的存储结构,.,4.2.3串的索引存储结构,串的索引存储结构的构造方法是:首先开辟一块地址连续的存储空间，用于存放各串本身的值。再另外建立一个索引表。在索引表的项目中存放一个串的名称、长度和在存储空间中的起始地址。,例如，有下面4个字符串:a=youb=arec=ad=student采用索引存储结构如图所示。,4.2串的存储结构,.,4.3串的基本运算,串连接:connect（s1，s2）将串s2连接在s1的尾部，形成一个新串。两串相等判断:equal（s1，s2）判断两个串是否相等，若相等返回1，否则返回0。取子串:substring（s，start，len）返回串s中从start开始的、长度为len的字符序列。插入子串:insert（s，s1，i）在串s的第i个位置插入串s1。删除子串:delete（s，i，j）从串s的第i个位置开始，连续删除j个字符。子串定位:match（s，s1）返回子串s1在串s中第一次出现的位置。子串替换:replace（s，s1，i，j）将串s中从第i个位置开始的长度为j的子串用串s1来替换。,.,1.串连接,STRINGconnect（STRINGs1，STRINGs2）STRINGs;inti;if（s1.len+s2.len=MAXLEN）for（i=0;is1.len;i+）/*将s1存放到s中*/s.chi=s1.chi;for（i=0;is.len+1)|(i=i;j-)s.chj+s1.len-1=s.chj-1;for(j=0;js1.len;j+)s.chj+i-1=s1.chj;/*插入s1串到s串指定位置*/s.len=s.len+s1.len;/*s串长度增加*/s.chs.len=0;/*设置字符串结尾标志*/return(s);/*返回s*/,4.3串的基本运算,.,5.删除子串,在串中删除从某一位置开始连续的字符。如在s串中，从第i个位置开始连续删除j个字符。可能出现三种情况:（1）如果i值不在s串范围内，不能删除。（2）从第i个位置开始到最后的字符数不足j个，删除时，不用移动元素，只需修改s串长度即可。（3）i和j都满足要求。删除后，要把后面其余的元素向前移动j位。,4.3串的基本运算,.,STRINGdelete(STRINGs,inti,intj)/*删除子串运算*/intk;if(is.len)/*i值不在s串值范围之内,不能删除*/printf(errorn);return;elseif(s.len-i+1j)/*第i个位置开始到最后的字符数不足j个时*/s.len=i-1;/*只修改s串长度*/else/*i和j都可以满足要求*/for(k=i+j-1;k=s.len;k+)/*元素向前移动j位*/s.chk-j=s.chk;s.len=s.len-j;/*s串长度减j*/return(s);,4.3串的基本运算,.,6.子串定位,串定位运算也称串的模式匹配。所谓模式匹配，就是判断某个串是否是另一个已知串的子串。如果是其子串，则给出该子串的起始位置。如果不是，则给出不是的信息（-1）。,设有一母串s和一子串s1，判断母串s中是否包含子串s1。其判断的基本方法是:从母串s中的第一个字符开始，按s1子串的长度s1.len，与s1子串中的字符依次对应比较。若不匹配，则再从s串中的第二个字符开始，仍按s1子串的长度s1.len，与s1子串中的字符依次对应比较。如此反复进行比较。直到匹配成功或者母串s中剩余的字符少于s1的长度为止。若匹配成功，则返回s1串在s串中的位置。若匹配不成功，则返回函数值-1。,4.3串的基本运算,.,intmatch(STRINGs,STRINGs1)/*子串定位运算*/inti,j,k;i=0;while(i=s.len-s1.len)/*i为s串中字符的位置*/*该循环执行到s串中剩余长度不够比较时为止*/j=i;/*j用作临时计数变量*/k=0;/*用k控制比较的长度小于s1.len*/while(ks1.len)/*比较结束时，未找到匹配字符串，返回标识-1*/,4.3串的基本运算,.,7.串置换,串置换就是把母串中的某个子串用另一个子串来替换。,字符串替换算法可以用删除子串的算法和插入子串的算法来实现。,4.3串的基本运算,.,4.4串的应用举例,文本编辑是串应用的一个典型例子。,在编辑过程中，可以把整个文本看成是一个字符串，也可以把它叫做文本串，那么页就是文本串的子串，行又是页的子串，等等。,.,串是一种数据类型受到限制的特殊的线性表，它的数据对象是字符集合，每个元素都是一个字符，一系列相连的字符组成一个串。串虽然是线性表，但又有其自己的特点，不是作为单个字符进行讨论，而是作为一个整体，即字符串，进行讨论。串的存储方式