《数据结构课件-串》由会员分享，可在线阅读，更多相关《数据结构课件-串（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
