查看: 4940|回复: 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;
! T) ?( R7 n0 F% _5 ~: Q8 H! K" R5 S temp[k-1]=1; //初始化
) Y: M6 s0 G; y8 T$ a for(i=k;i<=m;i++) //求出序列第k至第m个元素的值# T; }" P2 p' _$ L7 q. C! B2 ~! N
 {
- i0 v) K' m' W1 a6 [/ \! q sum=0;( x. @$ Z' [+ `& O$ M. M1 {; W
 for(j=i-k;j<i;j++) sum+=temp[j];
7 l6 J$ N6 T7 X- ~: q8 | temp=sum;
( [3 r$ t! q* ` }
/ g9 o, V) V. b# ] f=temp[m];
' Y2 i0 Y; {; N0 U Q }; k2 C$ p! X' r4 \, n/ W9 C
 return OK;
+ R$ Z9 a& g. G8 M4 e/ b}//fib
) @% U+ {2 [9 m+ b3 O分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m). 
8 x/ m& I2 E& N9 Y6 Z2 x7 v<>1.18 
* F9 a6 E) q5 J: T<>typedef struct{
3 o( X2 U) z; `9 M8 L# D char *sport;( E, Z4 U: Z* S* P
 enum{male,female} gender;* m$ S! F6 f/ p) n0 g/ O6 N2 p
 char schoolname; //校名为'A','B','C','D'或'E'! @2 R1 C$ N, _5 d) M
 char *result;5 ~6 E' S9 r9 j* A4 e
 int score;
+ v/ f9 K9 o8 f. @ } resulttype; . _% `5 H. R+ C$ L$ b
<>typedef struct{ h6 ~) Q( u' K" t/ d
 int malescore;
* B/ T: Z' q' M, s0 I int femalescore;
9 y+ r* a6 o2 u8 _ int totalscore;
5 U6 t4 i% G1 [* m1 L } scoretype; 9 c- [0 |$ S7 `7 }
<>void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中' J9 s( ^: X0 i& e \+ G
{* O; ]# _- X R( U: h; h$ w
 scoretype score;
0 _4 [2 T: Z, j3 O8 {7 h i=0;0 s9 \9 S2 x( L6 b) d+ X
 while(result.sport!=NULL)
! s4 v: ^2 `. B' H) K: i {
* e9 N. i) o" ~* M1 y6 K switch(result.schoolname)8 x" c0 N+ M% Q+ u( Q# ?2 G
{
+ w: X; Y3 K/ B: a: _( e case 'A':0 q' F( w9 ~* M# L
 score[ 0 ].totalscore+=result.score;
: N9 i3 T; v) E) U5 p) } if(result.gender==0) score[ 0 ].malescore+=result.score;
$ V0 Y$ G- g2 Q0 n+ s2 e0 i$ F else score[ 0 ].femalescore+=result.score;
; Z( d! ^" O8 q0 F break;$ P+ K5 ^1 U5 j2 W/ F; @2 U2 ~
 case 'B':
; U9 f( j9 q/ u7 L! E score.totalscore+=result.score;
4 Z' d4 g+ E7 w7 g if(result.gender==0) score.malescore+=result.score;
. ^* j! T: `: }5 B else score.femalescore+=result.score;; p( q* S! K# Q' x
 break;+ k! J2 n# O+ r: g' |
 …… …… ……
) ~/ J3 w$ B- A% L }
( s) G/ o- ~, Y4 L, u0 {# \# z, b i++；, S, v- e s7 c/ C9 t
 }( w$ X; ]5 Y8 D
 for(i=0;i<5;i++)
5 R0 C1 h6 e- D; } {2 J. F$ t1 a6 Q$ G2 \/ X9 k
printf("School %d:\n",i);' A( O) o) p1 @, V. V- V
printf("Total score of male:%d\n",score.malescore);
9 Y p/ _4 L1 V F2 Q5 ?" K* V printf("Total score of female:%d\n",score.femalescore); a. X2 V4 J. R
printf("Total score of all:%d\n\n",score.totalscore);
, ?/ p; e; [5 ? }
; H8 S+ p6 c0 p6 @5 v}//summary 
! V% t: N/ i/ z* F1 P<>1.19 & ^! z& l2 i' o9 w4 J
<>Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint
) d0 U/ U! `& l% L{& C- o' Q5 J* K- S+ c( U
 last=1;
 m4 G+ c2 i" p: \ for(i=1;i<=ARRSIZE;i++)
0 a6 g3 V2 Z& Z {
 c8 S# e' v5 V& u$ {' J0 T0 j a[i-1]=last*2*i;
. F0 r6 _3 X# u0 a4 T: i# |2 f! x' g4 { if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;
" U1 V" e: S* ~) Z! ~( O* j last=a[i-1];
% J8 E# \) x9 y6 D7 i return OK;
* g( o( j' V# ]% N) }4 f% e }
% L; f. W) U( J}//algo119
- E" v8 z- f5 m分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. : {, ?$ U) K" h, X0 r, E
<>1.20 
7 }0 X {: _" ~# h# Y<>void polyvalue()
$ c0 a4 Z$ }6 K1 M3 E) t9 k8 e{
' @9 U, |& ~+ T9 ~7 W( D float ad;
2 z! S: r; W. e) R% w5 [6 h9 C, n, T float *p=a;
% F9 j) {% ]( d2 j# i% p0 @ printf("Input number of terms:");
7 _) K- ]5 D# y3 \/ B$ l5 y9 B+ N scanf("%d",&n);
0 T$ _% n: c4 \. V8 U. D) [ printf("Input the %d coefficients from a0 to a%d:\n",n,n);
) w0 Q" p% Q$ K$ k. U2 J5 A for(i=0;i<=n;i++) scanf("%f",p++);
0 t% _6 @& f+ |( c* m printf("Input value of x:");& N; x- |9 r4 g) b. j n: I! l
 scanf("%f",&x);
* R# Q, n0 W* Q- u3 l p=a;xp=1;sum=0; //xp用于存放x的i次方
# k7 n2 M. F8 @5 T ^7 |( h, q for(i=0;i<=n;i++)
 C5 d" N8 ]0 Z. Z* S$ I {
5 B, V; a2 _5 _/ ? D6 K+ P- p( J) J sum+=xp*(*p++);
* ^+ P2 N* B$ i [9 Y5 h: l; y, N xp*=x;
. [) Y! C9 L3 v' A ?4 z }8 F% c9 C; c* I0 k. Q1 X
 printf("Value is:%f",sum);
1 }5 B6 ]6 {' E& C$ F# s9 T}//polyvalue2 j/ T- _# C# h2 \ A6 i+ R* S
< >

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

我也说一句

发表

使用道具举报

返回列表

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

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

浏览过的版块

发帖功臣

元老勋章

新人进步奖

QQ

电话咨询

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