第4章 字符串08.pdf

第4章字符串 4.1 串类型的定义 4.2 串的表示和实现 定长顺序存储表示 堆分配存储表示 串的块链存储表示 4.3 串的模式匹配算法 求子串位置的定位函数 1 4.1 串类型的定义 字符串是数据元素为字符的一种线性表，但 是通常以子串作为操作的基本单位。 串(String)是0个或多个字符组成的有限序 列。 一般记作S=‘a a a …a ’，其中S 是串名，单引号括起来 1 2 3 n 的字符序列是串值； （c 中使用双引号） a (1 ≦i ≦n)可以是字母、数字或其它字符；串中所包含 i 的字符个数n称为该串的长度。 长度为零的串称为空串，它不包含任何字符。 通常将仅由一个或多个空格组成的串称为空白串(Blank String) 注意：空串和空白串的不同，例如“ ”和“”分别表示长 度为1的空白串和长度为0的空串。 2 串中任意个连续字符组成的子序列称为该串 的子串，包含子串的串相应地称为主串。 串s 中的一个字符c的位置用一个整数表示，称为字符c在 串s 中的序号 （index ），串的第一个字符的序号为1。 通常将子串在主串中首次出现时的该子串的首字符对应 的主串中的序号，定义为子串在主串中的序号 （或位 置）。 例如，设A和B分别为A=“This is a string” B=“is” ，则B是A 的子 串，A为主串。B在A 中出现了两次，其中首次出现所对应的主 串位置是3。因此，称B在A 中的序号（或位置）为3 空串是任意串的子串，任意串是其自身的子串。 3 字符串的比较 如果s1与s2长度相同，且各个对应位置的字 符都相等，则s1 ＝s2。 如果s1的长度n1 小于s2的长度n2 ，且两字符 串的前n1个字符完全相同，则s1s2。 “abcd” ”abcdefgh” 如果s1与s2所有字符不完全相等，则比较第 一对不相同字符的ASCII码，较小字符所在 串为较小的串。 “Ac12”“abed” 字符的比较 按照字符在ASCII编码表中的次序可以比较字符的大小（编码的 大小）。例如，‘A’‘a’。 4 5 C字符串的存储和处理 用字符数组存放字符串 数组长度应大于字符串的长度，因为结尾要存放‘\0’ （空操作）。 字符串可以整体输入或输出。 输出时用数组名，遇到‘\0’结束。 输出字符不包括‘\0’。 1. char c[]={“China”}; 2. printf(“%s”,c); 3. scanf(“%s”,c); 用字符指针指向一个字符串 char *str=“I love China!”; printf(“%s”,str); 对字符串中字符的存取可以用下标，也可以用指 针。 c[i] *(str+i)