《数据结构——串学生讲解反转课堂学习教案.pptx》由会员分享，可在线阅读，更多相关《数据结构——串学生讲解反转课堂学习教案.pptx（45页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、会计学1数据结构数据结构(sh j ji u)串学生讲串学生讲解反转课堂解反转课堂第一页，共45页。目录(ml)content03040201串及其运算(yn sun)串的存储结构(jigu)及实现串的模式匹配实例分析第1页/共45页第二页，共45页。串的应用串的应用(yngyng)(yngyng)程序设计(chn x sh j)中的源程序、目标程序事物处理程序中，顾客(gk)姓名、地址、货物的产地、名称软件系统方面的字符编辑、情报检索、词法分析等多入侵检测系统 DNA序列检测 第2页/共45页第三页，共45页。串的定义串的定义(dngy)(dngy)由零个或多个字符组成的有限(yuxin)序
2、列，一般记作：S=a1a2a3an(1)S为串的名字(mng zi)(2)单引号括起来的字符序列为串的值将串值括起来的单引号本身不属于串，它的作用是避免串与常数或与标识符混淆123 123La La(3)ai(1in)可以是字母、数字或其他字符(4)n为串中字符的个数，称为串的长度特殊的线性表，数据元素限制为字符集第3页/共45页第四页，共45页。(1)空串(2)空白(kngbi)串(3)子串(4)主串(7)位置(wi zhi)(8)相等(xingdng)串(5)前缀子串、真前缀子串(6)后缀子串、真后缀子串(9)模式匹配长度为0的串，不包含任何字符仅由一个或多个空格组成的串，长度1是长度为0
3、的空串 长度为1的空白串串中任意个连续字符组成的子序列包含子串的串空串？自身？B=datastructureA=dataC=data structure字符在串中的序号子串在主串中的位置？两个串的长度相等每个对应位置字符相等子串从主串的某一位置开始，其在主串中首次出现的位置ddadatadatadataatataD=structure主串：A=abcaabcaaabc 子串：B=bca 子串B在主串中，从第1个位置开始的位置是：子串B在主串中，从第2个位置开始的位置是：26第4页/共45页第五页，共45页。串的基本串的基本(jbn)(jbn)运算运算串的抽象数据类型定义(dngy)：ADT S
4、tring数据对象(duxing)：数据关系：基本操作：ADT StringD=ai|aiCharacterSet，i=1,2,n,n0R=|ai-1,aiD，i=2,3,nStrAssign(S,chars)StrCopy(S,T)StrLength(S)StrInsert(S,pos,T)StrDelete(S,pos,len)StrCompare(S,T)StrCat(S,T)SubString(T,S,pos,len)StrIndex(S,pos,T)StrReplace(S,T,V)StrEmpty(S)StrClear(S)StrDestory(S)这些串的基本操作通常以“串的整体
5、”“串的一部分”作为操作对象第5页/共45页第六页，共45页。串的基本串的基本(jbn)(jbn)运算运算 对于以上串的基本操作，C语言的函数库文件 string.h 包括其中几个(j)字符串操作函数：gets(S)输入(shr)字符串puts(S)输出字符串strcat(S1,S2)连接字符串S2至S1后strcmp(S1,S2)比较字符串S1和S2strcpy(S1,S2)复制字符串S2至S1strlen(S)求字符串S的有效长度第6页/共45页第七页，共45页。串的基本串的基本(jbn)(jbn)运算运算StrInsert(S,pos,T)例:S=chater,T=rac,运行(ynxn
6、g)StrInsert(S,4,T)在字符串S的第pos个字符之前(zhqin)插入字符串T串S和串T存在，1posStrLength(S)+1操作结果：初始条件：结果：S=character第7页/共45页第八页，共45页。串的基本串的基本(jbn)(jbn)运算运算StrDelete(S,pos,len)例:S=chapter,运行(ynxng)StrDelete(S,5,3)从串S中删除(shnch)从第pos个字符开始连续len个字符后形成的子串串S存在，1posStrLength(S)-len+1操作结果：初始条件：结果：S=chap第8页/共45页第九页，共45页。串的基本串的基本
7、(jbn)(jbn)运算运算StrCat(S,T)例:S=man,运行(ynxng)StrCat(S,kind)将字符串T的值连接(linji)在串S的后面串S和串T存在操作结果：初始条件：结果：S=mankind第9页/共45页第十页，共45页。串的基本串的基本(jbn)(jbn)运算运算SubString(T,S,pos,len)例:S=commander,运行(ynxng)SubString(T1,S,4,3)截取字符串S中从第pos个字符开始(kish)连续len个字符形成的子串，并赋值给串T串S存在，1posStrLength(S)且0lenStrLength(S)-pos+1操作结
8、果：初始条件：结果：T1=man运行SubString(T2,S,5,0)运行SubString(T3,S,4,7)结果：T2=结果 T3无结果，函数返回错误第10页/共45页第十一页，共45页。串的基本串的基本(jbn)(jbn)运算运算StrIndex(S,pos,T)例:S=abcaabcaaabc,T=bca,运行(ynxng)StrInsert(S,1,T)若字符串S从第pos个字符后存在与字符串T相等的子串，则返回(fnhu)字符串T在串S中第pos个字符后首次出现的位置，否则返回(fnhu)0串S和串T存在，1posStrLength(S)操作结果：初始条件：结果：2运行StrI
9、nsert(S,4,T)结果：6第11页/共45页第十二页，共45页。串的基本串的基本(jbn)(jbn)运算运算StrReplace(S,T,V)例:S=abcaabcaaabca,T=bca,若V=x运行(ynxng)StrReplace(S,T,V)用字符串V替换字符串S中出现的所有与串T相等(xingdng)的不重叠的子串串S和串V存在，且串T为非空串操作结果：初始条件：结果：S=axaxaax若V=bc运行StrReplace(S,T,V)结果：S=abcabcaabc第12页/共45页第十三页，共45页。串的存储结构串的存储结构(jigu)(jigu)及及实现实现1.定长顺序(sh
10、nx)串2.堆串3.块链串 与线性表的顺序存储结构类似，使用一组地址与线性表的顺序存储结构类似，使用一组地址(dzh)(dzh)连续的存储单元存储串的字符序列，也称为静态存储分配的连续的存储单元存储串的字符序列，也称为静态存储分配的顺序串。直接使用定长的字符数组来定义。顺序串。直接使用定长的字符数组来定义。与定长顺序串类似，都是用一组地址连续的存储单元存储串与定长顺序串类似，都是用一组地址连续的存储单元存储串的字符序列，的字符序列，不同不同的是：其存储空间是的是：其存储空间是动态分配动态分配的的 采用采用链式链式存储结构，链表的每个节点可存放一个或多存储结构，链表的每个节点可存放一个或多个字符
11、，每个节点称为个字符，每个节点称为块块第13页/共45页第十四页，共45页。串的存储结构串的存储结构(jigu)(jigu)及实现及实现定长顺定长顺序串序串#define MAXLEN 50typedef struct char chMAXLEN+1;int len ;SString;存储(cn ch)结构截断(ji dun)串的实际长度在预定义长度MAXLEN的范围内随意变动时，超过MAXLEN，串值被舍去的情况字符串长度 0 或者 len ，此时0号单元格不用第14页/共45页第十五页，共45页。串的存储结构及实现串的存储结构及实现(shxin)(shxin)定长顺定长顺序串序串串插入(c
12、h r)函数Case 1 插入(ch r)后串长MAXLEN 在进行串的插入时，插入位置pos将位置分为两部分，记为A、B,长度分别为LA、LB，记插入部分为T,长度为LTCase 2 插入后串长MAXLEN，且pos+LTMAXLENCase 3 插入后串长MAXLEN，且pos+LTMAXLEN第15页/共45页第十六页，共45页。串的存储串的存储(cn ch)(cn ch)结构及实现结构及实现定定长顺序串长顺序串串插入(ch r)函数int SStrInsrt (SString *S ,int pos ,const SString T)int i ;if(NULL=S|NULL=S-ch
13、|NULL=T.ch|pos S-len+1)return 0 ;return 1;if(S-len+T.lenlen+T.len;i pos+T.len;i-)S-chi=S-chi-T.len;for(i=pos;i chi=T.chi-pos+1;S-len=S-len+T.len;else if(pos+T.lenMAXLEN;i pos+T.len;i-)S-chi=S-chi-T.len;for(i=pos;i chi=T.chi-pos+1;S-len=MAXLEN;else for(i=pos;ichi=T.chi-pos+1;S-len=MAXLEN;#define MAXL
14、EN 50typedef struct char chMAXLEN+1;int len ;SString;第16页/共45页第十七页，共45页。串的存储串的存储(cn ch)(cn ch)结构及实现结构及实现定长顺定长顺序串序串串删除(shnch)函数int SStrDelete (SString *S ,int pos ,int len)int i=1;if(NULL=S|NULL=S-ch|len 0|pos S-len-len+1)return 0 ;return 1;for(i=pos;ilen-len;i+)S-chi=S-chi+len;S-len=S-len-len;#defin
15、e MAXLEN 50typedef struct char chMAXLEN+1;int len ;SString;第17页/共45页第十八页，共45页。串的存储串的存储(cn ch)(cn ch)结构及实现结构及实现定长顺定长顺序串序串串连接(linji)函数Case 1 连接(linji)后串长MAXLEN 在进行串的连接时，假设原始串为S,长度为LS，待连接串为T,长度为LTCase 2 连接后串长MAXLEN，且LAch|NULL=T.ch)return 0 ;else return 0;if(S-len+T.lenlen+1;ilen+T.len;i+)S-chi=T.chi-S-
16、len;S-len=S-len+T.len;return 1;else if(S-lenlen+1;ichi=S-chi-S-len;S-len=MAXLEN;return 0;#define MAXLEN 50typedef struct char chMAXLEN+1;int len ;SString;第19页/共45页第二十页，共45页。串的存储串的存储(cn ch)(cn ch)结构及实现结构及实现定定长顺序串长顺序串求子串函数(hnsh)int SubSString (SString *T,SString S ,int pos ,int len)int i=1;if(NULL=T|N
17、ULL=T-ch|len 0|pos S-len|NULL=S.ch|lenS.len pos+1)return 0 ;for(i=1;ichi=S.chpos+i-1;T-len=len;return 1;弊端(b dun)：截断问题第20页/共45页第二十一页，共45页。串的存储结构串的存储结构(jigu)(jigu)及实现及实现堆串堆串 不限定串的最大长度，动态地分配串值的存储空间，只要存储空间能分配成功(chnggng)，则在操作的过程中就不会出现“截断”的情况。存储(cn ch)结构：typedef struct char *ch;int len;HString;串初始化函数：voi
18、d HStrInt(HString*S)S-ch=NULL;S-len=0;第21页/共45页第二十二页，共45页。串的存储结构串的存储结构(jigu)(jigu)及实现及实现堆串堆串串赋值函数(hnsh)：typedef struct char *ch;int len;HString;int HStrAssign(HString*S,const char*chars)int i=0;if(NULL=chars|NULL=S)return 0;while(charsi!=0)i+;S-len=i;if(0!=S-len)if(S-ch!=NULL)free(S-ch);S-ch=(char*)
19、malloc(S-len+1)*sizeof(char);if(NULL=S-ch)return 0;for(i=1;ilen;i+)S-chi=charsi-1;else S-ch=NULL;return 1;第22页/共45页第二十三页，共45页。串的存储串的存储(cn ch)(cn ch)结构及实现结构及实现堆串堆串 typedef struct char *ch;int len;HString;串插入(ch r)函数：int HStrInsert(HString*S,int pos,const HString T)int i;char*temp;if(NULL=S|NULL=S-ch|
20、NULL=T.ch|posS-len|poslen+T.len+1)*sizeof(char);if(NULL=temp)return 0;for(i=1;ichi;for(i=pos;ipos+T.len;i+)tempi=T.chi-pos+1;for(i=pos+T.len;ilen+T.len;i+)tempi=S-chi-T.len;free(S-ch);S-ch=temp;S-len=S-len+T.len;return 1;第23页/共45页第二十四页，共45页。串的存储结构串的存储结构(jigu)(jigu)及实现及实现堆串堆串 typedef struct char *ch;
21、int len;HString;串删除(shnch)函数：int HStrDelete(HString*S,int pos,int len)int i;char*temp;if(NULL=S|NULL=S-ch|len0|posS-len-len+1)return 0;temp=(char*)malloc(S-len-len+1)*sizeof(char);if(NULL=temp)return 0;for(i=1;ichi;for(i=pos;ilen-len;i+)tempi=S-chi+len;free(S-ch);S-ch=temp;S-len=S-len-len;return 1;第
22、24页/共45页第二十五页，共45页。串的存储结构串的存储结构(jigu)(jigu)及实现及实现堆串堆串 typedef struct char *ch;int len;HString;串连接(linji)函数：int HStrCat(HString*S,const HString T)int i=1;if(NULL=S|NULL=S-ch|NULL=T.ch)return 0;S-ch=(char*)realloc(S-ch,(S-len+T.len+1)*sizeof(char);if(NULL=S-ch)return 0;for(i=S-len+1;ilen;i+)S-chi=T.ch
23、i-S-len;S-len=S-len+T.len;return 1;第25页/共45页第二十六页，共45页。串的存储结构串的存储结构(jigu)(jigu)及实现及实现堆串堆串 typedef struct char *ch;int len;HString;求子串函数(hnsh)：int SubHString(HString*THString S,int pos,int len)int i=1;if(NULL=T|NULL=T-ch|NULL=S.ch|lenS.len-pos+1|posS.le)return 0;T-len=len;if(NULL!=T-ch)free(T-ch);T-c
24、h=(char*)malloc(T-len+1)*sizeof(char);if(NULL=T-ch)return 0;for(i=1;ilen;i+)T-chi=S.chpos+i-1;return 1;第26页/共45页第二十七页，共45页。串的存储结构串的存储结构(jigu)(jigu)及实现及实现块链串块链串块链的存储(cn ch)结构#define BLOCK_SIZE 4typedef struct block char chBLOCK_SIZE;struct block*next;Block;typedef structBlock*head;Block*tail;int len;
25、LString;因需要连接字符串，设置尾指针可便于操作，注意连接时需要处理第一个串的最后一个结点(ji din)中的无效字符块大小，指块链表中结点存放字符的个数。在这种存储方式中，块大小直接影响到串处理的效率，因此就需要考虑串值的存储密度。第27页/共45页第二十八页，共45页。串的存储结构串的存储结构(jigu)(jigu)及实现及实现块链块链串串存储密度=串值所占的存储(cn ch)位实际分配(fnpi)的存储位当BLOCK_SIZE1：当BLOCK_SIZE=1：此时块链表结构同线性链表其存储密度为1/3由于串长不一定是块大小的整数倍，则链表的最后一个结点不一定完全被串值所占满，此时需补
26、上#或其他字符块大小为4的块链表，其存储密度为1/2ABCDI#EFGHheadtail第28页/共45页第二十九页，共45页。串的模式匹配串的模式匹配定义(dngy)：找字串在主串中从第pos个字符后首次出现(chxin)的位置应用(yngyng)：文本编辑软件中的查找电子字典中查阅英文单词S a c a b a b a a c b a b a aT a b a a从S的第1个字符开始，T首次出现的位置为：从S的第7个字符开始，T首次出现的位置为：511第29页/共45页第三十页，共45页。串的模式匹配串的模式匹配算法(sun f)：BF模式匹配算法(sun f)KMP模式匹配算法(sun
27、f)目标串：主串S模式串：子串Ta c a b a b a a c b a ba b a a第30页/共45页第三十一页，共45页。串的模式匹配串的模式匹配BFBF算法算法(sun f)(sun f)Brute-Force 算法(sun f)，蛮力匹配算法(sun f)a c a b a b a a c b a ba b a a第一趟匹配第一趟匹配(ppi)(ppi)第二趟匹配第二趟匹配第三趟匹配第三趟匹配第四趟匹配第四趟匹配第五趟匹配第五趟匹配a c a b a b a a c b a b a b a a a c a b a b a a c b a b a b a aa c a b a b
28、a a c b a b a b a aa c a b a b a a c b a b a b a ai=1j=1i=2j=2i=2i=3i=6i=4i=9i=5j=1j=1j=1j=4j=1j=5字符相等i+;j+;字符不相等 j=1;i 回溯 i=2-2+2 i=2-1+2 i=6-4+2 i=4-1+2 匹配成功的条件 规律：i=i-j+2 jT.len,返回i-T.len第31页/共45页第三十二页，共45页。串的模式匹配串的模式匹配BFBF算法算法(sun f)(sun f)int Index(SString S，int pos,SString T)int i=pos,j=1;whil
29、e(i=S.len&j T.len)return i-T.len;else return 0;else i=i-j+2;j=1;BF算法(sun f)的时间复杂度第32页/共45页第三十三页，共45页。串的模式匹配串的模式匹配KMPKMP模式匹配算法模式匹配算法(sun f)(sun f)由D.E.Knuth、J.H.Morris和V.R.Pratt共同提出(t ch)的改进算法KMP算法(sun f)与BF算法(sun f)的不同之处：消除 主串S的指针 回溯a b a b c a b c a c b a ba b c a c第一趟匹配第一趟匹配i=1j=3第二趟匹配第二趟匹配第三趟匹配第三
30、趟匹配a b a b c a b c a c b a b a b c a ca b a b c a b c a c b a b a b c a ci=3i=3i=7i=11i=7j=1j=1j=2j=5j=6第33页/共45页第三十四页，共45页。串的模式匹配串的模式匹配KMPKMP模式匹配算法模式匹配算法(sun(sun f)f)S=S1S2 Si-j+1S i-j+2 Si-k+1 Si-1 Si SnT=T1 T2 Tj-k+1 Tj-1 Tj T=T1 Tk-1Tk 0 当当j=1nextj=Max1kj且且T1 Tk-1=T j-k+1 Tj-1 当此集合当此集合(jh)不为空时不为
31、空时 1 其他情况其他情况第34页/共45页第三十五页，共45页。串的模式匹配串的模式匹配KMPKMP模式匹配算法模式匹配算法(sun f)(sun f)模式串模式串abaabcac的的next值推导值推导(tudo)过过程程当当j=1时，时，next1=0当当j=2时，时，next2=1j值子串真前缀子串真后缀子串结果 3 ab 串不等串不等 a b ab 串不等串不等 a a ba aba 串长度(chngd)为14 j12345678 串串abaabcacnextj011221235子串长度为子串长度为1 1串不等串不等ab串不等串不等abaabaabaaaaaa子串长度为2串不等aba
32、baaabaab6baabab串不等aababaabaabc7abaabbaabc串不等abaaaabc串不等abaabc串不等abbc串不等串不等ac8abaabcaabaabcabaabbaabcaaabcaabaaabcaababcaabcaaa串不等串不等串不等串不等子串长度为1串不等继而讨论如何用算法求已知模式串next函数值：第35页/共45页第三十六页，共45页。串的模式匹配串的模式匹配KMPKMP模式匹配算法模式匹配算法(sun(sun f)f)T=T1 Tk-1 Tk T=T=T1 Tj-k+1 Tj-1 Tj Tm=(1)nextj+1 =k+1=nextj+1Tj-k,+
33、1 Tj-1 Tj TmTj-k,+1 Tk-1 Tk T1 Tk,-1 Tk,=nextk (2)若若Tj=Tk,则则nextj =k+1=nextk+1 若若Tj Tk,则继续则继续(jx)比较比较Tj和和Tnextk，即比较，即比较Tj和和Tnextnextk 然后一直然后一直(yzh)重复下去，若直到最后重复下去，若直到最后j=0时都一时都一直直(yzh)比较不成功，则比较不成功，则nextj=1 .第36页/共45页第三十七页，共45页。串的模式匹配串的模式匹配KMPKMP模式匹配算法模式匹配算法(sun f)(sun f)void Get_Next(SString T，int ne
34、xt)int j=1,k=0;next 1=0;while(j=T.len)if (k=0|T.ch j=T.chk)+j;+k;nextj=k;else k=next k;第37页/共45页第三十八页，共45页。串的模式匹配串的模式匹配KMPKMP模式匹配算法模式匹配算法(sun f)(sun f)a c a b a a b a a b c a c a a b ca b a a b c a c 第一趟匹配第一趟匹配(ppi)(ppi)i=1j=2第二趟匹配第二趟匹配(ppi)(ppi)第三趟匹配第三趟匹配i=2i=2i=8i=14i=8j=1j=1j=3j=1j=9在求得模式串的next函数
35、之后，匹配可按如下方式进行 j12345678 串串abaabcacnextj01122312a c a b a a b a a b c a c a a b c a b a a b c a c a c a b a a b a a b c a c a a b c a b a a b c a c a c a b a a b a a b c a c a a b c a b a a b c a c 第四趟匹配第四趟匹配next2=1next1=0next6=3j=6i=3第38页/共45页第三十九页，共45页。串的模式匹配串的模式匹配KMPKMP模式匹配算法模式匹配算法(sun f)(sun f)in
36、t Index_KMP(SString S，int pos,SString T)int i=pos,j=1;while(i=S.len&j T.len)return i T.len;else return 0;KMP算法(sun f)的时间复杂度O(n+m)第39页/共45页第四十页，共45页。串的模式匹配串的模式匹配KMPKMP模式匹配算法模式匹配算法(sun(sun f)f)a a a b a a a a b a a a a b 第一趟匹配第一趟匹配(ppi)(ppi)i=1j=4第二趟匹配第二趟匹配(ppi)(ppi)第三趟匹配第三趟匹配i=4i=4i=5i=10i=4j=1j=3j=1
37、j=2j=1但是上述定义的next函数在某些情况下是有缺陷的：j12345 串串aaaabnextj01234a a a b a a a a b a a a a b a a a b a a a a b a a a a b a a a b a a a a b a a a a b 第四趟匹配第四趟匹配next4=3next3=2next2=1j=6i=4next1=0a a a b a a a a b a a a a b 第五趟匹配第五趟匹配第40页/共45页第四十一页，共45页。串的模式匹配串的模式匹配KMPKMP模式匹配算法模式匹配算法(sun f)(sun f)a a a b a a a a
38、 b a a a a b 第一趟匹配第一趟匹配(ppi)(ppi)j=4i=1j=1j=6a a a b a a a a b a a a a b 第二趟匹配第二趟匹配(ppi)(ppi)i=4i=5i=10j=1T=T1 Tk-1 Tk T=T=T1 Tj-k+1 Tj-k,+1 Tj-1 Tj TmTj-k,+1 Tk-1 Tk T1 Tk,-1 Tk,=nextk=nextvalj=nextjnextvalj=nextvalnextj j12345 串串aaaabnextj01234nextvalj00004第41页/共45页第四十二页，共45页。串的模式匹配串的模式匹配KMPKMP模式匹
39、配算法模式匹配算法(sun f)(sun f)int Get_Nextval(SString T,int next,int nextval)int j=2,k=0;Get_Next(T,next);nextval 1=0;if (T.chj=T.chk)nextvalj=nextvalk;elsenextvalj=nextj;while(j=T.len)j+;第42页/共45页第四十三页，共45页。实例分析实例分析简单简单(jindn)(jindn)文本编辑器文本编辑器软件软件页、行、字符(z f)typedef struct WHString char*ch;int len;struct WHString*next;struct WHString*pre;int row;WHString;输入、统计(tngj)、查找、删除、插入第43页/共45页第四十四页，共45页。Thanks.Made by W_L第44页/共45页第四十五页，共45页。