串的定义及基本运算课件

串的定义及基本运算串的定义及基本运算56、极端的法规，就是极端的不公。西塞罗57、法律一旦成为人们的需要，人们就不再配享受自由了。毕达哥拉斯58、法律规定的惩罚不是为了私人的利益，而是为了公共的利益；一部分靠有害的强制，一部分靠榜样的效力。格老秀斯59、假如没有法律他们会更快乐的话，那么法律作为一件无用之物自己就会消灭。洛克60、人民的幸福是至高无个的法。西塞罗第四章 串第四章 串第四章 串第四章 串第四章 串三、串的基本运算 1.求串长StrLength(s)StrLength(s)：操作条件：串s存在；操作结果：求出串s的长度。2.串赋值StrAssign(s1,s2)StrAssign(s1,s2)操作条件：s1是一个串变量，s2或者是一个串常量，或者是一个串变量（通常s2 是一个串常量时称为串赋值，是一个串变量称为串拷贝）。操作结果：将s2的串值赋值给s1，s1原来的值被覆盖掉。6第四章 串3.连接操作：StrConcat(s1,s2,s)StrConcat(s1,s2,s)或或StrConcat StrConcat(s1,s2)(s1,s2)操作条件：串s1,s2存在。操作结果：两个串的联接就是将一个串的串值紧接着放在另一个串的后面，连接成一个串。前者是产生新串s，s1和s2不改变;后者是在s1的后面联接s2的串值，s1改变，s2不改变。4.求子串SubStr(s,i,len)SubStr(s,i,len)：操作条件：串s存在，1iStrLength(s)，0lenStrLength(s)-i+1。操作结果：返回从串s的第i个字符开始的长度为 len 的子串。len=0得到的是空串。7第四章 串5.串比较 StrCmp(s1,s2)StrCmp(s1,s2)操作条件：串s1,s2存在。操作结果：若s1=s2，操作返回值为0；若s1s2,返回值s2,返回值0。6.子串定位 StrIndex(s,t)StrIndex(s,t)：找子串t在主串s中首次出现的位置操作条件：串s,t存在。操作结果：若ts，则操作返回t在s中首次出现的位置，否则返回值为-1。8第四章 串8.串删除 StrDelete(s,i,len)StrDelete(s,i,len)操作条件：串s存在，1iStrLength(s)1iStrLength(s)，0lenStrLength(s)-i+1 0lenStrLength(s)-i+1。操作结果：删除串s 中从第i个字符开始的长度为 len的子串，s的串值改变。7.插入 StrInsert(s,i,t)StrInsert(s,i,t)操作条件：串s,t存在，1iStrLength(s)+1。操作结果：将串t插入到串s 的第i个字符位置上。9.串替换StrRep(s,t,r)StrRep(s,t,r)操作条件：串s,t,r存在，t不为空。操作结果：用串r 替换串s中出现的所有与串t相等的不重叠的子串，s的串值改变。9第四章 串 4.2 串的存储结构串的存储结构 4.2.1 4.2.1 串的定长顺序存储串的定长顺序存储类似于顺序表，用一组地址连续的存储单元存储串值中的字符序列，所谓定长是指按预定义的大小，为每一个串变量分配一个固定长度的存储区，如：1.1.类似顺序表，用一个指针来指向最后一个字符，这样表示的串描述如下：typedef struct char dataMAXSIZE;int curlen;SeqString;10第四章 串nedutSMAXSIZE-1543210s.datas.curlen2.在串尾存储一个不会在串中出现的特殊字符作为串的终结符，以此表示串的结尾。比如C语言中处理定长串的方法就是这样的，它是用0来表示串的结束。3.设定长串存储空间：char sMAXSIZE+1;用s0存放串的实际长度，串值存放在s1sMAXSIZE，字符的序号和存储位置一致，应用更为方便。11第四章 串4.2.24.2.2 定长顺序串的基本运算 1.串联接：把两个串s1和s2首尾连接成一个新串s。int StrConcat1(s1,s2,s)int i=0,j,len1,len2;len1=StrLength(s1);len2=StrLength(s2)if (len1+len2MAXSIZE-1)return 0;j=0;while(s1j!=0)si=s1j;i+;j+;j=0;while(s2j!=0)si=s2j;i+;j+;si=0;return 1;12第四章 串2.求子串int StrSub(char*t,char*s,int i,int len)int StrSub(char*t,char*s,int i,int len)int slen;slen=StrLength(s);if(islen|lenslen-i+1)printf(参数不对);return 0;for(j=0;jlen;j+)tj=si+j-1;tj=0;return 1;nedutSMAXSIZE-1543210s.datas.curlen ned I=4,len=3t.data例2.13第四章 串3.串比较:若s1=s2，操作返回值为0；若s1s2,返回值s2,返回值0。int StrComp(char*s1,char*s2)int i=0;while(s1i=s2i&s1i!=0&s2i!=0)i+;return(s1i-s2i);14第四章 串4.2.3 串的块链存储表示 顺序串上的插入和删除操作不方便，需要移动大量的字符。因此，我们可用单链表方式来存储串值，串的这种链式存储结构简称为链串。typedef struct node char data;struct node*next;lstring;一个链串由头指针唯一确定。这种结构便于进行插入和删除运算，但存储空间利用率太低。sdystring115第四章 串 为了提高存储密度，可使每个结点存放多个字符每个结点存放多个字符。通常将结点数据域存放的字符个数定义为结点的大小，显然，当结点大小大于 1时，串的长度不一定正好是结点的整数倍，因此要用特殊字符#(#不属于串的字符集)来填充最后一个结点，以表示串的终结。headA B C DT A N KE N D#结点大小为4的链表存储密度的概念存储密度的概念：16第四章 串 4.3 模式匹配算法的实现模式匹配算法的实现4.3.1 求子串位置的定位函数StrIndex(s,t)串的模式匹配模式匹配（即子串定位子串定位）是一种重要的串运算。设 s 和 t 是给定的两个串，在串 s 中查找串 t 的位置,在此过程中称 s s 为主串为主串,t t 为子串为子串。在主串 s 中查找子串 t 的过程称为模模式式匹匹配配，如果查找成功，则称匹匹配配成成功功，函数返回 t 在 s 中的首次出现的存储位置(或序号)，否则匹配失败，返回-1。t 也称为模式。17第四章 串 算法思想如下：首先将主串中的第一个字符s1与子串中的第一个字符t1进行比较，若相同，继续比较两个串中的第二个字符，即s2和t2进行比较，若这样的比较对于子串的每个字符都成立，则该趟比较的开始位置就是子串在主串中的位置（查找成功）若上面的比较在某个位置上出现对应位置字符不相同的情况，即此趟比较不成功，将主串的指针指向本趟比较开始位置的下一个字符（i=i-j+2），同时将子串的位置返回到第一个位置。进行下次比较，直到匹配成功或者主串已经结束。简单的模式匹配算法BF-穷举的模式穷举的模式18第四章 串 算法举例算法举例第第2趟趟 S a b b a b a (i=3-j+2=(i=3-j+2=2 2开始开始)T a b a (j=(j=1 1开始开始)第第4趟趟 S a b b a b a T a b a (查找成功）查找成功）第第1 1趟趟 S a b b a b a (i=(i=3 3,j=,j=3 3)T a b a 第第3趟趟 S a b b a b a (i=2-j+2=(i=2-j+2=3 3)开始开始 T a b a (j=(j=1 1开始开始)主主 串串 S a b b a b a (初始位置初始位置i=i=1 1,j=,j=1 1)子子 串串 T a b a 19第四章 串算法程序实现如下 int StrIndex_BF(char*s,char*t)int i=1,j=1;while(i=s0&jt0)return(i-t0);/*成功，返回存储位置*/else return(1);20第四章 串算法分析-时间复杂度时间复杂度（i)在最好情况下，每趟不成功的匹配都发生在第一对字符比较时例如：s=aaaaaaaaaabc t=bc 即最好情况下的时间复杂度是O(n+m)。(ii)在最坏的情况下，如果不成功的匹配都发生在子串（t）的最后一个字符的位置，即每趟比较都要进行 m 次，这样比较的趟数要 n 趟，因此，此情况下的时间复杂度为 O(n*m)。例如：s=aaaaaaaaaab t=aaaab21第四章 串算法分析优点：算法简单 实现容易缺点：算法复杂度高；重复比较次数比较，只要不匹配的情况，要从新开始；回溯次数比较多。22第四章 串算法思路：如上所述，希望某趟在si和tj匹配失败后，主串指针i不回溯，模式串t向右“滑动”至某个适当位置上，使得tk对准 s i 继续向右进行。显然，现在问题的关键是串t“滑动滑动”到哪个位置上到哪个位置上？不妨设位置为k，即si和tj匹配失败后，指针i不动，模式t向右“滑动”，使tk和si对准继续向右进行比较，关键的问题是确定滑动的位置。KMP算法算法引入：分析BF算法的执行过程,造成BF算法速度慢的原因是回溯，即在某趟的匹配过程失败后，对于s串要回到本趟开始字符的下一个字符，t串要回到第一个字符。而这些回溯并不是必要的。23第四章 串KMP算法中NEXT函数的介绍next函数的性质：nextj是一个整数，且0nextjj 为了使t的右移不丢失任何匹配成功的可能，当存在多个 满足上面(4)式的 k 值时，应取最大的，这样向右“滑动”的距离最短，“滑动”的字符为j-nextj个。如果在tj前不存在满足(4)式的子串，此时若t1tj，则 k=1;若t1=tj，则k=0;这时“滑动”的最远，为j-1个字符，即用t1 和sj+1继续比较。24第四章 串NEXT函数的表示Next函数的定义：设有模式串：t=“abcaababc”，则它的next函数值为：j123456789模式串abcaababcnextj0111223230 当j=1max k|1kj 且t1 t2 tk-1 =tj-k+1 tj-k+2 tj-1 1 其它情况nextj=25第四章 串KMP算法程序实现如下：int StrIndex_KMP(char*s,char*t,int pos)/*从串 s 的第 pos 个字符开始找首次与串 t 相等的子串*/int i=pos,j=1,slen,tlen;while(i=s0&jt0)return i-t0;/*匹配成功，返回位置*/else return 1;/*匹配不成功，返回信息*/26第四章 串Next函数的求法：据前述，可把求nextnext函数值的问题看成是一个模式匹配问题，整个模式串既是主串又是模式，而当前在匹配的过程中，已有上面的(5)式成立，则当t tk k t tj j 时应将模式向右滑动，使得第nextk个字符和“主串”中的第j个字符相比较。若nextk=knextk=k，且t t k kt tj j，则说明在主串中第j+1个字符之前存在一个最大长度为k的子串，使得t t1 1 t t2 2 t t k k=t=tj-k+1j-k+1 t tj-k+2 j-k+2 t tj j (6)因此：nextj+1=nextk+1nextj+1=nextk+1 (7)27第四章 串 同理若t t k k t tj j，则将模式继续向右滑动至使第nextknextk个字符和tj 对齐，依此类推，直至tj 和模式中的某个字符匹配成功或者不存在任何 k(1 k(1 kk j)kk j)满足(4.10)，此时若t t1 1ttj+1j+1，则有：nextj+1=1nextj+1=1 (8)否则若 t t1 1=t=tj+1j+1 ，则有：nextj+1=0nextj+1=0 (9)28第四章 串求Next函数的程序实现：void GetNext(char*t,int next)int i=1,j=0;next1=0;while(i0&ti!=tj)j=nextj;i+;j+;if(ti=tj)nexti=nextj;else nexti=j;29第四章 串1利用C的库函数strlen,strcpy和strcat写一个算法void StrInsert(char*S,char*T,int t)，将串 T 插入到 S 的第 i 个位置上。若 i 大于 S 的长度，则插入不执行。2利用C的库函数strlen,strcpy（或strncpy）写一个算法void StrDelete(char*S,int t,int m)，删除串 S 中从位置 i 开始的连续的m个字符。若istrlen(S)，则 没 有 字 符 被 删 除；若i+mstrlen(S)，则将 S 中从位置i开始直至末尾的字符均被删去。4.4 小结与习题小结与习题30谢谢你的阅读v知识就是财富v丰富你的人生71、既然我已经踏上这条道路，那么，任何东西都不应妨碍我沿着这条路走下去。康德72、家庭成为快乐的种子在外也不致成为障碍物但在旅行之际却是夜间的伴侣。西塞罗73、坚持意志伟大的事业需要始终不渝的精神。伏尔泰74、路漫漫其修道远，吾将上下而求索。屈原75、内外相应，言行相称。韩非