[第4章串.doc

第四章 串 讲课提要 【主要内容】 1．串的有关概念及基本操作 2．串的存储结构 3．串操作应用举例 【教学目标】 1．掌握串的有关概念及基本运算 2．熟悉串的存储结构 3．熟悉串操作应用举例 学习指导 1．概念和术语 串（String）（或字符串）：是由零个或多个字符组成的有限序列。一般记为 s= “aa… a” (n≥0) 其中，s是串的名，用双引号括起来的字符序列是串的值。 串的长度：串中字符的个数n。 子串和主串：串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。 空串：不包含任何字符的串，表示为“Ф”。 空格串：由一个或多个空格字符组成的串。例如：“ ”。 2．串的基本操作 （1）用串变量赋值assign(s,t)和用串常量赋值create(s,ss) （2）判等函数 equal(s, t） （3）求长函数 length(s) （4）连接函数 concat(s,t) （5）求子串函数 substring(s, pos , len) （6）定位函数 index(s,t) （7）置换函数 replace(s,t,v) （8）插入子串 insert(s,pos,t) （9）删除子串 delete(s,pos,k) （10）串的复制 copy(s,t) 【例3-1】已知字符串：a=“an apple”，b=“other hero”，c=“her”，求： （1）concat(substr(a,1,2),b)。 （2）replace(a,substr(a,5,1),c)。 （3）index(a,c)和index(b,c)。 解： （1）返回值为“another hero”，其中substr(a,1,2)的返回值为“an”。 （2）返回值为“an aherherle”，其中sub(a,5,1)的返回值为“p”。 （3）返回值分别为0和3。 3．串的顺序存储结构（顺序串） 串的顺序存储方式类似于线性表的顺序存储方式，其存储结构用C语言描述为： typedef struct strnode { char data[maxlen]; int len; }SeqString; //定义顺序串类型 【例3-2】设定串采用顺序存储结构，写出对串s1和串s2比较大小的算法。串值大小按字典排序（升序）方式，返回值等于-1，0和1分别表示s1s2，s1=s2和s1s2。 解： 算法思想： （1）比较s1和s2共同长度范围内的对应字符： 若s1的字符s2的字符，返回； 若s1的字符s2的字符，返回； 若s1的字符=s2的字符，按上述规则继续比较； （2）当（1）中对应字符均相同时，比较和的长度： 两者相等时，返回0； 前者后者时，返回1； 前者后者时，返回-1； 算法描述如下： #define MAXLEN 256 struct strnode{ char data[MAXLEN]; int len; }SeqString; //定义顺序串类型 int strcmp(SeqString s1, SeqString s2)//比较串s1和串s2的大小 { int comlen; if (s1.lens2.len) comlen=s1.len; //求出串s1和串s2的共同长度 else comlen=s2.len; for(i=0;icomlen;i++) //在共同长度内逐个字符比较 if(s1.ch[i]s2.ch[i]) return (-1); //s1s2 else if(s1.ch[i]s2.ch[i]) return (1); //s1s2 if(s1.ch[i]= =s2.ch[i]) return (0); //s1=s2 else if(s1.ch[i]s2.ch[i]) return (-1); //s1s2 else return (1); //s1s2 } 4．串的链式存储结构（即链串或块链结构） 使用链式存储结构的字符串，只要存储空间足够大，其长度没有任何限制，但逻辑上的连续性不体现为物理上的邻接性。每个字符和一个指针域形成一个结点，结点间的关系由链指针实现，即字符逻辑上的连续性由链指针描述。 其存储结构用C语言描述为： typedef struct strnode{ //定义字符串的结点类型 char data; struct strnode *next; }LinkString; 习题3 一、单项选择题 1. 空串与空格字符组成的串的区别在于（ ）。 A.没有区别 B.两串的长度不相等 C.两串的长度相等 D.两串包含的字符不相同 2. 一个子串在包含它的主串中的位置是指（ ）。