数学建模社区-数学中国

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

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