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