查看: 5003|回复: 3

《数据结构(c语言版)习题集》算法设计解决方案

字体大小: 正常放大

66 主题	1 听众	648 积分

VisaSky.com 加拿大移民留学网

TA的每日心情

	开心 2012-6-9 03:29

签到天数: 1 天

[LV.1]初来乍到

电梯直达

1^#

发表于 2004-11-28 18:02 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

<

>说明: 
<

>1. 本文是对严蔚敏《数据结构(c语言版)习题集》一书中所有算法设计题目的解决方案
<

>2. 本解答中的所有算法均采用类c语言描述,设计原则为面向交流、面向阅读,作者不保证程序能够上机正常运行(这种保证实际上也没有任何意义);
<

>3. 本解答原则上只给出源代码以及必要的注释,对于一些难度较高或思路特殊的题目将给出简要的分析说明,对于作者无法解决的题目将给出必要的讨论.目前尚未解决的题目有: 5.20, 10.40;
<

>4. 请读者在自己已经解决了某个题目或进行了充分的思考之后,再参考本解答,以保证复习效果;
<

>5. 由于作者水平所限,本解答中一定存在不少这样或者那样的错误和不足,希望读者们在阅读中多动脑、勤思考,争取发现和纠正这些错误,写出更好的算法来.
<

>第一章 绪论 
<

>1.16 
<

>void print_descending(int x,int y,int z)//按从大到小顺序输出三个数
{
 scanf("%d,%d,%d",&x,&y,&z);
 if(x<y) x<->y; //<->为表示交换的双目运算符,以下同
 if(y<z) y<->z;
 if(x<y) x<->y; //冒泡排序
 printf("%d %d %d",x,y,z);
}//print_descending 
<

>1.17 
<

>Status fib(int k,int m,int &f)//求k阶斐波那契序列的第m项的值f
{
 int tempd;
 if(k<2||m<0) return ERROR;
 if(m<k-1) f=0;
 else if (m==k-1) f=1;
 else
 {
for(i=0;i<=k-2;i++) temp=0;7 e5 d1 r8 N2 i) k3 F+ b' h
temp[k-1]=1; //初始化
" l: g( M% L& V# F+ R. C) T for(i=k;i<=m;i++) //求出序列第k至第m个元素的值/ n9 ?3 m; ], h3 x2 m- o
 {: W5 z+ d/ `" K; x8 u L* m
 sum=0;
+ s) N9 z" p4 U+ {3 Q) ~. ~, g' O; w for(j=i-k;j<i;j++) sum+=temp[j];3 H/ U( Y9 x# \9 g# ^
 temp=sum;
8 e$ y$ p8 |% _; g u. n }
$ I) P9 X$ Q. _8 ~# I f=temp[m];. f$ H0 Z C" H- P
 }6 Q6 h* N) ?. e0 m
 return OK;2 T' g1 J8 _) s5 M9 a) h
}//fib
7 x; K |- z4 a" ^8 W" D' c% a9 d分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m). 4 |; }$ s5 p0 h" a/ W
<>1.18 ! M) a. Y+ K* F3 K% z1 V4 ]
<>typedef struct{5 \1 a5 v+ T9 l+ h" z
 char *sport;
, v! I+ |9 Z; o: o% M; X8 f% C enum{male,female} gender;
: ~" m5 v# G2 x char schoolname; //校名为'A','B','C','D'或'E'8 K9 |0 j9 [9 h
 char *result;, ]- d t# x: S
 int score;
: H* m' o5 N. H# B } resulttype; 7 Y/ j9 ]3 y; j6 C
<>typedef struct{2 N9 L8 D6 Z$ M U' [
 int malescore;: X# r. b, n2 u! }3 X/ h1 U
 int femalescore;+ w' w; M7 X* b$ R
 int totalscore;
# e1 N# [" `/ }% r6 B } scoretype; 3 @3 A" n) G+ x0 ~. K# d$ Z
<>void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中
" Y# O) t2 ~) C# D8 o. L9 U{
* f7 V2 w) X/ M1 p scoretype score;) O, q; f! Q0 g# O+ U
 i=0;
