查看: 4947|回复: 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;
. b( t2 ~- w, m p3 h" t7 o) {+ Q temp[k-1]=1; //初始化4 y9 }1 T f1 r% ?, Z8 h
 for(i=k;i<=m;i++) //求出序列第k至第m个元素的值
( a& }" n- z- x/ x( } {
( ~0 k6 f2 B0 d6 _4 v) B% ` sum=0;( s0 e) U; p' d8 y( ~5 Q% _& `
 for(j=i-k;j<i;j++) sum+=temp[j];
& p! q1 l! T3 j+ a n' X temp=sum;
; R. B; j8 [% `9 N9 }0 R }
- o7 M+ j( U. L* ]- w; M e; s f=temp[m];- \; V; `8 I* m/ ]; s2 {
 }
) o+ n7 J8 u9 [, \5 L, I! l6 j return OK;; b9 p' w0 ]& [/ e( t8 P7 ^
}//fib
% H: E4 z, C) U. x' Z7 W分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m). 6 V- a' z G2 P$ K8 J
<>1.18 ; M8 \2 V1 j0 {/ h! ?& n; }2 F
<>typedef struct{8 F" T6 F2 f! D
 char *sport;1 k z" V1 @: T, A, j" P
 enum{male,female} gender;
# i/ e+ ]# n# H+ H# ~( ]# I char schoolname; //校名为'A','B','C','D'或'E'
" w4 U" _' J) @' @: v" b char *result;
+ h2 Z# @; |4 S3 K: \. U- P int score;- g8 G- g4 B- v1 z2 r
 } resulttype; 
1 ~. ]0 p0 Z7 b4 y! O, K<>typedef struct{
1 q3 ?8 M+ Z/ v9 m* f! A7 p0 @; w0 U int malescore;
1 U/ h+ {% m9 m* ]" J int femalescore;1 v* b! _3 `& O; u) G. t5 e
 int totalscore;
- l9 t5 h. T& A, X# o9 { } scoretype; 
& \4 z: i# b0 w! r- J4 o<>void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中
% M7 c4 T! j# q6 |* f' l. x0 j{ g/ |5 `2 O4 \+ O' Z4 [- \
 scoretype score;4 z" z M" b) d. e& C
 i=0;
0 H6 P5 {+ G: C) P, I7 w* k while(result.sport!=NULL)2 y5 K8 w3 P8 `! ^
 {
: d7 Q- N& L/ {% g9 k switch(result.schoolname)2 ?: Q B' H+ {# I
{
8 c$ W' ^" O. g/ P' u" [ case 'A':6 u! v" r1 M4 Y$ J" P
 score[ 0 ].totalscore+=result.score;
7 s6 n& }0 h |0 U; `+ ~: @2 j if(result.gender==0) score[ 0 ].malescore+=result.score;
- ^" h# F* I, P/ k else score[ 0 ].femalescore+=result.score;
 f, s1 I6 }! o' g+ @2 X! g3 Z break;' }5 L8 E! {. T2 P0 T9 @; ?
 case 'B':
2 ~$ k6 O7 Y1 g6 U score.totalscore+=result.score;% |; e) c( g& ^7 \9 ?) [: l6 {4 j$ Q
 if(result.gender==0) score.malescore+=result.score;
2 W5 q% [ b' _. q8 [% ^ else score.femalescore+=result.score;
4 x/ Z: y% j, h5 {4 @ break;
2 Y7 V$ j' z l, @ …… …… ……; S: E+ J1 v7 K' u5 S0 S
 }
/ W& n/ y$ j6 z& x% n. w, ] i++；
# r9 Q& \3 l+ z }, Q( s+ g3 o. ^8 o
 for(i=0;i<5;i++)
! R9 U' ?9 _, _4 i, i, e {. S0 G( U+ x2 ?7 w
printf("School %d:\n",i);4 c% [$ X! h! E+ n4 l" a G
printf("Total score of male:%d\n",score.malescore);
% Z/ j, ]5 A0 B! Z5 D5 \ printf("Total score of female:%d\n",score.femalescore);3 g3 K3 g) i4 p
printf("Total score of all:%d\n\n",score.totalscore);" ^4 q- k+ @+ p9 }- j! p( _
 }5 d4 J ?0 {8 c$ D* ?
}//summary ( `1 h( L, p: j1 t0 S' d
<>1.19 ' v$ \$ a, D& K' c u" B) M3 Q
<>Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint% s4 G8 O8 ~6 d
{+ M! Y$ j# B c' G1 i5 V
 last=1;
2 Y7 L/ x5 z* g! V: R for(i=1;i<=ARRSIZE;i++)( y/ P6 ?) f; I; l
 {- u( ?' F1 I: @( n8 |6 ^
 a[i-1]=last*2*i;6 z( H9 t& \7 ?9 {& ?5 T0 p% o
if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;
: n4 @8 T3 }- V: ~ last=a[i-1];" d2 r7 [: p5 s
return OK;- k/ L% y9 b/ ]* ?5 e; E
 }
4 J4 r- J" q. u$ e" K- p/ {}//algo119" ?& v. N0 S& S) g8 d8 c
分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. : ?, Z y4 X9 b0 K3 S7 f3 Q4 y |
<>1.20 
- O s$ H% H H% E2 V" m4 J5 S<>void polyvalue()( {2 R4 D$ q7 A' l' D2 a
{
1 R5 H* c% D# T& H. x+ I float ad;
- n2 r0 l, e: h1 i7 A- Z; U float *p=a;$ U; Z2 q! k. F8 }% T7 v
 printf("Input number of terms:");
/ Z, D5 M8 M8 ^ scanf("%d",&n);' |/ b; A! W( @* G) r! Z) }
 printf("Input the %d coefficients from a0 to a%d:\n",n,n);
% p. V9 S% V8 C/ S" O" e for(i=0;i<=n;i++) scanf("%f",p++);& e1 k- m1 n' W9 L9 w
 printf("Input value of x:");
2 M) _& b4 X d/ h, B8 |# I scanf("%f",&x);( y( M" e t' p
 p=a;xp=1;sum=0; //xp用于存放x的i次方2 g8 G$ {4 m! t: M0 S8 H+ K: Z J
 for(i=0;i<=n;i++)
- i) C& Z" p2 B& c {
, {* a' B- |3 W0 N- @* o& M sum+=xp*(*p++);7 Y2 d" T, A. I" P. _
xp*=x;& c0 b$ h o2 w! [1 z
 }- d' G/ n O/ K- n- R
 printf("Value is:%f",sum);7 {# X# G" z3 F, ^2 ^
}//polyvalue
6 a2 k; K' H! A* C; ^; |< >

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