Saturday, 27 September 2014

Doubly Linked List using c++

#include<iostream>
#include<stdlib.h>
#include<conio.h>
#include<string>

struct _node_student;

#define CREATE_NODE  ( struct _node_student* ) malloc(sizeof(_node_student) )

using namespace std;

// a struct to represent a student in a queue as a node of a doubly linked list
struct _node_student{
    //the student number
    unsigned int _std_num = 0;
    //pointer to next student node
    _node_student* next;
    //pointer to previous student node
    _node_student* prev;

} *ptr;


//class implementing a doubly linked list for queue at the department


class Queue{
    //total students PROCESSED  in queue at any instance 
    unsigned int _ttl_stdnt_procsd;

    //pointer to front of the queue
    _node_student* front;
    //pointer to end of the queue
    _node_student* end;

public:

    //constructor
    Queue(){
        _ttl_stdnt_procsd = 0;

        //make fornt and end point eachother
        front = CREATE_NODE;
        end = CREATE_NODE;

        front->next = NULL;
        front->prev = NULL;

        end->prev = front;
        end->next = NULL;

        front->next = end;
    }

    //accessor and manipulation functions
    void  addAtHead(unsigned int _ttl_stud);
    void  addAfter(unsigned int _stud_num);
    void  addBefore(unsigned int _stud_num);
    void  removeStudent(unsigned int num);
    void display();

    //getter and setter for total student processed
    int getTtlStdProcsd(){ return _ttl_stdnt_procsd; };
    void incrmntTtlStdProcsd(){ ++_ttl_stdnt_procsd; };


};


//functions add students at the end of queue
void Queue::addAtHead(unsigned int _ttl_stud)
{
    //get the  student number of first student  to be added this time as index
    unsigned int  index = getTtlStdProcsd() + 1;

    // update total student
    _ttl_stud += getTtlStdProcsd();

    //add all students at at end of the queue
    while (index <= _ttl_stud)
    {


        //get  end  student node already in queue
        _node_student* u = CREATE_NODE;
        u = end->prev;


        //create a new student node and initialise its number
        _node_student* v = CREATE_NODE;

        //update the queue by adding student node v after u in the queue
        v->next = end;
        v->prev = u;
        v->_std_num = index;


        u->next = v;
        end->prev = v;


        ++index;

        //increment total student processed
        incrmntTtlStdProcsd();
    }


}



// test function to display the queue

void Queue::display()
{
    ptr = CREATE_NODE;
    ptr = front->next;
    while (ptr->next != NULL)
    {
        cout << ptr->_std_num << " ";
        ptr = ptr->next;
    }



}


// add a student node before his/her's best  friend ;)
void Queue::addBefore(unsigned int _stud_num) {

    ptr = CREATE_NODE;
    ptr = front->next;
    while (ptr->_std_num != _stud_num)
    {

        ptr = ptr->next;

    }

    _node_student* v = CREATE_NODE;
    _node_student* u = CREATE_NODE;


    u = ptr->prev;

    //add v before his friend _stud_num
    v->next = ptr;
    v->prev = ptr->prev;

    ptr->prev = v;
    u->next = v;

    incrmntTtlStdProcsd();
    v->_std_num = getTtlStdProcsd();



}


// add a student node after his/her's best  friend :P
void Queue::addAfter(unsigned int _stud_num)
{
    ptr = CREATE_NODE;
    ptr = front->next;
    while (ptr->_std_num != _stud_num)
    {

        ptr = ptr->next;

    }

    _node_student* v = CREATE_NODE;
    _node_student* w = CREATE_NODE;

    w = ptr->next;

    //add v after student _stud_num
    v->next = ptr->next;
    v->prev = ptr;

    w->prev = v;
    ptr->next = v;

    incrmntTtlStdProcsd();
    v->_std_num = getTtlStdProcsd();


}


// kick out students from the queue
void Queue::removeStudent(unsigned int _stud_num)
{


    for (unsigned int i = 0; i < _stud_num; ++i)
    {
        _node_student* tmp = front;
        front = front->next;
        free(tmp);

    }


}




No comments:

Post a Comment