CS211 - Algorithms and Data Structures II

Department of Computer Science, NUIM



T Naughton, NUIM

Lab Exam 3



Problem 3A.1



#include<iostream>



int * ReadInts(int * listsize);

int CheckSqrRoot(const int list[], int listsize);



/* This computer program reads positive integers, one per line,

** from the keyboard into a list. The user indicates that they

** are finished by entering any negative integer (the negative

** integer itself is not stored). The computer program then checks

** if any of the numbers in the list is the square root of any other

** number in the list. The program terminates after finding the

** first such number. This program is written using fixed-size arrays,

** the new and delete commands, and a routine to copy the elements

** from one array to another.

*/



int * ReadInts(int * listsize){

  /*

  ** This function reads into a list as many integers as entered by

  ** the user and returns a pointer to the list. The length of the list

  ** is implicitly returned.

  */



  int newint;       // Holds the new int from the user

  int * list = NULL;

  int * templist = NULL;

  int counter;



  cout << endl << "Please enter a list of positive integers, one ";

  cout << "per line. Indicate the list is finished by entering any ";

  cout << "negative integer:" << endl;



  cin >> newint;

  /* When this loops first begins the list is of length *listsize

  ** and as each integer is entered by the user we increase this length

  ** by one.

  */

  while (newint >= 0){

    /* save a pointer to list called templist, create a new list,

    ** copy templist into list, append tempint, delete templist.

    */

    templist = list;



    (*listsize)++; // increase the length by one

    list = new int[*listsize];



    counter = 0;

    /* copy the old list into the new (longer) list

    */

    while (counter < ((*listsize)-1)){

      list[counter] = templist[counter];

      counter++;

    }

    list[counter] = newint;



    delete [] templist;



    /*

    ** Temporary code to test the function...

    *

    counter = 0;

    cout << "List is now " << *listsize << " long: ";

    while (counter < *listsize){

      cout << list[counter] << ',';

      counter++;

    }

    cout << endl;

    */



    cin >> newint; // read in the next int and check if it is >0

  }



  return list;

}



int CheckSqrRoot(const int list[], int listsize){

  /* Square each element in the list and compare it to each element

  ** in the list (including itself). If its square is found in the list

  ** then return its index (it will be the square root).

  ** Otherwise, return -1 to indicate no square root was found.

  */

  int rootindex;          // index to square root (if any)

  int counter;            // index to potential squares

  long int rootsquared;   // set to 'long' just in case

  bool found;             /* have we found a square root? This is used

                          ** to break out of the loop as soon as the

                          ** first is found.

                          */



  rootindex = 0; // start searching from the beginning of the list

  found = false;

  while ((rootindex < listsize) && !found){

    // Check if the square of list[rootindex] also exists in list[]

    rootsquared = list[rootindex]*list[rootindex];



    counter = 0; // start searching again from the beginning of list

    while ((counter < listsize) && !found){

      if (rootsquared == list[counter]){

        found = true; // stop when the first is found

      }

      counter++;

    }

    rootindex++;

  }

  rootindex--;   // It will have been incremented once too often



  if (found) {

    return rootindex;

  } else {

    return -1;

  }

}



void main(void){

  int root;          // Index of first root found

  int * list = NULL; // The list

  int listsize = 0;  /* Size of the list (zero before the user

                     ** enters any integers)

                     */



  list = ReadInts(&listsize);



  root = CheckSqrRoot(list, listsize);



  if (root >= 0){

    cout << endl << "The number " << (list[root]*list[root]);

    cout << " has a square root of " << list[root];

    cout << " in the list." << endl;

  } else {

    cout << endl << "No square root found in the list.";

  }



  delete [] list; /* This is not needed here, but it's

                  ** good programming practice to explicitly free

                  ** memory (i.e. delete) if one explicitly allocates

                  ** it (i.e. with new).

                  */



}













Problem 3B.1



#include<iostream>



char * ReadChars(int * listsize);

void CheckNeighbours(const char list[], int listsize, int * i1, int * i2);



