Computer Science II Lab 5
                 Lists, Stacks, and Deep Pondering


 Introduction
 ============
 Now that you've had some fun writing a game, let's continue the
 challenge by using data structures to solve complex problems.  In
 this lab, we'll take a look at a linked list, class templates, and
 doubly linked lists.  Finally, we will create a stack class which
 you will then use to solve a complex computer science problem.


 Crafting your Data Structures (Guided)
 ======================================
 Many problems are best solved using the proper data structures.  In
 this section, we will take a simple linked list and turn it into a
 doubly linked list.   The first step will be to copy the list.h file
 from the gopher directory.  This is a simple singly linked list with
 an iterator.  For convenience, I am listing the list.h file here,
 but you can go ahead and copy my file.

 --begin list.h--
    1  /*
    2   * File: list.h
    3   * Purpose:  Just a small linked list class
    4   */
    5  #ifndef LIST_H
    6  #define LIST_H
    7
    8  class List {
    9  private:
   10    class Node;
   11
   12  public:
   13    // Constructor and destructor
   14    List() {
   15      head = tail = 0x00;
   16    }
   17
   18
   19    ~List() {
   20      Node *cur;
   21
   22      //start at the head
   23      cur = head;
   24
   25      //kill all the things!
   26      while(cur) {
   27        cur = cur->next;
   28        delete head;
   29        head = cur;
   30      }
   31    }
   32
   33
   34    //high level operations
   35    void append(int data) {
   36      Node *node = createNode(data);
   37
   38      //special case, empty list!
   39      if(isEmpty()) {
   40        head = tail = node;
   41        return;
   42      }
   43
   44      tail->next = node;
   45      tail = node;
   46    }
   47
   48    void prepend(int data) {
   49      Node *node = createNode(data);
   50
   51      //special case, empty list!
   52      if(isEmpty()) {
   53        head = tail= node;
   54        return;
   55      }
   56
   57      node->next = head;
   58      head=node;
   59    }
   60
   61
   62    bool isEmpty() {
   63      return !head;
   64    }
   65
   66
   67    //iterator
   68    class iterator {
   69    public:
   70      //dereference
   71      int operator*() {
   72        return node->data;
   73      }
   74
   75      //comparison
   76      bool operator==(const iterator &rhs) {
   77        return node == rhs.node;
   78      }
   79
   80      bool operator!=(const iterator &rhs) {
   81        return node != rhs.node;
   82      }
   83
   84      //movement
   85      iterator &operator++() {
   86        if(node) node=node->next;
   87        return *this;
   88      }
   89
   90      iterator operator++(int) {
   91        iterator itr(*this);
   92
   93        if(node) node=node->next;
   94        return itr;
   95      }
   96
   97      iterator &operator--() {
   98        node=l.findPrevious(node);
   99        return *this;
  100      }
  101
  102      iterator operator--(int) {
  103        iterator itr(*this);
  104
  105        node=l.findPrevious(node);
  106
  107        return itr;
  108      }
  109
  110    private:
  111      //current node
  112      Node *node;
  113      List &l;
  114
  115      //private constructor
  116      iterator(Node *node, List &lst): l(lst) { this->node = node; }
  117
  118
  119      //we have but one friend
  120      friend class List;
  121
  122    };
  123
  124    //iterator creation
  125    iterator begin() {
  126      return iterator(head, *this);
  127    }
  128
  129
  130    iterator end() {
  131      return iterator(0x00, *this);
  132    }
  133
  134
  135    //iterator action
  136    void insertAfter(iterator &itr, int data) {
  137      //special case, insertion at the tail
  138      if(!itr.node || itr.node==tail) {
  139        append(data);
  140        return;
  141      }
  142
  143
  144      //insert after the iterator node
  145      Node *node = createNode(data);
  146      node->next = itr.node->next;
  147      itr.node->next = node;
  148    }
  149
  150
  151
  152  private:
  153    //inner type for storage of information
  154    class Node {
  155    public:
  156      int data;     //the payload
  157      Node *next;   //the link
  158
  159      Node() { next=0x00; }
  160    };
  161
  162    //private data elements
  163    Node *head;
  164    Node *tail;
  165
  166    //private helpers
  167    Node * createNode(int data) {
  168      Node *node = new Node();
  169      node->data = data;
  170      return node;
  171    }
  172
  173
  174    Node * findPrevious(Node *node) {
  175      Node * cur = head;
  176
  177      while(cur) {
  178        if(cur->next == node)
  179          return cur;
  180        cur = cur->next;
  181      }
  182    }
  183  };
  184
  185  #endif
 --end list.h--

 Review your notes about this list class and look it over.  Make sure
 you understand everything in the file before proceeding.  Now we are
 going to convert list.h into a doubly linked list.  Recall that a
 doubly linked list contains pointers in both directions.  The first
 step is to add this previous pointer to our internal node class.
 Modify your node class so that it looks like this:

 class Node {
 public:
   int data;     //the payload
   Node *next;   //the link
   Node *prev;   // the previous node
   Node() { next=0x00; }
 };


 Now that we have the previous link established, we have to make a
 few changes in the functions dealing with the links. Modify your
 append function so that it looks like this:

 //high level operations
 void append(int data) {
   Node *node = createNode(data);

   //special case, empty list!
   if(isEmpty()) {
     head = tail = node;
     return;
   }

   node->prev = tail;
   tail->next = node;
   tail = node;
 }


 Prepend must also be modified:

 void prepend(int data) {
   Node *node = createNode(data);

   //special case, empty list!
   if(isEmpty()) {
     head = tail= node;
     return;
   }

   node->prev = 0x00;
   node->next = head;
   head=node;
 }

 The decrement operators in the iterator class must also change:

   iterator &operator--() {
     if(node)
       node=node->prev;
     else
       node=l.tail;

     return *this;
   }

   iterator operator--(int) {
     iterator itr(*this);

     if(node)
       node=node->prev;
     else
       node=l.tail;

     return itr;
   }

 Let's add 1 more operator to the iterator, to make things a little
 easier later on:

   iterator & operator=(const iterator &itr) {
     this->node = itr.node;
     return *this;
   }

 Next we need to modify insertAfter:

 //iterator action
 void insertAfter(iterator &itr, int data) {
   //special case, insertion at the tail
   if(!itr.node || itr.node==tail) {
     append(data);
     return;
   }


   //insert after the iterator node
   Node *node = createNode(data);
   node->next = itr.node->next;
   itr.node->next = node;
 }

 Now that deletion is easy, we'll add  a new function:

  void remove(iterator &itr) {
   Node * node=itr.node;

   //update the iterator
   itr--;

   //handle the head node
   if(node==head) {
     head = node->next;
   }

   //handle the tail node
   if(node == tail) {
     tail = tail->prev;
   }

   //unlink
   if(node->prev)
     node->prev->next = node->next;
   if(node->next)
     node->next->prev = node->prev;

   //remove the node
   delete node;
 }


 Finally, we no longer need the private function "findPrevious" so go
 ahead and remove it.

 Now, before we continue, look over your modified list.h and take
 think about how the whole thing works.  Make sure you can get a
 clear mental image of how your linked list now works!

 Now, let's test our doubly linked list.  Enter and compile the
 following program.  If it works, it should display 1 and 2 on
 separate lines:

 --begin listTest.cpp--
    1  #include <iostream>
    2  #include "list.h"
    3
    4  using namespace std;
    5
    6  int main(void) {
    7    List lst;
    8    List::iterator itr = lst.end();
    9    int i;
   10
   11
   12    lst.append(1);
   13    lst.append(2);
   14    lst.append(3);
   15
   16    itr = lst.begin();
   17    itr++;
   18    ++itr;
   19    lst.remove(itr);
   20
   21    for(itr=lst.begin(); itr!=lst.end(); itr++)
   22      cout << *itr << endl;
   23
   24    return 0;
   25
   26  }
 --end listTest.cpp--

 Make sure this program works properly, and that you fully understand
 what it is doing before you proceed!

 Now, we have a really awesome container which can store as many
 integers as we want.  The problem is, there are more things in
 heaven and earth than are dreamt of by whole numbers!  So, let's
 generalize our class!

 We are going to modify our list by turning it into a template.
 Basically, the only thing that has to change each time we want to
 store a new type is the declared type of the data element.  This is
 such a trivial change that we can leave that to the compiler.
 Basically, the compiler will generate a new version of the class for
 each data type we want to store.

 The first step is to tell the compiler that the list class is not
 really a class, but it is a template class.  To do this, add the
 following before the class List definition:

   template <typename T>

 Now, we have the ability to pass in a type name as a template
 variable.  For instance, to make a list of integers, we could do:

   List<int> lst;

 Now, all that remains is to modify the class so it uses the template
 type instead of int.  This involves modifying 6 lines of code.  The
 modified versions of these lines appears as follows:

   void append(T data) {
   void prepend(T data) {
   T &operator*() {
   void insertAfter(iterator &itr, T data) {
   T data;       //the payload
   Node * createNode(T data) {

 I'm not going to tell you where they are though.  Finding them will
 be a good learning experience for you!

 Now, the last order of business before we move on to more
 interesting data structures is to get your listTest.cpp working with
 the template list.  There is a hint on how to do this earlier in
 this section.  You'll have to make a couple of changes, just let the
 compiler be your guide!


 All right!  Now that you have a templated list, let's make a stack
 out of it.  As we discussed in class, a stack is just a special kind
 of list, but we do not want to expose all the list functions to the
 users of the stack.  For this reason, we use the (admittedly
 controversial) private inheritance feature of C++.  The template
 stack.h file is listed below:

 --begin stack.h--
    1  /*
    2   * File: Stack.h
    3   * Purpose: Template linked list implementation of stack
    4   */
    5  #ifndef STACK_H
    6  #define STACK_H
    7
    8  #include "list.h"
    9
   10  template<typename T>
   11  class Stack : private List<T>{
   12    public:
   13
   14    //stack operations
   15    void push(T data) {
   16      this->prepend(data);
   17    }
   18
   19    //pop the stack
   20    T pop() {
   21      T result;
   22      typename List<T>::iterator itr = this->begin();
   23
   24      result = *itr;
   25      this->remove(itr);
   26
   27      return result;
   28    }
   29
   30
   31    T peek() {
   32      return *(this->begin());
   33    }
   34
   35    bool isEmpty(){
   36      return List<T>::isEmpty();
   37    }
   38
   39  };
   40  #endif
 --end stack.h--

 And let's wrap up the handholding with a nice little stack test
 file:

 --begin stackTest.cpp--
    1  #include <iostream>
    2  #include "stack.h"
    3
    4  using namespace std;
    5
    6  int main(void) {
    7    Stack<int> s;
    8
    9    s.push(1);
   10    s.push(2);
   11    s.push(3);
   12
   13    while(!s.isEmpty())
   14      cout << s.pop() << endl;
   15
   16    return 0;
   17  }
   18
 --end stackTest.cpp--


 That's it!  Verify that your stackTest works, and then you're on
 your own!



 Solving Difficult Problems with Stacks (Challenge)
 ==================================================
 That's a nice stack class you have there!  Let's see if you can put
 it to good use.  Remember that you can use stacks to simulate
 recursion, do back tracking, and directly solve inherently stack
 based problems.  Take a look at our examples section on gopher to
 get a good feel for how that works.  After you have done that, pick
 one of the problems from below and solve it using our stack class!


 Problems (choose one)
 ---------------------
 1.)  Write a program which can solve sudoku puzzles.  Sudoku puzzles
      are a 9x9 grid where each row and column contains each number
      1-9 only once.  Also, each 3x3 segment of the grid can only
      contain each number once.  Write your program so that it can
      take in a file containing a sudoku representation and prints
      out the completed puzzle.


 2.) Write a program which can solve the N-queens problem.  The
     N-queens puzzle is to place N queens on an NxN chess board so
     the queens do not attack each other.  Keep in mind that a queen
     can move any number of squares in a straight line or in a
     diagonal line.  Your program should take in the number of queens
     and print out a representation of the chess board with your
     queens in position.

 3.) Write a program which solves the knight's tour problem.  The
     knight's tour is a puzzle where a knight is placed on a chess
     board and then moved, using only legal knight moves, so that it
     visits each square exactly once.  It's OK for the knight to pass
     over a visited square, but it must not land on a visited
     square.  The program should take as input a letter and number
     indicating the initial position on a chess board.  It should
     then print out a series of squares that the knight lands on.

     It should print out 63 squares, with no revisited squares.

 4.) Write a program which can convert between RPN and fully
     parenthesized expressions.  The program should ask the user
     which they intend to enter, and then convert the input into the
     other type of expression.

 5.) Write a program which can solve those triangle peg puzzles
     featured at certain country themed restaurants.  The basic idea
     is this.  You start out with a triangle of pegs:
         0
        * *
       * * *
      * * * *
     * * * * *

     Where a * is a peg and 0 is an empty space.  The goal is to
     remove pegs by jumping them with other pegs and end up with only
     1 peg remaining.  You can only jump along the diagonal paths in
     the puzzle.

     For added challenge, let's make the program so that you can
     enter the location of the hole.  Your program should display
     what the puzzle looks like after each jump.


 Extra Credit
 ============
 You get full credit for solving just one of these problems.  I will
 give you 25 points extra credit for other solutions.  So if you do
 all 5, you will get a 200 on the lab!

 Good luck!

You are viewing proxied material from sdf.org. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.