查看: 5001|回复: 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;9 }9 J2 Q5 j) `' \- C
temp[k-1]=1; //初始化7 a, W) _, {4 x- n
 for(i=k;i<=m;i++) //求出序列第k至第m个元素的值
9 D) H* e, I$ u( M {
2 i) K6 B. L! C3 s0 x2 C# V sum=0;
. T: }' \& C' y1 I* l% ?% @ for(j=i-k;j<i;j++) sum+=temp[j];" A, z% Y% l% Q7 K4 g2 O
 temp=sum;
: d4 \; r( N/ d G+ `# v3 S% f }3 @/ @6 e0 B) f" s- `# c
f=temp[m];
& K6 e3 a0 h H2 M5 i; J }% o/ L O5 R+ ?3 `4 c3 C+ r7 N/ J
 return OK;; P6 H8 f' D, X4 H0 k7 D
}//fib+ ]3 o }: K, I$ F
分析:通过保存已经计算出来的结果,此方法的时间复杂度仅为O(m^2).如果采用递归编程(大多数人都会首先想到递归方法),则时间复杂度将高达O(k^m). 
# g7 E. D. i: Z<>1.18 4 l& `+ f/ J$ D2 v( ^: q# l' V
<>typedef struct{
8 Q1 h1 }0 ^5 G( K2 r6 u char *sport;
( r4 s+ E4 f1 } enum{male,female} gender;
" v# e- |0 m4 _/ K5 E, M char schoolname; //校名为'A','B','C','D'或'E'
0 Y- z+ D9 V& ]2 p; L( p4 `2 F char *result;
! x5 l6 n$ W k& `# g7 R int score;
9 v6 x% N; b& e9 _- }, @- E/ A } resulttype; * \% t% J% H3 a# o6 P+ `
<>typedef struct{+ ]: u$ U, y+ [& _6 Q9 }/ Z" U
 int malescore;/ h2 Q Q: p" |
 int femalescore;. m% a; _$ X8 Z
 int totalscore;; `% h$ f! U W8 e: Q7 `# v9 D6 j
 } scoretype; ) ~2 T! D9 E1 W# R* U, G9 q
<>void summary(resulttype result[ ])//求各校的男女总分和团体总分,假设结果已经储存在result[ ]数组中
& _- Z) R8 }/ O{
- v! ^& L! u2 Y. S scoretype score;1 }8 b3 t( h* }
 i=0;
6 s/ z: ]- d3 L$ H, r8 J6 D' h$ _ while(result.sport!=NULL)
4 `* }1 d) b5 y$ F {
9 N. T' O, k# {! `- [9 r, _4 F switch(result.schoolname)( d9 |) v p, I% z
{2 I# [3 \+ T8 b3 X: E* `: D
 case 'A':
& H5 ~6 q5 G5 H% u& l6 j score[ 0 ].totalscore+=result.score;+ m( i- V& b( z$ Z
 if(result.gender==0) score[ 0 ].malescore+=result.score;) \" I- S4 R8 Y7 r
 else score[ 0 ].femalescore+=result.score;
% Q; h" n1 A& C' r1 \ break;
1 a- D$ B: A* g2 A case 'B':
3 n; W" U6 W7 ~9 ]3 z9 x score.totalscore+=result.score;" Z$ Z$ }4 j& U) _$ m2 x3 }
 if(result.gender==0) score.malescore+=result.score;+ c' B4 ^6 {7 v M+ t; F
 else score.femalescore+=result.score;- m8 C) E4 R A( ~
 break;0 u# x* n+ J) p7 I# S
 …… …… ……
+ ^6 W0 g3 F, p1 S1 f8 U+ ~) S }" q4 S; x% L+ Y/ \5 o9 [' g0 E
i++；5 Y. W; j; B& a8 p7 S$ \, r
 }
* ^) r( x$ t1 M& |% ]3 N for(i=0;i<5;i++)' c+ v$ [9 c& |0 g+ D
 {9 U ^; x" _' F o+ [5 b: o% L
printf("School %d:\n",i);( l) I% h+ B: |9 h, B* T9 d/ d+ `' _
printf("Total score of male:%d\n",score.malescore);- u5 E0 \: h3 I0 h9 C
printf("Total score of female:%d\n",score.femalescore);
' W# S: ?+ m2 u+ D1 m6 w printf("Total score of all:%d\n\n",score.totalscore);: m9 X5 h& a0 F
 }
; x+ c6 c- m6 t# N5 D6 H& u8 K}//summary ! t' P/ [( p" ?# F
<>1.19 % s2 u' A: z2 j$ g4 K) H& }% L
<>Status algo119(int a[ARRSIZE])//求i!*2^i序列的值且不超过maxint5 S7 |1 g2 @2 |8 ^" d8 p
{
8 W! O8 x0 Z& @0 D+ e B last=1;& S: x) x/ C3 B0 U/ ]# \0 Y( C
 for(i=1;i<=ARRSIZE;i++)/ J& y$ R, P) o
 {" u$ H3 @% C2 [7 U5 r* r6 G9 M
 a[i-1]=last*2*i;
1 l% C' y0 e8 s1 J5 o+ f+ o. N if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;
! A% S" [) V0 y- ?& M last=a[i-1];
 z( L9 Y2 Z1 K Z7 s- Y+ e; f return OK;
" f0 q" Z/ Y7 _8 ]! W1 i }
; r/ v7 X# r) \+ n2 ]5 ~}//algo1198 y7 w: e+ N9 `" D
分析:当某一项的结果超过了maxint时,它除以前面一项的商会发生异常. . B) h- r8 W* D0 L) o- O
<>1.20 c6 t% c* U1 }/ d. g
<>void polyvalue()
; {4 y+ |, F. L. }* _{
. M8 l4 K6 L' U7 a3 ^ float ad;
4 L* \' B/ |$ |. ` float *p=a;
* w/ P) R3 {+ _: d& {& I printf("Input number of terms:");
, G* Z5 ?% W7 U. s' { scanf("%d",&n);* H( J" C- R7 E8 t( a
 printf("Input the %d coefficients from a0 to a%d:\n",n,n);( r0 v. F9 Y2 j1 n
 for(i=0;i<=n;i++) scanf("%f",p++);
. v, K2 Y# R, m1 ]2 z printf("Input value of x:");( R! R/ {' e4 D5 G) Q! m7 x
 scanf("%f",&x);9 p, u( F% F& C3 Q( h
 p=a;xp=1;sum=0; //xp用于存放x的i次方
8 {- j7 I" Q: l( W for(i=0;i<=n;i++)
1 u: V/ U& l; ~( L2 J8 Y {/ g x6 l8 ]8 T! v9 `8 E( t
sum+=xp*(*p++);
9 r' k( V0 `9 B* h xp*=x;& h- J: Q# n" _
 }$ x7 w6 V" ?3 a# j, u
 printf("Value is:%f",sum);' ^8 C1 z5 R" M5 o8 x
}//polyvalue4 K5 }+ V) T8 u$ f+ e4 I
< >

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