Chapter 2: Basic Abstract Data Types. Problem 2.20

Implement a circular queue where --
1. A pointer to the first element is kept.
2. Length of the queue is kept.

//problem 2.20 - circular queue - keep pointer to first element + length.

#include <iostream>
using namespace std;

const int MAXLENGTH = 10; 

class CIRQUEUE
{
    int list[MAXLENGTH]; 
    int front; 
    int length;

public: 
    //Constructor
    CIRQUEUE(); 
    bool QEmpty() { return !length; }
    bool QFull() { return length == MAXLENGTH ? true : false; }  
    bool EnQueue(int val); 
    bool DeQueue(int& val); //OUTPUT = val
    void PrintQ(); 
}; 

CIRQUEUE::CIRQUEUE()
{
    memset(list, 0, sizeof(list)); 
    front = length = 0; 
}

bool CIRQUEUE::EnQueue(int val)
{
    if( QFull() )
    {
        cout << "ERROR: Queue is full" << endl;
        return false;
    }

    list[(front+length)%MAXLENGTH] = val; 
    length++; 
    return true; 
}

bool CIRQUEUE::DeQueue(int& val) //OUTPUT = val
{
    if( QEmpty() )
    {
        cout << "ERROR: Queue is empty" << endl;
        return false;
    }

    val = list[front]; 
    front = (front+1)%MAXLENGTH; 
    length--; 
    return true; 
}

void CIRQUEUE::PrintQ()
{
    if( QEmpty() )
    {
        cout << "EMPTY CIRQUEUE." << endl;
        return; 
    }

    cout << "CIRQUEUE is ---->" << endl;

    int curr = front; 
    for ( int n = 0; n < length; n++ ) 
    {
        cout << list[curr] << " ";  
        curr = (curr+1)%MAXLENGTH; 
    }
    cout << endl << "<---- END of CIRQUEUE" << endl;
}

//Little driver program to test this
void main()
{
    CIRQUEUE q; 
    q.PrintQ(); 
    int val = 0;

    cout << endl << "EnQueuing 10 elements.. " << endl;
    for( val = 0; q.EnQueue(val); val++) 
        q.PrintQ();

    cout << endl << "DeQueuing 5 elements.. " << endl;
    q.DeQueue(val);
    q.PrintQ(); 
    q.DeQueue(val);
    q.PrintQ(); 
    q.DeQueue(val);
    q.PrintQ(); 
    q.DeQueue(val);
    q.PrintQ(); 
    q.DeQueue(val);
    q.PrintQ(); 

    cout << endl << "EnQueuing 10 elements.. " << endl;
    for( val = 0; q.EnQueue(val); val++) 
        q.PrintQ();
}

Chapter 2: Basic Abstract Data Types. Problem 2.16.2

Implement a DeQueue (Double ended Queue) using an linked list.

//DeQueue implemented via a linked list.
//no restrictions on the size of the queue since we are using a linked list.

#include <iostream>
using namespace std; 

struct NODE
{
    int nVal; 
    NODE* next;
}; 

class DEQUEUE
{
    NODE* front; 
    NODE* back; 
public:
    DEQUEUE() { front = back = NULL; } 
    bool IsQueueEmpty() { return ( front == NULL && back == NULL ) ? true : false; } 
    bool FrontInsert( int elem ); 
    bool BackInsert( int elem ); 
    bool FrontDelete(); 
    bool BackDelete(); 
    void Print(); 
}; 

bool DEQUEUE::FrontInsert( int elem )
{
    //allocate a new NODE. 
    NODE* newNode = new NODE; 
    newNode->nVal = elem; 
    newNode->next = front; 
    front = newNode; 
    if( !back )
    {
        //newNode is the first node. 
        //back also points to the same node. 
        back = front; 
    }
    return true;
}

bool DEQUEUE::BackInsert( int elem )
{
    //allocate a new NODE. 
    NODE* newNode = new NODE; 
    newNode->nVal = elem; 
    newNode->next = NULL; 
    if( IsQueueEmpty() )
    {
        //newNode is the first node.
        back = front = newNode;
    }
    else
    {
        back->next = newNode; 
        back = newNode;
    }
    return true;
}

bool DEQUEUE::FrontDelete()
{
    if( IsQueueEmpty() )
    {
        cout << "Queue is empty." << endl; 
        return false;
    }

    NODE* nodeDelete = front; 
    front = front->next; 
    delete nodeDelete; 

    if( !front )
    {
        //nodeDelete was the last node.
        back = NULL;
    }
    return true;
}

bool DEQUEUE::BackDelete()
{
    if( IsQueueEmpty() )
    {
        cout << "Queue is empty." << endl; 
        return false;
    }

    NODE* nodeDelete = back; 
    if( front == back )
    {
        //nodeDelete is the last node. 
        front = back = NULL; 
    }
    else
    {
        NODE* prevBack = front; 
        for( ; prevBack->next != back; prevBack = prevBack->next ); 
        back = prevBack; 
        back->next = NULL; 
    }
    delete nodeDelete; 
    return true;
}

void DEQUEUE::Print()
{
    cout << "DEQUEUE is --> " << endl << endl;
    if( IsQueueEmpty() )
    {
        cout << " EMPTY QUEUE " << endl;
    }
    else
    {
        NODE* curr = front; 
        for( ;curr != NULL; curr = curr->next ) 
            cout << "[" << curr->nVal << "]" ; 
        cout << endl;
    }
    cout << "<-- DEQUEUE END." << endl << endl;
}

