Question

/*
Array List

Modified from CS2 Software Design & Data Structures by Cliff Shaffer. OpenDSA

*/
#ifndef ALIST_H_RVC
#define ALIST_H_RVC
#include "List.h"

template // Array-based list implementation

class AList : public List {

private:
   ListItemType* listArray; //Dynamic Array (pointer)
   int listSize; //Current number of list items
   int curr; //Position of current element
   int MAX_SIZE;

public:

   //Constructors

   AList() {
       MAX_SIZE = 1000; // arbitrary
       listArray = new ListItemType[MAX_SIZE];
       clear();
   } //end constructor

   // Create a new list element with maximum size "MAX_SIZE" as a parameter
   AList(int m) {
       MAX_SIZE = m;
       listArray = new ListItemType[MAX_SIZE];
       clear();
   } //end constructor

   bool isEmpty() const {
       return listSize == 0;
   }

   void clear() { // Reinitialize the list
       listSize = curr = 0; // Simply reinitialize values
   }

   // Insert "it" at current position
   // return value indicates success

   bool insert(const ListItemType& it) {
       if (listSize >= MAX_SIZE) return false;

       for (int i = listSize; i > curr; i--) //Shift elements up
           listArray[i] = listArray[i - 1]; //to make room
       listArray[curr] = it;
       listSize++; //Increment list size
       return true;
   }

   // Append "it" to list
   bool append(const ListItemType& it) {
       cout << "\n\n******* This is to be completed for the lab\n\n";
       return true;
   }

   // Remove and return the current element
   ListItemType remove() {
       if (curr == listSize) curr--;

       ListItemType it = listArray[curr]; // Copy the element
       for (int i = curr; i < listSize - 1; i++) // Shift them down
           listArray[i] = listArray[i + 1];
       listSize--; // Decrement size
       if (curr > listSize) {
           curr = listSize;
       }
       return it;
   }

   void moveToStart() { curr = 0; } // Set to front
   void moveToEnd() { curr = listSize; } // Set to end
   void prev() { if (curr != 0) curr--; } // Move left
   void next() { if (curr < listSize) curr++; } // Move right
   int length() const { return listSize; } // Return list size
   int currPos() const { return curr; } // Return current position

                                           // Set current list position to "pos"
   bool moveToPos(int pos) {
       if ((pos < 0) || (pos > listSize)) return false;
       curr = pos;
       return true;
   }

   // Return true if current position is at end of the list5
   bool isAtEnd() const { return curr == listSize; }

   // Return the current element
   ListItemType getValue() const {
       return listArray[curr];
   }

   bool find(const ListItemType& it) {
       ListItemType curr =
       cout << "\n\n******* This is to be completed for the assignment\n\n";
       return true;
   }

   bool findNext(const ListItemType& it) {
       cout << "\n\n******* This is to be completed for the assignment\n\n";
       return true;
   }

   int count(const ListItemType& it) {
       cout << "\n\n******* This is to be completed for the assignment\n\n";
       return 0;
   }

};

#endif

Write the code for the find, findNext and count method in AList.h. This is an Array based list implementation problem in ADT, where we discuss about stacks

Answer 1

/*
Array List

Modified from CS2 Software Design & Data Structures by Cliff Shaffer. OpenDSA

*/
#ifndef ALIST_H_RVC
#define ALIST_H_RVC
#include "List.h"

template <class ListItemType>

class AList : public List

{

private:

   ListItemType* listArray; //Dynamic Array (pointer)

   int listSize; //Current number of list items

   int curr; //Position of current element

   int MAX_SIZE;

public:

   //Constructors

   AList() {

          MAX_SIZE = 1000; // arbitrary

          listArray = new ListItemType[MAX_SIZE];

          clear();

   } //end constructor

   // Create a new list element with maximum size "MAX_SIZE" as a parameter

   AList(int m) {

          MAX_SIZE = m;

          listArray = new ListItemType[MAX_SIZE];

          clear();

   } //end constructor

   bool isEmpty() const {

          return listSize == 0;

   }

   void clear() { // Reinitialize the list

          listSize = curr = 0; // Simply reinitialize values

   }

   // Insert "it" at current position

     // return value indicates success

   bool insert(const ListItemType& it) {

          if (listSize >= MAX_SIZE) return false;

          for (int i = listSize; i > curr; i--) //Shift elements up

                listArray[i] = listArray[i - 1]; //to make room

          listArray[curr] = it;

          listSize++; //Increment list size

          return true;

   }

   // Append "it" to list

   bool append(const ListItemType& it) {

          if (listSize >= MAX_SIZE) return false;

          listArray[listSize] = it;

          listSize++;

          return true;

   }

   // Remove and return the current element

   ListItemType remove() {

          if (curr == listSize) curr--;

          ListItemType it = listArray[curr]; // Copy the element

          for (int i = curr; i < listSize - 1; i++) // Shift them down

                listArray[i] = listArray[i + 1];

          listSize--; // Decrement size

          if (curr > listSize) {

                curr = listSize;

          }

          return it;

   }

   void moveToStart() { curr = 0; } // Set to front

   void moveToEnd() { curr = listSize; } // Set to end

   void prev() { if (curr != 0) curr--; } // Move left

   void next() { if (curr < listSize) curr++; } // Move right

   int length() const { return listSize; } // Return list size

   int currPos() const { return curr; } // Return current position

   // Set current list position to "pos"

   bool moveToPos(int pos) {

          if ((pos < 0) || (pos > listSize)) return false;

          curr = pos;

          return true;

   }

   // Return true if current position is at end of the list5

   bool isAtEnd() const { return curr == listSize; }

   // Return the current element

   ListItemType getValue() const {

          return listArray[curr];

   }

   //search for first occurrence in the list of an item. If found return true and set curr to the location.

   // if not found, return false and set curr to the end of the list.

   //virtual bool find(const ListItemType& newItem) = 0;

   // since it is a virtual function in the base class

virtual bool find(const ListItemType& it) {

          if(isEmpty())// list is empty

          {

                curr = 0;

                return false;

          }

          // loop over the list

          for(int i=0;i<listSize;i++)

                if(listArray[i] == it) // if ith element is it, return true

                {

                       curr = i; // set curr to index i

                       return true;

                }

          curr = listSize; // item not present, set curr to end of list

          return false;

   }

   //search for the next occurrence in the list of an item. Start with the next position after curr. If found return true and set curr to the location.

   // if not found, return false and set curr to the end of the list.

   //virtual bool findNext(const ListItemType& newItem) = 0;

// since it is a virtual function in the base class

   virtual bool findNext(const ListItemType& it) {

          if(isEmpty())// list is empty

          {

                curr = 0;

                return false;

          }

          // if current element is at the end return false

          if(isAtEnd())

                return false;

          // loop that starts from the location next to curr till the end of list

          for(int i=curr+1;i<listSize;i++)

          {

                if(listArray[i] == it) // if ith element is it, return true

                {

                       curr = i; // set current to i

                       return true;

                }

          }

          curr = listSize; // item not found, set curr to end of list

          return false;

   }

   // count the number of times a value is found in the list

   // curr should be set back to its current location after the count.

   // virtual int count(const ListItemType& newItem) = 0;

   // since it is a virtual function in the base class

   virtual int count(const ListItemType& it) {

          int freq = 0; // set freq to 0 at the start

       // loop over the list

          for(int i=0;i<listSize;i++)

                if(listArray[i] == it) // if ith element is it, increment freq

                       freq++;

          return freq;               //return freq

   }

};

#endif

//end of AList