查看: 4936|回复: 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;
1 a/ Q% Q' H2 s T1 }% O temp[k-1]=1; //初始化
: \# P/ ^; X9 L0 M0 F& F0 b for(i=k;i<=m;i++) //求出序列第k至第m个元素的值
4 g, p$ l+ s# E5 Y$ U0 @$ F {
$ _! x& c6 W' \3 O sum=0;
3 }3 k! N8 U; O" w for(j=i-k;j<i;j++) sum+=temp[j];5 o! i/ v4 O, l( Q' d. |) j0 W
 temp=sum;$ N) X, `( ]$ N& A1 r& Y' v
}
$ d1 h: I3 x) S- Y, d f=temp[m];
0 n7 v9 m# Q5 b) Z" Y0 p: ]: r" l }
1 l e, M' y" F: u K return OK;
0 z9 K, U/ q4 V# i9 e7 B}//fib, U/ P" X @0 ~
分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m). ' s4 y! s4 [9 n! c+ p3 e+ V
<>1.18 
. ] ^. x/ Z4 i' x7 V9 d. [<>typedef struct{; c5 E* S0 w/ s
 char *sport;: G O L7 A! r! d. l; i! P
 enum{male,female} gender; c8 _. ?8 a' o9 ]
 char schoolname; //校名为'A','B','C','D'或'E': Z; q3 ]& G0 v* Q6 V
 char *result;$ x7 O6 x, [ w7 J `0 n0 t
 int score;4 ~4 ~9 ?7 `7 F7 i4 h
 } resulttype; 
( R+ w; R$ k) X. v1 O<>typedef struct{
$ q! \) Y- N5 D8 A4 w8 g1 W: E4 j int malescore;" \) \ \+ {! g& t4 v0 h6 [
 int femalescore;; x; V2 @/ u* ^9 _2 @
 int totalscore;6 U: C$ p+ O/ J u, ?
 } scoretype; & T' {" J% n7 H# ]- p
<>void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中) x1 u6 |2 c$ H1 R% U( Y
{) D) i3 ^" d% h* u: F2 G8 O
 scoretype score;
. U$ S2 w, D4 C i=0;/ `) d& x/ C/ Y8 h4 k: E
 while(result.sport!=NULL)
. u. D- u, ?; g y {+ j" p- k4 q; H( R3 t5 B
switch(result.schoolname)
& N) }5 l) Q" {0 s. G {
) v% X- n3 e* U! F0 A$ S [& |8 r case 'A':
0 @: s( y* m: p9 K score[ 0 ].totalscore+=result.score;
! K: g5 _+ K* r/ X if(result.gender==0) score[ 0 ].malescore+=result.score;
. g5 z! P5 N3 C/ w else score[ 0 ].femalescore+=result.score;
% {. [& {9 q& F break;6 E8 H0 m: V8 R7 g, Y
 case 'B':: l* k7 ]8 ?5 ]. R
 score.totalscore+=result.score;% s5 t# }+ j. t) T2 ~( q
 if(result.gender==0) score.malescore+=result.score;8 ^+ }5 L; R8 _' H3 i
 else score.femalescore+=result.score;
) }: Q, e' w0 a break;* F+ W( V7 P/ m6 |% n0 A
 …… …… ……
 S- a% A4 y; J/ `- Q- d }
0 h0 a5 P5 V/ x: q i++；( l+ r- I6 W" | i# K5 q+ C
 }. v+ l5 Q( p. H" p
 for(i=0;i<5;i++)
; n$ ?+ t+ v5 K$ B7 l {
# q7 r- W) O3 V9 \& c printf("School %d:\n",i);
$ B/ G8 n7 G1 c# A! R printf("Total score of male:%d\n",score.malescore);
) a+ N( E. D0 b. J2 E' `5 ~ printf("Total score of female:%d\n",score.femalescore);) {0 _. R: x9 P! ?. p( n; y
printf("Total score of all:%d\n\n",score.totalscore);
) i( Y+ S; Z% ` h. z }
- s/ G: Q" h5 n2 _" p5 u/ O- _9 K}//summary * K5 x5 D8 t6 p( N3 x8 M
<>1.19 
7 u7 C9 \8 w5 r9 _<>Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint
% i9 l% p7 H- L{2 o J% e1 e2 k2 {+ Q# O
 last=1;6 [% Q4 H+ t9 Q. T6 k. k
 for(i=1;i<=ARRSIZE;i++)( p' x6 V# o6 b6 ?" b
 { u* M8 ]" N# X+ ^2 L8 k
 a[i-1]=last*2*i;$ F v" W! m; A1 E# G
if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;
! \4 e- s% R2 i# K" K last=a[i-1];
% i% O' G3 N# ^9 C- t0 k return OK;
' t$ L* @8 _9 w: s' E2 o }
2 d! c* y: _ i& j: A2 r# f}//algo119" w* E( U Z/ a* Z
分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. ! Q. S4 N8 ]! r& G
<>1.20 k- h- q3 D5 w4 }
<>void polyvalue()- R( ^/ t8 w$ H* K0 A6 Z7 y! p0 P. @
{' a. {5 U }8 N" Q$ |- y
 float ad;. ~9 K9 p+ c$ t7 q, l. u$ v
 float *p=a;; \+ s @8 F0 s" a
 printf("Input number of terms:"); l7 r$ }2 h% I! w2 U; L+ C
 scanf("%d",&n);$ w2 p- [9 t" D; v- o7 r
 printf("Input the %d coefficients from a0 to a%d:\n",n,n);1 ?8 f2 q2 ]" X4 N) L1 k
 for(i=0;i<=n;i++) scanf("%f",p++);% [ F$ m# t! t6 N: q7 C, p
 printf("Input value of x:");
2 | c$ x* w9 X1 J0 Z# t! Z* ~ scanf("%f",&x);+ H& S8 p9 r) y
 p=a;xp=1;sum=0; //xp用于存放x的i次方. l3 h$ @, O, R
 for(i=0;i<=n;i++)
% t) V: V! ?0 q( ]6 e' M# j, E {7 R8 X' S% B$ z1 N) h X% Y
sum+=xp*(*p++);; M9 B0 x% L$ S) g) K
xp*=x;* V" ?6 I; G6 M. c" p4 R
 }, `0 ^& h, ~$ B7 n5 W0 n- n
 printf("Value is:%f",sum);
; |2 ?' M+ y* \! I( S}//polyvalue
- k: w% Y' O3 O< >

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