第四章 数组.ppt

第四章串
串类型的定义
串的表示和实现
定长顺序存储表示
堆分配存储表示
串的块链存储表示
计算机科学系:王岚
串类型的定义
一、串和基本概念
串(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。
特别地,空串是任意串的子串,任意串是其自身的子串。
通常在程序中使用的串可分为两种:串变量和串常量。串常量和整常数、实常数一样,在程序中只能被引用但不能改变其值,即只能读不能写。
通常串常量是由直接量来表示的,例如语句Error(“overflow”)中“overflow”是直接量。但有的语言允许对串常量命名,以使程序易读、易写。如C++中,可定义
const char path[]=“dir/bin/appl”;
这里path是一个串常量,对它只能读不能写。
串变量和其它类型的变量一样,其取值是可以改变的。
两个串相等:长度相等,对应位置字符都相等。
二、串的抽象数据定义
串的抽象数据类型定义见书P71
三、串的基本操作
对于串的基本操作,许多高级语言均提供了相应的运算或标准库函数来实现。下面仅介绍几种在C语言中常用的串运算,其它的串操作见书P71。
定义下列几个变量:
char s1[20]=“dirtreeformat”,s2[20]=“”;
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(s3,s2); //s3=“dirtreeformat/”
(4)pare)
int strcmp(chars1,char s2);
该函数比较串s1和串s2的大小,当返回值小于0,等于0或大于0时分别表示s1<s2\s1=s2或s1>s2
例如:result=strcmp(“baker”,”Baker”) result>0
result=strcmp(“12”,”12”); result=0
result=strcmp(“Joe”,”Joseph”); result<0
(5)字符定位(strchr)
char strchr(char s,char c);
该函数是找c在字符串s中第一次出现的位置,若找到则返回该位置,否则返回NULL。
例如:p=strchr(s2,”.”); p 指向“file”之后的位置
if(p) strcpy(p,”.cpp”); s2=“”
上述串的操作是最基本的,其中后四个还有变种形式:strncpy,strncat,strncmp,strnchr。串的其余操作可由这些基本操作组合而成。
例1、求子串
求子串的过程即为复制字符序列的过程,将串S中的第pos个字符开始长度为len的字符复制到串sub中。
void substr(string sub,string s,int pos,int len)
{
if(pos<0 || pos>strlen(s)-1 || len<0)
error(“parameter er