📄 page_1048.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd"> <html> <head> <title>page_1048</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_1047.html">< previous page</a></td> <td align="center" width="40%" style="background: #EEF3E2"><strong style="color: #2F4F4F; font-size: 120%;">page_1048</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_1049.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 1048</font></td></tr></table><table border="0" cellspacing="0" cellpadding="0" width="100%"><tr><td rowspan="5"><img src="3e26ecb1b6ac508ae10a0e39d2fb98b2.gif" border="0" width="96" height="1" alt="3e26ecb1b6ac508ae10a0e39d2fb98b2.gif" /></td> <td colspan="3" height="12"></td> <td rowspan="5"><img src="3e26ecb1b6ac508ae10a0e39d2fb98b2.gif" border="0" width="96" height="1" alt="3e26ecb1b6ac508ae10a0e39d2fb98b2.gif" /></td></tr><tr><td colspan="3" height="2"><table cellpadding="0" cellspacing="0" border="0"><tr><td></td></tr></table></td></tr><tr><td></td> <td><font face="Times New Roman, Times, Serif" size="2">Linked List A list in which the order of the components is determined by an explicit link member in each node, rather than by the sequential order of the components in memory.</font></td><td></td></tr><tr><td colspan="3" height="2"><table cellpadding="0" cellspacing="0" border="0"><tr><td></td></tr></table></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="17"></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">Array Representation of a 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">A linked list can be represented as an array of </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">structs</font><font face="Times New Roman, Times, Serif" size="3">. For a linked list of </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">int</font><font face="Times New Roman, Times, Serif" size="3"> components, we use the following declarations:</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">struct聽NodeType<br />{<br />聽聽聽聽int聽component;<br />聽聽聽聽int聽link;<br />};<br /><br />NodeType聽list[1000];聽聽聽聽//聽Max.聽1000聽nodes<br />int聽聽聽聽聽聽head;</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 nodes all reside in an array named </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">list</font><font face="Times New Roman, Times, Serif" size="3">. Each node has two members: </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">component</font><font face="Times New Roman, Times, Serif" size="3"> (in this example, an </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">int</font><font face="Times New Roman, Times, Serif" size="3"> data value) and </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">link</font><font face="Times New Roman, Times, Serif" size="3">, which contains the <i>array index</i> of the next node in the list. The last node in the list will have a </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 -1. Because -1 is not a valid array index in C++, it is suitable as a special "end-of-list" value. The variable </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">head</font><font face="Times New Roman, Times, Serif" size="3"> contains the array index of the first node in the list. Figure 18-3 illustrates an array representation of the linked list of Figure 18-2.</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">Compare Figures 18-1 and 18-3. Figure 18-1 shows a list represented directly as an array. Figure 18-3 shows a list represented as a linked list, which, in turn, is represented as an array (of </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">structs</font><font face="Times New Roman, Times, Serif" size="3">). We said that when insertions and deletions occur frequently, it is better to use a linked list to represent a list than it is to use an array directly. Let's see why.</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">Figure 18-1 showed the effect of inserting 25 into the list; we had to shift array elements 2, 3, 4, ... down to insert the value 25 into element 2. If the list is long, we might have to move hundreds or thousands of numbers. In contrast, inserting the value 25 into the linked list of Figure 18-3 requires <i>no</i> movement of existing data. We simply find an unused slot in the array, store 25 into the </font><font face="Courier New, Courier, Mono New, Courier, Mono" size="3">component</font><font face="Times New Roman, Times, Serif" size="3"> member, and adjust 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 node containing 16 (see Figure 18-4).</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">Before we introduce the second technique for implementing a linked list-the use of dynamic data and pointers-let's step back and look at the big picture. We are interested in the list as an ADT. Because it is an ADT, we</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_1047.html">< previous page</a></td> <td align="center" width="40%" style="background: #EEF3E2"><strong style="color: #2F4F4F; font-size: 120%;">page_1048</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_1049.html">next page ></a></td> </tr> </table> </body> </html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -