PIC 10b Fall 2000 HW #3

Homework FAQ.

Solution Set.

Due date: Nov. 3. Lecture 1's due time is:  9:30am 
=========         Lecture 2's due time is:  noon.

Reading Assignment: Reading in Savitch Ch13, Sedgewick. Finish Ch3., Ch 4.1,4.2
===================
        
Files to submit:   pic10bhw3file1.h   -contains List class and Node class
=================                      interfaces
                   pic10bhw3file2.cpp -contains List class and Node class
                                       implementation   
                   pic10bhw3file3.cpp -driver program.

HW3 Purpose: Write a program to store arbitrarily long numbers 
============ and give the user the ability to perform certain manipulations
             on them. Numbers are store in linked-list each node 
             containing a single decimal digit. 


Specification:
==============
For this assignment you will have to write two classes: A class Node
which implements a node in a linked-list and a class List which
is a container for a singly linked-list and supports member functions 
for manipulating a list.

Node
====
Here are the private member variables of Node:
----

int Item;
Node *next;

Here are the public member functions a Node should support:
----

Node(); // creates a node with next set to NULL and Item set to 0.
Node(int i, Node *n); // creates a node with next set to n and Item set to i
Node(const Node& node); //copy constuctor. Makes a new Node with same Item and 
                     //next.
~Node(); //destructor. Does nothing since what next points to might
         //still be used by some other node.

Node& operator=(const Node& node); // copies node into the current object
                                   // and returns a reference to current object

void setItem(int i); //sets Item of current object to i
int getItem(); //returns Item of current object

void setNext(Node *n); //sets next equal to n
Node* getNext(); //returns next of current object


List
====
Here are the private member variables of List:
----

Node *head;

Here are the public member functions a List should support:
----
List(); // creates a node equal to NULL.
List(const List& l);// copy constuctor. Makes a new List containing
                       // copies of each of the nodes in l. 
                      
 
~List(); //destructor. Should have a tmp pointer to a Node.
         //It then repeatedly does the following till it gets to the
         //end of the list. Sets tmp to equal head. Sets head to equal
         //head->next and then deletes tmp.

List& operator=(const List& l); // copies the linked-list stored in l 
                                   // a new linked-list pointed to by the
                                   // head of the current object
                                   // and returns a reference to current object

Node* getNodeAt(int i);// returns a pointer to the ith node of the
                     // list pointed to by head. 0th node is head.

void delNode(int i); // removes the ith node of the list (if it exists)
                    // and makes the i-1th Node's next Node point to
                    // the i+1st node. In the case where i is 0 the
                    // 1st node becomes the new head of the list.

void insertNodeAt(Node *node, int i);
                    //place node between the i-1th node and the ith
                    //node in the List. In case i=0, node becomes
                    //the current head of the list and its next pointer
                    //points to the old head of the list.

Driver Program
==============

Here's what the driver program should do. It should have three lists:
num1, num2, and num3. 

It should use cin's get method to read character by character into two
arbitrarily long numbers into the List's num1 and num2.

For example if the user types the number:

123456

for to be input into num1. The the head node of num1 should contain
the int 6, the next node a 5, the next node a 4, etc.

On bogus inputs containing nondigits like:
1a344
(Here `a' is not a digit) it should print some error message and get another number.

Once your program has gotten these two numbers, it goes through 
the list num1 and num2 and makes a new list num3 which is the result
of adding num1 and num2. Finally, it prints out num3 to the screen.

A run of your program might look like:

Welcome to the addition program.
================================

Please enter a first number to add:
1234222 

Please enter a second number to add:
9795800

The sum of those two numbers was:
11030022

You should keep your code as easy to read as possible by using auxiliary 
functions. You should store the number in num3 with the head being the
most significant digit. i.e., in the above example the value contained
in the head node of num3 is 1.


Point Breakdown for HW3
=======================
If the submit program didn't collect your file
because you misnamed it or you did not follow
the required formatting instructions in the syllabus
you will get a 0 without an opportunity for a regrade.

If your driver program doesn't test something as described above, 
then you won't receive credit for it.

How well your code is commented.........1pt.
Node class has interface  
      as described......................1pt.
Node implements interface correctly.....1pt.
List class has interface
      as described......................1pt.
List implements interface correctly.....1pt.
Driver program works get num1 and num2
   into List's as described.............1pt. 
Bogus inputs are checked for............1pt. 
num3 is the sum of num1 and num2 and
 is output correctly....................1pt.
============================================
Total...................................8pts