boberman
2008-10-28 15:17:50
I thought it might be nice for some to see a demonstration of what a simple c++ program might look like. So, here is a Fibonacci generator, capable of generating Fibonacci numbers as big as you like.
This program demonstrates:
Partial doubly linked lists. operator overloads. Fairly good style (if I do say so myself :D). How pointers work. And OOp.
This program demonstrates:
Partial doubly linked lists. operator overloads. Fairly good style (if I do say so myself :D). How pointers work. And OOp.
#include <iostream>
#include <iomanip>
using namespace std;
/*************************************************************************
* Class: Node
* Description:
* This is a Node for a doubly linked list.
*************************************************************************/
class Node
{
public:
Node* getParent() const { return parent; }
Node* getChild() const { return child; }
int getData() const { return data; }
void setData(int inData);
void setChild(Node* inChild);
Node(int inData, Node* inParent, Node* inChild);
private:
Node* parent;
Node* child;
int data;
};
/*************************************************************************
* Class: BigNum
* Description:
* A double linked list that allows for the storage of very big numbers.
*************************************************************************/
class BigNum
{
public:
BigNum(int data=0);
BigNum(const BigNum& inBig);
~BigNum();
int getSize() const { return size; }
Node* getLast() const { return lastNode; }
BigNum& operator += (const BigNum& inNum);
BigNum& operator = (const BigNum& inNum);
private:
Node* firstNode;
Node* lastNode;
int size;
};
/*************************************************************************
* Node Constructor
* Description:
* Sets up the node.
*************************************************************************/
Node::Node(int inData, Node* inParent, Node* inChild)
{
parent = inParent;
child = inChild;
data = inData;
}
/*************************************************************************
* Member Function: setChild
* Description:
* Changes where the child node pointer points.
*************************************************************************/
void Node::setChild(Node* inChild)
{
child = inChild;
}
/*************************************************************************
* Member Function: setData
* Description:
* Changes the data in the node.
*************************************************************************/
void Node::setData(int inData)
{
data = inData;
}
/*************************************************************************
* BigNum Constructor
* Description:
* Sets up the BigNum. Creates the first node.
*************************************************************************/
BigNum::BigNum(int data)
{
size = 1;
firstNode = new Node(data, NULL, NULL);
lastNode = firstNode;
}
/*************************************************************************
* BigNum Copy Constructor
* Description:
* Creates a deep copy of BigNum.
*************************************************************************/
BigNum::BigNum(const BigNum& inBig)
{
size = inBig.size;
Node* inTemp = inBig.firstNode;
firstNode = new Node(inTemp->getData(), NULL, NULL);
Node* currNode = firstNode;
for (int i = 1; i < size; ++i)
{
inTemp = inTemp->getChild();
currNode->setChild(new Node(inTemp->getData(), currNode, NULL));
currNode = currNode->getChild();
}
lastNode = currNode;
}
/*************************************************************************
* BigNum Destructor
* Description:
* Deletes the BigNum object, ensures that memory is freed.
*************************************************************************/
BigNum::~BigNum()
{
Node* temp = firstNode;
for (int i = 0; i < size; ++i)
{
Node* curr = temp;
temp = temp->getChild();
delete curr;
}
}
/*************************************************************************
* Operator = for BigNum
* Description:
* Assignment operator that ensures that BigNum is freed up before
* assigning it anything.
*************************************************************************/
BigNum& BigNum::operator = (const BigNum& inNum)
{
// Delete any left over data
Node* temp = firstNode;
for (int i = 0; i < size; ++i)
{
Node* curr = temp;
temp = temp->getChild();
delete curr;
}
// Copy new data over
size = inNum.size;
Node* inTemp = inNum.firstNode;
firstNode = new Node(inTemp->getData(), NULL, NULL);
Node* currNode = firstNode;
for (int i = 1; i < size; ++i)
{
inTemp = inTemp->getChild();
currNode->setChild(new Node(inTemp->getData(), currNode, NULL));
currNode = currNode->getChild();
}
lastNode = currNode;
}
/*************************************************************************
* Operator += for BigNum
* Description:
* Overloads the += operator to allow two BigNums to be added to each
* other. This function is the most important for Fibonacci calculations.
*************************************************************************/
BigNum& BigNum::operator += (const BigNum& inNum)
{
// How big can a node before shifting it into a new node.
const int MAX_SIZE = 1000000000;
Node* currNode = firstNode;
Node* inCurrNode = inNum.firstNode;
int carryOver = 0;
int i = 0;
// Process each element of the two lists until we reach the end
// of either of the lists.
while (i < inNum.size && i < size)
{
int value[] = {currNode->getData(), inCurrNode->getData()};
currNode->setData((value[0] + value[1] + carryOver) % MAX_SIZE);
carryOver = (value[0] + value[1]) / MAX_SIZE;
// Prevents a segmentation fault that can occur.
if (currNode->getChild() != NULL)
{
currNode = currNode->getChild();
inCurrNode = inCurrNode->getChild();
}
++i;
}
// If the second list was smaller then the first,
// process any remaining carryovers
while (i < size && carryOver > 0)
{
int value = currNode->getData();
currNode->setData((value + carryOver) % MAX_SIZE);
carryOver = (value + carryOver) / MAX_SIZE;
if (currNode->getChild() != NULL)
{
currNode = currNode->getChild();
}
++i;
}
// If the second list is bigger then the first, add more nodes to the first
while (i < inNum.size)
{
int value = inCurrNode->getData();
currNode->setChild(new Node((value + carryOver)
% MAX_SIZE, currNode, NULL));
carryOver = (value + carryOver) / MAX_SIZE;
currNode = currNode->getChild();
++size;
++i;
}
// Process any remaining carry overs. At this point they should just
// be tagged onto the list.
if (carryOver > 0)
{
currNode->setChild(new Node(carryOver, currNode, NULL));
currNode = currNode->getChild();
++size;
}
lastNode = currNode;
return *this;
}
/*************************************************************************
* Operator << for ostream
* Description:
* Outputs a BigNum.
*************************************************************************/
ostream& operator << (ostream& out, const BigNum& big)
{
int size = big.getSize();
// Start from the end of the list and move up.
Node* curr = big.getLast();
for (int i = 0; i < size; ++i)
{
int data = curr->getData();
// Make sure that leading zeros are added to the output.
if (curr->getChild() != NULL)
{
out << setfill('0') << setw(9) << data;
}
else
{
out << data;
}
curr = curr->getParent();
}
return out;
}
/*************************************************************************
* Function: fib(int n)
* Description:
* Calculates a Fibonacci number for n, returns it as a type BigNum.
*************************************************************************/
BigNum fib(int n)
{
BigNum last(1);
BigNum value(0);
for (int i = 0; i < n; ++i)
{
BigNum temp(value);
value += last;
last = temp;
}
return value;
}
/*************************************************************************
* Function: main
* Description:
* Pipes data around. Mostly just executes the fib function.
*************************************************************************/
int main()
{
for (int i = 0; i < 350; ++i)
{
cout << fib(i) << endl;
}
return 0;
}