CS211 - Algorithms and Data Structures II

Department of Computer Science, NUIM



T Naughton, CS NUIM

Solutions for Tutorial 6





Lab Problem 6.2



#include<iostream>



/* This program illustrates a class to maintain an ordered linked list

** of integers. Integers are to be sorted in ascending order.

** The following methods are supported:

** -OrdIntList::Add // Add an int to the list at an appropriate pos

** -OrdIntList::PrintList // Print out the contents of the list

** -OrdIntList::Contains // Return true/false if an int is in the list

*/



class ListElement {

  // A very simple class describing each node of the list

 public:

  int element;

  ListElement * next;

};



class OrdIntList {



 public:

  OrdIntList(); // constructor

  ~OrdIntList(); // destructor



  // methods that act on IntList

  void Add(int newdata);

  void PrintList();

  void DeleteList();

  bool Contains(int element);



 private:

  ListElement * head; // a pointer to the head of the list



};



OrdIntList::OrdIntList(){

  head = NULL; // Initialise the list (mark the end of the list

               // with NULL).

}



OrdIntList::~OrdIntList(){

  DeleteList(); // Clean up when finished with the variable

}



void OrdIntList::Add(int newdata){

  // This method creates a new node with the data that is passed to

  // it, adding it in to the list in such a position as to maintain

  // an ascending order.

  ListElement * current; // pointer used to traverse list

  ListElement * temp; // pointer to the new node



  temp = new ListElement;

  temp->element = newdata;



  // There are three cases to take care of here. One, the list is

  // empty, two, the list is not empty, but new node must be

  // inserted at the beginning of the list, and three, the node

  // must be inserted somewhere else in the list.

  if (head == NULL) {

    temp->next = head;

    head = temp;



  } else if (newdata < head->element) {

    // Although these two lines of code are identical to those above,

    // using a separate condition is safer: evaluating head->element

    // when head==NULL will cause a runtime error.

    temp->next = head;

    head = temp;



  } else {

    current = head;

    while ((current->next->element < newdata) && (current->next != NULL)) {

      current = current->next;

    }

    // At this point, current is pointing at the last element with

    // a value less than newdata

    temp->next = current->next;

    current->next = temp;

  }

}



void OrdIntList::PrintList(){

  // This method prints out the list. It does so by printing out the

  // contents of the head of the list and then each subsequent element

  // in turn. It repeats this until the end of the

  // list (a NULL) is found. The function returns a pointer to the

  // head of the list. Note: this function will work if an empty

  // list is passed to it.

  ListElement * current;



  cout << endl << "List: ";

  current = head; // set current to point to the head of the list

  while (current != NULL) {

    cout << current->element << ' ';

    current = current->next;

  }

}



void OrdIntList::DeleteList(){

  // Delete the entire list

  ListElement * temp; // pointer to element to be deleted



  while (head != NULL) {

    temp = head;

    head = head->next;

    delete temp;

  }

  // head will have been set to NULL when loop terminates.

}



bool OrdIntList::Contains(int element){

  // Return true if element is in the list, false if not.

  ListElement * current;

  bool found;



  current = head;

  found = false;

  while ((current != NULL) && !found) {

    if (current->element == element) {

      found = true;

    }

    current = current->next;

  }

  return found;

}



void main(void){

  OrdIntList list; // the ordered list

  int tempint; // temporary storage



  list.Add(5);

  list.Add(2);

  list.Add(9);

  list.PrintList();



  tempint = 99;

  cout << endl << tempint << " is ";

  if (!list.Contains(tempint)) {

    cout << "not ";

  }

  cout << "in the list.";



  tempint = 9;

  cout << endl << tempint << " is ";

  if (!list.Contains(tempint)) {

    cout << "not ";

  }

  cout << "in the list.";

}















Tutorial Problem T6.1



#include<iostream>



