Find width of a tree pointed by head

Considering that the width of the tree is defined as the maximum number of nodes at any one level, the following code should hold good. Drop a comment if you think that this code s***s [:)]

public void maxWidthBST(NodeType rootNode)
        {
            int level=depthBST(rootNode);           
            int maxWidth=0;
            int intNodeCount=0;
            for(int counter=1; counter<=level;counter++)
            {
                intNodeCount = NodeCount(rootNode, counter);
                if(intNodeCount>maxWidth)
                {
                    maxWidth = intNodeCount;
                }   
            }
            Console.WriteLine(“The maximum width is: ” + maxWidth);
        }       

        public int NodeCount(NodeType root, int level)
        {
            int LWidth=0;
            int RWidth=0;
            int totalNodesAtLevel=0;
            if(level<=0) return 0;
            if(level==1)return 1;
            if(level>1)
            {
                if(root.Left !=null) LWidth=NodeCount(root.Left, level-1);
                if(root.Right !=null) RWidth= NodeCount(root.Right, level-1);
                totalNodesAtLevel = LWidth+RWidth;           
            }
            return totalNodesAtLevel;
        }

Advertisements

Finding if a string contains all unique characters.

I have used C# for this code snippet.


public class checkString
{
public static void Main()
{
string strSource = "ABCacd12";
if(CheckString1(strSource))
{
Console.WriteLine("Unique!!!");
}
else
{
Console.WriteLine("Not Unique!!!");
}
}

public static bool CheckString1(string str)
{
int strLength = str.Length;
for(int i=0;i<strLength;i++)
{
for(int j=i+1;j<strLength;j++)
{
if(str.ElementAt(i)==str.ElementAt(j)) return false;
}
}
return true;
}

}

Remove Duplicates from an Unsorted single linked list

void SLList::removeDuplicates()
{
    if(header)
    {
        Node *temp, *curChkNode, *last;
        temp=curChkNode=header;
        int curVal=0, length=0, counter=0;
        length=sllLength();
        cout<<"\nThe length of the list is:\t"<<length;
        while(counter!=length && curChkNode)
        {
            temp=curChkNode->next;
            curVal=curChkNode->data;
            while(temp)
            {
                if(curVal==temp->data)
                {
                    cout<<"\nA DUPLICATE IS PRESENT FOR:\t"<<curVal;
                    last->next=temp->next;
                }
                last=temp;
                temp=temp->next;
            }
            curChkNode=curChkNode->next;
            counter++;
        }   
    }
    else
    {
        cout<<"\nThe list is empty\n";
    }
    return;
}

C++ Compilation Error: error C2470: ‘SLList’ : looks like a function definition, but there is no parameter list; skipping apparent body

The compiler showed the error:

error C2470: ‘SLList’ : looks like a function definition, but there is no parameter list; skipping apparent body

I had coded this snippet using a notepad and hence after lots of head banging figured out that the issue was a stupid missed (:):

 

class SLList
{
    private:
        Node *header;
    public:
        SLList()
        {
            header=NULL;
        }
        void createList();
        void displayList();
        int sllLength();
        void removeDuplicates();
};

:::::::::::::

:::::::::::::::

int SLList:sllLength()
{
    int counter=0;
    if(header)
    {
        Node *temp;
        temp=header;
        while(temp)
        {
            counter++;
        }
        delete temp;
    }
    return counter;
}

 

should have been:

int SLList::sllLength()
{
    int counter=0;
    if(header)
    {
        Node *temp;
        temp=header;
        while(temp)
        {
            counter++;
        }
        delete temp;
    }
    return counter;
}

Design a doubly linked list and perform the following operations: 1)Add nodes to both front and rear 2)Display the list, 3)Delete nodes at front.tail and nth position

#include

using namespace std;

class Node
{
    public:
    int data;
    Node *prev, *next;
    Node()
    {
        data=NULL;
        prev=NULL;
        next=NULL;
    }   
};

class dll
{
    private:
        Node *header;
    public:
        dll(){
            header=NULL;
        }
        void createList();
        void displayList();
        void insertEnd();
        void deleteFirstNode();
        void deleteLastNode();
        void deleteNthNode();
};

void dll::deleteFirstNode()
{
    if(header)
    {
        Node *temp;
        temp=header;
        header=temp->next;
        header->prev=NULL;
        delete temp;
    }
    else
    {cout<<"\nThe list is empty!\n";}
    return;
}

