查看: 4987|回复: 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;
' ^. R2 |/ a) p6 t: \" S, U temp[k-1]=1; //初始化* Y" v$ o% ]$ M" p& q
 for(i=k;i<=m;i++) //求出序列第k至第m个元素的值
) D" ]2 A. Y+ `0 H8 l; |& r {& G. ]. ] h, K0 r+ G
 sum=0;& i; B. w$ I: K' W6 @/ s* t- d/ z
 for(j=i-k;j<i;j++) sum+=temp[j];/ T9 S0 ?0 z4 s" B5 d
 temp=sum;
$ _, G' i. K5 A/ ]+ S% X }, a h# j9 v) h' U
f=temp[m];6 c7 ]$ R4 A+ Z% Z y
 }
( T: [- [* ~' k, x7 d/ _ return OK;. w7 x9 H6 d1 U9 @$ a8 _8 [5 t
}//fib; N) B* O3 O/ Q# g; W
分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m). 
. n3 j+ b N; o; t8 i7 u1 ^' q<>1.18 1 t6 G. R" A& L0 j% l6 ]2 }2 d
<>typedef struct{
- n1 b( _" f& z' D x2 y char *sport;
- A: P+ M8 J& f" o2 J- }4 @) o enum{male,female} gender;0 j3 U; X% l$ T
 char schoolname; //校名为'A','B','C','D'或'E'3 X# J* T+ M( G4 e
 char *result; d5 K( j2 p8 `$ f" X0 D/ m
 int score;& P5 o7 _/ ^8 q. F
 } resulttype; 8 d8 ~, W# Q+ B
<>typedef struct{- Y/ x4 {$ J# o; N& [; A6 `
 int malescore;4 s! B/ z) R; J9 l2 Q
 int femalescore;* }: Q3 Y I! F. }0 P0 b. u$ c
 int totalscore;3 L, T; b8 x1 z! k* o# H
 } scoretype; ) ~7 d8 l g9 _% l% L8 @, i
<>void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中
; g7 b' f6 v' ?. {+ h% e* L3 B: Z$ G{
4 V/ C/ A; e* { scoretype score;
( I, H$ T1 p4 F1 e: T2 C i=0;
' X X+ M. K; ~) r while(result.sport!=NULL)
5 k6 I# @( L! P& [3 a! y {
4 r7 E( X& R5 v [1 H: F switch(result.schoolname)
0 H r- c- g; ~% J8 B( W {
& b1 f) d: s0 l3 f. b" E9 \4 G, a case 'A':/ x. P& h# _3 R- R6 X" T
 score[ 0 ].totalscore+=result.score;
2 u7 G: \% L4 h" A( z if(result.gender==0) score[ 0 ].malescore+=result.score;
 R4 o. \: S' v1 n* x7 b! V else score[ 0 ].femalescore+=result.score;* R- _9 j9 e6 m/ p
 break;6 h8 u4 h% M& H% b. A
 case 'B':
( s. w$ z7 {5 x score.totalscore+=result.score;+ F& r- D, R7 N' q* C/ }% i, i8 C
 if(result.gender==0) score.malescore+=result.score;
* e0 F" G; x) E+ P% a else score.femalescore+=result.score;- l5 v) C" `5 {& o' G0 u
 break;. T( I! ^# S- F$ p Y9 {! K. P
 …… …… ……
1 G7 T, ~- z% j4 v3 g }
% Q' j4 S5 U- ~6 @ i3 c i++；
1 f' ~: p% t* `3 j9 d# Y C }! a, Q' P G2 }; J; F
 for(i=0;i<5;i++)7 V7 P$ R' z( Q1 L" ? {; M' H
 {
7 u/ V7 y( m0 n( F( M printf("School %d:\n",i);$ x+ S, R% h5 I0 U5 E# h
printf("Total score of male:%d\n",score.malescore);) O# b& m" O' q/ N+ W( Q
printf("Total score of female:%d\n",score.femalescore);" i$ Z) y7 [, M$ ?+ v& b
printf("Total score of all:%d\n\n",score.totalscore);
, a. j- Z) }# H, K }3 k/ u( w0 t9 D0 ~! G
}//summary % d- W7 Z$ ?8 J) V% D+ b. H
<>1.19 
) w) `: j1 g1 o/ Y1 W$ b O% w3 W<>Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint
& n6 Q' |! a: }% w1 t; G{
3 v6 \- W# z. K& {7 L8 ~ last=1;
( z& Z8 I) ^. J" H# G1 _ for(i=1;i<=ARRSIZE;i++)9 u) j* S; `/ z
 {" N/ H* w3 y. W8 }9 d! D+ W
 a[i-1]=last*2*i;
1 h) Z- |7 M0 s3 g, N if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;( c/ ]( k8 l" d9 i
last=a[i-1];
& R1 Z- ~% F+ e3 T return OK;
( t2 U! P7 t) `- u# X- t }
: P- J ^" `6 ^}//algo119
! V. y( l7 [) D6 \$ N分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. 7 c2 U9 l5 _$ {& y z
<>1.20 
0 }6 B" G" D/ g' q+ i. A& \<>void polyvalue()
$ X( [( r' S) ~% r! E4 x4 l# s{
2 O' O- h7 f3 }% F7 l2 r% g3 } float ad;
" m% ]; ^* p) s8 R/ y float *p=a;
0 R! ^2 n& G* Q& d; \: Q1 V/ a# t printf("Input number of terms:");& ~; I1 A7 A4 V. q7 K
 scanf("%d",&n);( @( ^& q% p) {) ~" l% Z6 E$ C
 printf("Input the %d coefficients from a0 to a%d:\n",n,n);
! P4 l( y2 w$ {- |/ j, g for(i=0;i<=n;i++) scanf("%f",p++);
& b! }3 L+ I# A6 _ printf("Input value of x:");
3 R' K; d% q0 |9 q! Q5 M scanf("%f",&x);2 T6 _ q/ v" w2 V& ~' r! `8 o
 p=a;xp=1;sum=0; //xp用于存放x的i次方
& ?' d/ Z8 p9 f3 L7 P8 q$ N6 p' T for(i=0;i<=n;i++)
, x! }2 P- F) W6 T9 R {/ b) D; e8 J8 P
sum+=xp*(*p++);- z$ F* P7 ]+ f0 K4 \ p: ^+ k" V
xp*=x;2 s& z2 P _8 y) Z5 c# X
 } `) _( f! T6 r9 e1 |; ]1 |% O, B
 printf("Value is:%f",sum);$ W/ _. c& @6 a7 i8 g
}//polyvalue
( h" h7 g) O5 U# b4 n< >

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