In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of November 9th
(this exercise will still be available for submission after that deadline, but without couting towards your grade)
[to understand the context of this problem, you should read the class #05 exercise sheet]


[AED021] Counting elements

In this problem you should only submit a singlyLinkedList.h file with a self-containing definition of a class SinglyLinkedList<T>

Base Code

Use as a basis the class SinglyLinkedList<T> (see code | download code) which implements a generic singly linked list similar to what was done on classes, with methods to add and remove an element in the end, return the size, knowing if the list is empty or printing the list.

The Problem

Add a new method int count(T & v) to the class. The function should return the number of occurences of value v in the list.

Submission

You should submit the file singlyLinkedList.h with the method count added to SinglyLinkedList<T> as requested (and without removing any of the other existing methods). You can however create additional methods, if you need them.

Mooshak will use the following code to link to your class, read the inputs, build the lists and call your method, printing its result.

#include <iostream>
#include <string>

#include "singlyLinkedList.h"

// Read n and then n elements to add to the list using addFirst, followed by
// Read q and then q queries q_i to call count(q_i)
template <typename T>
void read() {
  int n;
  std::cin >> n;
  SinglyLinkedList<T> lst;
  for (int i=0; i<n; i++) {
    T v;
    std::cin >> v;
    lst.addFirst(v);
  }
  std::cout << "lst = " << lst.toString() << " | size = " << lst.size() << std::endl;
  std::cin >> n;
  for (int i=0; i<n; i++) {
    T q;
    std::cin >> q;
    std::cout << "lst.count(" << q << ") = " << lst.count(q) << std::endl;
  }   
}

int main() {

  int n;
  std::cin >> n;
  for (int i=0; i<n; i++) {
    std::string type;
    std::cin >> type;
    if (type == "int") read<int>();
    else if (type == "char") read<char>();
    else if (type == "string") read<std::string>();
  }
  
  return 0;
}

Example Input Example Output
3

int 8
1 2 3 4 3 1 2 1
5
1 2 3 4 5

char 5
a a a a a
2
b a

string 2
hello world
3
hello world c++
lst = {1,2,1,3,4,3,2,1} | size = 8
lst.count(1) = 3
lst.count(2) = 2
lst.count(3) = 2
lst.count(4) = 1
lst.count(5) = 0
lst = {a,a,a,a,a} | size = 5
lst.count(b) = 0
lst.count(a) = 5
lst = {world,hello} | size = 2
lst.count(hello) = 1
lst.count(world) = 1
lst.count(c++) = 0


Algorithms and Data Structures (L.EIC011) 2024/2025
DCC/FCUP & DEI/FEUP - University of Porto