void dll::deleteLastNode()
{
    if(header)
    {
        Node *temp, *last;
        temp=header;
        while(temp)
        {
            last=temp;
            temp=temp->next;
        }
        last->prev->next=NULL;
        delete last;
        delete temp;       
    }
    else
    {cout<<"\nThe list is empty!\n";}
    return;
}

void dll::deleteNthNode()
{
    if(header)
    {
        Node *temp, *last;
        temp=header;
        int position=0, counter=0;
        cout<<"Enter the node position that you want to delete: \t";
        cin>>position;
        if(position>=0)
        {
            while(counter!=position && temp)
            {
                last=temp;           
                temp=temp->next;
                counter++;
            }
            if(temp)
            {
            cout<<"\nThe node that you want to delete has value:\t\n"<data;
            last->prev->next=temp;
            temp->prev=last->prev;
            delete last;           
            }
            else{cout<<"\nThe list does not contain that many elements\n";}
        }
    }
    return;
}

void dll::insertEnd()
{
    if(header==NULL)
    {
        createList();
    }
    else
    {
        Node *newNode, *temp, *last;
        newNode=new Node;
        cout<<"Enter the value for the node:\t";
        cin>>newNode->data;
        temp=header;
        while(temp)
        {
            last=temp;
            temp=temp->next;
        }
        newNode->next=NULL; //newNode is the new last node
        newNode->prev=last;
        newNode->prev->next=newNode;           
    }
    return;
}

void dll::createList()
{
    int in_val;
    Node *temp;
    temp=new Node;
    cout<<"Enter the value for the node:\t";
    cin>>temp->data;
    if(header == NULL)
    {
        //This is the first node in the double linked list
        temp->next=NULL;
        temp->prev=NULL;       
    }
    else
    {
        //If this is a new node at the front of an already populated linkedlist
        temp->next=header;
        temp->next->prev=temp;
        header=temp;
    }
    header=temp;
    return;
}

void dll::displayList()
{
    Node *temp, *last;
    temp=header;
    cout<<"Display the list from first to last using the NEXT pointer.\n";
    while(temp)
    {   
        cout<data<<"\t"<<endl;
        last=temp;
        temp=temp->next;
    }
    /*if(last)
    {
        cout<<"Display the list from last to last using the PREV pointer.\n";
        while(last)
        {
            cout<data<<"\t"<<endl;
            last=last->prev;       
        }
    }*/
}

void main()
{
    cout<<"******This is a Doubly Linked List Demo******"<<endl;
    int choice=0;
    dll objDLL;
    do{
        cout<<"Enter the opration you want to perform: ";
        cout<<"\n1). Add a node at front of the list";
        cout<<"\n2). Display a node";
        cout<<"\n3). Add a node at end of the list";
        cout<<"\n4). Delete the node at head of the list";
        cout<<"\n5). Delete the node at tail of the list";
        cout<<"\n6). Delete the node at nth position of the list";
        cout<<"\n7). Exit\t";
    cin>>choice;
    switch(choice)
    {
        case 1: objDLL.createList(); break;
        case 2: objDLL.displayList(); break;
        case 3: objDLL.insertEnd(); break;
        case 4: objDLL.deleteFirstNode();break;
        case 5: objDLL.deleteLastNode();break;
        case 6: objDLL.deleteNthNode();break;
        case 7: exit(0);
        default: cout<<"\n Invalid operation/input detected. Please try again later.";
    }   
    }while(choice!=7);
}   

Creating a Stack using Linked List.

The operations to be supported:

1. PUSH

2. POP

3. Check if Empty

4. Check if Full

//I have just created the skeleton. Exception handling is not put in yet.

#include
using namespace std;

class stack
{
    public:
        stack();
        ~stack();
        void Push(int inData);
        int Pop();
        void display();
        bool IsEmpty();
    protected:
        typedef struct nodeT
        {
            int data;
            struct nodeT *next;   
        }node;
        node *firstElement;
};

//Class method implementation now
stack::stack()
{
    firstElement = NULL;
    return;
}

stack::~stack()
{
    node *next;
    while(firstElement)
    {
        next=firstElement->next;
        delete firstElement;
        firstElement=firstElement->next;
    }
    return;
}

