数据结构第五章串和数组练习.doc

基本概念题：1 设S1 =“Data Structure Course”，S2 =“Structure”，S3 =“Base”，求：（1） Length(S1)； 21（2） （2）Compare(S2, S3)； 1（3） Insert(S1, 5, S3)； DataBase Structure Course（4） Delete(S1, 5, 9)； Datae Course（5） SubString(S1, 5, 9, T)； Structur （6）Search(S1, 0, S2)； （7）Replace(S1, 0, S2, S3) Data Base Course算法设计题：2 设串采用静态数组存储结构，编写函数实现两个串的比较Compare(S, T)。要求比较结果有等于和不等于两种情况。void compare(String s1,String s2)int i=0;elsewhile(i=s1.length & s1.elemi!=s2.elemi)i+;if(i+1=s1.length)cout相等n;elsecout=s2.length ? s1.length : s2.length;for(int i=0;is2.elemi)flag=1;break; elseif(s1.elemis2.elemi) flag=-1;break;else continue;if(flag=1)couts2n;if(flag=-1)couts1s2n;if(i=s1.length)cout0)/*第一种情况，字符串V比T长的情况下*/ for(l=s+(m-n)*(count+1)-1;l=k;l-)Sl=Sl-m+n;for(l=k-n,j=0;jm;l+,j+)Sl=Vj;count+; else if(m-n0)/*第二种情况，字符串V比T短的情况下*/ for(l=k-n,j=0;jm;l+,j+)Sl=Vj;for(;l=k-n;l-,j-)Sl=Vj-1; signal=1; /if/for Ss+(m-n)*count=0;if(signal)return 1;/*返回值*/elsereturn 0;/Replace6 设字符串采用静态数组的顺序存储结构，（1） 编写算法删除字符串s中值等于ch的一个字符，并分析该算法的时间复杂度；void delchar(char *s, char ch) while(*s) if(*s = ch) /找到第一个ch break; s+; while(*s) /开始删除 *s = *(s+1); s+; （2）编写算法删除字符串s中值等于ch的所有字符。void delchar(char *a,char ch)int i,j;for(i=0,j=0;istrlen(a);i+)if(ai!=ch)aj+=ai;aj=0;7 设字符串采用单字符的链式存储结构，编写删除串s从位置i开始长度为k的子串的算法。8 设一个系统中二维数组采用以行序为主的存储方式存储，已知二维数组anm中每个数据元素占k个存储单元，且第一个数据元素的存储地址是Loc(a00)，求数据元素aij(0in-1, 0jm-1)的存储地址。Loc(aij)=Loc(a00)+(i*m+j)*k9 设一个系统中二维数组采用以行序为主的存储方式存储，已知二维数组a108中每个数据元素占4个存储单元，且第一个数据元素的存储地址是1000，求数据元素a45的存储地址。Loc(a45)=1000+(4*8+5