会计学记为：s=‘a1,a2,……..,an’(n≥0)练1：串是由字符组成的序列(xùliè)，一般记为。ADTSting{Objects:D={ai|ai∈CharacterSet,i=1,2,…，n,n≥0}Relations:R1={<ai-1,ai>|ai-1,ai∈D,i=2,…，n}functions://有13种之多StrAssign(&T,chars)//串赋值，生成值为chars的串TStrCompare(S,T)//串比较，若S>T，返回(fǎnhuí)值大于0…StrLength(S)//求串长，即返回(fǎnhuí)S的元素个数Concat(&T,S1,S2)//串连接，用T返回(fǎnhuí)S1＋S2的新串SubString(&Sub,S,pos,len)//求S中pos起长度为len的子串……Index(S,T,pos)//返回(fǎnhuí)子串T在pos之后的位置Replace(&S,T,V)//用子串V替换子串T}ADTSting设s=’IAMASTUDENT’,t=’GOOD’,q=’WORKER’。求：4.2串的表示(biǎoshì)和实现定长顺序存储特点：用一组连续的存储单元来存放串，直接使用定长的字符数组来定义(dìngyì)，数组的上界预先给出，故称为静态存储分配。例：用顺序存储方式实现(shíxiàn)求子串函数SubString(&Sub,S,pos,len)思路：利用(lìyòng)malloc函数合理预设串长空间。特点：若在操作中串值改变，还可以利用(lìyòng)realloc函数按新串长度增加(堆砌)空间。StatusStrInsert(HString&S,intpos,HStringT){//在串S的第pos个字符之前（包括尾部）插入串Tif(pos<1||pos>S.length+1)returnERROR;//pos不合法则告警(gàojǐng)if(T.length){//只要串T不空，就需要重新分配S空间，以便插入Tif(!（S.ch=(char*)realloc(S.ch,(S.length+T.length)*sizeof(char))))exit(OVERFLOW);for(i=S.length-1;i>=pos-1;--i)//为插入T而腾出pos之后的位置S.ch[i+T.length]=S.ch[i];//从S的pos位置起全部字符均后移S.ch[pos-1…pos+T.length-2]=T.ch[0…T.length-1];//插入T，略/0S.length+=T.length;//刷新S串长度}returnOK;}//StrInsertStatusStrAssign(HString&T,char*chars){if(T.ch)free(T.ch);for(i=0,c=chars;c;++i,++c);//求串长度(chángdù)if(!i){T.ch=NULL;T.length=0;}else{if(!(T.ch=(char*)malloc(i*sizeof(char))))exit(OVERFLOW);T.ch[0..i-1]=chars[0..i-1];T.length=i;}ReturnOK;}//StrAssign讨论(tǎolùn)：法1存储密度为；法2存储密度为；#defineCHUNKSIZE80//可由用户定义(dìngyì)的块大小typedefstructChunk{//首先定义(dìngyì)结点类型charch[CHUNKSIZE];//结点中的数据域structChunk*next;//结点中的指针域}Chunk;再次强调：串与线性表的运算有所不同，是以“串的整体(zhěngtǐ)”作为操作对象，例如查找某子串，在主串某位置上插入一个子串等。①BF算法(suànfǎ)设计思想：将主串的第pos个字符和模式的第1个字符比较，若相等，继续逐个比较后续字符；若不等，从主串的下一字符（pos+1）起，重新与第一个字符比较。IntIndex(SStringS,SStringT,intpos){i=pos;j=1;while(i<=S[0]&&j<=T[0]){if(S[i]==T[j]){++i,++j}//继续(jìxù)比较后续字符else{i=i-j+2;j=1;}//指针回溯到下一首位，重新开始匹配}if(j>T[0])returni-T[0];//子串结束，说明匹配成功elsereturn0;}//Index例：S=‘ababcabcacbab’，T=‘a