数据结构第4章串1.pptVIP

§4.1 串的定义及基本概念 定义:串（string)是 n ( ? 0 )个字符组成的有限序列， 记作: S = ”c1c2c3…cn” * 串的基本概念 串的基本运算 串的存储结构 模式匹配 例：S1=“Hello” S1是串名，“Hello”为串值，n=5 其中，ci 是串中字符 n 是串的长度 　　 n=0 称空串”” 串名（串变量） 串值 注：空串和空格串有区别，空串””n=0(不含任何字符） 空格串” ” n?0 n=4 串值必用“”，否则 123 视为数，应为“123” ; abc 视为串名，应为“abc” 串中任意连续个字符组成的子序列称为该串的子串，该串相应的称为主串。 例：S=”This is a string.” 　”This”、 ”string” 、 ”is”　 是S的子串，S是它们的主串。 　　当子串在主串中第一次出现时，把子串的第一个字符在主串中序号称为子串在主串中的位置。 1　　　　11　　　3 空串是任意串的子串。任意串是其自身的子串。 两个串相等的充分必要条件是： 　　　　两个串长度相等，对应位置的字符相同。 串的基本概念及术语 ADT List { 数据对象: D={ai|1?i ? n, n ? 0, ai属char类型 数据关系: R1={ ai ,ai+1 | ai ,ai+1 ?D, i=1,2, …,n-1} 基本运算: StrAssign(s,cstr ); StrCopy(s,t); StrEqual(s,t); StrLength(s); ConCat(s,t): SubStr(s,i,j); InsStr(s1,i,s2) DelStr(s,i,j); Index(s,t); RepStr(s,i,j,t); RepStr(s,t,r); DispStr(s);} 抽象数据类型串的定义 §4.2 串的存储结构 顺序串： S t r i n g typedef struct { char data[MaxSize]; /*串的存储空间*/ int len; /*当前串的长度*/ }SqString; 链串： S1 ? H e l l o 结点大小为1 结点大小为4 ? S2 G o o d m o r i n g ! 操作方便，特别是插入和删除操作，但存储密度太低。 存储密度相对高，但插入和删除操作效率太低。 索引存储： 用于存储多个串 堆 s t r i n g \0 C h i n e s e \0 D a t a s t r u c t u r e \0 c o m p u t e r \0 S1 1 S2 8 S3 23 S4 31 索引表 串名 首址 free last free free §4.4 串的模式匹配 目标串 S=”s1s2s3 ?? sn” 模式串 T=”t1t2 ?? tm” 模式匹配： 在目标串S中查找与模式串T相同子串的过程。 例：S=”This is a string.” T=”is” is index(S,T)=3 匹配成功 例：S=”This is a string.” T=”the” index(S,T)=0 匹配失败 第1趟 S a b b a b a c T a b a 匹配失败 第2趟 S a b b a b a c T a b a 匹配失败 第3趟 S a b b a b a c T a b a 匹配失败 第4趟 S a b b a b a c