📄 勘误(数据结构）.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0037)http://www.artech.com.cn/test/gai.htm -->
<HTML><HEAD><TITLE>勘误</TITLE>
<META http-equiv=Content-Type content="text/html; charset=gb2312">
<STYLE type=text/css>@import url( 勘误(数据结构）.files/sty.css );
</STYLE>
<META content="MSHTML 5.50.4134.100" name=GENERATOR></HEAD>
<BODY bgColor=#ffffff>
<DIV align=center><!-- #BeginLibraryItem "/Library/top.lbi" -->
<SCRIPT language=JavaScript>
<!--
function MM_reloadPage(init) { //reloads the window if Nav4 resized
if (init==true) with (navigator) {if ((appName=="Netscape")&&(parseInt(appVersion)==4)) {
document.MM_pgW=innerWidth; document.MM_pgH=innerHeight; onresize=MM_reloadPage; }}
else if (innerWidth!=document.MM_pgW || innerHeight!=document.MM_pgH) location.reload();
}
MM_reloadPage(true);
// -->
</SCRIPT>
<DIV align=center><IMG height=67 src="勘误(数据结构）.files/k2.gif" width=640
align=middle useMap=#Map border=0> <MAP name=Map><AREA shape=RECT
coords=67,48,128,68 href="http://www.artech.com.cn/kaoyan.htm"><AREA
shape=RECT coords=131,49,210,66
href="http://www.artech.com.cn/test/gengxin.htm"><AREA shape=RECT
coords=217,47,298,67 href="http://www.artech.com.cn/test/shiti.htm"><AREA
shape=RECT coords=303,48,384,66
href="http://www.artech.com.cn/test/luntan/lt.asp"><AREA shape=RECT
coords=392,49,470,64 href="http://www.artech.com.cn/test/lianmeng.asp"><AREA
shape=RECT coords=476,48,558,69
href="http://www.artech.com.cn/test/tuijian.htm"></MAP>
<SCRIPT>
document.write("<a href=http://best.netease.com/cgi-bin/view/viewbasic.cgi?wenyan target=_blank><img src=http://best.netease.com/cgi-bin/log.cgi?user=wenyan&refer="+escape(document.referrer)+"&cur="+escape(document.URL)+" border=0 alt=网易中文站点排行榜 width=0 height=0 align=top></a>");
</SCRIPT>
</DIV><!-- #EndLibraryItem --><BR>
<TABLE width=640 border=0>
<TBODY>
<TR class=txt>
<TD class=white>
<P><SPAN style="FONT-FAMILY: 宋体">数据结构第</SPAN><SPAN
lang=EN-US>1</SPAN><SPAN style="FONT-FAMILY: 宋体">章综合例题</SPAN><SPAN
lang=EN-US>1.2</SPAN><SPAN style="FONT-FAMILY: 宋体">题（第</SPAN><SPAN
lang=EN-US>8</SPAN><SPAN style="FONT-FAMILY: 宋体">页）解答</SPAN></P></TD></TR>
<TR class=txt>
<TD>
<DIV style="LAYOUT-GRID: 15.6pt none">
<P> </P>
<P style="TEXT-INDENT: 21pt"><SPAN
style="FONT-FAMILY: 宋体">与原解答相比增加了一个过程</SPAN><SPAN
lang=EN-US>Skip</SPAN><SPAN style="FONT-FAMILY: 宋体">，执行与</SPAN><SPAN
lang=EN-US>MoveNext</SPAN><SPAN
style="FONT-FAMILY: 宋体">类似但不同的功能，</SPAN><SPAN lang=EN-US>Skip</SPAN><SPAN
style="FONT-FAMILY: 宋体">是匹配情况下的向前移，只删除并释放相同值的元素（最后保留一个），</SPAN><SPAN
lang=EN-US>MoveNext</SPAN><SPAN
style="FONT-FAMILY: 宋体">是不匹配情况下的向前移，在移动过程中先删除并释放这个不匹配的元素，再删除并释放相同值的元素（也是最后保留一个）。</SPAN><SPAN
style="FONT-FAMILY: 宋体">另外，原解答没有考虑</SPAN><SPAN lang=EN-US>B</SPAN><SPAN
style="FONT-FAMILY: 宋体">、</SPAN><SPAN lang=EN-US>C</SPAN><SPAN
style="FONT-FAMILY: 宋体">耗尽而</SPAN><SPAN lang=EN-US>A</SPAN><SPAN
style="FONT-FAMILY: 宋体">未耗尽的情况，此处做了后续处理。此外原解答用</SPAN><SPAN
lang=EN-US>MoveNext</SPAN><SPAN style="FONT-FAMILY: 宋体">删去了</SPAN><SPAN
lang=EN-US>B</SPAN><SPAN style="FONT-FAMILY: 宋体">、</SPAN><SPAN
lang=EN-US>C</SPAN><SPAN
style="FONT-FAMILY: 宋体">中部分元素，实际上B、C中的元素不用删除，因为题目中只要求对A操作。整个过程请大家在纸上画一画，还是比较清楚的。</SPAN></P>
<P style="TEXT-INDENT: 21pt"><SPAN
style="FONT-FAMILY: 宋体">原解答整体思路有疏漏，现在给出的解答思路如下：</SPAN></P>
<P><SPAN> </SPAN>(1)<SPAN
style="FONT-FAMILY: 宋体">若三个相等，则大家都简单地向前移一个元素</SPAN></P>
<P><SPAN> </SPAN>(2)<SPAN
style="FONT-FAMILY: 宋体">否则找出最小的，向前移一个元素，如果两个并列最小，随便挑一个向前移（实际实现中是按</SPAN><SPAN
lang=EN-US>A</SPAN><SPAN style="FONT-FAMILY: 宋体">、</SPAN><SPAN
lang=EN-US>B</SPAN><SPAN style="FONT-FAMILY: 宋体">、</SPAN><SPAN
lang=EN-US>C</SPAN><SPAN
style="FONT-FAMILY: 宋体">的顺序），另一个将在下一次循环中得到解决</SPAN></P>
<P><SPAN> </SPAN><SPAN
style="FONT-FAMILY: 宋体">在</SPAN><SPAN lang=EN-US>(1)</SPAN><SPAN
style="FONT-FAMILY: 宋体">中</SPAN><SPAN lang=EN-US>A</SPAN><SPAN
style="FONT-FAMILY: 宋体">的移动用</SPAN><SPAN lang=EN-US>Skip</SPAN><SPAN
style="FONT-FAMILY: 宋体">，在</SPAN><SPAN lang=EN-US>(2)</SPAN><SPAN
style="FONT-FAMILY: 宋体">中</SPAN><SPAN lang=EN-US>A</SPAN><SPAN
style="FONT-FAMILY: 宋体">的移动用</SPAN><SPAN lang=EN-US>MoveNext</SPAN></P>
<P><SPAN> </SPAN>B<SPAN
style="FONT-FAMILY: 宋体">和</SPAN><SPAN lang=EN-US>C</SPAN><SPAN
style="FONT-FAMILY: 宋体">的移动均简单地进行指针赋值，而不应调用</SPAN><SPAN
lang=EN-US>MoveNext</SPAN><SPAN style="FONT-FAMILY: 宋体">过程</SPAN></P>
<P style="TEXT-INDENT: 21.75pt"><SPAN
style="FONT-FAMILY: 宋体">循环结束后，若</SPAN><SPAN lang=EN-US>A</SPAN><SPAN
style="FONT-FAMILY: 宋体">未耗尽，则</SPAN><SPAN lang=EN-US>A</SPAN><SPAN
style="FONT-FAMILY: 宋体">中剩下的元素显然不可能再匹配，应全部释放，被匹配的最后一个元素的</SPAN><SPAN
lang=EN-US>next</SPAN><SPAN style="FONT-FAMILY: 宋体">域置</SPAN><SPAN
lang=EN-US>NIL</SPAN></P>
<P style="TEXT-INDENT: 21.75pt"><SPAN
style="FONT-FAMILY: 宋体">改正后的解答如下：</SPAN></P>
<P><SPAN lang=EN-US><![if !supportEmptyParas]><![endif]>
<O:P></O:P></SPAN></P>
<P><SPAN lang=EN-US>TYPE</SPAN></P>
<P><SPAN> </SPAN>pointer =^node;</P>
<P style="TEXT-INDENT: 21pt"><SPAN lang=EN-US>node = RECORD</SPAN></P>
<P><SPAN>
</SPAN> data: datatype;</P>
<P><SPAN>
</SPAN> next: pointer</P>
<P><SPAN>
</SPAN> END;</P>
<P><SPAN> </SPAN>linklist =
pointer;</P>
<P><SPAN lang=EN-US><![if !supportEmptyParas]><![endif]>
<O:P></O:P></SPAN></P>
<P><SPAN lang=EN-US>PROCEDURE MoveNext(VAR pre, p: linklist);</SPAN></P>
<P><SPAN> </SPAN>BEGIN</P>
<P><SPAN>
</SPAN> pre^.next:=p^.next;</P>
<P><SPAN>
</SPAN> dispose(p);</P>
<P><SPAN>
</SPAN> p:=pre^.next;</P>
<P><SPAN>
</SPAN> WHILE pre^.data = p^.data
DO</P>
<P><SPAN>
</SPAN> BEGIN</P>
<P><SPAN>
</SPAN> pre^.next:=p^.next;</P>
<P><SPAN>
</SPAN> dispose(p);</P>
<P><SPAN>
</SPAN> p:=pre^.next</P>
<P><SPAN>
</SPAN> END;</P>
<P><SPAN> </SPAN>END</P>
<P><SPAN lang=EN-US><![if !supportEmptyParas]><![endif]>
<O:P></O:P></SPAN></P>
<P><SPAN lang=EN-US>PROCEDURE Skip(VAR pre, p: linklist);</SPAN></P>
<P><SPAN> </SPAN>BEGIN</P>
<P><SPAN>
</SPAN>pre:=p;</P>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -