文件名称：严版数据结构习题答案
文件大小：1.62MB
文件格式：RAR
更新时间：2013-03-04 13:40:34
严版 答案
严版数据结构一至九章课后习题答案五、算法设计题（每题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;i<=Strlen(S)-Strlen(T)+1;i++) //注意i的取值范围
if(!StrCompare(SubString(S,i,Strlen(T)),T)) //找到了与T匹配的子串
{ //分别把T的前面和后面部分保存为head和tail
StrAssign(head,SubString(S,1,i-1));
StrAssign(tail,SubString(S,i+Strlen(T),Strlen(S)-i-Strlen(T)+1));
StrAssign(S,Concat(head,V));
StrAssign(S,Concat(S,tail)); //把head,V,tail连接为新串
i+=Strlen(V); //当前指针跳到插入串以后
n++;
n++;
}//if
return n;
}//Replace
分析:i+=Strlen(V);这一句是必需的,也是容易忽略的.如省掉这一句,则在某些情况下, 会引起不希望的后果,虽然在大多数情况下没有影响.请思考:设S='place', T='ace', V='face',则省掉i+=Strlen(V);运行时会出现什么结果?
2. 【严题集5.18⑤】试设计一个算法，将数组An 中的元素A[0]至A[n-1]循环右移k位，并要求只用一个元素大小的附加存储，元素移动或交换次数为O(n)
解：
分析:要把A的元素循环右移k位,则A[0]移至A[k],A[k]移至A[2k]......直到最终回到A[ 0].然而这并没有全部解决问题,因为有可能有的元素在此过程中始终没有被访问过,而是被跳了过去.分析可知,当n和k的最大公约数为p时,只要分别以A[0],A[1],...A[p-1]为起点执行上述算法,就可以保证每一个元素都被且仅被右移一次,从而满足题目要求.也就是说,A的所有元素分别处在p个"循环链"上面.举例如下:
n=15,k=6,则p=3.
第一条链:A[0]->A[6],A[6]->A[12],A[12]->A[3],A[3]->A[9],A[9]->A[0]. /已“顺便”移动了A[6]、A[12]…
第二条链:A[1]->A[7],A[7]->A[13],A[13]->A[4],A[4]->A[10],A[10]->A[1].
第三条链:A[2]->A[8],A[8]->A[14],A[14]->A[5],A[5]->A[11],A[11]->A[2].
恰好使所有元素都右移一次.
虽然未经数学证明,但作者相信上述规律应该是正确的. 程序如下：
void RSh(int A[n],int k)//把数组A的元素循环右移k位,只用一个辅助存储空间
{
for(i=1;i<=k;i++)
if(n%i==0&&k%i==0) p=i;//求n和k的最大公约数p
for(i=0;i
【文件预览】：
数据结构习题答案
----数据结构作业答案第6章二叉树作业答案.doc(420KB)
----数据结构作业答案第1章作业答案.doc(185KB)
----数据结构作业答案第2章作业答案.doc(48KB)
----数据结构作业答案第7章作业答案.doc(1.19MB)
----数据结构作业答案第8章作业答案.doc(488KB)
----数据结构作业答案第3章作业答案.doc(378KB)
----数据结构作业答案第4~5章作业答案.doc(67KB)
----数据结构作业答案第9章排序作业题答案.doc(40KB)