/*

** This program shows some of the ways of printing a singly-linked list

** in reverse.

** -Push onto a linked list stack and then pop [O(n) space O(n) time]

** -Copy the linked list into a dynamically allocated fixed-size array

**    and print out the array in reverse [O(n) space O(n) time]

** -Iteration using the list size and a counter to print out the nth

**    element, followed by the (n-1)th, etc. [O(1) space O(n^2) time]

** -Iteration using a circularly-linked list and the list size

**    [O(1) space O(n^2) time]

** -Change to a doubly-linked list to allow traversal in both directions

**    [O(1) space O(n) time] -- is this cheating?

** -Recursion with a pointer to the next element in the list [O(1) space

**    O(n) time] -- neatest solution, however our model of computation

**    does not take into account the time and space overheads associated

**    with implementing a recursive call

**

** These techniques require use of the following methods:

** -Add a node to the front of a list

** -Count the number of elements in the list

** -Return the nth integer in the list (if the list has >n elements)

** -Return a pointer to the node that appears n nodes after the

**    currently pointed to node

*/



class ListElement {

  // A very simple class describing each node of the list

 public:

  int element;

  ListElement * next;

};



class IntList {



 public:

  IntList(); // constructor

  ~IntList(); // destructor



  // methods that act on IntList

  void AddtoFront(int newdata);

  void PrintList();

  void DeleteList();

  int Count();

  int ReturnElem(int index);

  ListElement * Seek(ListElement * current, int offset);



  void PrintListReverseRec(ListElement * current); // recursive

  ListElement * GetHeadPtr();

  void PrintListReverseStack(); // push onto stack & pop

  void PrintListReverseArray(); // array

  void PrintListReverseSeek(); // iteration, counter

  void PrintListReverseCir(); // iteration, circular

  //void PrintListinReverse(); // doubly-linked



 private:

  ListElement * head; // a pointer to the head of the list



};



IntList::IntList(){

  head = NULL; // Initialise the list (mark the end of the list

               // with NULL).

}



IntList::~IntList(){

  DeleteList(); // Clean up when finished with the variable

}



void IntList::AddtoFront(int newdata){

  // This method creates a new node with the data that is passed to

  // it, adding the node to the front of the list.

  ListElement * temp;      // Create a pointer to a new node

  temp = new ListElement;  // Allocate memory for the node

  temp->element = newdata; // Put the data in the node



  // Put this node at the top of the list by (a) pointing it at the

  // head of the list and (b) repointing the head of the list at this

  // node.

  // Can you see that the first time we add a node to the list

  // (i.e. when head==NULL) that we end up marking the end of the

  // list with a NULL?

  temp->next = head;

  head = temp;

}



void IntList::PrintList(){

  // This method prints out the list. It does so by printing out the

  // contents of the head of the list and then each subsequent element

  // in turn. It repeats this until the end of the

  // list (a NULL) is found. The function returns a pointer to the

  // head of the list. Note: this function will work if an empty

  // list is passed to it.

  ListElement * current;



  cout << endl << "List: ";

  current = head; // set current to point to the head of the list

  while (current != NULL) {

    cout << current->element << ' ';

    current = current->next;

  }

}



void IntList::DeleteList(){

  // Delete the entire list

  ListElement * temp; // pointer to element to be deleted



  while (head != NULL) {

    temp = head;

    head = head->next;

    delete temp;

  }

  // head will have been set to NULL when loop terminates.

}



int IntList::Count(){

  // Count the number of nodes in the list

  ListElement * current;

  int total;



  total = 0;

  current = head;

  while (current != NULL) {

    total++;

    current = current->next;

  }

  return total;

}



int IntList::ReturnElem(int index){

  // Return the nth element in the list. Zero is the first. If an nth

  // element does not exist then return -1

  ListElement * temp;



  // return as pointer to the nth element

  temp = Seek(head, index);



  // check if nth element exists

  if (temp == NULL) {

    return -1;

  } else {

    return temp->element;

  }

}