/* This computer program reads single characters, one per line,

** from the keyboard into a list. The user indicates that they

** are finished by entering a '%' character (the '%' is itself not

** stored). The computer program then checks if any of the letters,

** anywhere in the list, appear next to each other alphabetically.

** The program terminates after finding the first such pair of

** letters. This program is written using fixed-size arrays,

** the new and delete commands, and a routine to copy the elements

** from one array to another.

*/



char * ReadChars(int * listsize){

  /*

  ** This function reads into a list as many characters as entered by

  ** the user and returns a pointer to the list. The length of the list

  ** is implicitly returned.

  */



  char newchar;       // Holds the new char from the user

  char * list = NULL;

  char * templist = NULL;

  int counter;



  cout << endl << "Please enter a list of letters, one ";

  cout << "per line. Indicate the list is finished by entering a ";

  cout << "'%' character:" << endl;



  cin >> newchar;

  /* When this loops first begins the list is of length *listsize

  ** and as each character is entered by the user we increase this length

  ** by one.

  */

  while (newchar != '%'){

    /* save a pointer to list called templist, create a new list,

    ** copy templist into list, append tempint, delete templist.

    */

    templist = list;



    (*listsize)++; // increase the length by one

    list = new char[*listsize];



    counter = 0;

    /* copy the old list into the new (longer) list

    */

    while (counter < ((*listsize)-1)){

      list[counter] = templist[counter];

      counter++;

    }

    list[counter] = newchar;



    delete [] templist;



    /*

    ** Temporary code to test the function...

    *

    counter = 0;

    cout << "List is now " << *listsize << " long: ";

    while (counter < *listsize){

      cout << list[counter] << ',';

      counter++;

    }

    cout << endl;

    */



    cin >> newchar; // read in the next char and check for '%'

  }



  return list;

}



void CheckNeighbours(const char list[], int listsize, int * i1, int * i2){

  /* Compare the neighbours of each letter in the list with each element

  ** in the list (including itself). If a match is found in the list

  ** then implicitly return the indexes of both it and its its neighbour.

  ** Otherwise, set both indexes to -1 to indicate no neighbours found.

  ** We choose to assume that case is important, so that uppercase 'C'

  ** is not a neighbour of 'd'.

  ** We also assume that list[] contains only valid letters.

  */

  int firstindex;         // index to tested letters

  int counter;            // index to its potential neighbours

  bool found;             /* have we found neighbours? This is used

                          ** to break out of the loop as soon as the

                          ** first is found.

                          */



  firstindex = 0; // start searching from the beginning of the list

  found = false;

  while ((firstindex < listsize) && !found){

    /* Check if the its neighbours also exists in list[]. Start

    ** searching from the beginning of list.

    */

    counter = 0;

    while ((counter < listsize) && !found){

      if ( char(int(list[firstindex])-1) == list[counter] ||

           char(int(list[firstindex])+1) == list[counter] ){

        found = true; // stop when the first is found

      }

      counter++;

    }

    firstindex++;

  }

  counter--;      // Will have been incremented once too often

  firstindex--;   // Will have been incremented once too often



  if (found) {

    *i1 = firstindex;

    *i2 = counter;

  } else {

    *i1 = -1;

    *i2 = -1;

  }

}



void main(void){

  int i1, i2;         // Indexes of the neighbouring letters

  char * list = NULL; // The list

  int listsize = 0;   /* Size of the list (zero before the user

                      ** enters any letters)

                      */



  list = ReadChars(&listsize);



  CheckNeighbours(list, listsize, &i1, &i2);



  if (i1 >= 0){

    cout << endl << "Letters " << list[i1] << " and " << list[i2];

    cout << " appear next to each other alphabetically." << endl;

  } else {

    cout << endl << "No letters appear next to each other ";

    cout << "alphabetically." << endl;

  }



  delete [] list; /* This is not needed here, but it's

                  ** good programming practice to explicitly free

                  ** memory (i.e. delete) if one explicitly allocates

                  ** it (i.e. with new).

                  */



}