查看: 4773|回复: 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;* d, z ]) l& ]
temp[k-1]=1; //初始化6 u9 s- X* d7 r% s2 `# v
 for(i=k;i<=m;i++) //求出序列第k至第m个元素的值9 D, b/ m" |6 Z3 B
 {' _+ a I2 d2 T
 sum=0;
; ]7 n; E7 u* p. m5 H# h# R& D# |5 c for(j=i-k;j<i;j++) sum+=temp[j];/ y+ K# j k' J2 I M& ?
 temp=sum;& n6 a8 T% o/ o
}# `( q M* j/ v
f=temp[m];" Y$ ]7 U6 a m* O+ f a8 G( Y
 }
: j6 L2 S" s( q. K2 B1 t return OK;- a7 o0 o& c% }
}//fib, W$ l9 d0 l) }3 }2 N; ]4 o$ _
分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m). ( a# `* w6 l* c3 V7 H3 l
<>1.18 
- K% [; {! h9 L+ I: _ G5 ]8 f3 K<>typedef struct{3 N6 |$ j0 u+ j3 m, {
 char *sport;5 M. v& ]8 y( W3 I4 L
 enum{male,female} gender;
* A8 r. n+ Y! Z, @% {; H char schoolname; //校名为'A','B','C','D'或'E'9 A3 I P" y( t: ^ g0 |+ m/ p
 char *result;3 G$ ~' B% f' Q1 O& z. @/ j
 int score;1 H2 D, H% n" R5 w# C
 } resulttype; 
3 q: H" A! _4 t* j<>typedef struct{
9 W) ~+ F2 b8 w) Q0 `* Q. e% P. M int malescore;
1 f/ `5 D, A- X8 d. U int femalescore;, l% ~& A' M, D: r, \2 w) ^
 int totalscore;2 q" ]6 `' h) j. b7 r4 A) `
 } scoretype; , K* J5 D% m/ w/ x3 R7 L. ~
<>void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中
2 c0 k0 v# [9 U8 Q5 w1 I# G& ^7 O{: [ {. r0 k* F& q
 scoretype score;: }2 U0 x9 U+ n$ A4 Q+ c7 t
 i=0;- C4 Y/ }; G2 K: s7 V
 while(result.sport!=NULL)
7 A2 [4 p" R/ U% J" B' E/ _7 p {
% ?4 B7 A. `: V" W" ?8 B7 O switch(result.schoolname)
, L6 H1 Q. {2 g( X& A& e5 d- l {
8 |0 a' K2 @3 n1 P case 'A':
, o1 f( X# n6 J0 P% l score[ 0 ].totalscore+=result.score;( V$ ^8 S* H7 p' u9 @( K
 if(result.gender==0) score[ 0 ].malescore+=result.score;
% A' w. c- k$ a& z else score[ 0 ].femalescore+=result.score;$ l! j, P M/ B9 e) t3 |+ G
 break;* s/ Z. o9 R& T" v9 h
 case 'B':
! d1 N' I! F& r( ? L& K score.totalscore+=result.score;( Q3 R4 o3 y8 ~/ D( }
 if(result.gender==0) score.malescore+=result.score;
2 \' Z2 |9 o, c9 m else score.femalescore+=result.score;
* ^, ~5 l2 n: z" a' d3 s) u break;
( I6 I( K, @) S! Y& y& e# T L! a …… …… ……
, `# |# d6 J" N }' v# [2 g! H" [* D6 q
i++；
5 [% P# k6 y+ p$ X4 I" a6 m. j }: q6 X; H& a) |1 |! x$ b
 for(i=0;i<5;i++)
5 F3 a# Q0 p5 g, s# t+ m {# f5 T) k/ g' F" f+ @
printf("School %d:\n",i);
) H, p3 D, o) ^2 u/ G6 E printf("Total score of male:%d\n",score.malescore);
6 y9 e: E% \: W* ^ printf("Total score of female:%d\n",score.femalescore);6 u2 t0 n( ^% d5 k3 Q' B
printf("Total score of all:%d\n\n",score.totalscore);: t5 |, ?, }$ e) @1 c* z+ b
 }1 c O) ]- F4 T! R3 w) f. z
}//summary 
: F- u1 B1 q$ V& T# A. k<>1.19 + s) R8 A) r, ~. V
<>Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint
5 p |1 m0 Z6 R{- B W3 D& M l* S3 ]6 V0 S4 }7 F0 \
 last=1;
3 K# O, A2 i8 C0 j$ u- i for(i=1;i<=ARRSIZE;i++)
 D7 H# E/ n0 y# `5 X h {
: V; H' y2 x2 u/ c/ Y/ z+ z) ` X4 q a[i-1]=last*2*i;
- t/ K+ @7 c9 ?5 r% B* t- h if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;
3 K T0 A. a9 V# w6 _! ^ last=a[i-1];
: ^5 B- g1 M2 M0 s: G) m5 t; h& }; P return OK;. i$ H9 b" n. \4 r. U
 }
4 p' R% d4 M+ h8 r m, O}//algo119
* P9 c$ v0 x. }; U- \. |$ _分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. ) M' ^7 O0 B; U l% x
<>1.20 - ?3 s- o! E9 O m3 v8 ]% Y: c4 z% }
<>void polyvalue()
* w% Q9 H$ {* [$ b+ g0 m{7 K1 g) P4 ~1 u, R! K6 c- |8 k
 float ad;
5 W3 u/ q5 V. e$ v" D1 i float *p=a;
; J: r( |. |! `* _ printf("Input number of terms:");
0 h! x, Q& B' V scanf("%d",&n);5 I0 ?% y5 F4 Z7 n4 e e3 \
 printf("Input the %d coefficients from a0 to a%d:\n",n,n);% u7 Q" f% `5 u7 q' P+ U" F% _3 W
 for(i=0;i<=n;i++) scanf("%f",p++);
4 ]! _! J" X$ D7 Z printf("Input value of x:");
- d7 r4 ]- N; X W6 N8 ^7 I scanf("%f",&x);1 x" R' n% G& K: l. w
 p=a;xp=1;sum=0; //xp用于存放x的i次方, h7 @3 A9 A% ]7 K* P# E* W
 for(i=0;i<=n;i++)
3 D7 i) V6 E; m5 T: N, n) Y {
% r- }2 W! e' L2 z4 J0 _- f sum+=xp*(*p++);4 R; W' n& Z5 T# v
xp*=x;
* x6 p- q; G5 T! z5 D) R" Z% J* y }
% T: H- h* U. E1 u printf("Value is:%f",sum);
5 B* L0 U5 e! v! W- Z) l' g3 Y% d}//polyvalue: a: W+ c4 t, T! B8 P& C
< >

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