Data Structures. Write a third implementation of the Bag ADT in Putty and Unix. The implementation uses a linked data structure, however instead of using pointers, use an array of cells to represent the available memory for allocating new links in the chain. This representation uses an array of structs of the form: template

struct Cell {

T item;

int next;

}

Each cell in the array is analogous to a Node in a linked list, but instead of a pointer to the next Node, a Cell has an index into the array to indicate the next Cell in the chain. The main part of this is to manage the array of Cells to keep track of which indices of the array contain currently used Cells and which contain free Cells. The implementation must use this method:

The header file is started and is stored in ArrayLinkedBag.cpp. Any private data members and methods should be added. There is also a test_driver.cpp file that contains code to test all of the BagInterface methods as follows. The rest of the files are at https://github.com/jonjones22/project2.

-------------------------------------------------------------------------------------------------------------------------------------------------------------------------

ArrayLinkedBag.cpp

/** Implementation file for the class ArrayLinkedBag. @file ArrayLinkedBag.cpp */

#include "ArrayLinkedBag.h" #include

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------

test_driver.cpp

// Created by Frank M. Carrano and Tim Henry. // Copyright (c) 2013 __Pearson Education__. All rights reserved.

/** @file test_driver.cpp */ #include "BagInterface.h" #include "ArrayBag.h" #include "ArrayLinkedBag.h" #include "LinkedBag.h" #include #include #include

void displayBag(BagInterface<:string>* bagPtr) { std::cout getCurrentSize() bagItems = bagPtr->toVector(); std::sort(bagItems.begin(), bagItems.end()); int numberOfEntries = bagItems.size(); for (int i = 0; i

void bagTester(BagInterface<:string>* bagPtr) { std::cout isEmpty()

std::string items[] = {"one", "two", "three", "four", "five", "one"}; std::cout add(items[i]); } // end for

displayBag(bagPtr);

std::cout isEmpty()

std::cout getCurrentSize()

std::cout add("extra")

std::cout contains("three") contains("ten") getFrequencyOf("one") remove("one") getFrequencyOf("one") remove("one") remove("one")

displayBag(bagPtr);

std::cout clear();

std::cout isEmpty()

int main(int argc, char* argv[]) { if (argc != 2) { std::cout * bagPtr = NULL; std::string choice(argv[1]); if (choice == "ARRAY") { bagPtr = new ArrayBag<:string>(); } else if (choice == "LINKED") { bagPtr = new LinkedBag<:string>(); } else if (choice == "ARRAY_LINKED") { bagPtr = new ArrayLinkedBag<:string>(); } else { std::cout

std::cout

return 0; } ---------------------------------------------------------------------------------------------------------------------------------------------------------------------

FIGURE 4-11 (a) An array-based implementation of a linked chain; (b) after inserting "D" at the beginning of the chain; (c) after deleting "B" (a) item next (b) item next (c) item next 0 B 1 | 1 0 4 Linked chain 1 E 2 1 E 2 1 E 2 2 J -1 2 J -1 2 J -1 3 4 3 D 0 3D 1 5 4 5 4 5 6 5 6 5 6 Free list 6 7 6 7 6 7 -1 -1 -1 3 3 3 0 head free head free head free FIGURE 4-11 (a) An array-based implementation of a linked chain; (b) after inserting "D" at the beginning of the chain; (c) after deleting "B" (a) item next (b) item next (c) item next 0 B 1 | 1 0 4 Linked chain 1 E 2 1 E 2 1 E 2 2 J -1 2 J -1 2 J -1 3 4 3 D 0 3D 1 5 4 5 4 5 6 5 6 5 6 Free list 6 7 6 7 6 7 -1 -1 -1 3 3 3 0 head free head free head free