powerpoint 演示文稿 - 串类型的定义

1、14.1 串类型的定义一、串和基本概念 串(string)是零个或多个字符组成的有限序列。一般记作s=“a1a2an”，其中s 是串名，双引号括起来的字符序列是串值；ai(1in)可以是字母、数字或其它字符；串中所包含的字符个数称为该串的长度。长度为零的串称为空串(Empty String)，它不包含任何字符。 通常将仅由一个或多个空格组成的串称为空白串(Blank String) 注意：空串和空白串的不同，例如“ ”和“”分别表示长度为1的空白串和长度为0的空串。2 串中任意个连续字符组成的子序列称为该串的子串，包含子串的串相应地称为主串。 通常将子串在主串中首次出现时的该子串的首字符对应的

2、主串中的序号，定义为子串在主串中的序号（或位置）。 例如，设A和B分别为 A=“This is a string” B=“is” 则B是A的子串，A为主串。B在A中出现了两次，其中首次出现所对应的主串位置是3。因此，称B在A中的序号（或位置）为3。 特别地，空串是任意串的子串，任意串是其自身的子串。3 通常在程序中使用的串可分为两种：串变量和串常量。串常量和整常数、实常数一样，在程序中只能被引用但不能不能改变其值，即只能读不能写。通常串常量是由直接常量来表示的。 例如，语句 printf(“overflow”); 中“overflow”是直接常量。 但有的语言允许对串常量命名，以使程序易读、易

3、写。如C+中，可定义 const char path=“dir/bin/appl”; 这里path是一个串常量，对它只能读不能写。串变量和其它类型的变量一样，其取值是可以改变的。4二、串的基本操作对于串的基本操作，许多高级语言均提供了相应的运算或标准库函数来实现。下面仅介绍几种在C语言中常用的串运算。在使用字符串函数时要包含头文件“string.h”。 定义下列几个变量： char s120=“dirtreeformat”,s220=“file.mem”; char s330,*p; int result; 1. 求串长(length) int strlen(char *s); /求串的长度的

4、库函数 例如：printf(“%d”,strlen(s1); /输出1352 串复制(copy) char *strcpy(char *to,char *from); 该库函数将串from复制到串to中，并且返回一个指向串to的开始处的指针。 例如：strcpy(s3,s1); /s3=“dirtreeformat”定义下列几个变量： char s120=“dirtreeformat”,s220=“file.mem”; char s330,*p; int result;63 联接(concatenation) char * strcat(char *to,char *from)； 该函数将串f

5、rom复制到串to的末尾，并且返回一个指向串to的开始处的指针。 例如：strcat(s3,”)；/s3= “dirtreeformat” strcat(s3,s2); /s3=“dirtreeformatfile.mem”定义下列几个变量： char s120=“dirtreeformat”,s220=“file.mem”; char s330,*p; int result;执行了 strcpy(s3,s1); /s3=“dirtreeformat”74 串比较（compare) int strcmp(char *s1,char *s2); 该库函数比较串s1和串s2的大小。s1、s2从左至

6、右，逐个字符相比（ASCII码值） 当s1s2，返回值大于0。 例如：result=strcmp(“baker”,”Baker”) result0 result=strcmp(“12”,”12”); result=0 result=strcmp(“Joe”,”Joseph”); result0 85 字符定位(index) char *strchr(char *s,int ch); 该库函数是找ch在字符串s中第一次出现的位置，若找到则返回该位置，否则返回NULL。 例如：char s220=“file.mem”; char *p; p=strchr(s2,.); / p 指向“file”之后

7、的位置 if (p) strcpy(p,”.cpp”); /s2=“file.cpp” 上述串的操作是最基本的，其中后四个还有变种形式：strncpy，strncat，strncmp，strnchr。串的其余操作可由这些基本操作组合而成。9例1:求子串 求子串的过程即为复制字符序列的过程，将串s中的第pos个字符开始长度为len的字符复制到串sub中。 void substr(string sub,string s,int pos,int len) if (posstrlen(s) | len0) n=strlen(s); m=strlen(t); i=pos; while(i=n-m+1)

8、/i+m=l&i0&k=n-i+1) for(j=0;j=l&i0&k=1 & i0 & k=n-i+1) t.Length=k; t.StrAdr=free; for (j=0;jdata; /头结点的data域存放串长度 if(i=l&i0&k=n-i+1) p=s; for(j=0;jnext; /寻找子串起始位置 t=(nodetype*) malloc(sizeof(nodetype); t-data=k; /子串头结点的数据域存放长度 28 v=t; for(j=0;jnext=q; v=q; q-data=p-dat

9、a; p=p-next; /建立子串 return(t); else return(NIL); 29块链结构块链结构 #define NODENUM typedef struct node char dataNODENUM; struct node *next;nodetype; /结点类型定义typedef struct head int len; nodetype *next; headtype; /头结点类型定义 30s slenlenData0Data0 Data79Data79Data0Data0 Data79Data79 31headtype *substrl2(headtype

10、*s, int i,int k) headtype *t; nodetype *p, *v; int j,n,m,w,l,u; n=s-len; /n为主串s的长度 p=s-next; /初始p指向主串 s的结点 if (i=1&i0&k=n-i+1) m=i/NODENUM; /m为所求子串起始结点号 for(j=0;jnext; t=(headtype*) malloc(sizeof(headtype); t-len=k; t-next=(nodetype*)malloc(sizeof( nodetype); v=t-next; w=1; /子串结点计数器 32 u=1;

11、/主串结点计数器 l=i; /主串序号计数器 for(j=0;j=NODENUM*w) w+; v-next=(nodetype*)malloc(sizeof(nodetype); v=v-next; if (l=NODENUM*u) u+; p=p-next; v-dataj%NODENUM=p-datal%NODENUM; l+; return(t); else return(NIL);334.3 4.3 串的模式匹配算法串的模式匹配算法 子串定位运算又称为模式匹配(Pattern Matching)或串匹配(String Matching)，此运算的应用在非常广泛。例如，在文本编辑程序中

12、，我们经常要查找某一特定单词在文本中出现的位置。显然，解此问题的有效算法能极大地提高文本编辑程序的响应性能。 在串匹配中，一般将主串称为目标串，子串称之为模式串。设S为目标串，T为模式串，且不妨设： S=“s0s1s2sn-1” T=“t0t1tm-1” 串的匹配实际上是对于合法的位置0in-m依次将目标串中的子串si.i+m-1和模式串t0.m-1进行比较，若si.i+m-1=t0.m-1，34 则称从位置i开始的匹配成功，亦称模式t在目标s中出现；若si.i+m-1 t0.m-1，则称从位置i开始的匹配失败。上述的位置i又称为位移，当si.i+m-1=t0.m-1时，i称为有效位移；当si

13、.i+m-1 t0.m-1时，i称为无效位移。这样，串匹配问题可简化为是找出某给定模式T在一给定目标T中首次出现的有效位移。 串匹配的算法很多，这里我们只讨论一种最简单的称为朴素的串匹配算法。其基本思想是用一个循环来依次检查n-m+1个合法的位移i(0in-m)是否为有效位移。35其算法段为： for(i=0;i=n-m;i+) if (Si.i+m-1=T0.m-1) return i; 下面以第二种定长的顺序串类型作为存储结构，给出具体的串匹配算法。 int index(sstring s,sstring t,int pos) int i,j,k; int m=s.length; int n=t.length; for(i=0;i=n-m;