This is an introduction to algorithms programming in C.
Unlike C++ or Java, C itself does not support algorithms with its library. You need to write your own data structures to generate them.
For a first start, I will show how to implement some basic data structures in C, since they
are elementary for any algorithm you want to implement.
Top
A stack can be regarded as an array of data elements, that needs to be filled. There are 2 different kinds of stacks.
FIFO stack and LIFO stack.
FIFO is short for
First in, First out . That is, the first element that is added
to the array will also be the first to be removed.
LIFO is short for
Last in, First out . That is, the last element being added to
the array will be the first to be removed.
The
Stack pointer . Another important thing is, that all stacks, be it FIFO or LIFO have a so called stack pointer.
The stack pointer marks the last element of the array.
Push and
pop . Push and pop are the basic operations executed on a stack.
Push means, to add another item to the stack. Pop means, to remove another item from the stack.
Push and
pop are usually implemented as functions but they could also be implemented as a loop in the main program.
Implementing a LIFO stack. Now comes the fun. We are going to implement a LIFO stack. Before starting coding we
may need gather our basic informations about the stack.
Since its a LIFO stack, we may implement it as an array. Remember that LIFO means Last in, First out, so we need
to assure that the last element being added will be the first to be released. This is a rather straightforward operation,
since all arrays usually grow from bottom to top and we can simply remove the last element being added.
The code above shows possible implementations of push and pop . The implementation is hold easy to demonstrate their functionality.
In a real-world program you would have to check if the stack is empty or already filled, if the stack is full etc.
Push and
pop could than be used as follows:
This program is rather simple.
First it allocates space for the stack and then it uses push and pop operations to fill and empty the stack
Top
Lists are another basic and popular data structure.
Thats why some High Level programming languages like C++ and Java have implemented
them in their libraries. In C you need to build your own List. This is usually done with a struct.
typedef struct LinkedList
{
struct LinkedList* head;
struct LinkedList* next;
};
struct LinkedList list;
Having defined this list as a new data type you can use it like you would use any other elementary data type of C.
Basic List operations: Basic List operations are: insert an item, delete an item, move an item.
However, before doing any operation on lists, you need to allocate memory for the list
This function is rather simple. It allocates memory for the list dynamically as we have done with the stack. But it does a little bit more.
It also sets the pointer p as the one and only element, that is, it is the first and the last element of the list.
Top