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