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";
}
|