查看: 5002|回复: 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;+ N" t3 e( W: O& P, x% j
temp[k-1]=1; //初始化4 C- k8 ]! L. \# Q) T
 for(i=k;i<=m;i++) //求出序列第k至第m个元素的值5 s0 G1 p. Y$ P# k- G
 {
% L$ }% Z' D* R8 U sum=0;$ W5 a5 p6 l. ?4 M2 l6 a
 for(j=i-k;j<i;j++) sum+=temp[j];
4 m) n4 B. s; J4 @' v! G0 F- T" k temp=sum;8 L4 K& n- g S
}9 t$ V3 V4 g, @0 x: g
f=temp[m];
0 s, w$ Z' ^' U) V2 k- W# x }, P7 l& ]# K7 {7 a) k8 [" f
 return OK;
1 Z: y5 t" Q" r) k! w}//fib
* e' S; a7 }" `, g0 \$ t分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m). , ]" T- N4 E$ u2 u* \# N
<>1.18 
8 l; ^6 z4 \( J$ }/ g<>typedef struct{3 _1 u- [* u+ x3 I) m5 I. R% G% Q d
 char *sport;
8 t. g7 S. k5 p3 U7 ^ enum{male,female} gender;
. E/ x- G' k8 o! J" L# E, ] char schoolname; //校名为'A','B','C','D'或'E'0 D j. f4 J9 k8 `: ~
 char *result;
# Z$ u4 O7 f" @$ d' h% ?+ C int score;
 h8 h- q9 d: a" q; H j; } } resulttype; 6 W8 B) t' C3 @4 `, H5 n! F _( @
<>typedef struct{) Y0 J+ ?5 [* d8 W" n
 int malescore;
5 M) T0 F1 D I$ ~' D; \ int femalescore;1 s7 j' L2 Q; r B. X; F! `3 ]1 b p. t
 int totalscore;
+ i. e/ m9 F) L1 c B } scoretype; 6 a, X: f# D4 v9 D1 _' p" r; |
<>void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中% U* ~1 N0 g& g4 ?. P* A) d
{
( ]2 `6 `2 R4 K- M) i# M9 O' I scoretype score;3 D9 }) [$ j0 f8 t- P4 S% `
 i=0;/ f9 m# S% Z9 ~" f1 Y k
 while(result.sport!=NULL)
8 M4 _/ @# }% ~1 O! q) s {
* w: \' w8 f! @/ g4 y0 e3 U switch(result.schoolname)
: H& Q! {/ t; K* K/ M {
; I' w) }+ d$ Z8 k* K5 K3 H' u case 'A':
+ I" d8 a, V/ c; o; x3 E score[ 0 ].totalscore+=result.score;
9 n+ \' S2 }1 ^* p" Z if(result.gender==0) score[ 0 ].malescore+=result.score;
7 q/ \' a- u8 E: i1 Y" B! m else score[ 0 ].femalescore+=result.score;
7 e1 m3 {3 E& V0 ^4 c$ M- [ break;
6 |0 m: n4 p, W+ F& j' y case 'B':
+ y, d! \3 E& J" U$ Y score.totalscore+=result.score;
! n* r0 Y: s! O8 j- o1 t if(result.gender==0) score.malescore+=result.score;3 }& J; w& T+ J" z4 f# \ z/ J' v
 else score.femalescore+=result.score;& Z! }4 `, @$ A0 m2 ] M7 V7 l
 break;
" l8 i4 F& o" t' c- K. ^ …… …… ……
$ d- N+ r" P$ }& ^: g( a- C }: s; ]2 x. [$ ^+ d3 d& b/ l- _
i++；
! A: k5 H3 y9 ^0 F7 b6 L }2 }1 _: m& r7 e/ G G' a* W
 for(i=0;i<5;i++)
2 O, B7 f. m% p! k {9 y7 H4 Y& \* H' Q+ {
printf("School %d:\n",i);3 r& f9 ?1 o5 i
printf("Total score of male:%d\n",score.malescore);- v5 l( m+ R/ T% f- d2 ]+ D( e
printf("Total score of female:%d\n",score.femalescore);, b8 y" W0 X' N
printf("Total score of all:%d\n\n",score.totalscore);7 A& z: [& k k9 I3 l) N/ f4 b
 }( @8 v% M# G( l7 g
}//summary & G% K) ~& S" Q6 {( \3 ]
<>1.19 7 @ ?! ~3 K3 }. c, t" K2 r
<>Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint
/ z# z4 b3 ?" C% p# H- ^* x{2 b8 }( l% H- c' G4 h
 last=1;
: C E1 I& P) |. P& L for(i=1;i<=ARRSIZE;i++) C6 U4 t9 q$ t3 m& D8 P6 S
 {- {, H- d0 r& t9 s9 X0 F
 a[i-1]=last*2*i;# D$ I' h' S8 _. V$ M+ k
if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;
4 g- n) k2 N1 H last=a[i-1];, ^# j9 ]3 u9 H! b x- t) t# F% r# ~
return OK;
' V+ \7 K7 Q" ?5 I }
; I4 J% q* L" i G' h, W: n/ l# j}//algo119
# c% G+ Y/ B5 G分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. 
$ n" \0 [3 G/ L2 b7 T6 {4 \<>1.20 1 E$ ~( D& \- q4 T7 B- t
<>void polyvalue(); R G# v5 j* r1 ~) N- B8 Q6 V
{2 R" W" D9 ], p
 float ad;
, J! g# A4 g4 r0 e+ N, w# h float *p=a;1 ?' F. H' a7 h
 printf("Input number of terms:");9 \3 r6 g# Q: v. z1 X# [
 scanf("%d",&n);, t9 v; O. [8 x# _: A. | U& }
 printf("Input the %d coefficients from a0 to a%d:\n",n,n);
0 M+ E9 y" A& N. K# k0 p3 y. r for(i=0;i<=n;i++) scanf("%f",p++);" I$ f3 T5 {( ]6 P3 L
 printf("Input value of x:");' [1 ~5 i- |% p8 S
 scanf("%f",&x);
, i0 [, e! u6 d7 I2 N( \5 ]: _6 g p=a;xp=1;sum=0; //xp用于存放x的i次方- C8 U3 u0 U9 y- X9 a) ?1 M \/ u. L: n
 for(i=0;i<=n;i++)
/ W2 S) i5 X ~" J" ?& H. }, | {# E2 X6 j3 z4 ?+ a
sum+=xp*(*p++);
6 n/ E+ o8 @- s" R3 U: H xp*=x;
 Q- T7 Z6 y& M2 d$ w }
+ @- H. ~3 _" w" K. _) A0 p printf("Value is:%f",sum);2 i! z" W. Y0 x! V4 {6 i3 M9 T
}//polyvalue
3 O5 z* N0 `4 u/ s) ~/ j7 `- J5 b< >

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