查看: 4935|回复: 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;% [/ b, v9 j0 Q5 f/ ^
temp[k-1]=1; //初始化
( D+ m( }: X' @2 |! Q for(i=k;i<=m;i++) //求出序列第k至第m个元素的值2 a3 b( U$ B7 L' X; s
 {
0 ~0 m, ], ]4 h. a2 E% }0 H% ~% q sum=0;
" U& I5 N" i; Z+ n for(j=i-k;j<i;j++) sum+=temp[j];
' R& R; ^5 W; y temp=sum;. ?6 p$ B1 r2 O
}5 W( h: ?& |& {3 ?$ D9 J
f=temp[m];
- V: [. ]+ ?2 u# w+ B! I }; d; D3 C7 J7 s7 x3 j
 return OK;0 s$ Z9 V, Y% S) v% x5 _
}//fib
2 E) n# [/ [2 |. A' g分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m). 1 V5 {9 e* f$ ]( H
<>1.18 
4 m3 Z1 j0 ]) ]<>typedef struct{
, D. V7 E/ R! H8 L# b char *sport;
2 h$ ~+ k' d' a" v9 l! v) a enum{male,female} gender;
+ ?6 _, x5 Q' x- d1 Q+ Y char schoolname; //校名为'A','B','C','D'或'E'8 c* }) P! p) {) d+ T7 M
 char *result;( ^8 D" b C: t( w( J$ J
 int score;
5 z2 C+ R) W% P7 Z } resulttype; : @( w3 O C- I
<>typedef struct{/ p2 R v% r9 _ `9 e/ H5 c G5 {
 int malescore;! x* q s/ H3 Y8 P4 `
 int femalescore;# k. @; P- H" ]$ @: o/ m
 int totalscore;& X! S0 y( W% X; n; H" r
 } scoretype; + W+ P' r9 L- r( `+ y$ `0 A, q6 [) h
<>void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中
+ Z, w# \0 F- Y8 s S{3 b; E% Q$ B- F4 } r7 l+ c# q9 ^
 scoretype score;
* ^% n7 `3 S. a( j9 F9 C i=0;, R5 z2 P6 b/ U( G: x; a9 g$ v; c
 while(result.sport!=NULL)7 |- {) d7 Y9 N5 x
 {0 A- Z! p1 |$ [: z& g% V) R
switch(result.schoolname)
{8 G! a% G/ p/ e) v' z5 z
 case 'A':
2 w% p! h: f* n$ ~: Q- @# ~. { score[ 0 ].totalscore+=result.score;
( B; M9 Y% `: u5 E& B if(result.gender==0) score[ 0 ].malescore+=result.score;
+ }9 i* z+ H" g S else score[ 0 ].femalescore+=result.score;: s0 Y o. f" }% w; \2 X
 break;
0 X6 z. L% l5 K5 Q case 'B':
9 x, R. k8 ~1 B6 M2 H' ^ score.totalscore+=result.score;
: }: y0 X4 O; N, B if(result.gender==0) score.malescore+=result.score;
. i' r. N+ y8 H6 O3 R$ u else score.femalescore+=result.score;
. f7 P* ~+ {/ p/ K& o6 ? break;
+ g$ ]7 M. F3 y. G7 o0 ? …… …… ……; T* r/ Y+ j4 A/ F, z% P7 D! m) [
 }: Y- \4 c1 J# _2 \: Q( P1 W( F* S' q
i++；
3 e1 s0 q9 B7 Q! j- L }
: ~: i4 e1 m* ?. ]6 r for(i=0;i<5;i++)
* K0 c+ [+ M/ d8 ] A7 D {1 p7 _ H2 n+ ^" s" j3 t4 m
printf("School %d:\n",i);5 k$ U9 X, ~$ O- ~
printf("Total score of male:%d\n",score.malescore);/ x- E( G7 \4 G4 E& K& u& c4 d
printf("Total score of female:%d\n",score.femalescore);
3 M2 ^5 ]. V3 v; O& o1 \ printf("Total score of all:%d\n\n",score.totalscore);
; u8 |7 P p* E) R/ E6 _- r }: G" e5 x" n5 _% k: G
}//summary ! O! R3 J! R# b
<>1.19 
. e( o7 C. J ~3 M' R* E( }<>Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint" x, d7 p w" W
{4 w$ x. l& l. H' y+ G( t
 last=1;
; p0 c, J* y% G. J1 L% y for(i=1;i<=ARRSIZE;i++)
; Q) P' G: h. M3 d {
) `* P7 k" J9 @; \. @5 M a[i-1]=last*2*i;
/ g, t/ ~" r9 z8 \' _4 } if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;" Z1 |7 L8 e1 }9 I- A
last=a[i-1];
" |. `" h9 H" S' L( Z return OK;1 s7 [& U1 u+ p- }9 [
 }+ p# G8 `3 [7 K2 G
}//algo119/ L- P7 U8 B) h
分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. 
: x0 x1 w& E; B7 w4 p: {- n<>1.20 
) S" H; F0 Q2 {% j- g" c; V<>void polyvalue(), p6 C- D k0 A3 d+ V
{
: w2 J2 O- o2 Q+ i( Y. L2 K float ad;% g" e/ _5 |: u F! i o' ^% o
 float *p=a;( R7 r: B3 m( D4 }, M
 printf("Input number of terms:");. v. t: `# r; ~! U- t, S$ u( G
 scanf("%d",&n);5 t# O' u! e1 U3 Q2 `1 }" Q. \0 {
 printf("Input the %d coefficients from a0 to a%d:\n",n,n);
" {4 n& ~& e+ y, T for(i=0;i<=n;i++) scanf("%f",p++);5 O. j6 l& f8 h" }) S) d5 I
 printf("Input value of x:");( c1 k8 J: w/ k; L8 `
 scanf("%f",&x);
" y# ?0 Y2 @# p6 x p=a;xp=1;sum=0; //xp用于存放x的i次方8 _; y/ K, G- b' x8 d9 t
 for(i=0;i<=n;i++)3 h# o: ^5 A& G+ n6 y
 {: P" I$ Q3 q6 X! M1 Y
sum+=xp*(*p++);
! ~8 ^/ g* k7 ^+ z+ K xp*=x;
$ S, Q/ u0 m# S7 L. u }
9 v$ l( V9 o9 w( ^! C* a printf("Value is:%f",sum);
& \9 H/ s9 V: t1 O2 {& N}//polyvalue1 b& @+ g; P0 n7 `* U6 \0 F
< >

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