数学建模社区-数学中国

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

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