数据结构第四章串

数据结构第四章串

ID:43699570

大小:154.50 KB

页数:38页

时间:2019-10-12

数据结构第四章串_第1页
数据结构第四章串_第2页
数据结构第四章串_第3页
数据结构第四章串_第4页
数据结构第四章串_第5页
资源描述:

《数据结构第四章串》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、第四章串4.1串类型的定义4.2串的表示和实现4.2.1定长顺序存储表示4.2.2堆分配存储表示4.2.3串的块链存储表示4.3串的模式匹配4.1串类型的定义一、串和基本概念串(String)是零个或多个字符组成的有限序列。一般记作S=“a1a2a3…an”,其中S是串名,双引号括起来的字符序列是串值;ai(1≦i≦n)可以是字母、数字或其它字符;串中所包含的字符个数称为该串的长度。长度为零的串称为空串(EmptyString),它不包含任何字符。通常将仅由一个或多个空格组成的串称为空白串(Blank

2、String)注意:空串和空白串的不同,例如“”和“”分别表示长度为1的空白串和长度为0的空串。串中任意个连续字符组成的子序列称为该串的子串,包含子串的串相应地称为主串。通常将子串在主串中首次出现时的该子串的首字符对应的主串中的序号,定义为子串在主串中的序号(或位置)。例如,设A和B分别为A=“Thisisastring”B=“is”则B是A的子串,A为主串。B在A中出现了两次,其中首次出现所对应的主串位置是3。因此,称B在A中的序号(或位置)为3特别地,空串是任意串的子串,任意串是其自身的子串。通常

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

4、的基本操作对于串的基本操作,许多高级语言均提供了相应的运算或标准库函数来实现。下面仅介绍几种在C语言中常用的串运算,其它的串操作见的文件。定义下列几个变量:chars1[20]=“dirtreeformat”,s2[20]=“file.mem”;chars3[30],*p;intresult;求串长(length)intstrlen(chars);//求串的长度例如:printf(“%d”,strlen(s1));输出13(2)串复制(copy)char*strcpy(charto,charfrom)

5、;该函数将串from复制到串to中,并且返回一个指向串to的开始处的指针。例如:strcpy(s3,s1);//s3=“dirtreeformat”(3)联接(concatenation)charstrcat(charto,charfrom)该函数将串from复制到串to的末尾,并且返回一个指向串to的开始处的指针。例如:strcat(s3,”/”)strcat(s3,s2);//s3=“dirtreeformat/file.mem”(4)串比较(compare)intstrcmp(chars1,ch

6、ars2);该函数比较串s1和串s2的大小,当返回值小于0,等于0或大于0时分别表示s1s2例如:result=strcmp(“baker”,”Baker”)result>0result=strcmp(“12”,”12”);result=0result=strcmp(“Joe”,”Joseph”);result<0(5)字符定位(index)charstrchr(chars,charc);该函数是找c在字符串中第一次出现的位置,若找到则返回该位置,否则返回NULL。例如:p=

7、strchr(s2,”.”);p指向“file”之后的位置if(p)strcpy(p,”.cpp”);s2=“file.cpp”上述串的操作是最基本的,其中后四个还有变种形式:strncpy,strncat,strncmp,strnchr。串的其余操作可由这些基本操作组合而成。例1、求子串求子串的过程即为复制字符序列的过程,将串S中的第pos个字符开始长度为len的字符复制到串T中。voidsubstr(stringsub,strings,intpos,intlen){if(pos<0

8、

9、pos>st

10、rlen(s)-1

11、

12、len<0)error(“parametererror”)strncpy(sub,&s[pos],len);}例2、串的定位index(s,t,pos)在主串中取从第i个字符起、长度和串T相等的子串和T比较,若相等,则求得函数值为i,否则值增1直至S中不存在和串T相等的子串为止。intindex(strings,stringt,intpos){if(pos>0){n=strlen(s);m=strlen(t);i=pos;while

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。