查看: 4763|回复: 3

《数据结构(c语言版)习题集》算法设计解决方案

字体大小: 正常放大

66 主题	1 听众	648 积分

VisaSky.com 加拿大移民留学网

TA的每日心情

	开心 2012-6-9 03:29

签到天数: 1 天

[LV.1]初来乍到

电梯直达

1^#

发表于 2004-11-28 18:02 |只看该作者 |正序浏览

|招呼Ta 关注Ta

<

>说明: 
<

>1. 本文是对严蔚敏《数据结构(c语言版)习题集》一书中所有算法设计题目的解决方案
<

>2. 本解答中的所有算法均采用类c语言描述,设计原则为面向交流、面向阅读,作者不保证程序能够上机正常运行(这种保证实际上也没有任何意义);
<

>3. 本解答原则上只给出源代码以及必要的注释,对于一些难度较高或思路特殊的题目将给出简要的分析说明,对于作者无法解决的题目将给出必要的讨论.目前尚未解决的题目有: 5.20, 10.40;
<

>4. 请读者在自己已经解决了某个题目或进行了充分的思考之后,再参考本解答,以保证复习效果;
<

>5. 由于作者水平所限,本解答中一定存在不少这样或者那样的错误和不足,希望读者们在阅读中多动脑、勤思考,争取发现和纠正这些错误,写出更好的算法来.
<

>第一章 绪论 
<

>1.16 
<

>void print_descending(int x,int y,int z)//按从大到小顺序输出三个数
{
 scanf("%d,%d,%d",&x,&y,&z);
 if(x<y) x<->y; //<->为表示交换的双目运算符,以下同
 if(y<z) y<->z;
 if(x<y) x<->y; //冒泡排序
 printf("%d %d %d",x,y,z);
}//print_descending 
<

>1.17 
<

>Status fib(int k,int m,int &f)//求k阶斐波那契序列的第m项的值f
{
 int tempd;
 if(k<2||m<0) return ERROR;
 if(m<k-1) f=0;
 else if (m==k-1) f=1;
 else
 {
for(i=0;i<=k-2;i++) temp=0;
& ^( T8 T# O5 V5 i* c temp[k-1]=1; //初始化8 P% T9 P0 t% L4 a+ y
 for(i=k;i<=m;i++) //求出序列第k至第m个元素的值4 X0 c% q; D& b& ` |
 {1 B8 Z& I6 E: a) {
 sum=0;
' L/ g2 a4 e. g0 H1 W for(j=i-k;j<i;j++) sum+=temp[j];7 l- D6 d; O. M2 r9 W% M/ T2 E
 temp=sum;5 C% B% R' ]& j( }8 M
}
% Q3 |) R) K G! Y9 B: [# m f=temp[m];
2 m6 t5 ]) ?% @2 P; k, u& _ }( W; t$ v$ h9 l# @ Z' a \
 return OK;
* a+ W* l N# P: f5 q4 H# U}//fib
$ R) d/ }: Q( J2 x% c分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m). 
1 ]5 n0 g: s8 t/ o/ m5 B<>1.18 
/ F% W' }1 m0 r7 X$ f, B' ^<>typedef struct{
, Q* y r# H1 L; G% W. I! D! x char *sport;' x( I" O5 `/ ?8 F
 enum{male,female} gender;1 Y1 Z' I& [* N, f
 char schoolname; //校名为'A','B','C','D'或'E'
/ V+ N/ E9 q' J' J5 m k2 T char *result;7 c/ e7 l) O* o& O
 int score;
