📄 page_652.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd"> <html> <head> <title>page_652</title> <link rel="stylesheet" href="reset.css" type="text/css" media="all"> <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /> </head> <body> <table summary="top nav" border="0" width="100%"> <tr> <td align="left" width="30%" style="background: #EEF3E2"><a style="color: blue; font-size: 120%; font-weight: bold; text-decoration: none; font-family: verdana;" href="page_651.html">< previous page</a></td> <td align="center" width="40%" style="background: #EEF3E2"><strong style="color: #2F4F4F; font-size: 120%;">page_652</strong></td> <td align="right" width="30%" style="background: #EEF3E2"><a style="color: blue; font-size: 120%; font-weight: bold; text-decoration: none; font-family: verdana;" href="page_653.html">next page ></a></td> </tr> <tr> <td align="left" colspan="3" style="background: #ffffff; padding: 20px;"> <table border="0" width="100%" cellpadding="0"><tr><td align="center"> <table border="0" cellpadding="2" cellspacing="0" width="100%"><tr><td align="left"></td> <td align="right"></td> </tr></table></td></tr><tr><td align="left"><p></p><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td align="right"><font face="Times New Roman, Times, Serif" size="2" color="#FF0000">Page 652</font></td></tr></table><table border="0" cellspacing="0" cellpadding="0"><tr><td rowspan="5"></td> <td colspan="3" height="12"></td> <td rowspan="5"></td></tr><tr><td colspan="3"></td></tr><tr><td></td> <td><font face="Times New Roman, Times, Serif" size="3">While loop contains a compound condition: it stops when it either finds </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">item</font><font face="Times New Roman, Times, Serif" size="3"> or reaches the end of the list. We can insert a copy of </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">item</font><font face="Times New Roman, Times, Serif" size="3"> into </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">list[length]</font><font face="Times New Roman, Times, Serif" size="3">-that is, into the array component beyond the end of the list-as a sentinel. By doing so, we are guaranteed to find </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">item</font><font face="Times New Roman, Times, Serif" size="3"> in the list. The condition that checks for the end of the list (</font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">index < length</font><font face="Times New Roman, Times, Serif" size="3">) can then be eliminated (see Figure 12-2). Eliminating a condition saves the machine time that would be required to test it. In this case, we save time during every iteration of the loop, so the savings add up quickly. (The time saving comes at a cost, however. We sacrifice one array position for the sentinel.)</font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table><table border="0" cellspacing="0" cellpadding="0"><tr><td rowspan="5"></td> <td colspan="3" height="12"></td> <td rowspan="5"></td></tr><tr><td colspan="3"></td></tr><tr><td></td> <td><font face="Times New Roman, Times, Serif" size="3">In storing a copy of </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">item</font><font face="Times New Roman, Times, Serif" size="3"> as a sentinel in </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">list[length]</font><font face="Times New Roman, Times, Serif" size="3">, we assume that </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">length</font><font face="Times New Roman, Times, Serif" size="3"> is always less than </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">MAX_LENGTH</font><font face="Times New Roman, Times, Serif" size="3">. We must document this assumption in the function precondition. Also, we must document the fact that </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">list[length]</font><font face="Times New Roman, Times, Serif" size="3"> is modified by the function (even though </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">list[length]</font><font face="Times New Roman, Times, Serif" size="3"> is assumed to contain meaningless data initially). As well, we remove the word </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">const</font><font face="Times New Roman, Times, Serif" size="3"> in the declaration of the </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">list</font><font face="Times New Roman, Times, Serif" size="3"> parameter so that the compiler lets us modify the array.</font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table><table border="0" cellspacing="0" cellpadding="0"><tr><td rowspan="5"></td> <td colspan="3" height="12"></td> <td rowspan="5"></td></tr><tr><td colspan="3"></td></tr><tr><td></td> <td><font face="Times New Roman, Times, Serif" size="3">After the loop terminates, </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">found</font><font face="Times New Roman, Times, Serif" size="3"> can be set by checking to see if </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">index</font><font face="Times New Roman, Times, Serif" size="3"> is less than </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">length</font><font face="Times New Roman, Times, Serif" size="3">. Function </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">Search2</font><font face="Times New Roman, Times, Serif" size="3"> incorporates all of these changes.</font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table><table border="0" cellspacing="0" cellpadding="0"><tr><td rowspan="5"></td> <td colspan="3" height="12"></td> <td rowspan="5"></td></tr><tr><td colspan="3"></td></tr><tr><td></td> <td><font face="Courier New, Courier, Mono New, Courier, Mono" size="2">void聽Search2(<br />聽聽聽聽聽聽聽聽/*聽inout聽*/聽ItemType聽list[],聽聽聽聽//聽List聽to聽be聽searched<br />聽聽聽聽聽聽聽聽/*聽in聽*/聽聽聽聽ItemType聽item,聽聽聽聽聽聽//聽Item聽to聽be聽found<br />聽聽聽聽聽聽聽聽/*聽in聽*/聽聽聽聽int聽聽聽聽聽聽length,聽聽聽聽//聽Length聽of聽list<br />聽聽聽聽聽聽聽聽/*聽out聽*/聽聽聽int&聽聽聽聽聽index,聽聽聽聽聽//聽Location聽of聽item聽if聽found<br />聽聽聽聽聽聽聽聽/*聽out聽*/聽聽聽Boolean&聽found聽)聽聽聽聽//聽True聽if聽item聽is聽found</font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td rowspan="5"></td> <td colspan="3" height="12"></td> <td rowspan="5"></td></tr><tr><td colspan="3"></td></tr><tr><td></td> <td align="center"><font face="Times New Roman, Times, Serif" size="3"><img src="35023007f45a3375816ddf6183e3dc30.gif" border="0" alt="0652-01.gif" width="469" height="277" /></font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td rowspan="5"></td> <td colspan="3" height="12"></td> <td rowspan="5"></td></tr><tr><td colspan="3"></td></tr><tr><td></td> <td align="center"><font face="Times New Roman, Times, Serif" size="2">Figure 12-2<br />Generalized Sequential Search with Copy of item in list[length]</font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table></td></tr></table><p><font size="0"></font></p>聽 </td> </tr> <tr> <td align="left" width="30%" style="background: #EEF3E2"><a style="color: blue; font-size: 120%; font-weight: bold; text-decoration: none; font-family: verdana;" href="page_651.html">< previous page</a></td> <td align="center" width="40%" style="background: #EEF3E2"><strong style="color: #2F4F4F; font-size: 120%;">page_652</strong></td> <td align="right" width="30%" style="background: #EEF3E2"><a style="color: blue; font-size: 120%; font-weight: bold; text-decoration: none; font-family: verdana;" href="page_653.html">next page ></a></td> </tr> </table> </body> </html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -