【正文】 p != first ) { current = p。 return 1。 } return 0。 } Doubly Linked Lists:searching Another method? Data Structure Software College Northeastern University 1. p→ lLink = current。 2. p→ rLink =current→ rLink。 3. current→ rLink = p。 4. current = current→ rLink。 5. current→ rLink→ lLink = current。 1 2 3 4 5 Doubly Linked Lists:Inserting(1) Data Structure Software College Northeastern University template class Type void DblListType:: Insert ( const Type amp。 value ) { if ( current == NULL ) //空表情形 current = first→ rLink = new DblNode ( value, first, first )。 else { //非空表情形 current→ rLink =new DblNode ( value, current, current→ rLink )。 current = current→ rLink。 } current→ rLink→ lLink = current。 } Doubly Linked Lists:Inserting(2) Data Structure Software College Northeastern University 1. current→ rLink→ lLink = current→ lLink。 2. current→ lLink→ rLink = current→ rLink。 1 2 Doubly Linked Lists:Deleting(1) Data Structure Software College Northeastern University template class Type void DblListType::Remove ( ) { if ( current != NULL ) { DblNode *temp = current。 //被刪結(jié)點 current = current→ rLink。 //下一結(jié)點 current→ lLink = temp→ lLink。 //從鏈中摘下 temp→ lLink→ rLink = current。 delete temp。 //刪去 if ( current == first ) if ( IsEmpty ( ) ) current = NULL。 else current = current→ rLink。 } } Doubly Linked Lists:Deleting(2) Data Structure Software College Northeastern University template class Type int DblListType::Length ( ) const { //求雙向循環(huán)鏈表的長度 (不計表頭結(jié)點 ) DblNodeType * p = first→ rLink。 int count = 0。 while ( p != first ) { p = p→ rLink。 count++。 } return count。 } Doubly Linked Lists:counting Data Structure Software College Northeastern University template class Type int DblListType::First ( ) { if ( !IsEmpty ( ) ) //跳過表頭結(jié)點的第一個 { current = first→ rLink。 return 1。 } current = NULL。 return 0。 } template class Type int DblListType::Next ( ) { if ( current→ rLink == first ) { current = NULL。 return 0。 } current = current→ rLink。 return 1。 } Doubly Linked Lists:Changing Data Structure Software College Northeastern University template class Type int DblListType::Prior ( ) { if ( current→ lLink == first ) { current = NULL。 return 0。 } current = current→ lLink。 return 1。 } Doubly Linked Lists:Changing Data Structure Software College Northeastern University DLL pared to SLL ?Advantages: ?Can be traversed in either direction (may be essential for some programs) ?Some operations, such as deletion and inserting before a node, bee easier ?Disadvantages: ?Requires more space ?List manipulations are slower (because more links must be changed) ?Greater chance of having bugs (because more links must be manipulated) Data Structure Software College Northeastern University Problem: ?Inserting or Deleting use new and delete to obtain and release a piece of space ?dynamic management ?If operations of getting or returning are frequently, it may indicate more time required Two resolving way: ?Cursor Implementation of linked lists using static memory ?Initially We allocate many nodes to linked into spare lists Linked Lists: Cursor Implementation Data Structure Software College Northeastern University Tow important features of linked list: ?The data are stored in a collection of structure, each structure contains data and a pointer to the next structure ?A new structure can be obtained from the system?s global memory by a call to new and released by a call to delete Implementation: ?Have a global array of structure ?Array index can be used in place of an address Linked Lists: Cursor Implementation Data Structure Software College Northeastern University Global array of structures Address: Array index 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 0 define SpaceSize 1000 typedef struct Node{ ElementType data。 int next。 }Node,CursorSpace[Spacesize]。 Linked Lists: Cursor Implementation Data Structure Software College Northeastern University Simulation of malloc and free 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 0 Equivalent for malloc and free in cursor space array: ?Freelist: cells that are not in any lists ?Use cell 0 as a header of freelist ?A value of 0 for next is equivalent to NULL free list head Linked Lists: Cursor Implementation header Data Structure Software College Northeastern University freelist 1 2 3 4 5 6 7 8 9 10 0 0 1 2 3 4 5 6 7 8 9 10 freelist 2 header 1 3 4 5 6 7 8 9 10 0 0 1 2 3 4 5 6 7 8 9 10 Linked Lists: Cursor Implementation CursorAlloc to simulate malloc() Data Structure Software College Northeastern University int CursorAlloc(void) { //allocate a cell from freelist int p。 p = CursorSpace[0].next。 CursorSpace[0].next = CursorSpace[p].next。 return p。 } //end of CursorAlloc Linked Lists: Cursor Implementation Data Structure Software College Northeastern University freelist 8 header 2 c 3 b 4 e 5 g 6 f 7 d 1 9 10 0 0 1 2 3 4 5 6 7 8 9 10 freelist 4 header 2 c 3 b 5 e 8 g 6 f 7 d 1 9 10 0 0 1 2 3 4 5 6 7 8 9 10 Linked Lists: Cursor Implementation CursorFree to simulate Free() Data St