《算法与数据结构》教学课件-第3章 字符串--C语言描述（第2版）张乃孝编著汇.ppt

张乃孝 算法与数据结构——C语言描述 算法3.5 朴素的模式匹配算法 int index(PSeqString t, PSeqString p){ // 求p所指的串在t所指的串中第一次出现时， // p所指的串的第一个元素在t所指的串中的序号 int i,j;//i,j分别为p串、t串中当前字符的下标， i=0;j=0; while(ip-n jt-n) if(p-c[i] == t-c[j]){ i++;j++ else j=j-i-1; i=0; } if(i==p-n) return(j-p-n+1); else return 0; } * * 3 字符串 3.1 字符串及其抽象数据类型 3.2 字符串的实现 3.3 模式匹配 字符串：简称串，是特殊的线性表，其特殊性主要在于表中的每个元素是一个字符，以及由此而要求的一些特殊操作。 3.1 字符串及其抽象数据类型 3.1.1 基本概念 长度：一个串中包括的字符个数。长度为零的串称为空串。 子串：字符串s1中任意个连续的字符组成的子序列s2被称为是s1的子串，而称s1是s2的主串。 位置：子串在主串中的位置是以子串的第一个字符在主串中的字符序号(下标+1)。 相等：两个串的长度相等，并且对应位置上的字符都 相等。 ADT3.1 字符串的抽象数据类型 ADT String is operations string createNullStr(void) 创建一个空串 int isNullstr(String s) 判断一个串是否为空串 int length(String s) 求一个串的长度 String concat(String s1, String s2) 将两个串拼接在一起构成一个新串 String subStr(String s, int i, int j) 在串s中，求从串的第i个字符开始连续j个字符所构成的子串 int index(String s1,String s2) 求串S2在串S1中第一次出现的位置End ADT String 3.1.2 抽象数据类型 3.2 字符串的实现 3.2.1 顺序表示 3.2.2 链接表示 3.2.1 顺序表示 struct SeqString /* 顺序串的类型 */ { int MAXNUM /* 串允许的最大字符个数 */ int n; /* 串的长度，n?MAXNUM */ char *c; }; typedef struct SeqString *PSeqString; 顺序串的定义 例 算法3.1 创建空顺序串 PSeqString createNullStr_seq( int m ) { PSeqString pstr=new struct SeqString; //申请串空间 if (pstr!=NULL){ pstr-c=new char[m]; if(pstr-c){ pstr-n=0; pstr-MAXNUM=m; return (pstr); } else delete pstr; } printf(“Out of space!! \n”); return NULL; } 算法3.2 求顺序表示的串的子串 PSeqString subStr_seq(PSeqString s,int i,int j) // 求从s所指的顺序串中第i(i0)个字符开始连续取j个字符所构成的子串 { PSeqString s1; int k; s1 = createNullStr_seq(j); /* 创建一空串 */ if (s1==NULL) return (NULL); if ( i0 i=s-n j0 ) { if ( s-ni+j-1 ) j = s-n-i+1; /*若从i开始取不了j个字符,则能取几个就取几个*/ for (k=0;kj;k++) s1-c[k]=s-c[i+k-1]; s1-n=j; } return(s1); } struct StrNo