查看: 4758|回复: 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 x8 o& ^/ f9 e- x; S0 V
temp[k-1]=1; //初始化# u5 j. p4 I0 _; Z$ v" s
 for(i=k;i<=m;i++) //求出序列第k至第m个元素的值
3 _: }) l- P" v. h" w! L+ @ {1 h* {: ^% n# X# s' u J
 sum=0;
- Z4 T1 p" F' p% X8 C; `, v$ B" A for(j=i-k;j<i;j++) sum+=temp[j];2 n/ t* t7 l# B2 M7 c0 _, c1 s
 temp=sum;
$ K( j. f: @0 K \3 f" R }6 b" A& W& Q$ B
f=temp[m];
/ a7 e7 ]$ t7 w% C' `: E4 p }( q: o; u. y& [0 F8 ?2 J2 ?- H$ B
 return OK;2 \6 ?2 L% t1 [- B
}//fib1 c6 l( L6 ?8 ~* A h
分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m). / p! e& j4 P' ~
<>1.18 
& q3 x. Y! I! n. D$ o/ y _<>typedef struct{0 C& [% v/ w3 ]
 char *sport;
) q a5 n( d( h7 _ enum{male,female} gender;1 S5 t+ Q* N% y# Z3 p% F
 char schoolname; //校名为'A','B','C','D'或'E'
: o( D* [8 ^2 q" q char *result;1 @, q* X" n8 v9 F- S5 w6 }# N3 g
 int score;
( U }5 H) \, A) ^ } resulttype; * I) R0 S- e6 s" _5 |* H, k
<>typedef struct{
2 o- n* ?# d# d& A# x& h3 l int malescore;
/ d- d. e Q* V! D/ G int femalescore;( Z% O( g F" A8 d
 int totalscore;5 a9 N0 ~; d, K2 z" B- @# @
 } scoretype; , E9 @' V2 ]4 D6 ^' B. x+ W, s
<>void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中5 a5 J% f: c% ]0 c7 {0 w
{
$ i7 `9 |0 D% S( [ scoretype score;0 X* n& P" S1 e; v
 i=0;
4 i, U$ Q2 x$ k2 C$ Q' [ while(result.sport!=NULL)
( k/ F) U3 m& {5 O1 q {
7 ~2 L \% b, L; y6 C$ R switch(result.schoolname)8 W5 I) B2 O* H- Z( i0 r+ d+ Q
{: e1 {! [8 R: f; X
 case 'A':
) h* P# l/ z# \& _" |" L( N% A' u$ A5 N score[ 0 ].totalscore+=result.score;
! ^8 Q) d! Q. g3 t, A. ~. m1 D, Q) t if(result.gender==0) score[ 0 ].malescore+=result.score;
1 \ Z4 C: ?/ a: d! l. G: S& k else score[ 0 ].femalescore+=result.score; z+ }9 f+ g# ?
 break;. R1 V7 Y ~' N+ {, I$ r' E
 case 'B':$ z+ R8 @# p7 \) t3 B0 L
 score.totalscore+=result.score;
& d$ ^3 r( v, B: {1 _ if(result.gender==0) score.malescore+=result.score;
+ A7 x( m" M8 F/ t$ T- Y else score.femalescore+=result.score;
0 g3 H0 y P* e& V+ f9 B: m break;
3 N6 g% z X- e+ z …… …… ……
, i( x; \! [: Y- e h+ R3 H \ }: K' y+ s0 w! B2 \4 i" |
i++；
. C2 t) r* ~1 h5 _/ J C9 E }
- |" w! g# |1 {1 J for(i=0;i<5;i++)
: p+ b* z, N( q+ u {
7 |- m& U' g, S, y: i' z printf("School %d:\n",i);! S3 [( O; h. C: a9 [8 N5 n. }
printf("Total score of male:%d\n",score.malescore);
( O5 Z, h0 g7 t4 n3 ?+ a$ z printf("Total score of female:%d\n",score.femalescore);/ q- G0 n; i" Z: v) _+ t$ q
printf("Total score of all:%d\n\n",score.totalscore);# C+ F4 e) ^. _9 O8 y! O7 ?
 }0 w9 \" n- Y6 B# H" S1 n5 b' P" d
}//summary 
% L, C; K5 H3 Y. s+ z5 ~<>1.19 
8 M' y7 f( K; R<>Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint
9 R p) N6 w( p( b. w* `{
5 z0 t5 A d, C0 j/ } last=1;5 u. W6 W. X! @
 for(i=1;i<=ARRSIZE;i++)* L- m! B8 {' d" l
 {
7 \! J$ a k6 L) ]/ J a[i-1]=last*2*i;
. ?( k" g5 n# P( y9 a5 r' c if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;; ~- i" T& K- [9 n2 @- A: Y
last=a[i-1];
) |7 u! [( m* P! P return OK;
# x) t2 N" \4 _0 T' l }( j$ {$ A2 A7 y. }% r6 ~ \
}//algo1191 d `4 b& _& l& C3 R& g
分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. 0 w( o7 Y) O9 b3 P; N7 {8 _% k
<>1.20 # j4 ^7 `7 a# |; t
<>void polyvalue()+ j! }1 d) I% n. S5 ^
{5 Y2 b; i# c' Y0 d
 float ad;; O% l) t5 F$ m) R% b$ a* [
 float *p=a;
( B, j( q$ Y9 C( A printf("Input number of terms:");- f- W% E2 u7 s! ~$ u0 W5 z9 Y; B
 scanf("%d",&n);" O- S A2 H6 \2 w8 ?/ _7 W
 printf("Input the %d coefficients from a0 to a%d:\n",n,n);0 c/ ^4 B! }. n6 {% F
 for(i=0;i<=n;i++) scanf("%f",p++);
6 D# ]1 ^0 F& ` printf("Input value of x:");
4 l; V, u; M2 R/ d4 C" t. d scanf("%f",&x);
6 Q) d$ g, }& s9 p, @, Y- D5 H p=a;xp=1;sum=0; //xp用于存放x的i次方$ l8 L7 e/ y3 G8 A1 i" U
 for(i=0;i<=n;i++)
) P j! O2 t9 \4 ?2 P& r {/ P% q) s: Q0 t3 u0 J5 E; C
sum+=xp*(*p++);
2 t( F3 E% P% I; j! O7 b xp*=x;$ Y" I D) H" d z C' [ J! C
 }
. v# B; B, t( [: J* C printf("Value is:%f",sum);- X4 C0 X. ^; ], m$ b; \
}//polyvalue
3 X6 o6 {+ z* l3 D 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--)+ s/ o6 D' F' D2 s
va.elem[i+1]=va.elem;
% i* O c+ f3 c; x) p. L va.elem[i+1]=x;. E4 n+ m9 i3 a, k; b6 s8 X
 return OK;
, r/ L* a$ x. J, s: s3 ?3 z( F}//Insert_SqList <>2.12 <>int ListComp(SqList A,SqList B)//比较字符表A和B,并用返回值表示结果,值为正,表示A>B;值为负,表示A<B;值为零,表示A=B( W* u. h Q: w' p4 G6 S
{
 s$ T8 h$ @% v for(i=1;A.elem||B.elem;i++); G& @" o3 e1 l- {# J' e
if(A.elem!=B.elem) return A.elem-B.elem;) l J" o& s3 C( F, V2 n
 return 0;
. U4 |' M9 P+ o: K}//ListComp <>2.13 <>LNode* Locate(LinkList L,int x)//链表上的元素查找,返回指针
7 X4 d! r; ~+ a# \% W% f" w0 ?{1 G M$ {2 P' ]" W- L: k
 for(p=l->next;p&&p->data!=x;p=p->next);
. i) @ f2 E" O return p;
) o' i- c; w$ a6 x}//Locate <>2.14 <>int Length(LinkList L)//求链表的长度
7 P5 c) S7 T: [3 u; Z" q1 k( N{9 h( u! t6 x3 `
 for(k=0,p=L;p->next;p=p->next,k++);
: F2 O4 ~) Y, s% ~ return k;" z. \1 ^: b6 u5 M
}//Length <>2.15 <>void ListConcat(LinkList ha,LinkList hb,LinkList &hc)//把链表hb接在ha后面形成链表hc
* f8 u' q2 M# Z1 J0 v9 J! v+ n6 [{4 e# E( m9 x5 b' o1 N7 @7 m* q; K
 hc=ha;p=ha;
