1Chapter4 Lists,Stacks,and Queues1.Lists2.Stacks3.Queues21.lists1.1 Definition of lists1.2 ADT of lists1.3 Basic Implementation of Lists1.3.1 Array-based List1.3.2 Linked List1.3.3 Comparison1.4 Free list1.5 Double Linked List3Example of lists 001高等数学樊映川机械工业出版社002理论力学罗远祥电子工业出版社003高等数学华罗庚高等教育出版社004线性代数栾汝书高等教育出版社Digital Library-List of booksMore example?students/airlines/songs/numbers/words.List of4Definition of lists(1)A list is a finite,ordered sequence of data items called elements.Notation of list:(a0,a1,an-1)5Definition of lists(2)The empty list contains no elements.The length of the list is the number of elements currently stored.The beginning of the list is called the head,the end of the list is called the tail.Sorted lists and unsorted lists Operation of List(1)Operations on list:Add/delete element anywhere,searchnextprevious.7Operation of List(2)The position of a list to execute operations is defined as a fence栅栏.For example:fence8Operation of List(3)Ex:insert(99)Result:remove()Result:read()Get 32.91.lists1.1 Definition of lists1.2 ADT of lists1.3 Basic Implementation of Lists1.3.1 Array-based List1.3.2 Linked List1.3.3 Comparison1.4 Free list1.5 Double Linked List10List ADTtemplate class List public:virtual void clear()=0;virtual bool setPos(int pos)=0;virtual bool insert(const Elem&)=0;virtual bool append(const Elem&)=0;virtual bool remove(Elem&)=0;virtual bool getValue(Elem&)const=0;virtual void setStart()=0;virtual void setEnd()=0;virtual void prev()=0;virtual void next()=0;virtual int leftLength()const=0;virtual int rightLength()const=0;virtual void print()const=0;11List ADT Examples（1）Insert/remove/getvalue:MyList:MyList.insert(99);Result:MyList.remove(element);Result:element=99.MyList.getvalue(element);element=32.12List ADT Examples（2）setStart/setEnd/next/prevMyList:MyList.setStart();Result:MyList.setEnd();Result:MyList.prev();Result:MyList.next();Result:13List ADT Examples（3）Iterate through the whole list:for(MyList.setStart();MyList.getValue(it);MyList.next()DoSomething(it);it=12it=32it=15over14 Search for an element/Return true iff K is in listbool find(List&L,int K)int it;for(L.setStart();L.getValue(it);L.next()if(K=it)return true;/Found it return false;/Not foundList ADT Examples(4)151.lists1.1 Definition of lists1.2 ADT of lists1.3 Basic Implementation of Lists1.3.1 Array-based List1.3.2 Linked List1.3.3 Comparison1.4 Free list1.5 Double Linked ListData Storage of a ListList:(e1,e2,e3,e4,e5)e1e2e3e4e5e1e2e3e4e5array based listlinked list171.lists1.1 Definition of lists1.2 ADT of lists1.3 Basic Implementation of Lists1.3.1 Array-based List1.3.2 Linked List1.3.3 Comparison1.4 Free list1.5 Double Linked List18Array-Based List Class(1)template /Array-based listclass AList:public List private:Elem*listArray;/Array holding list int maxSize;/Maximum size of list int listSize;/Actual elem count int fence;/Position of fencefencelistArraylistsizemaxsize19Array-Based List Class(2)public:AList(int size=DefaultListSize)maxSize=size;listSize=fence=0;listArray=new ElemmaxSize;AList()delete listArray;void clear()delete listArray;listSize=fence=0;listArray=new ElemmaxSize;fencelistArraymaxsizelistSize20Array-Based List Class(3)void setStart()fence=0;void setEnd()fence=listSize;void prev()if(fence!=0)fence-;void next()if(fence=0)&(pos=0)&(pos=listSize);/get the first element after the fencebool getValue(Elem&it)const if(rightLength()=0)return false;else it=listArrayfence;return true;fencelistArraylistsize(1)22Array-Based List Class(5)-Insert Array-Based List Class(6)-Insert/Insert at front of right partitiontemplate bool AList:insert(const Elem&item)if(listSize=maxSize)return false;/Shift Elems up to make room for(int i=listSize;ifence;i-)listArrayi=listArrayi-1;012345listSizefenceInsert itemmaxsizelistArrayArray-Based List Class(6)-Insert/Insert at front of right partitiontemplate bool AList:insert(const Elem&item)if(listSize=maxSize)return false;/Shift Elems up to make room for(int i=listSize;ifence;i-)listArrayi=listArrayi-1;listArrayfence=item;listSize+;/Increment list size return true;012345listSizefenceInsert itemitemmaxsizelistArray(n)25Array-Based List Class(7)-append/Append Elem to end of the listtemplate bool AList:append(const Elem&item)if(listSize=maxSize)return false;listArraylistSize+=item;return true;listSizefenceappend itemmaxsizelistArray26Array-Based List Class(8)-remove/Remove and return first Elem in right/partitiontemplate bool AList:remove(Elem&it)if(rightLength()=0)return false;it=listArrayfence;/Copy Elem for(int i=fence;ilistSize-1;i+)listArrayi=listArrayi+1;123456listSizefenceremovemaxsizelistArray27Array-Based List Class(8)-remove/Remove and return first Elem in right/partitiontemplate bool AList:remove(Elem&it)if(rightLength()=0)return false;it=listArrayfence;/Copy Elem for(int i=fence;ilistSize-1;i+)listArrayi=listArrayi+1;listSize-;/Decrement size return true;12456listSizefenceremovemaxsizelistArray(n)281.lists1.1 Definition of lists1.2 ADT of lists1.3 Basic Implementation of