查看: 4939|回复: 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;
9 } }/ t. [7 T- ^4 ` temp[k-1]=1; //初始化) j0 ?$ A; k8 C! X+ w
 for(i=k;i<=m;i++) //求出序列第k至第m个元素的值
: I A/ p, x( _3 a8 x4 E {
* v0 h0 h( G' a, b4 T sum=0;6 p0 Y& j& \/ ^' A$ i0 ]
 for(j=i-k;j<i;j++) sum+=temp[j];
; ~& m* M) l* v5 Q! ]: M) ` temp=sum;
: s1 s, G, k! G }* x/ P# t9 I1 L" r
f=temp[m];+ p1 V7 _! E6 Q7 y, m7 A% f. n
 }
! J" s4 }) W5 \$ B9 ] return OK;
! i3 y) A1 h% X* k4 `}//fib& P0 u' W0 G: P3 j; w8 D J
分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m). 2 r7 R7 O/ F$ v# t2 `& H2 R6 x, A0 V
<>1.18 
5 m! m2 i Z$ Y" ~<>typedef struct{& A: O) u+ Z2 B$ g- t* _
 char *sport;
) s- G" [0 s( \+ Q8 h enum{male,female} gender;3 R2 K# n- m; e7 X; k) t g2 ~ U
 char schoolname; //校名为'A','B','C','D'或'E'
" z) P9 V. N* M+ {$ e4 X* P ?: T: U char *result;
. D: C. r6 g' {9 _$ @ int score;
 c. G7 v1 ^" o; | } resulttype; 
/ E7 u: V" C& P" ]4 D. |1 N6 M<>typedef struct{' F4 X+ _" ~, k+ y+ o* Z* c" t
 int malescore;
) t6 r0 m+ T) c+ k' c int femalescore;
; q- m' m: l0 F' {% i: r, } int totalscore;1 O1 d$ G( M y) ]
 } scoretype; 
( H4 l. g# x- {8 K: o, {5 D+ s% J<>void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中
7 r% U( f3 [9 P( }& q% q{9 |9 y, J3 R7 a
 scoretype score;; J2 f2 s d r' ^0 y' m) U
 i=0;
; H& E, C7 w$ m; D( K while(result.sport!=NULL)
, S9 H9 a3 a; O/ ] {8 ^7 C8 ~" ~/ R1 Q+ y" E; H
switch(result.schoolname)" p- U7 Z* s% U
{
: o; y) I$ ` F+ c" ?& d case 'A':
' K, D/ F; O% `2 d3 a* z) ^ score[ 0 ].totalscore+=result.score;
: q1 [: T, H3 b# o/ b if(result.gender==0) score[ 0 ].malescore+=result.score;
% I+ J3 M3 U! Q C, F- b else score[ 0 ].femalescore+=result.score;- \) s+ \7 T4 v, F' G% T( p0 p
 break;
7 x* U- v+ M: w7 d case 'B':
* }! {% m/ w" P# I7 \ score.totalscore+=result.score;
& O1 m* H9 ^' g- X8 J* z if(result.gender==0) score.malescore+=result.score;5 z, t6 I8 `" j' l
 else score.femalescore+=result.score;
$ Q9 v; L9 a6 }3 s/ h break;
+ U# R: g) C; [9 y# g" d0 w* p …… …… ……3 P' W7 m0 x3 o# _
 }8 ^+ k6 J) r. J' U
i++；
* g* v j: v3 N* b }
! x) l0 K* @% N: S5 v" q for(i=0;i<5;i++)
/ N2 W+ b5 @2 v$ I+ E! A: U# m% M {- R, t0 S+ x8 L: }
printf("School %d:\n",i);4 M( c; `% T8 B1 f% U
printf("Total score of male:%d\n",score.malescore);6 $ z9 W- N6 Q* b/ A
printf("Total score of female:%d\n",score.femalescore);; ], S* M$ X t" Q! a
printf("Total score of all:%d\n\n",score.totalscore);9 J, y; r% d- \- y
 }
' j6 z. |+ }5 M. z, R% u' R- }: ~}//summary 
8 G: f) ]7 Y( l1 C# _$ f$ r" K4 d<>1.19 # W& Y* D, M8 {2 s
<>Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint
1 E w& H# C. _9 b1 f* ~1 N{6 C; O' A1 S+ T1 }
 last=1;% o3 Y" Z5 H# ^; k0 v4 `, p
 for(i=1;i<=ARRSIZE;i++)6 _- O$ |. v8 A
 {' w! [1 Q* P/ j q; H4 ]
 a[i-1]=last*2*i;7 $ W. p+ B2 g) o- P4 E
if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;3 V r2 m7 b+ w+ G
last=a[i-1];
0 _; k+ U+ {& V' k7 L) F! D return OK;
% t; p+ i0 c' _ }5 Z4 Y% i: e8 f- {: o" J* @
}//algo119
! c8 s6 Y9 f% l" `+ ~0 n3 c M分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. % G5 w" Y* }3 Z! ], K3 O
<>1.20 
3 A& `# ]- \% @2 b& H Z<>void polyvalue()
# t1 y" F( \- h I; ]3 }% r: @6 o{
, ^; g2 N8 V, n7 I: ^% ?2 g! q float ad;
& a7 }( k% ^8 v, G# N/ w float *p=a;5 x8 B& [" j' {( J( \& D) O
 printf("Input number of terms:");
6 @' B/ B' | L9 i scanf("%d",&n);$ {" E7 [! m1 o# A3 z
 printf("Input the %d coefficients from a0 to a%d:\n",n,n);. [% }+ W1 H3 O) W
 for(i=0;i<=n;i++) scanf("%f",p++);
4 E4 u5 z! H1 _2 l. C printf("Input value of x:");3 E- Z3 A; Y! S
 scanf("%f",&x);& [, ~* S$ A5 X* l
 p=a;xp=1;sum=0; //xp用于存放x的i次方
% v% X& B3 D6 f. N* u6 i! n for(i=0;i<=n;i++)0 _/ ^* K3 ~; v$ ]) q( }
 {
2 h9 a* y, s( ? \: ~ sum+=xp*(*p++);* }( b k; X$ }! A) w) _# j
xp*=x;
2 m. J: y8 m4 L# y6 q- t& m; E } O9 M/ G5 h2 W3 ~3 |$ t0 Y$ [
 printf("Value is:%f",sum);
' x- m0 _+ P) _2 Y}//polyvalue( _2 J% N: X( V. Q2 c
< >

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