查看: 4970|回复: 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;+ i' O& I) L5 i1 Y) V e; h
temp[k-1]=1; //初始化
* a# g! U4 f$ f7 B! p; f for(i=k;i<=m;i++) //求出序列第k至第m个元素的值# T) ]0 F5 B4 t; J- v, y
 {+ o+ r" h/ G1 n* r2 _( h
 sum=0;: J; B, H2 Y) m0 i
 for(j=i-k;j<i;j++) sum+=temp[j];
1 z/ D- Y3 X, v temp=sum;
" ?: Q' k: L3 m: m9 I9 E/ M }2 k4 d0 D/ O0 c9 j. S a
f=temp[m];
! C2 h- @% M1 _ ^0 n1 Y* @+ v }
0 u7 ~! ^( b3 O( y3 z4 B return OK;
; v6 N1 n; O, Z}//fib1 ^1 s" ~$ d. Y) P: `
分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m). 
<>1.18 D0 k* C* }- X" y/ I
<>typedef struct{7 m' [( v3 Y A6 X6 v
 char *sport;
9 n/ Y( }/ P1 C( j0 W0 Y enum{male,female} gender;0 p. ]! _) S" Y- a
 char schoolname; //校名为'A','B','C','D'或'E'( ` O: O% y5 @& g8 S
 char *result;
+ U9 n0 Z; d. F4 ` int score;
5 G) G: o% B7 C# f6 W } resulttype; ! N' d2 ]* k4 \( i
<>typedef struct{
/ M& f/ A# j/ z" D7 j int malescore;* c2 U3 J7 T# C; p H' a3 j
 int femalescore;
- J0 {9 |9 t7 ^# K. g6 D! l% ? int totalscore;& y3 \' `3 w, P0 g+ u
 } scoretype; 4 L( a0 F' k; L# x1 Y0 q
<>void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中
9 z% `9 h7 @# K; L8 _" w{
/ {! {) ?5 M' ~" x5 A$ I5 N scoretype score;
% i6 B6 ]9 Z4 k i=0;$ M3 X- o2 k0 e0 c/ p5 [
 while(result.sport!=NULL)
7 X- j& Q! ?) D# M% E! u- X1 W0 r {
, [' Q# h$ |' j' P! l9 a- l8 e8 S switch(result.schoolname)
% k# h: O+ w0 O* n {
/ r/ b/ t) [0 Q2 |1 @ case 'A':
7 U6 ^* }. m8 U2 c. o# Z4 `0 I score[ 0 ].totalscore+=result.score;
3 H' D0 U. u* G6 b1 Q% q- A T if(result.gender==0) score[ 0 ].malescore+=result.score;
9 S2 p! r8 L0 h; U& z& C: U2 }5 R else score[ 0 ].femalescore+=result.score;
7 W) N7 L4 H' b1 v% O! c7 h" J q break;
) n8 g2 G- v/ O2 M case 'B':# g8 L( e5 B; K
 score.totalscore+=result.score;' F6 H; @: R/ p( w, ?
 if(result.gender==0) score.malescore+=result.score;
! |8 n8 [2 N- J" f/ D( a else score.femalescore+=result.score;
$ ~) j. p; n- E7 p6 a+ J9 y Z break;
: s+ J' r# ^$ y2 ~) m, z …… …… ……
5 ~' v6 s( r4 `" a9 r- R }
" p9 j9 {3 C$ K) {) Q" L( q i++；
# V5 |! {% o* G6 W# O }
/ i2 P6 E, K# N# T. Z for(i=0;i<5;i++)' `+ H, `1 d* W1 E! m
 {
/ w, ]' x5 J% d) Z! R printf("School %d:\n",i);1 l% i0 ]( U9 `6 N5 k
printf("Total score of male:%d\n",score.malescore);1 |* O% Q' D* P+ l& N- @
printf("Total score of female:%d\n",score.femalescore);
, e2 T; I4 K! ]+ F printf("Total score of all:%d\n\n",score.totalscore);! h0 L9 d& P' n! n/ P# |# y/ \
 }
8 b: z9 t6 M# ^9 q+ F: j}//summary # W$ i! H3 x# l
<>1.19 
2 P5 N+ I5 z+ E) I<>Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint( t2 f; n" i+ D3 i( ]) l! k
{
' F3 d( h! X' ^6 Q7 k. [9 {! N last=1;
! t3 k! @: ?1 d; V& V for(i=1;i<=ARRSIZE;i++)
. l' ~ o2 B: P+ ]# J+ } {( r! s T- |: H4 Q/ V# T
 a[i-1]=last*2*i;
% G. U ^+ R0 c- Y if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;
& b- ~; `9 @! ^2 d$ v# A last=a[i-1];
( e- F& q- j2 P5 @. f return OK;
 }# {( [1 h, {* s
}//algo119
, g, |" ?7 j- |7 W: n2 X分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. 
3 A0 {, S" M0 c u: g$ o5 `<>1.20 3 R* S4 [1 Q& g1 Z7 ?, A [5 D
<>void polyvalue()9 L X3 C( x, |
{- [" t. [) s) }( ]6 x9 i$ X" }
 float ad;
+ A- G; `4 U5 Q float *p=a;( N! t$ t3 q/ j6 z) u: x
 printf("Input number of terms:");
0 p! k8 @# R/ N Q4 l scanf("%d",&n); \# r2 M7 v6 X3 R) T
 printf("Input the %d coefficients from a0 to a%d:\n",n,n);9 B( @2 Z @9 J
 for(i=0;i<=n;i++) scanf("%f",p++);( t4 A% L+ m7 T. z
 printf("Input value of x:");
' y; ] T1 G+ ?# H scanf("%f",&x);) X8 w+ p+ O* b
 p=a;xp=1;sum=0; //xp用于存放x的i次方
- s) B* ?% A0 r$ X8 L9 G2 M7 E for(i=0;i<=n;i++)
5 @- p4 E u2 J6 q1 v# m {
& g) Q" E. y+ c* O8 ` sum+=xp*(*p++);+ }, q+ f5 B. \% [) M$ t0 q/ [
xp*=x;
" q% }6 T, M) K5 [( \. [& o& B }; `; c* E* q: L0 L$ a, P, [8 j
 printf("Value is:%f",sum);
' k! c& w7 c3 e}//polyvalue/ A3 \ Y+ ~, o8 |' Z2 z+ g
< >

zan

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

使用道具举报

╃無名草╃

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