Download as PPT, PDF, TXT or read online from Scribd
Download as ppt, pdf, or txt
You are on page 1/ 30
Unsorted Lists
CS 302 – Data Structures
Sections 3.1 & 3.2 What is a list? • A list is a homogeneous collection of elements. • Linear relationship between elements: (1) Each element except the first one has a unique predecessor. (2) Each element except the last one has a unique successor. Unsorted list • A list in which data items are placed in no particular order.
Sorted list • A list in which data items are placed in a particular order. • Key: a member of the class whose value is used to determine the order of the items in the list. Unsorted List Implementation template<class ItemType> class UnsortedType { public: currentPos void MakeEmpty(); bool IsFull() const; int LengthIs() const; void RetrieveItem(ItemType&, bool&); void InsertItem(ItemType); void DeleteItem(ItemType); void ResetList(); bool IsLastItem() void GetNextItem(ItemType&); private: int length; ItemType info[MAX_ITEMS]; int currentPos; }; Length: length of the list (i.e., different from array size!) Unsorted List Implementation template<class ItemType> (cont.) void UnsortedType<ItemType>::MakeEmpty() { length = 0; } O(1)
template<class ItemType> bool UnsortedType<ItemType>::IsFull() const { return (length == MAX_ITEMS); O(1) } Unsorted List Implementation (cont.) template<class ItemType> int UnsortedType<ItemType>::LengthIs() const { return length; O(1) } RetrieveItem (ItemType& item, Boolean& found) • Function: Retrieves list element whose key matches item's key (if present). • Preconditions: (1) List has been initialized, (2) Key member of item has been initialized.
• Postconditions: (1) If there is an element someItem
whose key matches item's key, then found=true and item is a copy of someItem; otherwise, found=false Item is in the list Item is NOT in the list
Retrieve Judy Unsorted List Implementation (cont.) template<class ItemType> void UnsortedType<ItemType>::RetrieveItem (ItemType& item, bool& found) { int location = 0; found = false; while( (location < length) && !found) if (item == info[location]) { O(N) found = true; item = info[location]; } else location++; Client/User of the class } must overload “==“ InsertItem (ItemType item) • Function: Adds item to list
• Preconditions: (1) List has been initialized, (2) List is not full, (3) item is not in list (i.e., no duplicates)
• Postconditions: item is in list.
InsertItem (ItemType item) (cont’d) Insert George Unsorted List Implementation (cont.)
GetNextItem, the list should not be modified (i.e., adding/deleting elements) Unsorted List Implementation (cont.)
template<class ItemType> bool UnsortedType<ItemType>::IsLastItem () { return (currentPos == length-1); O(1) } Exercise 3 (page 185): Write a client function that splits an unsorted list into two unsorted lists using the following specification.
SplitLists (UnsortedType list, ItemType item,
UnsortedType& list1, UnsortedType& list 2)
Function: Divides list into two lists according to the key of
item. Preconditions: list has been initialized and is not empty. Postconditions: list1 contains all the items of list whose keys are less than or equal to item’s key; list2 contains all the items of list whose keys are greater than item’s key; list remains unchanged. void SplitLists(const UnsortedType& list, ItemType item, UnsortedType& list1, UnsortedType& list2) { ItemType listItem;
list1.MakeEmpty(); list2.MakeEmpty(); list.ResetList(); What is the time while (!list.IsLastItem()) { complexity list.GetNextItem(listItem); using big-O? if(listItem > item) list2.InsertItem(listItem); else O(N) list1.InsertItem(listItem); } } Exercise: Write a client function that merges two unsorted lists into another unsorted list using the following specification.
Function: Merge list1 and list2 into another list.
Preconditions: list1 and list2 have been initialized. Postconditions: list contains all the items of list1 and list2; list is not allowed to contain duplicates. void MergeLists(UnsortedType list1, UnsortedType list2, UnsortedType& list) { ItemType item; bool found;
cout << “Not enough space to merge the lists” << endl; } What is the time complexity using big-O? O(N1+N2(N1+N2))=O(N1N2+(N2)2) list2.ResetList(); while (!list2.IsLastItem() && (!list.IsFull())) { list2.GetNextItem(item); list1.RetrieveItem(item, found); if(!found) list.InsertItem(item) more efficient! }
if(list.IsFull() && (!list2.IsLastItem()))
cout << “Not enough space to merge the lists” << endl; } What is the time complexity using big-O? O(N1+N2N1)=O(N1N2)
