【正文】 class List { public: ……… private: ListNode *first, *last。 }。 when index = 2, insert the node after the first element, and so on) ? If the insertion is successful, return 1. Otherwise, return 0. (If index is 1 or length+1 of the list, the insertion will fail.) ? Steps 1. Locate i1?th element 2. Allocate memory for the new node 3. Point the new node to its successor 4. Point the new node?s predecessor to the new node newNode i?th element Data Structure Software College Northeastern University ?Insert position ? Case 1： insert in front of the first node newnode→ link = first 。 int k = 0。 k++。 return 0。 first = newnode。 } return 1。amp。 return 0。 p→ link = q→ link。 //free the node pointed by q return k。 Data Structure Software College Northeastern University q = p→ link。 Deleting in a linked list with header Data Structure Software College Northeastern University Template of linked list(1) template class Type class List。 //結(jié)點鏈接指針 public: ListNode ( )。 } //給出當前結(jié)點的下一結(jié)點地址 Data Structure Software College Northeastern University void InsertAfter ( ListNodeType *p )。 public: ListNodeType *GetNode ( const Typeamp。 } //構(gòu)造函數(shù) ~List ( )。 ListNodeType *Find ( int i )。 }。 } Implementation of linked list(1) Data Structure Software College Northeastern University template class Type ListNodeType *ListNodeType::RemoveAfter ( ) { //摘下當前結(jié)點的下一結(jié)點 ListNodeType *tempptr = link。 //返回下一結(jié)點地址 } Implementation of linked list(2) Data Structure Software College Northeastern University template class Type ListNodeType*ListType::GetNode ( const Type amp。 } template class Type ListType :: ~List ( ){ //析構(gòu)函數(shù) (鏈表的公共操作 ) MakeEmpty ( )。 first→ link = q→ link。 //檢測指針 p指示第一個結(jié)點 int count = 0。 } Implementation of linked list(5) Data Structure Software College Northeastern University template class Type ListNodeType*List Type:: Find ( Type value ) { //在鏈表中從頭搜索其數(shù)據(jù)值為 value的結(jié)點 ListNodeType *p = first→ link。 return p。 int j = 0。 j++。 ListNodeType *newnode = //創(chuàng)建結(jié)點 GetNode ( value, p→ link )。 } Implementation of linked list(7) Data Structure Software College Northeastern University template class Type Type *ListType::Remove ( int i ) { //從鏈表中刪去第 i 個結(jié)點 ListNodeType *p = Find (i1), *q。 //重新鏈接 Type value = new Type ( q→ data )。value。 p→ data。 template class Type class ListIterator。 ListNodeType *link。 template class Type class ListIterator { public: ListIterator ( const ListType amp。 else return False。 else return False。 return amp。 } } current list with header Template definition(5) Data Structure Software College Northeastern University template class Type Type* ListIteratorType :: Next ( ) { //返回鏈表中當前結(jié)點的下一個結(jié)點的地址 if ( current != NULL amp。 current→ data。l ) { ListIteratorint li ( l )。 } return retval。 CircListNodeType *link。 Boolean IsEmpty ( ) { return first→ link == first。 void Firster ( ) { current = first。 void Insert ( const Type amp。 }。 } List ( const Type amp。amp。 template class Type class DblNode { friend class DblListType。 template class Type class DblList { public: DblList ( Type uniqueVal )。 } int Find ( const Type amp。 } int First ( )。 } void Insert ( const Type amp。 }。 } Data Structure Software College Northeastern University template class Type int DblListType:: Find ( const Type amp。amp。 } return 0。 4. current = current→ rLink。 else { //非空表情形 current→ rLink =new DblNode ( value, current, current→ rLink )。 2. current→ lLink→ rLink = current→ rLink。 //從鏈中摘下 temp→ lLink→ rLink = current。 } } 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。 } return count。 return 0。 return 1。 return 1。 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。 } //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