【正文】 return 1。 } } Doubly Linked Lists:Deleting(2) Data Structure Software College Northeastern University template class Type int DblListType::Length ( ) const { //求雙向循環(huán)鏈表的長(zhǎng)度 (不計(jì)表頭結(jié)點(diǎn) ) DblNodeType * p = first→ rLink。 4. current = current→ rLink。 }。 template class Type class DblList { public: DblList ( Type uniqueVal )。 }。 CircListNodeType *link。 } } current list with header Template definition(5) Data Structure Software College Northeastern University template class Type Type* ListIteratorType :: Next ( ) { //返回鏈表中當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)的地址 if ( current != NULL amp。 template class Type class ListIterator { public: ListIterator ( const ListType amp。value。 j++。 //檢測(cè)指針 p指示第一個(gè)結(jié)點(diǎn) int count = 0。 } Implementation of linked list(1) Data Structure Software College Northeastern University template class Type ListNodeType *ListNodeType::RemoveAfter ( ) { //摘下當(dāng)前結(jié)點(diǎn)的下一結(jié)點(diǎn) ListNodeType *tempptr = link。 public: ListNodeType *GetNode ( const Typeamp。 Data Structure Software College Northeastern University q = p→ link。amp。 k++。 class List { public: ……… private: ListNode *first, *last。 ListNode *first, *last。 } ListNode *newnode= new ListNode(x, NULL)。 } if ( i == 0 ) { //delete the first q = first。 template class Type class ListNode { friend class ListType。 //析構(gòu)函數(shù) void MakeEmpty ( )。 item, ListNodeType *next = NULL ) { ListNodeType *newnode = new ListNodeType ( item )。 //檢測(cè)指針 p 指示第一個(gè)結(jié)點(diǎn) while ( p != NULL amp。 if ( p→ link == NULL ) last = newnode。 } Implementation of linked list(8) Data Structure Software College Northeastern University Array versus Linked Lists ?Linked lists are more plex to code and management than arrays, but they have some distinct advantages. ?Dynamic: a linked list can easily grow and shrink in size. We don?t need to know how many nodes will be in the list. They are created in memory as needed. In contrast, the size of a C array is fixed at pilation time. ?Easy and fast insertions and deletions To insert or delete an element in an array, we need to copy to temporary variables to make room for new elements or close the gap caused by deleted elements. With a linked list, no need to move other nodes. Only need to reset some pointers. Data Structure Software College Northeastern University Arrays versus linked lists ?Space (storage) considerations ?A linked list requires pointers to nodes ?An array requires the maximum number of elements to be known in advance. If that maximum is not required, space is wasted at the end of the array. Data Structure Software College Northeastern University Arrays versus linked lists ?Time considerations ?Most methods in a linked list require more statements than those in an array, which may indicate more time required ?Arrays are quicker at finding and altering ?in the middle? ?Linked lists are quicker at additions and removals ?in the middle? Data Structure Software College Northeastern University Iterator class of list ?Iterator class of list is used to traverse nodes of list. ?priciple： ? Iterator class is friend of List and ListNode ? Iterator refer to the nodes of list。 } current current case 1 return True case 2 return False Template definition(3) Data Structure Software College Northeastern University template class Type Boolean ListIteratorType::NextNotNull ( ) { //檢查鏈表中下一元素是否非空 if ( current != NULL amp。 } else { current = NULL。 } Boolean Find ( const Type amp。 value ) { last =first = new ListNodeType( value )。 target )。 target ) { //在雙向循環(huán)鏈表中搜索含 target的結(jié)點(diǎn)， //搜索成功返回 1，否則返回 0。 current = current→ rLink。 } Doubly Linked Lists:counting Data Structure Software College Northeastern University template class Type int DblListType::First ( ) { if ( !IsEmpty ( ) ) //跳過表頭結(jié)點(diǎn)的第一個(gè) { current = first→ rLink。 p = CursorSpace[0].next。 } current = current→ rLink。 //下一結(jié)點(diǎn) current→ lLink = temp→ lLink。 return 1。 int operator ! ( ) { return current != NULL。 // p 在搜索成功時(shí)返回找到的結(jié)點(diǎn)地址 // p 在搜索不成功時(shí)返回空值 } Linked Lists: Searching in a CLL Data Structure Software College Northeastern University Variations of Linked Lists ?Doubly linked lists ?Each node points to not only successor but the predecessor ?There are two NULL: at the first and last nodes in the list ?Advantage: given a node, it is easy to visit its predecessor. Convenient to traverse lists backwards Head A ? B ? Data Structure Software College Northeastern University p == p→ lLink→ rLink == p→ rLink→ lLink Non_empty list empty list Doubly linked lists Data Structure Software College Northeastern University template class Type class DblList。 Implementation of Circular linked lists(2) Data Structure Software College Northeastern University Boolean Prior ( )。 //累加 p= ( )。 } current list with header Template definition(5) Data Structure Software College Northeastern University template class Type Type * ListIteratorType :: First ( ) { //返回鏈表中第一個(gè)元素的地址 if ( → link != NULL ){ current = link。 public: ……… private: Type data。 p→ link = q→ link。 // i 應(yīng) ? 0 ListNodeType *p = first→ link。 while ( first→ link != NULL ) { q = first→ link。 Type *Get ( int i )。 ListNodeType *NextNode ( ) { return link。 delete q。 p→ link = newnode。 p→ link = last = newn