查看: 4986|回复: 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;* z7 C9 [$ D1 c* t4 u) ~' {, G
temp[k-1]=1; //初始化% L( ?- X H7 B$ _
 for(i=k;i<=m;i++) //求出序列第k至第m个元素的值9 q2 z5 a. V6 v9 X7 I' Y8 A4 M
 {
5 m; e5 l7 D6 K$ c' S" ?8 g# c sum=0;: y' `3 m) R# U/ W( l9 v& Y' Y
 for(j=i-k;j<i;j++) sum+=temp[j];* ]2 i8 j1 n" d. ]0 |# u0 L0 y
 temp=sum;
" W5 e, a7 g1 l( b: o }
1 V3 l! b3 x0 J% p, |& [ f=temp[m];7 e' T3 g6 d! ^* x
 }
! Y5 @# O1 Q: z% K7 |8 ^/ A return OK;
, N( g7 s, @* w( l, L9 e}//fib. `/ G7 |- a" E1 u+ j
分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m). 
* K1 X* v( H* T( f" t<>1.18 / `* T9 V# F. y' I
<>typedef struct{7 S% c9 x0 a' k+ r- h& I
 char *sport;
, j: _+ V- j* K: x$ o$ ~6 O$ U2 m enum{male,female} gender;
5 M/ g' C _6 o7 ]" t3 \ char schoolname; //校名为'A','B','C','D'或'E'2 i% c/ x9 J' R$ t( g4 j. ?. q
 char *result;; ]. c- N% t/ n3 l. _
 int score;6 q! [& B' i) Y
 } resulttype; % K6 O9 u7 V6 `) `, T! d
<>typedef struct{
5 @ M, E8 J* M3 z int malescore;' I, I* c( F8 a4 M. H |. N- T6 [
 int femalescore;
7 e7 E% ^2 ?9 x+ n: m" O1 r* p: N int totalscore;
4 \/ p0 U9 f# Q8 P& `) O; W4 x/ I } scoretype; 
+ x) C8 W) U6 f# P+ q<>void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中
4 Q3 b- v/ P4 A5 O{
9 c% J" @3 }) `6 e scoretype score;
2 P' N$ O1 |, k" M0 w; Q6 } i=0;* x8 l3 l0 Z3 K0 @' P& J* W- m
 while(result.sport!=NULL)' g; E! w# m- U; N$ Z
 {" p% e& S. l& y) b1 M5 [
switch(result.schoolname)
5 z5 j- i c9 r3 f" z' L. X9 d {# g: j |7 {2 I6 V8 i% @$ D" U# N+ j6 B
 case 'A':9 `" t: }. i" [+ i& L: R
 score[ 0 ].totalscore+=result.score;# {! F# T9 l3 m* ?
 if(result.gender==0) score[ 0 ].malescore+=result.score;2 a0 |, @* h* Q" L" W( C, W! t
 else score[ 0 ].femalescore+=result.score;
0 K- I$ j6 R2 M1 |5 r break;
, _+ h4 f+ ]4 k: p+ U case 'B':) p: | B( i0 w% p1 J
 score.totalscore+=result.score;0 @0 Q/ }) l4 |4 X! z
 if(result.gender==0) score.malescore+=result.score;4 C7 [3 `9 ?/ [) ]) R q7 l
 else score.femalescore+=result.score;; t7 v# D$ U. j4 j4 ~" R+ W
 break;6 K9 Q9 f/ ^+ o( c
 …… …… ……+ B$ d) ?9 j' [5 q- S" a! D
 }
2 R: b p+ {1 a- h' M i++；9 I( D- ]0 `+ n! R c0 c% W7 M
 }# u* M4 T9 s; j4 @
 for(i=0;i<5;i++)
- v. Y" o) V4 @/ z {
 Z2 K; }% J# x4 t! P3 z( R+ G printf("School %d:\n",i);0 ?1 a) O; b4 n+ W
printf("Total score of male:%d\n",score.malescore);
. d" @/ s. w6 s printf("Total score of female:%d\n",score.femalescore);
8 b: z7 \4 J7 |9 r% V9 t1 A- M printf("Total score of all:%d\n\n",score.totalscore);
* e9 a7 ?8 H# o! [& Y+ s$ N }( O7 ~! s* v* w, \" x' a
}//summary 
" e/ m6 {( X. Q. i( s<>1.19 
& \% m3 x" F, M# c9 P5 @& K<>Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint" ?8 R& s# F2 l" V p" ^( v8 H
{2 N' u" v0 j* i- L
 last=1;
$ L" r* X, [# v D5 e for(i=1;i<=ARRSIZE;i++)& h4 Z; l# H+ {
 {+ |" q8 S: T' ~: s" L
 a[i-1]=last*2*i;
1 |1 u$ I2 o! t3 u, @1 g ?9 U$ | if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;
& v3 o3 n' P; |; ] last=a[i-1];
 n) O/ u5 w2 K" X& v" e0 S return OK;
: _- ?$ [# a/ N$ U }( r+ [- X2 v7 R$ i
}//algo119
6 h9 ]0 }2 w& a# t, H5 k- w, k分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. ; X- f+ y9 e& P$ h1 f, `2 b& a
<>1.20 : x) s) }* x/ \: K, H
<>void polyvalue()
0 r! z. l" _3 m! j{: g$ G6 \4 u5 T2 b
 float ad;) F7 F' M s: ]% ? h+ l" F" n T9 O" [' V
 float *p=a;9 }( r3 j. q$ J; d* y' g
 printf("Input number of terms:");% _, y- l- j* p# T. x1 k
 scanf("%d",&n);$ P: D0 ^. |6 I
 printf("Input the %d coefficients from a0 to a%d:\n",n,n);. \- @8 I+ T' c4 m
 for(i=0;i<=n;i++) scanf("%f",p++);
$ [3 J) A3 a3 N, y$ m5 P% ~- ^! @ printf("Input value of x:");& S+ E2 f) D5 d/ }3 Z' w
 scanf("%f",&x);
8 s7 g# }' N" c" n& ?' M: A% D* \/ | p=a;xp=1;sum=0; //xp用于存放x的i次方
/ K8 p/ N) \! Q; S( d7 }, K for(i=0;i<=n;i++)7 k! y* s4 U- G
 {
8 ^% O6 C+ h( m; B sum+=xp*(*p++);
* q, U+ `1 S6 I7 W& _0 J: r1 Z xp*=x;4 I) ~: p4 m* v0 g2 h$ {" ?
 }
) _& ~- i7 \5 L% e printf("Value is:%f",sum);( e0 R- U" l" a9 N
}//polyvalue
. u6 p0 J {4 T- a: f' D; A< >

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