查看: 4988|回复: 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;& O h' B) f2 o, Q) y* X4 r- G
temp[k-1]=1; //初始化 [( L, z6 ~$ q1 _6 U, }
 for(i=k;i<=m;i++) //求出序列第k至第m个元素的值/ ~* b8 r2 ?9 F, i& m6 g
 {- g# D; |& B! }
 sum=0;8 f I) j- j1 l( O( @, r) x! `' Q! f
 for(j=i-k;j<i;j++) sum+=temp[j];
- z- o u5 b! b% ]$ a$ T% u temp=sum;
+ ^4 x1 a7 }! o; V7 C }
7 i- |2 e4 Q- ^. s7 a* ]$ X f=temp[m];5 ^$ X9 e, P. R$ E) Y9 F
 }: v" p" p5 `/ d% z
 return OK;* l$ U) l( D% M8 l& h; V. { Q! F
}//fib
4 d q4 I3 H! I1 X$ B$ ^* R分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m). 
; ~* [9 y- {. l$ c; E( k<>1.18 
) x( W, Z& Q/ m7 d<>typedef struct{
% x7 `* x! N! e$ c char *sport;
$ s0 L% O1 T; D enum{male,female} gender;7 p; J3 `0 ]5 e7 ~* p4 L
 char schoolname; //校名为'A','B','C','D'或'E'
4 J% Z7 H" U4 o" [" ?4 g char *result;
! U8 D& `6 o X' O1 R& f int score;
- N$ s& Z) B) u; N: _$ X } resulttype; 
) K: X; Q8 X* m, k' w+ c7 n! s<>typedef struct{2 J3 ]6 y) G. A! G% O3 h
 int malescore;
 int femalescore;
" q; t/ F; R) U1 q0 q" D/ C int totalscore;, v% f' G, o) n) P4 K
 } scoretype; 6 o) A/ k( Q/ ]1 z
<>void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中9 I3 h* ?4 b+ d: l+ A( H* c
{0 E2 |; o: [3 e0 Z1 L
 scoretype score;/ X# m* z7 D$ }- `
 i=0;
, ~. T3 Z2 e) U! ^6 d. F while(result.sport!=NULL)
: q# r( ~5 j7 f- y, { {
) O* x& W( B8 v0 i% S switch(result.schoolname)8 t1 E/ w; y& x( j. r: |7 s
{0 S L9 @7 D0 L. o# t9 P1 \8 N
 case 'A':! o: ^+ f- t* [9 H! p. V8 v% v* I, K
 score[ 0 ].totalscore+=result.score;. y/ k. W8 a7 {, }! j( ~+ J# t O* @
 if(result.gender==0) score[ 0 ].malescore+=result.score;- V. h# o- ^- q2 r
 else score[ 0 ].femalescore+=result.score;3 N; v9 }$ v5 T& Q6 ^
 break;
+ a6 _ P0 ^9 x, d. U case 'B':
5 _/ q6 o* y9 I5 r score.totalscore+=result.score;8 s# g+ m' C0 d. T% R# z1 M
 if(result.gender==0) score.malescore+=result.score;& m" s# v6 E1 S0 O
 else score.femalescore+=result.score;+ o c: ~1 E$ p: ?
 break;% {3 P v1 o& E9 p, Z( a
 …… …… ……
+ y: N* K5 ?4 }: x& k }& m+ D2 H; ^ y; U
i++； r4 E e; C2 L6 E& i
 }
 for(i=0;i<5;i++)( e. A$ d' Q e: U5 B, q2 _# t" @
 {
4 i6 S4 P5 h: Q4 @& G printf("School %d:\n",i); E& M- W; V2 b4 j4 F, Y
printf("Total score of male:%d\n",score.malescore);: e" D5 s+ [! V8 G7 z
printf("Total score of female:%d\n",score.femalescore);
7 B+ x; {" |) ` printf("Total score of all:%d\n\n",score.totalscore);
$ y1 m, W% x' A S3 f1 n( \* \0 f }' y0 X3 r& P$ ?
}//summary 4 g" D5 P9 P4 E6 g8 C9 _! e! B
<>1.19 0 f0 `& U8 Q" w' A6 f7 ?
<>Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint
' C: q, q5 i1 r( V" Y3 G8 x{8 T- m% M" n9 I+ W/ f. w/ j2 n
 last=1;
( R9 U6 ]' F2 H for(i=1;i<=ARRSIZE;i++)
: V. Q. r3 W0 H: F {
0 k+ i: C4 Y; b, b7 l# N, n8 t2 p a[i-1]=last*2*i;
+ W, J: F+ `0 q+ P+ J* V4 r" S if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;" U* s& }( {: I
last=a[i-1];
8 t; g j. u$ L; w return OK;/ `' O* y8 c9 o% r. n
 }
6 w! y: E- f- { m}//algo1198 O* \8 u- h& Z1 _2 p
分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. $ L; _4 m' M2 T' Y
<>1.20 + d& \& m6 [$ t0 y2 f
<>void polyvalue()5 H1 W9 C5 @4 G- ?
{7 j `' W# c$ Q" E; ]" Q5 R) v* }: ?
 float ad;. t- |# }6 P9 a: I: v+ p$ ~
 float *p=a;
0 ]5 v, a2 d- S6 n! ^ printf("Input number of terms:");/ e4 Q2 X3 o( B8 I
 scanf("%d",&n);
7 p5 M- y$ d/ R4 W1 L printf("Input the %d coefficients from a0 to a%d:\n",n,n);) ^1 F! P. N; t& ]+ _1 l7 ~7 P
 for(i=0;i<=n;i++) scanf("%f",p++);7 w5 `6 y' @; v
 printf("Input value of x:");1 b5 W4 n2 }8 |% X* t; S# k# N2 j
 scanf("%f",&x);3 G% |- s7 }3 C) O: {+ t0 w
 p=a;xp=1;sum=0; //xp用于存放x的i次方/ L" w4 _* \% N3 A+ B; H
 for(i=0;i<=n;i++)% o0 w2 y4 |9 C( B- J7 y; i7 P
 {
, U! D' s8 }- W( ^- p6 d sum+=xp*(*p++);
; O+ E' M+ w) |- ~; @2 \9 N xp*=x;3 m- D' g" ]1 e. k! [7 T6 g
 }- u) b. i/ r: k# o* L) _- `. b! B
 printf("Value is:%f",sum);
3 H4 f" i+ r/ M- ]5 E% R v}//polyvalue* S) L+ \% H. [5 Z% m
< >

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