% E1 D% c6 ?, _6 u while(result.sport!=NULL)
% V& B' Q2 s8 h6 x l2 [- i$ B {+ |8 p1 C9 c5 |2 e
switch(result.schoolname)
& A8 L) \ t7 A {
9 J+ ]; T, n. j6 Y- ^$ N2 K9 G0 s1 [ case 'A':
9 h r8 \& E$ E; r6 M* Z score[ 0 ].totalscore+=result.score;9 d9 O& ~! F1 C) k$ e
 if(result.gender==0) score[ 0 ].malescore+=result.score;! P* ], c) m( F: r6 ?
 else score[ 0 ].femalescore+=result.score;
" ~4 q/ s$ Q. P) O3 Q7 H break;& s* r5 f: n8 D( s; _9 u
 case 'B':
# `- m, h" E3 h score.totalscore+=result.score;
) s) m( \* O% F) J. E, q if(result.gender==0) score.malescore+=result.score;
. W: o& E' Y5 i else score.femalescore+=result.score;4 Y3 |' P; q& k8 e$ S* q
 break;: i( t9 {& X/ o& B8 _% P, H9 H
 …… …… ……
! s4 }! c, u- y7 Q( W }8 u' J/ N$ h8 A
i++；
 q/ e& P* f) s& o+ X }
1 I: ?- h7 [+ ?1 L9 c) _2 O% z for(i=0;i<5;i++)* E) c" q, y; s- \# y* Y
 {: ~* ]/ S9 S1 u) \
printf("School %d:\n",i);3 V0 T* @8 o) c$ M0 T. T
printf("Total score of male:%d\n",score.malescore);
( E+ Z. P9 C I0 n( F1 i: K7 j% d1 g printf("Total score of female:%d\n",score.femalescore);
# d6 o) @( |1 I8 ] i9 Y5 [ printf("Total score of all:%d\n\n",score.totalscore);! Y& X E# |- K
 } K5 f( N, J% z% i8 ?
}//summary - M0 |! p" ?7 b% y
<>1.19 
3 y( F) D# Z% T# i$ v! y<>Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint2 z( a2 u& h0 B4 |6 D1 O% `+ V2 k
{# A/ o! d$ i( G, ?. @
 last=1;
5 s6 U5 ~( a3 U. J# ` for(i=1;i<=ARRSIZE;i++)
. E' h+ g, `; J0 P {" W7 o+ L& m2 b! n7 r+ { y- w; t
 a[i-1]=last*2*i;! w3 G/ y0 N" [, v# ?1 X4 n- D( m
if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;
 W5 y ?/ k2 W; M! P last=a[i-1];6 f! {; l8 a% r- }" B
return OK;. n2 }" w! f. y+ l+ Q
 }2 s/ ]4 S0 c4 }7 W7 v" o
}//algo119
0 M# l9 S6 T& I分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. 7 O; t) Q% h" H+ o& ]0 c
<>1.20 6 P" G8 E5 x/ r* @$ h
<>void polyvalue()
3 I) Q, B4 F% c& [, i7 A. q{
- I3 Y5 V5 X* p1 Z* b float ad;
- r6 N& l2 H7 O2 A2 Y- ~, W float *p=a;
$ p5 Z) E0 L1 H" ~& e1 \' [* w printf("Input number of terms:");! L6 f1 ~& S$ ~; f
 scanf("%d",&n);* \5 x9 q, {3 y0 s
 printf("Input the %d coefficients from a0 to a%d:\n",n,n);, _2 d% r" U; T# q
 for(i=0;i<=n;i++) scanf("%f",p++);
0 Y: k6 B4 S2 k5 V: ]; L; W& Y! A printf("Input value of x:");
 _$ }6 L. d* a7 J' I9 m scanf("%f",&x);2 w, R. m3 v- O1 V* V* P' C
 p=a;xp=1;sum=0; //xp用于存放x的i次方
) Z' s2 A, o' q) w for(i=0;i<=n;i++)9 w: A! ?+ ~6 j# \, G
 {* O# K, ]/ l) q/ ~- @; S8 s4 p
sum+=xp*(*p++);4 Q& E1 R) A+ @9 r2 H- f& k
xp*=x;
4 [$ n) S( C5 t6 m- e8 Q) A1 j }
6 m- b; D% W" h5 l* ] printf("Value is:%f",sum);7 i( a# ^* D: C; A. ~! Z7 p# J
}//polyvalue
) j9 u; w& b' ?& y6 c/ d< >

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