查看: 4993|回复: 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;5 E `5 \2 z( W' x: m
temp[k-1]=1; //初始化
) i- a( I% q. c) z7 j for(i=k;i<=m;i++) //求出序列第k至第m个元素的值
: n6 `6 u; ^/ g. C8 v( N {
0 N3 C2 K1 @1 V. A6 X. c sum=0;+ ^. O% |$ J6 l9 l# [
 for(j=i-k;j<i;j++) sum+=temp[j];
4 R8 z/ [6 v) Z7 b8 w temp=sum;) R$ Y$ h; Z( m! F1 t4 v, R$ g
}. K3 \. @& x0 D, C) l
f=temp[m];
, ~6 c9 e6 X% ]1 }5 u }: [; F' I- T" Y# b3 n$ Y. Z1 O
 return OK;
: L1 N. c) T3 g9 f' j}//fib
8 T, f, ^9 h: i9 B b. O分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m). 
& P( o+ K- k& r3 x! ^+ @<>1.18 
# L! ^1 s2 b6 ^( U3 W6 g<>typedef struct{2 Q; r: p% k- Z. t
 char *sport;
2 s- c# v2 @$ s enum{male,female} gender;; }7 J& O9 T$ s
 char schoolname; //校名为'A','B','C','D'或'E'% C' y5 _' U- g. E; j2 H1 b
 char *result;5 h* R% b8 b2 u1 T& w$ n
 int score;
6 I' J& W( s& @: y' T2 M6 @2 U: c' Y } resulttype; 
3 }2 G% ]: \" z) H! x<>typedef struct{
# M, X: q7 m: Z. ? int malescore;
3 O0 X; h% q5 E( c" ~ int femalescore;
: a7 y/ c7 V0 n; V' P9 | int totalscore;- y' N' ]! r* F' T6 k9 B/ h) L6 c
 } scoretype; : I0 \ l; ]7 C/ |3 o
<>void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中" a" F; ?; l h' c: |( v
{4 w0 ^& c- t, C/ S _/ [
 scoretype score;$ j \! _; }# A% a; Y
 i=0;: U, L+ g4 t, z* Y
 while(result.sport!=NULL)) }" P0 F2 G. j! w: M
 {
0 k* s9 e; d g" V switch(result.schoolname)! c! z' u! V; X3 p4 ~& ?: I- d
{
3 V; s8 z# F* r5 V1 j! g# U case 'A':
: P6 |# h7 C4 d3 R1 P. R; K score[ 0 ].totalscore+=result.score;$ P4 S( v4 J+ Y% h+ W) i" I
 if(result.gender==0) score[ 0 ].malescore+=result.score;
/ d3 q, o' b$ x( Z3 O/ j ~ else score[ 0 ].femalescore+=result.score;; W; o. B& @5 n' J0 p
 break;
8 _& N# A. S+ i+ l case 'B':
" h8 n6 V1 t' D4 l score.totalscore+=result.score;
% U& w# c" W6 _% N7 l7 [ if(result.gender==0) score.malescore+=result.score;/ P% A" i0 w9 g+ q6 D
 else score.femalescore+=result.score;
 s. }6 y' |7 [6 @ break;
8 ^4 Y9 g! {7 i3 o; _$ q …… …… ……
7 v" F0 C* T, f; | }. P8 T$ g4 b. L2 ?
i++；: o% ]$ x' L9 l7 ?3 ]/ M
 }
5 l9 `, v# ?2 F# s4 S for(i=0;i<5;i++)+ q& e% ^% x: D! X+ U
 {
& }2 w) u, j# ]) f4 A- r% ? printf("School %d:\n",i);
+ ?9 j/ Z6 s+ s- N6 M printf("Total score of male:%d\n",score.malescore);
# Y6 u% Z0 }: e2 R; |" [ printf("Total score of female:%d\n",score.femalescore);5 O( |9 H% q8 B- Y/ X' \8 D
printf("Total score of all:%d\n\n",score.totalscore);
3 T! \* J3 v% k. S# w( j: {: ?9 w }7 z9 q& }/ M( V( [
}//summary 
" c* x! V2 \. [7 S T<>1.19 8 v6 ]: o. v: b% @# O
<>Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint p$ D1 x1 m2 j3 ^. H e/ F
{; k/ x; Y, n5 q
 last=1;* H; I+ x) Y3 S
 for(i=1;i<=ARRSIZE;i++); ~& |/ P1 z0 l
 {! u% Q- B/ `5 h! n: t
 a[i-1]=last*2*i;, g1 c) V5 @# j7 L3 D, H- s
if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;5 Y4 Z3 D' S, R: R0 k
last=a[i-1];0 B& l: u1 h+ `- }: ]
return OK;. b" [5 ]! n, y8 Y/ _9 a
 }
1 J: a# C: Y; c) c# L8 y# _}//algo119
& H1 W5 Z( D! i7 p% R" e8 s分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. 
1 o) t. r! b8 u: b<>1.20 
) N. c( B0 w+ U2 F$ w5 B' ]<>void polyvalue()
7 g; f. G/ c5 K$ k0 |{
- J9 Y/ k% @6 L+ N# y float ad;: Z, l1 v1 v+ A5 W; @. T
 float *p=a;, A a- M$ H- u h) V/ c! h) }
 printf("Input number of terms:");
. O) i9 ^ e/ l scanf("%d",&n);
 d3 S) ?' E) T7 ` printf("Input the %d coefficients from a0 to a%d:\n",n,n);- D- s2 |! u' j }* N
 for(i=0;i<=n;i++) scanf("%f",p++);
1 Z+ q4 O; g2 a% `7 R printf("Input value of x:");- h% y4 m# c, s2 g, z
 scanf("%f",&x);$ u$ z" M J1 j" M2 Y* ^0 F$ P g& y
 p=a;xp=1;sum=0; //xp用于存放x的i次方' O3 M4 i) ?; Z4 }, Y
 for(i=0;i<=n;i++), E* A1 W& }/ T% |) U! W0 D* V
 {
8 c' z# q. E" p, j# C' |9 u sum+=xp*(*p++);
# ]4 [1 K% k4 _& x! f& F0 @ xp*=x;
$ f. h0 R! Z4 W8 x/ q }
6 W6 A0 e6 _/ p1 t9 G1 g- _5 n printf("Value is:%f",sum);. C1 q% Z9 A, r6 C& ]# Z% B
}//polyvalue
4 d: }$ Z" }4 @- A( w< >

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