数据结构课件第5章.ppt

第 5 章 串,5.1 串的应用实例及概念5.2 串的存储结构5.3 串的基本操作 5.4 串的ADT定义及类定义 5.5 实习五：串的演示程序,5.1 串的应用实例及概念,在各种高级语言的编译程序中，源程序和目标程序都被处理成字符串数据，各源程序编辑器的功能强弱有差异，但其基本操作是一致的，一般都包括串的查找、插入及删除等。例如，在Delphi中创建一个新的源程序文件，并在其中输入以下内容：,typeTstring=class private private declaration public public declaration end;,图 5.1 Delphi中源程序编辑器提供的字符串替换功能,一般地，串（字符串）被定义为由零个或多个字符组成的有限序列。记为：s=a1 a2 an(n0)其中，s是串的名，也称为串变量。单引号内的字符序列为串值。ai(1in)可以是字母、数字或其他字符。串中字符的数目n称为串的长度。零个字符的串称为空串(null string)，长度为零。,串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串称为主串。通常称字符在序列中的序号为该字符在串中的位置。子串在主串中的位置可以用子串的第一个字符在主串中的位置来表示。例如,假设a、b、c、d为如下的四个串：a=Data b=Structurec=Data Structure d=Data Structure,则它们的长度分别为4、9、13和14，并且a和b都是c和d的子串，a在c和d中的位置都是1。而b在c中的位置是5，在d中的位置则是6。,5.2 串的存储结构,5.2.1 顺序存储结构 和线性表的顺序存储结构相类似，串的存储结构可以用一组地址连续的存储单元存储串的字符序列。利用数组，可将这种数据类型描述如下：,const maxlen=允许的串最大长度;type strtp=record curlen:0.maxlen;ch:array 1.maxlen of char;end;,图 5.2 串的顺序存储结构(a)非紧缩方式；(b)紧缩方式,5.2.2 链式存储结构 和线性表的链式存储结构相类似，串的存储结构也可采用链式存储结构，即用线性链表来存储串值。在这种存储结构下，存储空间被分成一系列大小相同的结点，每个结点用data域存放字符，link域存放指向下一个结点的指针。这样，一个串就可以用一个线性链表来表示。由于串结构的特殊性，在串的链表结构中常常涉及到结点的大小问题，即如何确定结点的data域存放字符的个数问题。通常情况下，结点的大小为4或1，如图5.3所示。当结点的大小为4时,串所占用的结点中最后一个结点的data域不一定全被串值占满，这时通常补上“”或其他的非串值字符。,图 5.3 串的链式存储结构(a)节点大小为4的链表；(b)节点大小为1的链表,串的链式存储结构可定义如下：const nodesize=定义的结点大小;type link=node;node=record ch:array1.nodesize of char;next:link;end;linkerstring=record head:link;length:integer;end;,图 5.4 串存储的堆结构示例(a)存储空间；(b)映像空间,1.求子串操作 设源串为s，则求子串操作为将源串s的一部分复制到新串sub内。假设源串s:strtp已在外部进行了说明，截取的子串位置为pos:integer，截取长度为len:integer，并且取出的子串被复制入串sub:strtp中，则子串操作过程如下：procedure substring(pos,len:integer;var sub:strtp);功能：在源串s中截取从pos开始的长len的子串，并将其复制到字符串sub中。,5.3 串的基本操作,处理过程：(1)若截取子串的位置或长度超出合法值，即当pos s.curlen 或pos,len 1时，显示出错信息并终止。(2)若截取子串的位置在串长范围以内，且截取长度未超出最大可供截取长度，即当1poss.curlen且1lens.curlen-pos+1时，将源串s中从pos开始的长度为len的内容复制到串sub中，如图5.5所示。,图 5.5 求子串操作示意图,(3)若截取子串的位置在串长范围以内，但截取长度超出最大的可供截取长度，即当1poss.curlen且len s.curlen-pos+1时，按截尾法处理：将源串s从pos开始到串尾的全部内容复制给串sub。以下是该过程的程序清单：procedure substring(pos,len:integer;var sub:strtp);将源串s中指定位置的子串var i:integer;复制入串subbegin,if(pos s.curlen)or(pos s.curlen-pos+1 then len:=s.curlen-pos+1;最大可供截取长度 sub.curlen:=len;设定sub串长 for i:=1 to len do 复制源串s从pos开始长度为len的子串至sub sub.chi:=s.chpos+i-1;end;end;,2.删除操作 删除操作可删除源串s中指定范围内的串值。设源串s:strtp已在外部进行了说明，删除起始位置为pos:integer，删除长度为len:integer，则删除操作过程如下：procedure delete(pos,len:integer);功能：在源串s中删除从pos开始的长度为len的子串。,图 5.6 删除子串操作示意,处理过程：(1)若删除起始位置或长度超出合法值，即当pos s.curlen 或pos,len s.curlen-pos+1时，按截尾法处理：将源串s中从pos开始到串尾的全部内容删除。,以下是该过程的程序清单：procedure delete(pos,len:integer);将源串s中指定范围内的子串删除var i:integer;begin if(pos s.curlen)or(pos s.curlen-pos+1 then len:=s.curlen-pos+1;最大可供删除长度 for i:=pos to s.curlen-len do 将源串s从pos+len开始至 s.chi:=s.chlen+i;串尾的子串复制到从pos开始的位置 s.curlen:=s.curlen-len;重新设置s的串长 end;end;,3.插入操作 插入操作可将一个串插入源串s中的指定位置。设源串s:strtp已在外部说明，插入的串为t:strtp，插入位置为pos:integer，则插入操作过程为procedure insert(pos:integer;t:strtp);功能：在源串s中pos指示的位置之后插入串t。,处理过程：(1)当插入位置超出合法值或s串长已达最大值，即当pos maxlen 或s.curlen=maxlen时，显示出错信息并终止。(2)当插入位置在s串长范围以内，即当 1poss.curlen时，则将串t插入源串s中pos之后的位置，如图 5.7 所示。其中，如s、t两串之和超过串所允许的最大长度，则可采用截尾法截去超长部分，如图 5.8 所示。,图 5.7 插入子串操作示意,图 5.8 插入子串操作示意图(发生截尾),(3)当插入位置在串长范围以外但小于等于串长最大值，即当s.curlen posmaxlen时，则将串t连接至s的尾部，并采用截尾法截去超长部分。以下是该过程的程序清单：,procedure insert(pos:integer;t:strtp);在串s中的指定位置pos后插入串tvar i,len,n:integerbegin if(pos maxlen)or(pos s.curlen then pos:=s.curlen;则将其调整至串s的末尾 if s.curlen+t.curlenmaxlen then len:=s.curlen+t.curlen else len:=maxlen;计算新串长,n:=len-pos-t.curlen;if n 0 then 若新串长大于插入点之前的字符长度与 for i:=1 to n do 串t的长度之和，则将插入点之后的n个 s.chlen-i+1:=s.chpos+n-i+1;字符移至新串串尾 for i:=1 to t.curlen do 将串t复制入串s if pos+i len then break else s.chpos+i:=t.chi;s.curlen:=len;重新设置s的串长 end;end;,4.子串定位操作 子串定位操作可求取源串s中某一特定子串的位置。子串定位操作通常称为串的模式匹配，其中，要求被定位的子串称为模式。模式匹配是各种串处理系统中最重要的操作之一。如在本章开头提到的文本编辑器和信息检索的实例中，均涉及到串的模式匹配。实现模式匹配的最简单办法就是从s的第一个字符开始试着对t进行匹配，直至匹配成功或搜寻到串尾。设串s:strtp已在外部说明，被要求定位的子串（模式串）为t:strtp，则子串定位操作可被表达成如下函数：function position(t:strtp):integer;,功能：在源串s中查找与t相同的子串，若查找成功，则返回该子串的位置，否则返回0。处理过程:(1)从第s的一个字符开始对串t进行匹配。(2)若失败，则从s的下一位置的字符开始进行匹配。(3)重复(2)，直至匹配成功或搜寻到s的串尾。,为实现这一处理过程，我们可以设置两个指针i、j分别用来指示串s和t中当前正在比较的字符，并在算法开始时令i、j分别指向s和t的第一个字符。当i未到s串尾时，可作以下操作：（1）若i、j指示的字符相等，且j已达到串t的尾部，则匹配成功，返回字符串的位置。（2）若i、j指示的字符相等，且j还未达到串t的尾部，则i、j分别指向s和t中的下一个字符。（3）若i、j指示的字符不等，则匹配失败，i指向s中该趟匹配开始位置的下一个字符，j指向t的第一个字符，开始下一轮匹配。,当i已达到s最后一个字符而还未匹配成功，则s中无与t相等的子串。程序如下：,function position(t:strtp):integer;求串t在源串s中的位置var i,j:integer;begin i:=1;j:=1;i,j分别用来指示串s,t中当前比较的字符位置 while(i=s.curlen)and(j=t.curlen)do if s.chi=t.chj then 如果当前位置上的字符相同，则比较下一位字符,begin i:=i+1;j:=j+1;end else 若当前位置上的字符不相同，则指针i,j后退，重新开始匹配 begin i:=i-j+2;j:=1;end;若j已到t的串尾，则匹配成功，返回子串位置，否则返回0 if j t.curlen then position:=i-t.curlen else position:=0;end;,图 5.9 模式匹配过程,5.替换操作 替换操作可将源串s中某一特定子串用另外一个串替换。要成功实现替换操作，必须首先查找t在s中的位置。这可通过以上模式匹配函数实现。若匹配成功，下一步则是进行替换。替换可通过在s中先删除子串t，然后再插入串s来实现。设源串s:strtp已在外部说明，被要求替换的串为t:strtp，替换串为r:strtp，则替换操作过程如下：procedure replace(t,r:strtp);功能：在串s中用子串r替换子串t。,处理过程：(1)查找子串t在s中的位置。(2)在s中删除子串t。(3)在s中原来t的位置上插入子串r。程序清单如下：procedure replace(t,r:strtp);在源串s中，用串r替换子串tvar pos:integer;begin 调用模式匹配函数求子串t的位置 pos:=position(t);若匹配失败则显示出错信息 if pos=0 then showmessage(can not find substring)else begin delete(pos,t.curlen);删除子串t insert(pos-1,r);插入串r，完成替换 end;end;,5.4 串的ADT定义及类定义,5.4.1 串的ADT定义 根据面向对象程序设计的原则，实现部分与接口部分两者应该分离。接口部分可以用ADT定义即抽象数据类型定义来进行描述。一种数据类型的ADT定义由数据元素、结构及操作三部分组成。以下是串的ADT定义：元素：ai同属于字符类型，i=1,2,n n0。结构：元素间呈线性关系。,操作：常用的串的基本操作有以下几种：(1)create(s,ss)：初始化操作。建立一个串s，其值为字符序列ss。(2)equal(s,t)：判等函数。若s和t相等，则返回true，否则返回false。(3)length(s)：求长函数。其函数值为s中字符的个数。(4)substring(s,start,len)：求子串操作。若 1startlength(s)+1且 0lenlength(s)-start+1,则返回函数值为串s中第start个字符起，长度为len的字符序列；否则返回一个特殊的串常量。,(5)delete(s,pos,len)：删除操作。当 1poslength(s)且0lenlength(s)-pos+1 时,从串s中删去第pos个字符起长度为len的子串。(6)insert(s,pos,t):插入操作。当 1poslength(s)+1 时,在串s的第pos个字符之前插入串t。(7)position(s,t)：定位函数。若在主串s中存在和t相等的子串，则返回s中第一个这样的子串在主串s中的位置，否则函数值为 0。(8)replace(s,t,v)：置换操作。操作结果是以串v替换所有在串s中出现的和非空串t相等的子串。,5.4.2 顺序串的类定义,在采用顺序存储的串的类定义中，数据部分包括一个字符数组和一个有界整型变量，用以存放串值及串长。相应的操作包括初始化(constructor init)，求子串(procedure substring)，删除(procedure delete)，插入(procedure insert)，子串定位(function position)和替换(procedure replace)等。这些过程或函数被定义成公有型，可以向外部提供服务。顺序串的类定义可定义如下：,const maxlen=允许的串最大长度;Tstring=classprivate curlen:0.maxlen;ch:array 1.maxlen of char;,public procedure init(s:string);procedure substring(pos,len:integer;var sub:Tstring);procedure delete(pos,len:integer);procedure insert(pos:integer;t:Tstring);function position(t:Tstring):integer;procedure replace(t,r:Tstring);end;implementationvar s1:Tstring;proceduce Tstring.init(s:string),procedure Tstring.substring(pos,len:integer;var sub:Tstring);procedure Tstring.delete(pos,len:integer);procedure Tstring.insert(pos:integer;t:Tstring);function Tstring.position(t:Tstring):integer;procedure Tstring.replace(t,r:Tstring);,5.5 实习五：串的演示程序,5.5.1 问题说明 字符串可作为一种变量类型出现在程序设计语言中。有关串的基本操作包括插入、删除、定位、替换等，这些操作的特点是将串作为一个整体加以操作。编制一个GUI教学演示程序，演示字符串的各种操作的执行效果。,5.5.2 界面外观及功能要求,图 5.10 串的操作演示程序操作屏幕,按初态按钮时，可按编辑框中指定的字符串生成一个初始字符串，并作为当前字符串显示在绘图板中。按插入按钮时，可按数字增减器中指定的位置，在当前字符串中插入编辑框中指定的字符串。按删除按钮时，可按数字增减器中指定的位置与长度，删除当前字符串中相应的子串。按替换按钮时，可按编辑框中指定的被替换的字符串和要替换的字符串，对当前字符串执行替换操作，即将其中的被替换的字符串替换成要替换的字符串。,5.5.3 实现要点(1)采用顺序的存储结构来表示一个串，并将串定义成一个类。(2)对串的初始化操作设置一个字符串类型的参数，并可按该参数中的字符串来生成一个初始状态的串。(3)删除操作是指将被删除的子串后的部分向前移动。插入操作是指将插入位置之后的部分向后移动，然后再插入要插入的子串。替换操作是指先执行定位操作，然后按该位置执行删除后再插入。,5.5.4 类定义 将串定义成一个类，且采用顺序的存储结构，数据部分包括一个字符数组和一个有界整型变量，用以存放串值及串长，分别取名为ch及curlen。相应的操作为初始化(procedure init(s:string)，定位(function position(t:Tstring):integer)，删除(procedure dele(pos,len:integer)，插入(procedure inst(pos:integer;t:Tstring)，替换(procedure replace(t,r:Tstring)及显示(procedure prnt)等。串的类定义Tstring可定义如下：,Tstring=class private ch:array1.maxlen of char;curlen:0.maxlen;public procedure init(s:string);procedure prnt;function position(t:Tstring):integer;procedure dele(pos,len:integer);procedure inst(pos:integer;t:Tstring);procedure replace(t,r:Tstring);end;,5.5.5 类的实现(1)初始化过程(procedure init(s:string)：由参数s来建立字符串的顺序存储结构，即执行：len:=length(s);for i:=1 to len do chi:=si;curlen:=len;,(2)定位函数(function position(t:Tstring):integer:)可确定字符串t在当前串中的位置。若t为当前串的一个子串，则返回该子串在当前串中的位置，否则返回 0。其处理过程为：从当前串的第一个字符与t中的第一个字符开始比较，若相等，则继续逐个比较后继字符，否则从主串中本次开始位置的下一个字符位置开始继续比较，重复执行直至t中的每个字符依次与当前串中的字符相等则成功返回位置序号；或者直至当前串中的字符全都比较完仍不相等则不成功返回 0。,(3)删除过程(procedure dele(pos,len:integer)：)可按参数中指定的子串的开始位置及长度删除当前串中相应的子串。其处理过程为：检查参数是否合法，若不合法，则显示相应的信息或进行适当的调整。将删除串之后的部分前移。形成当前串的新的长度。,(4)插入过程(procedure inst(pos:integer;t:Tstring)：可按参数中指定的位置将参数中指定的字符串插入到当前字符串中。其处理过程为：检查位置参数是否合法以及当前字符串是否溢出，若合法且溢出，则进行以下的处理。求后移子串的长度n，若n0，则将该子串后移（从后向前逐个移动）。将插入串移入到当前串中相应的位置（若发生溢出则截断之）。形成当前串的新的长度。,(5)替换过程(procedure replace(t,r:Tstring)：按参数中指定的被替换的字符串和替换的字符串，对当前字符串执行替换操作，即将其中的被替换的字符串替换成要替换的字符串。其处理过程为：执行定位操作，求被替换的字符串在当前串中的位置，若被替换串存在，则执行删除操作，删除被替换串t，执行插入操作插入要替换串r。(6)显示过程(procedure prnt)：在绘图板中可将当前字符串中的字符逐个显示出来。,5.5.6 组件设置 PaintBox1：绘图板，显示栈的当前状态。Edit1,edit2：编辑框，用于指定插入或替换操作中作为参数的字符串。Sp1,sp2：数字增减器，用于指定插入操作中的位置或删除操作中的位置与长度。But0-4：初态、插入、删除、替换、退出按钮，用于执行演示操作。,5.5.7 界面功能的实现(1)窗体生成事件：在窗体生成事件处理程序中，生成一个Tstring类的实例chun1，并作为当前字符串，另外再生成两个Tstring类的实例chun2，chun3，可分别作为操作中的参数使用，生成时这些串的值一般可任意指定。,chun1:=Tstring.create;chun1.init(abcdefg);chun2:=Tstring.create;chun2.init(cde);chun3:=Tstring.create;chun3.init(ww);,(2)退出按钮：在退出按钮事件处理程序中，释放已生成的实例chun1,chun2,chun3，并关闭窗体释放空间。chun1.Free;chun2.Free;chun3.Free;close;release;,(3)初态按钮：按编辑框edit1 中指定的字符串生成一个初始字符串，并作为当前字符串显示在绘图板中。chun1.init(edit1.text);chun1.prnt,(4)插入按钮：按数字增减器sp1 中指定的位置，在当前字符串中插入编辑框edit1中指定的字符串，并在绘图板中重新显示当前字符串。pos:=sp1.value;s:=edit1.text;chun2.init(s);chun1.inst(pos,chun2);chun1.prnt,(5)删除按钮：按数字增减器sp1 中指定的位置及sp2 中指定的长度，删除当前字符串中相应的子串，并在绘图板中重新显示当前字符串。pos:=sp1.Value;len:=sp2.value;chun1.dele(pos,len);chun1.prnt,(6)替换事件：按在编辑框edit1 中指定的被替换的字符串和在编辑框edit2 中指定的要替换的字符串，对当前字符串执行替换操作，并在绘图板中重新显示当前字符串。s:=edit1.text;chun2.init(s);s:=edit2.text;chun3.init(s);chun1.replace(chun2,chun3);chun1.prnt,5.5.8 程序清单,implementationvar chun1,chun2,chun3:Tstring;procedure Tstring.init(s:string);var i,len:integer;begin len:=length(s);for i:=1 to len do chi:=si;curlen:=len;end;,procedure Tstring.prnt;var i,ix,iy:integer;rect1:Trect;s:char;begin rect1:=rect(0,0,550,100);chunForm.PaintBox1.Canvas.Brush.Color:=clBtnFace;chunForm.PaintBox1.Canvas.FillRect(rect1);chunForm.PaintBox1.Canvas.pen.width:=4;chunForm.PaintBox1.Canvas.font.Color:=clred;chunForm.PaintBox1.Canvas.font.size:=18;ix:=10;iy:=0;if curlen0 then for i:=1 to curlen do,begin s:=chi;chunForm.PaintBox1.Canvas.textout(ix+20,iy+12,s);ix:=ix+20 end end;function Tstring.position(t:Tstring):integer;var i,j:integer;begin i:=1;j:=1;while(i=curlen)and(j=t.curlen)do if chi=t.chj then begin i:=i+1;j:=j+1 end,else begin i:=i-j+2;j:=1 end;if jt.curlen then position:=i-t.curlen else position:=0;end;procedure Tstring.dele(pos,len:integer);var i:integer;begin if(pos curlen)or(len1)then showmessage(infeasible)else,begin if len curlen-pos+1 then len:=curlen-pos+1;for i:=pos to curlen-len do chi:=chlen+i;curlen:=curlen-len;end;end;procedure Tstring.inst(pos:integer;t:Tstring);var i,tlen,len,n:integer;begin if(pos maxlen)then showmessage(infeasible)else if curlen=maxlen then showmessage(overflow)else,begin tlen:=t.curlen;if pos curlen then pos:=curlen;if curlen+tlen 0 then for i:=1 to n do chlen-i+1:=chpos+n-i+1;for i:=1 to tlen do if pos+ilen then break else chpos+i:=t.chi;curlen:=len end;,end;procedure Tstring.replace(t,r:Tstring);var pos:integer;begin pos:=position(t);if pos=0 then showmessage(infeasible)else begin dele(pos,t.curlen);inst(pos-1,r)end;end;procedure TchunForm.FormCreate(Sender:TObject);,begin chun1:=Tstring.create;chun1.init(abcdefg);chun2:=Tstring.create;chun2.init(cde);chun3:=Tstring.create;chun3.init(ww);end;procedure TchunForm.Button0Click(Sender:TObject);begin chun1.init(abcdefg);chun1.prntend;,procedure TchunForm.Button1Click(Sender:TObject);var s:string;pos:integer;begin pos:=sp1.value;s:=edit1.text;chun2.init(s);chun1.inst(pos,chun2);chun1.prntend;procedure TchunForm.Button2Click(Sender:TObject);var pos,len:integer;begin pos:=sp1.Value;len:=sp2.value;chun1.dele(pos,len);chun1.prntend;,procedure TchunForm.Button3Click(Sender:TObject);var s:string;begin s:=edit1.text;chun2.init(s);s:=edit2.text;chun3.init(s);chun1.replace(chun2,chun3);chun1.prntend;procedure TchunForm.Button4Click(Sender:TObject);begin chun1.Free;chun2.Free;chun3.Free;close;release;end;end.,