数据结构four

《数据结构four》由会员分享，可在线阅读，更多相关《数据结构four（70页珍藏版）》请在装配图网上搜索。

1、121 1、熟悉串七种基本操作的定义，并能利用、熟悉串七种基本操作的定义，并能利用这些基本操作实现传的其他各种操作的方法。这些基本操作实现传的其他各种操作的方法。2 2、熟悉掌握在串的定长顺序存储结构上、熟悉掌握在串的定长顺序存储结构上实现串的各种操作的方法。实现串的各种操作的方法。3 3、掌握串的堆存储结构以及在其上实现串、掌握串的堆存储结构以及在其上实现串的各种操作的基本方法。的各种操作的基本方法。4 4、理解串匹配的、理解串匹配的 KMPKMP算法，熟悉算法，熟悉 next next 函函数的定义，学会手工计算给定模式串的数的定义，学会手工计算给定模式串的nextnext函数值和改进的函

2、数值和改进的 nextnext函数值。函数值。3 4ADT String 数据对象数据对象：D ai|aiCharacterSet,i=1,2,.,n,n0 数据关系数据关系：R1|ai-1,ai D,i=2,.,n 串是有限长的字符序串是有限长的字符序列，由一对单引号相列，由一对单引号相括，如括，如:a string 4.14.1串的抽象数据类型的定义串的抽象数据类型的定义5 基本操作基本操作：StrAssign(&T,chars)StrCopy(&T,S)DestroyString(&S)StrEmpty(S)StrCompare(S,T)StrLength(S)Concat(&T,S1,

3、S2)6SubString(&Sub,S,pos,len)Index(S,T,pos)Replace(&S,T,V)StrInsert(&S,pos,T)StrDelete(&S,pos,len)ClearString(&S)ADT String7 StrAssign(&T,chars)初始条件：chars 是字符串常量。操作结果：把 chars 赋为T 的值。StrCopy(&T,S)初始条件：。操作结果：由串 S 复制得串T。89 DestroyString(&S)初始条件：串 S 存在。操作结果：串 S 被销毁。StrEmpty(S)初始条件：串S存在。操作结果：若S为空串，则返回TRU

4、E;否则返回 FALSE。表示空串，空串的长度为零。1011例如：例如：StrCompare(data,state)0StrCompare(S,T)初始条件：初始条件：串S和T存在。操作结果：操作结果：若S T，则返回值 0；若S T，则返回值 0；若S T，则返回值 0。12 StrLength(S)：13C o n c a t(&T,S 1,S 2)例如例如：Concate(T,man,kind)求得 T=mankind14 SubString(&Sub,S,pos,len)15SubString(sub,commander,4,3)求得 sub=man；SubString(sub,com

5、mander,1,9)求得 sub=commander；SubString(sub,commander,9,1)求得 sub=r；子串为子串为“串串”中的一个字符子序列中的一个字符子序列16SubString(sub,commander,4,7)sub=?SubString(student,5,0)=manderg17I n d e x(S,T,p o s)初始条件：初始条件：串S和T存在，T是非空串，1posStrLength(S)。操作结果：操作结果：相同的子串,则返回它在主串s中第pos个字符之后第一次出现的位置,否则函数值为0.18 Index(S,T,1)=2；Index(S,T,3

6、)=6；Index(S,T,8)=0；“子串在主串中的位置子串在主串中的位置”意指子串中的第一个字符在主串中的位序位序。19 Replace(&S,T,V)初始条件串S,T和 V 均已存在,且 T 是非空串。操作结果：用V替换主串S中出现 的所有与(模式串)T相 等的不重叠的子串。20 S=abcaabcaaabca，T=bca x，则经置换后得到 S=axaxaax若 V=bc，则经置换后得到 S=abcabcaabc21StrInsert(&S,pos,T)初始条件：串S和T存在，1posStrLength(S)1。操作结果：在串S的第pos个字符 之前插入串T。例如：例如：S=chate