, j4 h$ ]% r/ b } resulttype; + S( f F8 i$ Q3 {( h
<>typedef struct{3 `$ @$ n( L# x& {# `1 h# u
 int malescore;
/ L& I& b* ^4 {7 e+ u int femalescore;+ `7 U* }' U" N6 S3 ?
 int totalscore;
. g. k3 ? V" f- e8 d } scoretype; 
4 A2 ?4 ~% s' Q! F! ]! I; V<>void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中
+ A, p$ ]0 K$ V# M{
/ J. t* I4 U7 D: i! c scoretype score;
) G, n1 {* a$ a3 v$ N i=0;
: \! y' F6 A' W; \- f0 O while(result.sport!=NULL)/ n; j$ L: e2 \1 c
 {$ t/ j3 W8 W1 ]# ?
switch(result.schoolname)
1 `! q0 |+ u8 s: f8 }% f+ w {
2 X: |* i0 @' b1 b$ C case 'A':
* w2 u- M, @ h: } score[ 0 ].totalscore+=result.score;6 A9 X. m J$ K% h2 T. n H3 E% P- M
 if(result.gender==0) score[ 0 ].malescore+=result.score;
* k* u3 M) Q: e4 C9 K' t& t else score[ 0 ].femalescore+=result.score;
# A) t8 w z8 @& o/ y1 w" c/ u break;
4 ?; l. k3 J/ F* y/ C; t! d case 'B':2 Z, h4 C* |# N- P, K
 score.totalscore+=result.score;
+ c [$ t2 |! l. X1 C- p ? if(result.gender==0) score.malescore+=result.score;# E* N: @6 x3 ^* a- J( f Z
 else score.femalescore+=result.score;
0 d' v' k$ H( j break;
" o' q5 _" w: x8 H9 {2 u …… …… ……
+ ]& N7 t; r. I/ d3 n q9 Y2 V }& W8 ~* a- Q$ ^$ P$ O7 o; C* x
i++；
' C& j7 ?8 {; C$ o4 ~ }# X- `/ e- W) m0 ~* R$ H2 \
 for(i=0;i<5;i++)
) T) G \0 k- B3 W6 B& i1 e {
' D* |- m+ w/ ]& R4 |- U6 p2 R printf("School %d:\n",i);6 t0 J/ Z/ {( U) I
printf("Total score of male:%d\n",score.malescore);
) G# m, W) ?1 Q0 v2 W) D printf("Total score of female:%d\n",score.femalescore);' I0 b: d: @8 P7 ^1 K2 I
printf("Total score of all:%d\n\n",score.totalscore);
5 C/ ^$ Z, i( {: U+ A( e }- `% T: g8 f% p/ ]- T' b
}//summary 2 c% x/ M' a% B3 @5 j/ T
<>1.19 9 L) T3 p- d0 p
<>Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint
8 w6 F' b2 r/ y: ]8 V2 J' I{
- I& d2 p7 h# E3 g5 [" j3 { last=1;
! y/ U( x# _ v7 ?( y for(i=1;i<=ARRSIZE;i++)
: L7 e$ X- @- U4 f) s {4 R; p0 Q- H/ q3 a+ O( ^5 @
 a[i-1]=last*2*i;
 T' h1 _5 U7 W2 p& z& Q if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;" l* y3 J# t0 @: c
last=a[i-1];) I' y5 E- _4 k
return OK;
" {* r& N* D! r7 _% Q+ R8 b% { }
* c) h& Z0 Z" x6 D* y}//algo119
3 o# S& j0 s' V5 V8 T分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. 
) B1 E$ t6 d0 H! A3 ^' D7 c<>1.20 
& o1 j9 E1 N/ @<>void polyvalue()
6 t4 l0 j Y! J$ O7 @7 |7 F! b{
( x* X5 B U& ~4 p: c% O) e* G! c float ad;4 \1 i; x( H$ W
 float *p=a;" T2 u1 J7 R/ h* C& a
 printf("Input number of terms:");
" N+ {( O0 b% |7 x' w( c scanf("%d",&n);
; r- l( _6 Y d# u& w8 m4 w! k6 L printf("Input the %d coefficients from a0 to a%d:\n",n,n);
0 ^+ v, I& `5 h; Q0 M' r; T( u for(i=0;i<=n;i++) scanf("%f",p++);
1 I: I1 A7 a0 e6 N3 \5 R printf("Input value of x:");
- {# R- V {+ `4 M, R scanf("%f",&x);6 k/ M6 v0 Q* {5 s0 r8 P
 p=a;xp=1;sum=0; //xp用于存放x的i次方) b: }, {8 j7 E+ t+ B0 p
 for(i=0;i<=n;i++)
! j/ W0 H; j( V5 t {5 e; m( b* ]# L, e, l9 j1 H/ a
sum+=xp*(*p++);
3 U$ U g& H' Z1 Y, Z# T xp*=x;
2 B' H3 n5 G7 W2 P: M! k }# v0 n( \9 W) r' a, Z5 Z9 t
 printf("Value is:%f",sum);
+ Z1 c) o- M6 u}//polyvalue
5 H9 C2 T( X" l/ t< >

zan

转播0 淘帖0 分享0 收藏0 支持0 反对0 微信

使用道具举报

铜豆子

0 主题	3 听众	22 积分

升级 17.89%

该用户从未签到

4^#

发表于 2007-6-20 21:54 |只看该作者 |招呼Ta 关注Ta

不是实习题的答案啊

我也说一句

发表

使用道具举报

布赖

4 主题	2 听众	134 积分

升级 17%

该用户从未签到

3^#

发表于 2004-12-18 00:28 |只看该作者 |招呼Ta 关注Ta

<

>很长呀<

>不过还是十分感谢

我也说一句

发表

使用道具举报

╃無名草╃

66 主题	1 听众	648 积分

VisaSky.com 加拿大移民留学网

TA的每日心情

	开心 2012-6-9 03:29

签到天数: 1 天

[LV.1]初来乍到

2^#

发表于 2004-11-28 18:16 |只看该作者 |招呼Ta 关注Ta

<

0cm 0cm 0pt; TEXT-INDENT: 144pt; mso-char-indent-count: 9.0">第二章线性表 <

>2.10 <

>Status DeleteK(SqList &a,int i,int k)//删除线性表a中第i个元素起的k个元素
{
 if(i<1||k<0||i+k-1>a.length) return INFEASIBLE;
 for(count=1;i+count-1<=a.length-k;count++) //注意循环结束的条件
 a.elem[i+count-1]=a.elem[i+count+k-1];
 a.length-=k;
 return OK;
}//DeleteK <

>2.11<

>Status Insert_SqList(SqList &va,int x)//把x插入递增有序表va中
{
 if(va.length+1>va.listsize) return ERROR;
 va.length++;
 for(i=va.length-1;va.elem>x&&i>=0;i--)
9 F# U" n/ s% c) _4 j va.elem[i+1]=va.elem;
( G# W0 }7 Y9 z: k6 l. j va.elem[i+1]=x;; F) w: j; N" m. ~
 return OK; v) @9 X1 N6 H
}//Insert_SqList <>2.12 <>int ListComp(SqList A,SqList B)//比较字符表A和B,并用返回值表示结果,值为正,表示A>B;值为负,表示A<B;值为零,表示A=B8 | ^' L: @0 s1 q! L
{# {: A! y. z2 P/ Z a
 for(i=1;A.elem||B.elem;i++)$ B; k9 h* w4 S8 x5 g
if(A.elem!=B.elem) return A.elem-B.elem;
1 M% A5 p7 g+ D. U/ B return 0;; n, o% P/ }4 T5 ?! N7 {) [
}//ListComp <>2.13 <>LNode* Locate(LinkList L,int x)//链表上的元素查找,返回指针2 q/ ]& s0 u7 j. @" B7 l
{( P# ~4 g4 P& `7 _, y
 for(p=l->next;p&&p->data!=x;p=p->next);6 v, Z2 {, @4 g) `# ]
 return p;
# _# U' p/ [9 L% ^& T# K# N" |}//Locate <>2.14 <>int Length(LinkList L)//求链表的长度
2 k1 b$ c* {0 W( W{
2 m z; ^( p8 N }% C for(k=0,p=L;p->next;p=p->next,k++);
1 \ E5 H& C5 P: A return k;: R4 X5 G- T- A2 |
}//Length <>2.15 <>void ListConcat(LinkList ha,LinkList hb,LinkList &hc)//把链表hb接在ha后面形成链表hc
, P% x! R* T5 ]/ f# n6 {{
: { W7 t6 J- [4 x v1 ?# a7 { hc=ha;p=ha;2 ~% }. ~/ y' F
 while(p->next) p=p->next;
. ?( p8 S- |' Z) y! _ p->next=hb;3 R& k l9 X; U, k$ j$ G/ t2 O
}//ListConcat <>2.16 <>见书后答案. <>2.17 <>Status Insert(LinkList &L,int i,int b)//在无头结点链表L的第i个元素之前插入元素b0 Z# X5 K3 t3 V. A: Y- L; s
{
& R; b5 l& n `) n/ _ p=L;q=(LinkList*)malloc(sizeof(LNode));6 B/ a {) v. D
 q.data=b;6 z6 y# f5 B1 K( S
 if(i==1)1 a2 \$ V$ u5 g! i
 {3 |$ S- f; j! I" A g
q.next=p;L=q; //插入在链表头部
# |0 `7 X5 O) T4 g4 ?+ K }
) O: ]& V' N! v) t* a$ k else
( P* D& M+ v: s4 y {7 }1 V2 p& o# L; {4 l. v2 n
while(--i>1) p=p->next;; C/ M* d2 x6 Q, N$ n/ B8 n
q->next=p->next;p->next=q; //插入在第i个元素的位置
* U9 e4 l' T' Y' Q# s* [ }$ d! M% u1 Z* n% J4 u$ |! s
}//Insert <>2.18 <>Status Delete(LinkList &L,int i)//在无头结点链表L中删除第i个元素
8 H" |( f) V, N- r" H' e& F) u6 d{
" U5 M" z- G) W+ y if(i==1) L=L->next; //删除第一个元素
1 A5 u9 @7 q; J$ g9 A: y% G4 N else
7 {5 P- q" p9 K9 j4 W. N {" M# S* r l4 J
p=L;
+ ]* ^. V5 }* O& w" y5 G while(--i>1) p=p->next;
' @% y8 x/ Z8 }" h% t p->next=p->next->next; //删除第i个元素
/ {# M! I7 @% T1 E/ R }. J7 {6 \" S9 w! m6 x
}//Delete <>2.19 <>Status Delete_Between(Linklist &L,int mink,int maxk)//删除元素递增排列的链表L中值大于mink且小于maxk的所有元素& X! L e! m9 w
{$ X% G8 ]( E9 E8 S1 {, S) |* S' L
 p=L;
- i* f5 y( j4 ~1 V& D4 \; q while(p->next->data<=mink) p=p->next; //p是最后一个不大于mink的元素
7 r A/ a5 r6 {/ O6 ] if(p->next) //如果还有比mink更大的元素+ y% V0 U+ G% V" f# `
 {
, U/ {$ e# x9 M6 S) L$ A9 C q=p->next;
. Z# m; K1 |2 N while(q->data<maxk) q=q->next; //q是第一个不小于maxk的元素
4 M5 C- p0 E5 { y p->next=q;
& N g7 }- k4 q1 y }" q4 L! _3 S& E9 \, C
}//Delete_Between <>2.20 <>Status Delete_Equal(Linklist &L)//删除元素递增排列的链表L中所有值相同的元素
$ ^& U1 a7 ~+ U/ L$ p9 m{8 J& k" w6 `. x6 n4 H" N
 p=L->next;q=p->next; //p,q指向相邻两元素
/ f; ?# f. g5 V9 T while(p->next)
. q1 |, l' {0 y, L7 {, J( d {4 Q3 [ a) {' |) |. P
if(p->data!=q->data). l/ K/ Y$ E. [- ?+ I a% J& N( x
{) R, i6 m2 ?2 I/ G+ v8 b7 w* a
 p=p->next;q=p->next; //当相邻两元素不相等时,p,q都向后推一步# Q: K0 }/ x1 o3 _6 p' Z
 }8 m* \, e0 R; C$ c W1 ~2 _- I; _; z
else
2 m3 j/ r+ ? ?, A {# u, @2 G* n* U; ~
 while(q->data==p->data)
- `" \" \4 ~" f L/ I {
% R/ h7 P$ g5 B" C free(q);
! @) F' ?( I5 o9 ]$ P% B. a( y7 @ q=q->next; # l! d! \( P! u! J: B
}3 O: X: x- b' p$ t: p
 p->next=q;p=q;q=p->next; //当相邻元素相等时删除多余元素9 t7 h5 ^3 x3 a, i; D
 }//else8 K+ q. v4 D4 G/ _7 L
 }//while4 I7 A% Q" m+ F @$ a" t- W
}//Delete_Equal <>2.21 <>void reverse(SqList &A)//顺序表的就地逆置4 `0 [0 J# c' P* u
{
$ C) Y& o! M9 ^# p for(i=1,j=A.length;i<j;i++,j--)- O- {" X5 b4 T2 f7 _8 T
A.elem<->A.elem[j];
9 h/ M/ z% I3 z6 @}//reverse <>2.22 <>void LinkList_reverse(Linklist &L)//链表的就地逆置;为简化算法,假设表长大于2
- |# x1 R; g5 u8 L# s9 z, S& T' i5 ^) x{
 B3 h5 P* q; j/ T3 `7 k p=L->next;q=p->next;s=q->next;p->next=NULL;2 a' S* @5 y9 O7 M' f+ F+ h
 while(s->next)6 e5 Y3 T" t8 L1 z+ Q
 {
9 ]6 ~, |. H+ i. V0 U q->next=p;p=q;
- s, }( }+ W& m; H9 ~5 B q=s;s=s->next; //把L的元素逐个插入新表表头; y5 Q. U: r/ |5 t/ W
 }
& ^: B( z) W5 _6 X: s* `3 E q->next=p;s->next=q;L->next=s;
+ S# Y. K9 r8 ^& C. m6 B}//LinkList_reverse* L" }% ~ H$ N3 ~# X
分析:本算法的思想是,逐个地把L的当前元素q插入新的链表头部,p为新表表头. <>2.23 <>void merge1(LinkList &A,LinkList &B,LinkList &C)//把链表A和B合并为C,A和B的元素间隔排列,且使用原存储空间
; M( A9 a0 \& t{, D5 k& Q% I( A4 I; j
 p=A->next;q=B->next;C=A;% _3 [# a$ ~' B" H' v% d
 while(p&&q)
- u* f4 i: d/ C6 D/ I0 G+ u1 N4 K {5 O, h3 i$ s: q9 R7 l
s=p->next;p->next=q; //将B的元素插入
! p1 V# e( o1 p" S4 Y+ Y if(s)6 u! M V( m7 {6 i9 A8 N
{8 }9 g) M& C- R4 Q
 t=q->next;q->next=s; //如A非空,将A的元素插入: C, g% n/ n, a" x/ P
 }# N) Z/ e( [- q* L: X$ K
p=s;q=t;: e o! H8 i4 w5 D$ j/ w
 }//while3 _. L, V) r$ m8 G/ _0 S! K( E6 v
}//merge1 <>2.24 void reverse_merge(LinkList &A,LinkList &B,LinkList &C)//把元素递增排列的链表A和B合并为C,且C中元素递减排列,使用原空间
0 U: A5 _/ Q1 Y T, E0 c0 P{1 h. L0 ~9 x; t& H* e& K
 pa=A->next;pb=B->next;pre=NULL; //pa和pb分别指向A,B的当前元素+ O7 ?, G/ [+ |6 u5 ]4 @
 while(pa||pb)
( N" }8 t& `% t6 C {/ \) _7 F* Y4 g8 n" K/ }
if(pa->data<pb->data||!pb)* F( u6 e2 T, _# [4 L x
{3 N0 b8 G3 r* n+ O& Z
 pc=pa;q=pa->next;pa->next=pre;pa=q; //将A的元素插入新表' R" ^$ w9 j1 V* h! [0 E' n1 h
 }
3 b5 m8 R% e& B8 I8 l" u9 h* E: d else h% v$ N/ ^" d
{
1 g! U6 d7 c4 M; d# ]) N pc=pb;q=pb->next;pb->next=pre;pb=q; //将B的元素插入新表
; p6 P9 X/ E+ o4 d$ \9 c }8 ^& U. K# s4 z
pre=pc;
4 F9 E4 R2 E( N2 G: t' a3 [ }/ X' o1 P8 R6 }5 |5 A0 \
 C=A;A->next=pc; //构造新表头
2 D$ l3 b" T7 n}//reverse_merge8 |2 `/ e+ a* s
分析:本算法的思想是,按从小到大的顺序依次把A和B的元素插入新表的头部pc处,最后处理A或B的剩余元素. 2.25 void SqList_Intersect(SqList A,SqList B,SqList &C)//求元素递增排列的线性表A和B的元素的交集并存入C中
0 k" n( p1 W T8 S) c) c1 h- Z{. f6 h7 ]- b9 }# z
 i=1;j=1;k=0;$ ]' j. {2 r8 {! h, \
 while(A.elem&&B.elem[j])" B( Q5 f9 f/ O- j+ J8 b* b
 {
' G ?5 e/ a( A5 E if(A.elem<B.elem[j]) i++;
- N; E/ A% \# c if(A.elem>B.elem[j]) j++;' a. |2 F7 E7 _. V" |/ o, s7 Z( |' ]
if(A.elem==B.elem[j])
$ E# f; v1 J; U% V {
0 o* X6 X, z. u( ` C.elem[++k]=A.elem; //当发现了一个在A,B中都存在的元素,
 i++;j++; //就添加到C中
" s; {; H7 `: k; a9 x6 ]) N/ _1 h }# V+ l1 [$ q& X2 Q& t* M1 E9 x2 I6 j
 }//while
1 a1 d% Y6 h9 S* V$ y$ m/ m8 R}//SqList_Intersect 2.26 void LinkList_Intersect(LinkList A,LinkList B,LinkList &C)//在链表结构上重做上题6 g x5 }% y# t
{" Y. ?8 j/ K: c5 p
 p=A->next;q=B->next;7 |0 K. X; S4 J0 `1 X
 pc=(LNode*)malloc(sizeof(LNode));0 O+ v: |, i1 C# {4 M$ r
 while(p&&q)
( ?* W2 w- q- K7 v9 T- R# W5 ~+ U {
7 W3 b' S1 k$ E0 n" K7 P if(p->data<q->data) p=p->next;% b$ E9 q0 y$ K# E, }4 A
else if(p->data>q->data) q=q->next;- Y5 I C* Q& w+ y7 U+ D4 O
else
$ b7 `) o3 Y9 m {
& o* @0 m6 `' W# h" ` o s=(LNode*)malloc(sizeof(LNode));$ g9 B2 v6 \" G! E+ G) V
 s->data=p->data;9 u# j' V O+ k" i( i* y
 pc->next=s;pc=s;
; h8 U, c& ^$ W p=p->next;q=q->next;5 W9 e0 Y! f3 ^7 C+ ^4 ?
}# f2 W: t4 L! U* T5 z. l3 M
 }//while7 A1 X1 N+ R# z# {4 u% ]! a
 C=pc;5 Y. A X& P2 E9 v- [
}//LinkList_Intersect 2.27 void SqList_Intersect_True(SqList &A,SqList B)//求元素递增排列的线性表A和B的元素的交集并存回A中
% B. A- l/ f$ E+ D) ^{
) [* E1 A! }/ @7 O i=1;j=1;k=0;# g4 A6 @# A* R, t/ B
 while(A.elem&&B.elem[j])
, U0 Q, R: q ]6 B, s. f' p7 E: H {
$ [7 P5 J& k5 f) v: U if(A.elem<B.elem[j]) i++;4 V% R/ q( J2 p8 Z- R
else if(A.elem>B.elem[j]) j++;* x+ z# H# H5 M5 Y
else if(A.elem!=A.elem[k])4 \( B) R$ X/ A, w% V3 u
{
 l, ]; ] M/ B3 k9 h: s A.elem[++k]=A.elem; //当发现了一个在A,B中都存在的元素
" K, z5 A+ X3 n6 U" I4 x5 m i++;j++; //且C中没有,就添加到C中# U5 m: g% V; r$ {# e- \$ q
 }
. }4 L) a/ r; e( F5 f }//while
' J8 T& a/ K* ?# i0 w while(A.elem[k]) A.elem[k++]=0;
( N. Y) i) G% \2 C6 l" a' o}//SqList_Intersect_True 2.28 void LinkList_Intersect_True(LinkList &A,LinkList B)//在链表结构上重做上题6 Z/ T7 {# T5 V1 I" J
{
+ x" S# O+ `+ g6 v p=A->next;q=B->next;pc=A;! z7 i, V1 k; l' W) r2 D
 while(p&&q)) f+ ?4 j: g0 R' @* b
 {
, w0 j% y3 f% D7 g+ `; i2 r5 J' s+ O2 K if(p->data<q->data) p=p->next;
8 e$ y" a. m, o else if(p->data>q->data) q=q->next;
) r# @0 c+ U {- v. Q4 _+ S else if(p->data!=pc->data)
0 p! j; d3 o, _ {
0 A. E) Z4 C' \( { pc=pc->next;
: L+ N5 l. O! E& d A. P8 R6 l! |8 N pc->data=p->data;
% d, P5 l( P x* p$ }3 D$ H p=p->next;q=q->next;
4 U2 U6 i, h) J, [ }
0 G' T/ ?+ r n }//while+ ? x+ `) R e. i0 D$ d
}//LinkList_Intersect_True 2.29 void SqList_Intersect_Delete(SqList &A,SqList B,SqList C)
) O/ [% _. t' ]% W{- y, G I2 z+ T# A1 N( W T3 W
 i=0;j=0;k=0;m=0; //i指示A中元素原来的位置,m为移动后的位置7 _( X, J: f$ M4 }
 while(i<A.length&&j<B.length&& k<C.length)
& V+ n' L3 X* @% r {$ r% c. H' h* i. D7 o+ [. d
if(B.elem[j]<C.elem[k]) j++;
: t- I. W" O8 t1 _: F- P else if(B.elem[j]>C.elem[k]) k++;
5 N( T2 q3 m6 F1 r c. V else
; n( f0 b6 U! } }) { {; H% P# i: Z/ |' S8 |3 o) R6 b( n; l
 same=B.elem[j]; //找到了相同元素same7 ]9 l' L, g- d
 while(B.elem[j]==same) j++;
) A0 w5 q) Z3 P6 j' y while(C.elem[k]==same) k++; //j,k后移到新的元素9 \3 B7 R5 g! D8 B* o6 e l
 while(i<A.length&&A.elem<same) / c* u% n. ?' G/ X
 A.elem[m++]=A.elem[i++]; //需保留的元素移动到新位置/ L6 \, M! N# \
 while(i<A.length&&A.elem==same) i++; //跳过相同的元素
, F( z) ~8 ?! K! ] Y% ? }
; c% `7 u6 u$ A. Z, N! G2 M }//while$ z+ G& v7 V/ {( o# C; F
 while(i<A.length)
5 W& M1 c8 Q. j' H* W* p A.elem[m++]=A.elem[i++]; //A的剩余元素重新存储。
 N9 t9 s; l$ w, X3 J/ k A.length=m; " h$ s3 q% W# C& g/ T2 w/ C* w
}// SqList_Intersect_Delete3 ^5 T @" c1 ~& D
分析:先从B和C中找出共有元素,记为same,再在A中从当前位置开始, 凡小于same的
0 v0 G" V. N+ `8 y元素均保留(存到新的位置),等于same的就跳过,到大于same时就再找下一个same. 2.30 void LinkList_Intersect_Delete(LinkList &A,LinkList B,LinkList C)//在链表结构上重做上题
) Z, b2 S8 S$ o/ _5 J1 j{8 L) L( |$ y/ f( J" O' Q' x$ A
 p=B->next;q=C->next;r=A-next;
 O; V3 j1 n, g2 H* Y9 ~ while(p&&q&&r)
9 T* U& u2 l( u, A( e9 K2 L {
6 N' B4 t. `/ l$ G% A/ Q- @; e3 R if(p->data<q->data) p=p->next;
4 Y U% s: T7 J else if(p->data>q->data) q=q->next;0 }2 G8 S2 i& r. }* h5 j
else) `2 j+ S1 V& J3 `, ^
{
% ]2 O' h# Q' K9 j2 | u=p->data; //确定待删除元素u
: C( z; V5 _2 V, l while(r->next->data<u) r=r->next; //确定最后一个小于u的元素指针r9 S1 j2 Q2 D1 m+ H2 L+ h) Q: ~
 if(r->next->data==u)& k2 Z' D- K3 K3 e; @7 x
 {5 A! D* [% ~$ B" G9 @( w" n& z8 Z. o
 s=r->next;8 h( p+ ^8 V0 y( p8 ^- g0 V9 y( i# e5 j
 while(s->data==u)
1 w, F2 e O& i! j. A [. q3 d {( V( O ?# Z1 b- V& A4 j
 t=s;s=s->next;free(t); //确定第一个大于u的元素指针s
: x- K. K" e5 {) D; `6 a }//while5 }; n* Y" [6 @- Y" l6 ^, U0 s
 r->next=s; //删除r和s之间的元素
/ n9 V5 A, T& d% q4 S }//if
( O* M% N* ~( ~. _# O# f7 } P while(p->data=u) p=p->next;
& R" W9 R! m' q. m5 r& V. O while(q->data=u) q=q->next;+ h, W# |6 C9 U& z# t
}//else
& J; t+ {# A6 `, u4 { }//while" ?. X9 ?$ g5 E; ]
}//LinkList_Intersect_Delete 2.31 Status Delete_Pre(CiLNode *s)//删除单循环链表中结点s的直接前驱. K0 @) v* X. E2 e
{7 F1 l- O) D3 ^; ~& s3 d9 V
 p=s;0 N( _$ Z" N U* Q; k3 j! X
 while(p->next->next!=s) p=p->next; //找到s的前驱的前驱p
/ g9 U6 z X; ? p->next=s;
( U1 Q& o' S6 o8 T# q return OK;
% e4 U. x o; q o}//Delete_Pre 2.32 Status DuLNode_Pre(DuLinkList &L)//完成双向循环链表结点的pre域1 K$ [8 v4 L$ n
{# [6 p3 K( U6 N* Z% Z
 for(p=L;!p->next->pre;p=p->next) p->next->pre=p;
7 W% ?4 e' s( x! |. H2 k1 c return OK;
3 f$ d% ~8 [8 D( ? r' ^}//DuLNode_Pre 2.33 Status LinkList_Divide(LinkList &L,CiList &A,CiList &B,CiList &C)//把单链表L的元素按类型分为三个循环链表.CiList为带头结点的单循环链表类型.
" }+ O% u# U( l* D{, O# N. u5 u# l) |
 s=L->next;
9 u! q) R5 Z$ S. u; ]3 f9 W- n K A=(CiList*)malloc(sizeof(CiLNode));p=A;) B: L( y8 o9 Y" Z5 t: l# }
 B=(CiList*)malloc(sizeof(CiLNode));q=B;0 J! x1 s, ~ d' |' z
 C=(CiList*)malloc(sizeof(CiLNode));r=C; //建立头结点
3 Q( e2 |% ?8 v% g C while(s)* h+ a( x( T# J% [% Y& Z5 W) N
 {
' V) L1 v, l" M: m7 N5 W4 |! | if(isalphabet(s->data))+ |0 H; ]; Z$ o! A
{5 }/ k2 A% l3 ]
 p->next=s;p=s;
0 J7 w- _( y/ W' W% | }
8 |, H0 m$ b$ @3 _" m else if(isdigit(s->data))& A4 t6 l3 j+ q8 F5 P3 g) k
{
5 |, z1 G, M3 h& g3 W q->next=s;q=s;) B1 q/ d- W; ?. ]
}
. r$ w R3 q$ d0 f# l; J else b( S& i O1 P; L. O& v J
{; X4 F/ L; U( q* j! W( m
 r->next=s;r=s;
/ f4 o+ q1 a% ^# m8 [+ p- y: P }
1 _8 _ o+ X2 }- K3 X }//while
$ `8 y5 h- N( k0 o5 Z( F; s p->next=A;q->next=B;r->next=C; //完成循环链表# s1 T7 m& ^9 p" T0 s8 I
}//LinkList_Divide 2.34 void Print_XorLinkedList(XorLinkedList L)//从左向右输出异或链表的元素值3 c @- @' U$ T, P1 N& x" n5 w
{, C# l$ f% }3 e$ f
 p=L.left;pre=NULL;; c* r M# U2 A, a% D# F8 ?/ a
 while(p)) @; G( h5 I2 }3 j1 b0 b
 { e C e8 i4 S9 }/ t
printf("%d",p->data);
5 k4 g" b7 M' Z9 x7 X q=XorP(p->LRPtr,pre);
% H/ L# t f8 x0 x& X( ] pre=p;p=q; //任何一个结点的LRPtr域值与其左结点指针进行异或运算即得到其右结点指针/ N0 ]* S; C5 k1 ~# ]( w
 }2 a, |+ H9 G$ O1 \1 M/ C2 s
}//Print_XorLinkedList 2.35 Status Insert_XorLinkedList(XorLinkedList &L,int x,int i)//在异或链表L的第i个元素前插入元素x
- u' |0 u+ {( r" |{- b n" i b' F; c: C( t6 @
 p=L.left;pre=NULL;
% V1 D# _0 x- m r=(XorNode*)malloc(sizeof(XorNode));
: A# \# M0 v( ? k: y$ }. ` r->data=x;
5 X+ J# T/ B: s! B if(i==1) //当插入点在最左边的情况5 M1 ~' y9 Y$ A1 b& b8 [
 {) j2 `6 s3 k0 `* p7 X$ x
p->LRPtr=XorP(p.LRPtr,r);
9 a! a2 s( ^0 P r->LRPtr=p;
0 y, T: z; f1 k8 t) k. i L.left=r;
+ l; D; A6 k& j$ W* H0 j9 N return OK;8 M( N6 N7 a6 v/ ^9 m$ d/ J
 }
/ R" }7 G5 ~# v7 W j=1;q=p->LRPtr; //当插入点在中间的情况# e- R# g' P6 f! @& b$ v
 while(++j<i&&q)
0 o4 D" g: g `1 d+ x {. c: }) a6 y% O% ~$ O6 \! X
q=XorP(p->LRPtr,pre);
7 m- y- {6 a) Y4 t# K- x" q9 t: M; ? pre=p;p=q;
* E4 h: {+ m+ j5 N }//while //在p,q两结点之间插入1 z: f9 z; F9 r& }: R
 if(!q) return INFEASIBLE; //i不可以超过表长- n4 s* t* p4 e6 E7 t
 p->LRPtr=XorP(XorP(p->LRPtr,q),r);* X; K2 z% B4 G5 R
 q->LRPtr=XorP(XorP(q->LRPtr,p),r);5 i5 j q2 _1 C( N" R8 G# s$ h
 r->LRPtr=XorP(p,q); //修改指针0 l6 y( G0 F( v0 h; Z& J
 return OK;
+ T$ G5 } |/ i: v}//Insert_XorLinkedList 2.36 Status Delete_XorLinkedList(XorlinkedList &L,int i)//删除异或链表L的第i个元素
3 ` Y# Q8 n ?3 t: M% _{3 u, S2 K3 M: k: C
 p=L.left;pre=NULL;' b/ W4 u) N% N
 if(i==1) //删除最左结点的情况
: ^4 K( o& ?4 m0 j {
5 q7 Y+ G0 n) {" l8 T q=p->LRPtr;
9 p1 H s* V( S5 H: |# h8 o q->LRPtr=XorP(q->LRPtr,p);
3 t* Y5 u5 m5 r6 Z4 g L.left=q;free(p);
5 H- V4 P- x+ U Q6 f3 s/ k1 ~ return OK;6 X( P* P% j. G7 W" c
 }
+ ^- y( @. p0 Q8 W/ j, y7 F. v. g5 Y j=1;q=p->LRPtr;; y4 a2 r6 K0 @# f, n
 while(++j<i&&q)! K0 }# O' E& e* n c" f
 {
2 E( p7 H+ e( x$ }- v: z q=XorP(p->LRPtr,pre);
 X# G$ w$ v1 r2 V' E! U( H pre=p;p=q;
4 C# Y8 V- ]" k# p8 v' P }//while //找到待删结点q
/ \0 U6 ^0 h t# V" i' z if(!q) return INFEASIBLE; //i不可以超过表长
" S# M! ?. h6 {' z: A0 y2 Q if(L.right==q) //q为最右结点的情况* B1 d3 W$ k0 F
 {9 @) R/ j$ x; q' X. n9 A/ E1 l
p->LRPtr=XorP(p->LRPtr,q);/ J8 Q# m9 f( V# [3 G
L.right=p;free(q);, w1 x' f& p3 b: m
return OK;0 p5 F: d; a) _0 A
 }
8 S4 t3 Z: K4 B- F r=XorP(q->LRPtr,p); //q为中间结点的情况,此时p,r分别为其左右结点4 M. u: t) _+ E
 p->LRPtr=XorP(XorP(p->LRPtr,q),r);, d* ]5 K0 ?+ B' A
 r->LRPtr=XorP(XorP(r->LRPtr,q),p); //修改指针3 Q0 K; v: u4 @( k: E3 o' @
 free(q);
" P: P' n- h3 E5 D0 w1 e: l return OK;
6 W/ @# ~' f2 r" a1 Z}//Delete_XorLinkedList 2.37 void OEReform(DuLinkedList &L)//按1,3,5,...4,2的顺序重排双向循环链表L中的所有结点1 e* @4 M6 n2 R! s8 c m
{
- B, l. T/ u" r' I- N% Z J p=L.next;
$ d+ k5 a3 w4 E( u while(p->next!=L&&p->next->next!=L)
- L2 N4 a1 P) l1 A9 A! h) K) b1 w {
- z6 N7 F, s' D- Z, d p->next=p->next->next;
4 |* m6 R# l& z0 e' m1 C* I p=p->next;+ X z' M! y6 x' N. K% f
 } //此时p指向最后一个奇数结点: C n- g4 C7 X: ]0 A' s5 S, b, k
 if(p->next==L) p->next=L->pre->pre;
4 F; L8 Z8 q* {' k else p->next=l->pre;
7 m% k% K/ d: W3 `* |: i p=p->next; //此时p指向最后一个偶数结点
1 f# k# b5 P. a. H3 T3 {5 c while(p->pre->pre!=L)
" U p/ }; H8 K& k9 r9 M {; h3 P, ?0 F& K! a3 x9 Z
p->next=p->pre->pre;/ W. O0 u+ ?$ f; M
p=p->next;
( }4 ~3 i2 ^8 L2 \* Q8 q9 u }
; L- e2 d1 K8 s) u0 Q% |5 I& A+ c p->next=L; //按题目要求调整了next链的结构,此时pre链仍为原状5 x2 E, D7 j( L7 m }% I5 c4 Z
 for(p=L;p->next!=L;p=p->next) p->next->pre=p;
! g- h: ^* h/ j L->pre=p; //调整pre链的结构,同2.32方法
3 n# O. p, G6 w7 U* V1 p5 S}//OEReform/ y g k; s* d! ]3 Q/ }8 p
分析:next链和pre链的调整只能分开进行.如同时进行调整的话,必须使用堆栈保存偶数结点的指针,否则将会破坏链表结构,造成结点丢失. 2.38 DuLNode * Locate_DuList(DuLinkedList &L,int x)//带freq域的双向循环链表上的查找 O7 f: s2 @1 Y$ S- N
{
) B. u& w) g8 J2 p p=L.next;
- P' D) T8 a2 P; V; } while(p.data!=x&&p!=L) p=p->next;% U. _( t5 s7 D
 if(p==L) return NULL; //没找到
1 D/ Q3 T# H2 ] p->freq++;q=p->pre;
; d, W- |; }4 Q! _; q while(q->freq<=p->freq) q=q->pre; //查找插入位置/ R e- ?: k- ], p% L7 F# }- z) F" f4 h
 if(q!=p->pre)9 h8 |) p% h1 E% h4 Z3 {( i
 {; [- Q* J2 _ }1 M4 d
p->pre->next=p->next;p->next->pre=p->pre;
+ \5 @* @ O) a3 F! i$ W q->next->pre=p;p->next=q->next;% J- ]0 b$ ^( U4 n, \
q->next=p;p->pre=q; //调整位置' T1 G! W! A8 K Y/ w
 }
* D8 [6 I4 I h5 S: Y6 ^ r+ k return p;
- O6 U+ @4 A1 G" a! Y}//Locate_DuList 2.39 float GetValue_SqPoly(SqPoly P,int x0)//求升幂顺序存储的稀疏多项式的值4 K5 \1 l$ u% ~* y# @; x
{4 ]9 N1 ]+ J' V5 \; p
 PolyTerm *q;, I9 }: w, f9 G0 }
 xp=1;q=P.data;
2 o+ S! M s' ?% N' D7 }) E2 j sum=0;ex=0;
7 O% n7 J& ^ ]) B: }6 p, I: n while(q->coef)7 P0 G6 m& _2 |+ i
 {
, f& m4 K; p' Z' e! s2 b while(ex<q->exp) xp*=x0;: ^9 G, l7 u6 G! Q
sum+=q->coef*xp;: \6 x; {* f$ P, p3 l" c
q++;* D) R2 M4 U- k: Z/ ]
 }
4 G3 o( G4 x' @% A return sum;
9 d5 x2 q: Y/ _0 G& l5 q3 _! q}//GetValue_SqPoly 2.40 void Subtract_SqPoly(SqPoly P1,SqPoly P2,SqPoly &P3)//求稀疏多项式P1减P2的差式P3
" W* r Z/ u* y! N2 B2 w& g3 L{
1 L- k1 D9 e; J8 v1 x PolyTerm *p,*q,*r;
; {3 `* R9 O" L, u9 i z; R Create_SqPoly(P3); //建立空多项式P3
3 J4 B M$ d- @& ^ p=P1.data;q=P2.data;r=P3.data;. d8 _8 w' A8 ]) V$ v4 F
 while(p->coef&&q->coef)7 n+ e4 k4 ]" a/ ~( E0 _
 {9 r' t: h) ~. L( C
if(p->exp<q->exp)
6 f( G4 b: s9 [+ J: R/ j {9 ]% ^8 e; F5 X! P* z7 f
 r->coef=p->coef;
) X+ K1 ~* Y. y9 ~ r->exp=p->exp;4 u7 Q) _: l" d) k, J; _9 D
 p++;r++;- V+ a1 J& Y# Y3 y, y% |% v, P$ q
}
. \1 @1 P0 [1 K5 _( E! l else if(p->exp<q->exp)0 b1 K1 D9 K" ^' i$ o
{( }0 L n. ~* N' p4 @" e
 r->coef=-q->coef;1 Y9 Q1 P) t3 |$ Q F4 I7 ~. y
 r->exp=q->exp;8 X# M) `; [* G2 V, N/ J3 P' Z5 r
 q++;r++;- N9 d7 E0 u5 X
}
5 g2 M1 n0 \) P; u else {6 |0 F% l. a0 V: S: ^1 z& A
{
" F0 T" X' U! f" k: ^$ U8 P6 i if((p->coef-q->coef)!=0) //只有同次项相减不为零时才需要存入P3中
% y1 j" o% o2 p: x, F; E {
: D# ^* m$ M- h# f0 B r->coef=p->coef-q->coef;
) \3 y" S, f& c! x. g: H r->exp=p->exp;r++;, A. ~) \2 i9 d6 K! h+ F6 y% c
 }//if
8 ^' g4 V* V+ }/ Y" j. d# `! E p++;q++;
" q9 D, i8 T9 K U' Q% t; k( ` }//else
, U- ~/ a' d; j; ]" `! z9 U }//while
; a+ n7 \9 i: R4 g# [6 l while(p->coef) //处理P1或P2的剩余项
' {6 H7 L& h9 @, v6 H' {1 x8 @ {
$ r5 W" ?( J( t1 Y0 `( h5 l/ U r->coef=p->coef;7 @% E% f& S% Y8 G
r->exp=p->exp;
. v2 e: M# `- z) i3 N( Z; e2 P p++;r++;3 C8 ~, E' w, {! l: x
 }
0 o8 W( u( l/ U8 H. I6 z while(q->coef)- ^4 h0 Q! k. w
 {
 m' y, Q6 @3 d, c8 K r->coef=-q->coef;. O; R2 i" J9 h- H4 ^
r->exp=q->exp;4 f" m( s+ m9 }
q++;r++;1 ^! s; J& \4 n! y% u
 }
! d. u. b7 {$ S}//Subtract_SqPoly 2.41 void QiuDao_LinkedPoly(LinkedPoly &L)//对有头结点循环链表结构存储的稀疏多项式L求导
: g2 `- W+ h1 H{/ v7 h1 m; Q4 u# A, S1 D
 p=L->next;
+ D6 L4 w1 l3 l0 `% D if(!p->data.exp)6 f3 d) F* T! Q6 Q2 s
 {7 g& H, u' Y* C/ `) s0 K. E1 e
L->next=p->next;p=p->next; //跳过常数项5 J+ A# f+ P+ d9 h: w8 ?
 }
2 W& c9 E u+ ]3 y8 q4 ] while(p!=L)/ e9 p9 _' } s4 j) ~. p
 {& o! e, {8 ?9 C7 ?& x! l1 z# i
p->data.coef*=p->data.exp--;//对每一项求导
2 f0 o1 S+ T# J5 o p=p->next;/ @ T5 K: C: t
 }
* J3 m: g- ~+ Y J1 F$ L}//QiuDao_LinkedPoly 2.42 void Divide_LinkedPoly(LinkedPoly &L,&A,&B)//把循环链表存储的稀疏多项式L拆成只含奇次项的A和只含偶次项的B; u F4 L4 ?$ f7 X" S3 x# G, l
{& ~' Z: Y6 y/ f
 p=L->next;
$ q5 T2 {/ i+ h- m% A; u A=(PolyNode*)malloc(sizeof(PolyNode));
7 t# O- X$ d4 M/ \( k4 } B=(PolyNode*)malloc(sizeof(PolyNode));
5 l1 R/ w) j a pa=A;pb=B;7 z5 d* O- A- B* c8 i/ B
 while(p!=L)
2 | [7 p3 x1 r8 u5 }3 i% S {
* q" L: t: ]( }- z9 K if(p->data.exp!=2*(p->data.exp/2))
5 [$ M, r3 b; G. s) g! Y4 D# I3 f {4 C2 l( P+ G* Q+ s7 A2 C" C) |
 pa->next=p;pa=p;
( p" }: h2 J1 |/ F }
3 q( l3 ~1 G1 A) z; _ else8 K0 ?% v* L9 y/ i( o. K& ^ Y
{( m. W7 O" o2 q3 V- |" m s5 ^
 pb->next=p;pb=p;- f# a- H! t( y; W
}# z# J! f+ L3 D/ J
p=p->next;0 ?. v. _8 p/ G8 ~
 }//while
, ~( w6 V, f0 a- {2 s/ E% x- y- J* `/ A pa->next=A;pb->next=B;
' D5 o- z5 m8 K F}//Divide_LinkedPoly

我也说一句

发表

使用道具举报

返回列表

帐号		密码		只需要一步，快速开始		注册地址	找回密码

《数据结构(c语言版)习题集》算法设计解决方案

发帖功臣

元老勋章

新人进步奖

QQ

电话咨询

关于我们| 联系我们| 诚征英才| 对外合作| 产品服务|