查看: 4975|回复: 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;" b5 e2 _9 \5 o2 r0 S" v' {( B" Y
temp[k-1]=1; //初始化
0 y' }! J- D5 f$ {' E& n for(i=k;i<=m;i++) //求出序列第k至第m个元素的值8 g+ U, T# L0 H* D/ j9 d/ }
 {7 J2 L4 U' [! `# L" f- b
 sum=0;$ ^# Q, ]/ W5 h6 n) @% C9 B
 for(j=i-k;j<i;j++) sum+=temp[j];
! `3 ]% e5 j, ] temp=sum;4 u, e; y9 ]& s" P# K
}+ [- {0 p, O' u9 u u' U
f=temp[m]; J9 r8 y2 _# e5 @% F
 }
' V0 O) I: K4 T% j% x return OK;( }) q7 }! l+ j) @2 X- e d
}//fib
" V0 ?0 h9 I* h# p分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m). 
7 V$ ?/ j, x! ?+ j& K<>1.18 , D U4 a2 G6 K9 c% L( W C
<>typedef struct{
3 D. k' w# ]% y: o0 W char *sport;
& O: e1 t: ^- T! s4 V5 h6 f. P* Q, x0 J enum{male,female} gender;1 N/ t# e. ^. A5 @ ?
 char schoolname; //校名为'A','B','C','D'或'E'# G; ]' b, I ~4 t c) N$ M
 char *result;
! X5 M7 ]+ h8 ^0 q int score;5 I4 k) _' |: Z( x
 } resulttype; 
$ r0 G" e5 ~% f/ f/ f<>typedef struct{( {( {3 P+ s2 U* f# u3 f+ Z
 int malescore;2 y" R7 ^, ]2 n6 Z
 int femalescore;
% s$ b) l1 h# ]$ r; `8 x int totalscore;
7 `2 t% N2 t* a: e3 h } scoretype; 
1 F! u+ j+ |5 f- q5 r<>void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中4 U6 E/ m) [: [1 L! A6 `" |
{
0 q" f3 y' k7 G. q! W3 R3 ` scoretype score;
) H& x7 B: D! B# i! N i=0;* U: ^' ?" \& l) u
 while(result.sport!=NULL)
$ T. `* ?: L* e* L S3 L5 j {
! A5 k; g( m7 ]# b6 M$ l switch(result.schoolname)
1 J8 x" ^- u$ K, `6 q. |( n {
: F+ o4 m0 a0 q. k case 'A':1 a5 f( i- ?+ p* r$ s9 K; P
 score[ 0 ].totalscore+=result.score;) B& S" i: `6 p9 ^1 m8 h
 if(result.gender==0) score[ 0 ].malescore+=result.score;. u) Y4 U$ H" j! Q, j0 N
 else score[ 0 ].femalescore+=result.score;0 M! ]" }! N: h5 G; W
 break;
7 S$ O/ Q/ V1 x+ p case 'B':) Y$ `( P* n8 q
 score.totalscore+=result.score;
! p) ?/ |1 X0 y: |% q if(result.gender==0) score.malescore+=result.score;4 ?! C" |! H) w
 else score.femalescore+=result.score;
' m' s5 H4 m- J. }4 v break;! A+ Z: r, K: `, a9 j Y
 …… …… ……
 L. r9 I* t, _0 H }
- k2 l) T' F8 J, s7 d i++；% h" M2 x: |8 x- t& V; e
 }0 F/ v# j/ g# b/ B. r' Y
 for(i=0;i<5;i++)
5 ?- \+ D, o9 ~( R% B/ C8 h {
 c' C ~1 J7 x, l2 u/ x z, C printf("School %d:\n",i); V$ K# }* @8 h6 R X8 Q
printf("Total score of male:%d\n",score.malescore);
3 s2 E$ y) f2 \( A6 O- U printf("Total score of female:%d\n",score.femalescore);/ Z4 R- H6 @7 ]8 _
printf("Total score of all:%d\n\n",score.totalscore);4 o7 z! u' W2 @: `# {1 B1 B. t
 }
' t2 R- @, A( v. t}//summary : n" v" S' n2 N& v7 W; ?- A3 r
<>1.19 $ I* ~5 ~! T/ t
<>Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint
. t2 t% e* r2 G1 T{# n* P! u* [: h: I6 P
 last=1;
. z! G7 ~7 `( c3 ~, C' q for(i=1;i<=ARRSIZE;i++)
2 ]' s' |6 v* @, W5 i {
& I+ @9 l Q9 D' e$ a6 u ?& \ a[i-1]=last*2*i;% r1 F) D) v' S5 A7 `9 D8 i# G& t
if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;
3 d3 ^. u* j$ E; ]% R last=a[i-1];
5 R0 n" C) _: B- ~# z) J( ~; m return OK;
/ i; @& x8 B& q+ i! d0 U2 O4 u }$ F6 R3 f# y. W l7 a8 J5 N( @% i, u
}//algo119
/ o% `0 e! D O0 ?. X分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. " r7 z) `2 E3 r( N
<>1.20 
4 m/ L, I6 l& t* A6 |2 V: J' a<>void polyvalue()
2 b/ ^* ]4 z. d{
# ]6 c, T: w1 E5 G8 p float ad;! H% K* {$ k; i2 ?" z0 p
 float *p=a;
) k5 f U; F b3 J |9 J6 N9 ] printf("Input number of terms:");' e g0 X) _- k0 d
 scanf("%d",&n);4 S, H% z+ R% ?) Y9 J6 Q: P# F) V/ l
 printf("Input the %d coefficients from a0 to a%d:\n",n,n);
4 G! n% `0 C9 z. o5 e1 Z for(i=0;i<=n;i++) scanf("%f",p++);
) h2 o5 Y) }8 j1 `- _0 d; f% b printf("Input value of x:");
+ ? C8 W3 W5 ^* ^! O scanf("%f",&x);
! p9 J* W1 l9 u# Q- S: I p=a;xp=1;sum=0; //xp用于存放x的i次方( p* T7 E3 S& @3 Y5 a, Y9 d. A
 for(i=0;i<=n;i++)
# g. Z2 g& w; U1 S$ r5 k. T" j6 ?9 E {
# k0 I+ \3 a+ ? sum+=xp*(*p++);: e% v2 |7 P4 D0 s. o
xp*=x;
3 ~0 e1 Z7 H3 u7 r9 W }
* P- \3 \) E3 N1 W ^* x printf("Value is:%f",sum);. ~. V# P9 c2 B0 D3 L( M
}//polyvalue
# J2 s Z3 S9 |< >

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