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). How pointers work. And OOp.
Code:#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; }





). How pointers work. And OOp.
Reply With Quote






