查看: 4971|回复: 3

《数据结构(c语言版)习题集》算法设计解决方案

字体大小: 正常放大

66 主题	1 听众	648 积分

VisaSky.com 加拿大移民留学网

TA的每日心情

	开心 2012-6-9 03:29

签到天数: 1 天

[LV.1]初来乍到

电梯直达

1^#

发表于 2004-11-28 18:02 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

<

>说明: 
<

>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; C' k: @. Q* z
temp[k-1]=1; //初始化& D7 G0 r ], t
 for(i=k;i<=m;i++) //求出序列第k至第m个元素的值7 R" A! k: }, q/ t# a7 e7 }) I
 {6 V0 q" o! b$ G4 L& \
 sum=0;
, y1 {* k9 D5 F; r5 J' U for(j=i-k;j<i;j++) sum+=temp[j];
! [9 ]% ~1 q/ q, @! y. a6 G temp=sum;
8 u7 X0 M0 N7 U }
% c3 a8 s/ t* D# E$ ~4 r f=temp[m];
: n! G3 Q; ]4 Y2 X- C9 z) n }1 l# b0 k) J z: D2 B
 return OK;
* l- p0 L% o. @0 f: h1 x}//fib8 _( v$ u( s. F S% `
分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m). 
6 T3 |# |9 b& z+ `# H( j O<>1.18 
8 U4 q* d" k2 N$ u$ J<>typedef struct{! C* B5 Z. [; v# G
 char *sport;
7 u9 U1 Z, e9 j- r enum{male,female} gender; R$ j! K8 n" R# e6 d- V: Q
 char schoolname; //校名为'A','B','C','D'或'E'5 P9 K( {* G& V0 p3 L
 char *result;
$ b8 }! Z5 b2 T& @$ g int score;
; w7 j! I& E" l3 z } resulttype; 
/ j/ S1 ]) b8 B% w, m) Z9 p<>typedef struct{
# d' F& _% B" o5 \, X int malescore;
$ Q: N+ Z- f( N% r int femalescore;
; H7 s5 A$ E! V3 k int totalscore;
4 a/ }& i4 ~5 G; s6 s8 n5 O } scoretype; 
; ~( m% M8 g F$ o0 t9 g: E<>void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中9 e- y. s) D) N5 g5 y
{
. @7 N1 ~& S- d" [ scoretype score;
7 c* Y7 m3 s0 q( U i=0;
& l E3 a# W" ^0 D# R+ m while(result.sport!=NULL)/ ]) p, l, B& f1 A
 {
8 a4 l: ~( Z% Q switch(result.schoolname)
8 o( Q, U W3 {1 O4 E! } {
 S' Z7 ]' r* ~/ j case 'A':
) x5 ]7 I- U# T+ ^/ S) o$ A score[ 0 ].totalscore+=result.score;0 j6 Z# g9 _" g; d0 ]
 if(result.gender==0) score[ 0 ].malescore+=result.score;
9 I9 [# S6 {; Q/ J else score[ 0 ].femalescore+=result.score;2 Z7 c" K% l* G' @9 n5 [# H# n
 break;
, Q3 h3 [' ]6 a7 ^ case 'B':
: G/ t+ R4 t* S9 C9 K1 Y! B" X score.totalscore+=result.score;' G: u+ `* r, `
 if(result.gender==0) score.malescore+=result.score;" L- j* U8 {5 `( @ W8 o' K% R
 else score.femalescore+=result.score;1 Z# }& Y: ]$ S& l9 a/ ?) i
 break;$ X/ k9 t$ L3 n; y' U- f
 …… …… ……0 _. }" P1 C3 \; q
 }
' z3 I' C& {0 |1 t8 p i++； T0 a5 C& {! T4 N" w
 }' F3 b9 p. f. E9 }
 for(i=0;i<5;i++) u Q" n: G6 P2 I7 y, `! B( T
 {
9 b* Z4 G" P0 i2 i& Q9 ?- h1 N printf("School %d:\n",i);) K- I0 ?& `- q/ D$ G5 m
printf("Total score of male:%d\n",score.malescore);7 M' C$ e. H, X- W9 V! ?! m8 w+ `
printf("Total score of female:%d\n",score.femalescore);
& J P6 y: J: q8 x' ^$ | printf("Total score of all:%d\n\n",score.totalscore);3 M# o5 m! S6 f* U
 }
, S+ O* R4 s2 w+ {( }1 `}//summary 
0 F5 o6 ?' E. \8 @6 Z( N<>1.19 
& y; m6 B! Z& m8 T2 X' Y<>Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint
7 U" ]+ W% c8 s* ~{: q9 C, L& P/ l
 last=1;1 O) `" r9 v' C! }
 for(i=1;i<=ARRSIZE;i++)
" t+ ^- b' r1 h9 f* {1 q3 _& S {/ O6 k2 t6 h6 T6 X z
 a[i-1]=last*2*i;
$ H1 T" e$ c, d+ i1 H( a if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;
" @! V: _0 V/ X) L: J last=a[i-1];
4 ~1 p4 N0 \" N! L) Q# F+ i: D! j return OK;
' P8 F/ A% V! z% v }
' W7 d4 ^( Z' v}//algo119
# N! H S" F; d( _# W* ^* S- Y# W分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. + x# F! t* E" x* }+ n
<>1.20 
. s7 i* T* d V' ^<>void polyvalue()
# g; o$ q6 H( M' X{6 @ b( L { U. L$ v5 ]
 float ad;7 L* D$ J+ C5 _5 ~0 M- q
 float *p=a;
- \; M) r) D- {5 T% G" w1 O printf("Input number of terms:");6 h; M' M: p" \: d- S/ D; u
 scanf("%d",&n);
* I* b% U$ c- G7 ]0 ]2 a4 X printf("Input the %d coefficients from a0 to a%d:\n",n,n);8 T7 [$ U) h2 Y% x
 for(i=0;i<=n;i++) scanf("%f",p++);6 ?* P" s4 |6 Z v" h8 ^" ]
 printf("Input value of x:");1 @# U) Y* V4 E7 m/ c5 \
 scanf("%f",&x);
0 E4 S+ q8 D$ e% l/ ^ p=a;xp=1;sum=0; //xp用于存放x的i次方( q) e7 n' @9 d4 U; ]
 for(i=0;i<=n;i++)5 H o: I8 T7 O4 s
 {
) J8 f- x6 T# z0 _+ Q sum+=xp*(*p++);7 m H9 O1 I7 L
xp*=x;
% g7 d) s' r" K% T% h% y6 d }
' e; n# p- o5 |: [ printf("Value is:%f",sum);
; L, c k; ^5 C}//polyvalue
/ N# e$ N2 P; J; M t< >

zan

转播0 淘帖0 分享0 收藏0 支持0 反对0 微信

使用道具举报

╃無名草╃

66 主题	1 听众	648 积分

VisaSky.com 加拿大移民留学网

TA的每日心情

	开心 2012-6-9 03:29

签到天数: 1 天

[LV.1]初来乍到

2^#

发表于 2004-11-28 18:16 |只看该作者 |招呼Ta 关注Ta

<

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个元素
{
 if(i<1||k<0||i+k-1>a.length) return INFEASIBLE;
 for(count=1;i+count-1<=a.length-k;count++) //注意循环结束的条件
 a.elem[i+count-1]=a.elem[i+count+k-1];
 a.length-=k;
 return OK;
}//DeleteK <

>2.11<

>Status Insert_SqList(SqList &va,int x)//把x插入递增有序表va中
{
 if(va.length+1>va.listsize) return ERROR;
 va.length++;
 for(i=va.length-1;va.elem>x&&i>=0;i--)' c9 c) b" O8 V* G
va.elem[i+1]=va.elem;6 r$ q/ Q. I- R8 I0 o
 va.elem[i+1]=x;
& x# o# R6 {7 w2 U return OK;$ |$ b7 l- U! W- W/ S
}//Insert_SqList <>2.12 <>int ListComp(SqList A,SqList B)//比较字符表A和B,并用返回值表示结果,值为正,表示A>B;值为负,表示A<B;值为零,表示A=B
; X4 U. e# W& r{
3 S3 ~1 ]0 \' ?& o! D% I for(i=1;A.elem||B.elem;i++)) a1 S7 W8 U) }* v, w2 d0 Z
if(A.elem!=B.elem) return A.elem-B.elem;- R* i. E& C* Q$ D+ ~
 return 0;
5 r; O, Z: t+ V. V- ^}//ListComp <>2.13 <>LNode* Locate(LinkList L,int x)//链表上的元素查找,返回指针
/ a7 k8 N! ] C' _. k% N6 L- w{& I! y( U6 a8 X6 J' W( \0 s
 for(p=l->next;p&&p->data!=x;p=p->next);
$ R( }' p$ t$ W4 }' C' R return p;
1 R0 C3 H. C; A) G7 v" P3 M}//Locate <>2.14 <>int Length(LinkList L)//求链表的长度7 E! h+ `7 z6 {1 K% Z9 |; U5 E `
{
7 m! N5 L+ r& n2 ^ for(k=0,p=L;p->next;p=p->next,k++);) L% q9 A* ^, _
 return k; `+ B4 N7 j. S I
}//Length <>2.15 <>void ListConcat(LinkList ha,LinkList hb,LinkList &hc)//把链表hb接在ha后面形成链表hc
9 I5 ~3 y# v L1 L! q{
8 r! T6 Y' P. t hc=ha;p=ha;
' R8 s$ W0 i9 L& B! N2 M5 a while(p->next) p=p->next;$ ?7 t1 U5 u- w a
 p->next=hb;% o* C+ ~; V& q9 F+ Z* |
}//ListConcat <>2.16 <>见书后答案. <>2.17 <>Status Insert(LinkList &L,int i,int b)//在无头结点链表L的第i个元素之前插入元素b
3 }& I* i% j0 v/ B{& l& [( `! b5 K% w, A/ i' B: N
 p=L;q=(LinkList*)malloc(sizeof(LNode));
