《计算机数据结构》由会员分享，可在线阅读，更多相关《计算机数据结构（3页珍藏版）》请在装配图网上搜索。
1、算法设计题(每题10分，共30分)1. 【严题集4.12】编写一个实现串的置换操作Replace(&S, T, V)的算法。解：int Replace(Stringtype &S,Stringtype T,Stringtype V);/将串 S 中所有子串 T 替换为V,并返回置换次数for(n=0,i=1;inext);printf(c”data)如果当前串长为0,则return(-1)否则开始递归：if串没有到末尾，则P=P-next;再调用invert(s);else printf(p-data);return严题集4.10答案：void String_Reverse(Stringtyp
2、e s,Stringtype &r)/求 s 的逆串 rStrAssign(r,); /初始化r为空串for(i=Strlen(s);i;i-)StrAssign(c,SubString(s,i,1);StrAssign(r,Concat(r,c); /把s的字符从后往前添加到r中/这是递推算法。/String_Reverse3.【严题集5.18】试设计一个算法，将数组An中的元素A0至An-1 循环右移k位，并要求只用一 个元素大小的附加存储，元素移动或交换次数为O(n)解：分析:要把A的元素循环右移k位，则A0移至Ak,Ak移至A2k.直到最终回到A 0,然而这并没有全 部解决问题，因为有
3、可能有的元素在此过程中始终没有被访问过，而是被跳了过去.分析可知，当n和k的最大 公约数为p时，只要分别以A0,A1,.Ap-1为起点执行上述算法，就可以保证每一个元素都被且仅被右移一 次，从而满足题目要求,也就是说,A的所有元素分别处在p个循环链上面,举例如下： n=15,k=6，则 p=3.第一条链:A0-A6,A6-A12,A12-A3,A3-A9,A9-A0. /已“顺便”移动了 A6、A12 第二条链:A1-A7,A7-A13,A13-A4,A4-A10,A10-A1.第三条链:A2-A 8,A8-A14,A14-A5,A5-A11,A11-A2.恰好使所有元素都右移一次.虽然未经数
4、学证明，但作者相信上述规律应该是正确的.程序如下：void RSh(int An,int k)/把数组A的元素循环右移k位，只用一个辅助存储空间for(i=1;i=k;i+)if(n%i=0&k%i=0) p=i;/求 n 和 k 的最大公约数 pfor(i=0;ip;i+)j=i;l=(i+k)%n;temp=Ai;while(l!=i)Aj=temp;temp=Al;Al=Aj;j=l;l=(j+k)%n;/循环右移一步Ai=temp;/for/RSh附加题：利用 C 的库函数 strlen, strcpy (或 strncpy)写一个算法 void StrDelete(char *S,int t,int m)，删 除串S中从位置i开始的连续的m个字符。若iNstrlen(S)，则没有字符被删除；若i+mNstrlen(S)，则将 S中从位置i开始直至末尾的字符均被删去。提示：strlen是求串长(length)函数：int strlen(char s); /求串的长度strcpy 是串复制(copy)函数：char *strcpy(char to,char from); / 该函数将串 from 复制到串 to中，并且返回一个指向串to的开始处的指针。
计算机数据结构
