数学建模社区-数学中国

标题: 《数据结构(c语言版)习题集》算法设计解决方案 [打印本页]

作者: ╃無名草╃ 时间: 2004-11-28 18:02
标题: 《数据结构(c语言版)习题集》算法设计解决方案
<

>说明: 
<

>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;* w7 H& ~+ ~2 S4 t' C* Y/ k
temp[k-1]=1; //初始化
5 K% m7 z: k/ E. X r) Y9 n for(i=k;i<=m;i++) //求出序列第k至第m个元素的值
1 U( ?' s# U$ K' H {
) l% A0 |; x9 W0 g) Z sum=0;2 b8 Y' ^9 C5 W, w4 n5 l7 O# C) @3 G5 D
 for(j=i-k;j<i;j++) sum+=temp[j];4 R, \7 k. d5 w2 s$ }
 temp=sum;
- a. R. R( e: n! j* ~) B* _2 y1 V }
* D4 {# C% m# n2 f0 Z f=temp[m];& u* ]1 w {1 V9 `- P& M/ }
 }+ p( K' z- d! S* Z, o% @
 return OK;
. ^9 [8 g% X1 j}//fib
4 O6 s( Q6 q' l! v# |分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m). , M' r/ d% i1 v* m2 ~& N/ S9 ]
<>1.18 * F0 `) z4 D# u/ U% T; R/ m' H
<>typedef struct{
) ~8 e: w6 H- D: V6 ?9 z char *sport;
" x% \" z' R' ?# Z enum{male,female} gender;5 {) p& _- g* R
 char schoolname; //校名为'A','B','C','D'或'E'8 k/ _6 M3 @: Y; b7 z* k
 char *result;
- x0 x- \! b- U int score;. o: E5 `/ n' z& p2 u$ q
 } resulttype; 4 U6 a! D1 c5 Z) f3 F- `! ~
<>typedef struct{
5 |7 s3 y5 E9 g' l int malescore;7 z0 p9 ]) c v
 int femalescore;- q7 r x: F0 F& ]# N/ g
 int totalscore;8 i+ Q+ w) y: Z) ~( V5 {
 } scoretype; 0 U: k+ d6 c" M! p5 _
<>void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中
8 n2 Y- G( \7 Y- y1 B{$ W! Y& n( j a# Y W- _
 scoretype score;0 y* D% {$ S$ \# p/ ?) L
 i=0;. B1 d' e5 C3 }0 ]5 R
 while(result.sport!=NULL)$ V" ~ U( t8 R, y& z
 {% ]& n4 E. G) }" x9 C" g
switch(result.schoolname)- _% e% q. m, k
{
: y3 F# E% h' B1 L- T$ |- J2 N* ^ case 'A':" Z8 ?7 U4 m* t- ~0 K# R
 score[ 0 ].totalscore+=result.score;
8 K% Z" B! Y' i( X if(result.gender==0) score[ 0 ].malescore+=result.score;, E3 `# y. g6 o5 ^8 i8 w( q
 else score[ 0 ].femalescore+=result.score;" ?0 n& K% e: I
 break;
6 I% E8 v+ ^. Q9 e$ Z( o' e! R case 'B':
! c9 A* i* v9 [ ^ score.totalscore+=result.score; `! p$ G# f4 O! G4 p/ P1 F) s1 X
 if(result.gender==0) score.malescore+=result.score;+ G% Q0 v6 M5 b( y
 else score.femalescore+=result.score;
. z# ?& o. K6 t3 s- ^9 h/ O break;$ m, \! m% c' N ^4 z
 …… …… ……! q8 i; k0 j' M' g4 i E* d
 }
3 P8 ~( @8 S* Z. t; u2 o i++；
2 F! V, |' ^7 c9 ~" S }
+ t: n/ _% h* K6 V2 L# ^6 F' q for(i=0;i<5;i++)
: C+ {$ B$ a6 {; k6 H { { L% @9 M t F) V
printf("School %d:\n",i);! F" l Q; O R
printf("Total score of male:%d\n",score.malescore);
6 R& ]& a6 m7 B0 n9 x" i printf("Total score of female:%d\n",score.femalescore);
; W0 W- c, j$ e1 _- x2 C printf("Total score of all:%d\n\n",score.totalscore);
3 ~$ h7 U. }- J8 {% ~& m }8 j* h) d. h+ Z8 M$ o
}//summary 1 [: e5 E! L8 h
<>1.19 ; [$ i& ^" [& z/ ?
<>Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint
8 X8 a* x7 u9 K8 l3 K. M{
- a5 V A1 Y. p4 Q2 G0 U1 e$ m last=1;
 H S( Y) q2 A0 L. a/ G for(i=1;i<=ARRSIZE;i++)) @" f7 m4 t Q
 {2 U1 Z2 c1 p: W- ^; f" x8 A
 a[i-1]=last*2*i;# ? _5 l |4 w8 f3 Y& h2 Y
if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;& O7 t% S3 U- e8 D, D2 J6 w; t
last=a[i-1];2 l" ^# ]2 ]( \8 P( M3 B) c
return OK;
( X r8 V! p0 ^" ?% ]% H }0 x9 ^$ j8 [1 V8 d+ v$ q W0 [! o
}//algo119
4 {9 {5 }8 M" r6 ?$ }# s$ c4 A, X分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. 
7 J8 @, H F3 e$ Y: }5 f<>1.20 , r; {' a; y+ R4 K
<>void polyvalue()( Q7 V9 r8 F0 n% T0 s
{
" P: l6 h- S, B+ N) _; U2 l: u float ad;
; \$ F, P1 v* h' c- K1 m$ r float *p=a;6 I+ Q+ d9 @, j
 printf("Input number of terms:");
. d+ f. p- `. V3 u# z4 { scanf("%d",&n);
: A2 G) j- }/ k printf("Input the %d coefficients from a0 to a%d:\n",n,n);5 m2 G0 z3 f- V! M0 m' F& B
 for(i=0;i<=n;i++) scanf("%f",p++);
+ o4 J/ I3 T3 ^3 F! t. C2 E7 h printf("Input value of x:");5 j- N1 l& L/ X# D! x1 D
 scanf("%f",&x);7 L# D! o, o& [$ t
 p=a;xp=1;sum=0; //xp用于存放x的i次方4 D5 y( v" ? l
 for(i=0;i<=n;i++)6 i3 Q, A+ Y. }
 {
3 ?: S9 [7 R7 u, N- O( i& J sum+=xp*(*p++);
, ~6 z" E9 Q L \- S. L8 c- P xp*=x;+ T$ L' g5 E8 q E6 A) [
 }
9 z; T% n: O$ a, Z3 e0 ? printf("Value is:%f",sum);, Z# }& z! `7 {2 s. k
}//polyvalue
& N' d: |9 |: b9 z! I; {< > 
作者: ╃無名草╃ 时间: 2004-11-28 18:16
< 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个元素8 A/ d% P, C" ]0 U
{, ~/ h# R# D& }* d5 s
 if(i<1||k<0||i+k-1>a.length) return INFEASIBLE;# ] z9 o3 B3 _ a& R' A. Z5 S
 for(count=1;i+count-1<=a.length-k;count++) //注意循环结束的条件
) E* D' M& n6 B. P* ^ a.elem[i+count-1]=a.elem[i+count+k-1];% k) A( p0 Z6 J- y
 a.length-=k;
8 m0 {9 |1 S O0 c* }9 u# ^ return OK;
9 C& B& M5 X2 Z }}//DeleteK <>2.11<>Status Insert_SqList(SqList &va,int x)//把x插入递增有序表va中
) i; g8 U4 W6 B+ p{) K" l% b" u* v0 C
 if(va.length+1>va.listsize) return ERROR;. u( \- O, B0 M: y" W* t
 va.length++;
# p: g e' \* ^/ l% m" H( @ for(i=va.length-1;va.elem>x&&i>=0;i--)
3 m8 l; `0 e0 Q' U8 t va.elem[i+1]=va.elem;
5 k# `: S: R7 v6 N va.elem[i+1]=x;
' d+ ^0 R2 O6 \/ _1 a return OK;
0 \; D8 P5 d( o, R' m/ |}//Insert_SqList <>2.12 <>int ListComp(SqList A,SqList B)//比较字符表A和B,并用返回值表示结果,值为正,表示A>B;值为负,表示A<B;值为零,表示A=B, k2 W; ^0 q* T1 D$ ? w4 J
{1 `( T4 C2 j+ n
 for(i=1;A.elem||B.elem;i++)4 ~" H# g9 d$ m) W2 S. O4 N
if(A.elem!=B.elem) return A.elem-B.elem;
( r! U; T' `3 Q0 n& C) K+ j return 0;+ h( ^# }3 Y: }; A8 V: |* [
}//ListComp <>2.13 <>LNode* Locate(LinkList L,int x)//链表上的元素查找,返回指针' V' i- M* a* {, C m
{
4 b# p3 d, f1 Y/ Z! l) k" S- A for(p=l->next;p&&p->data!=x;p=p->next);6 x" ~( H5 V9 |' m3 u
 return p;
0 I2 L: p$ d; A- }+ f* Q+ C! A3 B}//Locate <>2.14 <>int Length(LinkList L)//求链表的长度
8 W; q/ u3 A* V. R) h) k; S% W# A{; ~; O* a8 ^( w% c' f0 |. K
 for(k=0,p=L;p->next;p=p->next,k++);/ X% ^& v( g, [) {+ C
 return k;
9 i4 c8 x7 }* y# w2 H6 o}//Length <>2.15 <>void ListConcat(LinkList ha,LinkList hb,LinkList &hc)//把链表hb接在ha后面形成链表hc, Y1 q" x! e: @1 S
{% [4 E5 V, v0 t' L6 M3 t; ~
 hc=ha;p=ha;
5 q+ k6 M( N( o0 s7 B. s$ n while(p->next) p=p->next;: f% F$ \4 H/ l6 c; a4 |( \
 p->next=hb;
8 T" w! b8 v( Y; t& k( {}//ListConcat <>2.16 <>见书后答案. <>2.17 <>Status Insert(LinkList &L,int i,int b)//在无头结点链表L的第i个元素之前插入元素b
& R2 X8 d$ p/ b- q! h5 B{5 e5 i5 R5 j# j( y
 p=L;q=(LinkList*)malloc(sizeof(LNode));
3 q' @, j% U6 \5 W3 B; k' a q.data=b;
7 P) f# V v# f3 @ if(i==1)9 @7 z4 Y' w) S
 {
3 b4 X2 |! @+ S4 f" J1 P1 L, E q.next=p;L=q; //插入在链表头部
; u7 ^8 k0 G9 \/ r [ }
6 R" x/ }9 M: ? else
& F0 d" T2 e: [1 K+ f' H5 | {
( u$ e# d# u/ M/ t. P% a while(--i>1) p=p->next;
' U% k$ Y) o: g: P, X' M q->next=p->next;p->next=q; //插入在第i个元素的位置
' I5 R0 ]+ z m* p0 Q }$ k- ^0 E# _9 L% U$ t$ r9 g
}//Insert <>2.18 <>Status Delete(LinkList &L,int i)//在无头结点链表L中删除第i个元素
" @8 }5 Y3 i+ |+ t{
: v7 `: ^' J6 G9 t+ L/ q" y if(i==1) L=L->next; //删除第一个元素
% H4 U; N& q ]; p0 V else9 Z% H# c$ p9 t: ~& C- F8 @+ M: `
 {+ c/ O: K7 n. A1 {4 `( W- @9 t, S
p=L;" Z( s1 S: _! O/ c2 d8 c
while(--i>1) p=p->next;
5 l' r: a( n: x$ q p->next=p->next->next; //删除第i个元素
9 F7 R. a" B: u# @. C8 [# _; F4 `) n }" Z9 L* r1 x$ z- l( M% Q! w3 p
}//Delete <>2.19 <>Status Delete_Between(Linklist &L,int mink,int maxk)//删除元素递增排列的链表L中值大于mink且小于maxk的所有元素5 I* ?2 q7 ` d+ q6 T C
{+ I. B0 f6 Y7 \9 I4 w
 p=L;
* J, Z; ?4 R6 w4 r6 i while(p->next->data<=mink) p=p->next; //p是最后一个不大于mink的元素' h |7 q+ m; C9 y
 if(p->next) //如果还有比mink更大的元素
9 W% ~) s6 [6 s5 Q7 Y3 H5 D! j {
3 D1 b' x& l/ O9 F, r2 R G. o q=p->next;, q/ `7 ~( q, V* D- Z! e
while(q->data<maxk) q=q->next; //q是第一个不小于maxk的元素
: {, u7 s2 R# b p->next=q;
/ e1 s! e: p$ B! m }8 h: W" U. k ?/ g* {
}//Delete_Between <>2.20 <>Status Delete_Equal(Linklist &L)//删除元素递增排列的链表L中所有值相同的元素
6 d+ I; L [ o: S$ _{
- }: c8 t2 G" n8 |2 M p=L->next;q=p->next; //p,q指向相邻两元素1 R3 G# V$ t ]( x3 X! G
 while(p->next)& Q3 `! `) l$ t% H+ E5 \" y" }
 {
! W" e! t: O5 r6 s9 | if(p->data!=q->data)3 }- a8 `0 E# ~: V* U" ~, B
{
% G* j6 O& w. A! b$ ` p=p->next;q=p->next; //当相邻两元素不相等时,p,q都向后推一步 y- a, A( ?9 }
 } c4 V3 A- D* b9 n5 i5 m* E% z' v
else
* c4 s0 {- q. x {
0 d0 |2 o! y# A0 N- h) y' A while(q->data==p->data) " L4 ?* R. ^* a' X" N2 r
{7 |7 D- v( y: q' S. i; ^. C8 t
 free(q);: o2 w, ~8 b) \- ^% L
 q=q->next;
6 `$ R5 L# C1 l4 `! g }, ~5 _ e" C( Y
 p->next=q;p=q;q=p->next; //当相邻元素相等时删除多余元素
$ ~- l) p2 m4 U0 ^: m! | }//else
+ g9 e% Y- M' l. i/ G4 x# x }//while
7 t: N# I! U' m6 ^$ U \}//Delete_Equal <>2.21 <>void reverse(SqList &A)//顺序表的就地逆置
0 A. M. f0 z1 N. v, i! Y{8 u2 ?& s/ o( N
 for(i=1,j=A.length;i<j;i++,j--)
! M Y: h5 P5 y8 ]6 k A.elem<->A.elem[j];
' o# y7 l" R& k}//reverse <>2.22 <>void LinkList_reverse(Linklist &L)//链表的就地逆置;为简化算法,假设表长大于23 F# O# K* s! o% C' K
{2 a Y0 r6 j& D2 v
 p=L->next;q=p->next;s=q->next;p->next=NULL;
3 @3 Y/ `( M4 l while(s->next)$ O) U" v: D$ ?: V5 [8 s# |5 d
 {
3 _7 i" J/ u9 x q->next=p;p=q;
+ U: O1 F& G H0 W8 G q=s;s=s->next; //把L的元素逐个插入新表表头* t" n2 o6 x. O$ n6 K% S3 b
 }
1 B" }7 f: q. P q->next=p;s->next=q;L->next=s;
" I% K: i: {: H9 ]8 a( S# q% D l}//LinkList_reverse
0 S1 N1 }6 i V' Q" w( q1 Y分析:本算法的思想是,逐个地把L的当前元素q插入新的链表头部,p为新表表头. <>2.23 <>void merge1(LinkList &A,LinkList &B,LinkList &C)//把链表A和B合并为C,A和B的元素间隔排列,且使用原存储空间
& _( b5 P! Z; q4 n& U- g: ^{
! @: o7 C; K" p p=A->next;q=B->next;C=A;8 G* D" h Q( d2 r! G# @
 while(p&&q)4 C$ A+ u2 Q3 K* S9 c
 {
$ { D$ N1 Y% N& P s=p->next;p->next=q; //将B的元素插入
1 |6 h9 E/ t# F f0 ?& n U8 l if(s)
" o. q" J) k$ T/ [. h- R" |3 m {
7 I; S. X6 T! U3 c& l t=q->next;q->next=s; //如A非空,将A的元素插入
 }
& m# n4 n* V( v5 t p=s;q=t;
8 Q/ ]4 ?3 Z) E6 \0 P2 ^* J }//while' J, s1 k1 s& O" O5 m
}//merge1 <>2.24 void reverse_merge(LinkList &A,LinkList &B,LinkList &C)//把元素递增排列的链表A和B合并为C,且C中元素递减排列,使用原空间' ?2 C$ h% p( D' ~ ]
{- Q" |, l* t0 y( \7 F
 pa=A->next;pb=B->next;pre=NULL; //pa和pb分别指向A,B的当前元素& k _! T M: \
 while(pa||pb)
8 s* u6 q i0 E, ^, M, X( p {
7 B1 g3 x; f$ d if(pa->data<pb->data||!pb): Z# Q" B: p; f0 p3 R* I
{. u4 ^+ N! n6 ~2 E0 L G. z2 \
 pc=pa;q=pa->next;pa->next=pre;pa=q; //将A的元素插入新表& q" a- P1 e" E2 U" ~
 }; W" L9 N7 p5 G
else
( O& }$ P) u' R. q0 U/ M9 I: S {
8 |2 b5 |, y7 f- |! v g+ k pc=pb;q=pb->next;pb->next=pre;pb=q; //将B的元素插入新表
1 p! r& Y3 Y" M% ~; I }
% _2 Z' l+ Y; d. u4 K/ s! p- S pre=pc;$ N) _0 y! A. W) s# W$ g1 a& ]0 a
 }5 \, H+ {' a$ a& T) e5 \1 \- y
 C=A;A->next=pc; //构造新表头- x2 l( \( x( g `/ Z$ A
}//reverse_merge
* E; |2 S- O0 o分析:本算法的思想是,按从小到大的顺序依次把A和B的元素插入新表的头部pc处,最后处理A或B的剩余元素. 2.25 void SqList_Intersect(SqList A,SqList B,SqList &C)//求元素递增排列的线性表A和B的元素的交集并存入C中
' A9 J# C3 q7 i. l: `3 h{4 @: F3 ^8 n7 a
 i=1;j=1;k=0;
" a# L% h3 v' [6 X while(A.elem&&B.elem[j]). P# z/ P4 s# l4 S, g: n* R
 {/ F5 D {8 J. ~0 L' x/ E$ g M- c
if(A.elem<B.elem[j]) i++;+ E) N- b. i) m5 F$ w9 O/ h/ o
if(A.elem>B.elem[j]) j++;+ V1 d2 U1 {& Y! j9 R% V' v1 C8 h( o
if(A.elem==B.elem[j])
0 q& L" n5 V2 z {. i; {* U" s" g: Z1 y
 C.elem[++k]=A.elem; //当发现了一个在A,B中都存在的元素,% G3 C) o X+ U
 i++;j++; //就添加到C中$ D# ?0 u- o8 s, p1 F- p4 R# z
 }3 N0 N+ K9 L- H. q8 L. S- q0 Q
 }//while
! s9 g8 p' c" f7 ?+ g& U! @}//SqList_Intersect 2.26 void LinkList_Intersect(LinkList A,LinkList B,LinkList &C)//在链表结构上重做上题8 [1 z- M5 \& R( b
{
7 U8 D2 [2 F! e p=A->next;q=B->next;
9 ^7 f$ o% \0 N! B% | pc=(LNode*)malloc(sizeof(LNode));
7 Z$ e0 A% q$ h5 L0 l1 o while(p&&q)
! Q4 H, ?0 L- w' ?( N {+ F" x" Z1 r1 ]6 |5 l
if(p->data<q->data) p=p->next;8 A% V/ x- |: j
else if(p->data>q->data) q=q->next;" a5 }! _8 _4 g' b; f
else
4 D, B; _" J+ U4 R4 h {* Z& v5 P& B6 T/ I) B- s/ k
 s=(LNode*)malloc(sizeof(LNode));6 Z3 y7 u3 x1 l. f
 s->data=p->data;# V r5 @- f7 w& \" ~1 N
 pc->next=s;pc=s;
6 ~2 x8 i2 L% f! W" B' c p=p->next;q=q->next;$ P0 L) O j5 m5 e5 D5 ?+ e/ {* B
}
+ Q d7 l2 X! N: l% {2 t" J }//while
. C* I, w, f Y C=pc;# w! `7 f/ ^. Q' O+ d3 N
}//LinkList_Intersect 2.27 void SqList_Intersect_True(SqList &A,SqList B)//求元素递增排列的线性表A和B的元素的交集并存回A中+ x, i8 h4 T& P, w1 F A
{
' r( S! L+ s: L& _5 m- c i=1;j=1;k=0;! q3 w G1 p0 ~! X. b3 D
 while(A.elem&&B.elem[j])
& `2 k$ |2 }& i$ k3 G' C {; ?! m3 ~. P h! K1 a& M. }' f
if(A.elem<B.elem[j]) i++;( b% {( P$ R( r) ]
else if(A.elem>B.elem[j]) j++;
+ M% F/ v9 B6 P5 \ else if(A.elem!=A.elem[k])
9 D' \$ C% S& f$ x0 e) o {% [3 l1 ?, m' C" s: p
 A.elem[++k]=A.elem; //当发现了一个在A,B中都存在的元素
/ _+ F' ?" i g& Q7 `2 U# w i++;j++; //且C中没有,就添加到C中
: [, f( K- X5 l* c1 J5 z }7 i% R4 s5 p& `* l; `
 }//while
9 Z: ?: o: j) x/ k while(A.elem[k]) A.elem[k++]=0;
5 [5 e* ^6 N# W* L}//SqList_Intersect_True 2.28 void LinkList_Intersect_True(LinkList &A,LinkList B)//在链表结构上重做上题
' c; w- N& B7 H- t4 j* Z: Z{
2 M5 ?. w. y7 V3 y* S. r0 _ p=A->next;q=B->next;pc=A;
 ~9 r: j9 X0 f+ Y1 y while(p&&q)( P/ c; X/ g& @: M1 r( G2 I
 {2 X9 H% x: {6 W) `8 ~
if(p->data<q->data) p=p->next;
, x) j: A. X; S8 r ^ else if(p->data>q->data) q=q->next;
. h2 O: N. l1 {4 x9 U1 [ else if(p->data!=pc->data)
6 u$ `3 S' W2 F7 ?3 n* e {
" ?% s0 |0 O) b& J pc=pc->next;3 v% K9 l3 e, T! l
 pc->data=p->data;5 V% n# i, ?, @) I
 p=p->next;q=q->next;
* P' R$ S; J7 I2 d( R }
' T7 x& i( R% w }//while
; N, b9 |& @; f9 m. ~}//LinkList_Intersect_True 2.29 void SqList_Intersect_Delete(SqList &A,SqList B,SqList C)
1 K7 r( U5 X$ A; \; O) o- D{
6 b; S( ]1 J) M8 Y& n( M9 l+ a i=0;j=0;k=0;m=0; //i指示A中元素原来的位置,m为移动后的位置
1 L9 m- Y, `/ Y; p/ u% s' U while(i<A.length&&j<B.length&& k<C.length)
8 J" f2 g1 D5 k) G {
/ f2 V& p3 P L if(B.elem[j]<C.elem[k]) j++;& }( S5 C$ Z! s& C. i( K9 j! a
else if(B.elem[j]>C.elem[k]) k++;
# j6 f% y% S/ N* t* F/ O) ~ else/ x) Z7 H0 b. \; S5 C2 R
{
( I( q& W, _7 b same=B.elem[j]; //找到了相同元素same7 o5 ~8 ?# t2 r+ Q% g' O. D
 while(B.elem[j]==same) j++;$ m! F2 J2 q( F* C4 F" y7 s
 while(C.elem[k]==same) k++; //j,k后移到新的元素
( ?! S7 V- y% w% \ while(i<A.length&&A.elem<same)
4 h. y: ~( R3 H8 ?5 U5 w9 Q A.elem[m++]=A.elem[i++]; //需保留的元素移动到新位置
0 `8 p7 j+ W6 V/ f: p/ J while(i<A.length&&A.elem==same) i++; //跳过相同的元素. ]* d; }; h3 E: f5 [5 L
 }
! a! {( F* o$ W* @$ l, s }//while
/ ^$ o# L f( T+ j2 ]0 m8 l( ~ while(i<A.length) 0 _% Q/ a5 G0 _/ m5 N h5 j
A.elem[m++]=A.elem[i++]; //A的剩余元素重新存储。* }: V$ L: N8 ?! r* v; C4 J* g
 A.length=m; 1 N' K9 {; p5 a
}// SqList_Intersect_Delete
' C8 x7 m. o! F分析:先从B和C中找出共有元素,记为same,再在A中从当前位置开始, 凡小于same的& A9 ~- @. F9 p9 k
元素均保留(存到新的位置),等于same的就跳过,到大于same时就再找下一个same. 2.30 void LinkList_Intersect_Delete(LinkList &A,LinkList B,LinkList C)//在链表结构上重做上题
$ R, e6 y- C% s{$ P% n# d4 d6 A0 ~ Y& r% i# D
 p=B->next;q=C->next;r=A-next;* Q s" J$ e s
 while(p&&q&&r)* f' s# \$ c7 x
 {
, q2 p' V& ]9 m: q1 l+ s if(p->data<q->data) p=p->next;
" W+ Q( H& \6 j: i5 }! [8 U else if(p->data>q->data) q=q->next;5 w( E9 |6 L' T e4 s( L# Z* g( `
else1 a9 J- q$ C# U w
{
2 o: D4 r$ L( F; \ u=p->data; //确定待删除元素u
7 U2 D% Z9 U9 {% Y7 j. z while(r->next->data<u) r=r->next; //确定最后一个小于u的元素指针r
, C5 r% a* j+ s% Q- p if(r->next->data==u)
9 g! e* P/ h1 D; V6 V- X {
$ s7 M- y b- U- e s=r->next;
( p8 H) c3 E" r @& $ I3 Z. ?9 B" f while(s->data==u)
; {3 R- q3 B6 i* a0 K {
( L$ j% z' C4 i$ I! v t=s;s=s->next;free(t); //确定第一个大于u的元素指针s
4 A. U3 b5 j/ J$ Z/ N, P }//while
+ `& V$ Z6 J2 Y# M1 j$ ] r->next=s; //删除r和s之间的元素
5 j, g2 i3 i6 L' K5 f' f }//if
7 M* P. B+ d9 Y! x/ }( q while(p->data=u) p=p->next;$ b/ d' a3 s4 E5 L7 J( P. p- $ f
 while(q->data=u) q=q->next;
2 I( b9 v% a6 t! }0 e }//else* B, w5 i! D( }% V
 }//while8 [1 b& N' V: J
}//LinkList_Intersect_Delete 2.31 Status Delete_Pre(CiLNode *s)//删除单循环链表中结点s的直接前驱4 V* e4 @6 o! W# U7 r
{; X! G5 o$ U! H. p9 E
 p=s;% h/ _. x4 t' S9 Q, n& c8 b1 H
 while(p->next->next!=s) p=p->next; //找到s的前驱的前驱p
. l1 x0 S5 P$ N* Z p->next=s;8 j* f. r ^' A- ?. e; \( v3 p
 return OK;
4 q9 ? j9 k: j}//Delete_Pre 2.32 Status DuLNode_Pre(DuLinkList &L)//完成双向循环链表结点的pre域
% b8 a6 q" D1 D, M{% k! l# u& e' h2 t, q% Q
 for(p=L;!p->next->pre;p=p->next) p->next->pre=p;
' `6 ~% f# z. E* B6 ]$ O% K return OK;, d' S( w. U* m/ k2 B" E2 E$ y* v
}//DuLNode_Pre 2.33 Status LinkList_Divide(LinkList &L,CiList &A,CiList &B,CiList &C)//把单链表L的元素按类型分为三个循环链表.CiList为带头结点的单循环链表类型.
% [- _% z" ?6 ^5 a/ g{' ~; ]7 O. s6 a' s$ ?/ D
 s=L->next;, L( ^6 `& p: P; q
 A=(CiList*)malloc(sizeof(CiLNode));p=A;
- {5 N y# z) T5 V B=(CiList*)malloc(sizeof(CiLNode));q=B;: U( w7 G! \& @5 E
 C=(CiList*)malloc(sizeof(CiLNode));r=C; //建立头结点
/ P- T% j f7 Y0 d while(s)
% @* I: x1 F7 p2 W# ` {
: Q9 r; B- p- i! N4 M" _ if(isalphabet(s->data)), v' [/ T# d* s4 Z5 T; p
{
1 X6 t# |. I$ Y5 W9 m p->next=s;p=s;* M" x9 j$ o( h' t1 ?3 i" b6 |) u
}! c* z6 F6 z& N
else if(isdigit(s->data)); L: c+ A7 Y: L5 m2 L. B
{* k- _0 D" j+ I: F7 J
 q->next=s;q=s;! `4 l: p3 ^ A! ^
}
# Z+ Q4 A1 w9 Q) B* F+ i0 W7 d else
 x7 @+ c# M* J; ] {
+ F& z5 ?, H% }; |% Y r->next=s;r=s;
; F1 i' M' r9 Y. ?* D }3 c }+ |% i) U6 P$ n, y( d
 }//while! I. ~, b9 e" h L. n, z2 S! D
 p->next=A;q->next=B;r->next=C; //完成循环链表
/ c/ f) c- `# g& a- B. u) \+ h}//LinkList_Divide 2.34 void Print_XorLinkedList(XorLinkedList L)//从左向右输出异或链表的元素值2 ]( u+ j _7 ]: C4 C5 j% z
{
" ^" ] O) Q% [. H k: ^5 X p=L.left;pre=NULL;! ]8 T- {, i2 p
 while(p)
) \1 g" e) R, `# I {6 V) N' _+ \( s) V* U$ U+ w
printf("%d",p->data);
5 x& P; V, o$ u V q=XorP(p->LRPtr,pre);$ q& R2 s0 L+ o
pre=p;p=q; //任何一个结点的LRPtr域值与其左结点指针进行异或运算即得到其右结点指针
6 N3 d# h! _# q+ J% x5 F; i3 W }
) b5 p: D7 Z: W l% G}//Print_XorLinkedList 2.35 Status Insert_XorLinkedList(XorLinkedList &L,int x,int i)//在异或链表L的第i个元素前插入元素x" S8 y& N' U( |! o O
{
2 l6 g B9 _" S' Y! X {# @ p=L.left;pre=NULL;
( q( I4 Y" I% P* t0 t r=(XorNode*)malloc(sizeof(XorNode)); ?. R' O. N- g8 f* F' J( c6 I
 r->data=x;
. h9 {! \( k( _2 t0 ] if(i==1) //当插入点在最左边的情况" [. w% t( ?8 y0 f+ Y
 {
. Z1 Q8 t; C. U+ h" Z p->LRPtr=XorP(p.LRPtr,r);
' u9 R* |# P8 H9 [& H r->LRPtr=p;0 i' ]# D( h. E+ f
L.left=r;
7 r- G0 A4 f- u m. {- B8 V return OK;# E5 O; b' ?5 K# U* @1 [+ `
 }/ l$ W# P% v$ I! v2 c
 j=1;q=p->LRPtr; //当插入点在中间的情况
4 z# k3 n/ y0 [: X& j& k6 [ while(++j<i&&q)
% ?3 X0 h" m) y- x1 i {& P9 z' m( \5 V6 i) V1 z
q=XorP(p->LRPtr,pre);& H6 R% B4 {5 a, k3 N9 G7 c
pre=p;p=q;7 J: W; _' e4 e
 }//while //在p,q两结点之间插入7 {6 B! Q5 D! q+ l6 X
 if(!q) return INFEASIBLE; //i不可以超过表长
! ?3 {( f, l, ` p->LRPtr=XorP(XorP(p->LRPtr,q),r);- N; z# E1 M' m# y* f0 f, ^
 q->LRPtr=XorP(XorP(q->LRPtr,p),r);
8 R; `6 p+ X5 H9 E r->LRPtr=XorP(p,q); //修改指针
( y, i" F$ [6 Y# J" B4 c; r. M) `: C return OK;; I4 E% N# ~6 {- B! O$ ?! R! K7 ?/ [
}//Insert_XorLinkedList 2.36 Status Delete_XorLinkedList(XorlinkedList &L,int i)//删除异或链表L的第i个元素5 t3 ~$ y1 K/ }1 l: |7 a& [4 V
{8 n8 z. ]7 l' G. d! R" q3 M
 p=L.left;pre=NULL;
9 ~' g5 n* Z8 E$ ` if(i==1) //删除最左结点的情况0 X+ G5 |$ @5 U5 P% p
 {
1 P: B+ ^- @: P" ]8 [" J: [ q=p->LRPtr;
$ Y h' f t! \; ]- R q->LRPtr=XorP(q->LRPtr,p);4 F" _3 X3 z/ k
L.left=q;free(p);
8 J) \6 y4 L, i+ M/ ~ return OK;
) @; g. ]6 f/ y4 ~0 K) H }. V+ j$ s) u! }1 h- D
 j=1;q=p->LRPtr;0 {! O* g) S. A7 g+ ]$ r
 while(++j<i&&q)- a; Z2 Y+ J, q! i
 {
; w9 ~5 M! G [ q=XorP(p->LRPtr,pre);3 `/ B. d, J$ R5 {+ y+ E8 W1 ?2 [. N% Z
pre=p;p=q;
$ B; Q; n1 Q+ q* J0 S. B1 I. a; _- I }//while //找到待删结点q2 o8 v: D; ?5 K" T) {9 b9 T9 ^
 if(!q) return INFEASIBLE; //i不可以超过表长
+ u) ^* }2 g0 F% c9 }2 k! g1 R if(L.right==q) //q为最右结点的情况
( \) g- K# }7 R {. k0 `4 h& e+ }( {& y# d/ u7 g3 a
p->LRPtr=XorP(p->LRPtr,q);
7 N5 w2 K5 u1 N6 M) N L.right=p;free(q);3 N% D7 O- a# w. Z# S8 F$ T
return OK;! q3 f, i Q8 Y. J4 B# [1 |
 }- E4 K M. `* L4 g. S
 r=XorP(q->LRPtr,p); //q为中间结点的情况,此时p,r分别为其左右结点7 Z+ S/ u& E) Z; }8 z
 p->LRPtr=XorP(XorP(p->LRPtr,q),r);
, e% b& Q5 S0 V9 Z$ E _) E r->LRPtr=XorP(XorP(r->LRPtr,q),p); //修改指针/ R, s7 z1 W: `8 v f9 {
 free(q);
3 }) w. [& m- B) G2 y6 L/ s return OK; d: ^ f/ P2 g+ S
}//Delete_XorLinkedList 2.37 void OEReform(DuLinkedList &L)//按1,3,5,...4,2的顺序重排双向循环链表L中的所有结点
9 h/ B/ B1 m/ M: _$ X( I& d{
7 I5 l6 I, t/ F# P- [7 B p=L.next;1 D. p& F% i5 U4 m1 A O' l" S
 while(p->next!=L&&p->next->next!=L)
) R" B! ?& I: a) o {
+ Y0 A' z+ T; e4 A1 i- u p->next=p->next->next;2 ?: m2 m% q5 u
p=p->next;6 n2 \3 U7 f5 r' R
 } //此时p指向最后一个奇数结点/ b) X3 j d! k( h
 if(p->next==L) p->next=L->pre->pre; z# i5 B& v4 j# x) K
 else p->next=l->pre;
$ P+ A2 z0 g* Q" E0 I p=p->next; //此时p指向最后一个偶数结点 J l4 W( C4 S
 while(p->pre->pre!=L)
4 d, f! F7 J5 d( P+ W1 W! X {
& j8 Y) C0 \5 j# g p->next=p->pre->pre;
' c" V G, s. q+ D p=p->next;* J' ~$ f( H' K! P
 }
, T$ o3 L w# U9 v8 P. m2 \ p->next=L; //按题目要求调整了next链的结构,此时pre链仍为原状: V( m+ c9 }9 N( l+ _- c+ _9 a
 for(p=L;p->next!=L;p=p->next) p->next->pre=p;& ^, F& v/ Z9 W2 c* e
 L->pre=p; //调整pre链的结构,同2.32方法
}//OEReform( \$ t: t& i, T9 F, X3 W
分析:next链和pre链的调整只能分开进行.如同时进行调整的话,必须使用堆栈保存偶数结点的指针,否则将会破坏链表结构,造成结点丢失. 2.38 DuLNode * Locate_DuList(DuLinkedList &L,int x)//带freq域的双向循环链表上的查找1 ^/ Y# k6 p; R# ]
{
' z! A& k5 [& x- ?/ k p=L.next;" ?- T4 {( Q: x0 \: J
 while(p.data!=x&&p!=L) p=p->next;
% A; D. Z0 v0 h( P$ U if(p==L) return NULL; //没找到" n- L, p) @8 U9 \# y
 p->freq++;q=p->pre;
+ e( Y( O+ c* s# Y4 @ while(q->freq<=p->freq) q=q->pre; //查找插入位置+ Y6 }' X: ^: @4 G
 if(q!=p->pre)' D/ {1 }8 O1 L7 u
 {2 h4 a' h5 J: g' Q$ C9 O, {& o
p->pre->next=p->next;p->next->pre=p->pre;+ }1 T, n: `$ F' n8 y( j+ ]
q->next->pre=p;p->next=q->next;
& _" m+ }7 p6 S+ O$ R& g. h8 E- X q->next=p;p->pre=q; //调整位置
 d! q2 l* a4 M% q' e, f- n }" k: B p# s6 A6 p3 Y$ S; ?% i
 return p;
, m. h/ n! X; @+ g}//Locate_DuList 2.39 float GetValue_SqPoly(SqPoly P,int x0)//求升幂顺序存储的稀疏多项式的值
/ I6 e2 h2 N7 T( b6 a A+ R1 b{
 ~ R! M9 C2 f$ X PolyTerm *q;: c* v3 L$ y$ |8 t, M9 l
 xp=1;q=P.data;
. ]7 F A7 H6 [7 n sum=0;ex=0;
% n( X! R! p Q0 n1 v while(q->coef)0 V! A( y0 t& T) S
 {" ?0 a% @+ J2 u6 L; @) k
while(ex<q->exp) xp*=x0;; ]2 Y8 I2 u. `! g; O
sum+=q->coef*xp;
2 \' k2 k' T& v4 z4 p& U- _1 P q++;- N2 k* l8 Z% z4 B# p
 }
* A8 V% ], P( [" N+ _, ^5 N return sum;
# t) z" s7 d9 }8 O t# m6 X}//GetValue_SqPoly 2.40 void Subtract_SqPoly(SqPoly P1,SqPoly P2,SqPoly &P3)//求稀疏多项式P1减P2的差式P3# r9 z6 a8 U# `
{
6 j, T, i! B% f& S! a3 m9 \ PolyTerm *p,*q,*r;6 `. o3 w, h6 `0 \" |" C6 P$ X
 Create_SqPoly(P3); //建立空多项式P36 `8 W3 B4 H3 d$ Y* p# U H6 e
 p=P1.data;q=P2.data;r=P3.data;. N& c* D9 R5 k; P' h) j
 while(p->coef&&q->coef)
5 g( `/ w7 ^& P) [. h& v1 e {
! y: O: W/ o* H4 L6 q' w if(p->exp<q->exp); Y3 Q' x4 L. M7 D7 y* }5 o
{
& f m8 L8 x; T$ f4 p r->coef=p->coef;
2 d: d+ _$ {1 k0 J6 Z8 X% X# ~ r->exp=p->exp;
! l; P4 |4 _$ N1 x8 j# \$ u, K p++;r++;0 m3 Q2 \- R# L/ p
}
; n6 a+ t) G% [4 @( v- k! f5 ^5 e0 t else if(p->exp<q->exp)
' p1 y. G8 e# N# [* U8 e; U2 | {
/ u/ {- B. B: W2 { r->coef=-q->coef;
/ l7 `0 f9 Q) m9 n6 \, U9 Q2 A! i r->exp=q->exp;1 b. I3 E- u8 a4 Y
 q++;r++;- c, W4 p, _4 K5 P
}
9 K( v' z9 D4 w( u0 V. t! j else
 ^& `: I6 A; N8 V0 J2 H( e {
2 T/ G6 F* e" U% c/ B if((p->coef-q->coef)!=0) //只有同次项相减不为零时才需要存入P3中! V2 J# A: o: U3 g3 q( D* A
 {
( v) D; @% k9 x1 |! ~5 P r->coef=p->coef-q->coef; ^/ q& j) ?" I; B1 Y! m
 r->exp=p->exp;r++;
4 Y& U7 W; ^7 a* d- N; e. F2 O }//if3 {) n) N# E1 u& Q2 X# H; X: x
 p++;q++;
) J% I( h# n- g }//else
* b5 d8 T$ X$ O! ^; L }//while
) m& R( M& O9 p- |8 s while(p->coef) //处理P1或P2的剩余项
! L# N( e" b+ h3 e7 q7 K P {6 j+ ?6 O4 H4 ^* @
r->coef=p->coef;
; E+ f- N. y1 h" s3 A8 E6 E3 H r->exp=p->exp;; K# F3 w e3 y$ m$ m% O
p++;r++;
+ l" Y/ y! g/ \# L }
% b" T5 H: J. C; a while(q->coef) ~+ ?" t* B) S- e2 S+ F1 ?/ ` C: |
 {
9 B, m2 I, N/ n: p" I: } r->coef=-q->coef;3 h' ~+ {, z" P! W4 s% |( a' ?
r->exp=q->exp;2 b9 e( o4 _- }: n# B' B, Q
q++;r++;
2 d# v( a! X. N2 ^7 n0 f; B9 L% z }
( I0 L' D) ?) l/ h6 K9 Z& z# i}//Subtract_SqPoly 2.41 void QiuDao_LinkedPoly(LinkedPoly &L)//对有头结点循环链表结构存储的稀疏多项式L求导 F* P: U* R. ]5 f3 l( _. I
{
. k/ R6 |5 S" H+ z9 g5 d$ X4 O9 U6 L p=L->next;6 ]* v; O# Y; E4 a0 ~* b
 if(!p->data.exp)
+ F* ~" \" G. c M+ c. g n {
0 F) e% r" D* v+ D4 F% E L->next=p->next;p=p->next; //跳过常数项& F3 q7 k1 S) c
 }
1 u" J( q+ Z9 X8 \4 n. w while(p!=L)
& e" T2 p4 w: \- `( I- r' y {
& l( l* F4 v5 X% a1 [1 [/ l p->data.coef*=p->data.exp--;//对每一项求导6 c: z* o [+ d. @
 p=p->next;
 j6 O( [: P, \; M g }' `/ o9 _/ u5 ?; S
}//QiuDao_LinkedPoly 2.42 void Divide_LinkedPoly(LinkedPoly &L,&A,&B)//把循环链表存储的稀疏多项式L拆成只含奇次项的A和只含偶次项的B% t$ o+ N2 ~4 Z# |. h
{
4 p+ B; |' p; c6 g) f p=L->next;
5 T& T" y7 d1 Z' b A=(PolyNode*)malloc(sizeof(PolyNode));
* c) o% d5 _9 V: X( j4 {2 c ~ B=(PolyNode*)malloc(sizeof(PolyNode)); O9 ^9 m: s6 @. ^/ i8 ]% m
 pa=A;pb=B;3 _# ^7 P4 H @) \* v* a8 f
 while(p!=L)
& X7 u( Z6 @$ C' X9 z {
7 e# g, ?% ~' ?. `* D if(p->data.exp!=2*(p->data.exp/2))
) g) e: \, l) X) `6 X \; i; Q& B2 y {; G( d/ M# p; ^% U, y7 u( c) n( \& W
 pa->next=p;pa=p;
* f+ e Z: }5 X }
$ [8 v) r3 G2 s: C& ^2 Y) l else
- ` Z7 V* |) Z9 ?9 k* ?& W {% v$ ?, \+ D3 Y8 D* U
 pb->next=p;pb=p;
" ~( L5 L% \: j' M- T( O- l, I }
: Z% U0 y6 [- ?% x$ Y+ ^9 \' G6 N p=p->next;
6 V" q# c/ F7 u" s# A) i9 @" j }//while& C' d+ K! S( m3 ^/ J; |( n" D/ m
 pa->next=A;pb->next=B; . G7 p6 l2 {3 |, i
}//Divide_LinkedPoly
作者: 布赖 时间: 2004-12-18 00:28
<>很长呀<>不过还是十分感谢
作者: 铜豆子 时间: 2007-6-20 21:54
不是实习题的答案啊

欢迎光临数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5