【正文】 he k’th element and return it in x L = (a,b,c,d,e) delete(2,x) = L=(a,c,d,e), x=b, and index of c,d,e decrease by 1 delete(0) = error delete(20) = error O( n) . Simple Array Implementation of Lists AMN=∑(ni1)/n=(n1+n2+…… +1+0)/n=(n1)/2 n1 i=0 e1 e2 en . Simple Array Implementation of Lists ? insert (x , i) insert x after the i?th element L = (a,b,c,d,e,f,g) insert(0,h) = L = (h,a,b,c,d,e,f,g) index of a,b,c,d,e,f, and g increase by 1 insert(10,h) = error insert(6,h) = error O( n) . Simple Array Implementation of Lists 0 1 2 n1 n AMN=∑(n i)/(n+1)=(n+n1+…… +1+0)/(n+1)=n/2 n i=0 e1 e2 en . Simple Array Implementation of Lists 2. Use array Implementation merit : easy Search. short ing : Insertion and Removing(Deletion) spend a lot of time. . Linked Lists In order to avoid the linear cost of insertion and deletion. 1) Each node of a data object keeps a link or a pointer about the location of other relevant nodes L=(e1,e2,………e n) first Link field Data field …… null e1 e2 e3 en . Linked Lists ? The figure above is called a single linked list,and the structure is also called a chain ? A chain is a linked list in which each node represents one element. ? There is a link or pointer from one element to the next. ? The last node has a null pointer. . Linked Lists ? Deletion a element of a chain Delete(1,x) a b c d e null first first = 。 newNode .link = before .link。 } . Linked Lists 2) Iterator class for linked lists current ? package DataStructures public class LinkedListItr { LinkedListItr( ListNode theNode) { current = theNode。 } public void makeEmpty( ) { = null。 itr. Advance( ) ) ( ( ) + “ “ ) 。 if( != null ) = 。 != null ) = new ListNode( x, )。 newNode .right=firstNode。最后一個(gè)編號 7的旅客將贏得環(huán)球旅游。 2) if (i = = 1) { head = 。 } public void insertTerm( int coef, int exp ) public void zeroPolynomial( ) public Polynomial add( Polynomial rhs ) public Polynomial multiply( Polynomial rhs ) throws Overflow public void print( ) public static final int MAXDEGREE = 100。 = max( highPower, )。 for( int i = 0。 } public class Polynomial { public Polynomial( ) { /* Exercise */ } public void insertTerm( int coef, int exp ) { /* Exercise */ } public void zeroPolynomial( ) { /* Exercise */ } public Polynomial add( Polynomial rhs ) { /* Exercise */ } public Polynomial multiply( Polynomial rhs ) { /* Exercise */ } public void print( ) { /* Exercise */ } private List terms。 if (系數(shù)相加結(jié)果為 0){ p=pa。 pa前進(jìn) } 3)當(dāng)兩鏈表中有一鏈表為空，則將另一鏈表鏈入結(jié)果鏈表就可以 if (pb空了 ){ pc. link=pa。 } . Cursor implementation of Linked Lists public class CursorListItr { CursorListItr( int theNode ) { current = theNode。 } public void makeEmpty( ) public CursorListItr zeroth( ) { return new CursorListItr( header )。 i++) cursorSpace[ i ] = new CursorNode( null, i + 1 )。 cursorSpace[0].next = p。 cursorSpace[ tmp ].element = x。 } } ? makeEmpty for cursor implementation public void makeEmpty( ) { while( !isEmpty( ) ) remove( first( ).retrieve( ) )。 。 cursorSpace[ pos ].next = cursorSpace[ tmp ].next。 != 0) { int pos = 。 } private static void free( int p ) { cursorSpace[p].element = null。 for( int i = 0。 cursorSpace[ header ].next = 0。 } object element。 pb前進(jìn) } c)指數(shù)不等 pa. exp pb. exp //pa要插入結(jié)果鏈表 {pc. link=pa 。 p= pb(c++需要） 。 } 2) Class skeletons for linked list implemetation of the Polynomial ADT 3 1990 2 1492 11 1