Friday, November 14, 2014

Back to programming!

Finally we started programming again and moved on from all that nonsense of playing board games and whatnot. Part of this course we need to write weekly blogs so I will be more active again.

So in this course we have 3 assignments.

Assignment 1 - Create a linked list and a Binary search tree. (Almost done with this)
Assignment 2 - Consists of writing a webserver
Assignment 3 - Create our own 3D game and engine using DirectX.

So this week I will share my thoughts on Assignment 1. So I actually did create a linked list and a binary search tree a few months ago with the help from youtube, especially from Paul Programming .
It's not very hard. The hard part is keeping track of your pointers.

This week we also learned how to use templates in programming to make our programming more generic. I still have problems using templates in a effective way but I gave it a try and made a linked list and BST (Binary search tree) with templates in mind. at first I got a bunch of errors that made no sense but I fast started to get a hand of how the syntax was supposed to look. Though I'm still struggling with some things, For example when working with normal classes you can forward declare instead of using #include "headername.h" you just write class classname; before the class where you want to use it, so I wrote this:


( class LinkedList;                         //normal way to write a forward declare )

template<typename T>               //this is the way I tried with no success
class LinkedList<T>;


template <typnename T>
class TestModule
{
public:
                  LinkedList();
                  ~LinkedList();

private:
........
........
}

So I still have to figure out how to do that and also another thing I had problem with was how to use another template as a function parameter in a function that is part of class template. Like so:

template <typnename T>
class TestModule
{
public:
bool VerifyListErase(LinkedList<T> _List, const std::string& _Message);

.........
.........
}
If you read this and know how to solve this please feel free to comment below. I will write here again when I find a good solution. It's probably not that hard.
Recursion
So on to what I liked about this week. Recursion! Using recursive functions can be really useful but sometimes they might be tricky to understand. It is basically a function that calls itself within the function creating a loop. 

Below is a search function I wrote that starts the search in the binary search tree from the node that is entered in and search through the whole tree/sub tree for a specific key/data. If a match is found the boolean variable _Match is set to true.



If no match is found the function calls itself and goes to the left and does the whole thing over again until it’s not possible to go left anymore. Then the function moves upwards one step and then tries to go right. It searches through every node until something is found or not found. 

It technically moves through the tree like the red numbers below show. If new to the concept it’s quite hard to grasp so I will try to explain it again.  What happens when a function calls itself is that it goes deeper and deeper until the end and then it returns up one step and does the next instruction. if there is no instruction it goes up another step and checks and so on.

So for example looking at the picture below and starting at 1 the function goes left every iteration until it can't go left more and when number 5 is reached and no match is found the function moves up one step to number 6 and then calls the function again but now with parameter to go right. So it goes to number 7, when nothing is found it moves up to number 8 and then 9 and then goes right again down to 10 and then back up and so on until all nodes have been searched..



If you want to see my code here is a link to Bitbucket. You can use my code freely but if something breaks it’s not my fault. J

No comments:

Post a Comment