查看: 5010|回复: 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' q8 f6 m3 C% p% g6 y3 Y, `$ @ temp[k-1]=1; //初始化
! s" r. \1 F4 o# C for(i=k;i<=m;i++) //求出序列第k至第m个元素的值
. A4 @* g$ ]/ e" @ {
$ Q# U2 p3 h& K U1 [1 s sum=0;# N6 T: D( F: p1 X! t2 g
 for(j=i-k;j<i;j++) sum+=temp[j];
7 B9 m5 n; Y) x, b0 b# V# e( J1 O temp=sum;
1 n# H/ S! V5 T! d) z- h }
/ \/ C" G f& q: o8 o f=temp[m];0 m8 o! r" [) s! E( A/ O' [4 I
 } B" j: p- Z/ H8 K* @
 return OK;
6 d- `4 d+ I; d9 ^# l}//fib& j1 B) h! c& c! Y
分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m). - t7 o! e' q2 X. E2 T+ H8 \- q
<>1.18 5 ]! M1 w; ~# z8 [# x( r
<>typedef struct{6 ]5 N4 P8 [% G$ W% m. a
 char *sport;( V1 ?3 q% x8 `* t( h! ]
 enum{male,female} gender;5 l1 L: \* r5 M+ F7 z- C6 u' Q
 char schoolname; //校名为'A','B','C','D'或'E'
! m) h! o! a% U2 P( t char *result;, m6 H0 Z/ |7 L, J* |5 v
 int score;
' |. S' B$ J: L% h7 E4 j7 B( H& ] } resulttype; 
3 M* x# D) s: j9 U<>typedef struct{
 Q% Z1 P" K2 A+ p2 T* p int malescore;
; S" q$ q+ G- \5 {* u! D3 S+ n- P int femalescore;" Z7 v8 U7 `2 i1 {& U/ i4 E
 int totalscore;
6 \! W8 q' v" p1 k- ` } scoretype; 
( r+ \% Y, {' {/ R% h9 [7 O<>void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中9 l% M" X- B: S8 ]
{
0 s, L( F5 W! ~& m! _3 v Z$ `3 ~ scoretype score;
/ K& ?. S# o! Q* o8 E i=0;
( c! s4 c y; }' B while(result.sport!=NULL)' T6 i* t C. k% e( [7 x- c
 {; d" w+ F; ~2 U( v
switch(result.schoolname)
; Q+ v- _) G5 v6 o# b) g( X1 N {) Q9 }7 \8 F% U5 J5 c3 K& d2 P
 case 'A':
( D6 z3 x+ c" }9 `( D score[ 0 ].totalscore+=result.score;
& R- U2 u m `9 | if(result.gender==0) score[ 0 ].malescore+=result.score;6 Q/ I( i1 d: M+ j/ f1 C2 @# r
 else score[ 0 ].femalescore+=result.score;3 P( M f4 y9 Y2 k: a
 break;2 V) `# E) q) ^ Q5 w0 v
 case 'B':6 E |) A) a& E6 e' h7 x
 score.totalscore+=result.score;) a6 w- a. C* B, z; K
 if(result.gender==0) score.malescore+=result.score;
+ u9 y ~) \+ v: Y2 ?9 Q4 O else score.femalescore+=result.score;
& s& T& k H1 c4 G& r3 z8 f break;
; _2 D& M; E, |2 Y …… …… …… s# ?+ _% O3 P* i" Q t
 }
$ W5 V) u$ m( |' L5 ?; ?. o i++；: N1 y3 ?( a& H+ k* n6 \8 i
 }( V* G' R5 F; r4 M. u* Q
 for(i=0;i<5;i++)4 _- e8 K# Y+ s, L+ P
 {8 \5 b C4 m8 L
printf("School %d:\n",i);, k" n* B" ?* M7 h% |
printf("Total score of male:%d\n",score.malescore);
0 u1 R) T3 n6 D0 `2 h printf("Total score of female:%d\n",score.femalescore);, o$ z _# l5 o; e1 m
printf("Total score of all:%d\n\n",score.totalscore);5 S* z4 {% W3 m7 i( f
 }( s# w. a" f! O
}//summary 1 F2 N9 w1 _9 F v& j8 p+ d8 l6 ^
<>1.19 
2 P! m8 o% w* {7 Q<>Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint
4 v' F" j; x: F9 y{8 u0 W3 J2 k7 w; s; d1 [* r
 last=1;
 for(i=1;i<=ARRSIZE;i++)/ k6 r, M" D) a( ?1 C* D1 D
 {# _/ q! \5 j- ]2 |# O
 a[i-1]=last*2*i;
$ ~5 C( |8 q: [1 ~0 n2 | if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;
- g- u, V; T& R7 @ last=a[i-1];& M; d8 L1 g( v* M5 C
return OK;& ^! i1 A( t2 k4 B/ Z/ d/ {& }
 }7 a6 P) M' E+ X/ d/ m4 W6 l3 ` R
}//algo119
# t0 d+ ~$ p0 x; L! J' j( v) S3 J% Z分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. 
. u. \0 s, Z( G0 z- b o9 E<>1.20 . U& c1 C( g1 P- U* B9 `1 @
<>void polyvalue()
! f( [# V5 e; k' P5 N# B2 R: B{
7 }' X$ r$ o: ` float ad;
- [. P- _# t% M float *p=a;
7 I0 [4 e0 I# X% g printf("Input number of terms:");" Q) @; Z7 u! `9 h! X, A. q4 ]
 scanf("%d",&n);
5 P% T! c! e% _! q7 O/ A- r printf("Input the %d coefficients from a0 to a%d:\n",n,n);
2 K' P. J& X8 o- j% a for(i=0;i<=n;i++) scanf("%f",p++);+ @" ]8 S T; ^5 I8 w4 u2 M. H
 printf("Input value of x:");
. c2 T9 q/ I5 S scanf("%f",&x);
6 f% H) M8 t$ H' |0 \0 u7 ~ p=a;xp=1;sum=0; //xp用于存放x的i次方
) n& q, ^+ u+ ` for(i=0;i<=n;i++)
8 P$ J$ J; V+ }- H4 G/ K9 c {
/ {% A9 u, I; \3 E4 }6 y( c2 k9 c sum+=xp*(*p++);
' p+ [4 y$ h) |& Q5 S+ b* G xp*=x;) P7 g7 \2 X* h8 Y7 c1 h$ \
 }9 _: A1 p2 e! C
 printf("Value is:%f",sum);
4 {5 c' W/ s$ M# b. h}//polyvalue; C9 P6 H7 p v$ ]8 i5 J2 b
< >

zan

转播0 淘帖0 分享0 收藏0 支持0 反对0 微信

使用道具举报

╃無名草╃

66 主题	1 听众	648 积分

VisaSky.com 加拿大移民留学网

TA的每日心情

	开心 2012-6-9 03:29

签到天数: 1 天

[LV.1]初来乍到

2^#

发表于 2004-11-28 18:16 |只看该作者 |招呼Ta 关注Ta

<

0cm 0cm 0pt; TEXT-INDENT: 144pt; mso-char-indent-count: 9.0">第二章线性表 <

>2.10 <

>Status DeleteK(SqList &a,int i,int k)//删除线性表a中第i个元素起的k个元素
{
 if(i<1||k<0||i+k-1>a.length) return INFEASIBLE;
 for(count=1;i+count-1<=a.length-k;count++) //注意循环结束的条件
 a.elem[i+count-1]=a.elem[i+count+k-1];
 a.length-=k;
 return OK;
}//DeleteK <

>2.11<

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