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

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; /* 串的长度，nmaxnum */ char *c; ; typedef struct seqstring *pseqstring;,顺序串的定义,例,算法3.1 创建空顺序串 pseqstring createnullstr_seq( int m ) pseqstring pstr=new struct seqstring; /申请串空间 if (pstr!=null) pstr-c=new charm; 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 ,struct strnode ; typedef struct strnode *pstrnode; struct strnode char c; pstrnode link; ; typedef struct strnode *linkstring;,3.2.2 链接表示,链接串的定义,a,b,f ,.,(a) 不带头结点,a,b,f,.,(b) 带头结点,s,s,a,b,f,.,图3. 2 串的链接表示例,s,(c) 循环表表示,算法3.3 创建带头结点的空链串 linkstring createnullstr_link( void ) linkstring pst; pst=(linkstring)malloc( sizeof(struct strnode) ); if (pst!=null) pst-link = null; else printf(“out of space! n”); return (pst); ,算法3.4 求单链表示的串的子串 linkstring substr_link(linkstring s,int i,int j) / 求从s所指的带头结点的链串中第i(i0)个字符开始 / 连续取j个字符所构成的子串 linkstring s1; pstrnode p,q,t; int k; s1 = createnullstr_link( ); /* 创建空链串 */ if( s1 = null ) printf( “out of space!n“ ); return (null); if (ilink; else return(s1); if (p=null) return(s1);,t = s1; for (k=1;kc = p-c; q-link = null; t-link = q; /* 结点放入子链串中 */ t = q; p = p-link; return(s1); ,模式匹配：子串在主串中的定位操作(mn)。 t=t0 t1 t2 . . . . . . tn-1 目标 p=p0 p1 p2 pm-1 模式 从目标t中查找与模式p完全相同子串的过程。,3.3 模式匹配,3.3.1 朴素的模式匹配,t,a,b,b,b,a,a,p,图3.3 朴素的模式匹配过程,a b a,a b a,a b a,a b a,3.3.1 朴素的模式匹配,模式匹配的最简单的做法是：用p中的字符依次与t中的字符比较：如果t0 = p0，t1 = p1，tm-1 = pm-1，则匹配成功，调用求子串的操作substr(t,1,m)即是找到的子串。否则必有某个i（0im-1），使得ti pi，这时可将p右移一个字符，用p中字符从头开始与t中字符依次比较；如此反复执行，直到下面两种情况之一：或者到达某步时，ti = p0，ti+1 = p1，ti+m-1 = pm-1，匹配成功，substr(t,i+1,m)即是找到的（第一个）与模式p相同的子串；或者一直将p移到无法与t继续比较为止，则匹配失败。,算法3.5 朴素的模式匹配算法 int index(pseqstring t, pseqstring p) / 求p所指的串在t所指的串中第一次出现时， / p所指的串的第一个元素在t所指的串中的序号 int i,j;/i,j分别为p串、t串中当前字符的下标， i=0;j=0; while(in ,主串： “000000000000000000000000000000000000000000001” 模式串： “00000001”,朴素匹配算法简单，易于理解，但效率不高，主要原因是执行中有回溯，一旦比较不等，就将p所指的串右移一个字符，并从p0（算法中用p-c0表示）开始比较。在最坏的情况下，每趟比较都在最后出现不等，最多比较nm1趟，总比较次数为m*(nm1)，由于在一般情况下mn，所以算法运行时间为o(m*n)。,小 结 串是特殊的线性表，是由字符作元素组成的。它和线性表一