//A little program that uses the queue
void main()
{
    DEQUEUE q; 
    q.Print(); 
    //front insert elements in the queue. 
    q.FrontInsert(1); 
    q.FrontInsert(2); 
    q.FrontInsert(3); 
    q.FrontInsert(4); 
    q.FrontInsert(5); 
    q.Print();
    //back insert elements in the queue. 
    q.BackInsert(6);
    q.BackInsert(7);
    q.BackInsert(8);
    q.BackInsert(9);
    q.BackInsert(10);
    q.Print(); 
    //Delete 2 elements from front.
    q.FrontDelete(); 
    q.FrontDelete(); 
    q.Print(); 
    //Delete 2 elements from back.
    q.BackDelete(); 
    q.BackDelete(); 
    q.Print(); 

    //Delete everything else. 
    q.BackDelete(); 
    q.BackDelete(); 
    q.BackDelete(); 
    q.Print(); 
    q.FrontDelete(); 
    q.FrontDelete(); 
    q.FrontDelete(); 
    q.Print(); 
}
    

Chapter 2: Basic Abstract Data Types. Problem 2.16.1

Implement a DeQueue (Double ended Queue) using an array.

//DEQUEUE is a type of QUEUE data structure where elements can be inserted/deleted at both ends.

#include <iostream>
using namespace std;

const int MAXLENGTH = 10; 
//Double ended Queue - implemented via an array 
class DEQUEUE
{
    int last; //points to the last element. -1 if queue is empty. 
    int list[MAXLENGTH]; 
public:
    DEQUEUE(); 
    bool IsQueueEmpty() { return last == -1 ? true : false; }  
    bool IsQueueFull() { return last+1 == MAXLENGTH ? true : false; }
    bool FrontInsert(int elem); 
    bool BackInsert(int elem); 
    bool FrontDelete(); 
    bool BackDelete(); 
    void Print(); 
}; 

DEQUEUE::DEQUEUE()
{
    last = -1; 
    memset(list, 0, sizeof(list)); 
}

bool DEQUEUE::FrontInsert(int elem)
{
    if( IsQueueFull() )
    {
        cout << "Queue is full." << endl;
        return false;
    }
    if( !IsQueueEmpty() )
    {
        //if the q is not empty, make space for this element by shifting 
        //every other element downwards.
        for( int n = last+1; n > 0; n-- )
            list[n] = list[n-1]; 
    }
    list[0] = elem; 
    last++; 
    return true; 
}

bool DEQUEUE::BackInsert(int elem)
{
    if( IsQueueFull() )
    {
        cout << "Queue is full." << endl;
        return false;
    }
    last++; 
    list[last] = elem; 
    return true;
}

bool DEQUEUE::FrontDelete()
{
    if( IsQueueEmpty() )
    {
        cout << "Queue is empty." << endl;
        return false;
    }
    if( last != 0 )
    {
        //if there are more than one elements in the list... 
        //move all elements one step upwards.
        for( int n = 0; n < last; n++ )
            list[n] = list[n+1]; 
    }
    last--; 
    return true;
}

bool DEQUEUE::BackDelete()
{
    if( IsQueueEmpty() )
    {
        cout << "Queue is empty." << endl;
        return false;
    }
    last--; 
    return true;
}

void DEQUEUE::Print()
{
    cout << "DEQUEUE is --> " << endl << endl;
    if( IsQueueEmpty() )
    {
        cout << " EMPTY QUEUE " << endl;
    }
    else
    {
        cout << "Elements in Queue: [" << last+1 << "]" << endl;
        for( int n=0; n<last+1; n++ )
            cout << "[" << list[n] << "]"; 
        cout << endl;
    }
    cout << "<-- DEQUEUE END." << endl << endl;
}

//A little program that uses the queue
void main()
{
    DEQUEUE q; 
    q.Print(); 
    //front insert elements in the queue. 
    q.FrontInsert(1); 
    q.FrontInsert(2); 
    q.FrontInsert(3); 
    q.FrontInsert(4); 
    q.FrontInsert(5); 
    q.Print();
    //back insert elements in the queue. 
    q.BackInsert(6);
    q.BackInsert(7);
    q.BackInsert(8);
    q.BackInsert(9);
    q.BackInsert(10);
    q.Print(); 
    //Delete 2 elements from front.
    q.FrontDelete(); 
    q.FrontDelete(); 
    q.Print(); 
    //Delete 2 elements from back.
    q.BackDelete(); 
    q.BackDelete(); 
    q.Print(); 
}

Chapter 2: Basic Abstract Data Types. Problem 2.15

Circular Queues. 

Lets take a look at what a circular queue is -->  

If we wish to implement a queue using an array, we are faced with the inherent problem of deletion that plagues arrays - to delete an element, all elements after it need to be moved up - which is time consuming. 
One way out of this is to create a circular queue - where the list is imagined to be a circle. 
Lets look at an example. 

Lets take a queue of length 4. Initially all elements are empty - represented by E. 

E   E   E   E
F
B

F = Front pointer
B = Back pointer 

Queue is a First In First Out (FIFO) structure - think of a queue at a bank. 

When F = B, queue is empty. 
An element is added at B position. After adding the element, B points to the next empty space. This next step is circular -- that is when B reaches the end, it start over again from the start. 
An element is deleted at F position. After deleting the element, F points to the next element (again in circular order). 

