查看: 4972|回复: 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 R5 W3 M/ E2 ^/ v
temp[k-1]=1; //初始化
" Y. U- S/ E+ ~2 ]) }2 [/ \ for(i=k;i<=m;i++) //求出序列第k至第m个元素的值! w2 G" q( Z! P5 O4 J, B/ y! y
 {; H, F* l& g7 G
 sum=0;
. d2 P8 l+ A$ |: S: [ for(j=i-k;j<i;j++) sum+=temp[j];% C# j: w6 ^$ H$ d8 x
 temp=sum;
; g9 E$ M: q$ k( R }
' w Q% n$ \# d( U! I* y f=temp[m];, o4 o& M x- d. d* I
 }. T# N$ H) E9 F k _" i5 o( r
 return OK;
7 V' g, x( m/ f% z8 w}//fib
$ O- o! c1 M* w( r+ G分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m). 
6 c9 Y; N, T2 p<>1.18 
8 u8 g- G/ h9 L<>typedef struct{4 B: b# i! h Y$ c) M
 char *sport;# m% [: l' j7 f$ t' k$ ?
 enum{male,female} gender;
$ {3 p1 k3 M' K5 k9 h char schoolname; //校名为'A','B','C','D'或'E'4 Y- [+ R8 _4 h+ [: @+ Z1 E7 g
 char *result;
1 m4 `1 T# d8 I- ^+ h int score;9 f# v, p3 H$ @
 } resulttype; 
% l8 \0 O, {& p8 }* f<>typedef struct{
2 x+ u2 |1 f7 x! V2 Q8 w int malescore;
1 c5 w( t, N% n8 [. |8 x int femalescore;
8 S/ L7 C7 e7 N0 R- X% E int totalscore;
2 W; n6 O. J% [5 }0 d } scoretype; 3 b- z5 @! a1 K A' f% {
<>void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中
6 R8 G) y4 a' k5 t, w( P{
6 }6 Q# ?* {( x scoretype score;8 W d; @: k. N+ d6 \
 i=0;9 h% s: [/ `1 L. \. J2 I
 while(result.sport!=NULL)
% x) L0 o. T/ M/ J/ L {
 j4 M* {7 j" Z switch(result.schoolname): D" y+ i0 y, o. Y# c& A/ f! W% a" d5 y" ]! X
{
; `& b4 I% {0 P: X) }# {8 s. N p case 'A':
* Z1 ^+ [! [* Z2 i5 B score[ 0 ].totalscore+=result.score;
0 z7 X* k) b2 @- G if(result.gender==0) score[ 0 ].malescore+=result.score;
" o# Y! v' L; ` v else score[ 0 ].femalescore+=result.score;6 ?8 A$ y& \. p7 h1 \! K
 break;
* a; s7 i3 `; V' A2 p# ] case 'B':# Y" k" o; Y) }) S1 x; E
 score.totalscore+=result.score;& J3 p0 g0 E8 ]6 I% g$ M6 @' a$ e
 if(result.gender==0) score.malescore+=result.score;
* R0 B5 k, C u8 J3 W else score.femalescore+=result.score;5 `! i0 j" T6 |$ _/ E
 break;0 ^- y7 Y3 Z/ T" S
 …… …… ……
3 M6 L' Y' w" Y/ B }
1 _" a. z$ i7 A i++；
: N$ C) i9 C0 o! S" h }! V' G0 D) R H7 s# k7 _4 e ?
 for(i=0;i<5;i++)
) K! `. M6 q& y: [) Q3 I {
; ^! y V6 g/ }* X* K printf("School %d:\n",i);
 h# s; u) W/ f4 E2 A, | printf("Total score of male:%d\n",score.malescore);; G5 G; O7 A; ~7 F0 s
printf("Total score of female:%d\n",score.femalescore);
& o! q$ P0 l# P& M5 v2 k4 X" h" Q5 T, ^ printf("Total score of all:%d\n\n",score.totalscore);
% U1 m) O' A6 A& i/ H! E/ b }
9 K+ Q* v2 u# G V7 x}//summary 
+ f0 j3 V/ Z: O" D) I& p1 H/ V2 o<>1.19 + l/ \/ ~# B o+ y! F9 b/ x
<>Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint/ |! I2 }& F2 O, x
{
5 l" g+ Y& N) d5 E last=1;+ U0 d+ [: E$ K- ^5 F6 i% Y1 O
 for(i=1;i<=ARRSIZE;i++)
& ^3 N8 Z c9 I0 A( R {
: w: q3 T, U8 n1 L+ n$ c a[i-1]=last*2*i;2 Z) N% V' y+ S8 q: K
if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;
/ Y0 w5 U- q2 ~8 o; F) B5 n last=a[i-1];
return OK;6 d: X; @+ S* e
 }- D/ Q5 e- V5 T: y: X% T
}//algo119, }( M0 i# ?9 x$ F0 v% ^
分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. : `1 `/ H9 |* ~, a+ n" O( o9 g
<>1.20 
6 S2 ?/ ~3 I& Z& ^<>void polyvalue()
8 X" t% y% K: f{. ?4 i; o# M3 S- Z8 X8 m
 float ad;: I% f$ G3 ]! }; y
 float *p=a;
' x: X( \* y8 R4 d printf("Input number of terms:");
$ K( R; {7 h, N" C7 Y6 U2 } scanf("%d",&n);
: f* q, C% p1 P3 B$ Q2 k printf("Input the %d coefficients from a0 to a%d:\n",n,n);3 ~: z# d' U3 l
 for(i=0;i<=n;i++) scanf("%f",p++);7 v( W- y3 }5 u* ~# }( j9 Y; L
 printf("Input value of x:");
" C7 A" ^5 |% U( N scanf("%f",&x);
, U' T+ v* O/ M" [. p p=a;xp=1;sum=0; //xp用于存放x的i次方
4 ^2 o! v: E5 p# I% x# j* h5 b for(i=0;i<=n;i++)% P* U2 k; \8 L+ u+ q& v
 {. J' W( ^- c. c, B0 u
sum+=xp*(*p++); R' G- I3 r. R( g; |9 }
xp*=x;9 G. Y8 W- _1 H
 }
) x. m" C, ^$ h R printf("Value is:%f",sum);4 t, t7 `$ g3 g& q" S
}//polyvalue
3 B% C8 a% o- s< >

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