📄 page_1139.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd"> <html> <head> <title>page_1139</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_1138.html">< previous page</a></td> <td align="center" width="40%" style="background: #EEF3E2"><strong style="color: #2F4F4F; font-size: 120%;">page_1139</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_1140.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 1139</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">new dynamic node and copy the </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">component</font><font face="Times New Roman, Times, Serif" size="3"> value from the original node into the new node. However, we cannot yet fill in the </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">link</font><font face="Times New Roman, Times, Serif" size="3"> member of the new node. We must wait until we have cloned the second node so that we can store its address into the </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">link</font><font face="Times New Roman, Times, Serif" size="3"> member of the first node. Likewise, the cloning of the second node cannot complete until we have finished cloning the third node. Eventually, we clone the last node of the original list and set the </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">link</font><font face="Times New Roman, Times, Serif" size="3"> member of the cloned node to </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">NULL</font><font face="Times New Roman, Times, Serif" size="3">. At this point, the last node returns its address to the next-to-last node, which stores the address into its </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">link</font><font face="Times New Roman, Times, Serif" size="3"> member. The next-to-last node returns its address to the node before it, and so forth. The process completes when the first node returns its address to the first (nonrecursive) call, yielding an external pointer to the new linked list.</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">PtrToClone (In: fromPtr) // Recursive algorithm Out: Function value</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="440" 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">IF聽fromPtr聽聽is聽NULL<br />聽聽聽聽Return聽NULL<br />ELSE<br />聽聽Set聽toPtr聽=聽new聽NodeType<br />聽聽Set聽toPtr->component聽=聽fromPtr->component<br />聽聽Set聽toPtr->link聽=聽PtrToClone(fromPtr->link)<br />聽聽Return聽toPtr</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">Like the solution to the Towers of Hanoi problem, this looks too simple; yet, it is the algorithm. Because the actual parameter that is passed to each recursive call is </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">fromPtr->link</font><font face="Times New Roman, Times, Serif" size="3">, the number of nodes left in the original list gets smaller with each call. The base case occurs when the pointer into the original list becomes </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">NULL</font><font face="Times New Roman, Times, Serif" size="3">. Below is the C++ function that implements the algorithm.</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">NodePtr聽PtrToClone(聽/*聽in聽*/聽NodePtr聽fromPtr聽)<br /><br />//聽Precondition:<br />//聽聽聽聽聽fromPtr聽points聽to聽a聽list聽node聽(or聽==聽NULL)<br />//聽Postcondition:<br />//聽聽聽聽聽IF聽fromPtr聽!=聽NULL<br />//聽聽聽聽聽聽聽聽聽聽聽A聽clone聽of聽the聽entire聽sublist聽starting聽with聽*fromPtr<br />//聽聽聽聽聽聽聽聽聽聽聽is聽on聽the聽free聽store<br />//聽聽聽聽聽聽聽聽&&聽Function聽value聽==聽pointer聽to聽front聽of聽this聽sublist<br />//聽聽聽聽聽ELSE<br />//聽聽聽聽聽聽聽聽聽聽聽Function聽value聽==聽NULL<br /><br />{<br />聽聽聽聽NodePtr聽toPtr;聽聽聽聽聽//聽Pointer聽to聽newly聽created聽node</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_1138.html">< previous page</a></td> <td align="center" width="40%" style="background: #EEF3E2"><strong style="color: #2F4F4F; font-size: 120%;">page_1139</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_1140.html">next page ></a></td> </tr> </table> </body> </html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -