Basic Algorithms in C

Basic Data Structures
Stacks Lists

Basic Data Structures

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


Stacks

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



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




Clicky Web Analytics