数学建模社区-数学中国

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

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