数学建模社区-数学中国

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

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