查看: 4976|回复: 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;
( h1 n% E6 y- f! x" D temp[k-1]=1; //初始化
( A) u/ S- e. s7 a+ [ for(i=k;i<=m;i++) //求出序列第k至第m个元素的值
5 T8 Y8 g V) z6 U8 R3 @ {+ q( h' L, [3 T/ o7 k
 sum=0;' `( g' X- C/ h; E7 G
 for(j=i-k;j<i;j++) sum+=temp[j];) [4 s% G( `. j5 V9 ~$ J- R
 temp=sum;+ S) V+ d% y. j$ Y8 N
}
+ }* \) C' s1 k$ q, e- ? f=temp[m];5 a, ~% s6 d- p: i
 }
, K% q9 E, Z2 b% J5 B* N3 b; j return OK;5 R) H, C. E: G5 K7 C
}//fib- @: w3 c" T) V: ]) v& y
分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m). : G; y. O% N- W% i6 `
<>1.18 7 X8 ]' p% ~9 \$ ^/ ~ |6 x
<>typedef struct{
1 c6 v& ]4 T, y/ s' m5 P char *sport;! \8 f8 q# Y9 q! H
 enum{male,female} gender;4 E3 n* }) V. t. V1 `
 char schoolname; //校名为'A','B','C','D'或'E'7 p- X0 G K9 u8 d
 char *result;
1 z2 `- C8 Q. V; {% o1 H2 O int score;4 O; p+ E3 N# I3 T, u* \
 } resulttype; 
# F) I; w* ^ ~ L<>typedef struct{' O4 T6 ^- `) a! j5 {
 int malescore;
0 a+ }& d" F. D4 G9 ]6 n$ n int femalescore;$ |1 `; k8 ?5 p) m0 k" B8 g3 m
 int totalscore;
- t. w) j: w* Q# f f$ y } scoretype; 
5 z$ p* I8 @3 e2 g" ^: U7 x. M<>void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中
+ s: e" p* X1 M{5 X1 ~$ G7 B8 `
 scoretype score;
- Q7 `; J* t7 V& P' W6 c( Q i=0;
/ G: t: z: i# i K" E6 B) p. m while(result.sport!=NULL)% R* f% z$ d$ v5 b
 {
, b' Z& f* K; J) u4 e switch(result.schoolname) b0 C `% S- N; V; C+ `
{
* g: j' M& k. I; o, K: ^ case 'A':& r( o+ l) W, s* N* n* z
 score[ 0 ].totalscore+=result.score;( P4 w% t8 t. _% I
 if(result.gender==0) score[ 0 ].malescore+=result.score;
. o" P0 n' U: p+ `9 }- V else score[ 0 ].femalescore+=result.score;: y! Q2 l6 V" X, @( C* ?) v
 break;
( A- K3 S3 A8 D6 e- `, t- R case 'B':3 I/ X* K1 a8 C( T
 score.totalscore+=result.score;
; G4 M) e6 Z* |9 }/ A if(result.gender==0) score.malescore+=result.score;
& S& i1 X K9 n! i6 A# e2 d else score.femalescore+=result.score;. B& r) H1 c! ]& t, B& D3 M4 x
 break;
* u/ Z6 o0 G" m2 ?+ ?( i+ k- @ …… …… ……
" o/ n7 J* m, {! _/ m" e. q }/ N+ M1 `) }+ [
i++；) O: \7 S8 i. v# s
 }6 P8 I X, I$ ]8 a( _; Z, @+ w: T
 for(i=0;i<5;i++)
$ w5 @7 x" K+ U) j' l4 O, V, V {7 r, `% D: J8 I9 O) c
printf("School %d:\n",i);% N; D! B( X6 {9 O7 }5 D
printf("Total score of male:%d\n",score.malescore);; _2 L2 o& ]/ T0 T# S
printf("Total score of female:%d\n",score.femalescore);
. d! U: T4 Q# B5 ]: _# }2 Z printf("Total score of all:%d\n\n",score.totalscore);$ N, B( O$ ` v0 r/ M- T% x
 }& `. m1 Z% `0 Y% w
}//summary 4 n& J- c7 |: G/ n* i. D
<>1.19 . t7 g! H& o4 \$ ^4 @
<>Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint ?2 g1 {! L% @' p( l
{
' X9 D3 M& i3 F0 [5 y: g# P) E last=1;3 w K3 N. F- r
 for(i=1;i<=ARRSIZE;i++)
8 ]) \$ `# l; ` {1 B, h R9 c; C8 l& C/ a9 [
 a[i-1]=last*2*i;% R" j! q- ^, f& N" q+ O' X
if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;
1 J0 | W7 l8 J/ K last=a[i-1];3 M+ }4 x+ u. y) v7 y
return OK;3 c7 T& ?; A' o! y" ~2 h
 }1 e) ]. V, y3 N; a6 Q1 v2 O
}//algo119
% g5 \2 U+ W& j0 A+ L分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. 7 j2 v6 \: u8 Y7 b' S4 ]
<>1.20 0 v: T3 h( G) ]- u; |9 v# {
<>void polyvalue()
: @( F# z9 A1 ^) J* A O{$ B0 R2 ?4 V& [, G* t0 j
 float ad;
8 M5 |) d; s# z$ e1 ?, A float *p=a;
* H6 l9 V8 K# y5 G6 J printf("Input number of terms:");
! s' n3 i# p/ |0 x; Z scanf("%d",&n);4 |, e7 P. q6 v/ a1 y
 printf("Input the %d coefficients from a0 to a%d:\n",n,n);# U2 J0 k5 w$ s' [: q5 G" d
 for(i=0;i<=n;i++) scanf("%f",p++);2 x$ {' u* ^3 b! c* $ V
 printf("Input value of x:");6 z& s7 l8 P% u% m
 scanf("%f",&x);+ [! L8 ]) N+ o% |: ^
 p=a;xp=1;sum=0; //xp用于存放x的i次方
 for(i=0;i<=n;i++)
 r' X7 m0 G% x9 [3 R% f5 n {
- $ a, z2 {/ L, F sum+=xp*(*p++);
+ {, P( @* q% h1 f( ? xp*=x;
9 x, V( b! w& w4 c7 H }8 P O. z' D( |4 t \
 printf("Value is:%f",sum);% l$ G& `4 k; l+ T* Z; S9 j
}//polyvalue
5 R& x0 G9 i4 x% F1 ~. P< >

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