查看: 4937|回复: 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;' p$ ^& S3 Y) v0 V
temp[k-1]=1; //初始化5 U2 ], \- N6 c- m
 for(i=k;i<=m;i++) //求出序列第k至第m个元素的值2 F8 _& |2 O! t$ H! o
 {# t" i+ o% W! }! |2 z: N# s6 \( _
 sum=0;
, d, @& m& F9 ] for(j=i-k;j<i;j++) sum+=temp[j];
- N. k6 D @5 o0 V) I3 [ temp=sum;: b& u0 G: C+ k3 P
}7 x7 A. O3 ?4 Y3 x. h
f=temp[m];
0 G0 ^ r$ D# O: p# Z }4 \2 ?6 r5 m, M* K i
 return OK;
5 `6 I! ?% g4 k; f}//fib/ J0 |" G7 s' u+ H
分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m). 
! h& J7 ]# w* J Y$ O. O5 @<>1.18 ! q: A5 P b6 X! p
<>typedef struct{
, x9 Q) x1 k/ o8 A4 g: y5 N+ A char *sport;
/ |$ M/ [! {" o: ?8 z$ W enum{male,female} gender;
3 L3 O, g1 Q' q5 Y) H# K char schoolname; //校名为'A','B','C','D'或'E'
# ?# B6 L( X. I; [; b char *result;
" h. o: V- l2 _' @0 s0 d! V2 b1 M/ Z int score;
% O; ^8 t% T; {& }! L& @* s. r' W } resulttype; 
$ A# U' M9 U u/ Q( g6 S: X<>typedef struct{" O) D& E3 \4 |- f$ ]0 X
 int malescore;
4 o# e- h5 K2 w: V- f$ s int femalescore;8 {1 \' M$ U" W- U6 |5 c
 int totalscore;7 w2 I: S* w2 \7 \3 w
 } scoretype; 
, c3 Y6 X8 i4 E0 R<>void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中" w1 w) v) t) T& R# j9 f
{
) Q7 U, _3 { f0 b9 G, a! N scoretype score;9 ]4 E! r: Z8 X" i, R2 g+ H
 i=0;: f! r) n& W; w# F; M9 A
 while(result.sport!=NULL)5 [' V9 a# _; B$ U
 {
& o1 }0 w" T4 `9 O1 L, ]/ ~ switch(result.schoolname)
% w; E) B" P9 n# h' X O8 v* S2 V {% e, l3 V5 }0 M- Z
 case 'A':
7 \' X6 D1 K! G3 t/ |8 v/ v& n score[ 0 ].totalscore+=result.score;1 z: x- O- _, }; a1 _
 if(result.gender==0) score[ 0 ].malescore+=result.score;! K1 l2 L; M$ m+ a! }' \# A
 else score[ 0 ].femalescore+=result.score;
' O5 \) {" Y6 m. }; M break;* ]! c$ c: B t, l$ T) D* b& x5 J
 case 'B':
* q6 I# g! P. h% H6 g# A score.totalscore+=result.score;8 a1 [, g4 B5 F. c& p6 X1 k, h
 if(result.gender==0) score.malescore+=result.score;
% g) J; y' [' l; g5 O7 X else score.femalescore+=result.score;
7 y4 A0 h1 k' [2 G break;
6 Y& J1 T* a) V. U! { L …… …… ……/ q a3 c9 W! M; M
 }
8 P: m- X1 f* v4 ^ i++；
 Z$ V' t! t! [( f }0 @4 x: l1 o3 [# r% s9 m( s2 t
 for(i=0;i<5;i++). @' x: e5 t( x
 {
5 P9 N$ [1 R: e printf("School %d:\n",i);( M6 }0 M' p2 k6 o' D" c
printf("Total score of male:%d\n",score.malescore);
/ \9 C7 \+ b9 J* t% S printf("Total score of female:%d\n",score.femalescore);
' c. ]' s* Q; ^$ \ printf("Total score of all:%d\n\n",score.totalscore);
7 s# ^' }1 Z6 e$ e$ f8 y. B4 ` }8 x& x- e2 [4 r. M
}//summary 
% I, l+ O- I% y- {9 }! v: K6 J' u% a<>1.19 6 b7 x4 X% V1 N
<>Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint
7 k, W% @! e. N# {1 P5 v{
5 |% R6 l, c1 l) u6 y last=1;
# z- v) j5 i- b5 G ]) Y for(i=1;i<=ARRSIZE;i++)
' ]% l8 Z/ r) {2 R+ x {( I o; A/ B3 q4 v( y6 S% P
 a[i-1]=last*2*i;
 e6 `& i0 e, g% W0 a6 ~) k0 B if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;4 _/ L5 ?4 z" p3 S& x( z( B6 U& a
last=a[i-1];3 S9 A: r4 f& U, h
return OK;
 x" o6 r' P) o/ m }
2 I0 a, d) c! L# m$ A/ @}//algo119
$ |# r7 N- h+ f: o9 n+ G分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. * @1 S$ c4 w8 }2 P: R
<>1.20 $ h$ m) t8 v/ h' |
<>void polyvalue()
. X+ N# K/ h$ ^% U7 i$ Y- ?{3 ^" J( x: l: B+ v: `
 float ad;
. q& K( D; [3 p1 ?: I float *p=a;
" j3 h8 V- o0 H- e5 F6 z printf("Input number of terms:");7 b: b+ h, B( W' x7 a. l8 S! `$ M
 scanf("%d",&n);5 o- _( d$ u& O8 n: \4 I
 printf("Input the %d coefficients from a0 to a%d:\n",n,n);8 r# G* S* y5 O. ]
 for(i=0;i<=n;i++) scanf("%f",p++);( @& s$ `$ U; o u5 R& R
 printf("Input value of x:");8 X0 t( `6 z5 U$ R
 scanf("%f",&x);
& s) N- N1 U6 S) e& Z0 P! b' q3 u p=a;xp=1;sum=0; //xp用于存放x的i次方
" |& Q; y0 w1 p2 b* ]2 m% a for(i=0;i<=n;i++)% S2 S6 u# T0 v" e4 [# X, _
 {
8 X; R8 H. Z" a- q6 L5 V5 x sum+=xp*(*p++);
9 e, \4 b/ u# a0 Z& d+ V7 l& Q& X xp*=x;
3 L5 F3 y! z- }) s H6 ] }# _5 d! ?3 |5 L( E
 printf("Value is:%f",sum);# ^5 P* i/ ?& Y. l) |" @/ {% j
}//polyvalue
; @# s; A" Q0 |, r< >

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