Lets add some data to this queue. 

Initial position --> Empty Queue. 
E   E   E   E
F
B

Add 1 to the queue. 
1   E   E   E
F
    B

Add 2 to the queue. 
1   2   E   E
F
        B

Add 3 to the queue. 
1   2   3   E
F
            B

Add 4 to the queue. 
1   2   3   4
F
B

Notice a problem here. F = B but the queue is full! So how do we distinguish an empty queue from a full one? 

One strategy is to always leave one element empty - so this the above case, 
only three elements will fit in a queue of length 4. 
If B + 1 (in circular sense) = F, queue is Full. 

Another strategy is to keep a bit that represents an empty queue. 
If bit = 1 and F = B, queue is empty. 
If bit = 0 and F = B, queue is full. 

The problem is to implement this solution by keeping an extra bit.   

#include <iostream>
using namespace std;

const int MAXLENGTH = 10; 

class QUEUE
{
    int list[MAXLENGTH]; 
    int front; 
    int back;
    bool bQEmpty; 

public: 
    //Constructor
    QUEUE(); 
    bool QEmpty() { return bQEmpty ? true : false; }
    bool QFull() 
    { 
        if( (front == back) && !bQEmpty )
            return true;
        return false;
    }

    bool EnQueue(int val); 
    bool DeQueue(int& val); //OUTPUT = val
    void PrintQ(); 
}; 

QUEUE::QUEUE()
{
    memset(list, 0, sizeof(list)); 
    front = back = 0; 
    bQEmpty = true;
}

bool QUEUE::EnQueue(int val)
{
    if( QFull() )
    {
        cout << "ERROR: Queue is full" << endl;
        return false;
    }

    list[back] = val;
    back = (back+1)%MAXLENGTH; //circular
    if( bQEmpty )
        bQEmpty = false;
    return true; 
}

bool QUEUE::DeQueue(int& val) //OUTPUT = val
{
    if( QEmpty() )
    {
        cout << "ERROR: Queue is empty" << endl;
        return false;
    }

    val = list[front]; 
    front = (front+1)%MAXLENGTH; 
    if( front == back )
        bQEmpty = true;
    return true; 
}

void QUEUE::PrintQ()
{
    if( QEmpty() )
    {
        cout << "EMPTY QUEUE." << endl;
        return; 
    }

    cout << "QUEUE is ---->" << endl;

    //Printing this is a bit tricky :) 
    int n = front; 
    if( front == back ) //special case - queue is full.
    {
        cout << list[n] << " ";
        n = front+1;
    }

    for ( ; n != back; n=(n+1)%MAXLENGTH)
        cout << list[n] << " ";  

    cout << endl << "<---- END of QUEUE" << endl;
}

//Little driver program to test this
void main()
{
    QUEUE q; 
    q.PrintQ(); 
    int val = 0;

    cout << endl << "EnQueuing 10 elements.. " << endl;
    for( val = 0; q.EnQueue(val); val++) 
        q.PrintQ();

    cout << endl << "DeQueuing 5 elements.. " << endl;
    q.DeQueue(val);
    q.PrintQ(); 
    q.DeQueue(val);
    q.PrintQ(); 
    q.DeQueue(val);
    q.PrintQ(); 
    q.DeQueue(val);
    q.PrintQ(); 
    q.DeQueue(val);
    q.PrintQ(); 

    cout << endl << "EnQueuing 10 elements.. " << endl;
    for( val = 0; q.EnQueue(val); val++) 
        q.PrintQ();
}
    
    
            

Chapter 2: Basic Abstract Data Types. Problem 2.10