* A/ F+ [7 j' u$ c$ d# x. E8 Y q.data=b;
) h9 W, N1 w4 N# O if(i==1)
 L3 D% D6 R) D4 |! A0 b4 [ {
( w$ a8 \' m" z% Y: r+ _( w# v q.next=p;L=q; //插入在链表头部5 I* C- ^ q$ [/ P5 E+ S7 K' s3 J& L
 }" d. @/ L$ ~/ c; u
 else
" K" f. m5 |# O {/ Z8 ?3 i: I! C! D4 n' m1 Z" A! q
while(--i>1) p=p->next;+ h3 Z" @; z) z- J! V% L# B
q->next=p->next;p->next=q; //插入在第i个元素的位置
; }7 p0 @: y/ f- R, A; {( H- A1 V }. q- @" f0 z z. q/ t) r, E8 c
}//Insert <>2.18 <>Status Delete(LinkList &L,int i)//在无头结点链表L中删除第i个元素) ~9 A8 h7 ?+ R( M- i5 E4 e% _
{
0 i: G0 K( @. ]' d% V, y. W# h7 s if(i==1) L=L->next; //删除第一个元素
. S4 a& N5 l- w& C1 w$ e L" X: ? else
% Q# C i7 j. i! p {
- |- g3 y1 Q1 |+ R; J: p2 |- }# X p=L;
! C0 }0 e* R" Q7 h7 o3 f/ l( B while(--i>1) p=p->next;0 i0 \/ M1 h- o) m2 e+ \2 @9 T" I
p->next=p->next->next; //删除第i个元素6 E% j4 ~4 ^' Q$ Q' l9 g; ^0 L
 }+ k/ j, H ~) y, s) V
}//Delete <>2.19 <>Status Delete_Between(Linklist &L,int mink,int maxk)//删除元素递增排列的链表L中值大于mink且小于maxk的所有元素1 o8 v' m4 E) C+ u; ?9 t, I
{
! M4 P2 _2 k; o& T1 Y) {% H* t p=L;
. r9 n. a8 E$ T. B0 z while(p->next->data<=mink) p=p->next; //p是最后一个不大于mink的元素
: M6 _, R/ E6 U if(p->next) //如果还有比mink更大的元素' N" q, T C" P! A4 M0 ?
 {
% O- o4 P3 g# G- n5 z& l |1 h q=p->next;# m( Q1 {6 a; l
while(q->data<maxk) q=q->next; //q是第一个不小于maxk的元素: |& B+ D8 I1 h
 p->next=q;
; e; P1 W, E7 h }
( W4 q+ t# v- z* w5 D( z}//Delete_Between <>2.20 <>Status Delete_Equal(Linklist &L)//删除元素递增排列的链表L中所有值相同的元素
& i$ h: |' q' c/ A/ k; b{
/ w8 G+ ^ s8 {2 \ p=L->next;q=p->next; //p,q指向相邻两元素
, t: J* ]1 A6 {2 A; o8 D while(p->next)
% [1 g2 } h2 S) @0 U {
) i/ F% \. K' w4 n4 C if(p->data!=q->data)' K) s9 J0 L0 U2 Z! C
{( M$ {. \$ d" q, c4 d1 G7 ^/ q0 A% g
 p=p->next;q=p->next; //当相邻两元素不相等时,p,q都向后推一步
+ _/ |- ^* q* E& r. ^/ P c- [ }
6 e. I" x' w" W8 n: V# @* B3 ? else
3 ^: ~, l" |# y0 P& A {
/ J) v# O$ s9 I9 H6 ? ]# e while(q->data==p->data) 1 q4 Z! y3 X. @! H2 c8 U- m
{0 {( m0 B7 @6 a
 free(q);- J* ]# G# D& e R
 q=q->next;
' {" R! d |0 `; f" Z' G! \ }
1 ~- n/ ?( H: M6 C p->next=q;p=q;q=p->next; //当相邻元素相等时删除多余元素
. m. @8 P9 K2 S" I }//else+ m0 ?4 \) I$ k W7 E6 m6 Z/ R
 }//while
% |( F3 R& E, x9 Z7 J}//Delete_Equal <>2.21 <>void reverse(SqList &A)//顺序表的就地逆置
+ q2 U W( E; q& O3 O" B{7 h4 Q# S7 y* T( v6 I* x
 for(i=1,j=A.length;i<j;i++,j--)# G- ? |0 x# h8 i0 A
A.elem<->A.elem[j];
- K! N2 t: A: D}//reverse <>2.22 <>void LinkList_reverse(Linklist &L)//链表的就地逆置;为简化算法,假设表长大于2
9 O% w0 D3 n5 I{) x3 _# O, f7 H' N- b
 p=L->next;q=p->next;s=q->next;p->next=NULL;- e2 \: _% a" U* P8 v1 Q1 F) t
 while(s->next): @& b# [1 Z' u1 M
 {3 [) V- l6 ~8 g: s- O) B
q->next=p;p=q;% G; G2 f! w+ O3 k+ k
q=s;s=s->next; //把L的元素逐个插入新表表头
9 l$ `" ?) a1 \1 t }& D; M- h o7 @2 Q5 B" P
 q->next=p;s->next=q;L->next=s;
' L% t1 O* i( P. t}//LinkList_reverse
" @' F6 G' W# l6 N. @% F分析:本算法的思想是,逐个地把L的当前元素q插入新的链表头部,p为新表表头. <>2.23 <>void merge1(LinkList &A,LinkList &B,LinkList &C)//把链表A和B合并为C,A和B的元素间隔排列,且使用原存储空间% u( J* d1 }9 |" e) I+ r
{4 v9 f7 U1 }1 \* P, f9 {1 h/ Y" L
 p=A->next;q=B->next;C=A;' _" \1 T1 @7 T- u# j2 i3 }
 while(p&&q)
+ w! P( f X8 I: y: A/ V4 A {) ]) P: j/ y# x& A* e
s=p->next;p->next=q; //将B的元素插入' ]: d# ^4 t( L9 M
 if(s)
" j; f1 E: O+ @& y {; K5 B" N+ R0 j# i9 r3 @# x
 t=q->next;q->next=s; //如A非空,将A的元素插入1 U, A9 h; B: [* n* A! l
 }
7 Q) u0 ~4 \! o& j, M p=s;q=t;
- m/ P: v3 [# l. f }//while
' q% o( O# c. H2 e% [% `) g}//merge1 <>2.24 void reverse_merge(LinkList &A,LinkList &B,LinkList &C)//把元素递增排列的链表A和B合并为C,且C中元素递减排列,使用原空间
5 j$ h- e0 A; r' [; H{
" a- n0 I' c9 y& d( w/ w K9 q) U$ l pa=A->next;pb=B->next;pre=NULL; //pa和pb分别指向A,B的当前元素5 m' @5 F2 k1 o! i. n
 while(pa||pb) ^0 @- @: A. U" g1 R
 {
, e9 C7 m- O. J: X if(pa->data<pb->data||!pb)
# ?+ H$ u1 {+ U& C* R1 w. j8 W- H {4 ^# U4 W$ o/ T. w: C5 Z C
 pc=pa;q=pa->next;pa->next=pre;pa=q; //将A的元素插入新表# T, K$ \! k) y! B6 g
 }2 y! a1 ?; f6 C7 k5 |5 i
else' Y7 g4 u& M; A5 f0 ?6 ~7 p$ Y
{0 O0 j7 j, n6 g7 F1 D5 t
 pc=pb;q=pb->next;pb->next=pre;pb=q; //将B的元素插入新表
+ J) `$ J" l2 f h; k R" |- f5 R }
# Q/ [4 r% S, P- D pre=pc;% G- @0 }6 ~8 a. f) t' g( [$ R! ]0 w
 }+ I8 n7 U5 l8 D/ g
 C=A;A->next=pc; //构造新表头4 F4 f, h9 Y$ ?7 R! R7 x
}//reverse_merge/ r; w( C. f! S. P
分析:本算法的思想是,按从小到大的顺序依次把A和B的元素插入新表的头部pc处,最后处理A或B的剩余元素. 2.25 void SqList_Intersect(SqList A,SqList B,SqList &C)//求元素递增排列的线性表A和B的元素的交集并存入C中; m3 L- t, O, ] d# n2 Q
{7 [$ n7 v& }& R* A- [. Y1 G
 i=1;j=1;k=0;
5 T6 ^* O9 @# X# l' Q$ }" b1 q+ u4 m while(A.elem&&B.elem[j])
8 F7 h: A e, ~! V! f. p {3 w L4 _7 r9 {- _
if(A.elem<B.elem[j]) i++;% D$ G1 j3 y! I: `
if(A.elem>B.elem[j]) j++;; g5 e/ C! U) K: [
if(A.elem==B.elem[j])
: @$ G5 c& z8 J9 \ {9 e# i1 V; d2 b3 [2 o$ }- i
 C.elem[++k]=A.elem; //当发现了一个在A,B中都存在的元素,4 ?9 R+ j9 Q m& Q2 F) ?
 i++;j++; //就添加到C中" I) Z. Y& f+ u+ V6 ^5 u; T1 d1 |9 H7 f
 }! p% z: H8 ]$ l! L- ]2 d
 }//while
