02-12-2012, 05:20 PM
C/C++ Guides Extension
Recursion
Its not a C/C++ thing. Recursion can be implemented in "any language". Recursion is simply defined as having a function that calls itself inside of the function.
void badRecursion()
{
printf("This will eventually crash\n");
badRecursion();
}
The Function in the code above will call itself at an infinite number of times, until the application will crash.
A good example of recursion is the factorial number
int factorial(int number)
{
// If the number is 1 will return 1
if(number == 1)
return 1;
else
return num * factorial(num - 1); // Otherwise it will return number * factorial (number - 1)
}
Linked Lists
I know this is something that it is already implemented in C++/STL library, but Im only gonna show you the concepts of a linked list.
A linked list is a group of nodes that are linked together(the first node is linked to the second node, the second node is linked to the third node, till it reaches the last node.
2
Implementing a Linked LIst:
A linked list(simple linked list) contains a node that contains data, a tag, and a pointer to the next node structure:
C/C++
struct node{
int tag;
type Data;
node * next;
};
c++(Class method)
class node{
private:
int tag;
type data;
node *next;
public:
//public methods get/set
int getTag();
void setTag(int tag);
type getData();
void setData(type data);
node *getNextNode();
void setNextNode(Node *Next);
};
class LinkedList{
private:
int length;
node *first;
public:
void insertAfter(node * element);
void insertBeginning();
void removeAfter(node * element);
void removeBeginning();
int getLength();
};
Double linked lists are the same, but there is another member in the node structure, the previous node.
Queue
A queue is a Simple linked list that that works by the FIFO(first in first out) principle, the data is added at the beginning of the list(Queue), and its taken out at the End of the list(Queue).
2
A queue has a Head(last element) and a tail(first element);
class Queue{
private:
int length;
node *head;
node *tail;
public:
void addBefore(node * element);
void removeAfter();
int getLength();
};
Stack
A stack is the opposed of a queue, works with the by LIFO(last in first out) principle, the data is added at the end of the stack and its taken out at the beginning of the stack.
2
A stack has as elements 2 elements BP(base pointer), and SP(stack pointer, I have used BP and SP because for representation have put the x86 model).
class Stack{
private:
int length;
node *BP;
node *SP;
public:
void addAfter(node * element);
void removeAfter();
int getLength();
};
Heap
A heap is like a family tree, very node in heap has a parents, and childs, the root node does not have a parent.
2
struct node{
int tag;
type data;
node *Left, *Right, *parent;
};
class heap{
private:
node*root, *last, *first;
public:
void Insert(type data);
void remove(node root)
}.;