第4章串 4.1串类型的定义 4.2串的表示和实现《算法与数据结构（C＆Java）（第2版）》 同步教学（电子工业出版社）

6学科网 第四章串 4.1串类型的定义 4.2串的表示和实现 4.2.1定长顺序存储表示 4.2.2串的块链存储表示 4.3串的模式匹配 6学科网 WWW.ZXXK.CON 4.1串类型的定义 一、串和基本概念 串(String)是零个或多个字符组成的有限序列。 般记作S=“a1a2ag.an”,其中S是串名，双引号 括起来的字符序列是串值；a(1si≤n)可以是字母、 数字或其它字符；串中所包含的字符个数称为该串 的长度。长度为零的串称为空串(Empty String), 它不包含任何字符。 通常将仅由一个或多个空格组成的串称为空白串 (Blank String) 注意：空串和空白串的不同，例如“”和”分别表示 长度为1的空白串和长度为0的空串 6学科网 串中任意个连续字符组成的子序列称为该串的子串， 包含子串的串相应地称为主串。通常将子串在主串中首 次出现时的该子串的首字符对应的主串中的序号，定义 为子串在主串中的序号（或位置）。例如，设A和B分 别为 A=This is a string”B=“is” 则B是A的子串，A为主串。B在A中出现了两次，其 中首次出现所对应的主串位置是3。因此，称B在A中的 序号（或位置）为3。 空串是任意串的子串，任意串是其自身的子串。 6学科网 通常在程序中使用的串可分为两种：串变量和串常量。 串常量和整常数、实常数一样，在程序中只能被引用但 不能不能改变其值，即只能读不能写。通常串常量是由 直接量来表示的，例如语句Error(“overflow)中 “overflow”是直接量。但有的语言允许对串常量命名， 以使程序易读、易写。如C++中，可定义 const char path[]="dir/bin/appl"; 这里path是一个串常量，对它只能读不能写。串变量和 其它类型的变量一样，其取值是可以改变的。 6学科网 三、串的基本运算概述 为描述方便，假定用大写字母表示串名，小写字母表 示组成串的字符。 1.串复制 strepy(S,T) 表示将T串的值赋给S串。 2.联接 strcat(T1,T2) 表示将T1串和T2串联接起来，组成一个新的T1串。 3.求串长度 strlen (T) 求T串的长度。 6学科网 WWW.ZXXK.CO 4.子串substr(S,i,len) 表示截取S串中从第i个字符开始连续len个字符，构成一 个新串（显然该新串是$串的子串） 。 5.串比较大小strcmp(S,T) 比较S串和T串的大小，若S<T,函数值为负，若S=T,函 数值为零，若S>T,函数值为正。 6.串插入 insert(S,i,T) 在S串的第个位置插入T串。 7.串删除 delete(S,i,len) 删除串S中从第i个字符开始连续len个字符。 6学科网 8.求子串位置 index(S,T) 求T子串在S主串中首次出现的位置，若T串不是S 的子串，则位置为零。 9.串替换 Replace(S1,i,j,S2) 用S2串替换S1串中第i个字符开始的连续j个字符。 利用上述九种基本运算还可以组合成字符串的其他 有关操作。 6学科网 三、串的基本操作 对于串的基本操作，许多高级语言均提供了相应的 运算或标准库函数来实现。下面先介绍几种在C语言 中常用的串运算。 定义下列几个变量： char s1[20]="dirtreeformat",s2[20]="file.mem"; char s3[30],*p; int result; (1)求串长(length) int strlen(char*s;/求串的长度 例如：printf("%d”,strlen(s1);输出13 6学科网 WWW.ZXXK.CON (2)串复制copy) char *strcpy(char *to,char *from); 该函数将串from复制到串to中，并且返回一个指向串to 的开始处的指针。 例如：strcpy(s3,s1);/s3=“dirtreeformat'" (3)联接(concatenation) char strcat(char *to,char *from) 该函数将串from复制到串to的末尾，并且返回一个指向 串to的开始处的指针。 例如：strcat(s3,"/") strcat(s3,s2);//s3="dirtreeformat/file.mem" 6学科网 (4)串比较(compare) int strcmp(char *s1,char *s2); 该函数比较串s1和串s2的大小，当返回值小于0，等于 0或大于0时分别表示s1<s2、s1=s2或s1>s2 例如：result=-strcmp(“baker'","Baker'")result>0 result=strcmp("12",