📄 page_1068.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd"> <html> <head> <title>page_1068</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_1067.html">< previous page</a></td> <td align="center" width="40%" style="background: #EEF3E2"><strong style="color: #2F4F4F; font-size: 120%;">page_1068</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_1069.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 1068</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">Insert (In: item)</font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table><table cellspacing="0" border="0" width="432" cellpadding="4"><tr><td valign="top"><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">Set聽newNodePtr聽=聽new聽NodeType<br />Set聽component聽member聽of聽</font><font face="Symbol" size="2">*</font><font face="Courier New, Courier, Mono New, Courier, Mono" size="2">newNodePtr聽=聽item<br />Set聽prevPtr聽=聽NULL<br />Set聽currPtr聽=聽head<br />WHILE聽item聽>聽component聽member聽of聽</font><font face="Symbol" size="2">*</font><font face="Courier New, Courier, Mono New, Courier, Mono" size="2">currPtr<br />聽聽Set聽prevPtr聽=聽currPtr<br />聽聽Set聽currPtr聽=聽link聽member聽of聽</font><font face="Symbol" size="2">*</font><font face="Courier New, Courier, Mono New, Courier, Mono" size="2">currPtr<br />Insert聽</font><font face="Symbol" size="2">*</font><font face="Courier New, Courier, Mono New, Courier, Mono" size="2">newNodePtr聽between聽</font><font face="Symbol" size="2">*</font><font face="Courier New, Courier, Mono New, Courier, Mono" size="2">prevPtr聽and聽</font><font face="Symbol" size="2">*</font><font face="Courier New, Courier, Mono New, Courier, Mono" size="2">currPtr</font></td><td></td></tr><tr><td colspan="3"></td></tr><tr><td colspan="3" height="1"></td></tr></table></td></tr></table><br /><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">This algorithm is basically sound, but there are problems with it in special cases. If the new component is larger than all other components in the list, the event that stops the loop (finding a node whose component is larger than the one being inserted) does not occur. When the end of the list is reached, the While condition tries to dereference </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">currPtr</font><font face="Times New Roman, Times, Serif" size="3">, which now contains </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">NULL</font><font face="Times New Roman, Times, Serif" size="3">. On some systems, the program will crash. We can take care of this case by using the following expression to control the While loop:</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">currPtr聽isn't聽NULL聽AND聽item聽>聽component聽member聽of聽</font><font face="Symbol" size="2">*</font><font face="Courier New, Courier, Mono New, Courier, Mono" size="2">currPtr</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">This expression keeps us from dereferencing the null pointer because C++ uses short-circuit evaluation of logical expressions. If the first part evaluates to FALSE-that is, if </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">currPtr</font><font face="Times New Roman, Times, Serif" size="3"> equals </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">NULL</font><font face="Times New Roman, Times, Serif" size="3">-the second part of the expression, which dereferences </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">currPtr</font><font face="Times New Roman, Times, Serif" size="3">, is not evaluated.</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">There is one more point to consider in our algorithm: the special case when the list is empty or the new value is less than the first component in the list. Variable </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">prevPtr</font><font face="Times New Roman, Times, Serif" size="3"> remains </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">NULL</font><font face="Times New Roman, Times, Serif" size="3"> in this case, and </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">*newNodePtr</font><font face="Times New Roman, Times, Serif" size="3"> must be inserted at the top instead of between </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">*prevPtr</font><font face="Times New Roman, Times, Serif" size="3"> and </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">*currPtr</font><font face="Times New Roman, Times, Serif" size="3">.</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">The following function implements our algorithm with these changes incorporated.</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聽OrdList::Insert(聽/*聽in聽*/聽ComponentType聽item聽)<br /><br />//聽Precondition:<br />//聽聽聽聽聽component聽members聽of聽list聽nodes聽are聽in聽ascending聽order<br />//聽聽&&聽item聽is聽assigned<br />//聽Postcondition:<br />//聽聽聽聽聽New聽node聽containing聽item聽is聽inserted聽into聽its聽proper聽place<br />//聽聽聽聽聽in聽linked聽list<br />//聽聽&&聽component聽members聽of聽list聽nodes聽are聽in聽ascending聽order<br /><br />{</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_1067.html">< previous page</a></td> <td align="center" width="40%" style="background: #EEF3E2"><strong style="color: #2F4F4F; font-size: 120%;">page_1068</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_1069.html">next page ></a></td> </tr> </table> </body> </html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -