📄 da04.htm
字号:
<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-USstyle='font-family:宋体'><span style='mso-spacerun:yes'> </span>(9) exp<spanstyle='mso-spacerun:yes'> </span>(10) gettop(s) //</span><span style='font-family:宋体'>取栈顶操作符。<spanlang=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-USstyle='font-family:宋体'><span style='mso-spacerun:yes'> </span>(11) pop(s) <spanstyle='mso-spacerun:yes'> </span><spanstyle='mso-spacerun:yes'> </span><spanstyle='mso-spacerun:yes'> </span>//</span><spanstyle='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:宋体'> <spanlang=EN-US>(12­) sempty(s)</span> <span lang=EN-US><spanstyle='mso-spacerun:yes'> </span>//</span>将<spanlang=EN-US>pre</span>的最后一个字符（操作数）加入到中缀式<span lang=EN-US>exp</span>的最后。<spanlang=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-USstyle='font-family:宋体'><o:p> </o:p></span></p><p class=MsoNormal><span style='font-family:黑体;mso-hansi-font-family:宋体'>四．应用题<spanlang=EN-US><o:p></o:p></span></span></p><p class=MsoNormal><span style='font-family:宋体'> １．串是零个至多个字符组成的有限序列。从数据结构角度讲，串属于线性结构。与线性表的特殊性在于串的元素是字符。<spanlang=EN-US><o:p></o:p></span></span></p><p class=MsoNormal><span style='font-family:宋体'> ２．空格是一个字符，其<span lang=EN-US>ASCII</span>码值是<spanlang=EN-US>32</span>。空格串是由空格组成的串，其长度等于空格的个数。空串是不含任何字符的串，即空串的长度是零。<spanlang=EN-US><o:p></o:p></span></span></p><p class=MsoNormal><span style='font-family:宋体'> ３．</span><spanstyle='font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"'>最优的</span><span lang=EN-US style='font-family:宋体'>T(m,n)</span><spanstyle='font-family:宋体'>是<span lang=EN-US>O</span>（<span lang=EN-US>n</span>）。串<spanlang=EN-US>S2</span>是串<span lang=EN-US>S1</span>的子串，且在<span lang=EN-US>S1</span>中的位置是<spanlang=EN-US>1</span>。开始求出最大公共子串的长度恰是串<span lang=EN-US>S2</span>的长度<spanstyle='color:red'>，一般情况下，<span lang=EN-US>T(m,n) =O(m*n)</span>。<spanlang=EN-US><o:p></o:p></span></span></span></p><p class=MsoNormal><span style='font-family:宋体'> ４．朴素的模式匹配（<span lang=EN-US>Brute</span>－<spanlang=EN-US>Force</span>）时间复杂度是Ｏ（<span lang=EN-US>m</span>＊<span lang=EN-US>n</span>），<spanlang=EN-US>KMP</span>算法有一定改进，时间复杂度达到Ｏ（<span lang=EN-US>m</span>＋<spanlang=EN-US>n</span>）。本题也可采用从后面匹配的方法，即从右向左扫描，比较６次成功。另一种匹配方式是从左往右扫描，但是先比较模式串的最后一个字符，若不等，则模式串后移；若相等，再比较模式串的第一个字符，若第一个字符也相等，则从模式串的第二个字符开始，向右比较，直至相等或失败。若失败，模式串后移，再重复以上过程。按这种方法，本题比较<spanlang=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>算法主要优点是主串指针不回溯。当主串很大不能一次读入内存且经常发生部分匹配时，<spanlang=EN-US>KMP</span>算法的优点更为突出．<span lang=EN-US><o:p></o:p></span></span></p><p class=MsoNormal><span style='font-family:宋体'> ６．模式串的<span lang=EN-US>next</span>函数定义如下：<spanlang=EN-US> <o:p></o:p></span></span></p><p class=MsoNormal><span style='font-family:宋体'> <span lang=EN-US>next</span>［<spanlang=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=80src="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:宋体'><spanstyle='mso-spacerun:yes'> </span></span><spanstyle='font-family:宋体'>根据此定义，可求解模式串<span lang=EN-US>t</span>的<span lang=EN-US>next</span>和<spanlang=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-USstyle='font-family:宋体'>7</span><span style='font-family:宋体'>．解法同上题<spanlang=EN-US>6</span>，其<span lang=EN-US>next</span>和<span lang=EN-US>nextval</span>值分别为<spanlang=EN-US>0112123422</span>和<span lang=EN-US>0102010422</span>。<spanlang=EN-US><o:p></o:p></span></span></p><p class=MsoNormal align=left style='text-align:left'><span lang=EN-USstyle='font-family:宋体'>8</span><span style='font-family:宋体'>．解法同题<spanlang=EN-US>6</span>，<span lang=EN-US>t</span>串的<span lang=EN-US>next</span>和<spanlang=EN-US>nextval</span>函数值分别为<span lang=EN-US>0111232</span>和<spanlang=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-USstyle='font-family:宋体'>9</span><span style='font-family:宋体'>．解法同题<spanlang=EN-US>6</span>，其<span lang=EN-US>next</span>和<span lang=EN-US>nextval </span>值分别为<spanlang=EN-US>011123121231</span>和<span lang=EN-US>011013020131</span>。<spanlang=EN-US><o:p></o:p></span></span></p><p class=MsoNormal align=left style='text-align:left'><span lang=EN-USstyle='font-family:宋体'>10</span><span style='font-family:宋体'>．<span lang=EN-USstyle='color:red'>p1</span>的<span lang=EN-US>next</span>和<span lang=EN-US>nextval</span>值分别为：<spanlang=EN-US>0112234</span>和<span lang=EN-US>0102102</span>；<span lang=EN-USstyle='color:red'>p2</span>的<span lang=EN-US>next</span>和<span lang=EN-US>nextval</span>值分别为：<spanlang=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-USstyle='font-family:宋体'>11</span><span style='font-family:宋体'>．<span lang=EN-US>next</span>数组值为<spanlang=EN-US>011234567<span style='mso-spacerun:yes'> </span></span>改进后的<spanlang=EN-US>next</span>数组信息值为<span lang=EN-US>010101017</span>。<span lang=EN-US><o:p></o:p></span></span></p><p class=MsoNormal align=left style='text-align:left'><span lang=EN-USstyle='font-family:宋体'>12</span><span style='font-family:宋体'>．<span lang=EN-US>011122312</span>。<spanlang=EN-US><o:p></o:p></span></span></p><p class=MsoNormal align=left style='text-align:left'><span lang=EN-US⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -