?? da04.htm
字號(hào):
style='font-family:宋體'><span style='mso-spacerun:yes'>
</span>(7) exp<span style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span>(8)ch<span
style='mso-spacerun:yes'> </span>//</span><span style='font-family:宋體'>若<span
lang=EN-US>ch</span>是操作數(shù)且棧非空，則形成部分中綴表達(dá)式。<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>(9) exp<span
style='mso-spacerun:yes'>
</span>(10) gettop(s) //</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>(11) pop(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><o:p></o:p></span></span></p>
<p class=MsoNormal style='margin-left:114.0pt;mso-para-margin-left:.5gd;
text-indent:-108.3pt;mso-char-indent-count:-9.5'><span style='font-family:宋體'> <span
lang=EN-US>(12­) sempty(s)</span> <span lang=EN-US><span
style='mso-spacerun:yes'> </span>//</span>將<span
lang=EN-US>pre</span>的最后一個(gè)字符（操作數(shù)）加入到中綴式<span lang=EN-US>exp</span>的最后。<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal style='margin-left:114.0pt;mso-para-margin-left:.5gd;
text-indent:-108.3pt;mso-char-indent-count:-9.5'><span lang=EN-US
style='font-family:宋體'><o:p> </o:p></span></p>
<p class=MsoNormal><span style='font-family:黑體;mso-hansi-font-family:宋體'>四．應(yīng)用題<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal><span style='font-family:宋體'> １．串是零個(gè)至多個(gè)字符組成的有限序列。從數(shù)據(jù)結(jié)構(gòu)角度講，串屬于線性結(jié)構(gòu)。與線性表的特殊性在于串的元素是字符。<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal><span style='font-family:宋體'> ２．空格是一個(gè)字符，其<span lang=EN-US>ASCII</span>碼值是<span
lang=EN-US>32</span>。空格串是由空格組成的串，其長(zhǎng)度等于空格的個(gè)數(shù)。空串是不含任何字符的串，即空串的長(zhǎng)度是零。<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal><span style='font-family:宋體'> ３．</span><span
style='font-family:宋體;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"'>最優(yōu)的</span><span lang=EN-US style='font-family:宋體'>T(m,n)</span><span
style='font-family:宋體'>是<span lang=EN-US>O</span>（<span lang=EN-US>n</span>）。串<span
lang=EN-US>S2</span>是串<span lang=EN-US>S1</span>的子串，且在<span lang=EN-US>S1</span>中的位置是<span
lang=EN-US>1</span>。開(kāi)始求出最大公共子串的長(zhǎng)度恰是串<span lang=EN-US>S2</span>的長(zhǎng)度<span
style='color:red'>，一般情況下，<span lang=EN-US>T(m,n) =O(m*n)</span>。<span
lang=EN-US><o:p></o:p></span></span></span></p>
<p class=MsoNormal><span style='font-family:宋體'> ４．樸素的模式匹配（<span lang=EN-US>Brute</span>－<span
lang=EN-US>Force</span>）時(shí)間復(fù)雜度是Ｏ（<span lang=EN-US>m</span>＊<span lang=EN-US>n</span>），<span
lang=EN-US>KMP</span>算法有一定改進(jìn)，時(shí)間復(fù)雜度達(dá)到Ｏ（<span lang=EN-US>m</span>＋<span
lang=EN-US>n</span>）。本題也可采用從后面匹配的方法，即從右向左掃描，比較６次成功。另一種匹配方式是從左往右掃描，但是先比較模式串的最后一個(gè)字符，若不等，則模式串后移；若相等，再比較模式串的第一個(gè)字符，若第一個(gè)字符也相等，則從模式串的第二個(gè)字符開(kāi)始，向右比較，直至相等或失敗。若失敗，模式串后移，再重復(fù)以上過(guò)程。按這種方法，本題比較<span
lang=EN-US>18</span>次成功。<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal><span style='font-family:宋體'> ５．<span lang=EN-US>KMP</span>算法主要優(yōu)點(diǎn)是主串指針不回溯。當(dāng)主串很大不能一次讀入內(nèi)存且經(jīng)常發(fā)生部分匹配時(shí)，<span
lang=EN-US>KMP</span>算法的優(yōu)點(diǎn)更為突出．<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal><span style='font-family:宋體'> ６．模式串的<span lang=EN-US>next</span>函數(shù)定義如下：<span
lang=EN-US> <o:p></o:p></span></span></p>
<p class=MsoNormal><span style='font-family:宋體'> <span lang=EN-US>next</span>［<span
lang=EN-US>j</span>］<span lang=EN-US>=<sub><!--[if gte vml 1]><v:shapetype
id="_x0000_t75" coordsize="21600,21600" o:spt="75" o:preferrelative="t"
path="m@4@5l@4@11@9@11@9@5xe" filled="f" stroked="f">
<v:stroke joinstyle="miter"/>
<v:formulas>
<v:f eqn="if lineDrawn pixelLineWidth 0"/>
<v:f eqn="sum @0 1 0"/>
<v:f eqn="sum 0 0 @1"/>
<v:f eqn="prod @2 1 2"/>
<v:f eqn="prod @3 21600 pixelWidth"/>
<v:f eqn="prod @3 21600 pixelHeight"/>
<v:f eqn="sum @0 0 1"/>
<v:f eqn="prod @6 1 2"/>
<v:f eqn="prod @7 21600 pixelWidth"/>
<v:f eqn="sum @8 21600 0"/>
<v:f eqn="prod @7 21600 pixelHeight"/>
<v:f eqn="sum @10 21600 0"/>
</v:formulas>
<v:path o:extrusionok="f" gradientshapeok="t" o:connecttype="rect"/>
<o:lock v:ext="edit" aspectratio="t"/>
</v:shapetype><v:shape id="_x0000_i1025" type="#_x0000_t75" style='width:351.75pt;
height:60pt' o:ole="">
<v:imagedata src="da04.files/image001.wmz" o:title=""/>
</v:shape><![endif]--><![if !vml]><img width=469 height=80
src="da04.files/image002.gif" v:shapes="_x0000_i1025"><![endif]></sub><!--[if gte mso 9]><xml>
<o:OLEObject Type="Embed" ProgID="Equation.3" ShapeID="_x0000_i1025"
DrawAspect="Content" ObjectID="_1149856307">
</o:OLEObject>
</xml><![endif]--><o:p></o:p></span></span></p>
<p class=MsoNormal><span lang=EN-US style='font-family:宋體'><span
style='mso-spacerun:yes'> </span></span><span
style='font-family:宋體'>根據(jù)此定義，可求解模式串<span lang=EN-US>t</span>的<span lang=EN-US>next</span>和<span
lang=EN-US>nextval</span>值如下：<span lang=EN-US><o:p></o:p></span></span></p>
<table class=MsoNormalTable border=1 cellspacing=0 cellpadding=0
style='margin-left:34.95pt;border-collapse:collapse;border:none;mso-border-alt:
solid windowtext .5pt;mso-yfti-tbllook:191;mso-padding-alt:0cm 5.4pt 0cm 5.4pt;
mso-border-insideh:.5pt solid windowtext;mso-border-insidev:.5pt solid windowtext'>
<tr style='mso-yfti-irow:0;mso-yfti-firstrow:yes'>
<td width=119 valign=top style='width:89.25pt;border:solid windowtext 1.0pt;
mso-border-alt:solid windowtext .5pt;padding:0cm 5.4pt 0cm 5.4pt'>
<p class=MsoNormal><span lang=EN-US>j</span></p>
</td>
<td width=286 valign=top style='width:214.2pt;border:solid windowtext 1.0pt;
border-left:none;mso-border-left-alt:solid windowtext .5pt;mso-border-alt:
solid windowtext .5pt;padding:0cm 5.4pt 0cm 5.4pt'>
<p class=MsoNormal><span lang=EN-US>1<span style='mso-spacerun:yes'>
</span>2<span style='mso-spacerun:yes'> </span>3<span
style='mso-spacerun:yes'> </span>4<span style='mso-spacerun:yes'>
</span>5<span style='mso-spacerun:yes'> </span>6<span
style='mso-spacerun:yes'> </span>7<span style='mso-spacerun:yes'>
</span>8<span style='mso-spacerun:yes'> </span>9<span
style='mso-spacerun:yes'> </span>10 11 12 </span></p>
</td>
</tr>
<tr style='mso-yfti-irow:1'>
<td width=119 valign=top style='width:89.25pt;border:solid windowtext 1.0pt;
border-top:none;mso-border-top-alt:solid windowtext .5pt;mso-border-alt:solid windowtext .5pt;
padding:0cm 5.4pt 0cm 5.4pt'>
<p class=MsoNormal><span lang=EN-US>t</span><span style='font-family:宋體;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>串</span><span
lang=EN-US style='font-family:宋體'><o:p></o:p></span></p>
</td>
<td width=286 valign=top style='width:214.2pt;border-top:none;border-left:
none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;
mso-border-top-alt:solid windowtext .5pt;mso-border-left-alt:solid windowtext .5pt;
mso-border-alt:solid windowtext .5pt;padding:0cm 5.4pt 0cm 5.4pt'>
<p class=MsoNormal><span lang=EN-US>a<span style='mso-spacerun:yes'>
</span>b<span style='mso-spacerun:yes'> </span>c<span
style='mso-spacerun:yes'> </span>a<span style='mso-spacerun:yes'>
</span>a<span style='mso-spacerun:yes'> </span>b<span
style='mso-spacerun:yes'> </span>b<span style='mso-spacerun:yes'>
</span>a<span style='mso-spacerun:yes'> </span>b<span
style='mso-spacerun:yes'> </span><span
style='mso-spacerun:yes'> </span>c<span style='mso-spacerun:yes'>
</span>a<span style='mso-spacerun:yes'> </span>b</span><span
lang=EN-US style='font-family:宋體'><o:p></o:p></span></p>
</td>
</tr>
<tr style='mso-yfti-irow:2'>
<td width=119 valign=top style='width:89.25pt;border:solid windowtext 1.0pt;
border-top:none;mso-border-top-alt:solid windowtext .5pt;mso-border-alt:solid windowtext .5pt;
padding:0cm 5.4pt 0cm 5.4pt'>
<p class=MsoNormal><span lang=EN-US>next[j]</span><span lang=EN-US
style='font-family:宋體'><o:p></o:p></span></p>
</td>
<td width=286 valign=top style='width:214.2pt;border-top:none;border-left:
none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;
mso-border-top-alt:solid windowtext .5pt;mso-border-left-alt:solid windowtext .5pt;
mso-border-alt:solid windowtext .5pt;padding:0cm 5.4pt 0cm 5.4pt'>
<p class=MsoNormal><span lang=EN-US>0<span style='mso-spacerun:yes'>
</span>1<span style='mso-spacerun:yes'> </span>1<span
style='mso-spacerun:yes'> </span>1<span style='mso-spacerun:yes'>
</span>2<span style='mso-spacerun:yes'> </span>2<span
style='mso-spacerun:yes'> </span>3<span style='mso-spacerun:yes'>
</span>1<span style='mso-spacerun:yes'> </span>2<span
style='mso-spacerun:yes'> </span>3<span style='mso-spacerun:yes'>
</span>4<span style='mso-spacerun:yes'> </span>5</span><span
lang=EN-US style='font-family:宋體'><o:p></o:p></span></p>
</td>
</tr>
<tr style='mso-yfti-irow:3;mso-yfti-lastrow:yes'>
<td width=119 valign=top style='width:89.25pt;border:solid windowtext 1.0pt;
border-top:none;mso-border-top-alt:solid windowtext .5pt;mso-border-alt:solid windowtext .5pt;
padding:0cm 5.4pt 0cm 5.4pt'>
<p class=MsoNormal><span lang=EN-US>nextval[j]</span><span lang=EN-US
style='font-family:宋體'><o:p></o:p></span></p>
</td>
<td width=286 valign=top style='width:214.2pt;border-top:none;border-left:
none;border-bottom:solid windowtext 1.0pt;border-right:solid windowtext 1.0pt;
mso-border-top-alt:solid windowtext .5pt;mso-border-left-alt:solid windowtext .5pt;
mso-border-alt:solid windowtext .5pt;padding:0cm 5.4pt 0cm 5.4pt'>
<p class=MsoNormal><span lang=EN-US>0<span style='mso-spacerun:yes'>
</span>1<span style='mso-spacerun:yes'> </span>1<span
style='mso-spacerun:yes'> </span>0<span style='mso-spacerun:yes'>
</span>2<span style='mso-spacerun:yes'> </span>1<span
style='mso-spacerun:yes'> </span>3<span style='mso-spacerun:yes'>
</span>0<span style='mso-spacerun:yes'> </span>1<span
style='mso-spacerun:yes'> </span>1<span style='mso-spacerun:yes'>
</span>0<span style='mso-spacerun:yes'> </span><span style='color:red'>5</span></span><span
lang=EN-US style='font-family:宋體'><o:p></o:p></span></p>
</td>
</tr>
</table>
<p class=MsoNormal align=left style='text-align:left'><span lang=EN-US
style='font-family:宋體'>7</span><span style='font-family:宋體'>．解法同上題<span
lang=EN-US>6</span>，其<span lang=EN-US>next</span>和<span lang=EN-US>nextval</span>值分別為<span
lang=EN-US>0112123422</span>和<span lang=EN-US>0102010422</span>。<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal align=left style='text-align:left'><span lang=EN-US
style='font-family:宋體'>8</span><span style='font-family:宋體'>．解法同題<span
lang=EN-US>6</span>，<span lang=EN-US>t</span>串的<span lang=EN-US>next</span>和<span
lang=EN-US>nextval</span>函數(shù)值分別為<span lang=EN-US>0111232</span>和<span
lang=EN-US>0110132</span>。<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal align=left style='text-align:left'><span lang=EN-US
style='font-family:宋體'>9</span><span style='font-family:宋體'>．解法同題<span
lang=EN-US>6</span>，其<span lang=EN-US>next</span>和<span lang=EN-US>nextval </span>值分別為<span
lang=EN-US>011123121231</span>和<span lang=EN-US>011013020131</span>。<span
lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal align=left style='text-align:left'><span lang=EN-US
style='font-family:宋體'>10</span><span style='font-family:宋體'>．<span lang=EN-US
style='color:red'>p1</span>的<span lang=EN-US>next</span>和<span lang=EN-US>nextval</span>值分別為：<span
lang=EN-US>0112234</span>和<span lang=EN-US>0102102</span>；<span lang=EN-US
style='color:red'>p2</span>的<span lang=EN-US>next</span>和<span lang=EN-US>nextval</span>值分別為：<span
lang=EN-US>0121123</span>和<span lang=EN-US>0021002</span>。<span lang=EN-US><o:p></o:p></span></span></p>
<p class=MsoNormal align=left style='text-align:left'><span lang=EN-US
style='font-family:宋體'>11</span><span style='font-family:宋體'>．<span lang=EN-US>next</span>數(shù)組值為<span
?? 快捷鍵說(shuō)明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -