Question

C++ Data Structures

4. Write a client function that merges two instances of the Sorted List ADT using the following specification.

MergeLists(SortedType list1, SortedType list2, SortedType& result)

Function: Merge two sorted lists into a third sorted list.

Preconditions: list1 and list2 have been initialized and are sorted by key using function ComparedTo.

list1 and list2 do not have any keys in common.

Postconditions: result is a sorted list that contains all of the items from list1 and list2.

c. Write the function definition, using a linked implementation.

In order to verify that the code of MergeLists(SortedType list1, SortedType list2, SortedType& result) works, please integrate your code in the SortedType code below

**Use a driver to test your code.

//ItemType.h

#include <fstream>
const int MAX_ITEMS = 5;
enum RelationType {LESS, GREATER, EQUAL};

class ItemType
{
public:
ItemType();
RelationType ComparedTo(ItemType) const;
void Print(std::ostream&) const;
void Initialize(int number);
private:
int value;
};

#include "ItemType.h"
// Header file for Sorted List ADT.
struct NodeType;

class SortedType
{
public:
SortedType(); // Class constructor  
~SortedType(); // Class destructor

bool IsFull() const;
int GetLength() const;
void MakeEmpty();
ItemType GetItem(ItemType& item, bool& found);
void PutItem(ItemType item);
void DeleteItem(ItemType item);
void ResetList();
ItemType GetNextItem();

private:
NodeType* listData;
int length;
NodeType* currentPos;
};

struct NodeType
{
ItemType info;
NodeType* next;
};

SortedType::SortedType() // Class constructor
{
length = 0;
listData = NULL;
}

bool SortedType::IsFull() const
{
NodeType* location;
try
{
location = new NodeType;
delete location;
return false;
}
catch(std::bad_alloc exception)
{
return true;
}
}

int SortedType::GetLength() const
{
return length;
}

void SortedType::MakeEmpty()
{
NodeType* tempPtr;

while (listData != NULL)
{
tempPtr = listData;
listData = listData->next;
delete tempPtr;
}
length = 0;
}

ItemType SortedType::GetItem(ItemType& item, bool& found)
{
bool moreToSearch;
NodeType* location;

location = listData;
found = false;
moreToSearch = (location != NULL);

while (moreToSearch && !found)
{
switch(item.ComparedTo(location->info))
{
case GREATER: location = location->next;
moreToSearch = (location != NULL);
break;
case EQUAL: found = true;
item = location->info;
break;
case LESS: moreToSearch = false;
break;
}
}
return item;
}

void SortedType::PutItem(ItemType item)
{
NodeType* newNode;     // pointer to node being inserted
NodeType* predLoc;     // trailing pointer
NodeType* location;    // traveling pointer
bool moreToSearch;

location = listData;
predLoc = NULL;
moreToSearch = (location != NULL);

// Find insertion point.
while (moreToSearch)
{
switch(item.ComparedTo(location->info))
{
case GREATER: predLoc = location;
   location = location->next;
moreToSearch = (location != NULL);
break;
case LESS: moreToSearch = false;
break;
}
  
}

// Prepare node for insertion
newNode = new NodeType;
newNode->info = item;
// Insert node into list.
if (predLoc == NULL) // Insert as first
{
newNode->next = listData;
listData = newNode;
}
else
{
newNode->next = location;
predLoc->next = newNode;
}
length++;
}
void SortedType::DeleteItem(ItemType item)
{
NodeType* location = listData;
NodeType* tempLocation;

// Locate node to be deleted.
if (item.ComparedTo(listData->info) == EQUAL)
{
tempLocation = location;
listData = listData->next;   // Delete first node.
}
else
{
while (item.ComparedTo((location->next)->info) != EQUAL)
location = location->next;

// Delete node at location->next
tempLocation = location->next;
location->next = (location->next)->next;
}
delete tempLocation;
length--;
}

void SortedType::ResetList()
{
currentPos = NULL;
}

ItemType SortedType::GetNextItem()
{
ItemType item;
if (currentPos == NULL)
currentPos = listData;
item = currentPos->info;
currentPos = currentPos->next;
return item;

}

SortedType::~SortedType()
{
NodeType* tempPtr;

while (listData != NULL)
{
tempPtr = listData;
listData = listData->next;
delete tempPtr;
}

}

Answer 1

program code to copy

Driver.cpp


// Test driver
#include <iostream>
#include <fstream>
#include <string>
#include <cctype>
#include <cstring>

#include "sortedType.h"

using namespace std;
void PrintList(ofstream& outFile, SortedType& list);

int main()
{

  ifstream inFile;       // file containing operations
  ofstream outFile;      // file containing output
  string inFileName;     // input file external name
  string outFileName;    // output file external name
  string outputLabel;     
  string command;        // operation to be executed
  
  int number;
  ItemType item;
  SortedType list;
  bool found;
  int numCommands;


  // Prompt for file names, read file names, and prepare files
  cout << "Enter name of input command file; press return." << endl;
  cin  >> inFileName;
  inFile.open(inFileName.c_str());

  cout << "Enter name of output file; press return." << endl;
  cin  >> outFileName;
  outFile.open(outFileName.c_str());

  cout << "Enter name of test run; press return." << endl;
  cin  >> outputLabel;
  outFile << outputLabel << endl;

  inFile >> command;

  numCommands = 0;
  while (command != "Quit")
  { 
    outFile << command;
    if (command == "PutItem")
    {
      inFile >> number; 
      item.Initialize(number);
      list.PutItem(item);
      item.Print(outFile);
      outFile << " is inserted" << endl;
    }
    else if (command == "DeleteItem")
    {
      inFile >> number;
      item.Initialize(number);
      list.DeleteItem(item);
      item.Print(outFile);
      outFile << " is deleted" << endl;
    }
    else if (command == "GetItem")
    {
      inFile >> number;
      item.Initialize(number);
      list.GetItem(item, found);
      if (found)
        outFile << number << " found in list." << endl;
      else outFile << number  << " not in list."  << endl;  
    } 
    else if (command == "GetLength")  
      outFile << " Length is " << list.GetLength() << endl;
    else if (command == "IsFull")
      if (list.IsFull())
        outFile << "List is full." << endl;
      else outFile << "List is not full."  << endl;  
    else if (command == "MakeEmpty")
      list.MakeEmpty();
    else if (command == "PrintList")
      PrintList(outFile, list);
    else if (command == "MergeLists") 
        {
      
      SortedType testList, mergeTo;
      item.Initialize(2);
      testList.PutItem(item);
      item.Initialize(4);
      testList.PutItem(item);
      item.Initialize(8);
      testList.PutItem(item);
      item.Initialize(12);
      testList.PutItem(item);
      
      PrintList(outFile, testList);

      list.MergeLists(list, testList, mergeTo);
      outFile << "Merged Lists: ";
      PrintList(outFile, mergeTo);
      
    }
    else cout << " Command not recognized." << endl;
    numCommands++;
    cout <<  " Command number " << numCommands << " completed." 
         << endl;
    inFile >> command;   
  };
 
  cout << "Quit"  << endl << "Testing completed."  << endl;
  inFile.close();
  outFile.close();
  return 0;
}


void PrintList(ofstream& dataFile, SortedType& list)
// Pre:  list has been initialized.      
//       dataFile is open for writing.   
// Post: Each component in list has been written to dataFile.
//       dataFile is still open.         
{
  int length;
  ItemType item;

  list.ResetList();
  length = list.GetLength();
  for (int counter = 1; counter <= length; counter++)
  {
    ItemType item;
    item = list.GetNextItem();
    item.Print(dataFile);
  }
  dataFile << endl;
}

==============================================================

ItemType.cpp


// The following definitions go into file ItemType.cpp. 
#include <fstream>
#include <iostream>
#include "ItemType.h"

ItemType::ItemType()
{ 
  value = 0;
}

RelationType ItemType::ComparedTo(ItemType otherItem) const 
{
  if (value < otherItem.value)
    return LESS;
  else if (value > otherItem.value)
    return GREATER;
  else return EQUAL;
}

void ItemType::Initialize(int number) 
{
  value = number;
}

void ItemType::Print(std::ostream& out) const 
// pre:  out has been opened.
// post: value has been sent to the stream out.
{
  out << value;
}

============================================================================

ItemType.h

// The following declarations and definitions go into file 
// ItemType.h. 

#include <fstream>
const int MAX_ITEMS = 50;
enum RelationType  {LESS, GREATER, EQUAL};

class ItemType 
{ 
public:
  ItemType();
  RelationType ComparedTo(ItemType) const;
  void Print(std::ostream&) const;
  void Initialize(int number);
private:
  int value;
};
 
 ===================================================================================
 
 sortedType.cpp
 
 
 #include "sortedType.h"

struct NodeType
{
  ItemType info;
  NodeType* next;
};

SortedType::SortedType()  // Class constructor
{
  length = 0;
  listData = NULL;
}

bool SortedType::IsFull() const
{
  NodeType* location;
  try
  {
    location = new NodeType;
    delete location;
    return false;
  }
  catch(std::bad_alloc exception)
  {
    return true;
  }
}

int SortedType::GetLength() const
{
  return length;
}

void SortedType::MakeEmpty()
{
  NodeType* tempPtr;

  while (listData != NULL)
  {
    tempPtr = listData;
    listData = listData->next;
    delete tempPtr;
  }
  length = 0;
}

ItemType SortedType::GetItem(ItemType& item, bool& found)
{
  bool moreToSearch;
  NodeType* location;

  location = listData;
  found = false;
  moreToSearch = (location != NULL);

  while (moreToSearch && !found)
  {
    switch(item.ComparedTo(location->info))
    {
      case GREATER: location = location->next;
                    moreToSearch = (location != NULL);
                    break;
      case EQUAL:   found = true;
                    item = location->info;
                    break;
      case LESS:    moreToSearch = false;
                    break;
    }
  }
  return item;
}

void SortedType::PutItem(ItemType item)
{
  NodeType* newNode;    // pointer to node being inserted
  NodeType* predLoc;    // trailing pointer
  NodeType* location;   // traveling pointer
  bool moreToSearch;

  location = listData;
  predLoc = NULL;
  moreToSearch = (location != NULL);

  // Find insertion point.
  while (moreToSearch)
  {
    switch(item.ComparedTo(location->info))
    {
      case GREATER: predLoc = location;
                   location = location->next;
                    moreToSearch = (location != NULL);
                    break;
      case LESS:    moreToSearch = false;
                    break;
    }
    
  }

  // Prepare node for insertion
  newNode = new NodeType;
  newNode->info = item;
  // Insert node into list.
  if (predLoc == NULL)         // Insert as first
  {
    newNode->next = listData;
    listData = newNode;
  }
  else
  {
    newNode->next = location;
    predLoc->next = newNode;
  }
  length++;
}
void SortedType::DeleteItem(ItemType item)
{
  NodeType* location = listData;
  NodeType* tempLocation;

  // Locate node to be deleted.
  if (item.ComparedTo(listData->info) == EQUAL)
  {
    tempLocation = location;
    listData = listData->next;       // Delete first node.
  }
  else
  {
    while (item.ComparedTo((location->next)->info) != EQUAL)
      location = location->next;

    // Delete node at location->next
    tempLocation = location->next;
    location->next = (location->next)->next;
  }
  delete tempLocation;
  length--;
}

void SortedType::ResetList()
{
  currentPos = NULL;
} 

ItemType SortedType::GetNextItem()
{
  ItemType item;
  if (currentPos == NULL)
    currentPos = listData;
  item = currentPos->info; 
  currentPos = currentPos->next;
  return item;

} 

void SortedType::MergeLists(SortedType& list1, SortedType& list2, SortedType& result)
{
 
  int length = list1.GetLength();
  int i;
 
  list1.ResetList();
  for(i = 0; i < length; i++) 
  {
    result.PutItem(list1.GetNextItem());
  }
  
  length = list2.GetLength();
  list2.ResetList();
  
  for(i = 0; i < length; i++) 
  {
    result.PutItem(list2.GetNextItem());
  }
 
}

SortedType::~SortedType()
{
  NodeType* tempPtr;

  while (listData != NULL)
  {
    tempPtr = listData;
    listData = listData->next;
    delete tempPtr;
  }
}


=====================================================================

sortedType.h

#include "ItemType.h"
// Header file for Sorted List ADT.  
struct NodeType;

class SortedType
{
public:
  SortedType();     // Class constructor        
  ~SortedType();    // Class destructor

  bool IsFull() const;
  int  GetLength() const;
  void MakeEmpty();
  ItemType GetItem(ItemType& item, bool& found);
  void PutItem(ItemType item); 
  void DeleteItem(ItemType item);
  void ResetList();
  ItemType GetNextItem();
  void MergeLists(SortedType& list1, SortedType& list2, SortedType& result);

private:
  NodeType* listData;
  int length;
  NodeType* currentPos;
};


============================================================

listData.txt


GetLength
PutItem 5
PutItem 7
PutItem 6
PutItem 9
PrintList
MergeLists
PutItem 1
PrintList
MergeLists
GetItem 4
GetItem 5
GetItem 9
GetItem 10
IsFull
DeleteItem 5
IsFull
DeleteItem 1
DeleteItem 6
DeleteItem 9
PrintList
MakeEmpty
PrintList
Error
Quit

sample output