5 H1 b2 i% x4 J}//SqList_Intersect 2.26 void LinkList_Intersect(LinkList A,LinkList B,LinkList &C)//在链表结构上重做上题
4 Q9 _0 v2 B/ d: e" U( Y% R; e% n{) X% S' x' }- G. ?1 W
 p=A->next;q=B->next;
# d0 \0 L! x" d" w- a pc=(LNode*)malloc(sizeof(LNode));! x0 z* O4 }8 _0 g* w2 P
 while(p&&q)
8 i: x8 o! {& [7 A( s- l4 r {
3 n! x- u& V1 T8 Q( I3 C+ g- B4 y if(p->data<q->data) p=p->next;
* X6 T2 j, ?1 V) W* y2 Z6 Q else if(p->data>q->data) q=q->next;
. y( J. @$ w7 g) O else
, J, \- N- c- M {. `( i! n. [+ F; {6 _6 b
 s=(LNode*)malloc(sizeof(LNode));
; k4 m7 v: \8 s9 ~* N( O7 h s->data=p->data;
$ {' h; L+ `2 A5 [ pc->next=s;pc=s;
! Y% q; G5 c* b# W p=p->next;q=q->next;
' ]' n+ J4 V' }- R* _$ g4 V* K }
; q$ Q) d% S/ B }//while
! e) {. l" L5 @ C=pc;
" j+ S; @: t, A: n6 \; D- Y, H}//LinkList_Intersect 2.27 void SqList_Intersect_True(SqList &A,SqList B)//求元素递增排列的线性表A和B的元素的交集并存回A中 q2 k ^; {8 V6 T% q
{$ Y1 B4 e* F" b
 i=1;j=1;k=0;5 N' R; P+ X d/ M* [3 m/ E& d$ o- y
 while(A.elem&&B.elem[j])
" _$ P% P1 }: ^( U( y# [ {* y! x! H9 z- r3 |5 s! H ]
if(A.elem<B.elem[j]) i++;/ m9 \% M) v9 A( Y: S( Q8 N0 P
else if(A.elem>B.elem[j]) j++;: b2 p* u) l2 k" L" W6 W
else if(A.elem!=A.elem[k])
& I, A* d7 m2 Y) L# P {
& ~2 P) G0 w2 ]2 z6 S: ~% q A.elem[++k]=A.elem; //当发现了一个在A,B中都存在的元素
 a! E0 I/ z4 f7 T9 p0 ] i++;j++; //且C中没有,就添加到C中
 }
