road.htm

常用经典算法及讲解

yes">&nbsp;&nbsp;&nbsp; </span>node2.arr:=work;<span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>node2.parent:=0;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>node2.i1:=5; node2.j1:=2;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>node2.i2:=5; node2.j2:=3;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>ext_to_sd(node2,queue[0]^);</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>writeln(f1,'Huarong dao result:');</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>writeln(f1,'num=0');</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>prtnode(node2);</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>for i:=0 to 6 do</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>for j:=0 to 5 do</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>work2[i,j]:=20;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>for i:=1 to 2 do<span style="mso-spacerun:
yes">&nbsp; </span>{目标点状态}</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>begin</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>work2[i,1]:=5;
work2[i,2]:=4; work2[i,3]:=3; work2[i,4]:=2;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>end;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>work2[3,1]:=1; work2[3,2]:=1; work2[3,3]:=8;
work2[3,4]:=8;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>work2[4,1]:=0; work2[4,2]:=9; work2[4,3]:=9;
work2[4,4]:=1;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>work2[5,1]:=0; work2[5,2]:=9; work2[5,3]:=9;
work2[5,4]:=1;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>node2.arr:=work2;<span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>node2.parent:=0;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>node2.i1:=4; node2.j1:=1;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>node2.i2:=5; node2.j2:=1;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>ext_to_sd(node2,queue2[0]^);</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>end;{1}</span></p>

<p class=MsoPlainText><span lang=EN-US><![if !supportEmptyParas]>&nbsp;<![endif]><o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US>procedure<span style="mso-spacerun:
yes">&nbsp; </span>prtnode(node3:node_ext); {No.2 打印结点值}</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>var i,j:integer;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>begin {2}</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>with node3 do</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>begin {node3}</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>for i:=1 to 5 do</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>begin</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>for j:=1 to 4 do<span style="mso-spacerun: yes">&nbsp;
</span>write(f1,arr[i,j]:3);</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>writeln(f1);</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>end;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>end;{node3}</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>end; {2}</span></p>

<p class=MsoPlainText><span lang=EN-US><![if !supportEmptyParas]>&nbsp;<![endif]><o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US>procedure ext_to_sd(node0:node_ext;var
node3:node_sd); {No.3 结点类型转换，扩展结点转为标准结点}</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>var i,j:integer;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>begin {3}</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>with node3 do</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>begin</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>for i:=1 to 5 do</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>for j:=1 to 4 do</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>arr[i,j]:=node0.arr[i,j];</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>parent:=node0.parent;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>i1:=node0.i1;<span
style="mso-spacerun: yes">&nbsp; </span>j1:=node0.j1;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>i2:=node0.i2;<span
style="mso-spacerun: yes">&nbsp; </span>j2:=node0.j2;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>end;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>end; {3}</span></p>

<p class=MsoPlainText><span lang=EN-US><![if !supportEmptyParas]>&nbsp;<![endif]><o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US>procedure sd_to_ext(node0:node_sd;var
node3:node_ext); {No.4结点类型转换，标准结点转为扩展结点}</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>var i,j:integer;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>begin {4}</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>with node3 do</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>begin</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>for i:=1 to 5 do</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>for j:=1 to 4 do</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>work[i,j]:=node0.arr[i,j];</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>arr:=work;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>parent:=node0.parent;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>i1:=node0.i1;<span
style="mso-spacerun: yes">&nbsp; </span>j1:=node0.j1;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>i2:=node0.i2;<span
style="mso-spacerun: yes">&nbsp; </span>j2:=node0.j2;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>end;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>end; {4}</span></p>

<p class=MsoPlainText><span lang=EN-US><![if !supportEmptyParas]>&nbsp;<![endif]><o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US>procedure
result(k:integer;node3:node_ext); {No.5 搜索成功后的处理}</span></p>

<p class=MsoPlainText><span lang=EN-US>var i,tmp,num:integer;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>res:array [1..200]of integer;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;</span><span style="mso-spacerun: yes">&nbsp;&nbsp;
</span>snode:node_sd;</span></p>

<p class=MsoPlainText><span lang=EN-US>begin {5}</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>tmp:=node3.parent; num:=0;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>while(tmp&gt;0) do</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>begin</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>num:=num+1;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>snode:=queue[tmp]^;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>res[num]:=tmp;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>tmp:=snode.parent;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>end;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>writeln(f1,'num=',num);<span style="mso-spacerun: yes">&nbsp;
</span>writeln(f1,'queue_1');</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>for i:=num downto 1 do</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>begin</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>snode:=queue[res[i]]^;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>sd_to_ext(snode,node2);</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>writeln(f1,'num=',num-i+1);</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>prtnode(node2);</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>end;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>writeln(f1,'queue_2');</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>tmp:=k;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>while (tmp&gt;0) do</span></p>