查看: 4989|回复: 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;7 w. @/ y3 E0 J B: K1 S
temp[k-1]=1; //初始化
# `" Y' S9 i4 J( M( S) u for(i=k;i<=m;i++) //求出序列第k至第m个元素的值0 i9 l, @% \3 Q9 D# S
 {
& P4 C9 P' M+ j/ P sum=0;4 d9 \# ^5 }4 G" }8 V0 |5 T9 c
 for(j=i-k;j<i;j++) sum+=temp[j];
+ ], z- v y8 t9 i" \+ ]4 D temp=sum;* x" p- U# m5 w1 ]4 h: c! Z1 ]/ j
}
f=temp[m];
7 a8 w ^, i$ X( `, ~ }
3 f! S8 I3 v3 u return OK;4 r: X+ n3 g+ z( O/ \' q8 n8 D! u
}//fib5 J3 Y7 a( }8 P! a$ ^
分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m). " I) W( W# T3 n/ g7 K
<>1.18 
1 N4 O( b9 O; b, w<>typedef struct{: g$ R* p* ]1 N; I
 char *sport;
: m5 L* g) c6 \ enum{male,female} gender;! G( v% V0 `) n5 \* \$ |- E: {
 char schoolname; //校名为'A','B','C','D'或'E'3 }+ Z" \/ n V" ]$ P! W( E1 X" z
 char *result;
+ t, G$ V$ T4 A/ C3 d! R int score;/ U, i( `6 G/ G1 E
 } resulttype; 
" |# U% J5 s" `, q [5 \<>typedef struct{6 Y) V8 h7 i+ }' K. J7 ~
 int malescore;
! P8 w3 @8 I" ?! D7 L: R& w int femalescore;( h4 u' r4 d6 c- N
 int totalscore; H" \" T4 `: z; ~
 } scoretype; 4 s$ S) R& c& ?6 f
<>void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中
# |2 {: q' p7 y{
+ r+ R- Q& a' K& ~. k! |, D scoretype score;
- {* s0 N; T3 }7 P i=0;
6 \8 ] Z$ ?; D8 j5 ^/ y) n, }7 V; t while(result.sport!=NULL)' c) w: a2 F' F0 l9 ~. _. U
 {
switch(result.schoolname)- a9 L7 _+ H+ t
{2 E$ }6 ?. k2 b, L* @" K
 case 'A':
" \7 b: r3 E( ~* m4 ]& ?* r8 [5 v score[ 0 ].totalscore+=result.score;
8 Q+ b; r) e3 c: l! B9 F- L% ~3 T( |# l if(result.gender==0) score[ 0 ].malescore+=result.score;9 I+ b. a1 x$ u* _0 @ c
 else score[ 0 ].femalescore+=result.score;7 |5 L2 L8 R6 U' R2 g r0 C
 break;
. M! }. p% w! R% v case 'B':
: a, V. V9 V, V' A: ?! ` score.totalscore+=result.score;/ z# ?$ V R5 C7 _( u$ Y% L
 if(result.gender==0) score.malescore+=result.score;, G) M; `+ M+ a7 t' O7 `! R
 else score.femalescore+=result.score;
2 J$ Y! `% Z6 y9 t3 l8 H& x; g4 b break;. [/ @0 G; E' K5 Z6 P
 …… …… ……
8 B! I3 m* H5 }) i% ~4 y {" P }
$ W. x+ U% v% ^ i++；
2 @% F9 b7 N5 s8 U3 g9 X" B( c0 D }: @; Q. Y9 p0 S
 for(i=0;i<5;i++)
; i+ q0 {' e) N" _, ] {
# C. `/ ?! C2 G. z* i5 y printf("School %d:\n",i);, a( e' X6 B4 ?: Z; a& |
printf("Total score of male:%d\n",score.malescore);
 u& C* r" S0 C. @ printf("Total score of female:%d\n",score.femalescore);
2 o" [% _; ~0 G printf("Total score of all:%d\n\n",score.totalscore);
- w$ P4 }% g6 U9 ?/ P }1 c: b+ l) n! x d( Y/ r
}//summary 
' f8 X P% O( K# {$ |<>1.19 
" N9 O% q1 L0 U3 L" W0 Y<>Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint
% T; m7 ]4 |2 W' }, A$ A* c{0 c& Z) u; x1 M" c( |" d F1 x
 last=1;
; u4 s3 R' r# u C: V for(i=1;i<=ARRSIZE;i++)
9 B8 I" t2 w* ^: n. _1 a4 I) A0 o {. _0 I) ~# W9 } h6 @
 a[i-1]=last*2*i;0 \# p. E3 U: D+ J4 w; h
if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;) Z: n$ n/ x/ P; k
last=a[i-1];* `! I- W2 H( I, D
return OK;8 Z5 r- i8 o o, y. ^/ p
 }
 v' a- z6 ?6 O- P3 L0 M, I}//algo119
: s! m! Q5 _, F) h7 W分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. 
- U" m H2 Q& Y& Q: Z4 h: f<>1.20 
8 L7 I" |* S( z# q* d9 g) z<>void polyvalue()' q, k" k( |3 D- Y/ R# S5 B# p
{* M1 V1 O- f, K) W& q% A
 float ad;
1 z7 }; t4 @! Y" M2 O2 |- a float *p=a;
) Z) {' ?- u+ A7 y; ?0 ^/ { printf("Input number of terms:");. p5 h% K. t. P; Q: m
 scanf("%d",&n);+ _$ f! O; t! p/ Y6 j2 H- C
 printf("Input the %d coefficients from a0 to a%d:\n",n,n);
+ @" J" ~: [: ~. Z for(i=0;i<=n;i++) scanf("%f",p++);
 {5 a0 Q( d+ U T. K printf("Input value of x:");* a: k5 p* z8 ~7 C- R
 scanf("%f",&x);
9 M3 Z/ O# Y+ R1 R+ S, c7 y2 q p=a;xp=1;sum=0; //xp用于存放x的i次方
, r$ I2 n/ v+ C for(i=0;i<=n;i++)
( S) z4 y4 ?# b9 p5 H" E {
) N' _1 r) s# |% M" \' v( {( |9 c) ` sum+=xp*(*p++);
4 ]2 b0 N* {' a/ K# ~8 i xp*=x;
: B# G3 Q/ E% S" e T1 x9 x }/ O1 S" x9 b; g, i
 printf("Value is:%f",sum);
5 G- i9 p" Y5 I7 M}//polyvalue o" r9 k" B# V/ A4 q, u# U2 {
< >

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