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

基本概念题：

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; else while(i<=s1.length && s1.elem[i]!=s2.elem[i]){ i++; }

if(i+1==s1.length) cout<<\相等\\n\ else cout<<\不相等\\n\ }

3 设串采用静态数组存储结构，编写函数实现两个串的比较Compare(S, T)。要求比较结果有大于、等于和小于三种情况。

void compare2(String s1,String s2){ int max,flag;

max=s1.length>=s2.length ? s1.length : s2.length; for(int i=0;is2.elem[i]){ flag=1;break;} else if(s1.elem[i]

if(flag==1) cout<<\ if(flag==-1) cout<<\

if(i==s1.length) cout<<\ }

4 设串采用动态数组存储结构，编写函数实现两个串的比较Compare(S, T)。要求比较结果有大于、等于和小于三种情况。对比本题和习题4-13的算法，说明串的静态数组存储结构和串的动态数组存储结构是否对编写串的比较算法有影响。

静态数组存储结构，要定义字符串长度，且字符长度必须达到那么长。 动态数组存储结构，可按实际需要来确定字符长度。

5 设串采用静态数组存储结构，编写函数实现串的替换Replace(S, start, T, V)，即要求在主串S中，从位置start开始查找是否存在子串T，若主串S中存在子串T，则用子串V替换子串T，且函数返回1；若主串S中不存在子串T，则函数返回0。

Replace(char *S,int start,char *T,char *V){ int i,j,k,l,n,m,s,count=0,signal=0; n=strlen(T);/*求字符串长度*/ m=strlen(V); s=strlen(S);

for(i=start-1;S[i]!='\\0';i++)/*开始查找*/ { k=i; j=0; while(S[k]==T[j])/*与子串T对比*/ { k++; j++; }//while if(T[j]=='\\0')/*判断是否T存在*/ { if(m-n>0)/*第一种情况，字符串V比T长的情况下*/ { for(l=s+(m-n)*(count+1)-1;l>=k;l--) S[l]=S[l-m+n]; for(l=k-n,j=0;j

for(;l=k-n;l--,j--) S[l]=V[j-1]; } signal=1; } //if }//for

S[s+(m-n)*count]='\\0'; if(signal) return 1;/*返回值*/ else return 0; }//Replace

6 设字符串采用静态数组的顺序存储结构，

（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;i

}

7 设字符串采用单字符的链式存储结构，编写删除串s从位置i开始长度为k的子串的算法。

8 设一个系统中二维数组采用以行序为主的存储方式存储，已知二维数组a[n][m]中每个数据元素占k个存储单元，且第一个数据元素的存储地址是Loc(a[0][0])，求数据元素a[i][j](0≤i≤n-1, 0≤j≤m-1)的存储地址。

Loc(a[i][j])=Loc(a[0][0])+(i*m+j)*k

9 设一个系统中二维数组采用以行序为主的存储方式存储，已知二维数组a[10][8]中每个数据元素占4个存储单元，且第一个数据元素的存储地址是1000，求数据元素a[4][5]的存储地址。

Loc(a[4][5])=1000+(4*8+5)*4=1148

10设矩阵A、矩阵B和矩阵C为采用压缩存储方式存储的n阶上三角矩阵，矩阵元素为整数类型，要求：

（1）编写实现矩阵加C = A + B的函数。