QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 4937|回复: 3
打印 上一主题 下一主题

《数据结构(c语言版)习题集》算法设计解决方案

[复制链接]
字体大小: 正常 放大

66

主题

1

听众

648

积分

VisaSky.com 加拿大移民留学网

  • TA的每日心情
    开心
    2012-6-9 03:29
  • 签到天数: 1 天

    [LV.1]初来乍到

    发帖功臣 元老勋章

    跳转到指定楼层
    1#
    发表于 2004-11-28 18:02 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta
    < >说明: <p></p></P>+ M! E8 O* O' o9 ~7 f& {2 y
    <><FONT size=3>1. <FONT face=宋体>本文是对严蔚敏《数据结构</FONT>(c<FONT face=宋体>语言版</FONT>)<FONT face=宋体>习题集》一书中所有算法设计题目的解决方案<p></p></FONT></FONT></P>, I3 `3 Z- o0 j% [$ [1 y
    <><FONT size=3>2. <FONT face=宋体>本解答中的所有算法均采用类</FONT>c<FONT face=宋体>语言描述</FONT>,<FONT face=宋体>设计原则为面向交流、面向阅读</FONT>,<FONT face=宋体>作者不保证程序能够上机正常运行</FONT>(<FONT face=宋体>这种保证实际上也没有任何意义</FONT>);<p></p></FONT></P>
    1 F4 U5 o6 {1 ~<><FONT size=3>3. <FONT face=宋体>本解答原则上只给出源代码以及必要的注释</FONT>,<FONT face=宋体>对于一些难度较高或思路特殊的题目将给出简要的分析说明</FONT>,<FONT face=宋体>对于作者无法解决的题目将给出必要的讨论</FONT>.<FONT face=宋体>目前尚未解决的题目有</FONT>: 5.20, 10.40;<p></p></FONT></P>
    # E  y/ D( g2 v9 ~; ^<><FONT size=3>4. <FONT face=宋体>请读者在自己已经解决了某个题目或进行了充分的思考之后</FONT>,<FONT face=宋体>再参考本解答</FONT>,<FONT face=宋体>以保证复习效果</FONT>;<p></p></FONT></P>0 h! d; Z: K+ w5 O0 d1 i3 u; v1 w
    <><FONT size=3>5. <FONT face=宋体>由于作者水平所限</FONT>,<FONT face=宋体>本解答中一定存在不少这样或者那样的错误和不足</FONT>,<FONT face=宋体>希望读者们在阅读中多动脑、勤思考</FONT>,<FONT face=宋体>争取发现和纠正这些错误</FONT>,<FONT face=宋体>写出更好的算法来</FONT>.<p></p></FONT></P>6 P: L7 `& X2 V7 b
    < ><FONT face=宋体>第一章</FONT> <FONT face=宋体>绪论</FONT> <p></p></P># N% p( y& \2 q; L
    <><FONT size=3>1.16 <p></p></FONT></P>" F# R$ x3 |) O9 E" f
    <><FONT size=3>void print_descending(int x,int y,int z)//<FONT face=宋体>按从大到小顺序输出三个数</FONT></FONT>
    . G+ ~. M9 E/ p$ x( y<FONT size=3>{% F+ T3 J; [% u8 {4 ]1 i2 e9 l
      scanf("%d,%d,%d",&amp;x,&amp;y,&amp;z);
    * s' d. g0 D' G  {4 f% P  if(x&lt;y) x&lt;-&gt;y; //&lt;-&gt;</FONT><FONT size=3><FONT face=宋体>为表示交换的双目运算符</FONT>,<FONT face=宋体>以下同</FONT></FONT>. J0 d# C) o& s6 W. \! `3 e1 B" C* p0 Q# L
    <FONT size=3>  if(y&lt;z) y&lt;-&gt;z;: w0 W& y: a! y3 z$ ]( J( N* V9 W
      if(x&lt;y) x&lt;-&gt;y; //</FONT><FONT face=宋体 size=3>冒泡排序</FONT>5 @, z* u' v  H* _! O
    <FONT size=3>  printf("%d %d %d",x,y,z);+ M. s( ~2 W5 c/ B
    }//print_descending <p></p></FONT></P>
    / w. |5 c/ \' E$ }9 ?! W6 v<><FONT size=3>1.17 <p></p></FONT></P>
    , `5 s) x  _+ u9 Q" S: {8 P<><FONT size=3>Status fib(int k,int m,int &amp;f)//<FONT face=宋体>求</FONT>k<FONT face=宋体>阶斐波那契序列的第</FONT>m<FONT face=宋体>项的值</FONT></FONT><FONT size=3>f# Z6 n3 \5 B' d3 N" j
    {
    ) M2 a( ]$ ?" \& H) X  int tempd;
    8 G- ^3 s7 V" p6 h  if(k&lt;2||m&lt;0) return ERROR;2 t2 G3 H) ^  x, B& _( ?
      if(m&lt;k-1) f=0;
    " ^% q3 W* Y2 j0 J8 N0 u- f& ]5 q  else if (m==k-1) f=1;$ ^5 i. G! h- F& X+ s# @
      else7 i- O4 |  \* C& }5 j
      {  f- `" W& ]* N% y
        for(i=0;i&lt;=k-2;i++) temp=0;' p$ ^& S3 Y) v0 V
        temp[k-1]=1; //<FONT face=宋体>初始化</FONT></FONT>5 U2 ], \- N6 c- m
    <FONT size=3>    for(i=k;i&lt;=m;i++) //</FONT><FONT size=3><FONT face=宋体>求出序列第</FONT>k<FONT face=宋体>至第</FONT>m<FONT face=宋体>个元素的值</FONT></FONT>2 F8 _& |2 O! t$ H! o
    <FONT size=3>    {# t" i+ o% W! }! |2 z: N# s6 \( _
          sum=0;
    , d, @& m& F9 ]      for(j=i-k;j&lt;i;j++) sum+=temp[j];
    - N. k6 D  @5 o0 V) I3 [      temp=sum;: b& u0 G: C+ k3 P
        }7 x7 A. O3 ?4 Y3 x. h
        f=temp[m];
    0 G0 ^  r$ D# O: p# Z  }4 \2 ?6 r5 m, M* K  i
      return OK;
    5 `6 I! ?% g4 k; f}//fib/ J0 |" G7 s' u+ H
    </FONT><FONT size=3><FONT face=宋体>分析</FONT>:<FONT face=宋体>通过保存已经计算出来的结果</FONT>,<FONT face=宋体>此方法的时间复杂度仅为</FONT>O(m^2).<FONT face=宋体>如果采用递归编程</FONT>(<FONT face=宋体>大多数人都会首先想到递归方法</FONT>),<FONT face=宋体>则时间复杂度将高达</FONT>O(k^m). <p></p></FONT></P>
    ! h& J7 ]# w* J  Y$ O. O5 @<><FONT size=3>1.18 <p></p></FONT></P>! q: A5 P  b6 X! p
    <><FONT size=3>typedef struct{
    , x9 Q) x1 k/ o8 A4 g: y5 N+ A                    char *sport;
    / |$ M/ [! {" o: ?8 z$ W                    enum{male,female} gender;
    3 L3 O, g1 Q' q5 Y) H# K                    char schoolname; //<FONT face=宋体>校名为</FONT>'A','B','C','D'<FONT face=宋体>或</FONT></FONT><FONT size=3>'E'
    # ?# B6 L( X. I; [; b                    char *result;
    " h. o: V- l2 _' @0 s0 d! V2 b1 M/ Z                    int score;
    % O; ^8 t% T; {& }! L& @* s. r' W                  } resulttype; <p></p></FONT></P>
    $ A# U' M9 U  u/ Q( g6 S: X<><FONT size=3>typedef struct{" O) D& E3 \4 |- f$ ]0 X
                        int malescore;
    4 o# e- h5 K2 w: V- f$ s                    int femalescore;8 {1 \' M$ U" W- U6 |5 c
                        int totalscore;7 w2 I: S* w2 \7 \3 w
                      } scoretype; <p></p></FONT></P>
    , c3 Y6 X8 i4 E0 R<><FONT size=3>void summary(resulttype result[ ])//<FONT face=宋体>求各校的男女总分和团体总分</FONT>,<FONT face=宋体>假设结果已经储存在</FONT>result[ ]<FONT face=宋体>数组中</FONT></FONT>" w1 w) v) t) T& R# j9 f
    <FONT size=3>{
    ) Q7 U, _3 {  f0 b9 G, a! N  scoretype score;9 ]4 E! r: Z8 X" i, R2 g+ H
      i=0;: f! r) n& W; w# F; M9 A
      while(result.sport!=NULL)5 [' V9 a# _; B$ U
      {
    & o1 }0 w" T4 `9 O1 L, ]/ ~    switch(result.schoolname)
    % w; E) B" P9 n# h' X  O8 v* S2 V    {% e, l3 V5 }0 M- Z
          case 'A':
    7 \' X6 D1 K! G3 t/ |8 v/ v& n        score[ 0 ].totalscore+=result.score;1 z: x- O- _, }; a1 _
            if(result.gender==0) score[ 0 ].malescore+=result.score;! K1 l2 L; M$ m+ a! }' \# A
            else score[ 0 ].femalescore+=result.score;
    ' O5 \) {" Y6 m. }; M        break;* ]! c$ c: B  t, l$ T) D* b& x5 J
          case 'B':
    * q6 I# g! P. h% H6 g# A        score.totalscore+=result.score;8 a1 [, g4 B5 F. c& p6 X1 k, h
            if(result.gender==0) score.malescore+=result.score;
    % g) J; y' [' l; g5 O7 X        else score.femalescore+=result.score;
    7 y4 A0 h1 k' [2 G        break;
    6 Y& J1 T* a) V. U! {  L      </FONT><FONT size=3><FONT face=宋体>……</FONT>    <FONT face=宋体>……</FONT>    <FONT face=宋体>……</FONT></FONT>/ q  a3 c9 W! M; M
    <FONT size=3>    }
    8 P: m- X1 f* v4 ^    i++</FONT><FONT face=宋体 size=3>;</FONT>
      Z$ V' t! t! [( f<FONT size=3>  }0 @4 x: l1 o3 [# r% s9 m( s2 t
      for(i=0;i&lt;5;i++). @' x: e5 t( x
      {
    5 P9 N$ [1 R: e    printf("School %d:\n",i);( M6 }0 M' p2 k6 o' D" c
        printf("Total score of male:%d\n",score.malescore);
    / \9 C7 \+ b9 J* t% S    printf("Total score of female:%d\n",score.femalescore);
    ' c. ]' s* Q; ^$ \    printf("Total score of all:%d\n\n",score.totalscore);
    7 s# ^' }1 Z6 e$ e$ f8 y. B4 `  }8 x& x- e2 [4 r. M
    }//summary <p></p></FONT></P>
    % I, l+ O- I% y- {9 }! v: K6 J' u% a<><FONT size=3>1.19 <p></p></FONT></P>6 b7 x4 X% V1 N
    <><FONT size=3>Status algo119(int a[ARRSIZE])//<FONT face=宋体>求</FONT>i!*2^i<FONT face=宋体>序列的值且不超过</FONT></FONT><FONT size=3>maxint
    7 k, W% @! e. N# {1 P5 v{
    5 |% R6 l, c1 l) u6 y  last=1;
    # z- v) j5 i- b5 G  ]) Y  for(i=1;i&lt;=ARRSIZE;i++)
    ' ]% l8 Z/ r) {2 R+ x  {( I  o; A/ B3 q4 v( y6 S% P
      a[i-1]=last*2*i;
      e6 `& i0 e, g% W0 a6 ~) k0 B   if((a[i-1]/last)!=(2*i)) reurn OVERFLOW;4 _/ L5 ?4 z" p3 S& x( z( B6 U& a
       last=a[i-1];3 S9 A: r4 f& U, h
       return OK;
      x" o6 r' P) o/ m  }
    2 I0 a, d) c! L# m$ A/ @}//algo119
    $ |# r7 N- h+ f: o9 n+ G<FONT face=宋体>分析</FONT>:<FONT face=宋体>当某一项的结果超过了</FONT>maxint<FONT face=宋体>时</FONT>,<FONT face=宋体>它除以前面一项的商会发生异常</FONT>. <p></p></FONT></P>* @1 S$ c4 w8 }2 P: R
    <><FONT size=3>1.20 <p></p></FONT></P>$ h$ m) t8 v/ h' |
    <><FONT size=3>void polyvalue()
    . X+ N# K/ h$ ^% U7 i$ Y- ?{3 ^" J( x: l: B+ v: `
      float ad;
    . q& K( D; [3 p1 ?: I  float *p=a;
    " j3 h8 V- o0 H- e5 F6 z  printf("Input number of terms:");7 b: b+ h, B( W' x7 a. l8 S! `$ M
      scanf("%d",&amp;n);5 o- _( d$ u& O8 n: \4 I
      printf("Input the %d coefficients from a0 to a%d:\n",n,n);8 r# G* S* y5 O. ]
      for(i=0;i&lt;=n;i++) scanf("%f",p++);( @& s$ `$ U; o  u5 R& R
      printf("Input value of x:");8 X0 t( `6 z5 U$ R
      scanf("%f",&amp;x);
    & s) N- N1 U6 S) e& Z0 P! b' q3 u  p=a;xp=1;sum=0; //xp<FONT face=宋体>用于存放</FONT>x<FONT face=宋体>的</FONT>i<FONT face=宋体>次方</FONT></FONT>
    " |& Q; y0 w1 p2 b* ]2 m% a<FONT size=3>  for(i=0;i&lt;=n;i++)% S2 S6 u# T0 v" e4 [# X, _
      {
    8 X; R8 H. Z" a- q6 L5 V5 x    sum+=xp*(*p++);
    9 e, \4 b/ u# a0 Z& d+ V7 l& Q& X    xp*=x;
    3 L5 F3 y! z- }) s  H6 ]  }# _5 d! ?3 |5 L( E
      printf("Value is:%f",sum);# ^5 P* i/ ?& Y. l) |" @/ {% j
    }//polyvalue<p></p></FONT></P>
    ; @# s; A" Q0 |, r< ><p><FONT face="Times New Roman"> </FONT></p></P>
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信

    66

    主题

    1

    听众

    648

    积分

    VisaSky.com 加拿大移民留学网

  • TA的每日心情
    开心
    2012-6-9 03:29
  • 签到天数: 1 天

    [LV.1]初来乍到

    发帖功臣 元老勋章

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

    使用道具 举报

    布赖        

    4

    主题

    2

    听众

    134

    积分

    升级  17%

    该用户从未签到

    回复

    使用道具 举报

    铜豆子        

    0

    主题

    3

    听众

    22

    积分

    升级  17.89%

    该用户从未签到

    新人进步奖

    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2026-4-17 15:05 , Processed in 0.474179 second(s), 69 queries .

    回顶部