📄 da02.htm
字号:
<p class=MsoNormal style='text-indent:11.15pt;mso-char-indent-count:.98'><span
lang=EN-US style='font-family:宋体'>1</span><span style='font-family:宋体'>．顺序<span
lang=EN-US><span
style='mso-spacerun:yes'>
</span>2</span>．（<span lang=EN-US>n-1</span>）<span lang=EN-US>/2<span
style='mso-spacerun:yes'>
</span>3</span>．<span lang=EN-US>py->next=px->next; px->next=py<o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:11.15pt;mso-char-indent-count:.98'><span
lang=EN-US style='font-family:宋体'>4 </span><span style='font-family:宋体'>．<span
lang=EN-US>n-i+1<o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:11.15pt;mso-char-indent-count:.98'><span
lang=EN-US style='font-family:宋体'>5</span><span style='font-family:宋体'>．主要是使插入和删除等操作统一，在第一个元素之前插入<span
style='color:red'>元素</span>和删除第一个结点不必另作判断。另外，不论链表是否为空，链表指针不变。<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='margin-left:9.4pt'><span lang=EN-US style='font-family:
宋体'>6</span><span style='font-family:宋体'>．<span lang=EN-US>O(1)</span>，<span
lang=EN-US>O(n)<span style='mso-spacerun:yes'>
</span>7</span>．单链表，<span style='color:red'>多重</span>链表，（动态）链表，静态链表<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:11.15pt;mso-char-indent-count:.98'><span
lang=EN-US style='font-family:宋体'>8</span><span style='font-family:宋体'>．<span
lang=EN-US>f->next=p->next; f->prior=p; p->next->prior=f; p->next=f;<o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:11.15pt;mso-char-indent-count:.98'><span
lang=EN-US style='font-family:宋体'>9</span><span style='font-family:宋体'>．<span
lang=EN-US>p^.prior<span style='mso-spacerun:yes'>
</span>s^.prior^.next<o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:11.15pt;mso-char-indent-count:.98'><span
lang=EN-US style='font-family:宋体'>10</span><span style='font-family:宋体'>． 指针<span
lang=EN-US><span style='mso-spacerun:yes'> </span>11</span>．物理上相邻<span
lang=EN-US><span style='mso-spacerun:yes'> </span></span>指针<span
lang=EN-US><span style='mso-spacerun:yes'>
</span>12</span>．<span lang=EN-US>4<span
style='mso-spacerun:yes'> </span>2<o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:11.15pt;mso-char-indent-count:.98'><span
lang=EN-US style='font-family:宋体'>13</span><span style='font-family:宋体'>．从任一结点出发都可访问到链表中每一个元素。<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:11.15pt;mso-char-indent-count:.98'><span
lang=EN-US style='font-family:宋体'>14</span><span style='font-family:宋体'>．<span
lang=EN-US>u=p->next; p->next=u->next; free(u);<span
style='mso-spacerun:yes'> </span>15</span>．<span
lang=EN-US>L->next->next==L<span style='mso-spacerun:yes'>
</span>16</span>．<span lang=EN-US>p->next!=null<o:p></o:p></span></span></p>
<p class=MsoNormal style='margin-left:11.4pt;mso-para-margin-left:1.0gd'><span
lang=EN-US style='font-family:宋体'>17</span><span style='font-family:宋体'>．<span
lang=EN-US>L->next==L && L->prior==L<span
style='mso-spacerun:yes'>
</span>18</span>．<span lang=EN-US>s->next=p->next;p->next=s;<o:p></o:p></span></span></p>
<p class=MsoNormal style='margin-left:11.4pt;mso-para-margin-left:1.0gd'><span
lang=EN-US style='font-family:宋体'>19</span><span style='font-family:宋体'>．<span
lang=EN-US>(1) <b style='mso-bidi-font-weight:normal'>IF </b>pa=NIL <b
style='mso-bidi-font-weight:normal'>THEN</b> <b style='mso-bidi-font-weight:
normal'>return</b>(true);<o:p></o:p></span></span></p>
<p class=MsoNormal style='margin-left:11.4pt;mso-para-margin-left:1.0gd;
text-indent:19.5pt'><span lang=EN-US style='font-family:宋体'>(2) pb<>NIL <b
style='mso-bidi-font-weight:normal'>AND</b> pa^.data>=pb^.data<o:p></o:p></span></p>
<p class=MsoNormal style='margin-left:11.4pt;mso-para-margin-left:1.0gd;
text-indent:19.5pt'><span lang=EN-US style='font-family:宋体'>(3) <b
style='mso-bidi-font-weight:normal'>return</b>(inclusion(pa,pb));<o:p></o:p></span></p>
<p class=MsoNormal style='margin-left:11.4pt;mso-para-margin-left:1.0gd;
text-indent:19.5pt'><span lang=EN-US style='font-family:宋体'>(4) pb:=pb^.next;<o:p></o:p></span></p>
<p class=MsoNormal style='margin-left:11.4pt;mso-para-margin-left:1.0gd;
text-indent:19.5pt'><span lang=EN-US style='font-family:宋体'>(5) <b
style='mso-bidi-font-weight:normal'>return</b>(false);<o:p></o:p></span></p>
<p class=MsoNormal style='margin-left:11.4pt;mso-para-margin-left:1.0gd;
text-indent:19.5pt'><span style='font-family:宋体'>非递归算法：<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:28.5pt;mso-char-indent-count:2.5'><span
lang=EN-US style='font-family:宋体'>(1)pre:=pb; (2) pa<>NIL AND
pb<>NIL AND pb^.data>=pa^.data<span style='mso-spacerun:yes'>
</span>(3)pa:=pa^.next; pb:=pb->next;<o:p></o:p></span></p>
<p class=MsoNormal style='text-indent:28.5pt;mso-char-indent-count:2.5'><span
lang=EN-US style='font-family:宋体'>(4)pb:=pre^.next;pre:=pb;pa:=pa^.next;(5)<b
style='mso-bidi-font-weight:normal'>IF </b>pa=NIL <b style='mso-bidi-font-weight:
normal'>THEN</b> <b style='mso-bidi-font-weight:normal'>return</b>(true) <b
style='mso-bidi-font-weight:normal'>ELSE</b> <b style='mso-bidi-font-weight:
normal'>return</b>(false);<o:p></o:p></span></p>
<p class=MsoNormal><span lang=EN-US style='font-family:宋体'>[</span><span
style='font-family:宋体'>注<span lang=EN-US>]</span>：本题是在链表上求模式匹配问题。非递归算法中用指针<span
lang=EN-US>pre</span>指向主串中开始结点（初始时为第一元素结点）。若主串与子串对应数据相等，两串工作指针<span lang=EN-US>pa</span>和<span
lang=EN-US>pb</span>后移；否则，主串工作指针从<span lang=EN-US>pre</span>的下一结点开始（这时<span
lang=EN-US>pre</span>又指向新的开始结点），子串工作指针从子串第一元素开始，比较一直继续到循环条件失败。若<span
lang=EN-US>pa</span>为空，则匹配成功，返回<span lang=EN-US>true</span>，否则，返回<span
lang=EN-US>false</span>。<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:11.4pt;mso-char-indent-count:1.0'><span
lang=EN-US style='font-family:宋体'>20</span><span style='font-family:宋体'>．<span
lang=EN-US>A</span>．<b style='mso-bidi-font-weight:normal'><span lang=EN-US>VAR</span></b><span
lang=EN-US> head:ptr<span style='mso-spacerun:yes'> </span>B. new(p)<span
style='mso-spacerun:yes'> </span>C. p^.data:=k<span
style='mso-spacerun:yes'> </span>D. q^.next:=p<span
style='mso-spacerun:yes'> </span>E. q:=p(</span>带头结点<span
lang=EN-US>)<o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:11.4pt;mso-char-indent-count:1.0'><span
lang=EN-US style='font-family:宋体'>21</span><span style='font-family:宋体'>．（<span
lang=EN-US>1</span>）<span lang=EN-US>new(h);∥</span>生成头结点，以便于操作。<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:21.6pt'><span lang=EN-US
style='font-family:宋体'><span style='mso-spacerun:yes'> </span></span><span
style='font-family:宋体'>（<span lang=EN-US>2</span>）<span lang=EN-US>r^.next:=p; <span
style='mso-spacerun:yes'> </span>(3) r^.next:=q;<span
style='mso-spacerun:yes'> </span>(4) <b style='mso-bidi-font-weight:
normal'><span style='color:red'>IF </span></b>(q=NIL) <b style='mso-bidi-font-weight:
normal'><span style='color:red'>THEN</span></b> r^.next:=p;<o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:11.4pt;mso-char-indent-count:1.0'><span
lang=EN-US style='font-family:宋体'>22</span><span style='font-family:宋体'>．<span
lang=EN-US>A: r^.link^.data<>max <b style='mso-bidi-font-weight:normal'>AND</b>
q^.link^.data<>max<o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:34.2pt;mso-char-indent-count:3.0'><span
lang=EN-US style='font-family:宋体'>B: r:=r^.link<span
style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span>C: q^.link <span
style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span>D: q^.link <span
style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span>E: r^.link <span
style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span>F: r^.link<o:p></o:p></span></p>
<p class=MsoNormal style='text-indent:34.2pt;mso-char-indent-count:3.0'><span
lang=EN-US style='font-family:宋体'>G: r:=s</span><span style='font-family:宋体'>（或<span
lang=EN-US>r:= r^.link</span>）<span lang=EN-US><span
style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span>H: r:=r^.link <span
style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span>I: q^.link:=s^.link<o:p></o:p></span></span></p>
<p class=MsoNormal style='tab-stops:27.0pt'><span lang=EN-US style='font-family:
宋体'><span style='mso-spacerun:yes'> </span>23</span><span
style='font-family:宋体'>．<span lang=EN-US>(1)la<span
style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span>(2)0<span
style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span>(3)j<i-1<span
style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span>(4)p</span>↑<span lang=EN-US>.next
<span style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span>(5)i<1<o:p></o:p></span></span></p>
<p class=MsoNormal style='tab-stops:27.0pt'><span lang=EN-US style='font-family:
宋体'><span style='mso-spacerun:yes'> </span>24.(1)head^.left:=s<span
style='mso-spacerun:yes'> </span>∥head</span><span style='font-family:
宋体'>的前驱指针指向插入结点<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:31.8pt;tab-stops:27.0pt'><span
lang=EN-US style='font-family:宋体'>(2)j:=<span style='color:red'>1</span>;<o:p></o:p></span></p>
<p class=MsoNormal style='text-indent:31.8pt;tab-stops:27.0pt'><span
lang=EN-US style='font-family:宋体'>(3)p:=p^.right<span
style='mso-spacerun:yes'> </span></span><span style='font-family:宋体'>∥工作指针后移<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:31.8pt;tab-stops:27.0pt'><span
lang=EN-US style='font-family:宋体'>(4)s^.left:=p<o:p></o:p></span></p>
<p class=MsoNormal style='text-indent:31.8pt;tab-stops:27.0pt'><span
lang=EN-US style='font-family:宋体'>(5)p^.right^.left:=s;<span
style='mso-spacerun:yes'> </span></span><span style='font-family:宋体'>∥<span
lang=EN-US>p</span>后继的前驱是<span lang=EN-US>s<o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:31.8pt;tab-stops:27.0pt'><span
lang=EN-US style='font-family:宋体'>(6)s^.left:=p;<o:p></o:p></span></p>
<p class=MsoNormal style='text-indent:22.8pt;mso-char-indent-count:2.0;
tab-stops:27.0pt'><span lang=EN-US style='font-family:宋体'>25.(1)i<=L.last<span
style='mso-spacerun:yes'> </span>∥L.last </span><span style='font-family:
宋体'>为元素个数 <span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:22.8pt;mso-char-indent-count:2.0;
tab-stops:27.0pt'><span lang=EN-US style='font-family:宋体'><span
style='mso-spacerun:yes'> </span>(2)j:=j+1<span
style='mso-spacerun:yes'> </span></span><span
style='font-family:宋体'>∥有值不相等的元素<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:40.8pt;mso-char-indent-count:3.58;
tab-stops:27.0pt'><span lang=EN-US style='font-family:宋体'>(3)L.elem[j]:=L.elem[i]<span
style='mso-spacerun:yes'> </span></span><span style='font-family:宋体'>∥元素前移<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:40.8pt;mso-char-indent-count:3.58;
tab-stops:27.0pt'><span lang=EN-US style='font-family:宋体'>(4)L.last:=j<span
style='mso-spacerun:yes'> </span></span><span style='font-family:宋体'>∥元素个数<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:21.6pt;tab-stops:27.0pt'><span
lang=EN-US style='font-family:宋体'>26.(A)p^.link:=q;∥</span><span
style='font-family:宋体'>拉上链，前驱指向后继<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:21.6pt;tab-stops:27.0pt'><span
lang=EN-US style='font-family:宋体'><span style='mso-spacerun:yes'>
</span>(B)p:=q;</span><span style='font-family:宋体'>∥新的前驱<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:21.6pt;tab-stops:27.0pt'><span
lang=EN-US style='font-family:宋体'><span style='mso-spacerun:yes'>
</span>(C)p^.link:=head;</span><span style='font-family:宋体'>∥形成循环链表<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:21.6pt;tab-stops:27.0pt'><span
lang=EN-US style='font-family:宋体'><span style='mso-spacerun:yes'>
</span>(D)j:=0;<span style='mso-spacerun:yes'> </span></span><span
style='font-family:宋体'>∥计数器，记被删结点<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:21.6pt;tab-stops:27.0pt'><span
lang=EN-US style='font-family:宋体'><span style='mso-spacerun:yes'>
</span>(E)q:=p^.link</span><span style='font-family:宋体'>∥记下被删结点<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:21.6pt;tab-stops:27.0pt'><span
lang=EN-US style='font-family:宋体'><span style='mso-spacerun:yes'>
</span>(F)p^.link=q^.link<span style='mso-spacerun:yes'> </span></span><span
style='font-family:宋体'>∥删除结点<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:21.6pt;tab-stops:27.0pt'><span
lang=EN-US style='font-family:宋体'>27. (1)p:=r;∥r</span><span style='font-family:
宋体'>指向工作指针<span lang=EN-US>s</span>的前驱，<span lang=EN-US>p</span>指向最小值的前驱。<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:21.6pt;tab-stops:27.0pt'><span
lang=EN-US style='font-family:宋体'><span
style='mso-spacerun:yes'> </span>(2)q:=s;</span><span
style='font-family:宋体'>∥<span lang=EN-US>q</span>指向最小值结点，<span lang=EN-US>s</span>是工作指针<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:46.05pt;mso-char-indent-count:4.04;
tab-stops:27.0pt'><span lang=EN-US style='font-family:宋体'>(3)s:=s^.link</span><span
style='font-family:宋体'>∥工作指针后移<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:46.05pt;mso-char-indent-count:4.04;
tab-stops:27.0pt'><span lang=EN-US style='font-family:宋体'>(4)head:=head^.next;</span><span
style='font-family:宋体'>∥第一个结点值最小；<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:46.05pt;mso-char-indent-count:4.04;
tab-stops:27.0pt'><span lang=EN-US style='font-family:宋体'>(5)p^link:=q^.link;</span><span
style='font-family:宋体'>∥跨过被删结点（即删除一结点）<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:21.6pt;tab-stops:27.0pt'><span
lang=EN-US style='font-family:宋体'>28</span><span style='font-family:宋体'>．<span
lang=EN-US>(1) l^.key:=x;∥</span>头结点<span lang=EN-US>l</span>这时起监视哨作用<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:21.6pt;tab-stops:27.0pt'><span
lang=EN-US style='font-family:宋体'><span
style='mso-spacerun:yes'> </span>(2) l^.freq:=p^.freq<span
style='mso-spacerun:yes'> </span>∥</span><span style='font-family:
宋体'>头结点起监视哨作用<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='text-indent:45.85pt;mso-char-indent-count:4.02;
tab-stops:27.0pt'><span lang=EN-US style='font-family:宋体'>(3) q->pre->next=q->next;
q->next->pre=q->pre;<span style='mso-spacerun:yes'> </span></span><span
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -