查看: 4974|回复: 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;1 z, `! B5 Z" H2 J: ]. d* @2 J
temp[k-1]=1; //初始化
6 k7 `' l, f& R& R: G2 ~ for(i=k;i<=m;i++) //求出序列第k至第m个元素的值
0 f9 P) a! ~' \; [% ^% E {7 p- W5 E( x8 l% f$ c' c
 sum=0;
, T- P$ ^/ N8 I5 G8 b+ x for(j=i-k;j<i;j++) sum+=temp[j];2 Q) n( s9 B1 f1 s5 m) r
 temp=sum;; E; t: O& n" Q, N
}/ j& g# A) E3 n; L" n$ g( `1 b
f=temp[m];
. U7 P1 I" f. X4 }: v% f! O }
; h" A, w. P5 U, ` return OK;( v/ n2 {+ a. {
}//fib' Q+ W- P4 ~" q3 i+ v& C
分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m). 
: x# R' W& f* s# U, q<>1.18 
/ j- O1 j) Z7 S<>typedef struct{
+ A0 C- D8 G# k6 A& I% j9 _ char *sport;
9 X7 [4 y* D9 i" v' f enum{male,female} gender;" G2 [" E$ y+ x5 n% c5 ~- u+ }
 char schoolname; //校名为'A','B','C','D'或'E'5 F! O& B3 k" g$ @
 char *result;! t6 E/ p. T+ t z2 h( S2 |
 int score;$ P( ?% d) h0 r
 } resulttype; 4 y- n" L, ]& o. Q
<>typedef struct{8 L0 r! d; n% F6 Q, l
 int malescore;6 G2 t6 D, ?6 R1 e. Q! _1 Z
 int femalescore;
, v* Q2 W: L/ S/ Z5 q) W! D int totalscore;
- A+ ^- k- S: t7 Q } scoretype; 
- z1 Y: [1 h* N6 C) g: i<>void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中5 [' \/ k- e4 e" T
{1 ~: f8 O" w/ U7 W. L; \+ G( y
 scoretype score;9 {! r6 D- F: }/ [& D; N6 u H
 i=0;
9 y9 K8 e4 R* D \2 R" D% ?/ [ while(result.sport!=NULL)9 s. s9 ^" J* z/ R. Q4 P# n! V
 {: m8 B4 T, o, A! h1 `% d
switch(result.schoolname)
: ^! k7 h Z5 ]! Y {6 x. w9 y# `; y9 r+ l
 case 'A':; m1 F4 }; x: b% p, A" r
 score[ 0 ].totalscore+=result.score;
& {* F# Q/ s' ^ if(result.gender==0) score[ 0 ].malescore+=result.score;
4 m c- e# ]2 f8 ? else score[ 0 ].femalescore+=result.score;
( b9 Y& s, F. B break;+ {4 j/ g2 C7 [' I# u6 @
 case 'B':
9 |5 v2 V1 P' l score.totalscore+=result.score;
6 }2 P! g* l6 A+ ^% D5 u if(result.gender==0) score.malescore+=result.score;
- K3 a0 N( h; B ~+ b! e1 Q else score.femalescore+=result.score;
0 c2 m% ]( O, } V0 D6 [ break;
, [4 J) `( j6 h: ~+ ?/ T$ ]6 O; n: b …… …… ……1 K9 A: O+ u% v( o! }
 }
* @9 z% _# s0 |/ |' {& Z i++；' f2 z) c$ i1 v
 }9 V4 H2 y, w4 @% J! u, z. M
 for(i=0;i<5;i++)
( F$ y* e, z' O0 i; J8 ^( v; g {
. T! u4 {5 |. w/ z# k: K printf("School %d:\n",i);1 U# Z# N) ]% v" [) N/ W
printf("Total score of male:%d\n",score.malescore);
3 ? ~$ R. I, x' o- L; ]- L, \ printf("Total score of female:%d\n",score.femalescore);
1 R% Z1 U6 Q0 ?0 f& l* Z printf("Total score of all:%d\n\n",score.totalscore);
- w) @( P# p3 _ }& ~5 e( P$ m8 N/ ^* n5 l
}//summary 0 S$ Q* L4 ~6 P3 ]1 k* v
<>1.19 
1 v) B% |( v$ x; B8 U- g5 I2 {<>Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint
! p( C$ |" }6 M1 {3 I `{( ~) X( p5 U. S+ K4 n
 last=1;
& M. x- @( I1 A7 b% Z$ h for(i=1;i<=ARRSIZE;i++)5 O( ^4 `% E- {2 f' e- o- H$ x" h
 {
& ?- D& m3 d- ~( }! A a[i-1]=last*2*i;' w2 ^0 \2 s) S& V$ J" d; k
if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;
$ b5 A1 V; M* u0 S+ T4 B7 y, F last=a[i-1];
( Q) m$ X) N1 X1 ^, C7 x: v5 W return OK;
7 n' i1 t0 [* t: `% p ]1 y }2 J7 Q, ^3 U& y/ w' x$ x
}//algo119
7 _. t+ ^0 U% y/ L& I6 P分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. 
5 P; Y3 x. F% o5 q<>1.20 
" y/ k& ~4 D' j' ^/ f<>void polyvalue()
0 f# H+ |2 C1 k2 L) y) ~; ~9 j9 G7 g+ r{
! {5 n% f; F$ b6 R/ c/ J N float ad;
# D" I/ S1 ]/ X5 I# l float *p=a;& @8 S3 f* n1 _+ ?
 printf("Input number of terms:");
- S6 L( n2 r1 m scanf("%d",&n);
2 t4 j6 C3 t+ K6 C5 B1 H printf("Input the %d coefficients from a0 to a%d:\n",n,n);( y8 S# O1 T( C5 N8 v
 for(i=0;i<=n;i++) scanf("%f",p++);
* K+ j, Z$ }' G printf("Input value of x:");: q/ @0 c( \% ?$ R' T
 scanf("%f",&x);
( H0 L; S: O1 K. k) q p=a;xp=1;sum=0; //xp用于存放x的i次方
) f9 N' o$ r+ Q b+ q! a9 A5 H for(i=0;i<=n;i++)3 f% i( a: }" ^* L8 T
 {
# }2 |6 u4 i; J! J sum+=xp*(*p++);
0 i% S/ A+ N1 z- z xp*=x;" p) v/ h& l k. y. C5 \) d [7 t
 }# V6 G0 ^8 Q( a7 h$ k2 W" Y- u8 t
 printf("Value is:%f",sum);
" ]0 K: v' r/ k}//polyvalue1 y, l% ^0 L- ?
< >

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

我也说一句

发表

使用道具举报

返回列表

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

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

浏览过的版块

发帖功臣

元老勋章

新人进步奖

QQ

电话咨询

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