查看: 4942|回复: 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 Y( t1 l1 |: a. p! [
temp[k-1]=1; //初始化
) s5 q" }; m; Y$ L8 ]$ w0 w5 @ for(i=k;i<=m;i++) //求出序列第k至第m个元素的值
/ ~7 ]8 I7 |3 N {4 n6 R* [8 m8 }
 sum=0;
( g' |7 _' ?" `% w+ | o( b0 P for(j=i-k;j<i;j++) sum+=temp[j];( n. n% G/ ~' b% F1 P7 i
 temp=sum;
+ {, K; \- S! B N7 }( t }4 J* Y6 {( P5 C0 n9 m5 e+ }
f=temp[m];/ \3 R8 L7 ]: w4 G& d
 }. X* A* o e3 \- Z: t
 return OK;: b- a4 E# [5 Y
}//fib0 {" ~+ j& W( i# }: m
分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m). 6 v3 ~" o [* A$ Q
<>1.18 
 x9 h+ U3 H( B<>typedef struct{0 _: t% E1 R7 s
 char *sport;
2 M( d0 ]: h8 x/ F- L enum{male,female} gender;6 y- n( h- L% i, O+ R5 H
 char schoolname; //校名为'A','B','C','D'或'E'
7 d+ ^5 ^( A' [8 S8 j( B& k char *result;
! S) ]3 X! V9 U int score;
0 Q( u" h1 Q& b$ r% N0 w" M2 @ } resulttype; 0 t% `9 _. y! R: _( p8 }) S0 q
<>typedef struct{
9 U9 |8 g7 s. D& E+ F3 e) [! @ int malescore;, ?8 m6 U. N) j" K! M; H
 int femalescore; Z% Q, @; N! q% d3 `
 int totalscore;' ]- F3 o6 M1 u. Z: `
 } scoretype; 
) L- h- x! s$ [5 A<>void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中
$ V- X! M$ ^ q& k. W{
+ E3 j! E$ u) M3 t& k5 A scoretype score;
* Z' p# w* Y0 P7 D( J0 @' x i=0;' I* m! g6 L9 s
 while(result.sport!=NULL)
" Y' n% m0 Z; h* U3 n* l/ b {
+ r% w% k4 s- Q- t switch(result.schoolname)
( {9 l/ y2 k L+ p; ? {/ I3 {: U5 H# F3 b8 U1 X2 w
 case 'A':
8 [1 y, H% J# i S score[ 0 ].totalscore+=result.score;
& S. w8 q' p! F) w/ b if(result.gender==0) score[ 0 ].malescore+=result.score;2 G( p8 p0 N5 L( Q7 n: K& ~( Z
 else score[ 0 ].femalescore+=result.score;
' M' h6 x8 F2 `/ A5 @1 p' s! f0 i' | break;
, `" I. ~: a' i0 x case 'B':, ^* }& N& |. c$ ]8 O1 Q6 C7 t
 score.totalscore+=result.score;; d* B* Y6 f) v
 if(result.gender==0) score.malescore+=result.score;4 S( T R9 ]2 ^) D/ T0 u$ z
 else score.femalescore+=result.score;8 w2 g, M+ `5 t8 d2 b) M8 n
 break;3 ~, ?$ _0 O" k- A! [9 U
 …… …… ……
; \5 P' q# K# G& e2 i }
/ u( n' m1 g/ i) l. {% Y* X$ W) g i++；; i' d. U7 U+ V& y2 ]: A' A, |
 }2 `& u. ^& y; f; A9 _* I
 for(i=0;i<5;i++)
7 N3 b# Q$ C( Q6 c ?- q. s {' D4 S; r" v9 f. O
printf("School %d:\n",i);: ]6 L4 m. T( ?# d+ s0 d5 @
printf("Total score of male:%d\n",score.malescore);6 T; ?' g! F% J& Z
printf("Total score of female:%d\n",score.femalescore);
1 d7 g+ A! B3 {4 Y* [ printf("Total score of all:%d\n\n",score.totalscore);* F0 L! N9 K) r2 ]' w
 }
, d! b' R( g1 N& [}//summary 
+ s$ n* o. n% Z" v% s<>1.19 
5 @. @/ x. n$ F. j0 C<>Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint0 F7 F- t2 _( Z* y3 E E; S+ o+ Y/ p
{
( E+ h& c% f- I8 n last=1;$ w, r, p# L1 r, F
 for(i=1;i<=ARRSIZE;i++)
1 _: f+ O+ J4 K w4 d2 |4 S7 i {
0 t# ~" h* k j, h7 O' ~1 b a[i-1]=last*2*i;+ k, a$ z9 [5 N% ^$ a
if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;
. O" z/ k* ?: l7 _% ?" p& Y last=a[i-1];4 c8 W( H; S0 W3 Q
return OK;8 w) I7 t0 p! ?" K
 }
8 s# V% V' q( c# C) K3 q}//algo119: K5 x0 |1 d* l, ^$ a& x
分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. 
! ]/ v1 z- c" F5 p0 w<>1.20 
2 Y, x0 e5 O s; o. i; L* ]) g* G<>void polyvalue()) k, g3 l+ m; N( X5 \
{
' `1 V# [: y: s float ad;. ]. V2 ]$ o7 R }: }
 float *p=a;7 K5 H+ k/ j" p; Q( g- n
 printf("Input number of terms:");
0 P0 W, a$ q [. {% w1 x' V, }& ` scanf("%d",&n);
! P q9 w) Q2 [- Y7 o5 d5 Q printf("Input the %d coefficients from a0 to a%d:\n",n,n);' z* |1 J5 ?5 C. P8 P
 for(i=0;i<=n;i++) scanf("%f",p++);
! f7 P( d7 F$ n! j printf("Input value of x:");* H$ e7 {$ r1 N9 c1 l' j/ X
 scanf("%f",&x);
1 J* _9 z- _+ L, N) R! @ p=a;xp=1;sum=0; //xp用于存放x的i次方! l# m+ o( ^' k; p
 for(i=0;i<=n;i++)
% G, I! J$ y9 ~; p6 | {. T: h4 z" \) i( v
sum+=xp*(*p++);" o2 ^' B8 U- o6 G" x
xp*=x;. T: x6 M! @/ i+ B! A e+ D1 V% D
 }8 w0 e6 N* r3 \$ P7 k# q" M
 printf("Value is:%f",sum);: [; U# F7 c. ?6 T& h
}//polyvalue
6 E( @& a+ J! f% 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--)
8 W% e c" f F/ |( v! A va.elem[i+1]=va.elem;, z, g! G x2 @
 va.elem[i+1]=x;
4 C9 \- r R. \9 f) T4 t9 C return OK;- d& o0 ]5 x( r& R8 z
}//Insert_SqList <>2.12 <>int ListComp(SqList A,SqList B)//比较字符表A和B,并用返回值表示结果,值为正,表示A>B;值为负,表示A<B;值为零,表示A=B) L: y# C n8 ]2 [" M
{
# e+ m1 ^4 I+ E, K( k- [9 [ for(i=1;A.elem||B.elem;i++)
" n! m, N5 d8 k$ K$ d if(A.elem!=B.elem) return A.elem-B.elem;
6 t/ ^7 D# F$ P( E return 0;
7 O3 k, P) G+ \( j2 D}//ListComp <>2.13 <>LNode* Locate(LinkList L,int x)//链表上的元素查找,返回指针9 a2 [/ P5 h1 a( @, C
{5 t5 T: F( P6 j, S# [+ m! D8 U m
 for(p=l->next;p&&p->data!=x;p=p->next);
. O3 }$ \" X q" |3 {1 t- ?$ ? return p;
 C; }' b6 G) n}//Locate <>2.14 <>int Length(LinkList L)//求链表的长度
8 O3 {. g* j8 U{
; K$ G: f) c' V* d- d for(k=0,p=L;p->next;p=p->next,k++);- j4 j7 x8 p5 g" n( y
 return k;) M3 w+ o( W& L4 {
}//Length <>2.15 <>void ListConcat(LinkList ha,LinkList hb,LinkList &hc)//把链表hb接在ha后面形成链表hc
& g) G7 q+ C9 f, R6 ~+ E$ e- u: ~! Q{
0 F' J. o/ f5 L% I hc=ha;p=ha;, h8 [' D, S9 e# n; D6 \$ Y
 while(p->next) p=p->next;! w% N- N% W; |! q
 p->next=hb;
) b! x8 S# ~* d: o- n1 }}//ListConcat <>2.16 <>见书后答案. <>2.17 <>Status Insert(LinkList &L,int i,int b)//在无头结点链表L的第i个元素之前插入元素b: Q; B9 \$ o4 J' ?1 p G: P
{5 L4 c4 U7 X# ]
 p=L;q=(LinkList*)malloc(sizeof(LNode));
. j, b+ S! x! i/ c- D q.data=b;" ]* d4 @' Q1 `3 T6 G
 if(i==1)
! y9 {4 [/ n( ]' [% ` {
, A; d& D( S+ @. M% h8 I' H q.next=p;L=q; //插入在链表头部
( w; C. n0 R' X }
, D" ^8 O' J$ m. I2 l3 e else
1 ]( O) e! j7 u2 U; f; o {
+ w: n" T& ]9 Q4 v8 M! q- w7 C/ V7 v while(--i>1) p=p->next;/ T' t& T9 w! [
q->next=p->next;p->next=q; //插入在第i个元素的位置" ]# u' z: u/ D
 }& x% x+ ?% Q) |/ k- g! h
}//Insert <>2.18 <>Status Delete(LinkList &L,int i)//在无头结点链表L中删除第i个元素% u5 M2 a# G0 B! F0 k. J/ u( m
{' b6 G' K( O: y8 m) D! x
 if(i==1) L=L->next; //删除第一个元素
7 X* v2 u" F7 Q2 {0 V else- } K: t& J9 g* ~& }
 {
5 A1 U3 @ I8 ^" z1 R2 |' i" a, ~ p=L;
9 \9 \( x9 N' h: a" f while(--i>1) p=p->next;1 B: ~2 S# f9 ?- _6 m* {
p->next=p->next->next; //删除第i个元素% l, M3 N' }/ p2 I* B9 L
 }
5 C. p) l) a8 \( |1 f4 ]' s; `}//Delete <>2.19 <>Status Delete_Between(Linklist &L,int mink,int maxk)//删除元素递增排列的链表L中值大于mink且小于maxk的所有元素- G" J& w4 ]7 z9 C3 E D, R# S2 U
{
: P! @/ w' k( r2 S/ @. w! S p=L;
8 o, b+ `# L- S2 x8 M while(p->next->data<=mink) p=p->next; //p是最后一个不大于mink的元素% t/ G1 g; I8 F
 if(p->next) //如果还有比mink更大的元素
* c5 Y5 S' M# G, x/ |% A {, L. |, v' K: x7 H) H
q=p->next;9 I9 q! }9 M; h$ S
while(q->data<maxk) q=q->next; //q是第一个不小于maxk的元素 Y! _1 o2 C5 M3 d7 G5 n+ Q
 p->next=q;' T0 R. ]! Y. l6 k% j$ p
 }: N2 d6 G% f$ `) {
}//Delete_Between <>2.20 <>Status Delete_Equal(Linklist &L)//删除元素递增排列的链表L中所有值相同的元素
) H& R* `9 l5 s3 e# Y6 Y! Z& ?{
. g9 o0 D: F+ t/ V) o* q4 i( m p=L->next;q=p->next; //p,q指向相邻两元素
& K7 N& T: x9 t$ S while(p->next)
* Q/ U" ]0 V G: s5 [1 h {
6 P5 h. x) I( Y9 y4 K7 L/ h: G if(p->data!=q->data)0 d4 a8 T, Y4 ~" Q
{
, F. V N F$ L) y% d1 X5 n p=p->next;q=p->next; //当相邻两元素不相等时,p,q都向后推一步
) o; A: t; H2 @* E1 l- ? }
3 \8 l i2 I: \% Z Y: P else( M1 [! Z j1 r% W0 U( n: h
{
9 Y% R& `8 ?2 |) k while(q->data==p->data) . K, `. Q* _, k3 E# {
{" F/ Z9 W& M' ^5 i7 m1 N
 free(q);
' T. s( o7 S2 v6 }% d% Z5 B* y/ q$ A q=q->next; 8 p3 ?: R0 X. H, R2 ?
}
5 T/ v ^1 @8 ` p->next=q;p=q;q=p->next; //当相邻元素相等时删除多余元素' _1 k! A% t& `) l
 }//else m) x* V2 T0 s t! V9 s/ B
 }//while
& \& I0 H) M! d9 v}//Delete_Equal <>2.21 <>void reverse(SqList &A)//顺序表的就地逆置
 m- A2 ]9 f& f% v7 R2 I{ i; e* x" N$ q% Q# p
 for(i=1,j=A.length;i<j;i++,j--)5 |1 [: G1 m; ?8 v5 k8 k
A.elem<->A.elem[j];8 Y- b" p& U% `3 F; c s5 J7 P
}//reverse <>2.22 <>void LinkList_reverse(Linklist &L)//链表的就地逆置;为简化算法,假设表长大于2% Y# f P1 h( v
{
3 I. B l8 x7 U j p=L->next;q=p->next;s=q->next;p->next=NULL;: h, b0 n9 d+ T; g& v0 F9 n; N/ R2 ]
 while(s->next)
/ r# m& A3 G$ ^ {
9 V, O G, k0 G/ k& m9 ` q->next=p;p=q;
& T4 N* U6 L. U x5 n8 p$ M q=s;s=s->next; //把L的元素逐个插入新表表头2 d6 ^, k5 D, M5 T
 }
& f" C0 u% R! Y6 y5 u* q q->next=p;s->next=q;L->next=s;! [% c5 I' ^& K E
}//LinkList_reverse- e2 }4 I; M1 X5 ^8 M! X( s
分析:本算法的思想是,逐个地把L的当前元素q插入新的链表头部,p为新表表头. <>2.23 <>void merge1(LinkList &A,LinkList &B,LinkList &C)//把链表A和B合并为C,A和B的元素间隔排列,且使用原存储空间
6 F; c) J4 {8 ?5 N( u{' J( r, g- R) \3 M; {4 G0 f
 p=A->next;q=B->next;C=A;
2 ?, _7 N; k+ K2 C/ w1 `& ? while(p&&q)# u* r+ v. C2 Q; l _
 {
4 U# s @$ X0 x8 B# U s=p->next;p->next=q; //将B的元素插入
( _# v i3 a' } if(s)
* x) r: w- v) g$ o/ C: P {( k/ Q% U) r, i
 t=q->next;q->next=s; //如A非空,将A的元素插入3 x, V, l" K* Y
 }
+ M, E, q- P$ x p=s;q=t;
: q- T" x0 k2 [ }//while
& r; M" C5 o0 w6 \9 \9 J* B% E}//merge1 <>2.24 void reverse_merge(LinkList &A,LinkList &B,LinkList &C)//把元素递增排列的链表A和B合并为C,且C中元素递减排列,使用原空间
9 Y8 {$ N% Y9 T{' `" n: X: ~: w s0 t9 r2 C
 pa=A->next;pb=B->next;pre=NULL; //pa和pb分别指向A,B的当前元素( V0 O" G# ]1 M, G& `
 while(pa||pb) V9 u3 l- U$ p$ d v% {/ h
 {, _$ |) w9 ]4 t1 ]7 g
if(pa->data<pb->data||!pb)) R3 h/ T( _& D
{
1 E8 I* Y' d2 u- x& k9 [ pc=pa;q=pa->next;pa->next=pre;pa=q; //将A的元素插入新表
2 a0 ^" Y' b( M- d }
3 k( H6 a5 y1 T& |7 z else% e& S0 r, e1 X Z4 G3 t
{
3 H& B( `$ Y3 B% h7 h* w pc=pb;q=pb->next;pb->next=pre;pb=q; //将B的元素插入新表
/ I$ U7 [* }8 s; q- { }
" n! V% c% ^" e) {/ i- @ pre=pc;
6 O' b Y3 J- j% `2 w" T) Q }* h3 g/ |' ^* E: T* `9 \' S
 C=A;A->next=pc; //构造新表头
/ Z6 f% m' v% t/ U}//reverse_merge! a" n! `* Z7 ?% H p
分析:本算法的思想是,按从小到大的顺序依次把A和B的元素插入新表的头部pc处,最后处理A或B的剩余元素. 2.25 void SqList_Intersect(SqList A,SqList B,SqList &C)//求元素递增排列的线性表A和B的元素的交集并存入C中
; m$ M( I, X% G' Q2 o, y{7 I8 s$ m) P: u. n
 i=1;j=1;k=0;" d/ }3 t) p$ D: o+ x$ H. e6 e* G
 while(A.elem&&B.elem[j])1 M1 R: c1 P9 @* W
 {5 ?4 k. x5 Y9 H& r& Q- k+ ^
if(A.elem<B.elem[j]) i++; J& i/ b9 ?+ K9 W5 E$ f# ?. x
if(A.elem>B.elem[j]) j++;
+ ~' X3 A# \$ Y) a" `/ X if(A.elem==B.elem[j])% a3 ~4 `2 X& c; ^7 F q0 u
{
+ ?) R7 }5 P0 d+ a% t C.elem[++k]=A.elem; //当发现了一个在A,B中都存在的元素, |, l' B0 W5 y9 @# S
 i++;j++; //就添加到C中% k3 Q3 o( V. d4 I2 J) \% X
 }( r( G2 Y$ N8 T0 n
 }//while8 ^' K7 P+ A4 S. Y1 n; d3 T" |
}//SqList_Intersect 2.26 void LinkList_Intersect(LinkList A,LinkList B,LinkList &C)//在链表结构上重做上题6 V. V4 `; m) z
{
- A; U, x# b( q1 m0 ]/ ?* h& b2 j5 W p=A->next;q=B->next;1 O( V b+ p- R9 |5 q0 ~6 g) c
 pc=(LNode*)malloc(sizeof(LNode));
: b. O5 {$ `" z" S while(p&&q): y4 ^. \" ~' Y. V
 {. @$ x W& ?' t1 E( ]8 ]/ A
if(p->data<q->data) p=p->next;0 J8 d/ ^9 s7 g& {7 y
else if(p->data>q->data) q=q->next;
+ a) ] j: z# Q" ^; P$ d2 N else
! k8 n7 d: X2 [ {
3 g7 O0 C5 j! O j8 C s=(LNode*)malloc(sizeof(LNode));
# m. F( t5 R2 ?5 v) q0 H2 E( e s->data=p->data;
4 @& g) t) c* L pc->next=s;pc=s;
9 X' c6 c. O6 e0 r* ] p=p->next;q=q->next;2 | G& \! {& F% I I7 d$ D$ ]
}0 J4 A2 P* [1 |' r
 }//while- S5 {+ w0 |' M- d% E
 C=pc;. o1 y- v; _, S0 j" e
}//LinkList_Intersect 2.27 void SqList_Intersect_True(SqList &A,SqList B)//求元素递增排列的线性表A和B的元素的交集并存回A中
! w$ @2 m& P! j, u: W* A7 Q( D, l{4 W* C9 Y4 M8 {0 g) U; w
 i=1;j=1;k=0;
& J4 Y5 K+ n T9 C( @ while(A.elem&&B.elem[j])
# V" m8 O) I+ [5 s# L' x; | {0 T+ @& v4 O6 G. J! N+ ]0 G6 I9 L
if(A.elem<B.elem[j]) i++;
# f- v4 _! @1 P3 s else if(A.elem>B.elem[j]) j++;9 F2 a( u( B- F7 v# g+ M( {+ l* f4 A
else if(A.elem!=A.elem[k])
( s u. y0 u. a! g3 w' G5 N {
. j. ], i" d$ U* F! C A.elem[++k]=A.elem; //当发现了一个在A,B中都存在的元素 g: S7 @/ a g+ B9 t3 P+ ~
 i++;j++; //且C中没有,就添加到C中
+ G. T3 T e$ d' ]: ?& u; a6 o }0 ` ^, d" n7 W9 I
 }//while2 o, C+ i7 w4 e3 j$ [3 S" K4 C
 while(A.elem[k]) A.elem[k++]=0;4 D/ Y0 K) c4 q$ ]
}//SqList_Intersect_True 2.28 void LinkList_Intersect_True(LinkList &A,LinkList B)//在链表结构上重做上题4 j& O' e( p. y; w0 S u+ `
{
* U% h3 l& k$ `2 F) t! v8 t p=A->next;q=B->next;pc=A;
7 @1 u- \8 a% X, H$ `6 E while(p&&q)+ W5 K5 N$ l3 z# U4 f9 W* j
 {7 Q; `) H, R" E: y6 l
if(p->data<q->data) p=p->next;, Y8 V$ p5 `8 q s
else if(p->data>q->data) q=q->next;: `; L+ I! W: m2 R* d
else if(p->data!=pc->data)
" ]4 s# y5 L2 ], `3 o {5 D$ z) e" a5 y5 m1 y X* l5 o* m) P
 pc=pc->next;
" d( c q0 d# } [6 G pc->data=p->data;
4 M4 g) R0 a1 B8 ~* d( v/ F) A p=p->next;q=q->next;5 B2 h r" W+ o4 R h$ ^) G( K5 x
}3 G% C; l/ p& `" W# c3 {
 }//while
6 B8 h5 B ^) s) J}//LinkList_Intersect_True 2.29 void SqList_Intersect_Delete(SqList &A,SqList B,SqList C)
3 ?; ^: L. t( Q4 z+ u{$ G! |- I+ Q5 Q7 G" [
 i=0;j=0;k=0;m=0; //i指示A中元素原来的位置,m为移动后的位置
0 C9 c6 w) u# ?. B; R/ o: V" _3 ^ while(i<A.length&&j<B.length&& k<C.length)
# m6 X- a1 |3 \ {4 D6 w4 h9 x* f- j- W
if(B.elem[j]<C.elem[k]) j++;; `3 h" |- r, D# q1 G0 m/ ~! O) s
else if(B.elem[j]>C.elem[k]) k++;4 E. B6 k) \8 S& {
else
0 D4 y) Q3 d2 L+ F {
3 [* J2 ?, H. [3 Q same=B.elem[j]; //找到了相同元素same: j8 E# S/ o @
 while(B.elem[j]==same) j++;& N+ L' Y7 f& B
 while(C.elem[k]==same) k++; //j,k后移到新的元素
+ v) ^, D: N# D3 b& p, p while(i<A.length&&A.elem<same)
9 h/ {2 {' y; ~4 C( e' E A.elem[m++]=A.elem[i++]; //需保留的元素移动到新位置9 Q+ d. i3 `6 s
 while(i<A.length&&A.elem==same) i++; //跳过相同的元素+ [: _4 k1 Q2 j0 C+ a* F% _ G
 }
% b# ~. O* E, |: s2 d7 z }//while5 Z; b. ?8 Y8 D/ g/ }
 while(i<A.length) 2 s: P$ u9 |4 v4 H3 f4 G$ X9 @
A.elem[m++]=A.elem[i++]; //A的剩余元素重新存储。; q4 {9 K- L g/ X1 m
 A.length=m;
' b" M2 c+ S9 w" c" t* k}// SqList_Intersect_Delete" B6 V( b! f6 A! y
分析:先从B和C中找出共有元素,记为same,再在A中从当前位置开始, 凡小于same的# [8 _8 R0 g6 w; k+ m
元素均保留(存到新的位置),等于same的就跳过,到大于same时就再找下一个same. 2.30 void LinkList_Intersect_Delete(LinkList &A,LinkList B,LinkList C)//在链表结构上重做上题- b' w) Y8 L% w2 w
{
, U, s. a% j- T! G& v p=B->next;q=C->next;r=A-next;8 e) U; J- `- o- m3 |1 j
 while(p&&q&&r)
 f. }; O$ c$ f- E5 Y- N {9 ?; R9 b' Z/ t* T' t. C+ A
if(p->data<q->data) p=p->next;8 K5 n E9 e, I& I+ H
else if(p->data>q->data) q=q->next;( l8 p0 Z/ X1 u; k. F8 o2 c% a
else
, I/ w/ U+ v. g0 ^# F( A {
& d- A8 L2 A1 a# c% c u=p->data; //确定待删除元素u
3 j' U: z$ x& ?1 T0 R while(r->next->data<u) r=r->next; //确定最后一个小于u的元素指针r
1 N d* |% v0 R if(r->next->data==u)0 U* @1 W) K# y$ q5 g
 {
" [! v1 A8 e3 s s=r->next;
" u+ l1 A3 I) j* _. h6 L8 | while(s->data==u). d; U& |+ I/ r8 a
 {/ z- X0 a4 y# J' O/ i( I! U
 t=s;s=s->next;free(t); //确定第一个大于u的元素指针s/ _- S4 P& n9 H1 r
 }//while
* l' K, E5 H2 e* @* I0 n: l r->next=s; //删除r和s之间的元素' T' _0 s/ o d; V
 }//if
% x5 ]$ q/ }' [! d while(p->data=u) p=p->next;6 C. l5 ~* E) G; ^! k, M4 Z2 y
 while(q->data=u) q=q->next;
6 ]& k+ R; c" N; U0 y }//else
) H7 N% W8 h4 B& {" D }//while
! ]9 {3 o) Q2 h1 Q }# I}//LinkList_Intersect_Delete 2.31 Status Delete_Pre(CiLNode *s)//删除单循环链表中结点s的直接前驱% z* B0 |3 n5 ~' p
{
 s+ L# X1 w8 O p=s;
0 ^2 N( A& N, s while(p->next->next!=s) p=p->next; //找到s的前驱的前驱p7 M) X/ L/ N& t6 h; y
 p->next=s;
- @6 A5 E3 p. b( n: x return OK;7 n! ] X4 i4 A- l& J
}//Delete_Pre 2.32 Status DuLNode_Pre(DuLinkList &L)//完成双向循环链表结点的pre域
, _& n1 {! ?' `' f{
/ `9 D5 x( m: B; Y4 t( w/ I for(p=L;!p->next->pre;p=p->next) p->next->pre=p;+ d8 g2 w1 ^7 w, E
 return OK;
4 B. w; i, e3 b! x}//DuLNode_Pre 2.33 Status LinkList_Divide(LinkList &L,CiList &A,CiList &B,CiList &C)//把单链表L的元素按类型分为三个循环链表.CiList为带头结点的单循环链表类型.& ~: @1 c% z2 F9 v" Y
{, ^% Y# O% I% C9 R8 j
 s=L->next;
1 A* j$ r& \6 [1 E5 R; [" S A=(CiList*)malloc(sizeof(CiLNode));p=A;
) @4 O: }7 n3 I2 a" ^7 \; W B=(CiList*)malloc(sizeof(CiLNode));q=B;
( {' F( S% ~/ C4 f: O C=(CiList*)malloc(sizeof(CiLNode));r=C; //建立头结点
+ W% A4 f ?6 u2 e, b while(s)
( W! a$ R' x$ _9 z, \3 N# P {
3 e7 u% s( ~3 }1 b$ f if(isalphabet(s->data))( c+ }( R" T: [% K [8 a9 o
{
* l' B( ]! S7 O$ c p->next=s;p=s;
4 d( g" Q5 A; a3 V+ [2 N }
3 [7 w6 k5 x1 i; I2 N else if(isdigit(s->data))
& M0 B* g+ S" r- g+ O. Q; _3 s {
- _+ |+ O; z0 t% n2 P# t/ } q->next=s;q=s;
" _* n8 e, F- \! ? e. Y }
6 n1 k- C. ^8 p! u9 N else2 N% }9 u, w# X( K1 [
{
' Q* J; k* H4 N) v r->next=s;r=s;
5 H' A B) P9 S* N, ?) P/ m7 P }
) ^) S0 I. j% ^& K$ l0 ?8 G }//while, R0 d4 y+ I, h8 S3 l' j
 p->next=A;q->next=B;r->next=C; //完成循环链表) J& e8 s+ S/ M2 e( w( L0 {0 ^
}//LinkList_Divide 2.34 void Print_XorLinkedList(XorLinkedList L)//从左向右输出异或链表的元素值
+ w/ e0 B1 X1 d0 g% X2 w1 W. P |/ _{
6 F) i. W- H3 |: Y. { p=L.left;pre=NULL;4 u0 j2 v4 n7 Z8 P7 ?9 `
 while(p)
8 |8 R% v8 I& [& o {& f2 [9 O$ U3 t, ]* ]$ J, f9 ^9 q: {
printf("%d",p->data);. a# c7 b% {; B2 ~
q=XorP(p->LRPtr,pre);5 @6 U( h$ u7 Q% m! g
pre=p;p=q; //任何一个结点的LRPtr域值与其左结点指针进行异或运算即得到其右结点指针% B/ l6 c# Q% Z$ z3 L, }) H
 }, p( k" @) e; t6 t8 o* d
}//Print_XorLinkedList 2.35 Status Insert_XorLinkedList(XorLinkedList &L,int x,int i)//在异或链表L的第i个元素前插入元素x
) P+ {8 m& Q+ o2 z7 ?0 ]0 D' F{5 ~& n( |/ y% o) h# w
 p=L.left;pre=NULL;
( D" x) u$ C6 F, Y Z r=(XorNode*)malloc(sizeof(XorNode));+ u0 t$ z) h+ N0 g' j: A( i
 r->data=x;
: K5 e0 ^6 w h/ y* ` if(i==1) //当插入点在最左边的情况
7 @4 v7 n* _3 A {
% d4 X# c* W+ ?' I, \6 T1 z1 I p->LRPtr=XorP(p.LRPtr,r);8 {5 O E0 P% I0 G' `, m' S
r->LRPtr=p;: I" E' r5 z$ N: j% M
L.left=r;( J, s9 f3 z1 |$ K6 n, h3 V7 g
return OK;# B0 b* Z; q2 o6 b+ e- d* T
 }" y6 w/ a7 ~: F; @+ F% ~0 P
 j=1;q=p->LRPtr; //当插入点在中间的情况7 t9 ? Y \; w# L% o
 while(++j<i&&q)+ D0 o2 I. g" p/ |: S
 {7 k: T, N9 Y$ O: R
q=XorP(p->LRPtr,pre);. D6 r0 h. M; t- ^
pre=p;p=q;
* U# p: ^' ^; S& j! O! F0 F }//while //在p,q两结点之间插入
; c$ @1 l% m9 t. G if(!q) return INFEASIBLE; //i不可以超过表长, n8 w" \& _: e
 p->LRPtr=XorP(XorP(p->LRPtr,q),r);
: e7 ]$ m. r% F q->LRPtr=XorP(XorP(q->LRPtr,p),r);
; O( t' k( X4 h* o8 q) O; u r->LRPtr=XorP(p,q); //修改指针
( {& G+ Y, Z/ d+ q3 ~- I return OK;1 A3 y/ y( g$ s5 {- |* ]
}//Insert_XorLinkedList 2.36 Status Delete_XorLinkedList(XorlinkedList &L,int i)//删除异或链表L的第i个元素2 m% P& }$ I' ~
{: C% l: q% s: j+ s9 l
 p=L.left;pre=NULL;
4 t' _, i& c( F' t7 [4 v if(i==1) //删除最左结点的情况
$ Q) A) b; T. C' b% y {
/ ?" j. c4 s! c7 i5 F) x q=p->LRPtr;
% ^" C4 v# K. g3 `$ ]$ x+ J q->LRPtr=XorP(q->LRPtr,p);0 n7 g6 h7 m5 H: l. q* X
L.left=q;free(p);
' w a$ h+ {9 o+ } return OK;
" C3 Z7 o% H! u" l; h9 [# [# \ }
$ H6 r& L# y( L j=1;q=p->LRPtr;7 y+ w: r% c+ L9 W( J
 while(++j<i&&q)
4 b5 V8 v5 D" |6 n) N5 _7 V6 o {
( N$ x; ]' s7 b# z# K! u q=XorP(p->LRPtr,pre);; v: u% ]5 w6 J1 ^+ A
pre=p;p=q;& p. U! G$ ?# f4 q( o
 }//while //找到待删结点q
. N% i1 K6 ^$ t# `0 O5 R, ]; v if(!q) return INFEASIBLE; //i不可以超过表长
" d# p; X, L/ J; J. q" S if(L.right==q) //q为最右结点的情况
" a& B$ X' Y* ~- K {
9 p7 ]& s( |* ~, a% H; O0 h. n9 V p->LRPtr=XorP(p->LRPtr,q);
( K8 r% j, G. F1 N5 L2 Z' J1 I L.right=p;free(q);
; O6 }! k# E! e+ ?4 q' j9 | return OK;
9 X4 Q6 ]- M7 ~( e5 O! j" @- q }" e3 g# u: L( f" B
 r=XorP(q->LRPtr,p); //q为中间结点的情况,此时p,r分别为其左右结点' A4 A! } d8 J: N% c# _" O' f
 p->LRPtr=XorP(XorP(p->LRPtr,q),r);
& z# g: g7 |; }5 b8 O. F9 B! V r->LRPtr=XorP(XorP(r->LRPtr,q),p); //修改指针( c$ w0 t$ ~& L) H* P* ?; M, D* Y
 free(q);
/ n; F: ?9 J8 S- \; `* H6 c' C return OK;5 Q5 { H7 I. D, r
}//Delete_XorLinkedList 2.37 void OEReform(DuLinkedList &L)//按1,3,5,...4,2的顺序重排双向循环链表L中的所有结点' ^8 |0 x7 C1 z1 u' _' z
{
7 p2 L( t g" A) T9 F2 r p=L.next;4 y% ~1 M, S* | O* O
 while(p->next!=L&&p->next->next!=L)/ G o- i# a# U' U9 k9 r
 {9 S- j6 k8 S/ r; G
p->next=p->next->next;
1 O8 |+ r t$ s9 m2 [2 A, m$ i p=p->next;
, O; b( c: c( ~9 ^$ f } //此时p指向最后一个奇数结点
! X( s6 ]. d* Y# C+ y2 x6 I if(p->next==L) p->next=L->pre->pre;, g3 l1 A! s& N1 }: n1 p
 else p->next=l->pre;7 d' D9 q& w, \+ a0 P
 p=p->next; //此时p指向最后一个偶数结点
8 l. A' j" \ s' a4 B$ a while(p->pre->pre!=L)
& d* }3 H7 G: {4 t( X P {7 V7 K! y, y4 M5 _4 V4 e5 D
p->next=p->pre->pre;
+ E' z9 d( Z2 p I/ l0 W0 i p=p->next;7 R% y4 P, v8 E' [% E& S7 d' p( p
 }, c- h4 I1 G% t! z/ V* {
 p->next=L; //按题目要求调整了next链的结构,此时pre链仍为原状8 Y; C/ x. R# \: m9 D; {2 n# h
 for(p=L;p->next!=L;p=p->next) p->next->pre=p;' g; X! Q6 g( B; Y! Y& y u! \
 L->pre=p; //调整pre链的结构,同2.32方法
- a$ x' t% C1 N) E o}//OEReform
* `5 x4 v: |) P7 U4 t" D9 u分析:next链和pre链的调整只能分开进行.如同时进行调整的话,必须使用堆栈保存偶数结点的指针,否则将会破坏链表结构,造成结点丢失. 2.38 DuLNode * Locate_DuList(DuLinkedList &L,int x)//带freq域的双向循环链表上的查找& C, j' C& b& D& L m- Z
{$ ^# D! Q* }# p' q/ Z! `
 p=L.next;7 h# u8 K: L5 N+ M
 while(p.data!=x&&p!=L) p=p->next;, u) M1 }+ ]$ |
 if(p==L) return NULL; //没找到
: H& r Y( N9 y9 e. m: w p->freq++;q=p->pre;
' ]9 Z* k1 u' |7 R& ?: W) X& Q) @! _ while(q->freq<=p->freq) q=q->pre; //查找插入位置
% {( I6 m+ E: m+ |$ Z* P$ b if(q!=p->pre)
( \/ g; R, V$ Q- i( _+ } {
7 g; m O+ u/ F: ~ p->pre->next=p->next;p->next->pre=p->pre;
" x9 \4 i0 |) r* g6 e q->next->pre=p;p->next=q->next;* |' c* O/ j1 _" i% ~- Y0 Z
q->next=p;p->pre=q; //调整位置& h( u1 X3 _# V: T
 }
3 @" y' r( l5 ~9 w" \( | return p;' e: E B0 a7 f: Q1 `! [# W" Z
}//Locate_DuList 2.39 float GetValue_SqPoly(SqPoly P,int x0)//求升幂顺序存储的稀疏多项式的值6 w; l, A* G; [, O3 l
{
) d' U k$ W) J& a- X* m PolyTerm *q;
( H' I6 u% }+ }" j xp=1;q=P.data;
$ l# I7 `- _" t4 j/ a3 h( _ sum=0;ex=0;
- u# v( ]8 S; e2 g& ^5 G6 b5 f while(q->coef)' Q2 A" f! ?0 C
 {
" N1 z! Q6 y7 o7 c* A* r$ K8 M while(ex<q->exp) xp*=x0;7 f& N4 m3 O7 X$ e
sum+=q->coef*xp;4 w2 \# l6 k- Z9 c4 S0 q4 b) _
q++;
, O' A/ ]: K7 {0 |6 |/ | }
8 j" J' Q2 @8 `$ q+ S& X1 r return sum;
* x+ v, @3 y& S, z& T- X" A4 B}//GetValue_SqPoly 2.40 void Subtract_SqPoly(SqPoly P1,SqPoly P2,SqPoly &P3)//求稀疏多项式P1减P2的差式P38 j. @. k; C. x- y
{
' _' `! s% a7 F- u' ~ PolyTerm *p,*q,*r;
( i# I0 M2 G" U Create_SqPoly(P3); //建立空多项式P3. f! S4 O+ S5 V. b% Z0 p' S6 h: E# s$ O( ^
 p=P1.data;q=P2.data;r=P3.data;* d4 D1 Y( k6 v) Z/ P
 while(p->coef&&q->coef)
1 R3 h" v4 p. a/ Q' H {- }- x+ h! Z! @% U1 U' d
if(p->exp<q->exp)) ~5 A! w6 K) g% F
{
0 {7 `! B9 F* S$ q& U4 b r->coef=p->coef;. N7 G8 x0 O1 |5 V- _8 f
 r->exp=p->exp;
 ]4 W J& z- e2 ~7 v p++;r++;
% ?+ j$ {% u+ u5 I1 x1 [ }! j$ u/ u! r, c
else if(p->exp<q->exp)
- s9 n) |7 P1 O9 v4 C {
& {; P+ ]3 Z* z6 S r->coef=-q->coef;
: U# \: d6 Z) h. @# j7 S r->exp=q->exp;
4 O$ R o5 f* `/ E q++;r++;& a# D% }3 u" [- g m
}' E3 ?/ _9 Y1 w2 G6 E4 ]" d/ l
else
) G8 H6 g! V( z6 c: S) z {$ Q$ c3 H8 u2 G
 if((p->coef-q->coef)!=0) //只有同次项相减不为零时才需要存入P3中- b, S6 j( c" C
 {# J6 N5 y7 f6 @* l/ P- K
 r->coef=p->coef-q->coef;9 i/ {' g8 z0 G! d- ?5 N p' W
 r->exp=p->exp;r++;
1 ^: ^, h3 W- L' N& k }//if
: L: t) f6 e2 w& M p++;q++;
. [5 ~) R; M' S5 y }//else
0 a" U: ?) u4 n j" I }//while6 L8 }" X9 n) c! A
 while(p->coef) //处理P1或P2的剩余项" C) Q n3 [# r* z2 E+ t3 r
 {% g& i" c& y2 U% W
r->coef=p->coef;
! Z2 U8 j; c0 O" c# @ r->exp=p->exp;
# I% |9 C( g0 J9 b9 A! d% T p++;r++;
: y0 J Z6 {: N9 K$ y" h }- s: ^* A; F8 P
 while(q->coef)2 N/ Y, h; L' X- ]3 j8 r' I, x- Q) |
 {
8 E- W' V) {& h" |! r0 Y$ q( ? r->coef=-q->coef;' T- u l- n& T( q e# v
r->exp=q->exp;4 }, z" x h q; L" d( _: J
q++;r++;6 k2 k3 X6 w( U8 z! S3 F5 N
 }5 _: |% n( F) n: @! w T
}//Subtract_SqPoly 2.41 void QiuDao_LinkedPoly(LinkedPoly &L)//对有头结点循环链表结构存储的稀疏多项式L求导
8 K' M+ h3 S1 n/ o/ A9 M{
* z+ ^; j0 w: Y' k% Y" g p=L->next;
1 h- g9 {3 c. Z2 \& v if(!p->data.exp)
# p5 m0 w* b, L8 Z {8 Z1 H0 z# f' I- ?4 Q3 v
L->next=p->next;p=p->next; //跳过常数项
8 l' a6 L8 r, _ }
 while(p!=L), o: G2 u9 h# S0 {$ }
 {& z$ n/ B9 z) J1 U
p->data.coef*=p->data.exp--;//对每一项求导
: X! N$ T6 Z3 j ?4 l p=p->next;$ |: F6 h8 I# Z) R1 [! t
 }
( B4 ~6 Q% i0 _( K}//QiuDao_LinkedPoly 2.42 void Divide_LinkedPoly(LinkedPoly &L,&A,&B)//把循环链表存储的稀疏多项式L拆成只含奇次项的A和只含偶次项的B
4 Q$ n$ ]2 K3 H3 B F{
& v" u0 q1 r0 e- {( Z p=L->next;' Z( ~7 Z$ Y: n0 o6 t7 h
 A=(PolyNode*)malloc(sizeof(PolyNode));' @( D$ M' S1 y
 B=(PolyNode*)malloc(sizeof(PolyNode));
" }& @8 l- K! N8 {, M5 d- [& i) e pa=A;pb=B;
- R9 U! Y% n3 a: p while(p!=L)6 c8 u1 A1 z4 t* h% ^( A" F' \# M
 {1 s- R1 d. y# I( x/ [: e
if(p->data.exp!=2*(p->data.exp/2))# y; |$ d# U0 g
{# U& f' R, t1 a4 \& k; Z+ V) d3 c
 pa->next=p;pa=p; i9 |. s% x; B) o# `3 _1 B( t
}" ]& [. |5 r' V1 X N& H5 b: r0 J" g
else- I, y; j/ Z0 w/ {( \
{
1 d U9 j) s& h8 {4 F# A# S pb->next=p;pb=p;
: J8 G& F+ X8 D9 v/ n& x2 n }. s0 Q$ `6 ~7 o4 b4 k, b; z0 Q
p=p->next;4 D7 K m* p( l) T! T6 P1 |, L
 }//while
; K) F U6 q2 \4 K- l pa->next=A;pb->next=B;
: e- H0 |% I# ]. S& y}//Divide_LinkedPoly