數(shù)據(jù)結(jié)構(gòu)英文教學(xué)課件：chapter4 Array and Linked list exercise

1、Software College Northeastern UniversityData StructureSoftware College Northeastern Universityz Reverse a list List:Reverse()if L contains three nodes with data 1, 2, and 3 (read in order from the head of the list to the tail) then the Reverse list that is returned by the function should also contai

2、n three nodes with data 3, 2, and 1 (read in order from the head of the list).Data StructureSoftware College Northeastern UniversitySequence List Solutions Data StructureSoftware College Northeastern UniversitySequence List SolutionsData StructureSoftware College Northeastern UniversitySequence List

3、 SolutionstempData StructureSoftware College Northeastern UniversitySequence List SolutionstempData StructureSoftware College Northeastern UniversityData StructureSoftware College Northeastern UniversitySequence List SolutionsData StructureSoftware College Northeastern UniversityData StructureSoftwa

4、re College Northeastern UniversityTemplate of linked list(1)template class List;template class ListNode friend class List; Type data; /結(jié)點(diǎn)數(shù)據(jù)結(jié)點(diǎn)數(shù)據(jù) ListNode *link; /結(jié)點(diǎn)鏈接指針結(jié)點(diǎn)鏈接指針public: ListNode ( ); /鏈表結(jié)點(diǎn)構(gòu)造函數(shù)鏈表結(jié)點(diǎn)構(gòu)造函數(shù) ListNode ( const Type& item ); ListNode *NextNode ( ) return link; /給出當(dāng)前結(jié)點(diǎn)的下一結(jié)點(diǎn)地址給出當(dāng)前結(jié)點(diǎn)

5、的下一結(jié)點(diǎn)地址Data StructureSoftware College Northeastern Universityvoid InsertAfter ( ListNode *p ); /在當(dāng)前結(jié)點(diǎn)后插入結(jié)點(diǎn)在當(dāng)前結(jié)點(diǎn)后插入結(jié)點(diǎn)p ListNode *RemoveAfter ( ); /摘下當(dāng)前結(jié)點(diǎn)的下一結(jié)點(diǎn)摘下當(dāng)前結(jié)點(diǎn)的下一結(jié)點(diǎn);template class List ListNode *first, *last;public: ListNode *GetNode ( const Type& item, ListNode *next ); /創(chuàng)建數(shù)據(jù)為創(chuàng)建數(shù)據(jù)為item，指針為，指針為n

6、ext的新結(jié)點(diǎn)的新結(jié)點(diǎn)Template of linked list(2)Data StructureSoftware College Northeastern University List ( const Type & value ) last =first = new ListNode( value ); /構(gòu)造函數(shù)構(gòu)造函數(shù) List ( ); /析構(gòu)函數(shù)析構(gòu)函數(shù) void MakeEmpty ( ); /鏈表置空鏈表置空 int Length ( ) const; /求鏈表長(zhǎng)度求鏈表長(zhǎng)度 ListNode *Find ( Type value ); ListNode *Find ( i

7、nt i ); int Insert ( Type value, int i ); Type *Remove ( int i ); Type *Get ( int i ); void Reverse(); Template of linked list(3)Data StructureSoftware College Northeastern UniversityLinked List Solutions 15FirstLastData StructureSoftware College Northeastern UniversityInsert Before the first elemen

8、t 15FirstLastPData StructureSoftware College Northeastern UniversityLinked List Solutions 25FirstLastP1Data StructureSoftware College Northeastern UniversityLinked List Solutions 35FirstP21Data StructureSoftware College Northeastern UniversityLinked List Solutions 45FirstP321Data StructureSoftware College Northeastern UniversityLinked List Solutions 5FirstP4321Data StructureSoftware College Northeastern UniversityLinked List SolutionsFirstNULLP5432Data StructureSoftware College Northeastern Universitytemplate void List:Reverse( ) ListNode