+ o7 a; w6 c2 P6 X }//while
/ ~/ q" n2 ?' r0 y3 Q while(A.elem[k]) A.elem[k++]=0;
0 m8 W# ^6 n6 }}//SqList_Intersect_True 2.28 void LinkList_Intersect_True(LinkList &A,LinkList B)//在链表结构上重做上题! i& U8 r+ _/ ^4 r5 n! o/ H
{7 p2 c0 H2 Y( z! k1 b- N- k$ {0 M
 p=A->next;q=B->next;pc=A;
& u) b/ _% f. B# b0 N* l while(p&&q)
2 H$ u4 `5 Q% S! U1 C, \( R$ _. _ {: q9 O9 [* g1 m
if(p->data<q->data) p=p->next;
, l0 e( ]0 K9 {! d" D+ {2 y0 _ else if(p->data>q->data) q=q->next;2 w* }" l' b6 ]) ]8 X
else if(p->data!=pc->data)# { u2 e: x9 Y+ Z# z
{
$ P. `+ G9 Y5 u% Z% M pc=pc->next;" o# ~" ~/ y( |
 pc->data=p->data;3 u2 E) f3 `( S
 p=p->next;q=q->next;
5 ]5 h$ B* {; Y/ m* {" W+ p }
1 q9 H- F1 S! R7 |5 _3 y$ Y }//while
4 F0 g! a5 A1 Z% p1 o}//LinkList_Intersect_True 2.29 void SqList_Intersect_Delete(SqList &A,SqList B,SqList C)
. t8 H7 j; S+ m8 b{
; }0 |3 R6 o. { {# X i=0;j=0;k=0;m=0; //i指示A中元素原来的位置,m为移动后的位置$ g7 Z- |3 x) |9 L
 while(i<A.length&&j<B.length&& k<C.length) 0 Y* ?1 e( i7 \* Y/ B
 {7 D0 x6 _, {: j) C& J
if(B.elem[j]<C.elem[k]) j++;8 ?2 L9 W3 f! L" T
else if(B.elem[j]>C.elem[k]) k++;1 s6 G- T7 g# G( d8 ?
else( N: d* K# A" x+ Q; m" R' |, |8 f
{
4 P) Q8 P7 E9 p: i same=B.elem[j]; //找到了相同元素same
+ r6 @7 r! G# \" ^+ h while(B.elem[j]==same) j++;6 Z! b& ]0 ~' ?- J
 while(C.elem[k]==same) k++; //j,k后移到新的元素
! u8 ? I, D3 b& v while(i<A.length&&A.elem<same)
 ~8 f+ ^) @9 Y3 I0 T A.elem[m++]=A.elem[i++]; //需保留的元素移动到新位置1 e0 C4 t& x$ r. r
 while(i<A.length&&A.elem==same) i++; //跳过相同的元素
8 S2 P* O6 w4 w @( Z, Q; B' h }
' q7 d8 [: f! {' c3 v ~ }//while
; g1 _' s |; K& w while(i<A.length)
% j; r4 Z- s/ M1 T A.elem[m++]=A.elem[i++]; //A的剩余元素重新存储。5 X( S; D0 p: f7 w
 A.length=m; ' N A( `) l, ]2 r. ]: c9 K
}// SqList_Intersect_Delete
/ }" v4 ~9 g$ m" r8 G* z分析:先从B和C中找出共有元素,记为same,再在A中从当前位置开始, 凡小于same的
- y. R3 u: N s! o2 _3 j% c元素均保留(存到新的位置),等于same的就跳过,到大于same时就再找下一个same. 2.30 void LinkList_Intersect_Delete(LinkList &A,LinkList B,LinkList C)//在链表结构上重做上题
7 q3 G9 l g4 Q7 V* W/ n+ Q! h{* ]+ o( o. |0 ]8 K7 y0 ~
 p=B->next;q=C->next;r=A-next;: R% a( `6 k% W
 while(p&&q&&r)& s2 h& [1 u( ~. v
 {0 T0 j8 F$ ?# M: D, G8 [
if(p->data<q->data) p=p->next;
; Q4 [, d9 S' h) L else if(p->data>q->data) q=q->next;; t+ g+ i3 E# o
else; k2 o6 ^5 e" C8 ? F$ y2 |3 Z
{* C+ h& b- X& O. ^' ?
 u=p->data; //确定待删除元素u2 v- B' G2 j% \; w3 [8 Z( w8 t
 while(r->next->data<u) r=r->next; //确定最后一个小于u的元素指针r
, t6 j7 J# \' ` if(r->next->data==u)
2 f( Z8 ~- n0 Z4 d" [: f {+ t$ B7 g( v5 O( ^
 s=r->next;
& ^1 G$ _4 z7 R( ]% S6 X while(s->data==u)
. [2 b$ ?! u1 V1 U, f {1 n$ ?( y$ {& ^1 K+ s! k" g
 t=s;s=s->next;free(t); //确定第一个大于u的元素指针s
+ S w" d: I- j3 ]) J5 {# q+ U6 D2 T }//while1 l+ ], x: v. w" S$ d) h( m
 r->next=s; //删除r和s之间的元素
. T' M: B. U2 A( T9 {6 \: T }//if
7 Z/ k4 i4 _+ s$ S" Q) N while(p->data=u) p=p->next;7 J) B( E. B% v" }3 M# L8 ?
 while(q->data=u) q=q->next;1 \4 [; E7 ^) s6 q5 N5 e! B. C
}//else( E) R9 ?1 y% y! l# }
 }//while
" E2 ?' C4 p( B& [( S) E: z G}//LinkList_Intersect_Delete 2.31 Status Delete_Pre(CiLNode *s)//删除单循环链表中结点s的直接前驱9 d2 b; ^2 w1 n& ] F
{# a8 h( y1 x6 j0 i+ c5 @
 p=s;
+ T$ e' b% E' S while(p->next->next!=s) p=p->next; //找到s的前驱的前驱p
' S8 s& p- ]9 D4 r! U5 W0 `3 Z7 d p->next=s;( b3 P: O& O- V c( q) |
 return OK;* P& z' k. w& [1 L/ P5 ^6 B
}//Delete_Pre 2.32 Status DuLNode_Pre(DuLinkList &L)//完成双向循环链表结点的pre域
& l! k$ x( W! f% t4 T{( t9 Q* n3 ~ u9 o
 for(p=L;!p->next->pre;p=p->next) p->next->pre=p;
8 b! g; f- h5 N& \ return OK;
6 P1 h2 v* y. ^5 r6 i( k0 h) h}//DuLNode_Pre 2.33 Status LinkList_Divide(LinkList &L,CiList &A,CiList &B,CiList &C)//把单链表L的元素按类型分为三个循环链表.CiList为带头结点的单循环链表类型.* T; k. a$ s0 Q B# W% e2 \5 @. \
{
9 q( u( B" G U: D0 {; f s=L->next;
# [4 D; o0 O' u; U& A A=(CiList*)malloc(sizeof(CiLNode));p=A;
, S6 `4 m) `! G" ]; `2 I7 ] B=(CiList*)malloc(sizeof(CiLNode));q=B;
5 T0 a4 [9 m; E8 M+ I2 k4 m( { C=(CiList*)malloc(sizeof(CiLNode));r=C; //建立头结点
' a3 \# m9 @. r9 i+ x/ U! @" v while(s)2 ^3 q& l* H* a4 o$ E: d
 {* A [% ~% `# p: _+ y* x$ s
if(isalphabet(s->data))
7 `5 U, r8 d1 A% Z% R {
9 G( b0 F! M, V5 M5 G' k' Z p->next=s;p=s;
8 A7 M3 d+ b+ B8 p0 S }
" H! Y% |" }! r4 f2 ~4 u6 D/ j else if(isdigit(s->data))
" D. r6 {# a$ g9 q s {
3 }) R8 N) [1 U q->next=s;q=s;+ D! r: y# F( a, U& l5 l
}
& N; U6 P0 b+ d) P3 H& v( f; D else( P+ M F# p- `9 N( K$ W2 y: N
{
$ p4 E5 ]# |# ]4 o M r->next=s;r=s;
! M) E! z, o3 i- K* c }( B, q7 I* o% B' k, n6 p
 }//while
6 S. W& \0 L/ D* B/ b( q; Q p->next=A;q->next=B;r->next=C; //完成循环链表5 ~4 \' ~' }8 V; n' v
}//LinkList_Divide 2.34 void Print_XorLinkedList(XorLinkedList L)//从左向右输出异或链表的元素值
- _( p$ Z$ @4 f{- O/ s# J K+ L W. o
 p=L.left;pre=NULL;. Y8 Y, B1 L& \) N2 V: i
 while(p)- C3 m8 g" C6 L: [9 K. Z
 {: q. L- D. |+ ]4 Y+ W' R
printf("%d",p->data);% s% r* H+ e* f7 E
q=XorP(p->LRPtr,pre);' {0 p& u% n* ~* K1 M: H/ S
pre=p;p=q; //任何一个结点的LRPtr域值与其左结点指针进行异或运算即得到其右结点指针% ? G z! n4 C7 k h. e! y" n9 L
 }& O- ` I0 [( W% R1 f8 o; r5 v* J2 n
}//Print_XorLinkedList 2.35 Status Insert_XorLinkedList(XorLinkedList &L,int x,int i)//在异或链表L的第i个元素前插入元素x
! f% _' c: l, d# U4 C! }3 H{* I- f) e* o; b+ b' j2 D
 p=L.left;pre=NULL;
1 C9 q( P7 b) x: Y6 p+ }/ f' s r=(XorNode*)malloc(sizeof(XorNode));
" g' m' M- n3 j1 o& i r->data=x;) S+ c) J6 P% f9 i
 if(i==1) //当插入点在最左边的情况 D% {- n3 ]/ t, Z% h
 {
" M# I& [5 m# J. j p->LRPtr=XorP(p.LRPtr,r);
4 b, J* Y9 [1 k+ O. m' V r->LRPtr=p;
- Q8 _3 J( ^) J: }2 |. K+ ^ L.left=r;0 m4 S. R" X0 e( e" k" B
return OK;
 @3 o% U/ U2 j z6 {0 k0 L }
 N p3 t# P. i: b4 r j=1;q=p->LRPtr; //当插入点在中间的情况2 d3 Q5 ^) J" i$ I1 p
 while(++j<i&&q)
# q2 o( _1 j0 m+ X. M; G {+ a6 R( a/ W* p8 \5 d
q=XorP(p->LRPtr,pre);
, r! ^$ ]% o2 \' k" Y: l pre=p;p=q;
) V- a% c1 c1 K& I# F, o( \! z8 u4 y }//while //在p,q两结点之间插入
! j/ |& z' s8 Z% `! K8 ^/ A! D if(!q) return INFEASIBLE; //i不可以超过表长) Y: l' p) F# V# F6 T5 w$ Y! j- A
 p->LRPtr=XorP(XorP(p->LRPtr,q),r);; x8 G& m/ _. s" y5 m9 o7 p/ G
 q->LRPtr=XorP(XorP(q->LRPtr,p),r);
# L S; M8 a: u9 R1 Q# f( L r->LRPtr=XorP(p,q); //修改指针9 `! Q" Y6 d Z/ r# l `
 return OK;4 @6 b. W' w0 }+ o; z
}//Insert_XorLinkedList 2.36 Status Delete_XorLinkedList(XorlinkedList &L,int i)//删除异或链表L的第i个元素8 d2 `8 L# v/ Z! J
{
! W8 r5 V9 n) h! A1 V4 ?& h p=L.left;pre=NULL;/ R% p$ @$ X9 S w$ Z4 P
 if(i==1) //删除最左结点的情况
* S: }) ^0 K: h, c, ?7 i {
1 A) c# H( l# ~ G q=p->LRPtr;
0 Z( Q# O9 F: T7 [! _# B. Q q->LRPtr=XorP(q->LRPtr,p);
! C# @6 I' w: L( _4 H L.left=q;free(p);
5 C8 X0 z! z( u0 V3 \6 Y/ L+ X return OK;
/ ]8 Z2 e3 X: G; J; m }2 a7 S6 E7 J4 D5 ^2 m4 m4 K
 j=1;q=p->LRPtr;
; f% N" Z/ N5 T5 k9 H while(++j<i&&q)
3 f' D: p& L+ C% H {
$ n1 v5 n' M6 I7 L' H q=XorP(p->LRPtr,pre);; s% Y/ h' m; i0 c# @
pre=p;p=q;6 X. X6 L% l2 z, a0 P4 q6 R
 }//while //找到待删结点q
/ ]! t3 \! N! D% c& M9 E if(!q) return INFEASIBLE; //i不可以超过表长
, B8 |8 z# |* ~6 ^& X) v if(L.right==q) //q为最右结点的情况
* @0 f6 [* \ _' @4 _+ W {) e. o# D, |2 r. F: J- R
p->LRPtr=XorP(p->LRPtr,q);1 ^( ^3 c7 P2 b$ R' P) k' |8 H% J
L.right=p;free(q);
( {2 e% H/ M$ |& h" \ ^- ^* s8 H return OK;5 p. h$ ~& q3 m; G9 N) w
 }
; e2 C+ x9 L& d- v, y8 l" d2 i r=XorP(q->LRPtr,p); //q为中间结点的情况,此时p,r分别为其左右结点
4 V, j9 m8 O& g6 z( }4 O$ w p->LRPtr=XorP(XorP(p->LRPtr,q),r);! r5 @ l, N+ G0 {3 J; K
 r->LRPtr=XorP(XorP(r->LRPtr,q),p); //修改指针6 V3 T( K+ W) ?; d: ]
 free(q);
8 o0 }/ | q( [ return OK;
; B8 p' F* p& z U2 w8 ?}//Delete_XorLinkedList 2.37 void OEReform(DuLinkedList &L)//按1,3,5,...4,2的顺序重排双向循环链表L中的所有结点- d/ |4 x, C, o% E
{4 M+ k4 F: u! P: X+ f S! W3 B9 f- g
 p=L.next;3 L, R0 Z. H3 m0 E2 Q' A, t
 while(p->next!=L&&p->next->next!=L)
- e" b' }+ g; l/ ~ {5 a; t$ q' \ t2 K2 f' F
p->next=p->next->next;/ S6 W: P9 W# U2 X& x- K. O& n
p=p->next;
9 F' s# n5 D& ?- _ o, @$ P& k } //此时p指向最后一个奇数结点7 u% N+ t0 J) v9 U3 I# M. [% r
 if(p->next==L) p->next=L->pre->pre;
( ]0 ?0 }, ~& A8 D6 Y i. l else p->next=l->pre;
" g: z2 x9 z5 C% G" k: h p=p->next; //此时p指向最后一个偶数结点2 E; m) j+ F, I; R. t% ~# s
 while(p->pre->pre!=L)
9 _" `& x9 W7 Q+ X" A {
$ [. { l# U/ K" X1 f) }" Z p->next=p->pre->pre; c7 N- e ?8 L' U, v2 ]
p=p->next;4 U3 } J! L/ `' R* j
 }
+ {9 k$ P- C0 r0 r$ h5 n$ a. w p->next=L; //按题目要求调整了next链的结构,此时pre链仍为原状9 J8 R. y3 b# i6 G' O$ Q V9 E5 D
 for(p=L;p->next!=L;p=p->next) p->next->pre=p;: j7 r; N& `1 Y& r" @3 U
 L->pre=p; //调整pre链的结构,同2.32方法
1 R' j# v# A; A( K}//OEReform9 u( j \- M9 J) I
分析:next链和pre链的调整只能分开进行.如同时进行调整的话,必须使用堆栈保存偶数结点的指针,否则将会破坏链表结构,造成结点丢失. 2.38 DuLNode * Locate_DuList(DuLinkedList &L,int x)//带freq域的双向循环链表上的查找
3 y: g7 b+ t6 X4 P9 X$ O5 H& d{' z; ?9 x, v& N6 t+ j3 U7 o' _
 p=L.next;
5 Z! d" g* T9 q/ X# Q, [" D! _$ w while(p.data!=x&&p!=L) p=p->next;
9 I6 V4 c+ d3 d$ z$ X8 m if(p==L) return NULL; //没找到
+ Z: g/ k+ X' q9 J* `, `" g p->freq++;q=p->pre;3 C, Q! C5 b$ \ I+ m- D6 o
 while(q->freq<=p->freq) q=q->pre; //查找插入位置
0 k/ y$ r. Y' I r( k8 }: G l if(q!=p->pre)- D4 _' O9 m4 I
 {1 @3 W4 D, V/ t9 y$ v$ {# d5 o* g
p->pre->next=p->next;p->next->pre=p->pre;# y: x, v3 r+ \$ }" _ b0 @. X
q->next->pre=p;p->next=q->next;$ S& f2 _$ P1 h/ ?$ g* c
q->next=p;p->pre=q; //调整位置
' s! K1 Y( ~3 t L }$ }2 {; k2 B- [, v3 n, Y
 return p;
& N* b C9 u1 G}//Locate_DuList 2.39 float GetValue_SqPoly(SqPoly P,int x0)//求升幂顺序存储的稀疏多项式的值
2 V8 B0 I$ A* g: e" W& N5 \{
" h b$ k1 h% Q' E8 y! O PolyTerm *q;5 y' b5 G# @ r
 xp=1;q=P.data;
* O* N4 \& z) y) P2 L. l sum=0;ex=0;) h! {6 Y7 c8 F; w/ g0 }/ ^
 while(q->coef)
! r* M3 o2 v- S" ~3 O {) e" L/ Z9 U4 w
while(ex<q->exp) xp*=x0;" g) q9 j* L2 ~2 M9 R) M1 B/ e# k
sum+=q->coef*xp;
. O6 o6 E# e g9 E6 J$ { q++;
" l Y) `2 Q9 E/ t }" ?- I/ b6 D; |$ _
 return sum;. U5 X2 o4 Y" m" r, K6 U4 e
}//GetValue_SqPoly 2.40 void Subtract_SqPoly(SqPoly P1,SqPoly P2,SqPoly &P3)//求稀疏多项式P1减P2的差式P3
9 K5 e) U* D( d% y{
) G, Q+ W2 P. V% V7 u* W- X! L/ N PolyTerm *p,*q,*r;
' s7 G+ ^, j$ U0 O; D | l Create_SqPoly(P3); //建立空多项式P3
) C3 `4 k( Y1 @+ {, R7 f# ~ p=P1.data;q=P2.data;r=P3.data;8 p9 \3 [0 `4 g! h' w
 while(p->coef&&q->coef)
6 P1 J; L7 i: G, { {
9 t( d* I* s/ m( _' [- v3 H if(p->exp<q->exp)' v! Y. Q9 ~9 X3 @* ~) @) _
{
2 n, o# v6 S7 n* j( e r->coef=p->coef;
! K) T% j' O& u6 a4 \% h8 I% m r->exp=p->exp;
0 Q8 F/ U( e$ R p++;r++;
' [+ ]9 P1 i% e, I2 a }
+ a1 h* ^, z9 R2 a0 P# \ else if(p->exp<q->exp)
, P1 R$ L b7 Z5 V) z, x6 x- s {* ] @4 i b7 k0 K1 u
 r->coef=-q->coef;+ w" |' J) M9 Y# p7 I, B
 r->exp=q->exp;
: Z# b2 h8 w7 Y q++;r++;* T2 R% c7 N0 M6 s, H
}" l8 a8 @. z& X W/ g2 f
else: u, E0 K& P5 D" q
{
& P! G+ @2 x. ~3 s* z, I: { if((p->coef-q->coef)!=0) //只有同次项相减不为零时才需要存入P3中
+ f/ L, i% U7 J2 j5 L# F {# k) n% Y$ C9 ]/ L* f* l, n! l6 _
 r->coef=p->coef-q->coef;" {( a, u% o& I& J
 r->exp=p->exp;r++;
/ R: ?9 K/ X- P }//if
7 X- Z Y. [- _. G p++;q++;0 [ O4 p3 u4 h& f; m
}//else2 I! [8 ^6 u$ c% s- n
 }//while
( j6 q8 a- p6 s while(p->coef) //处理P1或P2的剩余项
+ p8 v. Y% K1 Y- M6 ^( e* ^3 D {
 h7 M" U9 S# w: c r->coef=p->coef;' B& I1 ?) ^3 x7 x2 R: }
r->exp=p->exp;$ m6 e! z* S7 {& \3 g! n
p++;r++;0 k6 \$ D- g% z
 }
. R7 N8 w! `. X while(q->coef)% Q! _/ o- S* ~
 {
0 C9 _7 n( \4 ~. i# c r->coef=-q->coef;0 r/ R. q A% b% W$ D& B8 E
r->exp=q->exp;
+ M: y& ^# x' u) {4 w q++;r++;9 M1 N) t% \) v% i. h
 }0 W, O1 n+ e3 @' }/ l
}//Subtract_SqPoly 2.41 void QiuDao_LinkedPoly(LinkedPoly &L)//对有头结点循环链表结构存储的稀疏多项式L求导9 @; k& E" J n( K. w0 u
{$ N2 a3 J2 v5 W" u5 ?3 ]
 p=L->next;* P! W% o5 L X4 Y/ ?: d
 if(!p->data.exp)- C! m- c5 Q- \7 f. }
 {7 O4 ?/ J& Q7 H
L->next=p->next;p=p->next; //跳过常数项
: d" b# ?! Z4 x6 q9 v }; S# J% O- m" }4 O! |
 while(p!=L)% }$ k1 ^7 }' U- l7 ^8 R) `( G
 { R+ y1 J) O( K. w4 f+ {
p->data.coef*=p->data.exp--;//对每一项求导0 a: Z, a/ p: y- K2 q0 X
 p=p->next;& J6 L& N( {9 n7 f; }) t
 }
" c5 y: P; ^, C2 D}//QiuDao_LinkedPoly 2.42 void Divide_LinkedPoly(LinkedPoly &L,&A,&B)//把循环链表存储的稀疏多项式L拆成只含奇次项的A和只含偶次项的B
# H4 K8 b' p% p" H0 L{' s' _) a0 C, b [" I
 p=L->next;+ X( n6 ^' `0 b8 z7 `. R( j
 A=(PolyNode*)malloc(sizeof(PolyNode));
; U% w/ K6 A& D( N0 H$ K B=(PolyNode*)malloc(sizeof(PolyNode));
2 J7 M4 @ k( A* Y! l' l' c3 ^( g pa=A;pb=B;
# T) }4 o+ a6 ~. ^7 s, c& A3 A while(p!=L)
, P* |+ Z" ]3 N+ R {9 `# L/ B5 l ?. k$ i6 W5 w
if(p->data.exp!=2*(p->data.exp/2))
. R* Y( f# ?1 _7 J {8 d5 G4 e7 R: e5 r- d4 O& d2 v
 pa->next=p;pa=p;
8 P3 }5 F" C: }2 E. f% _ }+ A6 p7 o3 ~$ m7 l0 s+ v; Q
else1 W* h2 q/ }) _' `/ L: G. E7 g4 _
{+ o6 o! }8 A3 m( [2 f# n S9 k
 pb->next=p;pb=p;5 O6 _4 @" w( b3 z; I1 q" A
}0 D' @ K' Z+ K( s# L- d- d
p=p->next;% m+ ~8 h7 V9 d$ O: ~: r
 }//while
! w* E2 l5 e9 P" N' O pa->next=A;pb->next=B;
! ~& g# z M( w& k; m}//Divide_LinkedPoly