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

数据结构,.,2,第四章串,.,3,4.1串的抽象数据类型的定义,4.2串的表示和实现,.,4,4.1串的抽象数据类型的定义,串：是由零个或多个字符组成的有限序列。s=a1a2an空串：零个字符的串。长度：串中字符的数目。子串：串中任意个连续的字符组成的子序列。主串：包含子串的串。位置：通常称字符在序列中的序号为该字符在串中的位置。,.,5,4.1串的抽象数据类型的定义如下：,ADTString,数据对象：,Dai|aiCharacterSet,i=1,2,.,n,n0,数据关系：,R1|ai-1,aiD,i=2,.,n,串是有限长的字符序列，由一对单引号相括，如:astring,.,6,基本操作：,StrAssign(,SubString(sub,commander,1,9),SubString(sub,commander,9,1),求得sub=r,求得sub=commander,.,13,SubString(sub,commander,4,7)sub=?,SubString(sub,beijing,7,2)=?sub=?,SubString(student,5,0)=,起始位置和子串长度之间存在约束关系,长度为0的子串为“合法”串,.,14,Index(S,T,pos)初始条件：串S和T存在，T是非空串，1posStrLength(S)。操作结果：若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个字符之后第一次出现的位置;否则函数值为0。,.,15,假设S=abcaabcaaabc,T=bca,Index(S,T,1)=2;,Index(S,T,3)=6;,Index(S,T,8)=0;,“子串在主串中的位置”意指子串中的第一个字符在主串中的位序。,.,16,Replace(/0号单元存放串的长度,一、串的定长顺序存储表示,.,26,按这种串的表示方法实现的串的运算时，其基本操作为“字符序列的复制”,串的实际长度可在这个预定义长度的范围内随意设定，超过予定义长度的串值则被舍去，称之为“截断”,特点:,.,27,StatusConcat(SStringS1,SStringS2,SString/Concat,例如：串的联接算法中需分三种情况处理：,T1.S10=S11.S10;TS10+1.S10+S20=S21.S20;T0=S10+S20;uncut=TRUE;,if(S10+S20=MAXSTRLEN)/未截断,elseif(S10MAXSTRSIZE)/截断,else/截断(仅取S1),T1.S10=S11.S10;TS10+1.MAXSTRLEN=S21.MAXSTRLENS10;T0=MAXSTRLEN;uncut=FALSE;,T0.MAXSTRLEN=S10.MAXSTRLEN;/T0=S10=MAXSTRLENuncut=FALSE;,.,28,typedefstructchar*ch;/若是非空串，则按串长分配/存储区，否则ch为NULLintlength;/串长度HString;,二、串的堆分配存储表示,.,29,通常，C语言中提供的串类型就是以这种存储方式实现的。系统利用函数malloc()和free()进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为“堆”。C语言中的串以一个空字符为结束符，串长是一个隐含值。,这类串操作实现的算法为:先为新生成的串分配一个存储空间，然后进行串值的复制。,.,30,三、串的块链存储表示,也可用链表来存储串值，由于串的数据元素是一个字符，因此用链表存储时，通常一个结点中存放的不是一个字符，而是一个子串。,存储密度=,数据元素所占存储位,实际分配的存储位,.,31,#defineCHUNKSIZE80/可由用户定义的块大小typedefstructChunk/结点结构charchCHUNKSIZE;structChunk*next;Chunk;typedefstruct/串的链表结构Chunk*head,*tail;/串的头和尾指针intcurlen;/串的当前长度LString;,.,32,例如:在编辑系统中，整个文本编辑区可以看成是一个串，每一行是一个子串，构成一个结点。即:同一行的串用定长结构(80个字符),行和行之间用指针相联接。,实际应用时，可以根据问题所需来设置结点的大小。,.,33,本章作业,1.两个串相等的充分必要条件是什么？2.空串与空格串是相同的吗？为什么？,.,34,习题一,1.for(i=1;i=n;+i)for(j=1;j=n;+j)cij=0;for(k=1;k=n;+k)cij+=aik*bkj;O（n3）2.for(i=1;i=n;i=2*i)+x;O（log2n）,3.s=0;for(i=0;i=n;i+)for(j=0;jnext;（2）p-next=s;（3）t=p-data;（4）p-data=s-data;（5）s-data=t;9.在一个单链表中删除p所指结点时，应执行以下操作：q=p-next;p-data=p-next-data;p-next=p-next-next;free(q);,.,37,习题一,10.从顺序表中删除所有值为x的元素。voiddelall(Sqlist,.,38,习题一,11.某百货公司仓库中有一批电视机，按其价格从低到高的次序构成了一个单链表存于计算机中，链表的每个结点指出同样价格的若干台，现在又新到m台价格为h元的电视机入库，试完成该算法。typedefstructLNodefloatcost;intnum;StructLNode*next;LNode,*LinkList;VoidTvsets(LinkList,.,39,习题一,12若一个栈的输入序列是1，2，3，n，输出序列的第一个元素是n，则第i个输出元素是（D）。A不确定Bn-iCn-i-1Dn-i+113设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5、e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的顺序是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是（C）。A6B4C3D214一个栈的入栈序列是1，2，3，4，5，则栈的不可能的输出序列是（C）。A54321B45321C43512D1234515在操作序列push(1)、push(2)、pop、push(5)、push(7)、pop、push(6)之后，栈顶元素和栈底元素分别是什么？（push(k)表示整数k入栈，pop表示栈顶元素出栈。）【解答】栈顶元素为6，栈底元素为1。,.,40,习题一,16栈和队列是两种特殊的线性表，栈的操作特性是（），队列的操作特性是（），栈和队列的主要区别在于（）。【解答】后进先出，先进先出，对插入和删除操作限定的位置不同17循环队列的引入是为了克服