【正文】 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。 return 1。 } return count。 //從鏈中摘下 temp→ lLink→ rLink = current。 else { //非空表情形 current→ rLink =new DblNode ( value, current, current→ rLink )。 } return 0。 } Data Structure Software College Northeastern University template class Type int DblListType:: Find ( const Type amp。 } void Insert ( const Type amp。 } int Find ( const Type amp。 template class Type class DblNode { friend class DblListType。 } List ( const Type amp。 void Insert ( const Type amp。 Boolean IsEmpty ( ) { return first→ link == first。 } return retval。 current→ data。 return amp。 else return False。 ListNodeType *link。 p→ data。 //重新鏈接 Type value = new Type ( q→ data )。 ListNodeType *newnode = //創(chuàng)建結點 GetNode ( value, p→ link )。 int j = 0。 } Implementation of linked list(5) Data Structure Software College Northeastern University template class Type ListNodeType*List Type:: Find ( Type value ) { //在鏈表中從頭搜索其數據值為 value的結點 ListNodeType *p = first→ link。 first→ link = q→ link。 //返回下一結點地址 } Implementation of linked list(2) Data Structure Software College Northeastern University template class Type ListNodeType*ListType::GetNode ( const Type amp。 }。 } //構造函數 ~List ( )。 } //給出當前結點的下一結點地址 Data Structure Software College Northeastern University void InsertAfter ( ListNodeType *p )。 Deleting in a linked list with header Data Structure Software College Northeastern University Template of linked list(1) template class Type class List。 //free the node pointed by q return k。 return 0。 } return 1。 return 0。 int k = 0。 }。 class ListNode { friend class List。 }。 first = newnode； （ Before） （ After） first newnode newnode first Linked List:Inserting a new node(2) Data Structure Software College Northeastern University ? Case 2： insert in the middle of the list newnode→ link = p→ link。 } // Locate i1?th element if ( i0 || p == NULL amp。 } else { //else newnode→ link = p→ link。 k i1 ) { p = p→ link。 } if ( q == last ) last = p。 p→ link = q→ link。 //鏈表結點構造函數 ListNode ( const Typeamp。 item, ListNodeType *next )。 int Insert ( Type value, int i )。 if ( link == NULL ) return NULL。 delete first。 while ( p != NULL ) { //逐個結點檢測 p = p→ link。 // p 在搜索成功時返回找到的結點地址 // p 在搜索不成功時返回空值 } Implementation of linked list(6) Data Structure Software College Northeastern University template class Type ListNodeType *ListType :: Find ( int i ) { //在鏈表中從頭搜索第 i 個結點，不計頭結點 if ( i 1 ) return NULL。 } return p。 if ( p == NULL || p→ link == NULL ) return NULL。 } Implementation of linked list(8) Data Structure Software College Northeastern University template class Type Type *ListType::Get ( int i ) { //提取第 i 個結點的數據 ListNodeType *p = Find ( i )。 template class Type class ListNode { //表結點 friend class List Type。 l ) : list ( l ), current ( link ) { } //構造函數 : 引用鏈表 l, 表頭為當前結點 private: listType list。 } current current case 1 return True case 2 return False Template definition(4) Data Structure Software College Northeastern University template class Type ListNodeType* ListIteratorType :: Firster ( ) { //返回鏈表中頭結點的地址 current = 。amp。 //鏈表為空時返回 0 int *p= ( )。 } Implementation of Circular linked lists(1) Data Structure Software College Northeastern University template class Type class CircList { public: CircList ( Type value )。 } Boolean First ( )。 插入 Implementation of Circular linked lists(3) Data Structure Software College Northeastern University Variations of Circular Linked Lists ?Circular linked lists ?construct an empty Circular linked list CircList ( const Type amp。 p→ data != value ) p = p→ link。 ~DblList ( )。 int Next ( )。 Implementation of Doubly linked lists(3) Data Structure Software College Northeastern University Doubly linked lists:Searching Data Structure Software College Northeastern University Doubly Linked Lists:constructing template class Type DblListType::DblLIst ( Type uniqueVal ) { //雙向循環(huán)鏈表的構造函數 , 創(chuàng)建表頭結點 first = new DblNodeType ( uniqueVal )。 p→ data != target ) p = p→ rLink。 5. current→ rLink→ lLink = current。 1 2 Doubly Linked Lists:Deleting(1) Data Structure Software College Northeastern University template class Typ