7、r，T=rac，则执行 StrInsert(S,4,T)之后得到 S=character22StrDelete(&S,pos,len)初始条件：串S存在 1posStrLength(S)-len+1。操作结果：从串S中删除第pos个 字符起长度为len的子串。ClearString(&S)初始条件：串S存在。操作结果：将S清为空串。2324 对于串的基本操作集可以有不同的定义方法，在使用高级程序设计语言中的串类型时，应以该语言的参考手册为以该语言的参考手册为准准。gets(str)输入一个串；puts(str)输出一个串；strcat(str1,str2)串联接函数；strcpy(str1,s

8、tr2,k)串复制函数；strcmp(str1,str2)串比较函数；strlen(str)求串长函数；例如：C语言函数库中提供下列串处理函数：25在上述抽象数据类型定义的13种操作中，串赋值串赋值StrAssignStrAssign、串复制、串复制StrcopyStrcopy、串比较串比较StrCompareStrCompare、求串长、求串长StrLengthStrLength、串联接串联接ConcatConcat以及求子串以及求子串SubStringSubString等六种操作构成串类型的最小操作子集等六种操作构成串类型的最小操作子集。即：这些操作不可能利用其他串操作来实现，反之，其他串

9、操作（除串清除ClearString和串 销毁DestroyString外）可在这个最小操作子集上实现。26 例如，可利用串比较、求串长和求子串等操作实现定位函数Index(S,T,pos)。算法的基本思想为：算法的基本思想为：StrCompare(SubString(S,i,StrLength(T),T)?0 S 串 T 串 T 串iposn-m+127int Index(String S,String T,int pos)/T为非空串。若主串为非空串。若主串S中第中第pos个字符之后存在与个字符之后存在与 T相等的子串相等的子串，则返回第一个，则返回第一个 这样的子串在这样的子串在S中的位

10、置，否则返回中的位置，否则返回0 if(pos 0)n=StrLength(S);m=StrLength(T);i=pos;while(i=n-m+1)SubString(sub,S,i,m);if(StrCompare(sub,T)!=0)+i;else return i;/while /if return 0;/S中不存在与T相等的子串/Index28又如串的置换函数：S 串 T 串 V 串 V 串pospos subinews 串sub29 串串的逻辑结构和线性表线性表极为相似，区别区别仅在于串的数据对象约束为字符集。串的基本操作和线性表有很大串的基本操作和线性表有很大差别。差别。在线性

11、表的基本操作中,大多大多以以“单个元素单个元素”作为操作对象作为操作对象;在串的基本操作中，通常以通常以“串的整体串的整体”作为操作对象作为操作对象。30 在程序设计语言中，串只是作为输入或输出的常量出现，则只需存储此串的串值，即字符序列即可。但在多数非数值处理的程序中，串也以变量的形式出现。31一、串的定长顺序存储表示一、串的定长顺序存储表示二、串的堆分配存储表示二、串的堆分配存储表示三、串的块链存储表示三、串的块链存储表示32#define MAXSTRLEN 255/用户可在255以内定义最大串长 typedef unsigned char Sstring MAXSTRLEN+1;/0号

12、单元存放串的长度33v 按这种串的表示方法实现的串的运算时，其基本操作为 v 串串的实际长度可在这个予定义长度的范围内随意设定,超过予定义长度的串值则被舍去,称之为“截断截断”。特点特点:34Status StrInit(String s)int i;for(i=0;i=MAXSTRING;+i)si=0;return OK;Status StrAssign(String s,char*t)char*p;int i;p=t;i=1;while(*p&i=MAXSTRING)si=*p;+i;+p;s0=i-1;return OK;/如果串t的长度大于MAXSTRING,则t被截断35Statu

13、s StrLength(String s)return s0;Status StrCopy(String s,String t)int i;for(i=0;iStrLength(t)?StrLength(t):StrLength(s);while(si=ti&iti)return 1;if(siti)return-1;if n StrLength(s)return 1;if n StrLength(t)return 1;return 0;37Status Concat(String t,String s1,String s2)int i,len,j;i=1;j=1;for(i=1;i=StrL

14、ength(s2)?StrLength(s2):(MAXSTRING-StrLength(s1);for(;j=len;+i,j+)ti=s2j;t0=i-1;return OK;/注意注意StrLength(s1)+StrLength(s2)StrLength(s1)+StrLength(s2)大于大于MAXSTRINGMAXSTRING，要截断，要截断38Status SubString(String sub,String s,int pos,int len)int i,j,n;j=1;if(posStrLength(s)StrInit(sub);return ERROR;if(lenSt

15、rLength(s)-pos+1)StrInit(sub);return ERROR;n=(len=StrLength(s)-pos+1?len:StrLength(s)-pos+1);for(i=pos;i=n;+i)subj=si;+j;sub0=j-1;return OK;39Status StrInsert(String s,int pos,String t)String s1,s2,s3;StrInit(s1);StrInit(s2);StrInit(s3);if(posStrLength(s)+1)return ERROR;SubString(s1,s,1,pos-1);SubSt

16、ring(s2,s,pos,StrLength(s)-pos+1);Concat(s3,s1,t);Concat(s,s3,s2);return OK;40Status StrDel(String s,int pos,int len)String s1,s2;if(posStrLength(s)return ERROR;if(lenStrLength(s)-pos+1)return ERROR;StrInit(s1);StrInit(s2);SubString(s1,s,1,pos-1);SubString(s2,s,pos+len,StrLength(s)-pos-len+1);Concat

17、(s,s1,s2);return OK;41 typedef struct char*ch;/若是非空串,则按串长分配存储区，/否则ch为NULL int length;/串长度 HString,*LString;二、串的堆分配存储表示二、串的堆分配存储表示42 通常，C语言中提供的串类型就是以这种存储方式实现的。系统利用函数malloc()和free()进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为“堆堆”。C语言中的串以一个空字符为结束符，串长是一个隐含值。这类串操作实现的算法为：先为新生成的串分配一个存储空间，然后进行串值的复制。43Status Str

18、Assign(Lstring t,char*chars)char*c;if(t-ch)free(t-ch);for(i=0,c=chars;*c;+i,+c);/求求charschars的长度的长度 if(!i)t-ch=NULL;t-length=0;else t-ch=(char*)malloc(i*sizeof(char);if(!(t-ch)exit OVERFLOW;t-ch0,1,i-1=chars0,1,i-1;t-length=i;return OK;44int StrLength(Lstring s)return s-length;int StrCompare(Lstring

19、 s,Lstring t)int i;for(i=0;ilength&ilength;+i)if(si!=ti)return s-chi-t-chi;return s-length-t-length;Status ClearString(LString s)if(s-ch)free(s-ch);s-ch=NULL;s-length=0;return OK;45Status Concat(LString T,LString S1,LString S2)if(!(T-ch=(char*)malloc(S1-length+S2-length)*sizeof(char)exit(OVERFLOW);T

20、-ch0.S1-length-1=S1-ch0.S1-length-1;T-length=S1-length+S2-length;T-chS1-length.T-length-1=S2-ch0.S2-length-1;return OK;/Concat46 Status)/用用Sub返回串返回串S的第的第pos个字符起长度为个字符起长度为len的子串的子串 if if(!len)Sub-ch=NULL;Sub-length=0;else return OK;/SubString 47 Sub-ch=(char*)malloc(len*sizeof(char);Sub-ch0.len-1=S-c

21、hpos-1.pos+len-2;Sub-length=len;48Status StrInsert(LString s,int pos,HString t)LString s1,s2,s3;ClearStr(s1);ClearStr(s2);CLearStr(s3);if(posStrLength(s)+1)return ERROR;SubString(s1,s,1,pos-1);SubString(s2,s,pos,StrLength(s)-pos+1);Concat(s3,s1,&t);Concat(s,s3,s2);return OK;49Status StrDel(LString s

22、,int pos,int len)LString s1,s2;if(posStrLength(s)return ERROR;if(lenStrLength(s)-pos+1)return ERROR;ClearStr(s1);ClearStr(s2);SubString(s1,s,1,pos-1);SubString(s2,s,pos+len,StrLength(s)-pos-len+1);Concat(s,s1,s2);return OK;50存储密度存储密度=51#define CHUNKSIZE 80 /可由用户定 /义的块大小 typedef struct Chunk /结点结构 ch

23、ar chCUNKSIZE;struct Chunk *next;Chunk;typedef struct /串的链表结构 Chunk*head,*tail;/串的头和尾指针 int curlen;/串的当前长度 LString;52 例如:在编辑系统中，整个文本编辑区可以看成是一个串，每一行是一个子串，构成一个结点。即:同一行的串用定长结构(80个字符),行和行之间用指针相联接。实际应用时，可以根据问题所需来设置结点的大小。53 这是串的一种重要操作，很多软件，若有“编辑编辑”菜单项的话，则其中必有“查找查找”子菜单项。4.34.3 串的模式匹配算法串的模式匹配算法54初始条件：串S和T存在

24、，T是非空串，1posStrLength(S)。操作结果：若主串S中存在和串T值相 同的子串返回它在主串S中 第pos个字符之后第一次出 现的位置；否则函数 值为0。首先，回忆一下串匹配(查找)的定义:INDEX(S,T,pos)55 下面讨论以定长顺序结构表示串时的几种算法。一、简单算法一、简单算法二、首尾匹配算法首尾匹配算法三、三、KMP(D.E.Knuth,V.R.Pratt,J.H.Morris)算法算法 (克努特克努特-莫里斯莫里斯-普拉特算法普拉特算法)56int Index(String S,String T,int pos)/返回子串返回子串T在主串在主串S中第中第pos个字符

25、之后的位置。若不存在，个字符之后的位置。若不存在，则函数值为则函数值为0。其中，。其中，T非空，非空，1posStrLength(S)。i=pos;j=1;while(i=S0&j T0)return i-T0;else return 0;/Index一、简单算法一、简单算法时间复杂度O(n*m)“00000001”,“001”57 先比较模式串的第一个字符，再比较模式串的最后一个字符，最后比较模式串中从第二个到第 n-1个字符。二、首尾匹配算法二、首尾匹配算法58 int Index_FL(String S,String T,int pos)slength=S0;tlength=T0;i=p

26、os;patStartChar=T1;patEndChar=Ttlength;while(i=slength tlength+1)if(Si!=patStartChar)+i;/重新查找匹配起始点 else if(Si+tlength-1!=patEndChar)+i;/模式串的“尾字符”不匹配 else return 0;/检查中间字符的匹配情况检查中间字符的匹配情况59 k=1;j=2;while(j tLength&Si+k=Tj)+k;+j;if(j=tLength)return i;else +i;60KMP算法的时间复杂度可以达到O(m+n)当 Si Tj 时，已经得到的结果：Si

27、-j+1.i-1=T1.j-1 若已知 T1.k-1=Tj-k+1.j-1 则有 Si-k+1.i-1=T1.k-1三、三、KMP(D.E.Knuth,V.R.Pratt,J.H.Morris)算法算法61定义：定义：模式串的next函数其它情况且时当 1 pp ppp jk1|Maxk1j 0j1-j1k-j1-k21next62 int Index_KMP(SString S,SString T,int pos)/1posStrLength(S)i=pos;j=1;while(i=S0&j T0)return i-T0;/匹配成功 else return 0;/Index_KMP63这实际

28、上也是一个匹配的过程，不同在于：主串和模式串是同一个串已知：next1=0；假设：nextj=k;又 Tj=Tk则：nextj+1=k+1若：Tj Tk则需往前回溯，检查 Tj=T?64 void get_next(SString&T,int&next)/求模式串T的next函数值并存入数组next i=1;next1=0;j=0;while(i T0)if(j=0|Ti=Tj)+i;+j;nexti=j;else j=nextj;/get_next65还有一种特殊情况需要考虑：例如：nextvalj=00004nextj=0123466 void get_nextval(SString&T,int&nextval)i=1;nextval1=0;j=0;while(i T0)if(j=0|Ti=Tj)+i;+j;if(Ti!=Tj)nexti=j;else nextvali=nextvalj;else j=nextvalj;/get_nextval67 。本章小节本章小节68 。6970