Saturday, October 19, 2013

Doubly Linked List

So after spending so much more time than I ever want to spend on linked lists, I've written what I believe to be working code for it.

//Node.h
struct Node
{
    unsigned int val;
    Node* next;
    Node* prev;
};

//linkedlist.h

struct Node;

class LinkedList
{
    Node* front;
    Node* back;
    unsigned int size;
public:
    LinkedList();
    ~LinkedList();
    void pushBack(int val);
    void popBack();
    void pushFront(int val);
    void popFront();
    int getFront();
    int getBack();
    bool isEmpty();
};

linkedlist.cpp
#include"linkedList.h"
#include"Node.h"

LinkedList::LinkedList()
    : front(nullptr), back(nullptr), size(0) {}

LinkedList::~LinkedList()
{
    while(!isEmpty())
        popFront();
}

void LinkedList::pushBack(int val)
{
    Node* t = new Node();
    t->val = val;
    t->next = nullptr;

    if(!front) //if there is no list make t front and back
        front = back = t;
    else
    {
        back->next = t;
        t->prev = back;
        back = t;
    }
    size++;
}

void LinkedList::popBack()
{
    if(back)
    {
        if(front == back)
        {
            delete back;
            back = front = nullptr;
        }
        else
        {
            Node* t = back->prev;
            t->next = nullptr;
            delete back;
            back = t;
        }
        size--;
    }
}

void LinkedList::pushFront(int val)
{
    Node* t = new Node();
    t->val = val;
    t->prev = nullptr;

    if(!front)
        front = back = t;
    else
    {
        front->prev = t;
        t->next = front;
        front = t;
    }
    size++;
}

void LinkedList::popFront()
{
    if(front)
    {
        if(front == back)
        {
            delete front;
            front = back = nullptr;
        }
        else
        {
            Node* t = front->next;
            t->prev = nullptr;
            delete front;
            front = t;
        }
        size--;
    }
}

int LinkedList::getBack()
{
    return back->val;
}

int LinkedList::getFront()
{
    return front->val;
}

bool LinkedList::isEmpty()
{
    return (!size);
}

This is pretty similar to the code for the Single Linked List that we went over in class, but it makes it so much easier to popBack. Instead of having to start at the front of the list and looping through every node to get to the one before the end, you can just put Back->prev into a temp pointer.

The only "downside" of this is that you do have one more member variable to keep track of and you need to be setting the prev pointer to null when you popFront.

Now that that part's done, time to attempt an Iterator!

Monday, September 23, 2013

Basic Math

 This is a pretty basic program that adds, subtracts, multiplies, or divides 2 numbers based on user input. I used a #define to create a shortcut for std::cout and the same can be done for std::endl if you wish to reduce how much typing you have to do.

Another interesting function I used is isDigit(x) which is part of the ctype.h library. It will return 0 if x is not a digit and something other than 0 if it is a digit. The reason I looped through the entire string is that if someone were to input 5gg and I only checked the first character it would come back as true and my atoi conversion would pick it up as only a 5, which could give unintended results. Since argv[] can be treated as a string I know it will end with a null byte and I just loop through to check every character till I reach the end.


#include<iostream>
#include<cstring>
#include<cstdlib>
#include<ctype.h>

#define COUT std::cout

int main(int argc, char *argv[])
{
    bool valid;
  
    if (argc == 4)
    {
        for(int i = 0; argv[1][i] != '\0'; i++) //checks if 1st argument is all digits
        {
            if(!isdigit(argv[1][i]))
                valid = false;  
        }
      
        for(int i = 0; argv[3][i] != '\0'; i++) //checks if 3rd argument is all digits
        {
            if(!isdigit(argv[3][i]))
                valid = false;  
        }

        if(valid)
        {
            double leftSide = atof(argv[1]);
            double rightSide = atof(argv[3]);

      
            //checks if 3rd argument is a valid operator then calculates - else prints error message
            if(strcmp(argv[2], "+") == 0)
                COUT << leftSide + rightSide << std::endl;
            else if(strcmp(argv[2], "-") == 0)
                COUT << leftSide - rightSide << std::endl;
            else if(strcmp(argv[2], "x") == 0)
                COUT << leftSide * rightSide << std::endl;
            else if(strcmp(argv[2], "/") == 0)
                COUT << leftSide / rightSide << std::endl;
            else
                COUT << "bm <number> <+-x/> <number>" << std::endl;
        }
        else
            COUT << "bm <number> <+-x/> <number>" << std::endl;
    }
    else
        COUT << "bm <number> <+-x/> <number>" << std::endl;

   
    return 0;
}