What is a primary data structure


Exercise course B_ET
Example 2


History lists are used in command-oriented user interfaces (e.g. under UNIX) to save a certain number of the commands last entered by the user so that they can be accessed later if necessary. This technique enables the experienced operator to work much more effectively, since certain recurring character strings do not have to be entered more than once.

Your task is to implement a C ++ class that implements a history list for any commands according to the following specification.

General requirements:

  • Each command is a C ++ string of any length.
  • The maximum number of elements in the history list is in principle unlimited. A specific instance of the class always has a current maximum length at a certain point in time, but this can be changed at any time using the function described below.
  • New commands are generally added to the end of the list. If the current maximum length has already been reached, the first (oldest) entry is automatically removed.
  • When they are entered in the list, all commands receive an unsigned integer as an identifier. This is managed in a counter that is continuously increased by one with each entry. An overflow and thus a return to zero is permissible and therefore does not have to be checked. Once a number has been assigned to a command, it can no longer be changed.

    Example: The two entries with the numbers 9 and 10 are in a list with the current maximum length 2. Then the command inserted below is given the number 11. Since the list is limited to two elements, command 9 is automatically removed.

  • The concrete implementation of the requirements mentioned is up to you. Recommendation:
    • simple linked list as the primary data structure,
    • Management of pointers to access the beginning and end of the list,
    • Management of the current and maximum number of elements as well as the counter for the unique numbers.

    The nodes in the list should only contain a pointer to the command string as useful data.

The following list indicates the member functions to be implemented, which must have exactly the explicitly named arguments. An unspecified return type means that nothing will be returned.

  • Constructor: creates an empty list.
    Argument: maximum length of the list (unsigned integer, default: 0).
  • Destructor: Releases all memory dynamically requested by member functions of the class.
  • Function: Releases all memory dynamically requested by member functions of the class. The list then has the length 0.
  • Operator: adds a new command to the list.
    Argument: pointer to the command.
    The function must dynamically create the required memory space and append the command to the list. If the maximum length has been exceeded, the first element must be completely removed automatically.
  • Operator: searches for a command with a specific identifier.
    Argument: identifier.
    Return: Pointer to the command assigned to the identifier or 0, if not available.
  • Function: status query.
    Arguments: 3 references to unsigned integers via which the current maximum length, the length of the list and the current status of the identifier counter are returned.
  • Function: changing the maximum length.
    Argument: new maximum length.
    If the new maximum length is smaller than the current length of the list, the current length must be reduced accordingly by completely deleting the front elements.
  • Implementation of an operator for outputting the content of the list, with its identifier appearing in front of the command. This operator cannot be a member of the class, but must still have access to all private data.

Show the use of the class you want to create in a small main program.