' B( P, c A" H1 A; l while(p->next) p=p->next;
: }1 {+ h G, u8 M" D p->next=hb;' J& ?: M$ h0 @/ j8 ?: ^5 r1 u0 t' I
}//ListConcat <>2.16 <>见书后答案. <>2.17 <>Status Insert(LinkList &L,int i,int b)//在无头结点链表L的第i个元素之前插入元素b
, s7 Z7 x$ `. H1 P+ }{: P9 P' R9 z3 [: q
 p=L;q=(LinkList*)malloc(sizeof(LNode));
; Y$ r, l, e# R q.data=b;
6 X* |) S& |. C& u# r if(i==1)
& [/ E. b$ R( z) y7 j {
) L7 D7 U) C! P" I: H q.next=p;L=q; //插入在链表头部1 q$ E" L8 R* f) [) |
 }7 M, R! W z! M' @
 else; A( V- e- b0 I0 m5 N4 J: q
 {
6 F; |+ t0 B2 h" ] while(--i>1) p=p->next;4 Z% a' C' ` ~) Q1 c9 b4 N' s
q->next=p->next;p->next=q; //插入在第i个元素的位置' H( {0 H( y$ M' t, w
 }
1 G8 G7 G1 `$ k4 V; a" s6 u}//Insert <>2.18 <>Status Delete(LinkList &L,int i)//在无头结点链表L中删除第i个元素
0 v3 l; j0 q& v; [: G& ]{
 if(i==1) L=L->next; //删除第一个元素
; w) l- @0 ^4 p; y- i# ^+ _ else
* y5 A1 ]1 q6 S* P' @$ ^+ w: L {' T5 p O; U: _3 ]/ h) _
p=L;& F A2 l/ D4 z
while(--i>1) p=p->next;
) u) q/ n% N6 A% z0 c/ ]& h p->next=p->next->next; //删除第i个元素
- ]5 V' n e$ u T }
 Y3 h0 [5 \! r8 f* n}//Delete <>2.19 <>Status Delete_Between(Linklist &L,int mink,int maxk)//删除元素递增排列的链表L中值大于mink且小于maxk的所有元素
/ S6 ^, k' _8 D! |# v0 C{: ?; `) M* D, H; W- P
 p=L;
