数据结构郝春梅C语言版第4章答案.ppt

第4章 串 学习目标与要求： 了解串的基本概念和基本运算。 熟练掌握串的顺序存储结构，掌握串的堆式存储结构和串的链式存储结构。 熟练掌握串的顺序存储结构中的连接、相等判断、取子串、插入、删除和子串查找等算法的实现。 4.1 串的定义及基本操作 串即字符串，计算机处理的对象分为数值数据和非数值数据，字符串是最基本的非数值数据。 字符串的应用非常广泛，它是许多软件系统(如字符编辑、情报检索、词法分析、符号处理、自然语言翻译等系统)的操作对象。 在事务处理程序中，顾客的姓名和地址以及货物的名称、产地和规格等一般也是作为字符串处理的。字符串是一种特定的线性表，其特殊性在于组成线性表的每个元素都是一个单字符。 4.1.1 串的基本概念 串(String)是零个或多个字符组成的有限序列。一般记为： S=a1…an (n≥0) 其中S是串的名字，用双引号括起来的字符序列是串的值，ai(1≤i≤n)可以是字母、数字或其他字符。它称为串的元素，是构成串的基本单位，i是它在整个串中的序号；n为串的长度，表示串中所包含的字符个数。 4.1.1 串的基本概念 几个术语 （1）长度——串中字符的个数，称为串的长度。 （2）空串——长度为零的字符串称为空串。 （3）空格串——由一个或多个连续空格组成的串称为空格串。 （4）串相等——两个串是相等的，是指两个串的长度相等且对应字符都相等。 （5）子串——串中任意连续的字符组成的子序列称为该串的子串。 （6）主串——包含子串的串称为该子串的主串。 （7）模式匹配——子串的定位运算又称为串的模式匹配，是一种求子串的第一个字符在主串中序号的运算。被匹配的主串称为目标串，子串称为模式。 4.1.1 串的基本概念 【例】字符串的长度及子串的位置。 字符串 字符串长度 S1=＂SHANG＂ 5 S2=＂HAI＂ 3 S3=＂SHANGHAI＂ 8 S4=＂SHANG□HAI＂ 9 // □表示空格，下同 S1是S3、S4的子串，S1在S3、S4中的位置都为1。 S2也是S3、S4的子串，S2在S3中的位置为6； S2在S4中的位置为7。 （2）使用gets() 函数 格式为：gets(字符数组名); 【例】 char str[10]; printf(＂Input your str: ＂); gets(str); 使用gets()方式输入时，字符串中允许含有空格。 2．字符串的输出 字符串的输出也有两种方法： （1）使用printf () 函数 使用printf () 函数时，输出格式中要设置＂%s＂，再加上字符数组名。 【例5-4】 printf(＂Your str is %s＂,str); （2）使用puts () 函数 格式为：puts (字符数组名); 【例5-5】 printf(＂Your str is ＂); puts (str); 4.1.2 串的基本操作 下面给出串的基本操作。 (1)StrAssign(S,chars)：串赋值操作。将字符串chars的值赋值给串S。 (2)StrLength(S)：串长度操作。返回串S的长度，即串S中的元素个数。 (3)StrInsert(S,T,pos)：串插入操作。如果1≤pos≤StrLength(S)+1时，在串S的第pos个字符之前插入串T。 (4)StrDelete(S,pos,len)：串删除操作。如果1≤pos≤StrLength(S)-len+1，则从串S中删除第pos个字符起长度为len的子串。 4.1.2 串的基本操作 (5)StrCopy(S,T)：串复制操作。将串T复制到串S中。 (6)StrEmpty(S)：串判空操作。若串S为空串，则返回1；否则返回0。 (7)StrCompare(S,T)：串比较操作。若串S与T相等则返回1；否则返回0。 (8)StrClear(S)：串清空操作。将串S清为空串。 (9)StrConcat(S,T)：串连接操作。将串T连接在串S的后面。 4.1.2 串的基本操作 (10)SubString(Sub,S,pos,len)：求子串操作。若存在位置1≤pos≤StrLength(S)且1≤len≤StrLength(S)-pos+1，则用Sub返回串S的第pos个字符起长度为len的子串。