查看: 5005|回复: 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;% Y" g% ^* _' B& Q- L9 T' D
temp[k-1]=1; //初始化. Q% @, v8 Z* Z: E; v1 }1 Q5 {. v) Q
 for(i=k;i<=m;i++) //求出序列第k至第m个元素的值3 t9 D K, N4 Y- L5 A
 {
- J+ ^ {& Q; g; L B sum=0;( B9 g1 u3 ?/ \7 w$ H! p
 for(j=i-k;j<i;j++) sum+=temp[j];
; ^! B7 o* i: _0 ^# u+ N temp=sum;$ K* ~9 g8 R& A' Q4 k: D, B t
}
, B Z* m+ {& w$ L f=temp[m];
0 C. [& G0 x0 B( V1 H1 L }
7 W% Q* l+ _, J5 E, n& a9 P- n4 z6 D return OK;: E. x! z( q( c0 \# x+ \3 u/ } H
}//fib; A( O3 R# b8 { I& f
分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m). 
: Z* R3 g7 M* r6 K<>1.18 6 ~: m% o. r- w- ^
<>typedef struct{
4 l- Q: E+ Z( c6 F. H char *sport;
; y9 W( l c1 H+ Q7 e5 \( X* d enum{male,female} gender;
, w, H I8 Z" h char schoolname; //校名为'A','B','C','D'或'E'# W1 t& w5 F8 ]( ?8 X8 j g4 f
 char *result;
5 e3 a. x8 |' y) L% ^, k, [7 l( p int score;1 \! C4 w" y: u: w# N2 \
 } resulttype; 
- e- j, c; ^/ A' x2 d8 C<>typedef struct{9 u! K l! M5 `/ H- {! X1 ?
 int malescore;
, I% X# ]/ s3 A! v' d0 h) x, J int femalescore;/ h+ J T8 q9 w* R0 O5 m
 int totalscore;; Z5 A" `' u* u
 } scoretype; 
/ b4 D# W9 |% D- U. }# a' K<>void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中
, S+ F. b F E! b+ \7 A{! D/ x9 |8 g% S, R
 scoretype score;
. O y' b0 T' x/ O9 T2 j i=0;
/ e; Y- g! l% ]. h& u3 U while(result.sport!=NULL)- D9 S/ Y0 }5 }
 {
2 Y7 A9 \. W+ s: L5 i switch(result.schoolname)0 v: H: Q( l* \9 l. p5 @5 q
{
; Y4 @* t5 R7 a7 j: F case 'A':
. m* Q' c6 s) I- J( Q! u: @7 \" o% h score[ 0 ].totalscore+=result.score;
6 r9 x. N8 E! T. `5 M if(result.gender==0) score[ 0 ].malescore+=result.score;4 I, c6 _6 S2 B( x" q
 else score[ 0 ].femalescore+=result.score;6 N6 p' L% ]& X; L8 q: g- \; x7 G4 B
 break;
$ E7 u3 p ^ ^) c$ v n case 'B':, d0 A' @, D2 L7 \9 ?( p q
 score.totalscore+=result.score;
" J4 ~ U4 z# x8 G. Y* I) C if(result.gender==0) score.malescore+=result.score;
& J. ?' r/ p8 c9 t% X' i# N5 i else score.femalescore+=result.score;6 L7 R3 m4 Y; s4 u( \: M
 break;
% }/ X+ b, z6 {# K' j$ B …… …… ……
2 h8 J7 I T- b) i$ q7 X }
7 u+ t7 C1 n: ^! v: A" g) B2 p2 b i++；; d1 D9 P/ S k: Q
 }
; b$ h, C! i# ?2 P9 j M- ~' g for(i=0;i<5;i++)9 _7 m" N( Z% S9 q1 x. g$ n! l$ l
 {
$ r" P% J2 D8 A' F- K. c' ]3 i) g2 V( \ printf("School %d:\n",i);
/ _8 s n# [0 N6 w0 Y. e printf("Total score of male:%d\n",score.malescore);
! j! G. Z/ {- X1 ]' B! B printf("Total score of female:%d\n",score.femalescore);% x( F6 s9 G0 O: Y7 w
printf("Total score of all:%d\n\n",score.totalscore);# E) ?6 Q k3 l! Q, w. ?7 q
 }) a2 b8 f, `( x. B+ }" t
}//summary 4 c$ K) U3 @/ W. g
<>1.19 
4 I& t: [) x( O+ J8 F, {5 e<>Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint! D% g) s8 _' W& O( H) p
{
: K; Z* `4 _! z( W& }2 s! R7 C6 e last=1;
, q; L- Q6 L' r2 a for(i=1;i<=ARRSIZE;i++)
5 e) A, `3 \ P- c$ j' c( T, G7 ` {
3 [& w7 e, ~# } a[i-1]=last*2*i;/ c/ c/ {- N! C
if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;1 ^ b6 C; t5 U4 X, q
last=a[i-1];0 b7 G" i6 W0 r0 }$ Y# B2 m. B
return OK;
) A& j) [2 [& f! ` }/ t7 `0 l7 Q2 I
}//algo1192 @9 i/ \& h8 J
分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. " g8 E7 @# f9 Q
<>1.20 % I1 J4 R( H9 P2 Z% Z) U0 g
<>void polyvalue()
6 j s! h7 d) K; t{: j3 z T4 S+ a" N2 s
 float ad;) c [ @0 r: Q' I: w3 |
 float *p=a;/ K( w9 m! R4 {5 b; e* k- q
 printf("Input number of terms:");/ O3 {9 a. q$ t* g
 scanf("%d",&n);% l1 \& _. y1 B1 A& S5 k( @0 b
 printf("Input the %d coefficients from a0 to a%d:\n",n,n);
8 |9 q( J( n4 S" z6 e- _ for(i=0;i<=n;i++) scanf("%f",p++);
$ a; C3 \* F6 \! |/ q printf("Input value of x:");; k* }" Y. ^) J h' O6 Z: N! k
 scanf("%f",&x);5 l% t& H' f" G7 `$ m0 e% F
 p=a;xp=1;sum=0; //xp用于存放x的i次方
1 b+ h! C8 Q* f% Z/ l/ [5 j) S4 N5 n for(i=0;i<=n;i++)
; i B3 q, q6 g) m8 u" D- a6 C0 _ {/ Y/ G4 `; K; ~5 L7 j8 b" j
sum+=xp*(*p++);
9 W" W# X+ j, J- l' ~: a xp*=x;
: `3 j5 v5 s: K# J; w }
 printf("Value is:%f",sum);
 O r# s( b# d5 A}//polyvalue! ?. d' G' g' R8 _$ A" f
< >

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

我也说一句

发表

使用道具举报

返回列表

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

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

浏览过的版块

发帖功臣

元老勋章

新人进步奖

QQ

电话咨询

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