void stack::Push(int inData)
{
    node *newNode = new node;
    newNode->data=inData;
    newNode->next=firstElement;
    firstElement = newNode;
    return;   
}

//Note that the Pop operation is intended to return the data stored in the top most node and free

//that space in the stack
int stack::Pop()
{
    node *nodeToPop;
    int data;
    nodeToPop=firstElement;
    firstElement=firstElement->next;
    data=nodeToPop->data;
    delete nodeToPop;
    return data;
}

bool stack::IsEmpty()
{
    if(!firstElement) return 1;
    else return 0;
}

void stack::display()
{
    node *ptr;
    ptr=firstElement;
    if(ptr)
    {
        cout<<"The stack elements are: "<<endl;
        while(ptr)
        {
            cout<data<<endl;
            ptr=ptr->next;
        }   
    }
    else
    {
        cout<<"There are no elements in the stack!!!!"<<endl;
    }
}

void main()
{
    stack objStack;
    int indata=0, choice=1;
    while(choice!=0)
    {
        cout<<"Stack Operations Main Menu: 1.Push 2.Pop    3.IsEmpty 4.IsFull 0.Exit"        

<<endl;
        cin>>choice;
        switch(choice)
        {
            case 0:
                exit(1); //Normal program Termination
            case 1:
                cout<<"Enter the number to Push: ";   
                cin>>indata;
                objStack.Push(indata);
                break;
            case 2:
                if(!objStack.IsEmpty())
                {
                cout<<"The number popped from the stack is: "<<objStack.Pop()       

            <<endl;
                }
                else {cout<<"Cannot pop from an empty stack!!!"<<endl;}
                break;
            case 3:
                cout<<"Checking if the stack is empty…";
                if(objStack.IsEmpty())
                {
                    cout<<"The stack is empty."<<endl;
                }
                else
                {
                    cout<<"The stack is not empty"<<endl;;
                }
                break;
            case 4:
                //TO Do
            default:
                cout<<"Illegal Action. Please try again!!!"<<endl;
        }
        objStack.display();
        cin.get();
    }   
}

Find the nth Element from last in a linked list.

/*
Find the nth Element from last in a linked list.
*/

#include

using namespace std;

struct node{int data; struct node *next;};

struct node* createlist()
{
    node *nodeHolder,*pointerToTheFirstNode, *temp;

    int elementCount=0;
    pointerToTheFirstNode = (node*)malloc(sizeof(node));
    temp=pointerToTheFirstNode;
    cout<<"Enter the number of elements you want in the list:    ";
    cin>>elementCount;
    cout<<endl;

    while(elementCount!=0)
    {
    temp->next=(node*)malloc(sizeof(node));
    cout<<"Enter the elements for the nodes:    ";
    cin>>temp->data;
    nodeHolder=temp;   
    temp=temp->next;
    elementCount–;
    }
    nodeHolder->next =NULL;
    free(temp);
    return pointerToTheFirstNode;
}

void display(struct node *headerPointer)
{

    node *ptr;
    ptr = headerPointer;
    cout<<endl<<"The list that we just created is:    ";
    while(ptr!=NULL)
    {
        cout<data<<" ";
        ptr=ptr->next;
    }
    cout<<endl;
}

int lenlist(struct node *header)
{
    node *ptr;
    int len=0;
    ptr=header;
    while(ptr!=NULL)
    {
        len=len+1;
        ptr=ptr->next;
    };
    return len;
}

void findElementFromLast(struct node *header, int intPos)
{
    node *ptr;
    ptr=header;
    int matchPos=0;
    int listLen = lenlist(ptr);
    cout<<"The length of the list is:    "<<listLen<<endl;
    cout<<"The element that is at "<< intPos <<" from the last node will be at "<<listLen-intPos<< " from the first node."<<endl;

    while(ptr!=NULL)
    {
        matchPos=matchPos+1;
        if(matchPos ==     (listLen-intPos))
        {
            cout<<"The value of the node that is at "<< intPos <<"th position from last is: "<data;
        }
        ptr=ptr->next    ;
    }
}

void main()
{
    node *header;
    int intPosFromLast=0;

    header=createlist();
    display(header);

    cout<<"Enter the position element that you want to find in the list we just created:    ";
    cin>>intPosFromLast;
    findElementFromLast(header,intPosFromLast);
}