《数据结构课件-串》由会员分享,可在线阅读,更多相关《数据结构课件-串(35页珍藏版)》请在金锄头文库上搜索。
1、第四章 串4.1 串类型的定义4.2 串的表示和实现4.3 串的模式匹配算法4.4 串操作应用举例14.1.1 串的逻辑结构定义 串是由零个或多个字符组成的有限序列。 一般记为:S=a1a2an (n=0) 长度串中字符的数目。 空串零个字符的串,用符号来表示空串。子串 串中任意个连续的字符组成的子序列。 主串包含子串的串。 位置 字符在序列中的序号为该字符在串中的位置。 例:a=bei b=jing c=beijing d=bei jing 则:a,b,c,d的长度分别为:3、4、7、8。a、b是c和d的子串。a 在c和d中的位置都是1。b在c中的位置是4,在d中的位置是52相等 当两个串的
2、长度相等,并且各个对应位置的字 符都相等,则称两个串是相等的。 空格串由一个或多个空格组成的串称为空格串。注意:串值必须用一对单引号括起来,但单引号本身不 属于串。例: x=123; x=123; tsing=tsing3串的抽象数据类型的定义: ADT String数据对象:D=ai|ai(-CharacterSet,i=1,2,.,n,n=0数据关系:R1=|ai-1,ai(-D,i=2,.,n基本操作:StrAssign( m=strlength(t); i=pos;while (i最大串长;(3)S1串长已=最大串长;h hg gf fe ed dc cbjbaia828TS2S116
3、算法描述如下:Status Concat(SString sub1len=spospos+len-1;sub0=len;if 1poslength(s) 且 0 lenlength(s)-pos+1用sub返回从串s中第pos个字符起,长度为len的字符序列。 else 返回error184.2.2 堆分配存储表示这种存储表示的特点是,仍以一组地址连续的存储单 元存放串值字符序列,但它们的存储空间是在程序执行过 程中动态分配而得。在C语言中,存在一个称之为堆的自由 存储区,并由C语言的动态分配函数malloc()和free()来管理. 利用函数malloc()为每个新产生的串分配一块实际串长所
4、 需存储空间,为处理方便,约定串长也作为存储结构的一部分。堆分配的存储表示:typedef structchar *ch;int length; HString;19ADT string 的堆分配存储的表示和实现:堆分配存储的表示;基本操作的函数原型说明;基本操作的算法描述;P7677204.2.3 串的块链存储表示例: s=abcdefghii # # # heada b c de f g hheadabci为了便于进行串的操作,当以链表存储串值时,除 头指针外还可附设一个尾指针指示链表的最后一个结点, 并给出当前串的长度,称如此定义的串存储结构为块链结构。21块链结构串的C表示:#defi
5、ne CHUKSIZE 80Typedef struct chunk char chCHUKSIZE;struct chunk *next;chunk;Typedef struct chunk *head,*tail;Int curlen;Lstring;例: Lstring S; s.head s.tail s.curlena bc de # 522串块链结构结点大小的选择依据:存储密度=串值所占的存储位实际分配的存储位i # # # heada b c de f g hheadabci例:存储密度=9 15=3 5存储密度=9 18=1 2234.3 串的模式匹配算法定位函数 index(
6、s,t,pos)的算法实现:算法分析 : S=abdgjgutabcdhhuac t=abcInt index (string s,string t,int pos) if (pos0) n=strlength(s); m=strlength(t); i=pos;while (it0 返回t在s的位置值else return(0);return( i-t0);i=pos; j=1;while (it0 return( i-t0);else return(0); 28例:S=abtabcdhhuac t=abc index(s,t,1)的匹配过程:第一趟匹配: abtabcdhhuac abci
7、=3j=3 第二趟匹配: abtabcdhhuac abci=2j=1第三趟匹配: abtabcdhhuac abci=3j=1 第四趟匹配: abtabcdhhuac abci=7j=4i=1,j=1i=4j=1 294.4 串操作应用举例 4.4.1文本编辑 文本编辑修改字符数据的形式或格式,包括串的查找、插入、删除等基本操作。文本编辑可以用于源程序的输入和修改(如图一):图一30用于报刊和书籍的编辑排版以及办公室的公文书信的起草 和润色(如图二):图二31在进行文本编辑时,我们把整个文本看成是一个字符串,称为文本 串,页则是文本串的子串,行又是页的子串。例如有下列一段源程 序:progr
8、am p;var i,j,k:integer;beginread(i,j);if ij then k:=j else k:=i;writeln(k)end.文本串的存储示意图:201 221 241 261.P r o g r a m p ; v a r i , j , k : i n t e g e r ; 32为了管理文本串的页和行,要为文本串建立相应的页表和 行表,即各子串的存储映象。行号 起始地址 长度 101 201 11102 212 20(1)页表:每一项包含页号、该页的起始行号;页号 起始行号 1 1 2 11 (2)行表:每一项包含行号、该行的起始地址、长度;33文本串的基本
9、操作:(1)在某行内插入或删除若干字符。(2)插入或删除一行。(3)查找子串。342.写出定长顺序存储结构的strdelete-ss(&s,pos,len)操作的算法。3.上机题:编写程序,完成定长顺序存储结构的strinsert- ss(&s,pos,t)和strdelete-ss(&s,pos,len)操作。strinsert界面要求:输入串S:abcdefgh# 输入插入串t:123输入插入位置:5串S的新值: abcd123efghStrdelete界面要求:输入串S:abcdefgh输入删除位置:3输入删除长度:2串S的新值:abefgh作业: 1.用5种串的基本操作(strassign、strcompare、strlength、concat、substring)来 逻辑实现strdelete(s,pos,len)操作.(注:格式参照p72算法4.1,即不考虑串的存储结构)35