厦门大学：《数据结构》课程教学课件（PPT讲稿）第四章 串（1/2）

数据结构

数据结构

第四章串 ■4.1串类型的定义 ■4.2串的表示和实现 4.2.1定长顺序存储表示 4.2.2堆分配存储表示 4.2.3串的块链存储表示 4.3串的模式匹配算法 43.1求子串位置的定位函数 4.3.2模式匹配的一种改进算法 ■4.4串操作应用举例 4.41文本编辑 4.4.2建立词索引表

第四章 串 ◼ 4.1 串类型的定义 ◼ 4.2 串的表示和实现 4.2.1 定长顺序存储表示 4.2.2 堆分配存储表示 4.2.3 串的块链存储表示 ◼ 4.3 串的模式匹配算法 4.3.1 求子串位置的定位函数 4.3.2 模式匹配的一种改进算法 ◼ 4.4 串操作应用举例 4.4.1 文本编辑 4.4.2 建立词索引表

4.1串类型的定义 一、 串和基本概念 串(String)是零个或多个字符组成的有限序列。一 般记作S=a1a2a3.an',其中S是串名，双引号括 起来的字符序列是串值；a(l≤i≤n)可以是字母、 数字或其它字符；串中所包含的字符个数称为该 串的长度。长度为零的串称为空串(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”是直接量。 但有的语言允许对串常量命名，以使程序易读、 易写。如C++中，可定义 const char path[]="dir/bin/appl"; 这里path是一个串常量，对它只能读不能写。串变 量和其它类型的变量一样，其取值是可以改变的。 二、串的抽象数据定义 串的抽象数据类型定义：书P71

程序中只能被引用但不能不能改变其值，即只能读 不能写。通常串常量是由直接量来表示的，例如 语句Error(“overflow”)中“overflow”是直接量。 但有的语言允许对串常量命名，以使程序易读、 易写。如C++中，可定义 const char path[]=“dir/bin/appl”; 这里path是一个串常量，对它只能读不能写。串变 量和其它类型的变量一样，其取值是可以改变的。 二、串的抽象数据定义 串的抽象数据类型定义：书P71

三、串的基本操作 对于串的基本操作，许多高级语言均提供了相 应的运算或标准库函数来实现。下面仅介绍 几种在C语言中常用的串运算，其它的串操作 见的文件。 定义下列几个变量： char s120=“dirtreeformat'”,s220=“file.mem”; char s330],*p; int result; ( 求串长(length) int strlen(char s);/求串的长度 例如：printfd”,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

(2)串复制(copy) char *strcpy(char to,char from); 该函数将串from复制到串to中，并且返回一个指 向串to的开始处的指针。 例如：strcpy((s3,s1;/s3=“dirtreeformat (3)联接(concatenation) char strcat(char to,char from) 该函数将串rom复制到串to的末尾，并且返回一个 指向串to的开始处的指针。 例如：strcat(s3,”/ strcat(s3,s2);//s3="dirtreeformat/file.mem

（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

(④串比较(compare) int strcmp(chars1,char s2); 该函数比较串s1和串2的大小，当返回值小于0，等于0或大 于0时分别表示$1s2 例如：result=-strcmp(baker'”,"Baker" result>0 result=strcmp(12","12");result=0 result=strcmp("Joe","Joseph");result<0 (5)字符定位ndex) char strchr(char s,char c); 该函数是找©在字符串中第一次出现的位置，若找到侧返回 该位置，否则返回NULL。 例如：p=strchr(s2,”；p指向"fle”之后的位置 if(p)strcpy(p,".cpp");s2="file.cpp

(4)串比较（compare) int strcmp(chars1,char s2); 该函数比较串s1和串s2的大小，当返回值小于0，等于0或大 于0时分别表示s1s2 例如：result=strcmp(“baker” , ”Baker”) result>0 result=strcmp(“12” , ”12”); result=0 result=strcmp(“Joe” , ”Joseph”); result<0 （5）字符定位(index) char strchr(char s,char c); 该函数是找c在字符串中第一次出现的位置，若找到则返回 该位置，否则返回NULL。 例如：p=strchr(s2,”.”); p 指向“file”之后的位置 if(p) strcpy(p,” .cpp ”); s2=“file.cpp

上述串的操作是最基本的，其中后四个还有变种形式： strncpy,strncat,strncmp。串的其余操作可由这些基本操作 组合而成。 例1、求子串 求子串的过程即为复制字符序列的过程，将串$中的第pos 个字符开始长度为len的字符复制到串T中。 void substr(string sub,string s,int pos,int len) if(posstrlen(s)-1 len<0) error(parameter error") strncpy(sub,&s pos],len);

上述串的操作是最基本的，其中后四个还有变种形式： strncpy，strncat，strncmp。串的其余操作可由这些基本操作 组合而成。 例1、求子串 求子串的过程即为复制字符序列的过程，将串S中的第pos 个字符开始长度为len的字符复制到串T中。 void substr(string sub,string s,int pos,int len) { if(posstrlen(s)-1 || len<0) error(“ parameter error ”) strncpy(sub,&s[pos],len); }

例2、串的定位index(s,tpos) 在主串中取从第pos个字符起、长度和串T 相等的子串和T比较，若相等，则求得函数值为 pos,否则值增1直至$中不存在和串T相等的子串 为止

例2、串的定位index(s,t,pos) 在主串中取从第pos个字符起、长度和串T 相等的子串和T比较，若相等，则求得函数值为 pos，否则值增1直至S中不存在和串T相等的子串 为止