《数据结构教程》第4章串.ppt
《《数据结构教程》第4章串.ppt》由会员分享，可在线阅读，更多相关《《数据结构教程》第4章串.ppt（70页珍藏版）》请在装配图网上搜索。
第4章串,4.1串的基本概念,4.2串的存储结构,本章小结,4.3串的模式匹配,串(或字符串),是由零个或多个字符组成的有穷序列。含零个字符的串称为空串,用Ф表示。串中所含字符的个数称为该串的长度(或串长)。通常将一个串表示成"a1a2…an"的形式。其中,最外边的双引号本身不是串的内容,它们是串的标志,以便将串与标识符(如变量名等)加以区别。每个ai(1≤i≤n)代表一个字符。,4.1串的基本概念,当且仅当两个串的长度相等并且各个对应位置上的字符都相同时,这两个串才是相等的。一个串中任意个连续字符组成的子序列(含空串,但不含串本身)称为该串的子串。例如,“a”、“ab”、“abc”和“abcd”等都是“abcde”的子串（平凡子串不包括自身）。,例4.1问题:“abcde”有多少个平凡子串?,解:空串数:1含1个字符的子串数:5含2个字符的子串数:4含3个字符的子串数:3含4个字符的子串数:2共有1+2+3+4+5=15个子串。,串的基本运算如下:(1)StrAssign(intlen;}strtype;其中,ch域用来存储字符串,len域用来存储字符串的当前长度,MaxSize常量表示允许所存储字符串的最大长度。在C语言中每个字符串以\0标志结束。,顺序串中实现串的基本运算如下:(1)StrAssign(str,cstr)将一个字符串常量赋给串str,即生成一个其值等于cstr的串s。voidStrAssign(SqString},(2)StrCopy(s,t)将串t复制给串s。voidStrCopy(SqString},(3)StrEqual(s,t)判断两个串是否相等:若两个串s与t相等返回真(1)；否则返回假(0)。intStrEqual(SqStrings,SqStringt){intsame=1,i;if(s.len!=t.len)same=0;/*长度不相等时返回0*/elsefor(i=0;is.len+1)/*参数不正确时返回空串*/{printf("参数不正确\n");returnstr;},for(k=0;kstr*/str.data[k]=s.data[k];for(k=i+j-1;kstr*/str.data[k-j]=s.data[k];str.len=s.len-j;returnstr;},(9)RepStr(s,i,j,t)在串s中,将第i(1≤i≤StrLength(s))个字符开始的j个字符构成的子串用串t替换,并返回产生的新串。SqStringRepStr(SqStrings,inti,intj,SqStringt){intk;SqStringstr;str.len=0;if(is.len||i+j-1>s.len)/*参数不正确时返回空串*/{printf("参数不正确\n");returnstr;},for(k=0;kstr*/str.data[k]=s.data[k];for(k=0;kstr*/str.data[i+k-1]=t.data[k];for(k=i+j-1;kstr*/str.data[t.len+k-j]=s.data[k];str.len=s.len-j+t.len;returnstr;},(10)DispStr(s)输出串s的所有元素值。voidDispStr(SqStrings){inti;if(s.len>0){for(i=0;inext,*q=t->next;while(p!=NULL},(4)StrLength(s)求串长:返回串s中字符个数。intStrLength(LiString*s){inti=0;LiString*p=s->next;while(p!=NULL){i++;p=p->next;}returni;},(5)Concat(s,t)返回由两个串s和t连接在一起形成的新串。LiString*Concat(LiString*s,LiString*t){LiString*str,*p=s->next,*q,*r;str=(LiString*)malloc(sizeof(LiString));r=str;while(p!=NULL)/*将s的所有结点复制到str*/{q=(LiString*)malloc(sizeof(LiString));q->data=p->data;q->next=NULL;r->next=q;r=q;p=p->next;},p=t->next;while(p!=NULL)/*将t的所有结点复制到str*/{q=(LiString*)malloc(sizeof(LiString));q->data=p->data;q->next=NULL;r->next=q;r=q;p=p->next;}returnstr;},(6)SubStr(s,i,j)返回串s中从第i(1≤i≤StrLength(s))个字符开始的、由连续j个字符组成的子串。LiString*SubStr(LiString*s,inti,intj){intk;LiString*str,*p=s->next,*q,*r;str=(LiString*)malloc(sizeof(LiString));r=str;if(iStrLength(s)||jStrLength(s)){printf("参数不正确\n");returnstr;/*参数不正确时返回空串*/},for(k=0;knext;for(k=1;kstr*/{q=(LiString*)malloc(sizeof(LiString));q->data=p->data;q->next=NULL;r->next=q;r=q;p=p->next;}r->next=NULL;returnstr;},(7)InsStr(s1,i,s2)将串s2插入到串s1的第i(1≤i≤StrLength(s)+1)个字符中,即将s2的第一个字符作为s1的第i个字符,并返回产生的新串。LiString*InsStr(LiString*s,inti,LiString*t){intk;LiString*str,*p=s->next,*p1=t->next,*q,*r;str=(LiString*)malloc(sizeof(LiString));r=str;if(iStrLength(s)+1){printf("参数不正确\n");returnstr;/*参数不正确时返回空串*/},for(k=1;kdata=p->data;q->next=NULL;r->next=q;r=q;p=p->next;}while(p1!=NULL)/*将t的所有结点复制到str*/{q=(LiString*)malloc(sizeof(LiString));q->data=p1->data;q->next=NULL;r->next=q;r=q;p1=p1->next;}while(p!=NULL)/*将*p及其后的结点复制到str*/{q=(LiString*)malloc(sizeof(LiString));q->data=p->data;q->next=NULL;r->next=q;r=q;p=p->next;}r->next=NULL;returnstr;},(8)DelStr(s,i,j)从串s中删去从第i(1≤i≤StrLength(s))个字符开始的长度为j的子串,并返回产生的新串。LiString*DelStr(LiString*s,inti,intj){intk;LiString*str,*p=s->next,*q,*r;str=(LiString*)malloc(sizeof(LiString));r=str;if(iStrLength(s)||jStrLength(s)){printf("参数不正确\n");returnstr;/*参数不正确时返回空串*/},for(k=0;kdata=p->data;q->next=NULL;r->next=q;r=q;p=p->next;}for(k=0;knext;while(p!=NULL)/*将*p及其后的结点复制到str*/{q=(LiString*)malloc(sizeof(LiString));q->data=p->data;q->next=NULL;r->next=q;r=q;p=p->next;}r->next=NULL;returnstr;},(9)RepStr(s,i,j,t)在串s中,将第i(1≤i≤StrLength(s))个字符开始的j个字符构成的子串用串t替换,并返回产生的新串。LiString*RepStr(LiString*s,inti,intj,LiString*t){intk;LiString*str,*p=s->next,*p1=t->next,*q,*r;str=(LiString*)malloc(sizeof(LiString));r=str;if(iStrLength(s)||jStrLength(s)){printf("参数不正确\n");returnstr;/*参数不正确时返回空串*/},for(k=0;kdata=p->data;q->next=NULL;r->next=q;r=q;p=p->next;}for(k=0;knext;while(p1!=NULL)/*将t的所有结点复制到str*/{q=(LiString*)malloc(sizeof(LiString));q->data=p1->data;q->next=NULL;r->next=q;r=q;p1=p1->next;},while(p!=NULL)/*将*p及其后的结点复制到str*/{q=(LiString*)malloc(sizeof(LiString));q->data=p->data;q->next=NULL;r->next=q;r=q;p=p->next;}r->next=NULL;returnstr;},(10)DispStr(s)输出串s的所有元素值。voidDispStr(LiString*s){LiString*p=s->next;while(p!=NULL){printf("%c",p->data);p=p->next;}printf("\n");},例4.3在链串中,设计一个算法把最先出现的子串"ab"改为"xyz"。,解:在串s中找到最先出现的子串"ab",p指向data域值为a的结点,其后为data域值为b的结点。将它们的data域值分别改为x和z,再创建一个data域值为y的结点,将其插入到*p之后。本例算法如下:,voidRepl(LiString*}},4.3串的模式匹配设有主串s和子串t,子串t的定位就是要在主串s中找到一个与子串t相等的子串。通常把主串s称为目标串,把子串t称为模式串,因此定位也称作模式匹配。模式匹配成功是指在目标串s中找到一个模式串t；不成功则指目标串s中不存在模式串t。,4.4.1Brute-Force算法Brute-Force简称为BF算法,亦称简单匹配算法,其基本思路是:从目标串s="s0s1…sn-1"的第一个字符开始和模式串t="t0t1…tm-1"中的第一个字符比较,若相等,则继续逐个比较后续字符；否则从目标串s的第二个字符开始重新与模式串t的第一个字符进行比较。依次类推,若从模式串s的第i个字符开始,每个字符依次和目标串t中的对应字符相等,则匹配成功,该算法返回i；否则,匹配失败,函数返回-1。,intindexpos(SqStringstr,SqStringsubstr){inti,j,k,idx=-1;for(i=0;i
- 配套讲稿：
如PPT文件的首页显示word图标，表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制：
部分文档作品中含有的国旗、国徽等图片，仅作为作品整体效果示例展示，禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词：
- 数据结构教程 数据结构 教程 章串
装配图网所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
链接地址：https://www.zhuangpeitu.com/p-11576798.html