5.3串的块装储录 也可用链表来存储串值,由于串的数据元素是一个字符,它只 有8位二进制数,因此用链表存储时,通常一个结点中存放的 不是一个字符,而是一个子串。 存储密度= 款据元素所占存位 实际分配的存储位 # define chunKsize80∥可由用户定义的块大小 typedef struct Chunk{∥结点结构 char ch[CUnKSIZEl; struct Chunk *next Chunk typedef struct{∥串的链表结构 Chunk为ead,ta;∥串的头和尾指针 int curlen;∥串的当前长度 STring;
5.2.3 串的块链存储表示 也可用链表来存储串值，由于串的数据元素是一个字符，它只 有 8 位二进制数，因此用链表存储时，通常一个结点中存放的 不是一个字符，而是一个子串。 存储密度 = 数据元素所占存储位 实际分配的存储位 #define CHUNKSIZE 80 // 可由用户定义的块大小 typedef struct Chunk { // 结点结构 char ch[CUNKSIZE]; struct Chunk *next; } Chunk; typedef struct { // 串的链表结构 Chunk *head, *tail; // 串的头和尾指针 int curlen; // 串的当前长度 } LString;
Shead Thisfistas S cruden S tail Ing 实际应用时,可以根据问题所需来设置结点的大小。 例如:在编辑系统中,整个文本编辑区可以看成是一个串,每 行是一个子串,构成一个结点。即:同一行的串用定长结构 (80个字符)行和行之间用指针相联接
S.head S.crulen S.tail T h i s a s t r i n g ^ i s 例如: 在编辑系统中，整个文本编辑区可以看成是一个串，每 一行是一个子串，构成一个结点。即: 同一行的串用定长结构 (80个字符),行和行之间用指针相联接。 实际应用时，可以根据问题所需来设置结点的大小
链式存储特点:用链表存储串值,易插入和删除。 法1:链表结点(数据域)大小取1 m[A.一B·一c· NULL 法2:链表结点(数据域)大小取n例如n=4) head ABC D E FGH ###NULL 讨论:法存储密度为12法存储密度为915=35 显然,著数据元素很多,用法2存储更优一称为块链结构
讨论：法1存储密度为 ；法2存储密度为 ； 显然，若数据元素很多，用法2存储更优—称为块链结构 链式存储特点 ：用链表存储串值，易插入和删除。 法1：链表结点（数据域）大小取1 法2：链表结点（数据域）大小取n(例如n=4) 1/2 9/15=3/5 A B C I NULL head head A B C D E F G H I # # # NULL
53串的馈匹配算法 算法目的:确定主串中所含子串第一次出现的位置(定位) 即如何实现ndex(s,Tpos)函数 B又称典的、经典的、补素的、穷举的) KmP算特点:速度快) 模式匹配( Pattern Matching)即子串定位运算(ndex函数) Indexi( S, T,pos函数 初始条件:串S和存在,T是非空串,1 pos sTreNgth(s) 操作结果:若主串S中存在和申T值相同的子串,则返回它在主串S 中第pos个字符之后第一次出现的位置;否则函数值为0。 注:S称为被匹配的串,T称为模式串。若S包含串T,则称匹配 成功。否则称匹配不成功
模式匹配(Pattern Matching) 即子串定位运算(Index函数). 初始条件：串S和T存在，T是非空串，1≤pos≤StrLength(s) 操作结果：若主串S中存在和串T值相同的子串，则返回它在主串S 中第pos个字符之后第一次出现的位置；否则函数值为0。 注：S称为被匹配的串，T称为模式串。若S包含串T，则称匹配 成功。否则称匹配不成功。 算法目的：确定主串中所含子串第一次出现的位置（定位） ——即如何实现Index(S,T,pos)函数 5.3 串的模式匹配算法 • BF算法 (又称古典的、经典的、朴素的、穷举的) • KMP算法 (特点：速度快) Index(S,T,pos)函数
S扇 Pos TEa nm+1T串 in S T T BF算法设计思想 将主串的第pos个字符和模式的第1个字符比较, 若相等,继续逐个比较后续字符; 若不等,从主串的下一字符(pos+1)起,重新与第一个字符比较。 直到主串的一个连续子串字符序列与模式相等。返回值为S中与T匹配的子劇列 第一个字符的房号,即匹配成功。 S=“ a b a b cabac b a b 否则,匹配失败,返回值0 'abc a c pos=5
S串 T串 T串 i pos n-m+1 S串 T 串 T串 i j j>m i j i j i>n j T串 i BF算法设计思想：j 将主串的第pos个字符和模式的第1个字符比较， 若相等，继续逐个比较后续字符； 若不等，从主串的下一字符（pos+1）起，重新与第一个字符比较。 直到主串的一个连续子串字符序列与模式相等。返回值为S中与T匹配的子序列 第一个字符的序号，即匹配成功。 否则，匹配失败，返回值0 . S=‘a b a b c a b c a c b a b’ T=‘a b c a c’ pos=5