ListElement * IntList::Seek(ListElement * current, int offset){

  // Return a pointer to the nth element after the node pointed to by

  // current. offset = zero returns current. If an nth element does

  // not exist then return NULL

  int counter;

  counter = 0;

  while ((counter < offset) && (current != NULL)) {

    current = current->next;

    counter++;

  }

  // Return current. If the list was exhausted before index was found

  // such that current==NULL then just return it anyway.

  return current;

}



ListElement * IntList::GetHeadPtr(){

  // Return a pointer to the head of the list (which is private)

  return head;

}



void IntList::PrintListReverseRec(ListElement * current){

  // This method prints out the list in reverse order. It does so by

  // employing a nice effect in recursion. We recursively seek the

  // end of the list and on the way out of the multiple recursive

  // calls we print the list elements. As always, we want our function

  // to work if an empty list is passed to it.

  if (current != NULL) {

    PrintListReverseRec(current->next);

    cout << current->element << ' ';

  } else {

    cout << endl << "List in reverse (Recursive): ";

  }

}



void IntList::PrintListReverseStack(){

  // Push onto a linked list stack and then pop

  IntList stack;

  ListElement * current;



  current = head;

  while (current != NULL) {

    stack.AddtoFront(current->element);

    current = current->next;

  }

  cout << endl << "List in reverse (Stack)...";

  stack.PrintList();

}



void IntList::PrintListReverseArray(){

  // Copy the linked list into a dynamically allocated fixed-size array

  // and print out the array in reverse

  int * array;

  int size;

  ListElement * current;

  int count;



  size = Count();

  array = new int[size];

  current = head;

  count = 0;

  while (count < size) {

    array[count] = current->element;

    count++;

    current = current->next;

  }

  cout << endl << "List in reverse (Array): ";

  count--;

  while (count >= 0) {

    cout << array[count] << ' ';

    count--;

  }

  delete [] array;

}



void IntList::PrintListReverseSeek(){

  // Iteration using the list size and a counter to print out the nth

  // element, followed by the (n-1)th, etc.

  int current;



  cout << endl << "List in reverse (Seek): ";

  current = Count() - 1; // Count()-1 will be the highest index

  while (current >= 0) {

    cout << ReturnElem(current) << ' ';

    current--;

  }

}



void IntList::PrintListReverseCir(){

  // Iteration using a circularly-linked list and the list size. Jump

  // Count() times to a position (Count()-1) nodes away.

  int size; // size of list and so also the number of jumps

  int jumpsize; // size of each jump

  ListElement * current; // points to the next node for printing

  int count;



  cout << endl << "List in reverse (Circular): ";



  // Turn list into a circularly-linked list

  size = Count();

  current = Seek(head, size - 1); // find last element

  current->next = head;



  // Start printing

  current = head;

  jumpsize = size - 1;

  count = 0;

  while (count < size) {

    current = Seek(current, jumpsize);

    cout << current->element << ' ';

    count++;

  }



  // Turn back into a singly-linked list (so our destructor will

  // terminate correctly)

  current = Seek(head, size - 1); // find last element

  current->next = NULL;



}



void main(void){



  /*

  ** Call the methods here to test them.

  */



  IntList list;

  int tempint;



  cout << endl << endl;



  // Test for an empty list first

  list.PrintList();

  cout << endl << "List is " << list.Count() << " long.";

  list.PrintListReverseRec(list.GetHeadPtr());

  list.PrintListReverseStack();

  list.PrintListReverseArray();

  list.PrintListReverseSeek();

  list.PrintListReverseCir();



  // Now test for a non-empty list

  list.AddtoFront(9);

  list.AddtoFront(0);

  list.AddtoFront(2);

  list.AddtoFront(1);

  list.AddtoFront(0);

  list.PrintList();

  cout << endl << "List is " << list.Count() << " long.";

  list.PrintListReverseRec(list.GetHeadPtr());

  list.PrintListReverseStack();

  list.PrintListReverseArray();

  list.PrintListReverseSeek();

  list.PrintListReverseCir();

}