数据结构英文教学课件：chapter4 Array and Linked list exercise

1、Data StructureSoftware College Northeastern UniversityArray and Linked listData StructureSoftware College Northeastern UniversityProgramming Exercise 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 li

2、st that is returned by the function should also contain three nodes with data 3, 2, and 1 (read in order from the head of the list).Data StructureSoftware College Northeastern UniversitySequence List Solutionstemplate class SeqList Type *data; int MaxSize; int last; /index of the last elementpublic:

3、 SeqList ( int MaxSize = defaultSize ); SeqList ( ) delete data; int Length ( ) const return last+1; int Find ( Type & x ) const; void Reverse(); Data StructureSoftware College Northeastern UniversitySequence List Solutions12345140124lastData StructureSoftware College Northeastern UniversitySequence

4、 List Solutions1234514012454321140124tempData StructureSoftware College Northeastern UniversitySequence List Solutions5432114012454321140124tempData StructureSoftware College Northeastern University template void SeqList:Reverse() /Reverse the list Type *temp; temp = new Typelast+1; if(temp != NULL)

5、 for(int i=0,j=last;i=last;i+,j-) *(temp+i)=*(data+j) for(int i=0;i=last;i+) *(data+i)=*(temp+j) delete temp; Data StructureSoftware College Northeastern UniversitySequence List Solutions12345140124Data StructureSoftware College Northeastern University template void SeqList:Reverse() /Reverse the li

6、st int halflength = (last+1)/2; Type temp; for(int i=0;j=last;ihalflength;i+,j-) temp = *(data+i); *(data+i) = *(data+j); *(data+j) = temp; Data StructureSoftware College Northeastern UniversityTemplate of linked list(1)template class List;template class ListNode friend class List; Type data; /结点数据

7、ListNode *link; /结点链接指针public: ListNode ( ); /链表结点构造函数 ListNode ( const Type& item ); ListNode *NextNode ( ) return link; /给出当前结点的下一结点地址Data StructureSoftware College Northeastern Universityvoid InsertAfter ( ListNode *p ); /在当前结点后插入结点p ListNode *RemoveAfter ( ); /摘下当前结点的下一结点;template class List Lis

8、tNode *first, *last;public: ListNode *GetNode ( const Type& item, ListNode *next ); /创建数据为item，指针为next的新结点Template of linked list(2)Data StructureSoftware College Northeastern University List ( const Type & value ) last =first = new ListNode( value ); /构造函数 List ( ); /析构函数 void MakeEmpty ( ); /链表置空

9、int Length ( ) const; /求链表长度 ListNode *Find ( Type value ); ListNode *Find ( int 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 S

10、tructureSoftware College Northeastern UniversityInsert Before the first element 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 SolutionsFirstNULLP54321Data StructureSoftware College Northeastern Universitytempl