查看: 4990|回复: 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;. r1 {- Z. ]" _3 ^- P
temp[k-1]=1; //初始化
( b6 ^( n; w, d# D3 w' G for(i=k;i<=m;i++) //求出序列第k至第m个元素的值
5 u& k9 B, \4 j2 p1 v; F" X {
6 r% P7 j' _! P; | sum=0;
" t1 n( r' ^7 M. p for(j=i-k;j<i;j++) sum+=temp[j];% ]8 p0 G# D4 n* Y3 @& j6 ^" u
 temp=sum;
) e5 a8 y8 L0 o } l0 b9 N9 a+ U: M6 Q A
f=temp[m];
, O$ B- [9 Q( s) w/ @( T }+ Q+ W S1 [4 o* c
 return OK;. _3 y0 {1 G( `0 K
}//fib
; u( v* X2 ?/ q+ o$ c分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m). % C+ F9 K: ?; l6 @7 J0 e; ]
<>1.18 + c+ r( v1 B" s: e+ V" H' s5 n
<>typedef struct{1 u0 x# o0 t9 D% v, r
 char *sport;
2 E% G. m/ V# C! K4 J n# g% y2 t enum{male,female} gender;4 x2 B3 c! W+ A* {9 j1 D1 a
 char schoolname; //校名为'A','B','C','D'或'E'
- O+ h# H, \5 C8 C0 Z char *result;
$ i2 U, d* m4 A0 F& \ int score;
, N6 h8 o9 B9 N9 \( R* @ } resulttype; 
: R, R7 ` ^9 N0 ^: v+ Z<>typedef struct{
; L& k o1 P# c) W# g* c int malescore;
! X4 [, T) N ^3 u' @7 a9 } int femalescore;5 T2 R/ s! V/ o' I5 j- F
 int totalscore;
* ~) r3 o1 i) R& m, Q0 q } scoretype; 
; t$ }; k2 t. C7 N( f6 \& U<>void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中$ j) I+ q+ b; Y; G6 c' }) k
{. {* {. s3 e+ g3 `$ O$ Z! ^
 scoretype score;; b" y3 z" a; p- P4 F
 i=0;# v) @7 ~' v% y' B
 while(result.sport!=NULL)1 ]9 Y) V0 m' A& Y3 e
 {
% ?& {, z9 y* x! h/ u& m# f o switch(result.schoolname)
- \* ]4 b, z8 G0 D. W {* `! \, M8 w# l- b, b* Q
 case 'A':: ?. `5 ?. s, y5 v1 E1 @9 g# k" i0 G
 score[ 0 ].totalscore+=result.score;& a) q; _1 q5 t R4 ~4 r1 p. K
 if(result.gender==0) score[ 0 ].malescore+=result.score;
7 [' h4 d& }# ^/ t else score[ 0 ].femalescore+=result.score;
7 _/ g- c7 a+ R: s' U7 \ break;5 h N* u+ z2 I. D5 `' U8 h" U( P
 case 'B':; ?% n0 [+ A* I" {2 p# M; I
 score.totalscore+=result.score;' E) d) c; M6 Q; f+ k }
 if(result.gender==0) score.malescore+=result.score;
# I6 D/ e" w' s. g" Y else score.femalescore+=result.score;
' v. b5 S5 ~3 q& Y' V0 C4 U5 v break;
+ @' V: W6 ]8 G0 `2 _9 ?$ o …… …… ……
2 b% `$ s$ L+ U5 |" ] }5 a5 p/ }; E$ s0 F9 i: B
i++；
* K3 Z/ d9 ~' l }) u' a' W: x. ?6 ]* K2 Y9 R
 for(i=0;i<5;i++)
+ q+ _ q" d4 J# v2 F {
2 V K& M A* [; ~( Q! ~, Q; } printf("School %d:\n",i);" U L4 T6 C% l' Q
printf("Total score of male:%d\n",score.malescore);$ s/ U9 u' @# U/ \
printf("Total score of female:%d\n",score.femalescore);$ j6 U1 M6 o' m9 ?* S; l
printf("Total score of all:%d\n\n",score.totalscore);
! j4 I0 c& }$ H% q2 l }
$ N" ?% `. }0 m/ z' E}//summary 
) q9 _, f- l9 {! E, ~<>1.19 
) Y9 X) t0 F( w7 t: N<>Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint& v4 X t5 p6 B1 L# z' E+ X: n+ W
{4 U' R% p( E" a( k: }
 last=1;
( [" j* r5 Q' g5 K for(i=1;i<=ARRSIZE;i++)
4 S7 }8 J' m$ P {
- p4 s" K0 v% @' j7 b0 [4 E0 f5 E a[i-1]=last*2*i;; a1 U# y. Z- g+ x6 [$ A% o: Q
if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;
; {9 ^9 C0 @& P1 w last=a[i-1];
& l8 y. ?( t" g, F* Q/ t. g) V return OK;/ E$ [$ u7 \8 ^: ~3 z6 _6 S
 }
0 }* G$ [+ T' w! k}//algo119
; v2 G4 ]$ C% h$ u分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. 
& |) F& |5 j/ t$ q% _+ |! v# @) O<>1.20 3 g& M$ e! ~; j% q: E+ m" ~2 {
<>void polyvalue()- {8 s3 k& w6 q! z' z
{
 V& U9 D( H, r0 x; M1 \ float ad;
1 ~+ u3 b6 V# u& ]& k float *p=a;# A* f* \, A4 |
 printf("Input number of terms:");
4 U+ z+ u6 {( i scanf("%d",&n);7 |/ R* o U# H: P7 Q! l. F- d: t
 printf("Input the %d coefficients from a0 to a%d:\n",n,n);/ i- z5 r7 H$ b0 ]
 for(i=0;i<=n;i++) scanf("%f",p++);* N) }6 A4 E5 r8 ~0 U
 printf("Input value of x:");
, z g) j! i* D, A7 w scanf("%f",&x);0 y$ ` B- g# s) r5 o" B
 p=a;xp=1;sum=0; //xp用于存放x的i次方
" q( W# Y4 e% J9 n4 G1 n% X for(i=0;i<=n;i++); H' A6 |1 p& a$ G6 D# |
 {
, T" {/ Z, w% z1 @7 H' }+ B sum+=xp*(*p++);! Q8 {' ^* c$ ^
xp*=x;
; L/ R9 u& L* ]- F }: Z' G( D z Z) L. S8 H8 f" G, f2 e
 printf("Value is:%f",sum);
/ L+ R+ I8 g4 Q, E) Q}//polyvalue
1 B, N4 S7 S @: S T. ~( h5 L H< >

zan

转播0 淘帖0 分享0 收藏0 支持0 反对0 微信

使用道具举报

铜豆子

0 主题	3 听众	22 积分

升级 17.89%

该用户从未签到

4^#

发表于 2007-6-20 21:54 |只看该作者 |招呼Ta 关注Ta

不是实习题的答案啊

我也说一句

发表

使用道具举报

布赖

4 主题	2 听众	134 积分

升级 17%

该用户从未签到

3^#

发表于 2004-12-18 00:28 |只看该作者 |招呼Ta 关注Ta

<

>很长呀<

>不过还是十分感谢

我也说一句

发表

使用道具举报

╃無名草╃

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

我也说一句

发表

使用道具举报

返回列表

帐号		密码		只需要一步，快速开始		注册地址	找回密码

《数据结构(c语言版)习题集》算法设计解决方案

浏览过的版块

发帖功臣

元老勋章

新人进步奖

QQ

电话咨询

关于我们| 联系我们| 诚征英才| 对外合作| 产品服务|