数学建模社区-数学中国

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

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