查看: 5004|回复: 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;
" z. b+ R3 G& [+ n! h temp[k-1]=1; //初始化
: g9 w% p+ [9 U g9 y for(i=k;i<=m;i++) //求出序列第k至第m个元素的值
8 T7 N1 j" Q, Q {
: f; }+ Z) Z. A$ l sum=0;! M$ f& }, d0 E, H$ n7 P
 for(j=i-k;j<i;j++) sum+=temp[j];
) L% S* y- ?# {. [3 p temp=sum;# o" l. Z4 `. P, \ L
}- m- [; U( X1 Q3 ~( p8 n3 t
f=temp[m];
3 w1 W) z9 i0 B }
( p; @1 e* b- {1 B return OK;' z0 ]& L# b5 v# M: {5 Z; c
}//fib
6 }" Y8 V) u! M& k8 E4 H3 t, A# W分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m). $ g0 [6 {# J O& v+ C9 o4 b
<>1.18 $ g7 Z3 {- t! f- w2 E* p
<>typedef struct{
8 j, X( Q. x0 ]4 o2 t; X char *sport;9 i8 w% e+ w6 ^
 enum{male,female} gender;! l( K2 M3 O- l8 c1 L/ U# l
 char schoolname; //校名为'A','B','C','D'或'E'
4 D: q6 R5 l$ S char *result;
. Z1 u9 ?. O# M5 H% B. S/ \7 ~ int score;8 i1 B. @. Q' f2 e* t; G
 } resulttype; 9 f/ x! N7 N, r5 H0 N4 u c* D
<>typedef struct{
# q; v; n- z- |4 b- w/ E5 s int malescore;
% S) V. T7 C% B. H* e6 @4 u9 N int femalescore;7 i* C: w3 ?$ H
 int totalscore;
/ T H( U0 H# S5 _6 y) D$ u } scoretype; 
: f, l# }/ s4 t4 r! Z% o& f<>void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中
3 D3 G# g) L8 Y{
+ \ i# b$ [% E$ n F scoretype score;- S3 @5 i% R9 `3 D3 `, Q
 i=0;
, ~2 ?8 a) [$ I) K while(result.sport!=NULL)
; y* b0 f" s# t/ C {
 X$ H! O1 q* P4 d, d switch(result.schoolname)
& \6 ?( q% ], u6 o {
8 z+ J2 U6 R, E# c7 Z case 'A':; [5 g/ d$ R' H, ^" o
 score[ 0 ].totalscore+=result.score;
1 T* F4 @, |! r0 t if(result.gender==0) score[ 0 ].malescore+=result.score;, w$ E' K+ _* Y/ r- J
 else score[ 0 ].femalescore+=result.score;
% f9 c1 g/ _2 C" F! M" K0 x break;& i, O7 \- K1 V* [4 b+ ^9 @
 case 'B':+ t/ W& D, f' y
 score.totalscore+=result.score;
9 q' W% i: T( y4 N: A% M% A7 R if(result.gender==0) score.malescore+=result.score;
) f# O7 u& X" K else score.femalescore+=result.score;
# C3 U9 i% [; Z4 R% l8 o break;
% ]0 s4 ]1 C6 x1 }: y \4 o …… …… ……. ^3 q3 |, o h
 }
; P. ?4 ]3 Y4 [* ~ i++；5 k: p1 }9 [1 L- E
 }
5 a% {, M# X. O$ ~2 w* Y U+ ` for(i=0;i<5;i++)2 P$ \+ \4 m5 \; Y: X
 {+ r, F5 K( V0 F- H4 m! d
printf("School %d:\n",i);
# L, B( l7 o$ Z, \4 v printf("Total score of male:%d\n",score.malescore);& t3 x) j: k- X
printf("Total score of female:%d\n",score.femalescore);
1 f6 t5 r% n, r/ F2 h& o+ w printf("Total score of all:%d\n\n",score.totalscore);3 ]; U& D6 u# D; ]
 }- n! c( P$ F/ S9 x" ~+ k; ^, E
}//summary % M3 ], O; a0 w# U+ F9 g& y
<>1.19 $ ]3 a' ^. Y& H. @2 ~- m5 P8 S0 }7 w
<>Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint+ l7 Q# u+ y, C+ k2 h8 u" o' G6 z" u
{
& s& s0 V7 c" y5 R: L last=1;
% i4 b0 k4 W- r6 N for(i=1;i<=ARRSIZE;i++)" [; W5 R( k& i4 a9 `! x9 z
 {1 I( O( E, Q% Z/ n4 h( t
 a[i-1]=last*2*i;8 K6 u5 A: l2 F
if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;0 Q% {: s" o* A
last=a[i-1];7 N, b0 C5 u5 B8 s
return OK;
0 Y& Z) V" L- w/ b6 g" ] }
7 _. l' _$ b8 N/ C( d+ `( H# t$ X}//algo119; ^7 `2 \3 B7 U& Q3 l* H
分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. ; v! r; b$ E- {2 D2 l: C! I
<>1.20 6 W' p% n2 h% v
<>void polyvalue()5 E0 P8 @, @; A
{
% }2 ~4 @7 @& ^0 k float ad;- _& l# `! t+ I3 S/ F+ H* n5 O
 float *p=a;/ N6 u; L) O* p7 d2 s
 printf("Input number of terms:");4 I2 n/ Y) m2 @# }! V( m
 scanf("%d",&n);
; S9 u- F% i7 q/ N! _ printf("Input the %d coefficients from a0 to a%d:\n",n,n);
* ]+ V! d3 t- B( x for(i=0;i<=n;i++) scanf("%f",p++);: j, E7 k3 g. _; f' z! b' _
 printf("Input value of x:");
- \$ x: P, z% Y* z scanf("%f",&x);" _3 P9 r% H3 `& z5 R* M: `
 p=a;xp=1;sum=0; //xp用于存放x的i次方# [. k" ^1 C0 X \; G
 for(i=0;i<=n;i++) G3 k$ ~5 N6 g5 {
 {# h2 c/ h; U, x Z: O
sum+=xp*(*p++);
: ?% {9 C/ c+ t xp*=x;* [* B# s" e, M+ v' g$ y# G
 }
 printf("Value is:%f",sum);
+ A9 [3 h) W; e) ^3 M! W' s7 ?) @}//polyvalue7 V* f5 f* u' M0 @, N
< >

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