查看: 4762|回复: 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;
3 x& [9 ^. ?. \3 M" n2 ? D" X temp[k-1]=1; //初始化
5 r9 y3 j, p7 @: d( }% Q; Q for(i=k;i<=m;i++) //求出序列第k至第m个元素的值/ F+ ^$ ?0 h$ @1 E
 {, K. L9 }3 X9 ]. ]4 R( l- n
 sum=0;
 c7 }* X% J% _, W+ F2 a for(j=i-k;j<i;j++) sum+=temp[j];
3 u' ~& s, R0 ~: P6 W5 g4 l temp=sum;
6 d' Y$ u" [+ S1 i$ M% ?& ? I }
4 j$ N. E+ Z/ p; F) r3 r f=temp[m];
6 A: R) R! }4 J8 j# d- s }- }; u: w" h/ x+ V( x D" Z
 return OK;+ U* p* j* P" P, L
}//fib
' z+ f! s7 j7 U2 @, h分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m). 
0 Q0 R0 b! ^: D. Z: S) C<>1.18 ; A. Y* ~' E) Z2 l1 ]
<>typedef struct{3 R7 U$ H" A6 N4 b7 C& E; s
 char *sport;0 s1 m/ ^' V0 [# e8 f
 enum{male,female} gender;0 J }: p* n s& s
 char schoolname; //校名为'A','B','C','D'或'E'
" u) S5 L Z- a2 u# a char *result;
4 D, A e6 R& R) g. Z9 m% q int score;
' @- X' R( m0 k$ R' @7 a } resulttype; 8 P; w5 D9 |6 w3 @3 f$ `
<>typedef struct{7 s/ @. E; Y: O
 int malescore;
6 ?: F/ u) D: Z- s% [ int femalescore;# g) \0 w) M$ {+ m! j2 b# F% p
 int totalscore;
4 T7 P. a0 P, ^% Z } scoretype; ' a8 w4 a I3 D* B6 G
<>void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中
) b& v; C! {9 x4 I{2 x! b6 l9 e9 G+ F! _- p
 scoretype score;4 G; t6 X# D0 q+ y' ~/ l3 l
 i=0;+ D" @* \% N! c4 H' i
 while(result.sport!=NULL)$ X" A4 B) b. g5 S* I
 {
0 L2 t. B R/ ` switch(result.schoolname)
6 l$ C* `- N( x8 L% R {
 ]5 U, [% ]) ~6 Q# j case 'A':, V+ u" @, l' P2 q2 T$ j; s$ a
 score[ 0 ].totalscore+=result.score;
3 w; d. v# ?& [. H: g4 B if(result.gender==0) score[ 0 ].malescore+=result.score;: C0 e4 v* v0 c5 C+ R6 q9 u& r2 \
 else score[ 0 ].femalescore+=result.score;
6 h; | e, t" `5 j$ Y, p break;
5 h* r* b8 j. V3 P2 ^ {7 F case 'B':
( G1 S: ^! l! G+ l/ Q6 F( f- B score.totalscore+=result.score;+ o7 L( r: o( Y8 w" s: M
 if(result.gender==0) score.malescore+=result.score;. }8 {/ @& |$ U7 m7 j; s6 q
 else score.femalescore+=result.score;
 Y L/ @2 c8 S0 [ break;
/ C; v2 C6 K% ]/ R+ K. t) c …… …… ……
% B3 y! s' V1 S2 F" G! J( } }2 M) q4 ^9 m0 ?) C" }& v# O8 H
i++；% N. Q" Q* K3 z+ n) S1 T6 j# T! ?! c
 }
; ^: n9 F6 k& \8 b# U& v for(i=0;i<5;i++)' o# C% B7 i- |0 U2 O1 c @& e
 {
" ]* _$ r \0 Z2 C7 t# Y7 e printf("School %d:\n",i);8 ^! |" Q, z6 }; N# {: \9 Q3 F
printf("Total score of male:%d\n",score.malescore);9 g$ T* h. T) `; @; n
printf("Total score of female:%d\n",score.femalescore);8 V9 |, ^5 t$ S+ z0 C1 G
printf("Total score of all:%d\n\n",score.totalscore);
6 d. Y3 p: \& k+ c/ H. w7 [& W" ]0 ?7 I }. m1 }# v4 v X* i/ [/ H h
}//summary 
/ W) ?% `2 U# [: m<>1.19 
/ u7 s+ b; {5 n. ~, l" H<>Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint/ O/ u7 W6 K& n7 Y% {5 N
{6 \6 P3 K% ]2 \; \/ {
 last=1;
& T3 H1 E; `0 J5 a& l for(i=1;i<=ARRSIZE;i++)/ t: L9 Z& X3 g
 {+ A& b, V- }4 N+ W. R) S
 a[i-1]=last*2*i;0 w" ]- H' K- ~
if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;, m; ~- `/ e& Q* T
last=a[i-1];: M' W' L6 {# D1 K9 F' C
return OK;7 I9 k; o* `8 U8 d0 O9 a5 v2 a
 }0 |* N5 V3 e* S* ?6 ?- B1 a
}//algo119" r5 J; H F+ L( C! W( m
分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. 
$ t2 x6 h; d1 G& T! l8 u<>1.20 1 t5 y3 Y* \: p0 _( P5 U/ s( ~1 A: Z
<>void polyvalue()
- I1 ~' ~0 Y5 S3 {/ w{
3 ] f; Q+ W5 H+ i& y6 g float ad;
7 d5 g* z# w6 {0 I7 ^$ |; p5 ^ float *p=a;
2 {0 u. q. t5 y) b* J printf("Input number of terms:");9 ]* p) e7 n O7 S3 D! U. q+ t: `2 h
 scanf("%d",&n); |7 T/ [; X, \& b! V1 M4 m. E
 printf("Input the %d coefficients from a0 to a%d:\n",n,n);$ d8 h8 o s4 n
 for(i=0;i<=n;i++) scanf("%f",p++);
3 b% D D W9 j printf("Input value of x:");, Q; t- m; w) l' l
 scanf("%f",&x);. n9 P4 i2 e7 l% m9 v6 X7 f4 [
 p=a;xp=1;sum=0; //xp用于存放x的i次方7 X7 o( X. ~+ o( l
 for(i=0;i<=n;i++)# {8 P1 P: V2 \+ W! h8 e6 E) d
 {
; v% v( x" y3 M* O$ n0 g* U sum+=xp*(*p++);% V9 g7 |1 p; ]/ |* L; [
xp*=x;4 W( @ g- R% d* R3 G0 [* Z
 }# U. z3 i, \+ p$ D$ v
 printf("Value is:%f",sum);: ]$ b% Q5 ? q1 n2 j7 h, J
}//polyvalue1 L' @. _0 p5 Z7 E$ G# i
< >

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