查看: 4973|回复: 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;. I$ r5 Z2 c# J2 _$ y
temp[k-1]=1; //初始化+ |& a. ?: `& a1 \
 for(i=k;i<=m;i++) //求出序列第k至第m个元素的值& b1 g7 v+ w/ \' U
 {
2 K3 k8 Y, k& D- v; N5 _ sum=0;) q, l& [0 k$ z) }8 `$ u! s2 b( D
 for(j=i-k;j<i;j++) sum+=temp[j];2 Z: ?6 x3 E2 g
 temp=sum;# X) D$ W# W! Z# P' K5 m0 {
}7 Z2 ?4 z: `6 b+ t! b% A; Q* v
f=temp[m];- @ K4 R2 y" K6 n/ J* c, {( b" b
 }
2 T* t) O" ^6 N. R return OK;
0 K2 `6 Q6 q7 [0 l3 Z6 V- |0 E; O}//fib& N! M I5 j$ X+ b
分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m). - `4 I' r2 J' W& B m3 M/ u, o, j
<>1.18 
2 k# x; c4 ]5 L \5 W<>typedef struct{5 y" s9 z l3 ]; @. I0 E9 S- d
 char *sport;
/ r& I- Q1 a7 |% P) g enum{male,female} gender;
) c+ B: a; Y1 u3 h5 b8 I char schoolname; //校名为'A','B','C','D'或'E'
" E9 E9 l W/ t" |! `0 @( _% y char *result;
1 R. }, z& G, g+ @3 w3 J( h& m int score;
' @1 L/ t) N3 V } resulttype; & I N9 \. d, }8 @% ?% G8 ]+ r( L
<>typedef struct{
, O# }/ z) e) \0 H1 a int malescore;
/ c Z- f9 S9 N p: `) ^ int femalescore;
4 w3 t% m3 B* i int totalscore;
8 ?! z3 B, [4 e* h8 T4 @ F# X* Q } scoretype; 
! [9 k" _/ i, W2 K6 d' U<>void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中
4 N0 |6 X5 q( ^7 K8 @9 y( A{, [$ y3 }+ @: j$ J) J+ L5 T
 scoretype score;
& ?) c" C' R( S! A/ M' J& M i=0;" }5 ^% |; ~ f k. ]0 i; V
 while(result.sport!=NULL); I+ E& _8 ^3 V. l9 b& N0 z
 {
1 u- [. U3 z9 T/ y switch(result.schoolname)5 l2 B: a3 n7 G+ W& @$ ^
{
* k7 h& c/ n) m case 'A':/ H: D+ M7 d+ `$ m# a) D, D
 score[ 0 ].totalscore+=result.score;+ P& X. D: P& C2 b9 f; w% B* y# C6 O
 if(result.gender==0) score[ 0 ].malescore+=result.score;$ f7 U$ M0 o/ s! C
 else score[ 0 ].femalescore+=result.score;. P% C5 |# t4 Y" z- y* e
 break;. P7 c, b: P4 V7 F
 case 'B':, U4 r& w; ~+ i- [- S( O" Z( S
 score.totalscore+=result.score; }. K" b# |! {" l
 if(result.gender==0) score.malescore+=result.score;6 x' h, E" z% a C: ^# u
 else score.femalescore+=result.score;1 \7 Y0 ]3 L+ a
 break;, m) q4 u* i# [ w. g# u2 L. P
 …… …… ……. w9 Z$ J# M6 |$ _# }7 q
 }4 h( w$ z- A5 m2 ]
i++；
0 p1 R) ?5 L0 _ }
 for(i=0;i<5;i++)
 E! t( z9 F, }; Q8 I {& ^( R- |1 J- l! E. C
printf("School %d:\n",i);
" P# c% L2 h: D# [( B printf("Total score of male:%d\n",score.malescore);
! j/ Q& |. X& L$ V2 \& D2 u% ^. } printf("Total score of female:%d\n",score.femalescore);
& A9 d9 t1 i7 ]! A/ g/ x. t0 ? printf("Total score of all:%d\n\n",score.totalscore);
2 a+ h4 p( ?, M1 U, A! X( X }
2 e9 ?+ X* R w}//summary ! s/ g; u1 v; t/ e
<>1.19 + _7 w6 U1 ^# ?! s% ]
<>Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint, t5 w. n2 p, }4 t2 A# k" P
{
) \/ E6 ^3 v& m7 K last=1;4 e5 K$ m, t' d7 k5 C. {
 for(i=1;i<=ARRSIZE;i++)4 G+ m* O; R( e5 e9 B
 {
/ |% l/ f: u/ J2 z! Q; C0 j a[i-1]=last*2*i;. e6 y* k$ T4 J) e. O! C1 Z8 C5 h6 f
if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;& }* ~1 S% t s; Z5 b2 s) D8 |
last=a[i-1];
9 L8 E- k9 [! Z! O1 M return OK;! E; J8 s. A8 y8 X9 F; f
 }8 M- x2 {4 Q8 K
}//algo119" O+ z/ x& e% \1 a
分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. 
' G. h5 m- @. G" Q8 i% G8 z9 m0 ?<>1.20 
& e8 n: d4 y$ S<>void polyvalue()
9 H5 {) o: G; \& o: j{. `/ Y, D3 n5 D$ k( M" Q1 o
 float ad;( I: Y0 P8 F/ U) m7 C3 r. Y
 float *p=a;& `% p9 ]- G* F/ x1 S% o) }6 k' T
 printf("Input number of terms:");& q5 u+ e9 R9 b3 l: i
 scanf("%d",&n);
# h( e* z. l8 a: L printf("Input the %d coefficients from a0 to a%d:\n",n,n);6 C- L/ z5 V5 S: K7 \
 for(i=0;i<=n;i++) scanf("%f",p++);/ j5 ~. F0 s1 F6 l" b
 printf("Input value of x:");
1 W2 F/ N$ Q9 h) h1 O! P scanf("%f",&x);+ o! s$ a, }+ v6 E
 p=a;xp=1;sum=0; //xp用于存放x的i次方
5 [; u( d" ^- r9 P for(i=0;i<=n;i++)
6 c! R# P" V0 a+ k8 T R {) h; g& g3 ]- \" F: H. ]
sum+=xp*(*p++);
* S9 g& q% f# r3 I' n5 z7 C xp*=x;4 [% v2 p$ i5 a) ^ L
 }
0 R2 E y+ v- o8 }- V5 K4 A' X printf("Value is:%f",sum);1 q- }$ R! c3 s& A1 x& L& Z
}//polyvalue
0 M( T u% n. e9 ]1 w' L< >

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