资源描述
Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Implementing an Unsorted List as a Linked Structure,CS 308 Data Structures,1,Implementing an Unsorted List as a Linked Structure,Allocate memory for each new element dynamically,Link the list elements together,Use two pointers,currentPos,and,listData, to mark the current position in the list and the beginning of the list,Use an integer variable,length, to store the current length of the list.,2,Implementing an Unsorted List as a Linked Structure (cont.),3,Unsorted List Class Specification,template ,struct NodeType;,template,class UnsortedType ,public:,UnsortedType();,UnsortedType();,void MakeEmpty();,bool IsFull() const;,int LengthIs() const;,void RetrieveItem(ItemType,void InsertItem(ItemType);,void DeleteItem(ItemType);,void ResetList();,bool IsLastItem() const;,void GetNextItem(ItemType,private:,int length;,NodeType* listData;,NodeType* currentPos;,;,4,Function RetrieveItem,5,Function RetrieveItem (cont.),template,void UnsortedType:RetrieveItem,(ItemType& item, bool& found),NodeType* location;,location = listData;,found = false;,while( (location != NULL) & !found) ,if(item = location-info) ,found = true;,item = location-info;,else,location = location-next;,6,Function InsertItem,Just insert the item at the beginning of the list,7,Function InsertItem (cont.),template ,void UnsortedType:InsertItem (ItemType newItem),NodeType* location;,location = new NodeType;,location-info = newItem;,location-next = listData;,listData = location;,length+;,8,Function DeleteItem,Find the item first,In order to delete it, we must change the pointer in the,previous,node!,9,Function DeleteItem (cont.),Solution: compare,one item ahead,(,(location-next)-info),) !,Deleting the first node is a special case .,10,Important:,this implementation will work without problems ONLY if the item to be deleted IS in the list ! (precondition),11,Function DeleteItem (cont.),template ,void UnsortedType:,DeleteItem,(ItemType item),NodeType* location = listData;,NodeType* tempLocation;,if(item = listData-info) ,tempLocation = location;,listData = listData-next;,/ delete first node,else ,while(!(item = (location-next)-info),location = location-next;,/ delete node at location-next,tempLocation=location-next;,location-next = (location-next)-next;,delete tempLocation;,length-;,12,Other UnsortedList functions,template,UnsortedType:,UnsortedType(),length = 0;,listData = NULL;,template,void UnsortedType:,MakeEmpty(),NodeType* tempPtr;,while(listData != NULL) ,tempPtr = listData;,listData = listData-next;,delete tempPtr;,length=0;,13,Other UnsortedList functions,(cont.),template,UnsortedType:,UnsortedType(),MakeEmpty();,template,bool UnsortedType:,IsFull() const,NodeType* ptr;,ptr = new NodeType;,if(ptr = NULL),return true;,else ,delete ptr;,return false;,14,template,int UnsortedType:,LengthIs() const,return length;,template,int UnsortedType:,ResetList(),currentPos = listData;,template,void UnsortedType:,GetNextItem(ItemType& item),item = currentPos-info;,currentPos = currentPos-next;,template,bool UnsortedType:,IsLastItem() const,return(currentPos = NULL);,Other UnsortedList functions,(cont.),15,Write a client function that merges two instances of the Unsorted List ADT using the following specification.,MergeLists(UnsortedType list1, UnsortedType list2, UnsortedType& result),Function,: Merges two unsorted lists into a third unsorted list (no duplicates).,Preconditions,: list1 and list2 have been initialized.,Postconditions,: result is an unsorted list that contains all of the items from list1 and list2.,16,ItemType item;,bool found;,list1.Reset();,list2.Reset();,result.MakeEmpty();,while ( !list1.IsLastItem() ); ,list1.GetNextItem(item);,if ( !result.IsFull() ),result.InsertItem(item);,while ( !list2.IsLastItem() ); ,list2.GetNextItem(item);,list1.RetrieveItem(item, found);,if ( !found ),if ( !result.IsFull() ),result.InsertItem(item);,17,Comparing unsorted list implementations,Big-O Comparison of Unsorted List Operations,Operation,Array Implementation,Linked Implementation,Class constructor,O(1),O(1),Destructor,O(1),O(N),MakeEmpty,O(1),O(N),IsFull,O(1),O(1),LengthIs,O(1),O(1),ResetList,O(1),O(1),GetNextItem,O(1),O(1),RetrieveNextItem,O(N),O(N),InsertItem,O(1),O(1),DeleteItem,O(N),O(N),18,Exercises,9, 10, 11, 15 - 18,19,
展开阅读全文