Data Structures

Data Structures and Algorithms

In this tutorial we introduce more complex data structures (containers) and algorithms which operate on these containers. We therefore require a mechanism to introduce new custom data types, e.g. $\mathrm{struct}$ in C or $\mathrm{class}$ in C++.

Linear Container (Vector)

Create a new data type containing an array of $\mathrm{strings}$ . Then write the following functions to provide some basic functionality to the container:

L1: An initialization for a given range of the container with default values.

L1: A function to edit a single entry of the container at a certain position.

L1: A function to delete an entry. A deletion of an entry can be modeled by, e.g. setting the string to an empty string.

L2: A function to sort the entries of the container.

L2: A function to search for a string. This function should return the position within the container.

L2: A modified search method which does not require a linear search (which means, that all entries have to be searched).

Associative Container (Map)

Create a new data type containing a $\mathrm{key}$ and a $\mathrm{value}$ . Create a container with an arbitrary size of these elements. Write the following functions to enhance the functionality of the container:

L1: A function, which initializes a given range of the container with default values.

L1: A function to edit a single entry of the container at a certain position.

L1: A function to delete an entry. A deletion of an entry can be modeled by, e.g. setting the key value to zero.

L1: A function to sort the entries of the container by their key value.

L1: A function to search for a key. This function should return the position within the container.

L2: A modified search method which does not require a linear search (which means, that all entries have to be searched).

L2: A function which calculates the key based on the string, e.g. accumulate all values of the characters of the string modulo the size of the container.

L3: A function which reads in the strings from a file and count how often each word occurs.

Cipher

Create a data structure which contains $\mathrm{word}$ and $\mathrm{cipher\_key}$ . Use an array of this data structure to create a word and cipher container. Write the following functions:

L1: A function which loads a textfile into the container. The cipher_key should be zero in the beginning. Use an arbitrary text file as input file.

L1: A function to calculate a hash value based on the word, e.g., the sum of the characters forming the word.

L1: A function which encrypts a single entry of the container, e.g., an addition of each character and the key. Be aware, that the resulting values have to be within the character limits. Also include the calculation of the cipher_key (e.g., add the hash and the key modulo 23.

L2: A function which encrypts the complete container. The initial key has to be provided by the user. Each subsequent step should use the cipher_key from the last word. Write the result to the screen and into a file.

L2: A method, which decrypts the container and outputs the result to the screen as well as to a file.

C++ Reference Implementation: Associative Container

#include<iostream>
#include<fstream>
#include<map>

int main(int argc, char** argv)
{
  std::string filename1(argv[1]);
  std::ifstream file_in(filename1.c_str());

  std::map<std::string, long> container;
  std::map<std::string, long>::iterator cit;

  if (!file_in.is_open())
    {
      std::cout << "file not found.. name: " << filename1 << std::endl;
      return -1;
    }
  while (!file_in.eof())
    {
      std::string inputstr;
      file_in >> inputstr;
      container[inputstr]++;

    }

  std::cout << "writing in file .. " << std::endl;
  std::string filename2(argv[2]);
  std::ofstream file_out(filename2.c_str());

  if (!file_out.is_open())
    {
      std::cout << "file not found.. name: " << filename2 << std::endl;
      return -1;
    }
  
  for (cit = container.begin(); cit != container.end(); ++cit)
    {
      file_out << (*cit).first << "\t" 
	       << (*cit).second << std::endl;
    }
  file_out.close();

  return 0;
}

C++ Reference Implementation: Cipher

#include<iostream>
#include<fstream>
#include<vector>

struct entry
{
  std::string   word;
  long          cipher_key;
};

long calculate_hash(entry const& entr)
{
  long temp_hash_key = 0;
  for (unsigned long i =0 ;i < entr.word.size(); ++i)
    {
      temp_hash_key += entr.word[i];
    }
  return temp_hash_key;
}

long load_text(std::vector<entry>& text_field, std::string filename)
{
  std::ifstream file_in(filename.c_str());
  file_in.setf(std::ios::uppercase);
  if (!file_in.is_open())
    {
      std::cout << "file not found.. name: " << filename << std::endl;
      return -1;
    }
  while (!file_in.eof())
    {
      entry tempentry;
      file_in >> tempentry.word;
      std::transform (tempentry.word.begin(),
		      tempentry.word.end(), 
		      tempentry.word.begin(), toupper);
      tempentry.cipher_key = 0;
      text_field.push_back(tempentry);
      calculate_hash(text_field[text_field.size()-1]);
    }
  return 0;
}

long write_text(std::vector<entry> const& text_field, std::string filename)
{
  std::ofstream file_out(filename.c_str());
  if (!file_out.is_open())
    {
      std::cout << "file not found.. name: " << filename << std::endl;
      return -1;
    }
  for (unsigned long i=0; i < text_field.size(); ++i)
    {
      file_out << text_field[i].word << " ";
    }
  file_out.close();
  return 0;
}
// ------
long encrypt(entry const& clear_text, entry& encrypted_text, long key)
{
  long ascii_offset = 'A';
  encrypted_text.word.resize(clear_text.word.size());
  for (unsigned long j=0; j< clear_text.word.size();++j)
    {
      encrypted_text.word[j] = ascii_offset + (clear_text.word[j]-ascii_offset + key)%26;
    }
  encrypted_text.cipher_key = (calculate_hash(clear_text) + key)%24;
  return 0;
}
long encrypt_text(std::vector<entry> const& clear_text, 
		  std::vector<entry> &      encrypted_text, long init_key)
{
  long key = init_key;
  encrypted_text.resize (clear_text.size() );
  for (unsigned long i = 0; i < clear_text.size(); ++i)
    {
      encrypt (clear_text[i], encrypted_text[i], key);
      key = encrypted_text[i].cipher_key;
    }
  return 0;
}
// ------
// ------
long decrypt(entry const& clear_text, entry& encrypted_text, long key)
{
  long ascii_offset = 'A';
  encrypted_text.word.resize(clear_text.word.size());
  for (unsigned long j=0; j< clear_text.word.size();++j)
    {
      encrypted_text.word[j] = ascii_offset + (26+clear_text.word[j]-ascii_offset-key)%26;
    }
  encrypted_text.cipher_key = (calculate_hash(encrypted_text) + key) % 24;
  return 0;
}
long decrypt_text(std::vector<entry> const& clear_text, 
		  std::vector<entry> &      encrypted_text, long init_key)
{
  long key = init_key;
  encrypted_text.resize (clear_text.size() );
  for (unsigned long i = 0; i < clear_text.size(); ++i)
    {
      decrypt (clear_text[i], encrypted_text[i], key);
      key = encrypted_text[i].cipher_key;
    }
  return 0;
}
// -------

int main(int argc, char** argv)
{
  std::vector<entry>  text_field, encrypted_field, decrypted_field;
  std::cout << "encrypting.. " << std::endl;
  long global_key = 12;
  load_text   ( text_field, argv[1] );
  encrypt_text( text_field, encrypted_field , global_key );
  write_text  ( encrypted_field, argv[2] );
  std::cout << "decrypting.. " << std::endl;
  decrypt_text( encrypted_field, decrypted_field, global_key);
  write_text  ( decrypted_field, argv[3] );
  return 0;
}