Problem 2.10. We wish to store a list in an array A whose cells consist of two fields,
data to store an element and position to give the (integer0 position of the element.
An integer last indicates that A[0] through A[last] are used to hold the list.
The type LIST can be defined by

type
    LIST = record
        last := integer;
        elements: array[1.. maxlength] of record
              data: elementtype;
              position: integer
        end
end;

//problem 2.10. 

#include <iostream>
#include <string>
using namespace std;

struct REC
{
    int nData;
    int nPos; //starts from 1. 
}; 

struct LIST
{
    int nLast; //points to the last element in the list.
              //size of the list = nLast+1
    REC list[10];     //Statically allocated for simplicity. 
                    //This would be replaced by a pointer to an array in a
                    //profressional program.
}; 

void CreateList(LIST* listStr); 
bool ListHasSpace(LIST* listStr); 
void PrintList(LIST* listStr); 
bool AddElementToList(LIST* listStr, int data, int pos); 
void DeleteElemAtPos(LIST* listStr); 

void main()
{
    LIST listStr; 
    memset(&listStr,0,sizeof(listStr)); //memset to set everything to 0. 
                                  //elements with 0 position are invalid as position starts with 1.
    listStr.nLast = 9; //10-1 because the list can only hold 10 objects for now

    //Create the list by taking user input
    CreateList(&listStr); 
    cout << "List created." << endl;
    PrintList(&listStr); 
    string sAns = "n"; 
    while(1)
    {
        DeleteElemAtPos(&listStr);
        PrintList(&listStr); 
        cout << "Continue with deletions (y/n)?:"; 
        cin >> sAns;  
        if( sAns[0] == 'n' || sAns[0] == 'N' )
            break;
    }
}

void CreateList(LIST* listStr)
{
    if( !listStr )
        return; 

    while( ListHasSpace(listStr) )
    {
        int data = 0;
        int pos = 0;

        PrintList(listStr); 
        
        cout << "Enter the data for element in the list:"; 
        cin >> data; 
           cout << endl; 
        cout << "Enter the position of this data item in the list:"; 
        cin >> pos;
        
        if( !AddElementToList(listStr, data, pos) )
        {
            cout << "Invalid position." << endl;
        }
    }
}

//Returns true if there are empty elements in the list. 
//Empty elements are defined by a position of 0. 
bool ListHasSpace(LIST* listStr)
{
    if( !listStr )
        return false;

    for( int n = 0; n < listStr->nLast+1; n++ )
    {
        if( listStr->list[n].nPos == 0 )
            return true; 
    }
    return false;
}

void PrintList(LIST* listStr)
{
    if( !listStr )
        return; 
    if( listStr->nLast <= 0 )
        return; 

    cout << "List --------> " << endl;
    for( int n = 0; n < listStr->nLast+1; n++ )
    {
        if( listStr->list[n].nPos == 0 )
            cout << "<Empty Element>" << endl;
        else
            cout << "Data [" << listStr->list[n].nData << "]" << " Pos [" << listStr->list[n].nPos << "]." << endl;
    }
    cout << "<----------- End of List" << endl;
}

//true if element can be successfully added - which means there is space in the list as well as position is unique
bool AddElementToList(LIST* listStr, int data, int pos)
{
    if( !listStr )
        return false;
    if( pos == 0 )
        return false;

    //first validate if this position already exists in the list or not. 
    //if it does, error out
    //and while we are traversing the list, find the next empty space too. 
    int nPositionInList = -1; 
    for( int n = 0; n < listStr->nLast+1; n++ )
    {
        if( nPositionInList == -1 && listStr->list[n].nPos == 0 )
            nPositionInList = n;
        if( listStr->list[n].nPos == pos )
        {
            //something is already there at this position. 
            return false;
        }
    }
    if( nPositionInList == -1 )
    {
        return false;
    }
    //all set to add the element
    listStr->list[nPositionInList].nData = data;
    listStr->list[nPositionInList].nPos = pos;
    return true;
}

void DeleteElemAtPos(LIST* listStr)
{
    if( !listStr )
        return;

    int pos = -1; 
    cout << "Enter position of element to delete: " << endl;
    cin >> pos;

    if( pos == 0 )
    {
        cout << "Invalid Position." << endl;
        return;
    }

    if( listStr->nLast <= 0 )
    {
        cout << "List is empty." << endl;
           return;
    }    

    //assumption: the list does not contain duplicate elements with the same position.
    int posToDelete = -1;
    //find the element that needs to be deleted.
    for( int n = 0; n < listStr->nLast+1; n++ )
    {
        if( listStr->list[n].nPos == pos )
        {
            posToDelete = n; 
            break;
        }
    }
    if( posToDelete == -1 )
    {
        cout << "Could not find element with position [" << pos << "]." << endl;
        return;
    }
    cout << "Element at position [" << pos << "] will be deleted." << endl; 
    //Delete the element at the position by overwriting this with elements after it. 
    for( int n = posToDelete; n < listStr->nLast; n++ )
    {
        listStr->list[n].nData = listStr->list[n+1].nData;
        listStr->list[n].nPos = listStr->list[n+1].nPos;
    }
    //one element less from the array. 
    listStr->nLast--; 
}

Chapter 2: Basic Abstract Data Types. Problem 2.9

The following procedure was intended to remove all occurances of element x from list L. Explain why it doesn't always work and suggest a way to repair the procedure so it performs its intended task. 

procedure delete (x : elementtype; var L: LIST); 
    var
        p: position
    begin
        p := FIRST(L);
        while p <> END(L) do begin
            if RETRIEVE(p,L) = x then
                DELETE(p,L);
        p := NEXT(p,L);
    end
end; {delete}

In the above problem, you can't just delete the NODE without adjusting the previous pointer to point to the node after the one to be deleted.

Chapter 2: Basic Abstract Data Types. Problem 2.8

Write a function to interchange the elements at position p and NEXT(p) in a singly linked list.

//program to exchange two nodes. 
//2 cases are important -- 
//If the node is the head node, in which case the head pointer needs to be adjusted.
//If the node is not the head node, it is a simple swap.

#include <iostream>
using namespace std;

struct NODE
{
    int nValue;
    NODE* next;
}; 

void CreateList(NODE** head); 
void PrintList(NODE* head); 
void ExchangeNodes(NODE** head, int nodeToExchange); 

void main()
{
    NODE* head = NULL; 
    CreateList(&head); 
    PrintList(head);
    ExchangeNodes(&head, 1); 
    PrintList(head);
    ExchangeNodes(&head, 5);
    PrintList(head);
}

void CreateList(NODE** head)
{
    if( !head )
        return;
    
    NODE* current = *head;
    for( int i = 1; i < 11; i++ )
    {
        NODE* newNode = new NODE;
        if( !newNode )
            return;
        newNode->nValue = i;
        newNode->next = NULL; 

        if( current == NULL )
        {
            //first node
            current = newNode;
            *head = current;
        }
        else
        {
            current->next = newNode;
            current = newNode;
        }
    }
}

void PrintList(NODE* head)
{
    if( !head )
        return;

    cout << "List is --> " << endl;
    for( NODE* current = head; current != NULL; current = current->next )
        cout << "[" << current->nValue << "]" << endl;
}

void ExchangeNodes(NODE** head, int nodeToExchange)
{
    if( !head )
        return;
    NODE* prev = NULL;
    NODE* curr = *head;
    for( ; curr != NULL; curr = curr->next )
    {
        if( curr->nValue == nodeToExchange )
            break;
        prev = curr;
    }

    if( !curr )
    {
        cout << "Element " << nodeToExchange << " not found." << endl;
        return;
    }
    if( curr->next == NULL )
    {
        cout << "Element " << nodeToExchange << " found but its next is NULL." << endl;
        return;
    }

    //we need to exchange
    if( prev == NULL )
    {
        //curr is the first node and we need to change the head of the list.
        NODE* temp = curr->next;
        *head = temp; //the list now starts with the second node
        prev = temp->next; 
        temp->next = curr; 
        curr->next = prev;
    }
    else
    {
        //curr is not the first node. 
        NODE* temp = curr->next->next;
        prev->next = curr->next;
        curr->next = temp;
        prev->next->next = curr;
    }
}

Chapter 2: Basic Abstract Data Types. Problem 2.7

//2.7 -- implement a linked list to store a binary number. 
//each node should store one bit. 
//add a recursive operation to increment this binary number. 

#include <iostream>
#include <string>
using namespace std;

//each node stores one bit. 
struct NODE
{
    unsigned char bit; //The smallest data type in C is a char.
    NODE* next;
}; 

bool ValidateBinaryNumberString(const string& sBinaryNumberStr); 
int RecursiveIncBinaryNumber(NODE* node); 
void CreateListForBinaryNumber(NODE** head, const string& sBinaryNumberStr); 
void PrintBinaryNumber(NODE* head); 
void IncrementBinaryNumber(NODE** head); 
int RecursiveIncBinaryNumber(NODE* node);

void main()
{
    cout << "Enter the binary number --> " << endl;
    string sBinaryNumber; 
    cin >> sBinaryNumber; 
    if( !ValidateBinaryNumberString(sBinaryNumber) )
    {
        cout << "Binary number in invalid format. Valid number can contain only 1 or 0 characters." << endl;
        return;
    }
    //Lets create a linked list to represent this binary number. 
    //the MSB is stored in the head and LSB just before the tail.
    NODE* head = NULL;
    CreateListForBinaryNumber(&head, sBinaryNumber); 
    PrintBinaryNumber(head); 
    IncrementBinaryNumber(&head); 
    PrintBinaryNumber(head);
}

bool ValidateBinaryNumberString(const string& sBinaryNumberStr)
{
    if( !sBinaryNumberStr.length() )
        return false;

    for(int n=0; n<sBinaryNumberStr.length(); n++)
    {
        if( sBinaryNumberStr[n] != '0' && sBinaryNumberStr[n] != '1' )
           return false;
    }
    return true;
}    
    
void CreateListForBinaryNumber(NODE** head, const string& sBinaryNumberStr)
{
    if( !head )
        return; 
    if( !sBinaryNumberStr.length() )
        return;

    NODE* curr = NULL;

    for( int n=0; n<sBinaryNumberStr.length(); n++ )
    {
        NODE* newNode = new NODE;
        newNode->bit = sBinaryNumberStr[n] == '1' ? 1 : 0; 
        newNode->next = NULL;

        if( *head == NULL )
            *head = newNode;
        else
            curr->next = newNode;
        curr = newNode;
    }
}

void PrintBinaryNumber(NODE* head)
{
    if( !head )
        return; 

    cout << "Binary Number is --> " << endl;
    for( NODE* curr = head; curr != NULL; curr=curr->next )
    {
        if( curr->bit )
            cout << "1"; 
        else
            cout << "0";
    }
    cout << endl << "<-- End of Binary Number." << endl;
}

void IncrementBinaryNumber(NODE** head)
{
    if( !head )
        return; 

    int nBitToAdd = RecursiveIncBinaryNumber(*head); 
    //This takes care of the case where there is a carry over from the Most signinficant bit.
    if( nBitToAdd )
    {
        //We need to add a new node for this bit. 
        NODE* newNode = new NODE; 
        newNode->bit = 1;
        NODE* temp = *head; 
        *head = newNode;
        newNode->next = temp;
    }
}

//Recursively adds one to the binary number. 
//returns a 1 if there is a carry over otherwise 0. 
int RecursiveIncBinaryNumber(NODE* node)
{
    if( !node )
        return 0; 

    int nBitToAdd = 1; //This starts with 1 because we want to add 1 to the binary number.
    if( node->next )
        nBitToAdd = RecursiveIncBinaryNumber(node->next);

   if( nBitToAdd )
   {
        if( node->bit == 0 )
        {
            nBitToAdd = 0; 
             node->bit = 1;
        }
   }
   return nBitToAdd; 
}
                

        

Chapter 2: Basic Abstract Data Types. Problem 2.4

//program to concatenate list of lists into a single list 
//in this program, number of lists are 10. 

#include <iostream>
using namespace std;

struct NODE
{
    int nValue;
    NODE* next;
}; 

void CreateLists(NODE** lists, int nLists); 
NODE* CreateSortedList(int nStart, int nInc, int nTotal); 
void PrintLists( NODE** list, int nLists); 
void PrintList( NODE* list); 
NODE* ConcatLists(NODE** lists, int nLists); 

void main()
{
    //array of sorted lists
    NODE* lists[10] = { 0 }; //Note: In C, there is no easy way to initialize all elements (not considering memset) - except if you want to initialize
                             //all elements to 0 - which is what I want in this case. 
                             
    CreateLists(lists,sizeof(lists)/sizeof(lists[0])); 
    PrintLists(lists,sizeof(lists)/sizeof(lists[0])); 
    NODE* newList = ConcatLists(lists, sizeof(lists)/sizeof(lists[0]));
    PrintList(newList); 
}

void CreateLists(NODE** lists, int nLists) //Pass array by reference
{
    if( !lists )
        return;

    int nStart = 0; 
    int nInc = 2; 
    for( int n = 0; n < nLists; n++ )
    {
        lists[n] = CreateSortedList(nStart,nInc,10); 
        //Just to add some variety to the lists created
        nStart += 10; 
        if( nInc == 2 )
            nInc = 1; 
        else 
            nInc = 2; 
    }
}

//Creates a sorted list of nTotal elements. 
//First element assigned a value nStart. 
//Second element = nStart+nInc
//and so on...
NODE* CreateSortedList(int nStart, int nInc, int nTotal)
{
    NODE* head = NULL;
    NODE* curr = NULL;
    for( int i = 0; i < nTotal; i++ )
    {
        NODE* newNode = new NODE; 
        newNode->nValue = nStart; 
        newNode->next = NULL;
        if( !head )
        {
            //first node
            head = newNode;
            curr = head;
        }
        else
        {
            //second node onwards
            curr->next = newNode;
            curr = curr->next;
        }
        nStart += nInc; 
    }
    return head;
}
        
void PrintLists( NODE** list, int nLists)
{
    for( int n = 0; n < nLists; n++ )
    {
        PrintList(list[n]);
    }
}

void PrintList( NODE* list)
{
    if( !list )
    {
        cout << "Empty list." << endl;
        return;
    }
    cout << "List is --> " << endl;
    for( NODE* curr = list; curr != NULL; curr = curr->next )
        cout << curr->nValue << " "; 
    cout << endl << "<-- End of list." << endl;
}

//the main function that does the concatenation 
NODE* ConcatLists(NODE** lists, int nLists)
{
    if( !lists )
        return NULL; 

    NODE* newList = NULL; 
    NODE* currList = NULL;
    NODE* endOfNewList = NULL;

    //Run the loop for all but the last list cause it just needs to be appended
    for( int n = 0; n < nLists-1; n++ )
    {
        currList = lists[n]; 
        if( !newList )
            newList = currList;
        else
            endOfNewList->next = currList;
        //Find the end of this list for next iteration
        for( endOfNewList = currList; endOfNewList->next != NULL; endOfNewList = endOfNewList->next ); 
    }
    endOfNewList->next = lists[nLists-1]; 
    return newList; 
}

Chapter 2: Basic Abstract Data Types. Problem 2.3.b

//program to merge n sorted lists
//in this program, n = 10. 

#include <iostream>
using namespace std;

struct NODE
{
    int nValue;
    NODE* next;
}; 

void CreateLists(NODE** lists, int nLists); 
NODE* CreateSortedList(int nStart, int nInc, int nTotal); 
void PrintLists( NODE** list, int nLists); 
void PrintList( NODE* list); 
NODE* MergeAllSortedLists(NODE** lists, int nLists); 
bool MoreThanOneListRemaining(NODE** lists, int nLists); 

void main()
{
    //array of sorted lists
    NODE* lists[10] = { 0 }; //Note: In C, there is no easy way to initialize all elements (not considering memset) - except if you want to initialize
                             //all elements to 0 - which is what I want in this case. 
                             
    CreateLists(lists,sizeof(lists)/sizeof(lists[0])); 
    PrintLists(lists,sizeof(lists)/sizeof(lists[0])); 
    NODE* newList = MergeAllSortedLists(lists, sizeof(lists)/sizeof(lists[0]));
    PrintList(newList); 
}

void CreateLists(NODE** lists, int nLists) //Pass array by reference
{
    if( !lists )
        return;

    int nStart = 0; 
    int nInc = 2; 
    for( int n = 0; n < nLists; n++ )
    {
        lists[n] = CreateSortedList(nStart,nInc,10); 
        //Just to add some variety to the lists created
        nStart += 10; 
        if( nInc == 2 )
            nInc = 1; 
        else 
            nInc = 2; 
    }
}

//Creates a sorted list of nTotal elements. 
//First element assigned a value nStart. 
//Second element = nStart+nInc
//and so on...
NODE* CreateSortedList(int nStart, int nInc, int nTotal)
{
    NODE* head = NULL;
    NODE* curr = NULL;
    for( int i = 0; i < nTotal; i++ )
    {
        NODE* newNode = new NODE; 
        newNode->nValue = nStart; 
        newNode->next = NULL;
        if( !head )
        {
            //first node
            head = newNode;
            curr = head;
        }
        else
        {
            //second node onwards
            curr->next = newNode;
            curr = curr->next;
        }
        nStart += nInc; 
    }
    return head;
}
        
void PrintLists( NODE** list, int nLists)
{
    for( int n = 0; n < nLists; n++ )
    {
        PrintList(list[n]);
    }
}

void PrintList( NODE* list)
{
    if( !list )
    {
        cout << "Empty list." << endl;
        return;
    }
    cout << "List is --> " << endl;
    for( NODE* curr = list; curr != NULL; curr = curr->next )
        cout << curr->nValue << " "; 
    cout << endl << "<-- End of list." << endl;
}

//the main function that does the sorting
NODE* MergeAllSortedLists(NODE** lists, int nLists)
{
    if( !lists )
        return NULL; 

    NODE* newList = NULL;
    NODE* nodeToTake = NULL; 
    NODE* currNode = NULL;
    int nListToInc = 0; //This points to the list from a node is taken

    //Continue until we have just one list left
    while( MoreThanOneListRemaining(lists,nLists) )
    {
        nListToInc = -1; 
        for( int n = 0; n < nLists; n++ )
        {
            //find the node that we want to append to our new list
            if( lists[n] )
            {
                if( nodeToTake )
                {
                    if( nodeToTake->nValue > (lists[n])->nValue )
                    {
                        nodeToTake = lists[n]; 
                        nListToInc = n; 
                    }
                }
                else
                {
                    nodeToTake = lists[n]; 
                    nListToInc = n; 
                }
            }
        }
        if( nListToInc == -1 )
        {
            cout << "Error in logic." << endl;
            return NULL;
        }
        else
        {
            lists[nListToInc] = (lists[nListToInc])->next; 
        }
        //we have our node that we want to append to the new list
        if( !newList )
        {
            newList = nodeToTake;
            currNode = newList;
        }
        else
        {
            currNode->next = nodeToTake;
            currNode = currNode->next;
        }
        nodeToTake = NULL;
    }

    //At this point, we'll have one list left
    NODE* lastList = NULL;
    for( int n = 0; n < nLists; n++ )
    {
        if( lists[n] )
        {
            lastList = lists[n]; 
            break;
        }
    }
    if( lastList )
        currNode->next = lastList;

    return newList;
}

//returns true if valid elements in array > 1.
//return false if valid elements in array <= 1. 
bool MoreThanOneListRemaining(NODE** lists, int nLists)
{
    if( !lists )
        return false;
    int nCount = 0;
    for( int n = 0; n < nLists; n++ )
    {
        if( lists[n] )
            nCount++;
    }
    return (nCount > 1 ? true : false);
}

Chapter 2: Basic Abstract Data Types. Problem 2.3.a

// a program to merge two sorted lists
//

#include <iostream>
using namespace std;

struct NODE
{
    int nValue;
    NODE* next;
}; 


void CreateList1(NODE** list)
{
    if( !list )
        return;

    int array[] = { 1, 2, 3, 5, 6 };
    NODE* curr = NULL;  
    for( int i = 0; i < sizeof(array)/sizeof(array[0]); i++ )
    {
        NODE* newNode = new NODE;
        newNode->nValue = array[i]; 
        newNode->next = NULL;

        //insert it
        if( curr == NULL )
        {
            //first node
            curr = newNode;
            *list = curr;
        }
        else
        {
            //second node onwards
            curr->next = newNode;
            curr = newNode;
        }
    }
}

void CreateList2(NODE** list)
{
    if( !list )
        return;

    int array[] = { 0, 1, 4, 5, 6 };
    NODE* curr = NULL;  
    for( int i = 0; i < sizeof(array)/sizeof(array[0]); i++ )
    {
        NODE* newNode = new NODE;
        newNode->nValue = array[i]; 
        newNode->next = NULL;

        //insert it
        if( curr == NULL )
        {
            //first node
            curr = newNode;
            *list = curr;
        }
        else
        {
            //second node onwards
            curr->next = newNode;
            curr = newNode;
        }
    }
}

void PrintList( NODE* list)
{
    if( !list )
        return;

    cout << "List is --> " << endl;
    for( NODE* curr = list; curr != NULL; curr = curr->next )
        cout << "[" << curr->nValue << "]" << endl;
    cout << "<-- End of list." << endl;
}

NODE* MergeTwoLists( NODE* list1, NODE* list2 )
{
    if( !list1 || !list2 )
        return NULL;

    NODE* newList = NULL; 
    NODE* currNode = NULL; 
    NODE* nodeToTake = NULL;  

    while( list1 && list2 )
    {
        if( list1->nValue <= list2->nValue )
        {
            //We take this node.
            nodeToTake = list1; 
            list1 = list1->next;
        }
        else
        {
            nodeToTake = list2;
            list2 = list2->next; 
        }

        if( newList == NULL )
        {
            newList = nodeToTake;
            currNode = nodeToTake;
        }
        else
        {
            currNode->next = nodeToTake;
            currNode = currNode->next;
        }
    }

    if( list1 )
    {
        //append list 1 to the new list
        currNode->next = list1; 
    }
    else
    {
        //append list 2 to the new list
        currNode->next = list2;
    }
    return newList; 
}

void main()
{
    NODE* list1 = NULL; 
    NODE* list2 = NULL;    
    CreateList1(&list1);
    CreateList2(&list2);
    PrintList(list1);
    PrintList(list2);
    NODE* mergeList = MergeTwoLists(list1, list2); 
    PrintList(mergeList);
}

Chapter 2: Basic Abstract Data Types. Problem 2.2.b

//implement a list as linked list

#include <iostream>
using namespace std;

struct NODE
{
    int nValue;
    NODE* next;
}; 

void Delete(NODE** head, int elemToDelete); 
void CreateList(NODE** head); 
void PrintList(NODE* head); 
void Insert( NODE** head, int elemToInsert); 

void main()
{
    NODE* head = NULL; 
    CreateList(&head); 
    PrintList(head);
    Insert(&head, 0);
       Insert(&head, 11); 
    PrintList(head); 
    Delete(&head,0); 
    Delete(&head, 11);
    Delete(&head, 4);
    PrintList(head); 
}

void CreateList(NODE** head)
{
    if( !head )
        return;
    
    NODE* current = *head;
    for( int i = 1; i < 11; i++ )
    {
        NODE* newNode = new NODE;
        if( !newNode )
            return;
        newNode->nValue = i;
        newNode->next = NULL; 

        if( current == NULL )
        {
            //first node
            current = newNode;
            *head = current;
        }
        else
        {
            current->next = newNode;
            current = newNode;
        }
    }
}

void PrintList(NODE* head)
{
    if( !head )
        return;

    cout << "List is --> " << endl;
    for( NODE* current = head; current != NULL; current = current->next )
        cout << "[" << current->nValue << "]" << endl;
}

void Insert( NODE** head, int elemToInsert )
{
    if( !head )
        return; 

    NODE* prev = NULL; //this points to the element after which we need to insert the element. 
    NODE* current = *head;
    for( ; current != NULL; current = current->next )
    {
        if( current->nValue > elemToInsert )
            break;
        else
            prev = current;
    }

    NODE* newNode = new NODE; 
    newNode->nValue = elemToInsert;
    newNode->next = NULL; 

    if( prev == NULL )
    {
        //we need to insert the element at the head of the list
        newNode->next = *head; 
        *head = newNode;
    }
    else
    {
        //we need to insert the element after prev
        NODE* temp = prev->next; 
        prev->next = newNode;
        newNode->next = temp; 
    }
}

void Delete(NODE** head, int elemToDelete)
{
    if( !head )
        return;

    NODE* prev = NULL; 
    NODE* current = *head;

    for( ;current != NULL; current = current->next )
    {
        if( current->nValue == elemToDelete )
            break;
        else
            prev = current;
    }

    if( current == NULL )
    {
        //element not found.. nothing to be deleted. 
        cout << "element not found" << endl;
    }
    else
    {
        //current points to the element that needs to be deleted.
        //prev points to the one before current
        if( prev == NULL )
        {
            //head node needs to be deleted
            *head = (*head)->next; 
        }
        else
        {
            prev->next = current->next;
        }
        delete current;
    }
}

Chapter 2: Basic Abstract Data Types. Problem 2.2.a

//list as an array - provide insert(), delete() and locate() functionality

#include <stdio.h>

void list_delete( int* array, int& size, int elemToDelete ); 
int locate( int* array, int size, int elemToLocate); 
void insert( int* array, int& size, int elemToInsert ); 
void PrintArray( int* array, int size); 

void main()
{
    int array[100];
    array[0] = 1;
    array[1] = 2;
    array[2] = 3;
    array[3] = 4;
    array[4] = 5;
    array[5] = 6;
    array[6] = 7;

    int size = 7; //current size of the array. 

    //lets use the functions.
    int pos = -1;
    pos = locate( array, size, 0 );
    if( pos == -1 )
        printf("element 0 not found." ); 
    else
        printf("element 0 found at position [%d].\n", pos );

    pos = locate(array, size, 6);
    if( pos == -1 )
        printf("element 6 not found." ); 
    else
        printf("element 6 found at position [%d].\n", pos );

    PrintArray(array, size); 

    //insert
    insert( array, size, 0);
       insert( array, size, 10 ); 
    insert( array, size, 11 ); 
    
    PrintArray( array, size);
    
    //delete
    list_delete( array, size, 0 ); 
    list_delete( array, size, 1 ); 
    list_delete( array, size, 2 ); 

    PrintArray( array, size ); 
}

int locate( int* array, int size, int elemToLocate)
{
    for( int i = 0; i < size; i++ )
    {
        if( array[i] == elemToLocate )
            return i;
    }
    return -1;
}

void insert( int* array, int& size, int elemToInsert )
{
    //find position of where to insert the elem
    int i; 
    for( i=0; i< size; i++ )
    {
        if( array[i] > elemToInsert )
            break;
    }

    if( i != size ) 
    {
        //we need to move the array in right direction
        for( int j = size; j > i; j-- )
        {
            array[j] = array[j-1];
        }
    }
    array[i] = elemToInsert;
    size++; 
}

void list_delete( int* array, int& size, int elemToDelete )
{
    //find pos of element to delete.
    int i;
    for( i = 0; i < size; i++ )
    {
        if( array[i] == elemToDelete )
            break;
    }
    if( i == size-1 )
    {
        //last elem needs to be deleted
        size--; 
    }
    else if( i == size )
    {
        //element not found
    }
    else
    {
        /* need to move the elements to the left. */ 
        for( int j = i; j < size-1; j++ )
            array[j] = array[j+1];
        size--; 
    }
}

void PrintArray( int* array, int size)
{
    printf("\n Array is --> \n" );
    printf("\n");
    for( int i = 0; i < size; i++ )
    {
        printf("[%d]\n", array[i] );
    }
    printf("\n");
    printf("End of array.\n");
}