Results 1 to 3 of 3

Thread: For your enjoyment, A demonstration of C++ programming.

  1. #1
    Join Date
    Dec 2007
    Location
    Somewhere in Idaho
    Posts
    480
    Mentioned
    0 Post(s)
    Quoted
    0 Post(s)

    Default For your enjoyment, A demonstration of C++ programming.

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

  2. #2
    Join Date
    Aug 2006
    Location
    London
    Posts
    2,021
    Mentioned
    2 Post(s)
    Quoted
    0 Post(s)

    Default

    i like it

    you see this though
    Code:
    const int MAX_SIZE = 1000000000;
    isnt there an exact value for the largest int?

    maybe use UINT_MAX from <climits>
    Join the Official SRL IRC channel. Learn how to Here.

  3. #3
    Join Date
    Dec 2007
    Location
    Somewhere in Idaho
    Posts
    480
    Mentioned
    0 Post(s)
    Quoted
    0 Post(s)

    Default

    Quote Originally Posted by Yakman View Post
    i like it

    you see this though
    Code:
    const int MAX_SIZE = 1000000000;
    isnt there an exact value for the largest int?

    maybe use UINT_MAX from <climits>
    There is. And it can be determined by something like max = floor(pow(2, size_of(int) * 8));

    However, the assignment (this was a school assignment) was specific in that the max size of a node was 999,999,999.

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Similar Threads

  1. Programming
    By aciid phreek in forum Who Are You ? Who ? Who ?
    Replies: 3
    Last Post: 02-15-2008, 04:18 PM
  2. Programming
    By rkroxpunk in forum News and General
    Replies: 10
    Last Post: 05-21-2007, 09:41 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •