7,8 串与数组.pptx

串和数组 ;本章的要求;串的基本概念;串的基本概念;串的基本概念;串的基本运算;串的基本运算;串的基本运算;串的基本运算——组合运算;串的基本运算——组合运算;串的顺序存储表示;串的顺序存储表示;顺序串的基本操作: 插入;StrInsert(SeqString *s,int pos, Seqstring t) { int i; if ( pos 0 || pos s-length) //插入位置不合法 return(0); if (s-length + t. length = maxsize) //插入后串长=maxsize { for (i = s-length+t.length-1; i = pos+t.length; i--) s-ch[i] = s-ch[i-t.length]; //元素后移 for (i=0; it.length;i++) s-ch[i+pos] = t.ch[i]; //插入t s-length = s-length +t.length; } else if (pos + t.length = maxsize) //插入后串长maxsize，但串t的字符序列可以全部插入 { for ( i = maxsize -1; i = t.length+pos;i--) s-ch[i] = s-ch[i-t.length]; //元素后移 for (i=0; it.length;i++) s-ch[i+pos] = t.ch[i]; //插入t s-length = maxsize; } else //串t的部分字符序列要舍弃 { for (i=0;i=maxsize-pos-1;i++) s-ch[i+pos] = t.ch[i]; s-length = maxsize; } return(1);};顺序串的删除;串的链式存储表示;串的链式存储表示;串的模式匹配算法;顺序串上的模式匹配;S:;算法5.1 顺序串的模式匹配。 int Index(seqstring*S, seqstring*T,int pos) //顺序串的朴素模式匹配，串的位序从1开始 { i=pos; j=1; // 目标串从第pos个字符开始与模式串的第一个字符开始进行比较 while(i=S-lengthj=T-length) if(S-ch[i-1]==T-ch[j-1]) //串从向量的0元素开始存放 { i++; j++; } //继续比较后面的字符 else//本趟不匹配，设置下一趟匹配的起始位序 { i=i-(j-1)+1;//(j-1)指针移动个数,+1表示跳过本趟首次比较的字符 j=1; } if(jT-length) return(i-T-length); //匹配成功 else return(0); //匹配不成功 };顺序串上的模式匹配;链串上的模式匹配;算法5.2 链串的模式匹配。 LinkString*Index(LinkString*S,LinkString*T,LinkString*pos) //从pos所指示的位置开始查找模式串T在目标串S中首次出现的位置 { LinkString*shift,*sp,*tp; shift=pos; sp=shift; tp=T; while(sp!=NULLtp!=NULL){ if(sp-data==tp-data){ //继续比较后续结点中的字符 sp=sp-next; tp=tp-next; } else{ //本趟匹配不成功，设置下一趟匹配的起始位置 shift=shift-next; sp=shift; tp=T; } } if(tp==NULL) return shift; //