CSE225L – Data Structures and Algorithms Lab

Lab 04
Unsorted List (array based)

In today’s lab we will design and implement the List ADT where the items in the list are unsorted.
UnsortedType.h template <class ItemType>
bool UnsortedType<ItemType>::GetNextItem(ItemType&
#ifndef UNSORTEDTYPE_H_INCLUDED item)
#define UNSORTEDTYPE_H_INCLUDED {
if(currentPos<length-1){
const int MAX_ITEMS = 5; currentPos++;
item = info [currentPos] ;
template <class ItemType> class UnsortedType return true;
{ }
public : return false;
UnsortedType(); }
void MakeEmpty(); template <class ItemType>
bool IsFull(); bool
int LengthIs(); UnsortedType<ItemType>::RetrieveItem(ItemType&
bool InsertItem(ItemType); item)
bool DeleteItem(ItemType); {
bool RetrieveItem(ItemType&); int location = 0;
void ResetList(); bool found = false;
bool GetNextItem(ItemType&); while ((location < length) && !found)
private: {
int length; if(item == info[location])
ItemType info[MAX_ITEMS]; {
int currentPos; found = true;
}; item = info[location];
#include "UnsortedType.tpp" }
#endif // UNSORTEDTYPE_H_INCLUDED else
{
UnsortedType.tpp location++;
}
#include "UnsortedType.h" }
return found;
template <class ItemType> }
UnsortedType<ItemType>::UnsortedType() template <class ItemType>
{ bool UnsortedType<ItemType>::InsertItem(ItemType
length = 0; item)
currentPos = -1; {
} if(!IsFull())
{
template <class ItemType> info[length] = item;
void UnsortedType<ItemType>::MakeEmpty() length++;
{ return true;
length = 0; }
} return false;
}
template <class ItemType> template <class ItemType>
bool UnsortedType<ItemType>::IsFull() bool UnsortedType<ItemType>::DeleteItem(ItemType
{ item)
return (length == MAX_ITEMS); {
} int flag = 0;
int location = 0;
template <class ItemType> while (location < length )
int UnsortedType<ItemType>::LengthIs() {
{ if(item == info[location])
return length; {
} flag = 1;
break;
template <class ItemType> }
void UnsortedType<ItemType>::ResetList() location++;
{ }
currentPos = -1; if(flag==1)
} {
info[location] = info[length - 1];
length--;
return true;
}
return false;
}
Tasks:
Generate the driver file (main.cpp) where you perform the following tasks. Note that you cannot make any change to
the header file or the source file.
Task No Operation to Be Tested and Description of Action Input Values Expected Output
• Create a list of integers
• Insert four items 5 7 6 9
• Print the list 5769
• Print the length of the list 4
• Insert one item 1
• Print the list 57691
• Retrieve 4 and print whether found or not Item is not found
• Retrieve 5 and print whether found or not Item is found
Task 1 • Retrieve 9 and print whether found or not Item is found
• Retrieve 10 and print whether found or not Item is not found
• Print if the list is full or not List is full
• Delete 5
• Print if the list is full or not List is not full
• Delete 1
• Print the list 769
• Delete 6
• Print the list 79
• Write a class studentInfo that represents
a student record. It must have variables to
store the student ID, student’s name and
student’s CGPA. It also must have a function
to print all the values.
• Modify UnsortedType class from class
template to a class that works with only
studentInfo type.
• Now modify DeleteItem() and
RetrieveItem() function such that items
can be deleted or retrieved using id of
studentInfo objects.
• Create a list of objects of class studentInfo.
Task 2
15234 Abdullah 2.6
13732 Muhammad 3.9
• Insert 5 student records 13569 Ali 1.2
15467 Saad 3.1
16285 Mahdi 3.1
• Delete the record with ID 15467
• Retrieve the record with ID 13569 and print
Item is found
whether found or not along with the entire 13569, Ali, 1.2
record
15234, Abdullah, 2.6
13732, Muhammad, 3.9
• Print the list
13569, Ali, 1.2
16285, Mahdi, 3.1