第四章串 °4.1串类型的定义 °42串的表示和实现 42.1定长顺序存储表示 422堆分配存储表示 423串的块链存储表示
第四章 串 ⚫ 4.1 串类型的定义 ⚫ 4.2 串的表示和实现 4.2.1 定长顺序存储表示 4.2.2 堆分配存储表示 4.2.3 串的块链存储表示
串类型的定义 串和基本概念 串( String)是零个或多个字符组成的有限序列。 般记作S=a1aa3.an3,其中S是串名,双引号括 起来的字符序列是串值;a1(1≡i≡n)可以是字母 数字或其它字符;串中所包含的字符个数称为该串 的长度。长度为零的串称为空串( Empty 它不包含任何字符 通常将仅由一个或多个空格组成的串称为空白 (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”)中“ overf1ow”是直接量。但 有的语言允许对串常量命名,以使程序易读、易 写。如C中,可定义 char path[]=“dir/bin/app1”; 这里path是一个串常量,对它只能读不能写。串 变量和其它类型的变量一样,其取值是可以改变 的 串的抽象数据定义 串的抽象数据类型定义台书P71
只能被引用但不能不能改变其值，即只能读不能 写。通常串常量是由直接量来表示的，例如语句 Error(“overflow”)中“overflow”是直接量。但 有的语言允许对串常量命名，以使程序易读、易 写。如C中，可定义 char path[]=“dir/bin/appl”; 这里path是一个串常量，对它只能读不能写。串 变量和其它类型的变量一样，其取值是可以改变 的。 二、串的抽象数据定义 串的抽象数据类型定义台书P71
串的基本操作 对于串的基本操作,许多高级语言均提供了相 应的运算或标准库函数来实现。下面仅介绍几种在 C语言中常用的串运算,其它的串操作见文件。 定义下列几个变量: char s1[20]=“ dirtreeformat”; char s2[20]=“file.mem?” char s3[30], *p int result (1)求串长( length int strlen(char*s);//求串的长度 例如: printf(“%d”, strlen(s1));//输出13
三、串的基本操作 对于串的基本操作，许多高级语言均提供了相 应的运算或标准库函数来实现。下面仅介绍几种在 C语言中常用的串运算，其它的串操作见文件。 定义下列几个变量： char s1[20]=“dirtreeformat”; char 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= dirtier t (3)串联接( concatenation) char strcat(char *to, char *from) 该函数将串from复制到串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
(4)串比较( compare int strcmp(char sl, char *s2) 该函数比较串s1和串s2的大小,当返回值小于0,等于 0或大于0时分别表示s1s2。例如: result= strcmp(“ baker”,” Baker”);sult>0 result= strcmp(12”,”12”) re 0 result= strcmp(“Joe”,” Joseph");/resu (5)字符定位( index) char米 strchr(char米s,char米c) 该函数是找c在字符串s中第一次出现的位置,若找 到则返回该位置,否则返回NULL。 例如 :p= strchr(s2,” );//p指向“file”之后的置 if(p) strcpy(p,”.cp”);//s2=“file.cpp
(4)串比较（compare) int strcmp(char *s1,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在字符串s中第一次出现的位置，若找 到则返回该位置，否则返回NULL。 例如：p=strchr(s2,”.”);//p 指向“file”之后的位置 if (p) strcpy(p,”.cpp”); //s2=“file.cpp
上述串的操作是最基本的,其中后四个还有变种形式: strncpy, strncat, strncmp, strnchr。串的其余操作 可由这些基本操作组合而成 例1、求子串 求子串的过程即为复制字符序列的过程,将串S中的 第poS个字符开始长度为1en的字符复制到串sub中 void substr(string sub, string s, int pos, int len) if(posstrlen(s)-len len<O) error("parameter error strncpy(sub, &s [pos], len
上述串的操作是最基本的，其中后四个还有变种形式： strncpy，strncat，strncmp，strnchr。串的其余操作 可由这些基本操作组合而成。 例1、求子串 求子串的过程即为复制字符序列的过程，将串S中的 第pos个字符开始长度为len的字符复制到串sub中. void substr(string sub,string s,int pos,int len) { if(posstrlen(s)-1en || len<0) error(“parameter error”) strncpy(sub,&s[pos],len); }
例2、串的定位 index(s,t,pos) 在主串s中,若pOs>0,则在第pos个字 符的字符中的从第i个字符起、长度和串T 相等的子串和T比较,若相等,则求得函数 值为i,否则值增1直至S中不存在和串T相 等的子串为止且返回0;若pos<=0,则返回 0值
例2、串的定位index(s,t,pos) 在主串s中，若pos>0, 则在第pos个字 符的字符中的从第i个字符起、长度和串T 相等的子串和T比较，若相等，则求得函数 值为i，否则值增1直至S中不存在和串T相 等的子串为止且返回0；若pos<=0，则返回 0值
int index(string s, string t, int pos)i f(pos>0)i n=strlen (s)m=strlen pos, while (i<n-m+1 substr (sub, S, l, m) f (strcmp (sub, t)!=0)++i else return(i); return(0)
int index(string s,string t,int pos){ if(pos>0){ n=strlen(s);m=strlen(t);i=pos; while (i<n-m+1){ substr(sub,s,i,m); if (strcmp(sub,t)!=0) ++i; else return(i);} } return(0); }