查看: 4941|回复: 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;
8 b: C5 Q; b8 T- P1 \* H0 S temp[k-1]=1; //初始化# {1 l( S* i/ K2 F4 v
 for(i=k;i<=m;i++) //求出序列第k至第m个元素的值
! L9 _3 p) R( }! n {
# I3 @1 `. t/ n1 b* l$ z sum=0;, ^* W3 ~' z. u5 X, V; }: C# |; S- I
 for(j=i-k;j<i;j++) sum+=temp[j];
/ y0 {) \: k0 f' Q( O6 U: j temp=sum;# d3 l1 ^! X& N9 o2 P, T( F
}
' ~- L7 k! e" a" ? f=temp[m];
7 C7 a3 z' }0 Z: p) \% G }
1 l2 t! _( ?: S return OK;
$ e3 @% B7 N N, U% ^* y}//fib! e# z7 ^9 Z0 c9 y! ]
分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m). ' d+ {5 h; q* _* P
<>1.18 8 J$ x+ s) |( O3 {0 o
<>typedef struct{
& s; _/ C5 \1 g- E$ h7 y% v char *sport;1 G. S9 m( H/ W+ o
 enum{male,female} gender;
3 j0 F w* A* E9 ? char schoolname; //校名为'A','B','C','D'或'E'
' y& V0 f- \: u: ~. r/ y% A5 M char *result;2 @7 }2 T4 s, J6 G8 a/ Z% D P
 int score;% V# d R2 p ?) U
 } resulttype; ' J) M& i9 G6 S/ W% J& j1 g
<>typedef struct{
1 X1 {$ k7 p1 F/ S3 c2 @, e4 v6 U% z( { int malescore;
1 ~8 p) `9 p" L5 R5 t* O7 w int femalescore;( Z" s( T: D' o* O" s
 int totalscore;- t2 r. o# w" d: C2 \3 D
 } scoretype; G( ^' @* @2 B- _% ~/ ~
<>void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中
! b' [3 V; a9 z: \4 E{! L' q0 N9 o6 |5 H
 scoretype score;5 C; o% Y! z0 Y$ g( }: a5 Y" h4 ~
 i=0;* C8 E3 a1 `/ Y: p
 while(result.sport!=NULL)( {7 F k5 p0 ?4 ~, P( ]( k
 {
& k/ ^8 m9 J7 Q5 U, p) [9 S6 [- e0 \3 [ switch(result.schoolname): t9 I! B1 Y0 ?+ e7 v5 P X
{7 E' L4 T- j, q& z% j# A* ]
 case 'A':
) H8 D4 L' m, F7 Q+ Q6 Q# `5 j/ F score[ 0 ].totalscore+=result.score;
, i) z4 M' T; l1 i) @4 M if(result.gender==0) score[ 0 ].malescore+=result.score;
/ {9 M; |! i ?7 n+ e, T2 K else score[ 0 ].femalescore+=result.score;$ |) |2 ~6 T( Y% k9 `3 q
 break;9 K% I+ t- ~$ x7 o
 case 'B':
8 @: u9 @; s% ^9 A( W5 @8 r$ { score.totalscore+=result.score;
! P1 i: j0 d; M7 w if(result.gender==0) score.malescore+=result.score;
7 ~# c) g2 z" _3 H# C( P$ _ else score.femalescore+=result.score;3 z* {4 f4 U% Y2 o( @
 break;
( |8 j1 N& ~9 |2 h6 P& o …… …… ……, U. G9 ~' P& |; t$ P! r
 }
! b Y Z. v$ y# { i++；, \* A% Q; k1 L
 }
# A6 {7 M7 c. i# G for(i=0;i<5;i++): J1 q- ` X9 F& V8 z3 c
 {) F1 X) l0 J# Q% u5 d4 ?* p; k
printf("School %d:\n",i);
 W8 U4 u/ u P+ g3 e4 h printf("Total score of male:%d\n",score.malescore);
" S( D. d+ a/ y8 u/ d0 S$ ~ printf("Total score of female:%d\n",score.femalescore); v- Y; Y6 s5 p+ J# U8 \) x2 P
printf("Total score of all:%d\n\n",score.totalscore);
; U) }' ?7 o' R1 q+ N( F }
! B0 I5 [& g1 q& G) b* v: b/ ?+ A}//summary 
: F& u# K! Q5 r0 H<>1.19 9 R( I. G/ G6 Y
<>Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint
3 H; q; r$ o# b3 t$ A% R% N4 {! O7 i2 ~{
7 s h% d6 Z8 m; h1 p$ R7 p9 } last=1;9 q- |0 q- E6 {7 x% y7 }, n
 for(i=1;i<=ARRSIZE;i++)$ w- f) l" `% w; x$ L
 {& Y7 A; U; _. \) W \
 a[i-1]=last*2*i;* f0 g b, \7 p% @1 V, U
if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;- B, E9 e! m( L9 x
last=a[i-1];
- F" b) q1 a$ D* [ return OK;
$ t4 y0 q8 d1 \2 d; c }6 d6 P; \: M; W+ V6 h! [" p5 J
}//algo119
7 g0 _0 l! p3 p' I- r6 y4 r: V分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. u$ O' `6 G3 x3 Y
<>1.20 
$ N- D) ~7 K+ Q+ j2 u" d$ g! ]; j<>void polyvalue(), G4 T5 b3 ~) u, [% S& q" d3 j
{$ _: @/ f' i- V F) I! B: w
 float ad;
% T. e( z% j$ ~/ i8 P( a float *p=a;
) s9 P/ o. V6 G, L; { printf("Input number of terms:");
/ w& B, r; x: z3 O0 w* [ scanf("%d",&n);
, p) D% q O1 N" ?( @5 R printf("Input the %d coefficients from a0 to a%d:\n",n,n);
) j* Q$ c: F: t+ ~% H; z. A for(i=0;i<=n;i++) scanf("%f",p++);
9 R5 z2 o% G; y: A. m printf("Input value of x:");' W8 h+ L& F0 d; C
 scanf("%f",&x);( {6 m5 I/ h1 o2 [) y! A0 Y
 p=a;xp=1;sum=0; //xp用于存放x的i次方
0 }; o/ Q" J' o4 p* @. n for(i=0;i<=n;i++)7 ]8 |( D. D9 x5 Q
 {
0 {/ V6 `: @) ?6 u* z6 x. X; ^1 r* G sum+=xp*(*p++);2 _& e! F6 ?4 g2 q) ?4 ~
xp*=x;
4 ~: h! N8 b# P& j }; G; U! s7 i" S( U$ \# B5 v! Y
 printf("Value is:%f",sum);4 A! F2 Q0 B. i9 y1 R
}//polyvalue6 ]7 f" }9 q# W4 A. f2 n. R D
< >

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