第四章串 §4.1串类型的定义 §4.2 串的表示和实现 4.2.1定长顺序存储表示 4.2.2堆分配存储表示 4.2.3串的块链存储表示
第四章 串 §4.1 串类型的定义 §4.2 串的表示和实现 4.2.1 定长顺序存储表示 4.2.2 堆分配存储表示 4.2.3 串的块链存储表示
4.1串类型的定义 串和基本概念 串(String)是零个或多个字符组成的有限序列。 一般记作S=a1a2a3.an',其中S是串名，引号括 起来的字符序列是串值： a(1sisn)可以是字母、数字或其它字符； 串中所包含的字符个数称为该串的长度。长度为零 的串称为空串(Empty String),它不包含任何字符。 通常将仅由一个或多个空格组成的串称为空白串 (Blank String) 注意：空串和空白串的不同，例如··和”分别 表示长度为1的空白串和长度为0的空串
4.1 串类型的定义 一、串和基本概念 串(String)是零个或多个字符组成的有限序列。 一般记作S=‘a1a2a3…an ’，其中S 是串名，引号括 起来的字符序列是串值； ai(1≦i≦n)可以是字母、数字或其它字符； 串中所包含的字符个数称为该串的长度。长度为零 的串称为空串(Empty String)，它不包含任何字符。 通常将仅由一个或多个空格组成的串称为空白串 (Blank String) 注意：空串和空白串的不同，例如‘ ’和‘’分别 表示长度为1的空白串和长度为0的空串
串中任意个连续字符组成的子序列称为该串的子串， 包含子串的串相应地称为主串。 通常将子串在主串中首次出现时的该子串的首字 符对应的主串中的序号，定义为子串在主串中的序 号（或位置）。 例如，设A和B分别为 A='This is a string'B='is' 则B是A的子串，A为主串。B在A中出现了两次 其中首次出现所对应的主串位置是3。因此，称B在 A中的序号（或位置)为3。 特别地，空串是任意串的子串，任意串是其自身 的子串
串中任意个连续字符组成的子序列称为该串的子串， 包含子串的串相应地称为主串。 通常将子串在主串中首次出现时的该子串的首字 符对应的主串中的序号，定义为子串在主串中的序 号（或位置）。 例如，设A和B分别为 A=‘This is a string’ B=‘is’ 则B是A的子串，A为主串。B在A中出现了两次， 其中首次出现所对应的主串位置是3。因此，称B在 A中的序号（或位置）为3。 特别地，空串是任意串的子串，任意串是其自身 的子串
通常在程序中使用的串可分为两种：串变量和串 常量。串常量和整常数、实常数一样，在程序中只 能被引用但不能改变其值，即只能读不能写。 通常串常量是由直接量来表示的，例如语句 Error(“overflow)中"overflow'是直接量。但 有的语言允许对串常量命名，以使程序易读、易写。 如，可定义 const char path[]="dir/bin/appl"; 这里path是一个串常量，对它只能读不能写。 串变量和其它类型的变量一样，其取值是可以改 变的。 两个串相等：长度相等，对应位置字符都相等。 二、串的抽象数据定义
通常在程序中使用的串可分为两种：串变量和串 常量。串常量和整常数、实常数一样，在程序中只 能被引用但不能改变其值，即只能读不能写。 通常串常量是由直接量来表示的，例如语句 Error(“overflow”)中“overflow”是直接量。但 有的语言允许对串常量命名，以使程序易读、易写。 如，可定义 const char path[]=“dir/bin/appl”; 这里path是一个串常量，对它只能读不能写。 串变量和其它类型的变量一样，其取值是可以改 变的。 两个串相等：长度相等，对应位置字符都相等。 二、串的抽象数据定义
串的基本操作 对于串的基本操作，许多高级语言均提供了相 应的运算或标准库函数来实现。下面仅介绍几种 在C语言中常用的串运算。 定义下列几个变量： char s1[20]='dirtreeformat',s2[20]='file.mem'; char s3[30],*p; int result; (1)求串长(length) int strlen(char*s);l求串的长度 例如：printf(“%d”,strlen(s1);输出13
三、串的基本操作 对于串的基本操作，许多高级语言均提供了相 应的运算或标准库函数来实现。下面仅介绍几种 在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