数据结构 邓欣-ch4.pptVIP

“ ” “ ” 第四章 串 4.1 串类型、基本概念 4.2 串的表示和实现 4.2.1 定长顺序存储表示 4.2.2 串的链、块链存储表示 1.串的基本概念 串(String)是零个或多个字符组成的有限序列。一般记作S=“a1a2a3…an”，其中S 是串名，双引号括起来的字符序列是串值；ai(1≦i≦n)可以是字母、数字或其它字符；串中所包含的字符个数称为该串的长度。长度为零的串称为空串(Empty String)，它不包含任何字符。 通常将仅由一个或多个空格组成的串称为空白串(Blank String) 注意：空串和空白串的不同，例如“ ”和“”分别表示长度为1的空白串和长度为0的空串。 4.1串类型、基本概念 下面是一些串的例子：（1）a = “This is a string” （2）b = “string” （3）c = “ “（4）d = “”（5）e = “你好” 说明： 串中包含的字符个数，称为串的长度。 长度为0的串称为空串，它不包括任何字符; 串中所包含的字符可以是字母、数字或其他字符，这依赖于具体计算机所允许的字符集。 2 串的有关术语 1）子串 串中任意连续的字符组成的子序列称为该串的子串;例：c = “ DATA STRUCTURE”，f=“DATA” f是c的子串 2）子串的位置 子串t 在主串S中的位置是指主串s 中第一个与T相同的子串的首字母在主串中的位置; 例：s=“ababcabcac” , t=“abc” 子串T 在主串S中的位置为3 3）串相等 两个串相等，当且仅当两个串长度相同，并且各个对应位置的字符都相同； 3 串的基本操作 串的逻辑结构与线性表一样，都是线性结构。但由于串的应用与线性表不同，串的基本操作与线性表有很大差别。 1）串赋值操作assign( s, t) 功能：将串t 的值赋给串变量s 2）串相等判断 equal(s,t) 函数 串的联接操作 concat( s , t ) 把串t 接在串 s 后面 求串长操作 lenght(s) 5) 求子串操作sub ( s, start, len, t) 若 0=startlength(s) 0=len=length(s)-start 则t 中值为从串s 的第start个字符, 起长度为len 的字符序列, 并且函数返回值为1, 否则为0； 7） 替换操作 replace( s, t ,v ) 功能：由串v 替换串s 中出现的所有和 t 相同的不重叠子串；8）复制串操作 strcopy(s, t) 功能：由串变量 s 复制得到串变量 t ； 9）判空操作 empty( s ) 功能：若为空串，则返回1，否则返回0 10）串置空操作 ClearString( s ) 功能：将s 清为空串 11) 串插入操作 StrInsert( s, start , t) 功能：将串t 插入到串s 的第start 字符之前 12）串删除操作 StrDelete( s, start , len) 功能：从串s 中删除第 start 个字符起长度len 为的子串 4、C语言中的基本操作 对于串的基本操作，许多高级语言均提供了相应的运算或标准库函数来实现。下面仅介绍几种在C语言中常用的串运算，其它的串操作见的文件。 定义下列几个变量： char s1[20]=“dirtreeformat”,s2[20]=“file.mem”; char s3[30],*p; int result; 求串长(length) int strlen(char *s); //求串的长度 例如：printf(“%d”,strlen(s1)); 输出13 （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(