2 e: C* [- X( v5 u) V) o; k! S while(p->next->data<=mink) p=p->next; //p是最后一个不大于mink的元素8 e+ d- N: Q# |+ Q
 if(p->next) //如果还有比mink更大的元素: P/ k! D: M T1 R" R
 {
+ i% ?* H& o/ w* [ q=p->next;
: s; G( @8 z% e while(q->data<maxk) q=q->next; //q是第一个不小于maxk的元素* d: M; K4 j7 j5 s
 p->next=q;; I* L5 Y1 s# u/ D' l1 G
 }
 ?# U I; [9 g' y( D}//Delete_Between <>2.20 <>Status Delete_Equal(Linklist &L)//删除元素递增排列的链表L中所有值相同的元素( E3 C; |! j R1 ]- A
{8 ?; T8 s# X8 T: r7 O, ?4 `
 p=L->next;q=p->next; //p,q指向相邻两元素
$ _% r( y- Z/ _& s* q while(p->next)2 Y: P0 g, Y3 u
 {2 c) ?6 B- r% k6 D. @$ w
if(p->data!=q->data)" @7 i9 J! W0 ?; j6 R2 z; V$ \, l
{
( w4 m$ {& C& m$ q p=p->next;q=p->next; //当相邻两元素不相等时,p,q都向后推一步
; o* W( Q7 y$ B9 {6 @8 g2 U6 W2 b }/ u9 l. N* N7 S, i
else$ o! Y/ W5 q+ Q* j [0 a4 P
{1 F& o' o1 X; N0 w2 p% ]/ ]4 _+ c
 while(q->data==p->data) 4 a L, |. y: {( R! O5 h
{
9 C& Q: J I" ~; P4 B free(q);5 S6 E q3 h) D+ ]
 q=q->next;
8 N& f2 _, S0 f& e# o: ]+ r! t! q }
9 \3 u8 i- J P7 s c p->next=q;p=q;q=p->next; //当相邻元素相等时删除多余元素
+ f) H' U. y; r7 g" B x( e9 n: R" ] }//else
, j/ U3 o7 u6 ]9 U- `( Z0 c6 P }//while
$ y, j5 C" {5 T B9 p}//Delete_Equal <>2.21 <>void reverse(SqList &A)//顺序表的就地逆置
9 U0 U/ E' ~( Z# N1 R2 U3 h. m. t{
7 C! p9 v+ P* B7 S for(i=1,j=A.length;i<j;i++,j--)
. y* n+ J; ?/ L3 w& ]' s A.elem<->A.elem[j];
3 Z P2 X3 M q# F}//reverse <>2.22 <>void LinkList_reverse(Linklist &L)//链表的就地逆置;为简化算法,假设表长大于2
7 R: b& u# ]5 t1 M$ y; `& @{
! ]" F) E3 Q& {" T. @3 d8 i p=L->next;q=p->next;s=q->next;p->next=NULL;; e+ K! n* p: ]" _: k2 _
 while(s->next)
/ m. a: w2 g& m( B {
" E* V2 D* _" V: E5 b. |+ x q->next=p;p=q;. D, h2 E! ]5 X- Z, M v# c
q=s;s=s->next; //把L的元素逐个插入新表表头( V+ s9 y! ^5 Z
 }
4 m6 W; r, b5 t h6 t: R) T2 A q->next=p;s->next=q;L->next=s;; i+ |) Y7 d. c* S
}//LinkList_reverse8 R i/ M' [1 t" W
分析:本算法的思想是,逐个地把L的当前元素q插入新的链表头部,p为新表表头. <>2.23 <>void merge1(LinkList &A,LinkList &B,LinkList &C)//把链表A和B合并为C,A和B的元素间隔排列,且使用原存储空间
! p8 N" D/ E) c* ^4 k{; C8 D; t, o4 \/ {9 n* I
 p=A->next;q=B->next;C=A;
* q$ x) A$ W+ t Y while(p&&q)
0 s3 d2 Y4 I% n {
( L7 t3 s/ V) ^$ y: a s=p->next;p->next=q; //将B的元素插入
/ ]7 \8 M! `& n2 k& Y: Q+ m if(s)
" M( O8 G9 ?3 m4 I7 H6 L, z {% S4 K8 _+ U2 n/ g- F* `% X) b
 t=q->next;q->next=s; //如A非空,将A的元素插入
& N: r M% w+ o8 t% U6 S' k" p2 ] }2 ]& I. B( @0 H/ p
p=s;q=t;
 z6 _/ M0 F! g/ L }//while
7 \; |( Q) q' R' e1 x8 t- P}//merge1 <>2.24 void reverse_merge(LinkList &A,LinkList &B,LinkList &C)//把元素递增排列的链表A和B合并为C,且C中元素递减排列,使用原空间9 |, a# Q4 S' s0 y9 X) u; g
{# X" f3 D5 M! A0 Z
 pa=A->next;pb=B->next;pre=NULL; //pa和pb分别指向A,B的当前元素
: s; c9 P9 v3 p( U6 ?/ e1 [ while(pa||pb)7 H0 Q6 O* v. V# F" ]( `
 {6 E- e& K. ^: k, M& H: G+ C
if(pa->data<pb->data||!pb)
2 d* H9 g7 a8 t5 H: B {
- l( s; h! Z1 b* }, m; ?0 C7 H pc=pa;q=pa->next;pa->next=pre;pa=q; //将A的元素插入新表
" G! H& o# R! T }4 P7 ?6 @( j( @' x
else2 H, v% X; Q+ r# \: |( F
{
$ k2 V! |& X7 g. u: W" |/ r pc=pb;q=pb->next;pb->next=pre;pb=q; //将B的元素插入新表
+ d8 x$ @* @" j- \ }5 D9 W. w& j9 [9 n0 u
pre=pc;
% e6 e8 w" I0 e- i( i2 d6 C6 | }, F2 i- S8 s- e: T
 C=A;A->next=pc; //构造新表头
. I5 G- U0 k" `. ]! H/ ^}//reverse_merge' i" \+ L& d3 b* n6 L: m1 \" S
分析:本算法的思想是,按从小到大的顺序依次把A和B的元素插入新表的头部pc处,最后处理A或B的剩余元素. 2.25 void SqList_Intersect(SqList A,SqList B,SqList &C)//求元素递增排列的线性表A和B的元素的交集并存入C中
- N2 u2 r9 j: W" t$ p! ?{
# }5 P- ]; {) ^/ T3 G8 A5 \ i=1;j=1;k=0;7 v. n. j$ x7 O. w! [# E4 s8 N8 [
 while(A.elem&&B.elem[j])
3 G8 ^: N* N: M {
1 l6 s9 c; `: d& | if(A.elem<B.elem[j]) i++;
" L- q; Z* z3 B" B' k if(A.elem>B.elem[j]) j++;$ K. T$ V6 @2 X1 v
if(A.elem==B.elem[j])# R! C9 d$ d% D$ g4 J
{
0 L7 L; W) B) c4 m/ Y C.elem[++k]=A.elem; //当发现了一个在A,B中都存在的元素,
/ y( ~( `4 L& M1 m( p i++;j++; //就添加到C中& E( v- K3 V/ U
 }2 h% ?/ a, C& s! Y" S9 R
 }//while" j6 ?/ P! f0 t' q) ]8 l
}//SqList_Intersect 2.26 void LinkList_Intersect(LinkList A,LinkList B,LinkList &C)//在链表结构上重做上题
5 W& e" w6 g, b" z$ h- G. Y8 \{! L( Z+ z$ g# m5 Z% U$ U
 p=A->next;q=B->next;! `* H% L' R; A' z- f# r" ?9 T
 pc=(LNode*)malloc(sizeof(LNode));$ }7 `0 s4 G$ T0 B+ N. Y1 J
 while(p&&q)
 s1 c' P. l( ?( p1 A" \3 z {
4 d+ U, ^5 H: x! f- ? m if(p->data<q->data) p=p->next;3 y3 h3 n @" s/ m
else if(p->data>q->data) q=q->next;; O7 Y- D; N$ }* `
else
& {* h( B% V |; f {
, Y- `4 c* [: M: \ s=(LNode*)malloc(sizeof(LNode));* E8 c7 g% O, r( x" n# G3 m+ X* j9 U
 s->data=p->data;4 _/ T6 n4 s6 c5 K1 k. P
 pc->next=s;pc=s;
4 f+ U# l; }) h+ o p=p->next;q=q->next;0 _( i7 u, [4 v* e e7 Z+ T1 e4 ~
}3 w# C+ n/ m, H8 v
 }//while$ N5 j& I* \3 {; }6 Q3 }
 C=pc;
1 O' k, `6 p4 K" D}//LinkList_Intersect 2.27 void SqList_Intersect_True(SqList &A,SqList B)//求元素递增排列的线性表A和B的元素的交集并存回A中
: F) _! L: f u# \8 r{
9 Y2 m! e0 U; K8 Z. @) E: N i=1;j=1;k=0;% G+ L5 _ D) u( J; q7 I: h: @) [
 while(A.elem&&B.elem[j])
0 g! \( L0 b% B8 h9 t' u) n' {; ~ {7 _7 E9 \, \# C5 E. J. ?
if(A.elem<B.elem[j]) i++;8 e3 ^4 z8 ?9 T0 l g1 G6 Q
else if(A.elem>B.elem[j]) j++;0 N; I) K$ S1 |
else if(A.elem!=A.elem[k])( e2 ~ t# I0 B# w3 ~. \# |
{; ?7 d. x' ~7 J( v$ Q
 A.elem[++k]=A.elem; //当发现了一个在A,B中都存在的元素4 V0 y* I, J, _: O( o
 i++;j++; //且C中没有,就添加到C中6 Z- o+ \, M: \. r
 }
) t: o- g% P" }+ F1 d' L }//while& o6 x0 b% E& x, u
 while(A.elem[k]) A.elem[k++]=0;" E' ?% ]( Z0 J) e' q2 o) ?# g. g6 O
}//SqList_Intersect_True 2.28 void LinkList_Intersect_True(LinkList &A,LinkList B)//在链表结构上重做上题& K' c9 D1 u/ h. H l, T
{
, U- T: M. N, i p=A->next;q=B->next;pc=A;2 G) {0 f r. Y4 K) _2 `
 while(p&&q)
8 ~8 Z6 L, g# M {
& t9 x% W/ I& ]6 M* D( @/ E/ v if(p->data<q->data) p=p->next;/ V* s7 H, d$ H1 M/ C
else if(p->data>q->data) q=q->next;' h7 m6 J3 ^+ D- D) g6 \' i
else if(p->data!=pc->data)+ b0 p$ u2 f3 k% E, J( N
{
5 y. J8 Q8 V9 ~1 u/ Z& @7 p pc=pc->next; D& _% D* X4 n7 p
 pc->data=p->data;' @ H4 |& H! ], i9 a2 Y( l# ^
 p=p->next;q=q->next;
! t% Y: t `% J9 c& e* y; M }
8 n7 t3 U# r4 B" b0 V% \3 ^4 p }//while
4 i2 K3 E( L ^7 C- P}//LinkList_Intersect_True 2.29 void SqList_Intersect_Delete(SqList &A,SqList B,SqList C)
8 A5 V) D/ I9 D3 n8 S4 i! ]5 x7 z: O{
* ^0 Q/ [6 ?- u i=0;j=0;k=0;m=0; //i指示A中元素原来的位置,m为移动后的位置& p9 m/ A2 B: x' L6 k' [% Y7 b
 while(i<A.length&&j<B.length&& k<C.length) 6 s/ |7 N' @4 c- I
 {, \9 c5 {$ @9 o4 |- s2 E q
if(B.elem[j]<C.elem[k]) j++;) H2 P c$ `; ?7 Y
else if(B.elem[j]>C.elem[k]) k++;- K" u# J1 u0 Q' r
else& q! r6 Z& ~1 A- W# t+ q( C/ W
{& f- H+ M9 C6 i3 a2 E m* V4 m6 W
 same=B.elem[j]; //找到了相同元素same
( @8 ]: s6 ]) T) } while(B.elem[j]==same) j++;: U8 x+ E' r/ a- I$ @
 while(C.elem[k]==same) k++; //j,k后移到新的元素
7 f- M& V; L8 ?( J0 b while(i<A.length&&A.elem<same) ; v9 u# B* J6 H: u( O4 }2 _
 A.elem[m++]=A.elem[i++]; //需保留的元素移动到新位置7 R9 q+ |- F- B8 O* N" E9 G/ W
 while(i<A.length&&A.elem==same) i++; //跳过相同的元素
% l! Y$ W& i8 B4 a9 K: W }0 Z: G/ e/ ~0 Q' n: y; G" b; u" F6 R
 }//while* j' `8 l$ H% q1 n
 while(i<A.length) : s' I0 X& F" M
A.elem[m++]=A.elem[i++]; //A的剩余元素重新存储。
& ?/ s l$ c, T% [3 r- A) { A.length=m; 1 }4 f7 r6 _/ j0 d& T
}// SqList_Intersect_Delete; M% A5 w4 f! Y3 X+ e, v! ^
分析:先从B和C中找出共有元素,记为same,再在A中从当前位置开始, 凡小于same的, Z% j/ F8 z- d% A3 t7 t
元素均保留(存到新的位置),等于same的就跳过,到大于same时就再找下一个same. 2.30 void LinkList_Intersect_Delete(LinkList &A,LinkList B,LinkList C)//在链表结构上重做上题; X9 ~6 x+ O, i9 f# P/ A$ b8 d
{
+ C, _% x8 W# b& T& C( A' Y! W p=B->next;q=C->next;r=A-next;4 X$ H7 l4 D9 G% f; s
 while(p&&q&&r). L3 w1 Z( F6 t& J4 l
 {
. q5 ?! B' T9 U4 m/ @: y+ F' v if(p->data<q->data) p=p->next;
( u8 b& [$ l1 D, Z else if(p->data>q->data) q=q->next;1 x; L! i) ?2 G4 ^
else7 J5 [5 z+ f8 X3 e- b2 R$ K
{) D$ x$ Z8 B7 S5 r# `8 z! v
 u=p->data; //确定待删除元素u' R: t' v) H! ^: j: {
 while(r->next->data<u) r=r->next; //确定最后一个小于u的元素指针r' y- L% G5 V Q
 if(r->next->data==u)6 h. ~: A( J" W- ?, Q8 z' j/ ]
 {9 l9 R) g" j: ~% j7 M8 o# a7 `
 s=r->next;
% p/ K) T4 d8 _2 J6 T* L, K3 C while(s->data==u)/ |* e! B" P* S2 l' h% L, S
 {
( d0 D# P2 {; G t=s;s=s->next;free(t); //确定第一个大于u的元素指针s/ H! q+ M7 F5 {+ l
 }//while
' S7 ? Y% |: ?2 g, S r->next=s; //删除r和s之间的元素
6 k1 f: W3 @4 Q7 R# S, ~ }//if
8 J+ t$ w- E) d7 q% P0 ?: X7 @: j while(p->data=u) p=p->next;
, O# Z# O4 U3 b& c+ |% M while(q->data=u) q=q->next;
& _) F5 z8 N- n2 ? q& T+ R }//else
) a$ t$ J6 {) K$ S3 N+ h }//while0 _+ ?7 e7 l5 h$ V9 \ ^& x# q
}//LinkList_Intersect_Delete 2.31 Status Delete_Pre(CiLNode *s)//删除单循环链表中结点s的直接前驱
/ _% D7 j3 w) r9 s{* A1 E: N# t& d4 @* x7 O
 p=s;
" |7 k. G' ^: s8 L4 v while(p->next->next!=s) p=p->next; //找到s的前驱的前驱p
; ^ W4 ^6 X" i6 `0 F$ o/ x p->next=s;
$ U% `) u+ m$ N' c( I% @ return OK;% F; x9 m' \3 q* B! v! g% i
}//Delete_Pre 2.32 Status DuLNode_Pre(DuLinkList &L)//完成双向循环链表结点的pre域! M* y( \: j' y, L1 B& W4 g3 r) k/ W8 N
{. O) W; o, R6 i1 M* `
 for(p=L;!p->next->pre;p=p->next) p->next->pre=p;
* e; ? z6 M4 W* E: Q return OK;
" @$ L" u' L. C/ {6 u6 ?* x}//DuLNode_Pre 2.33 Status LinkList_Divide(LinkList &L,CiList &A,CiList &B,CiList &C)//把单链表L的元素按类型分为三个循环链表.CiList为带头结点的单循环链表类型.
1 M# A t2 n/ ]+ T" t{% T! U. [: ~# }) h
 s=L->next;( I* A$ {: h; Q
 A=(CiList*)malloc(sizeof(CiLNode));p=A;( j+ N! z e: K* W$ X
 B=(CiList*)malloc(sizeof(CiLNode));q=B;
& |. ]6 m, @6 P- w C=(CiList*)malloc(sizeof(CiLNode));r=C; //建立头结点
0 h* L- m& v1 q9 d7 W6 ] while(s)1 k9 a) U* y Q3 k
 {
, ]7 z* r6 ^$ j$ v( t if(isalphabet(s->data))
; d' B9 C2 _0 B/ A$ N8 \; U5 i {" y* ~4 l( ^0 N! X/ F% e% I
 p->next=s;p=s;6 H9 M0 h$ A4 D
}
; l4 h' F# k% e3 T else if(isdigit(s->data))1 S& T% o1 x$ }0 ?
{$ ~/ f& B2 d: }/ i' ~# s8 f
 q->next=s;q=s;
- r0 P2 l# [2 l0 A t9 ^% \ }9 J# d' g: ]1 X8 `2 H' j
else3 f, c0 y5 e$ v8 {8 r! }+ A
{
( I- J n) ~/ A1 i: F" t r->next=s;r=s;4 X3 o( A8 e6 b, O/ O5 \
}( V$ W4 h( g/ @3 Q
 }//while* y" E: U' k+ ?6 v6 N2 A- f
 p->next=A;q->next=B;r->next=C; //完成循环链表! l) H/ f0 i I& N5 {
}//LinkList_Divide 2.34 void Print_XorLinkedList(XorLinkedList L)//从左向右输出异或链表的元素值
/ [8 \2 l: n' A) V% V{0 Y3 E2 f8 D; T% L. `# ]+ \# ~
 p=L.left;pre=NULL;+ i9 {% p. Z, J) q9 ?4 p* E# z- C
 while(p)8 i7 E5 m4 h3 o) X
 {, n, F5 Z& G- k' m+ k
printf("%d",p->data);# T2 b5 x5 n3 J" L' {6 X
q=XorP(p->LRPtr,pre);
+ y0 C/ Y, j% u- h+ N+ F' a pre=p;p=q; //任何一个结点的LRPtr域值与其左结点指针进行异或运算即得到其右结点指针
! D9 D4 G; @9 e2 j }
, A: V6 D5 X; S) _+ E}//Print_XorLinkedList 2.35 Status Insert_XorLinkedList(XorLinkedList &L,int x,int i)//在异或链表L的第i个元素前插入元素x
 c2 ^, F, D3 y, x{! l# W) w( a. Y2 ^. h4 G0 `
 p=L.left;pre=NULL;
2 f2 Z s5 B- E0 b4 ~: ] r=(XorNode*)malloc(sizeof(XorNode));$ w" ]* x- A, @" Z$ E
 r->data=x;$ Y2 ^( Z3 _$ O1 @3 }0 a) Q' q! }4 W
 if(i==1) //当插入点在最左边的情况- V& u( \. t, \2 |, W
 {) U$ K* { M3 L/ l& M: m/ ~0 C
p->LRPtr=XorP(p.LRPtr,r);% y' x! H3 [7 `% T4 W8 _# A( [% {
r->LRPtr=p;! b3 A6 f$ N; v3 u9 I# l9 u9 K* A
L.left=r;
4 w* x. t4 X9 W1 b+ A4 Y+ g4 U return OK;6 U/ O$ U% H+ s e5 Y! U1 @
 }
" s9 k8 D8 f+ N8 { j=1;q=p->LRPtr; //当插入点在中间的情况
5 d+ I3 m' `, D8 q# V while(++j<i&&q), m- J3 L3 |5 [- M0 D2 X
 {
; x1 g- }2 t% P) Y# S. l$ D# M& d q=XorP(p->LRPtr,pre);, D0 @* E4 H/ Y
pre=p;p=q;# g7 V; y% \$ m8 Z5 K
 }//while //在p,q两结点之间插入
# R: e1 Y: E, T4 s- S# D* c1 ]9 _ if(!q) return INFEASIBLE; //i不可以超过表长
% \1 t; t6 j, D$ l% E& F p->LRPtr=XorP(XorP(p->LRPtr,q),r);2 k0 R% f5 Y' K8 |( \4 O3 V
 q->LRPtr=XorP(XorP(q->LRPtr,p),r);
, [% J' C6 I9 j' t, u* P r->LRPtr=XorP(p,q); //修改指针/ ]3 B/ ~# S" R! o1 U
 return OK;
7 v" D3 h8 [6 y8 ]; g; N}//Insert_XorLinkedList 2.36 Status Delete_XorLinkedList(XorlinkedList &L,int i)//删除异或链表L的第i个元素: }2 n" z! z, `
{! `- f. x9 o( ?+ l5 j# V+ Q* }( \- \
 p=L.left;pre=NULL;
7 H d3 I/ Z! y if(i==1) //删除最左结点的情况# e" M: r0 K' U7 ?# J
 {' ]: G7 F& ] y/ q
q=p->LRPtr;! |; [2 j# _4 @. b+ }! e/ O4 G
q->LRPtr=XorP(q->LRPtr,p);
) `" y2 ]; v/ l+ E L.left=q;free(p);
: F) J7 T, `8 x3 `1 r$ M return OK;
: |0 g) m$ B0 S/ p1 i }
2 {6 Z4 U5 M l7 z) e# d$ B j=1;q=p->LRPtr;7 E" o3 n+ Y+ t6 ~5 `1 \7 o
 while(++j<i&&q)- ]* v: H% w/ B1 X! I
 {* \$ `: S' a* \% I
q=XorP(p->LRPtr,pre);
& y" R, z/ k1 t$ [ pre=p;p=q;: |8 w) l- B' r8 g) c& p
 }//while //找到待删结点q1 V( }( e. n; {' I# e' p; b
 if(!q) return INFEASIBLE; //i不可以超过表长
! O( ^1 x2 }4 Q; G6 M' M9 j if(L.right==q) //q为最右结点的情况# U5 p" ^* W# R& l. ?& L- x
 {+ B9 t9 @1 [/ D9 c4 D# A
p->LRPtr=XorP(p->LRPtr,q);- U: H3 o+ g4 p A6 [7 I8 k" q
L.right=p;free(q);
# l+ _$ ~4 C5 H0 M1 c* \. h8 i return OK;; y( t3 g7 \- ?' ]) F0 s8 _
 }+ x' n! r" n1 w1 M
 r=XorP(q->LRPtr,p); //q为中间结点的情况,此时p,r分别为其左右结点
 z! |3 P' B: i5 ~ p->LRPtr=XorP(XorP(p->LRPtr,q),r);
5 W( X. s1 p# x" W" I# c r->LRPtr=XorP(XorP(r->LRPtr,q),p); //修改指针
3 U2 C; l# Y8 \& @1 b- O. x free(q);
' D: [# R( Z/ |/ \7 U! P; Q return OK;3 L2 C) y2 {# B5 M! Y/ D1 Q5 {+ {
}//Delete_XorLinkedList 2.37 void OEReform(DuLinkedList &L)//按1,3,5,...4,2的顺序重排双向循环链表L中的所有结点% f2 S$ Y% d M* m% [
{
% ~9 Y7 c" Q3 L8 V- v p=L.next;
# _; z( L4 V# {- y' H, P while(p->next!=L&&p->next->next!=L)1 F- ?2 Y1 i: p# z" \) G5 B
 {
8 L! p, F' `+ d- d p->next=p->next->next;
/ I+ T3 P/ ?3 i5 |% Y+ r p=p->next;
! z, V& }( ~, L5 |# i5 f& y& d5 I; ^" P } //此时p指向最后一个奇数结点
2 d( c4 ?4 G4 u# M if(p->next==L) p->next=L->pre->pre;
: X$ a3 y% {: J4 p+ ~6 V: W else p->next=l->pre;- i% K. l5 {! H8 J6 n6 J; d& N
 p=p->next; //此时p指向最后一个偶数结点
0 L: {( I" V9 o5 _& ]7 ?6 H$ K while(p->pre->pre!=L)
6 u- X' f- l7 b+ \% i" M {3 s4 I: f8 d# [
p->next=p->pre->pre;
4 q& ?8 e6 u+ t p=p->next;" V! H9 j5 g: M! s2 A$ ?! o: ?
 }. c' E8 m; s; _" X5 z
 p->next=L; //按题目要求调整了next链的结构,此时pre链仍为原状4 _, G: _' ]- T1 `! a# p" d6 t
 for(p=L;p->next!=L;p=p->next) p->next->pre=p;
5 {- M# W) J+ S, w$ c L->pre=p; //调整pre链的结构,同2.32方法/ z3 n5 ~! s0 e \) t# A
}//OEReform
; j) c, H4 ]! v$ |* q6 K6 d分析:next链和pre链的调整只能分开进行.如同时进行调整的话,必须使用堆栈保存偶数结点的指针,否则将会破坏链表结构,造成结点丢失. 2.38 DuLNode * Locate_DuList(DuLinkedList &L,int x)//带freq域的双向循环链表上的查找! Z6 Q) H5 Q1 }6 `
{1 G! [. U5 \9 L' t' A
 p=L.next;
; c' c; ]# z7 T2 |' a9 W while(p.data!=x&&p!=L) p=p->next;
( H5 P( I" a' U6 K2 q5 ]8 j% h( q' S if(p==L) return NULL; //没找到
7 N" v5 }( F8 Q( n: h1 M p->freq++;q=p->pre;0 w0 I; e7 L: ?8 q& ~
 while(q->freq<=p->freq) q=q->pre; //查找插入位置
 if(q!=p->pre)
5 F0 }3 e# O5 X" h$ B- r& O5 F- m3 N {! X/ @+ R3 p |* i: K1 ~
p->pre->next=p->next;p->next->pre=p->pre;
4 S) s L, Z1 H! X" n7 _1 Y* t q->next->pre=p;p->next=q->next;
% H9 {. U2 y, G: A8 N" c( n0 B q->next=p;p->pre=q; //调整位置
) a* I5 O( ~+ { }
( L6 T; q2 j. \9 Y8 P A return p;
6 Q0 f3 F: V7 [ G6 G) a}//Locate_DuList 2.39 float GetValue_SqPoly(SqPoly P,int x0)//求升幂顺序存储的稀疏多项式的值* x, ^# B0 ~% o2 a4 b
{
/ W* S t" m, q$ U8 ~$ b PolyTerm *q;
7 L' W% r: h$ r3 R5 S) O xp=1;q=P.data;7 {; _ { o5 S! }
 sum=0;ex=0;
; g" b8 |. s% H$ i) g2 i- C while(q->coef)
7 V0 ?% ?9 Z3 \. B; o4 Q/ { {% ]/ N0 ]# c# ]9 Y9 v
while(ex<q->exp) xp*=x0;
0 r4 i1 `' [4 u; X3 _1 f9 K sum+=q->coef*xp;
; A* L" G; l" z% U q++;- V/ Z, O, U" w D$ P8 d
 }
% V7 t3 q" R7 {; L# \4 x8 L# x+ B& ^ return sum;
( B7 C/ ]: b: g+ | x}//GetValue_SqPoly 2.40 void Subtract_SqPoly(SqPoly P1,SqPoly P2,SqPoly &P3)//求稀疏多项式P1减P2的差式P3
- G) o3 o2 l* t, R3 H{
; h' y4 g" C" ^# h6 T/ ?& k PolyTerm *p,*q,*r;
( v$ m4 b- E/ O) H; ` Create_SqPoly(P3); //建立空多项式P3
 S, r+ r g2 f1 P, N p=P1.data;q=P2.data;r=P3.data;; k* u. D& _' ?5 v& u, X) F. A
 while(p->coef&&q->coef)
" h, `3 g6 c: v0 @/ w: t0 p {
0 g C( M' y" G" s2 \ if(p->exp<q->exp)
1 A$ K+ n; R+ `$ ^5 ~. ? {! W3 }4 [6 J, X1 h3 W( n0 n' d
 r->coef=p->coef;! g4 g/ R5 J( v0 o# {
 r->exp=p->exp;
+ l: o0 _8 j4 u1 i p++;r++;) ^6 P5 @0 |" o$ o# O8 N
}
6 Y2 s/ T" {3 }5 s( c1 M* a else if(p->exp<q->exp)' n% K' o9 F. M2 m0 m& Y
{4 i$ m& ^% i$ L9 D0 @6 B
 r->coef=-q->coef;- B: C/ J& s3 G) O
 r->exp=q->exp;
9 p5 m7 d p% n% s q++;r++;
+ O& [% e3 O' [- v3 H( ~' v$ i& ` }
3 e( ^, r+ d1 }, V else
: m, l& d; r! n( y- x {
6 ~& h2 T, w4 e/ ~7 {5 A; f1 \ if((p->coef-q->coef)!=0) //只有同次项相减不为零时才需要存入P3中
4 k5 U& u3 R( @% V; o# d, K1 ]6 Y3 k {
- S% K# R' c" V' \ S9 \ r->coef=p->coef-q->coef; {8 U" g- ]! S* G: }- s
 r->exp=p->exp;r++;
, L; t7 [, a" R8 u+ x, [0 x }//if
2 ~4 v; B/ P! Y {3 S2 X/ q p++;q++;! X( }9 Y, |& |
}//else
/ C& {; o5 y; w- j8 @2 Y) J }//while
& s2 i# \' ^1 G8 v# G0 B8 z5 g1 P while(p->coef) //处理P1或P2的剩余项
- n: z- }- ?2 S, G* s {/ b" M: H% N6 v% v0 O. t% Z
r->coef=p->coef;% `+ W! E6 e6 X
r->exp=p->exp;
; ^5 S6 E+ M/ a; l p++;r++;) |$ c' b. x/ ?* M) a8 U
 }/ O3 ]+ u! I1 W* M/ P
 while(q->coef)
$ q4 f/ @% _% a! B2 X2 K& Y {/ W$ Z4 J- D) {6 W; z
r->coef=-q->coef;
3 p, u8 U5 o4 e0 O r->exp=q->exp;, S8 l* E' s Q; W+ K
q++;r++;, r: e7 a. T5 @( m/ @1 C5 E
 }5 I2 ]) c7 j2 X& A' B# W: j9 N
}//Subtract_SqPoly 2.41 void QiuDao_LinkedPoly(LinkedPoly &L)//对有头结点循环链表结构存储的稀疏多项式L求导
/ k4 v) t( s! w; |- A' ?5 P7 u% g{
( o* B Y0 y" _) I6 x- s$ t p=L->next;: t S$ t4 W: I7 l' j& M$ [; w' G. S
 if(!p->data.exp)
& K& R! J/ g% i( R% _, g/ o {' }5 y/ \+ S+ n1 h9 I- T" G
L->next=p->next;p=p->next; //跳过常数项9 _0 |) E- Q" K
 }* c% K8 g9 x% O
 while(p!=L)
2 F( S% Q" P+ [/ e* O# a. W {6 F6 Z/ X D% q, r0 d
p->data.coef*=p->data.exp--;//对每一项求导9 ~ d! y( P4 M/ p' l4 c
 p=p->next;+ F7 N, I" f0 G3 v
 }3 E. F2 h+ H4 k( o& F/ S
}//QiuDao_LinkedPoly 2.42 void Divide_LinkedPoly(LinkedPoly &L,&A,&B)//把循环链表存储的稀疏多项式L拆成只含奇次项的A和只含偶次项的B- [! D* U" ~1 s9 P% x0 O* X: [4 P
{8 J1 v* s; I/ \# k
 p=L->next;
- S5 _9 b8 _* h A=(PolyNode*)malloc(sizeof(PolyNode));8 n5 c: H% Q: Z8 s
 B=(PolyNode*)malloc(sizeof(PolyNode));
 y- U* s; S8 x6 P6 n pa=A;pb=B;
0 u* C# ^* `0 h5 v# Z- l" i5 K while(p!=L)3 S4 C% Y4 o0 q% d9 G
 {
, {4 C/ Y. X, ~7 z0 s( b if(p->data.exp!=2*(p->data.exp/2))
* r) Q% J$ `; a) U9 n( q- r& X! e {
' c. o# d) A% V" ]; }9 M5 I& c pa->next=p;pa=p;
* j8 B) a& J8 ~- W) w5 i# \ }
: H# k) n% [1 Q9 ^6 f8 w+ u4 d else$ J) g% G6 o) w
{
$ n; m6 ?" f' ^$ m: f% K pb->next=p;pb=p;
# W$ i$ J& G p }
; N+ [* z4 z- @7 m8 ]$ q0 [ p=p->next;
/ R6 e, _- r0 j) q }//while
4 C6 c& {5 J/ B- n! F4 r- J pa->next=A;pb->next=B; % Z& q! l" T; M+ K4 H
}//Divide_LinkedPoly