Question

Data Structure

6. Write a recursive routine that will have an integer array and an index as parameters and will return the count of all odd integers. You may assume that the index starts out at the END of the array.

12. Write the implementation function for ArrayBag in C++, called bagLess, that takes an ItemType of item as parameters and use it count items in the current bag that are less than the item (hint: use toVector)

13. Write a sum function in C++ for LinkedBag of integers (must use pointers to traverse the linked list) that will return a sum of all values.

15. Write a Grammar that starts with a letter or a group of letters (assume uppercase), has an '?' or '!', and ends with a letter or a group of letters (uppercase)

16.

Given: e + f / (a – b) * c

Write out the prefix form

Answer 1

12)mplementation function for ArrayBag in C++

#include "ArrayBag.h"

#include <cstddef>

  template<class ItemType>

  ArrayBag<ItemType>::ArrayBag(): itemCount(0), maxItems(DEFAULT_CAPACITY)

  {

  } // end default constructor

  template<class ItemType>

int ArrayBag<ItemType>::getCurrentSize() const

{

return itemCount;

} // end getCurrentSize

  template<class ItemType>

  bool ArrayBag<ItemType>::isEmpty() const

  {

   return itemCount == 0;

  } // end isEmpty

  template<class ItemType>

  bool ArrayBag<ItemType>::add(const ItemType& newEntry)

  {

   bool hasRoomToAdd = (itemCount < maxItems);

   if (hasRoomToAdd)

   {

   items[itemCount] = newEntry;

   itemCount++;

   } // end if

  

   return hasRoomToAdd;

  } // end add

  template<class ItemType>

  bool ArrayBag<ItemType>::remove(const ItemType& anEntry)

  {

   int locatedIndex = getIndexOf(anEntry, 0);

   bool canRemoveItem = !isEmpty() && (locatedIndex > -1);

   if (canRemoveItem)

   {

   itemCount--;

   items[locatedIndex] = items[itemCount];

   } // end if

     

   return canRemoveItem;

  } // end remove

  template<class ItemType>

  void ArrayBag<ItemType>::clear()

  {

   itemCount = 0;

  } // end clear

  template<class ItemType>

  bool ArrayBag<ItemType>::contains(const ItemType& anEntry) const

  {

   return getIndexOf(anEntry, 0) > -1;

  } // end contains

  template<class ItemType>

  int ArrayBag<ItemType>::getFrequencyOf(const ItemType& anEntry) const

  {

   return countFrequency(anEntry, 0);

  } // end getFrequencyOf

  template<class ItemType>

  vector<ItemType> ArrayBag<ItemType>::toVector() const

  {

   vector<ItemType> bagContents;

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

   bagContents.push_back(items[i]);

     

   return bagContents;

  } // end toVector

  // private

  template<class ItemType>

  int ArrayBag<ItemType>::countFrequency(const ItemType& anEntry, int searchIndex) const

  {

   int frequency = 0;

   if (searchIndex < itemCount)

   {

   if (items[searchIndex] == anEntry)

   {

   frequency = 1 + countFrequency(anEntry, searchIndex + 1);

   }

   else

   {

   frequency = countFrequency(anEntry, searchIndex + 1);

   } // end if

   } // end if

   return frequency;

} // end countFrequency

// private

template<class ItemType>

int ArrayBag<ItemType>::getIndexOf(const ItemType& target, int searchIndex) const

{

int result = -1;

if (searchIndex < itemCount)

{

if (items[searchIndex] == target)

{

result = searchIndex;

}

else

{

result = getIndexOf(target, searchIndex + 1);

} // end if

} // end if

  

return result;

}

13)sum function in C++ for LinkedBag of integers

class Node

{
public:
int data;
Node* next;
};
  
/* Function to create a
new node with given data */
Node* newNode(int data)
{
Node* new_node = new Node();
new_node->data = data;
new_node->next = NULL;
return new_node;
}
  
/* Function to insert a node at the
beginning of the Singly Linked List */
void push(Node** head_ref, int new_data)
{
/* allocate node */
Node* new_node = newNode(new_data);
  
/* link the old list off the new node */
new_node->next = (*head_ref);
  
/* move the head to point to the new node */
(*head_ref) = new_node;
}
  
/* Adds contents of two linked lists and
return the head node of resultant list */
Node* addTwoLists(Node* first, Node* second)
{
  
// res is head node of the resultant list
Node* res = NULL;
Node *temp, *prev = NULL;
int carry = 0, sum;
  
// while both lists exist
while (first != NULL
|| second != NULL) {
// Calculate value of next
// digit in resultant list.
// The next digit is sum of
// following things
// (i) Carry
// (ii) Next digit of first
// list (if there is a next digit)
// (ii) Next digit of second
// list (if there is a next digit)
sum = carry + (first ? first->data : 0)
+ (second ? second->data : 0);
  
// update carry for next calulation
carry = (sum >= 10) ? 1 : 0;
  
// update sum if it is greater than 10
sum = sum % 10;
  
// Create a new node with sum as data
temp = newNode(sum);
  
// if this is the first node then
// set it as head of the resultant list
if (res == NULL)
res = temp;
  
// If this is not the first
// node then connect it to the rest.
else
prev->next = temp;
  
// Set prev for next insertion
prev = temp;
  
// Move first and second
// pointers to next nodes
if (first)
first = first->next;
if (second)
second = second->next;
}
  
if (carry > 0)
temp->next = newNode(carry);
  
// return head of the resultant list
return res;
}
  
// A utility function to print a linked list
void printList(Node* node)
{
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
cout << endl;
}
  
/* Driver code */
int main(void)
{
Node* res = NULL;
Node* first = NULL;
Node* second = NULL;
  
// create first list 7->5->9->4->6
push(&first, 6);
push(&first, 4);
push(&first, 9);
push(&first, 5);
push(&first, 7);
printf("First List is ");
printList(first);
  
// create second list 8->4
push(&second, 4);
push(&second, 8);
cout << "Second List is ";
printList(second);
  
// Add the two lists and see result
res = addTwoLists(first, second);
cout << "Resultant list is ";
printList(res);
  
return 0;
}

15)where you want to go? ,oh! The Historic University Town

16)PREFIX : + e / f (a-b) * c