串数组和广义表A.ppt

4.1串（String） 练习1：串是由 字符组成的序列，一般记 。 练习： 设 s =“I AM A STUDENT”, t =“GOOD”, q=“WORKER”。求： 算法种类： （4）求解next[j] 算法流程图:（类似于串匹配算法，视主串与模式串为同一个串Ｔ； KMP算法的时间复杂度 注意：由于BF算法在一般情况下的时间复杂度也近似于O(n+m)，所以至今仍被采用。 串插入函数实现 template class T1 void StringT1::StrInsert(int pos, StringT1 T) 基本算法思想: 1）判定pos是否合法，1=pos=length+1合法;不合法，给出错误信息。 2）只要串T不空，就需要重新分配s空间，以便插入T；设置新串串长L=length+T.length; 3）为新串s1重新申请存储空间，大小为L+1； 4）将串s的第1位到第pos-1位的串值复制到s1中； 5）将T插入s1 6）将串s的第pos位后面的串值复制到s1中； 7）s1[L]=‘\0’ 8）设s串长为新值length=T.length+length 9）释放s的存储空间，并让其指向s1串。 template class T1 void StringT1::StrInsert(int pos, StringT1 T) {//在串s的第pos位置（包括尾部）插入串 int i,j; if (pos1||poslength+1) throw pos不合法!; if (T.length) {//只要串T不空，就需要重新分配s空间，以便插入T char *s1;int L=length+T.length; s1=new char[L+1]; if (s1==NULL) throw 空间分配失败！; //复制第1位到第pos-1位的串值 for(i=0;ipos-1;i++) s1[i]=s[i]; //将T插入s for(j=0;j=T.length-1;j++,i++) s1[i]=T.s[j]; //插入s而腾出pos之后串值 for ( j=pos-1;jlength; j++,i++) s1[i]=s[j]; s1[L]=\0; length+=T.length; delete []s; s=s1;//s新值 } } 串删除函数实现 template class T void StringT::StrDelete(int pos,int len) 基本算法思想: 1）先判pos和len是否合法； 不合法条件：pos1 || poslength||len=0 || len length-pos+1 2）设置新串串长L=length－len; 3）为新串s1重新申请存储空间，大小为L+1； 4）将串s的第1位到第pos-1位的串值复制到s1中； 5）将串s的第pos+len位开始，到串尾复制到s1串中； 6）设s串长为新值length=length-len; 7）释放s的存储空间，并让其指向s1串。 template class T void StringT::StrDelete(int pos,int len) { int i,j; if (pos1 || poslength||len=0 || len length-pos+1) throw “pos或length不合法！; int L=length-len; char *s1=new char[L+1]; for(i=0;i=pos-2;i++) s1[i]=s[i]; for(j=pos+len;j=length+1;j++,i++) //从第pos+len位开始，到串尾复制到s1串中 s1[i]=s[j-1]; length-=len; delete []s; s=s1;//s新串 } 求子串实现 template class T1 StringT1 StringT1::SubString(int pos,int len) 基本算法思想: 1）判pos和len是否合法： pos1 || poslength||len=0 || len length-pos+1 2）生成新的串