Fall 2000 PIC 10b HW3 Solutions Page

Return to homework page.

//
// File: pic10bhw3file1.h
//
// Contents: Contains interface for the Node and List classes.
//
//


#ifndef List_H
#define List_H


// Class name: Node
//
// Purpose: Serves as a base unit for a linked-list. Contains a data Item
//          and a link to the next Node.
//
// Remark: Future homeworks will use templates          
//
// Known Bugs: none 

class Node
{
   public:
 	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

    private:
	int item;
	Node *next;

};

// Class name: List
//
// Purpose: a class for singly linked list. Supports member functions
//          to create a list, add, search for and delete nodes.
//          Also can check if two lists equal.
//
// Remark: Interface a bit clunky but hey that eans you can't
//         go and download it from some other web-site.         
//
// Known Bugs: none 

class List
{
    public:

	List(); 
			// creates a node equal to NULL.

	List(const List& list);
			// copy constuctor. Makes a new List and the elements
                       // in the nodes pointed to by the head of this
                       // object should be the same as those in list.
                      
 
	~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& list); 
				// copies the linked-list stored in list     
                                // 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.

    private:
	Node* head;
};
#endif


//
// File: pic10bhw3file2.cpp
//
// Contents: Contains implementations of the Node and List Classes.
//
//


#include<iostream.h>
#include<stddef.h>
#include<stdlib.h>
#include "pic10bhw3file1.h"

//
//
// Node class member functions
//
//

// Function name: Node()
//
// Purpose: Default constructor. Sets up a node where the item is 0 and next
//          NULL                    
//
// Known Bugs: none
 
Node::Node()
{
	item=0;
	next=NULL;
}

// Member Function name: Node(int i, Node *n) 
//
// Purpose: Constructor to creates a node where the item is i and next node
//          is n                      
//
// Known Bugs: none

Node::Node(int i, Node *n)
{
	item=i;
	next=n;	
}
	
// Member Function name: Node
//
// Purpose: Copy constructor. Copies the Node in node into the current 
//          object                   
//
// Known Bugs: none

Node::Node(const Node& node)
{
	item=node.item;
	next=node.next;
}

// Member Function name: ~Node
//
// Purpose: Destructor. Does nothing since no dynamically allocated          
//          data
// Remark: Just to get use to the idea of having a destructor 
Node::~Node()
{
}

// Member Function name: operator= 
//
// Purpose: Checks if two items have the same item and next  
//                    
//
// Known Bugs: none

Node& Node::operator=(const Node& node)
{
	item=node.item;
	next=node.next;
	return *this;
}

// Member Function name: setItem
//
// Purpose: set the item of the Node to be i                      
//
// Known Bugs: none

void Node::setItem(int i)
{
	item=i;
}

// Member Function name: getItem()
//
// Purpose: returns the item stored in the node.  
//                    
//
// Known Bugs: none

int Node::getItem()
{
	return item;
}

// Member Function name: setNext()
//
// Purpose: sets the value of the next pointer of the current Node.
//                    
//
// Known Bugs: none

void Node::setNext(Node *n)
{
	next=n;
} 

// Member Function name: getNext()
//
// Purpose: returns the next pointer of the current Node.  
//                    
//
// Known Bugs: none

Node* Node::getNext()
{ return next;
}

//
//
// List Class member functions
//
//



// Member Function name: List()
//
// Purpose:  creates an empty list                    
//
// Known Bugs: none

List::List()
{
	head=NULL;
}

// Member Function name: List(const List& l)
//
// Purpose: Copy constructor. Copies each node of l into the  
//          into nodes of current object.          
//
// Known Bugs: none

List::List(const List& l)
{
	Node *prev, *ctmp;

	if(l.head ==NULL){ 
				head=NULL;
				return;
			}
	head = prev = new Node(*(l.head));

	for(Node* tmp=l.head->getNext(); tmp !=NULL; tmp=tmp->getNext())
	{
		ctmp = new Node(*tmp);
		prev->setNext(ctmp);
		prev=ctmp;
	} 
}

// Member Function name: ~List()
//
// Purpose: Destructor. Deletes the nodes stored in the current List 
//                    
//
// Known Bugs: none

List::~List()
{
	Node *tmp=head,*prev;

	while(tmp !=NULL)
	{
		prev=tmp;
		tmp=tmp->getNext();
		delete prev;
	}
}

// Member Function name: operator=(const List& l) 
//
// Purpose: checks if two lists are Node-wise equal  
//          That is, their Nodes have same items.          
//
// Known Bugs: none

List& List::operator=(const List& l)
{
	Node *prev, *ctmp;


	if(this == &l) return *this;

	if(l.head ==NULL){ 
				head=NULL;
				return *this;
			}

	head = new Node(*(l.head));
	prev = head;

	for(Node* tmp=l.head->getNext(); tmp !=NULL; tmp=tmp->getNext())
	{
		ctmp = new Node(*tmp);
		prev->setNext(ctmp);
		prev = ctmp;
	} 

	return *this;	
}

// Member Function name: getNodeAt
//
// Purpose: returns the node at location i in the list.  
//          If i is beyond end of List returns NULL.           
//
// Known Bugs: none

