数据结构_string.ppt

第四章 串 4.1 串类型的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 4.1 串类型的定义 一、串的概念 串(string):由零个或多个字符组成的有限序列。一般表示为：S=‘a1a2…an’(n?0)。 二、串的抽象数据类型定义 ADT String{ 数据对象：D={ai|ai?Charset,i=1,2,…n,n?0} 数据关系：R1={ai-1,ai| ai-1,ai ?D,i=2,3,…,n} 基本操作： 详见P71~P72 }ADT String 三、串的基本操作 对于串的基本操作，许多高级语言均提供了相应的运算或标准库函数来实现。下面仅介绍几种在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)); 续 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); 续 4.串比较（compare) int strcmp(chars1,char s2); 该函数比较串s1和串s2的大小，当返回值小于0，等于0或大于0时分别表示s1s2\s1=s2或s1s2 例如：result=strcmp(“baker”,”Baker”); result0 result=strcmp(“12”,”12”); result=0 result=strcmp(“Joe”,”Joseph”); result0 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，strnchr。串的其余操作可由这些基本操作组合而成。 4.2 串的表示和实现 一、定长顺序存储表示 类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。 1. 定长数组描述： 2. 定长顺序存储下的串操作的实现 1) 串联接Concat(T,S1,S2) Concat(T,S1,S2) 算法 用T返回由S1和S2联接成的新串，若未截断，则返回TRUE，否则返回FALSE。 2) 求子串SubString(Sub,S,pos,len) Status SubString(SStringSub, SString S, int pos,int len){ if(pos1||posS[0]||len0||lenS[0]-pos+1) return ERROR; Sub[1..len]=S[pos..pos+len-1]; Sub[0]=len; return OK;} 4.2 串的表示和实现 在顺序存储结构中，实现串操作的原操作是“字符序列的复制”。当串的长度超过上界MAXSTRLEN时，就会被截断，而避免上述情况的发生，就需要引入动态空间分配。 2. 基本操作的算法描述 1）字符串设定操作StrAssign(HString T,char *chars) // 生成一个值为串chars的串T StrAssign算法 Status StrAssign(HString T, char *chars){ if(T.ch) free(T.ch); //释放空间 for(i=0,c=chars