0
Posted March 2, 2011 by Spyros in C/C++ Programming
 
 

Essential Data Structures in C++

391px-Data_stack.svg
391px-Data_stack.svg

This tutorial is a simple explanation of some data structures that we can use in C++. I pretend you understand first how each structure works before you look at some code. However, we can’t avoid using some code and I ended adding templates of some structures. This tutorial doesn’t contain all data structures but I’m sure the most important ones are here and this will be a big help in improving your skills in C++.

Array

It’s a collection of elements of the same type directly accessed by an integer index;

Static Array: has a fixed number of elements and it’s allocated during compilation time;

Ex: int x[20];

Dynamic Array: it’s created using allocation techniques and dynamic memory management. Can be resized.

Ex: Int *x = new int [20];

File

It is an external data collection with an associated data structure named by “stream”; Direct Access – files in hard disk; Sequential access – files in tapes;

The reading operation withdraw data from an input stream;
The writing operation merges new data at the end of output stream;

Files are used to save large amounts of data;

Linked List

• Sequential collection of elements;
• No minimum or maximum limit of elements since it is resizable whether the elements are added or removed from the list;
• Doesn’t allow direct access;
• The elements can be disposed through a numeric or alphabetical ordering;
• The elements can be accessed in any position of the list;

The implementation of this structure can be done through an array (the implementation is limited to the array size) or through a Linked List (the structures are created dynamically).

A linked least is composed by nodes. Each node has two fields:
-the object including on the list;
-a pointer to the next element (node) of the list;

Characteristics:
-memory space filled by the list grow accordingly with the needs of the application;
-the operations add() and remove() elements are realized by the local manipulation of the pointers;

A template of the class Linked List that will help a lot:

template< class T>
class List{

    private:
        Node< T>* head;
        void destroylist();

    public:
        List(){head=NULL;};
        List(const List< T>& l);
        ~List();
        bool empty() const{ return head==NULL;};
        void add(int k,const T& elem);
        int lenght() const;
        void remove(int k,T& x);
        bool find(int k, T& x) const;
        const List< T>& operator = (const List< T>& l);
        void write(ostream& out) const;
};

Stack

•the elements are added and removed just by one side of the stack, the top;
•always an element is added or removed of the stack the top is updated;
•it’s a structure where is applied the LIFO order (Last In First Out);

Stacks are used in:
-Evaluation of Numerical Expressions;
-Recursion;

A template for the class Stack:

template< class T>
class Stack{

    private:
        Node< T>* top;
        void destroystack();
        const Stack< T>& invert();

     public:
         Stack(){ top=NULL;}
         Stack(const Stack< T>& s);
         ~Stack();
         bool empty() const{ return top==NULL;};
         void push(const T& elem); //insert an element on the top of the stack
         void pop(T& x); //remove the element on the top of the stack
         const T& top() const{ return top->info;}
         int lenght() const; //return stack lenght
         const Stack< T>& operator = (const Stack< T>& s);
         void write(ostream& ostr) const;
};

Queue

•The access to the elements it’s done using both sides of the queue;
•The elements are “removed” by the front of the queue;
•The elements are “added” by the back of the queue;
•The elements stay always in the same order they arrived which means we have a FIFO type order (First in, First Out);

Queues are used in waiting lists:
-simulation studies;
-Task escalation in operative systems;

Template of class Queue:

template< class T>
class Queue{

    private:
        Node< T>* begin;
        Node< T>* end;
        void destroyqueue();

    public:
        Queue< T>(){ begin=NULL; fim=NULL;};
        Queue< T>(const Queue< T>& q);
        ~Queue< T>();
        bool empty() const{ return begin==NULL;};
        void push_back(const T& elem);
        void pop_front(T& x);
        const T& front() const{ return begin->info;};
        const T& back() const{ return end->info;};
        int lenght() const;
        const Queue< T>& operator = (const Queue< T>& q);
        void write(ostream& ostr) const;
};

Dequeue

•Linear structure more general then the stacks and the queues;
•It’s a special type of queue where the removes and the adds can be done in the front or in the back of the queue;
•Like the queues this structure can be implemented with vector or linked list;

Simple template of Dequeue:

template< class T>
class DQueue: public Queue< T>{

    public:
        DQueue();
        DQueue(const Dequeue< T>& dq);
        ~DQueue();
        void push_front(const T& x);
        void pop_back(T& x);
};

And that’s it for today. Hope you learn something about data structures with this. Now it’s start practicing. Good work!

This is a guest post, thank you !


Spyros