数据结构之串.docVIP

第四章 串 4.1 串的定义和运算 一、串的定义 串也称字符串，是由n(n≥0)个字符组成的有限序列，记为：s=”a1a2a3……an” ai（1≤i≤n）可以是字母、数字或其它字符。 请注意，空串与空格串的区别。 我们将一个串中若干个相连字符组成的子序列称为该串的子串。包含子串的串称这为主串。 例如，两个串t=”struct”和s=”data structure”，称t是s的子串。 二、串的运算 设t,s,s1,s2均为串名。 串复制操作 StrCopy (t, s)，由串s复制得串t。 例如：s=”data structure”,执行StrCopy(s,t)后，t=”data structure” 。 联结操作 Concat (t, s1, s2)，用串s1和串s2联结而成的一个新串t。 例：s1=”data ”,s2=”structure”, 执行Concat(t, s1, s2)后,t=”data structure”。 联结函数符合结合律，不符合交换律。即： Concat (t, s1, s2，s3) = Concat (t, Concat (t, s1, s2),s3) ) = Concat (t, s1, Concat (t, s2, s3) ) 求串的长度：StrLength (s)，得串s中的元素个数 例如：s=”data structure”，则串的长度为14。 求子串操作 SubStr (s, i, m，t), 求得由主串s的第i个字符开始，长度为m子串t。 例如：s=”data structure”，执行 SubString ( s, 6, 6,t)，得t=”struct”。 判两个串是否相等：StrEqual(s, t)，当两个串s和t的长度相等，且两个串对应位置的每个字符都相等, 返回TRUE，否则返回FLASE。 例：s=”data structure”，t=”data structure”，执行 StrEqual( s, t)，得TURE。 求子串在串中的序号（又称定位） Index (s, t)，若主串s中存在和串t值相同的子串, 则返回它在主串s中第1个字符之后第一次出现的位置; 否则函数值为0。 如: s=”data structure”，t=”struct”，执行 Index( s, t)，返回6。 s=”data structure”，t=”date” ,执行 Index( s, t)，返回0。 置换操作 Replace (s, t, v)，若主串s中存在和串t值相同的子串, 则用v来替换。注意用v替换主串s中出现的所有与t相等的不重叠的子串。 例如：s=”abcabcababcaab” ，t=”cab”，v=”c” ,执行 Replace( s,t,v)，得：s=”abccabcaab”。 4.2 串的存储结构 一、行结构 unsigned char String[ 256]; // 用户可在255以内定义最大串长 // 0号单元存放串的长度 这种存储结构是一种定长的顺序存储结构，较适应于源程序等的存储。 二、 堆结构 （1）串值的存储 struct strstore { char *ch; //若是非空串，则按串长分配存储区，否则ch为NULL int pos; // pos是空闲区的首地址（已占用空间）的长度 }; 其中：pos是空闲区的首地址（已占用空间）的长度，s1和s2是串名，17和15是子串的长度 （2）串名的存储 串 名 开始地址 串的长度 串 名 开始地址 结束地址 串 名 开始地址 开始地址 例：文本编辑 P （1）串值的存储 （2）串名的存储 串名 开始地址 串的长度 1 1000 40 2 1040 16 3 1056 35 4 1091 14 5 1105 1 （3）操作： 插入、删除、排版等 4.3 模式匹配 s= “s1 s2,……sn”，t= “t1 t2……tm”，m≤n 在s中是否存在长度为m的子串“si si+1……si+m-1”，使得“si si+1 ……si+m-1”= “t1 t2……tm”。 称s为文本，t为模式。 s= “s1 s2,…si si+1……si+m-1…sn”， “t1 t2……tm ” 4.3.1 串匹配（有哪些信誉好的足球投注网站）算法 基本思想 从文本s的第一个字符起和模式t的第一个字符进行比 较，若相等，则继续逐个比较后续字符，否则从文本的第二个字符起重新和模式的字符进行比较。依次类推，直至 si=t1, si+1=t2,……,si+m-1=