?? da04.htm
字號:
style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span>8</span>．<span lang=EN-US>(1)</span>模式匹配<span
lang=EN-US><span style='mso-spacerun:yes'> </span>(2)</span>模式串<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='margin-left:11.4pt;text-indent:-11.4pt;mso-char-indent-count:
-1.0'><span lang=EN-US style='font-family:宋體'>9</span><span style='font-family:
宋體'>．<span lang=EN-US>(1)</span>其數據元素都是字符<span lang=EN-US>(2)</span>順序存儲<span
lang=EN-US>(3)</span>和鏈式存儲<span lang=EN-US>(4)</span>串的長度相等且兩串中對應位置的字符也相等<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='margin-left:11.4pt;text-indent:-11.4pt;mso-char-indent-count:
-1.0'><span lang=EN-US style='font-family:宋體'>10</span><span style='font-family:
宋體'>．兩串的長度相等且兩串中對應位置的字符也相等。<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='margin-left:11.4pt;text-indent:-11.4pt;mso-char-indent-count:
-1.0'><span lang=EN-US style='font-family:宋體'>11</span><span style='font-family:
宋體'>．<span lang=EN-US>’xyxyxywwy’<span
style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span>12</span>．<span lang=EN-US>*s++=*t++
</span>或（<span lang=EN-US>*s++=*t++</span>）<span lang=EN-US>!=</span>‘<span
lang=EN-US>\0</span>’<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='margin-left:11.4pt;text-indent:-11.4pt;mso-char-indent-count:
-1.0'><span lang=EN-US style='font-family:宋體'>13</span><span style='font-family:
宋體'>．（<span lang=EN-US>1</span>）<b style='mso-bidi-font-weight:normal'><span
lang=EN-US>char</span></b><span lang=EN-US> s[ ]<span
style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span>(2) j++ <span
style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span>(3) i >= j<o:p></o:p></span></span></p>
<p class=MsoNormal><span lang=EN-US style='font-family:宋體'>14</span><span
style='font-family:宋體'>．<span lang=EN-US>[</span>題目分析<span lang=EN-US>]</span>本題算法采用順序存儲結構求串<span
lang=EN-US>s</span>和串<span lang=EN-US>t</span>的最大公共子串。串<span lang=EN-US>s</span>用<span
lang=EN-US>i</span>指針（<span lang=EN-US>1<=i<=s.len</span>）。<span
lang=EN-US>t</span>串用<span lang=EN-US>j</span>指針（<span lang=EN-US>1<=j<=t.len</span>）。算法思想是對每個<span
lang=EN-US>i</span>（<span lang=EN-US>1<=i<=s.len</span>，即程序中第一個<b
style='mso-bidi-font-weight:normal'><span lang=EN-US>WHILE</span></b>循環），來求從<span
lang=EN-US>i</span>開始的連續字符串與從<span lang=EN-US>j</span>（<span lang=EN-US>1<=j<=t.len</span>，即程序中第二個Ｗ<span
lang=EN-US>HILE</span>循環）開始的連續字符串的最大匹配。程序中第三個（即最內層）的<b style='mso-bidi-font-weight:
normal'><span lang=EN-US>WHILE</span></b>循環，是當<span lang=EN-US>s</span>中某字符（<span
lang=EN-US>s</span>［<span lang=EN-US>i</span>］）與<span lang=EN-US>t</span>中某字符（<span
lang=EN-US>t</span>［<span lang=EN-US>j</span>］）相等時，求出局部公共子串。若該子串長度大于已求出的最長公共子串（初始為０），則最長公共子串的長度要修改。<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='margin-left:11.4pt;mso-para-margin-left:1.0gd;
text-indent:11.15pt;mso-char-indent-count:.98'><span style='font-family:宋體'>程序（<span
lang=EN-US>a</span>）：（<span lang=EN-US>1</span>）（<span lang=EN-US>i+k<=s.len</span>）<span
lang=EN-US>AND(j+k<=t.len) AND(s[i+k]=t[j+k])<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:宋體'><span
style='mso-spacerun:yes'>
</span><span
style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span>//</span><span style='font-family:宋體'>如果在<span
lang=EN-US>s</span>和<span lang=EN-US>t</span>的長度內，對應字符相等，則指針<span lang=EN-US>k </span>后移（加<span
lang=EN-US>1</span>）。<span lang=EN-US><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:宋體'><span
style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span></span><span
style='font-family:宋體'>（<span lang=EN-US>2</span>）<span lang=EN-US>con:=false <span
style='mso-spacerun:yes'> </span>//s</span>和<span lang=EN-US>t</span>對應字符不等時置標記退出<span
lang=EN-US><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:宋體'><span
style='mso-spacerun:yes'>
</span></span><span style='font-family:宋體'>（<span lang=EN-US>3</span>）<span
lang=EN-US>j:=j+k <span style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span>//</span>在<span
lang=EN-US>t</span>串中，從第<span lang=EN-US>j+k</span>字符再與<span lang=EN-US>s[i]</span>比較<span
lang=EN-US><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:宋體'><span
style='mso-spacerun:yes'>
</span></span><span style='font-family:宋體'>（<span lang=EN-US>4</span>）<span
lang=EN-US>j:=j+1<span
style='mso-spacerun:yes'> </span>//t</span>串取下一字符<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='margin-left:11.4pt;mso-para-margin-left:1.0gd;
text-indent:61.35pt;mso-char-indent-count:5.38'><span style='font-family:宋體'>（<span
lang=EN-US>5</span>）<span lang=EN-US>i</span>：<span lang=EN-US>=i+1<span
style='mso-spacerun:yes'> </span>//s</span>串指針<span
lang=EN-US>i</span>后移（加<span lang=EN-US>1</span>）。<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='margin-left:11.4pt;mso-para-margin-left:1.0gd'><span
style='font-family:宋體'> 程序（<span lang=EN-US>b</span>）：<span lang=EN-US>(1)
i+k<=s.len && j+k<=t.len && s[i+k]==t[j+k]<span
style='mso-spacerun:yes'> </span>//</span>所有注釋同上（<span lang=EN-US>a</span>）<span
lang=EN-US><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:宋體'><span
style='mso-spacerun:yes'>
</span>(2) con=0<span style='mso-spacerun:yes'> </span>(3) j+=k<span
style='mso-spacerun:yes'> </span>(4) j++<span
style='mso-spacerun:yes'> </span>(5) i++<o:p></o:p></span></p>
<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:.5gd;
text-indent:-28.5pt;mso-char-indent-count:-2.5'><span lang=EN-US
style='font-family:宋體'>15</span><span style='font-family:宋體'>．（<span
lang=EN-US>1</span>）<span lang=EN-US>0<span style='mso-spacerun:yes'>
</span></span>（<span lang=EN-US>2</span>）<span lang=EN-US>next[k]<o:p></o:p></span></span></p>
<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:.5gd;
text-indent:-28.5pt;mso-char-indent-count:-2.5'><span lang=EN-US
style='font-family:宋體'>16</span><span style='font-family:宋體'>．（<span
lang=EN-US>1</span>）<span lang=EN-US>i</span>：<span lang=EN-US>=i+1<span
style='mso-spacerun:yes'> </span></span>（<span lang=EN-US>2</span>）<span
lang=EN-US>j:=j+1<span style='mso-spacerun:yes'> </span>(3)i:=i-j+2<span
style='mso-spacerun:yes'> </span>(4)j:=1;<span
style='mso-spacerun:yes'> </span>(5)i-mt</span>（或<span lang=EN-US>i:=i-j+1</span>）<span
lang=EN-US><span style='mso-spacerun:yes'> </span>(6)0<o:p></o:p></span></span></p>
<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:.5gd;
text-indent:-28.5pt;mso-char-indent-count:-2.5'><span lang=EN-US
style='font-family:宋體'>17.</span><span style='font-family:宋體'>程序中遞歸調用<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:.5gd;
text-indent:-28.5pt;mso-char-indent-count:-2.5'><span lang=EN-US
style='font-family:宋體'><span style='mso-spacerun:yes'> </span></span><span
style='font-family:宋體'>（<span lang=EN-US>1</span>）<span lang=EN-US>ch1<>midch<span
style='mso-spacerun:yes'> </span>//</span>當讀入不是分隔符<span lang=EN-US>&</span>和輸入結束符<span
lang=EN-US>$</span>時，繼續讀入字符<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:.5gd;
text-indent:-28.5pt;mso-char-indent-count:-2.5'><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>ch1=ch2<span
style='mso-spacerun:yes'> </span>//</span>讀入分隔符<span lang=EN-US>&</span>后，判<span
lang=EN-US style='color:red'>ch1</span>是否等于<span lang=EN-US>ch2</span>，得出真假結論。<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:.5gd;
text-indent:-28.5pt;mso-char-indent-count:-2.5'><span lang=EN-US
style='font-family:宋體'><span style='mso-spacerun:yes'> </span></span><span
style='font-family:宋體'>（<span lang=EN-US>3</span>）<span lang=EN-US>answer</span>：<span
lang=EN-US>=true<o:p></o:p></span></span></p>
<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:.5gd;
text-indent:-28.5pt;mso-char-indent-count:-2.5'><span lang=EN-US
style='font-family:宋體'><span style='mso-spacerun:yes'> </span></span><span
style='font-family:宋體'>（<span lang=EN-US>4</span>）<span lang=EN-US>answer</span>：<span
lang=EN-US>=false<o:p></o:p></span></span></p>
<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:.5gd;
text-indent:-28.5pt;mso-char-indent-count:-2.5'><span lang=EN-US
style='font-family:宋體'><span style='mso-spacerun:yes'> </span></span><span
style='font-family:宋體'>（<span lang=EN-US>5</span>）<span lang=EN-US>read</span>（<span
lang=EN-US>ch</span>）<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:.5gd;
text-indent:-28.5pt;mso-char-indent-count:-2.5'><span lang=EN-US
style='font-family:宋體'><span style='mso-spacerun:yes'> </span></span><span
style='font-family:宋體'>（<span lang=EN-US>6</span>）<span lang=EN-US>ch=endch<o:p></o:p></span></span></p>
<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:.5gd;
text-indent:-28.5pt;mso-char-indent-count:-2.5'><span lang=EN-US
style='font-family:宋體'>18</span><span style='font-family:宋體'>．（<span
lang=EN-US>1</span>）<span lang=EN-US>initstack</span>（<span lang=EN-US>s</span>）<span
lang=EN-US><span style='mso-spacerun:yes'> </span>/</span>／棧<span
lang=EN-US>s</span>初始化為空棧。<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:.5gd;
text-indent:-28.5pt;mso-char-indent-count:-2.5'><span lang=EN-US
style='font-family:宋體'><o:p> </o:p></span></p>
<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:.5gd;
text-indent:-28.5pt;mso-char-indent-count:-2.5'><span style='font-family:宋體'> <span
lang=EN-US><span style='mso-spacerun:yes'> </span>(2) setnull (exp) <span
style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span>//</span>串<span lang=EN-US>exp</span>初始化為空串。<span
lang=EN-US> <o:p></o:p></span></span></p>
<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:2.5gd;
text-indent:-5.7pt;mso-char-indent-count:-.5'><span lang=EN-US
style='font-family:宋體'>(3) ch in opset<span style='mso-spacerun:yes'>
</span><span style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span><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='margin-left:34.2pt;mso-para-margin-left:.5gd;
text-indent:-28.5pt;mso-char-indent-count:-2.5'><span lang=EN-US
style='font-family:宋體'><span style='mso-spacerun:yes'>
</span>(4) push (s,ch)<span style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span>//</span><span
style='font-family:宋體'>如<span lang=EN-US>ch</span>是運算符，則入運算符棧<span lang=EN-US>s</span>。<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:.5gd;
text-indent:-28.5pt;mso-char-indent-count:-2.5'><span lang=EN-US
style='font-family:宋體'><span style='mso-spacerun:yes'>
</span>(5) sempty (s)<span style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span>//</span><span
style='font-family:宋體'>判棧<span lang=EN-US>s</span>是否為空。<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:.5gd;
text-indent:-28.5pt;mso-char-indent-count:-2.5'><span lang=EN-US
style='font-family:宋體'><span style='mso-spacerun:yes'>
</span>(6) succ := false <span style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span>//</span><span
style='font-family:宋體'>若讀出<span lang=EN-US>ch</span>是操作數且棧為空，則按出錯處理。<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='margin-left:34.2pt;mso-para-margin-left:.5gd;
text-indent:-28.5pt;mso-char-indent-count:-2.5'><span lang=EN-US
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -