数学建模社区-数学中国

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

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