字符串与模式匹配算法

《字符串与模式匹配算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、字符串与模式匹配算法2009/03/05内容：作业讲解字符串概念与抽象数据类型串模式匹配21-1链表插入31-2按逆序输出41-3删除重复值节点51-3删除重复值节点61-3删除重复值节点71-3删除重复值节点8循环链表合并（2-1）91011字符串基本概念字符串简称串，是一种特殊的线性表，其特殊性主要在于表中的每个元素是一个字符。一个串可以记作s="s0s1…sn-1"（n≥0），其中s是串的名字，双引号括起来的字符序列s0s1…sn-是串的值。例如：A="123"B="ABBABBC"C="BB"D="

2、BB"E=""1213C语言中定义的字符串存储结构：字符指针…操作：char*strcpy(char*dst,char*sorc)intstrcmp(char*str1,char*str2);char*strcat(char*dest,constchar*sorc,size);char*strstr(char*str,constchar*strSearch);size_tstrlen(constchar*str);gets(char*);puts(char*);1415由字符串构成的线性

3、表16自定义字符串ADTStringcreateNullStr(void)创建一个空串。intIsNullStr(Strings)判断串s是否为空串，若为空串，则返回1，否则返回0。intlength(Strings)返回串s的长度。Stringconcat(Strings1,Stings2)返回将串s1和s2拼接在一起构成的一个新串。StringsubStr(Strings,inti,intj)在串s中，求从串的第i个字符开始连续j个字符所构成的子串。intindex(Strings1,Strings2)如果串

4、s2是s1的子串，则可求串s2在串s1中第一次出现的位置。17顺序结构字符串ADT的定义structSeqString{/*顺序串的类型*/intMAXNUM;/*串允许的最大字符个数*/intn;/*串的长度，nMAXNUM*/char*c;};typedefstructSeqString*PSeqString;18顺序串示例s=“abcdefg”abcdefgs.n=7s.c0123456MAXNUM-119自定义字符串ADT——创建顺序结构空串PSeqStringcreateNullStr_seq(int

5、m){PSeqStringpstr=(PSeqString)malloc(sizeof(structSeqString));if(pstr!=NULL){pstr->c=(char*)malloc(sizeof(char)*m);if(pstr->c！=NULL){pstr->n=0;pstr->MAXNUM=m;return(pstr)}elsefree(pstr);}printf("Outofspace!!");returnNULL;}structSeqString{intMAXNUM;intn;char

6、*c;};20自定义字符串ADT——初始化字符串21自定义字符串ADT——取指定子串22链接结构字符串ADT的定义structStrNode;/*链串的结点*/typedefstructStrNode*PStrNode;/*结点指针类型*/structStrNode{/*链串的结点结构*/charc;PStrNodelink;};typedefstructStrNode*LinkString;/*链串的类型*/字符串结尾？长度？23字符串的链接存储示例sabcd^sabcd^不带头结点带头结点abcds带尾指针的

7、循环链表24链接存储字符串的基本运算创建空链串联结两个串取单链串的子串删除子串追加方式插入子串子串定位[模式匹配]求串长25创建带头结点的空链串LinkStringcreateNullStr_link(void){LinkStringpst;pst=(LinkString)malloc(sizeof(structStrNode));if(pst!=NULL)pst->link=NULL;elseprintf("Outofspace!");/*创建失败*/return(pst);}26取单链串的子串27串模式匹

8、配问题设有两个串t和p:t=t0t1…tn-1，p=p0p1…pm-1其中1