Node* List::getNodeAt(int i)
{
	Node* tmp =head;

	for(int j=0; j < i; j++)
	{
		if(tmp==NULL) return NULL;
		tmp=tmp->getNext();
	}

	return tmp;
}

// Member Function name: delNode
//
// Purpose: Delete's the node at location i if it exists.   
//          Otherwise give an error.          
//
// Known Bugs: should be more elegant.

void List::delNode(int i)
{
	Node* tmp, *prev;

	if(i==0) prev=head;
 
	else prev = getNodeAt(i-1);

	if(prev==NULL) {
		cout << "delete" << i << " failed2\n";
		return;
	}

	tmp = prev->getNext();

	if(i == 0) { head =tmp;
		    delete prev;}

	else {prev->setNext(tmp->getNext());
	     delete tmp;}
}

// Member Function name: insertNodeAt
//
// Purpose: add Node node between location i-1 and i in the current list      
//
// Known Bugs: should be more elegant.

void List::insertNodeAt(Node *node, int i)
{
	Node *tmp, *prev;

	if(node==NULL ) {
		cout << "insert" << i << " failed2\n";
		return;
	}

	if(i==0) {
			tmp = head; 
		        head = node;
			head->setNext(tmp);
			return;
		 }	

        prev = getNodeAt(i-1);
	if(prev==NULL ) {
		cout << "insert" << i << " failed3\n";
		return;
	}
	tmp = prev->getNext(); 
	prev->setNext(node);
	node->setNext(tmp);
}

//
// File: pic10bhw3file3.cpp
//
// Contents: Contains the main driver program.
//
//

#include<iostream.h>
#include "pic10bhw3file1.h"

//
// Functions Prototypes
//

List ReadNum(); // reads an arbitrarily long number from keyboard

void SumNum(List num1, List num2, List& num3);
		// adds num1 to num2 to create num3

void OutputNum(List n); //Outputs the number stored in n.

// Function name: main()
//
// Purpose: Driver of adder program. Call ReadNum twice to  
//          get inputs from the user, then call SumNum to add them,          
//          finally calls OutputNum to print out the result.
//
// Known Bugs: none

int main()
{
	List num1, num2, rnum3;


	cout << "Welcome to the addition program.\n";
	cout << "================================\n\n";
	cout << "Please enter a first number to add:\n";

	num1= ReadNum();
	
	cout << "Please enter a second number to add:\n";

	num2= ReadNum();

        cout << "\nThe sum of those two numbers was:\n";

	SumNum(num1,num2,rnum3);

	OutputNum(rnum3);	

	return 0;
}

// Function name: Readnum()
//
// Purpose: Returns a List whose Node's item's consists of decimal digits
//          List is gotten from the keyboard. If a non-decimal digit
//          is entered a warning is printed and a new input is gotten.        
//
// Known Bugs: none

List ReadNum()
{
	List *tmp;
	Node *tmpNode;
	char c='0';
	bool flag=true, flag2=true;
	
	while(flag) // keeps going till get non-bogus input
	{
		tmp = new List();
		flag =false;

		while (flag2) //keeps going till see a carriage return
		{
		   cin.get(c);

		   if(!flag && c<='9' && c>='0') 
                                          //only add if
                                          //if input line not bogus so far
                                          //and current char is a digit
	 	   { 			
                                tmpNode = new Node(c-'0',NULL);
	 		   	tmp->insertNodeAt(tmpNode,0);
		   }

		   else if( c== '\n') flag2=false; //end of current line

		   else flag=true; //input is bogus 	
		}
		if(flag)
		{  cout << "Bogus input! Please re-enter that number:\n";
		   delete tmp;
                   flag2=true;
		}
	}

	return *tmp;

}

// Function name: SumNum(List num1, List num2, List& num3)
//
// Purpose: Add the numbers stored in reverse order in Lists num1 and num2
//          together producing the number stored in a List num3 stored  
//          in forward order.          
//
// Remark: We are essentially using the Lists as stacks.
//         List Copy constructor invoked for num1 and num2

void SumNum(List num1, List num2, List& num3)
{

	Node *tmpNode,*t1,*t2;
	int carry =0; //carry digit
	int value;   //sum of current digit of num1 and num2
	bool flag=true;
	
	while(flag) //keep adding till have reached of both num1 and num2
	{
		flag=false;

		t1= num1.getNodeAt(0);

		t2= num2.getNodeAt(0);
		
		value = carry;
		if(t1 !=NULL) 
		{
			flag=true;
			value +=t1->getItem();			
			num1.delNode(0);
		}
		if(t2 !=NULL) 
		{
			flag=true;
			value +=t2->getItem();
			num2.delNode(0);			
		}
		if(flag)
		{
			carry = value/10;
			tmpNode = new Node(value%10,NULL);
			num3.insertNodeAt(tmpNode,0);
		}
	}
}

// Function name: OutputNum(List n)
//
// Purpose: Prints out the number stored in n.                       
//
// Remark: List copy constructor invoked in creating n

void OutputNum(List n)
{
	Node* tmp;
	bool flag=true;

	while(flag)
	{		
		tmp = n.getNodeAt(0); //combined with delNode below
                                      //acts like a Stack pop.
		if (tmp != NULL)
		{
			cout << tmp->getItem();
			n.delNode(0);
		}
		else flag =false;		
	}
	cout << "\n";
}