查看: 4787|回复: 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;5 s( K8 \' ?# C4 ]7 N1 d0 T* K4 a
temp[k-1]=1; //初始化) m- p; Z7 U4 _- a8 T8 H
 for(i=k;i<=m;i++) //求出序列第k至第m个元素的值2 H% s E# r* m) k1 N
 {
* r ?1 q" B( F5 [, P: {1 \ sum=0;* z) d4 T+ y; x$ E* J5 c
 for(j=i-k;j<i;j++) sum+=temp[j];
# _+ q: `" U4 T, }* G" f) s3 [ temp=sum;
: v/ O! \" c: O! A) s% R% _ }
# R' Z" a, M+ ~' R f=temp[m];8 ~1 F8 L( R g1 j& m0 r2 k. i
 }* R/ V) v/ B5 y: G$ R' \
 return OK;% L t2 J- Z" t
}//fib& b1 N* D W1 N8 t
分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m). 
4 U, v1 k: ]9 V! z3 g. g: v<>1.18 
3 {( r% ]& d: s( N9 r3 Z<>typedef struct{# J$ T4 A" C% W" k, q2 [3 r$ a
 char *sport;. d$ m T4 z# \4 C6 ^" D, E
 enum{male,female} gender;' Q: d( ?' Q, G+ \9 {
 char schoolname; //校名为'A','B','C','D'或'E'
6 } Z. p* k5 H2 t: B) g char *result;
$ s i+ ?: T8 A$ X int score;
: n& @( O# ~. X5 j: @/ O } resulttype; , \/ d; [1 L3 L! f. V3 Q
<>typedef struct{
) U9 I0 M4 h0 o) D3 V4 [6 D int malescore;
/ D9 q2 w$ h$ i& E0 P3 I" } int femalescore;" |+ I( J4 p$ z2 e/ q& K( j! ~
 int totalscore;' N+ p+ g8 |1 D {/ I4 e
 } scoretype; 4 e9 d/ p$ @) q! Y
<>void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中7 M- s' Z0 c* t- _9 o
{" s6 W+ j' z$ T3 J$ Z3 u. G# a
 scoretype score;
. Z. M7 I9 w7 d/ a5 k i=0;
0 X3 N1 P; X+ W while(result.sport!=NULL)+ b3 K9 S- _# M: d
 {5 h9 x6 Z9 q1 _6 a' Q, N
switch(result.schoolname): q' S4 b) D/ V8 Z& M
{
# n- x' M& @' G! Q3 I' q3 B* ?5 Q) } case 'A':
7 v6 q; R% {! Y: S score[ 0 ].totalscore+=result.score;
# T G2 A, S5 c, I5 P if(result.gender==0) score[ 0 ].malescore+=result.score;
0 L: l2 z* R8 M. ~ else score[ 0 ].femalescore+=result.score;
3 t3 |1 x' @5 x; v break;
( u6 _: j5 Q2 G$ q/ q m2 t case 'B':
7 h. U7 n: {' o$ E. @) a7 c( g score.totalscore+=result.score;
4 o o q8 ~, L( O% l0 C' D/ Z) p if(result.gender==0) score.malescore+=result.score;+ L5 {+ f. [) ~5 p* N J
 else score.femalescore+=result.score;
# X0 G2 @0 R/ Y4 _4 A& r break;/ o5 m$ o1 u( |
 …… …… ……2 y& U3 i! N C
 }
7 i) j. E* E, T/ s- n$ o5 }# E i++；
' ~" K& z% B Z2 Z: Q5 ^ }2 `2 I) T) F! e
 for(i=0;i<5;i++)
2 K+ p8 Z6 d$ \* l; j$ _, o8 G! y {: K. I+ f# R# `( j. F1 N4 l
printf("School %d:\n",i);3 g6 r+ o0 C! Z* `' a: Y
printf("Total score of male:%d\n",score.malescore);0 u) ]4 h' v7 q |3 I5 e
printf("Total score of female:%d\n",score.femalescore);
9 O+ b: ]4 \" K7 F3 K* P printf("Total score of all:%d\n\n",score.totalscore);
3 d. j$ ~5 F; `4 J. F! t5 v/ i. H }6 n0 l$ Q3 z% L! [& e
}//summary ! C3 A- d' \( [7 K- C' G
<>1.19 9 K4 T3 g9 D7 ~, N" i; Y
<>Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint/ X9 j" f) [$ z6 m6 R" R
{
; G5 u5 v! _' b% @; a, d3 n4 u0 Y last=1;
( n3 T8 V5 V; c/ o for(i=1;i<=ARRSIZE;i++)
6 z. V3 y& g+ x$ I2 T {
, Q7 C7 G( |1 c+ l3 O4 t, s9 G) w* N a[i-1]=last*2*i;
' {9 u8 p, \( S0 S% O% I if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;) B$ T+ w' c7 `
last=a[i-1];4 v3 y" T8 ]: K2 v
return OK;8 M6 Z e3 y3 K ~1 d
 }
( B d* ~. v' p2 ~7 ~8 F" I6 ]}//algo119# K8 v9 m! P' L. O$ P, }( \5 P
分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. 
9 Z/ O3 `9 w q6 [. C/ P- ^, D<>1.20 ; C, i; @$ j$ j4 i: C& F1 S$ y
<>void polyvalue()4 k" U. X j- V5 m- S7 `/ X
{
2 q& G& P$ q( H3 d float ad;
9 a' { U$ f3 ^& x0 O; E- ~) P float *p=a;3 m* x' W6 D- t- e/ H
 printf("Input number of terms:");
: n5 R. q3 k. Y7 Z; B scanf("%d",&n);
0 R+ b$ G! Y! u s! N* X- | printf("Input the %d coefficients from a0 to a%d:\n",n,n);' L8 G0 W; L7 e# c
 for(i=0;i<=n;i++) scanf("%f",p++);9 m' t s" @' m' H
 printf("Input value of x:");7 p1 d; M+ P+ }5 ?; e/ ?( x# }
 scanf("%f",&x);* R/ Y7 w$ ?% l
 p=a;xp=1;sum=0; //xp用于存放x的i次方
7 S) c/ }# ~! H! G7 ] for(i=0;i<=n;i++)
! c% Z V1 v7 _2 j$ M! H- q1 D0 v {6 n8 N; E# y; R- C2 r9 a
sum+=xp*(*p++);
 r% F! y4 A* z xp*=x;4 K9 J; n: M/ C" T
 }1 X$ \0 N/ n7 i3 W4 s6 U7 S
 printf("Value is:%f",sum);) S, Y3 w8 n0 B9 L
}//polyvalue
3 {4 S3 L" ~6 Y w1 @< >

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