严蔚敏C语言版《数据结构》习题集答案

第一章 绪论 x,y,z)/按从大到小顺序输出三个数 %d,%d,%d,&x,&y,&z); if(,以下同 if(if(%d %d %d,x,y,z); /k,m,f)/求 f if(;i+; i=ix&i=0;i+1=i; i+1=x; K; /,)/比较字符表 ,并用返回值表示结果 ,值为 1,表示 AB;值为 示 i?1:; : /当两个字符表可以互相比较的部分完全相同时 ,哪个较长 ,哪个就较大 /,x)/链表上的元素查找 ,返回指针 p=l-p&p-x;p=p- p; /)/求链表的长度 k=0,p=L;p-p=p-k+); k; / hc=ha;p=p-p=p-p-/见书后答案 . L,i,b)/在无头结点链表 b p=L;q=(; b; if(i=1) p;L=q; /插入在链表头部 ) p=p-q-p-p-q; /插入在第 /L,i)/在无头结点链表 if(i=1) L=L- p=L; ) p=p-p-p- /L, p=L; p-(p- /如果还有比 q=p-q-q; /L)/删除元素递增排列的链表 p=L-q=p-,p- if(p-q- p=p-q=p-,p, q-p- q); q=q- p-q;p=q;q=p-/A)/顺序表的就地逆置 i=1,j=j; /L)/链表的就地逆置 ;为简化算法 ,假设表长大于 2 p=L-q=p-s=q-p-s- q-p;p=q; q=s;s=s- q-p;s-q;L-s; /析 :本算法的思想是 ,逐个地把 A,B,C)/把链表 合并为 C,的元素间隔排列 ,且使用原存储空间 p=A-q=B-=A; p&q) s=p-p-q; /将 if(s) t=q-q-s; /如 将 p=s;q=t; /(A,B,C)/把元素递增排列的链表 合并为 C,且 使用原空间 -, if(! pc=pa;q=pa=q; /将 pc=pb;q=pb=q; /将 C=A;A-/析 :本算法的思想是 ,按从小到大的顺序依次把 的元素插入新表的头部 最 后处理 的剩余元素 . ,C)/求元素递增排列的线性表 的元素的交集并存入 i=1;j=1;k=0; i&j) ij) j+; i=j) +k=i; /当发现了一个在 A, i+;j+; /就添加到 /(,C)/在链表结构上重做上题 p=A-q=B-; C=p&q) if(p-p=p-if(p-q-q=q- s=(; s-p-s;pc=s; p=p-q=q- /(A,)/求元素递增排列的线性表 的元素的交集并存回 i=1;j=1;k=0; i&j) ij) j+; i!=k) +k=i; /当发现了一个在 A,i+;j+; /且 就添加到 i+;j+; /k) k+=0; /A,)/在链表结构上重做上题 p=A-q=B-; p&q) if(p-p=p-if(p-q-q=q-if(p- pc=p-p=p-q=q- /(A,) i=0;j=0;k=0;m=0; /中元素原来的位置 ,k) k+; j; /找到了相同元素 j=j+; k=k+; /j,q=C-r=p&q&r) if(p-p=p-if(p-q-q=q- u=p-(r-(r-u) s=r-s-u) t=s;s=s-t); /确定第一个大于 s / r-s; /删除 r和 /if p-u) p=p-q-u) q=q-/s)/删除单循环链表中结点 p=s; p-s) p=p-s; K; /L)/完成双向循环链表结点的 p=L;!p-p=p-p-p; K; /L,A,B,C)/把单链表 s=L-A=(;p=A; B=(;q=B; C=(;r=C; /建立头结点 s) if(s- p-s;p=s; if(s- q-s;q=s; r-s;r=s; /p-;q-;r-; /完成循环链表 /)/从左向右输出异或链表的元素值 p=p) %d,p- q= p;p=q; /任何一个结点的 /L,x,i)/在异或链表 x p=r=(; r-x; if(i=1) /当插入点在最左边的情况 r); p; r; K; j=1;q=(+ p;p=q; /,q) q),r); p),r); p,q); /修改指针 K; /L,i)/删除异或链表 p=if(i=1) /删除最左结点的情况 q=p); q;p); K; j=1;q=+ p;p=q; /(!q) (q) / q); p;q); K; r=p); /此时 p,q),r); q),p); /修改指针 q); K; /L)/按 1,3,5,.的顺序重排双向循环链表 p=p-L&p-L) p-p-p=p- /此时 if(p-L) p-p-l-p=p-(p-L) p-p-p=p- p-; /按题目要求调整了 此时 p=L;p-L;p=p-p-p; L-p; /调整 同 /析 :如同时进行调整的话 ,必须使用堆栈保存偶数结点的指针 ,否则将会破坏链表结构 ,造成结点丢失 . L,x)/带 p=x&p!=L) p=p-if(p=L) ;q=p-q-p!=L) q=q-(q!=p- p-p-p-p-q-p;p-q-q-p;p-q; /调整位置 p; /, q; ;q=; q- q-q+; /1,2, p,*q,*r; 3); /建立空多项式 P3 p=q=r=p-q- if(p- r-p-r-p-p+;r+; if(p- r-q-r-q-q+;r+; p-=0) /只有同次项相减不为零时才需要存入 r-p-r-p-r+; /if p+;q+; /(p- r-p-r-p-p+;r+; q- r-q-r-q-q+;r+; /L)/对有头结点循环链表结构存储的稀疏多项式 p=L-p- L-p-p=p- p!=L) p-p- /L,&A,&B)/把循环链表存储的稀疏多项式 和只含偶次项的 B p=L-A=(; B=(; ; p!=L) if(p-2*(p-) p;pa=p; p;pb=p; p=p-/; /三章 栈与队列 ; ; (m)/初始化一个大小为 =(; =+m; =; =; K; /i,x)/i=0表示低端栈 ,i=1表示高端栈 if() (i=0) *+=x; if(i=1) *-=x; K; /i,x)/i=0表示低端栈 ,i=1表示高端栈 if(i=0) if(=) x=*; if(i=1) if(=) x=*+; K; /,H表示硬席 ,S表示软席 p=q=s); p) p=H) s,*p); /把 H存入栈中 (q+)=*p; /把 S调到前部 p+; s) s,c); *(q+)=c; /把 H接在后部 /&前和 &后部分是否为逆串 ,是则返回 1,否则返回 0 s); e=)!=&) if(e=) ;/不允许在 &之前出现 s,e); (e=)!=) s) ; s,c); if(e!=c) ; s) ; ; / ; p=p;p+) p=() ; p=) if(gy= gy=,y); /修改左邻点的颜色 if(y1) if(gx= gx,x,; /修改上邻点的颜色 if(x=0) s=0; if(m0&n=0) s=n+g(*n); K; /g _n,s)/递归算法 if(n=e) p=(p+A/p)/2; p; /这一题的所有算法以及栈的变化过程请参见数据结构 ( ,作者不 再详细写出 . Q)/初始化循环链表表示的队列 Q Q=(; Q-; /Q,x)/把元素 x 插入循环链表表示的队列 Q,Q 指向队尾元素 ,Q-Q- p=(; p-x; p-p; Q=p; /修改尾指针 Q,x)/从循环链表表示的队列 x =Q-x=p-Q-p-p); K; /Q,x)/带 1) /表示 空 ,1表示 满 x; )%; /队列满 /Q,x)/带 0) )%x= ; /队列空 K; /析 :当循环队列容量较小而队列中每个元素占的空间较多时 ,此种表示方法可以 节约较多的存储空间 ,较有价值 . Q,x)/带 )%x; ; K; /Q,x)/带 环队列出队算法 0) )% /,是则返回 1,否则返回 0 );); c=)!=) ,c);,c); /同时使用栈和队列两种结构 ) ,a);,b); if(a!=b) K; /k,n)/求 n+1项 ); /其 为 k i=0;i= x; )% /插入在队尾 x; /插入在队头 K; /Q,x)/输出受限的双端队列的出队操作 )%K; /,P表示硬座 ,H表示硬卧 ,S表示软卧 ,最终按 r=); r) r=P) E); D); /实际 上等于不入队列 ,直接输出 r=S) E); ,*r,0); /0 表示把 A); ,*r,1); /1 表示把 /) D); ); /四章 串 s,r)/求 r r,); /初始化 i=s);i; c,s,i,1); r,r,c); /把 /s,t,r)/求所有包含在串 r r,); i=1;t) r,r,c); /(S,);/将串 替换为 V,并返回置换次数 n=0,i=1;s=,&it0) ; if(is0) ti; if(it0) si; si-ti; /S,);/将串 替换为 V,并返回置换次数 n=0,i=1;) /找到了与 分三种情况处理 0=V0) l=1;l=i+T0;Sl+V0=Sl; l=1;) r+r0=c; /(s,t)/从串 并返回删除次数 n=0,i=1; k=i;p;p=p- r=(; r-ch=p-q-r;q=r; q-/s,t)/把串 串 p=s-q=t-p&q;p=p-q=q- p-ch=q-ch;p; q) p=(; p-ch=q-p;p; p-/s,t)/串的比较 ,ss=,q=t-p&q&p-q-ch;p=p-q=q- p&!q) ; p) (q- q) p-p-/s)/求串 元素个数 ) i=0,p=s-p;p=p-i+); i; / s,t)/连接串 并返回指针 p=; q=p,r=s-r;r=r- q-; q=q-q-ch=r-/(r=t-r;r=r- q-; q=q-q-ch=r-/p; / s,其值等于串 s从 p=;q=p; r=s;r=r- /找到 r i=1; q-; q=q-q-ch=r- /复制串 t q-p; /t,s,c)/用块链存储结构 ,把串 p=p&!(i=p,c) p=p-(!p) /没找到 q=p-r=(; /将包含字符 j=0;j=#; /原结点 j=i;j=p-chj; p-chj=#; /# p-r; r-q; /把串 p和 /; /p,c)/在某个块中查找字符 c,如找到则返回位置是第几个字符 ,如没找到则返回 0 i=0;i!=c;i+); if(i=; i+1; /)/判断以块链结构存储的串 L 是否为回文序列 ,是则返回 1,否则返回 0 ); p=i=0;k=1; /从 1开始 ) k=1;i); /将前半段的字符入串 if(k()/2) ,c); /将后半段的字符与栈中的元素相匹配 if(p-chi!=c) ; /失配 +i=,当为块中最后一个元素时 ,转到下一块 p=p-i=0; /; /成功匹配 /t)/将堆结构表示的串 if( ; i=1;i=i+l+l; l=0;/当插入位置大于串长时 ,看作添加在串尾 ; i=i=i+i; /后移为插入字符串让出位置 i=0;) ; /T)/链串上的 p=T-p-;q=T; p- if(q=T|p-q- p=p-q=q-p-q; q=q-/* ,返回值为匹配的子串首指针 p=q=T-p&q) if(q=T|p-q- p=p-q=q- q=q-/q) i=1;p; /发现匹配后 ,要往回找子串的头 /)/求 ,i=1; ;i;k; /作记录 /( dn, d :%dn, n); /析 :错位值 依次把串 2向右错位平移 1格 ,2格 ,3格 ,.1 相匹配 ,如果存在最长重复子串 ,则必然能在此过程中被发现 记录已发现的最长重复子串 第一次出现位置 ,第二次出现位置和长度 重复子串 是否允许有重叠部分 ,本算法假定允许 只需在第二个 句的循环条件中加上 k=T0) ,S);,T); ,T);,S); /为简化设计 ,令 中较长的那个为 A,较短的那个为 B ,i=1;) i;0; /右端的右边 i;i+B0; /左右两端之间 . /以上是根据 A 和 B 不同的相对位置确定 A 上需要匹配的区间