查看: 4938|回复: 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;4 J& u3 N4 i& v. _; j, b& o* ~
temp[k-1]=1; //初始化( J4 a0 `, Z) U$ D+ ^. R6 ~4 Y
 for(i=k;i<=m;i++) //求出序列第k至第m个元素的值
' S4 e$ Q5 F5 J; W1 \ {
1 Q6 i7 X3 N, b sum=0;
$ ^% x0 m X6 T2 {! d4 s! L for(j=i-k;j<i;j++) sum+=temp[j];
; s& k L3 v# O) t" U" } temp=sum;
2 C+ w/ D5 T5 R }' h& z8 d# P2 @: H2 d* I
f=temp[m];! \* W4 a$ c- J2 V, W
 }0 j- _7 `- @! h/ \0 m
 return OK; r. t: e+ y e5 ~
}//fib
* o# n: {- K1 @; \分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m). 
& V, W" y. h* `: ?5 x# q<>1.18 $ |. K! J E$ h6 U
<>typedef struct{6 i( m, {' d- N
 char *sport;
/ z6 ^! M* U' J. q5 {: x; f* I/ Z4 Z enum{male,female} gender;9 e8 K# @+ c3 E* n6 P2 [. m4 S: }
 char schoolname; //校名为'A','B','C','D'或'E'* @# ]4 D8 z, ^) O6 E( N
 char *result;) |1 j& ^8 n: D7 s" }% [2 `
 int score;
& D, ~0 x; i) ~9 ^$ b9 C- B7 T) Y } resulttype; 7 [1 f5 j% Q4 Y
<>typedef struct{
" X8 Z) W/ G# I7 u/ @- I$ I. b int malescore;
, \; I1 w4 M' Q9 K1 R6 t5 ~5 I int femalescore;+ ~$ [! f( J4 t' o% V- @( z( t
 int totalscore;
7 k( \6 F4 P8 y/ @ Q0 U& L8 a } scoretype; + ?; F# `1 S* h* v1 A& W8 g
<>void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中; k; S$ H$ L3 E1 U
{, h% L) z' ~1 N; F
 scoretype score;2 j; R" N" B% X V
 i=0;$ [$ q8 ?2 w: b2 r' e
 while(result.sport!=NULL)
! g) J0 h ^1 Y( W, L {. p; B- a( ?8 j0 ^: g8 }" @8 ?
switch(result.schoolname)
& i6 I M! k" n6 i+ A3 P8 G {% v4 g) b' [/ ~9 `( |% p) }
 case 'A':" v9 M( A* x( p2 z
 score[ 0 ].totalscore+=result.score;+ g/ p; N8 |3 Z' K
 if(result.gender==0) score[ 0 ].malescore+=result.score;5 _: Q0 g8 H9 E. ]. _
 else score[ 0 ].femalescore+=result.score;1 {6 c7 N7 r2 ]' b+ K5 X1 |
 break;
 _5 v' d5 m$ E5 G* g% m6 S) ^2 [ case 'B':
7 V9 Y9 l2 f8 x, w score.totalscore+=result.score;
8 \" I& a/ r1 ?; ~/ a! S. A if(result.gender==0) score.malescore+=result.score;2 }4 q" e0 [' Z y) y7 M3 K- c6 X
 else score.femalescore+=result.score;7 m$ e: b$ P* Y& ?0 j( p
 break;
$ }+ h7 I3 c# H" L …… …… ……: S. X8 `1 ?" t- P. M8 ]5 L' P- O
 }
. y* L& M" v" N$ t i++；
- Z7 f" G: }! v$ L8 { }
: ^6 W: l1 N: S3 T4 g for(i=0;i<5;i++)
+ H" `; G& ?4 |- A {5 ~' U: m, S* v9 q) F0 t- w
printf("School %d:\n",i);
# |) S$ f8 D' _% L3 c4 R+ a/ n/ Y printf("Total score of male:%d\n",score.malescore);
9 ]* |+ y, h* t printf("Total score of female:%d\n",score.femalescore);
5 D3 g; I' j" W. | printf("Total score of all:%d\n\n",score.totalscore);
; i- O/ p0 w T3 h) g }& Q; u1 U: u+ @: t, ]" O+ N) d
}//summary + b: d g; c2 T: w: {
<>1.19 # D1 o, Y$ T* O- w: g U+ g ]% G8 ?/ z
<>Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint
) B# }% J4 G' R4 W! F{
, w7 m, I. U r# H last=1;1 P$ n, k O2 @8 U6 `
 for(i=1;i<=ARRSIZE;i++)
' A4 U* L0 R" l i. Z" }9 o2 | {; ?1 B3 s5 V- h! v. X7 s% K
 a[i-1]=last*2*i;
# `% i7 A" {) m: {9 m2 E if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;: U0 i. f7 [ e& E T3 I& l& Q+ M: B# X
last=a[i-1];
' G$ d7 A% w' x* h* G return OK;9 q1 e; j& J$ J" U S& H. g
 }
* n2 T: u2 K3 n}//algo119
. B4 O' p- n' _6 R分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. 
# p/ n0 {/ B" u+ M4 y<>1.20 
/ c s& X& M# V1 a! o3 {1 q9 V7 i* I<>void polyvalue()' X7 ^5 r2 z: z- m
{
# e. Z( B( P/ F$ U6 O7 j! {5 ? float ad;8 C$ y- m5 D0 J, e& Q, J" f' K+ V/ G
 float *p=a;
' s, l5 M( ]( f printf("Input number of terms:");. U1 Y* U- X) N: w: a& E6 U8 S0 n
 scanf("%d",&n);+ X. W: T$ ]5 w4 ]; L
 printf("Input the %d coefficients from a0 to a%d:\n",n,n);6 L1 H5 r# o5 b2 e/ k3 u6 z$ |( Z, y
 for(i=0;i<=n;i++) scanf("%f",p++);
' H9 F* J. M% j* X# s( R9 C* X printf("Input value of x:");4 ~1 G7 \! G8 N, e1 x5 H2 l
 scanf("%f",&x);
, l5 v% h3 S) ]: ~4 _. W8 N p=a;xp=1;sum=0; //xp用于存放x的i次方/ e) V1 r$ m5 d
 for(i=0;i<=n;i++)) L& F4 L( m- ] _# @
 {
' ]3 F2 Q$ [0 ? sum+=xp*(*p++);
. X, T3 a& J( [9 d& U xp*=x;; X: j* Y: f) N$ w; w; f7 s+ `3 [9 f
 }
" c+ c; \% Z5 J+ m4 c printf("Value is:%f",sum);% t0 M& m; V5 b* L8 s. i7 m
}//polyvalue
4 [ r; z8 Z' F< >

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