查看: 4791|回复: 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;; N0 S3 l, s' `) J% O4 L0 I5 ?0 ^
temp[k-1]=1; //初始化4 A5 ]) Y' B$ ?7 j1 ^' c
 for(i=k;i<=m;i++) //求出序列第k至第m个元素的值% g. y) r" f/ K c
 {
" l/ X1 Z& _7 Z% j1 W/ d+ S# ?4 @ sum=0;
' P: I" X' P, d for(j=i-k;j<i;j++) sum+=temp[j];) j* n% K2 b0 O1 Z$ c5 Y
 temp=sum;) {! a' e& w: A+ p
}
# A- }6 f: ~, l+ c' H f=temp[m];! S* [, {2 w3 q. g8 ~- X6 b
 }; ~, t% { |9 q
 return OK;
/ A( t7 ]( W r3 E1 X2 N& Q' Y8 J}//fib2 J/ L: p; U, V }7 T; {3 n
分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m). 
$ p8 o n1 k& Z4 J+ a- m<>1.18 # o" o" ?% x S' A
<>typedef struct{
0 S" e4 G- {9 a8 I; M char *sport;
, h5 S. }/ |9 Y5 @2 } enum{male,female} gender;$ g& l; F; o) l* {
 char schoolname; //校名为'A','B','C','D'或'E'
! L! y1 p7 C( {4 b: n$ e char *result;
8 E0 H" b2 W6 m int score;
* d4 Q% P4 N# Q; q' s7 y } resulttype; 
; X4 D, K. }+ N0 B8 x<>typedef struct{3 d- S" w# D2 x/ M6 B0 h
 int malescore;
3 O, W( L& [) }7 Y+ M int femalescore;
2 Y# u! e2 l* {# d! r8 a1 w8 c int totalscore;$ ]% V6 j$ ]5 Q6 j7 t! A* w
 } scoretype; 1 b, B8 Y9 R: a) s) x
<>void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中( h: k! l& l4 F1 U: G
{% ]4 k. ?# S A- ]$ b- {, }! C- k
 scoretype score;
+ d; y- Q* D% t; D! q2 D! s i=0;: {+ s, p( \7 Y( \1 I1 Y% T
 while(result.sport!=NULL)2 V, V6 c, K/ _- t P" h
 {/ N, u6 E5 Y3 g& g# V: x
switch(result.schoolname)+ H* G. c; H, E) U
{+ [' `% a& ]7 K
 case 'A':
" @* x& i, p5 h! I score[ 0 ].totalscore+=result.score;
* C' A0 n5 _" Q/ b3 W if(result.gender==0) score[ 0 ].malescore+=result.score;
1 Q: _. e. \+ h* _6 P else score[ 0 ].femalescore+=result.score;
: C- ?: K" d; Q) \3 i break;. p! H* n x/ l, G) l
 case 'B':4 Q% c: }! q( M, n2 A% n
 score.totalscore+=result.score;
$ {0 W% _; ]9 h' M* q7 c# z4 l- j if(result.gender==0) score.malescore+=result.score;1 ~: J! y+ q4 J, }, c
 else score.femalescore+=result.score;: ^& n: t' a7 N1 v d7 r
 break;
! f5 h) d& ?+ Y; u4 z. Y …… …… ……
3 J8 [6 q0 d8 B( {9 M. Z3 H5 X }, H7 z3 j; e P B8 t7 {
i++；% x# i/ [( N6 Z3 ?, M
 }' W3 ^" k* V) |
 for(i=0;i<5;i++)
2 z8 j* Z$ k- O0 W$ \$ X7 J {
: z$ @' v% b& e7 `6 j: G9 F9 A2 T printf("School %d:\n",i);
% U K. ^# s$ } printf("Total score of male:%d\n",score.malescore);
. T6 R" y2 @4 G$ o: @: ^" U printf("Total score of female:%d\n",score.femalescore);
5 L5 a* x' ~9 M; g- R printf("Total score of all:%d\n\n",score.totalscore);
2 g" u' r7 S! m( i; M }6 W/ e6 q8 K3 V5 @
}//summary - i, e) _7 |% r# D f3 r( r o
<>1.19 ( I! a3 w$ {( F
<>Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint, B2 y/ F- N" `6 c, x3 q3 w
{+ C3 I# _ E/ |& J: n
 last=1;+ J7 ?; Z) Q) P7 k3 j
 for(i=1;i<=ARRSIZE;i++)
) ]# n: Z7 a! ^) W4 v {
5 G1 w* ?8 U9 H/ J a[i-1]=last*2*i;! |- y& r4 a7 N' v; P( c1 z9 E
if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;2 c( \2 X7 Q* E( `8 Z! [
last=a[i-1];
6 {9 d! \, A& E& U- \ return OK;
8 B/ x3 q% O! w4 L: l }
! F, m. K5 L5 B0 `; O8 s8 h}//algo119: d; q3 B2 ~9 G4 X$ K$ \; K
分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. 
: W- q3 q3 _+ Z' `<>1.20 4 T5 L6 c- P; r
<>void polyvalue()
/ l. Z5 S9 J2 K6 ], _( I; P+ {0 {{. B" o, Z3 G# R1 `
 float ad; V& [0 Q, J& Y2 r/ z3 B
 float *p=a;6 |, P4 K7 d& d4 O' ?
 printf("Input number of terms:");" g; W W. Q" ]4 B/ r: s2 h
 scanf("%d",&n);# ^6 T) V8 D4 O
 printf("Input the %d coefficients from a0 to a%d:\n",n,n);
; j, Q' |: M; O+ w7 @9 h% J( Q2 v for(i=0;i<=n;i++) scanf("%f",p++);/ @1 [0 Q# G% F$ f
 printf("Input value of x:");* E. @8 c9 Q/ z; \$ O# F: b
 scanf("%f",&x);
$ L3 V+ l* N4 ~- L& y { p=a;xp=1;sum=0; //xp用于存放x的i次方
( d5 G( V/ I: { for(i=0;i<=n;i++); }: o9 J0 u$ c9 k1 j/ T/ J
 {& S0 W% x5 N) C$ t0 H
sum+=xp*(*p++);# f$ y3 q7 R6 l
xp*=x;7 P/ H3 w. C5 E+ V0 o3 I
 }
$ O3 w; E/ s' w2 B& h# m printf("Value is:%f",sum);
8 n( Z" C1 B% v S}//polyvalue: y7 B! y# e& H; q# v9 z% }
< >

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