Data Structures and Algorithms

Assignment Name : A dictionary store keyword and its meaning, provides facility for adding new keyword, deleting keyword and  updating values of any entry. Also provides facility to display whole data stored in ascending/descending order. Also find how many maximum comparisons may be required for finding.
#include<iostream>
using namespace std;
class node
{
public:
    node *l,*r;
    string keyword,meaning;
};

class Tree
{
private:
    node *root;
public:
    Tree()
{
        root=NULL;
}
    void insert();
    void acending(node *);
    void decending(node *);
    void search(node *);
    void put();
    void display();
    void remove(string );
    void display1();
};

void Tree::insert()
{
    node *nn;
    nn=new node();

    cout<<"Enter new keyword :";
    cin>>nn->keyword;
    cout<<"Enter its meaning :";
    cin>>nn->meaning;
    nn->l=nn->r=NULL;

    if(root==NULL)
    {
        root=nn;
    }
    else
    {
        node *t,*p;
        t=root;

        while(t!=NULL)
        {
            p=t;
            if(nn->keyword>t->keyword)
            {
                t=t->r;
            }
            else
            {
                t=t->l;

            }
        }
        if(nn->keyword>p->keyword)
        {
            p->r=nn;
        }
        else
        {
            p->l=nn;
        }
    }

}


void Tree::acending(node *root)
{
node *t=root;
    if(t!=NULL)
    {
        acending(t->l);
        cout<<"\t"<<t->keyword;
        cout<<"\t"<<t->meaning<<endl<<"\t\t\t\t";
        acending(t->r);
    }

}

void Tree::decending(node *root)
{
node *t=root;
    if(t!=NULL)
    {
        decending(t->r);
        cout<<"\t"<<t->keyword;
        cout<<"\t"<<t->meaning<<endl<<"\t\t\t\t";
        decending(t->l);

    }

}

void Tree::search(node *root)
{
    node *t=root;
    node *nn=new node();

    cout<<"\nEnter key which you to search :";
    cin>>nn->keyword;

    while(t!=NULL)
    {

        if(nn->keyword==t->keyword)
            break;

        if(nn->keyword>t->keyword)
        {
            t=t->r;

        }else
        {
            t=t->l;

        }
    }

    if(t==NULL)
    {
        cout<<"\n\t\t\t\t key is not present\n";

    }
    else
        cout<<"\n\t\t\t\t key is present and meaning is:"<<t->meaning;

}

void Tree::remove(string k)
{
    node *t=root,*p;

    while(t->keyword!=k)
    {
        p=t;
        if(k<t->keyword)
            t=t->l;
        else
            t=t->r;
    }

    if(t->l==NULL && t->r==NULL)
    {
        if(p->l==t)
            p->l=NULL;
        else
            p->r=NULL;
        cout<<"\nEnter Key is delete and meaning is :"<<t->meaning<<endl;
    }
    else
    {
        if(t->l==NULL && t->r!=NULL)
        {
            if(p->l==t)
                p->l=t->r;
            else
                p->r=t->r;
            cout<<"\nEnter Key is delete and meaning is :"<<t->meaning<<endl;
        }
        else
        {
            if(p->l==t)
                p->l=t->l;
            else
                p->r=t->l;
            cout<<"\nEnter Key is delete and meaning is :"<<t->meaning<<endl;
        }
    }

    if(t->l!=NULL &&t->r!=NULL)
    {
        node *t1=t->l;
        string nkey,nmean;

        while(t1->r)
            t1=t1->r;
        nkey=t1->keyword;
        nmean=t1->meaning;
        remove(t1->keyword);
        t->keyword=nkey;
        t->meaning=nmean;
        cout<<"\nEnter Key is delete and meaning is :"<<t->meaning<<endl;
        }

    }



    void Tree::display()
{
    search(root);
}

void Tree::put()
{
    cout<<"dictionary in ascending order:"<<"\t";
    acending(root);
    cout<<endl<<"dictionary in descending order:"<<"\t";
    decending(root);

}

int main()
{
    Tree t;

    int ch;
    string k;
    do
    {
        cout<<endl<<"1.insert"<<endl;
        cout<<"2.display"<<endl;
        cout<<"3.search"<<endl;
        cout<<"4.delete"<<endl;
        cout<<"5.exit"<<endl;
        cout<<"Enter choice :";
        cin>>ch;

        switch(ch)
        {
        case 1:
            t.insert();
            break;
        case 2:
            t.put();
            break;
        case 3:
                    t.display();
                    break;
        case 4:
                    cout<<"\nEnter Key which u want to delete";
                    cin>>k;
                    t.remove(k);
                    break;
        case 5:
                    return 0;
        default :
            cout<<"invaild choice";

            return 0;

        }
    }while(ch!=-1);

return 0;

}

********************** OUTPUT ***********************
 

1.insert
2.display
3.search
4.delete
5.exit
Enter choice :1
Enter new keyword :SANdy
Enter its meaning :SUnil

1.insert
2.display
3.search
4.delete
5.exit
Enter choice :1
Enter new keyword :Balya
Enter its meaning :Bhagwat

1.insert
2.display
3.search
4.delete
5.exit
Enter choice :1
Enter new keyword :Jambhya
Enter its meaning :Kamble

1.insert
2.display
3.search
4.delete
5.exit
Enter choice :1
Enter new keyword :Brother
Enter its meaning :Sai

1.insert
2.display
3.search
4.delete
5.exit
Enter choice :1
Enter new keyword :r
Enter its meaning :Radhika

1.insert
2.display
3.search
4.delete
5.exit
Enter choice :2
dictionary in ascending order:        Balya    Bhagwat
                            Brother    Sai
                            Jambhya    Kamble
                            SANdy    SUnil
                            r    Radhika
              
dictionary in descending order:        r    Radhika
                            SANdy    SUnil
                            Jambhya    Kamble
                            Brother    Sai
                            Balya    Bhagwat
              
1.insert
2.display
3.search
4.delete
5.exit
Enter choice :3

Enter key which you to search :jambhya

                 key is not present

1.insert
2.display
3.search
4.delete
5.exit
Enter choice :3

Enter key which you to search :Jambhya

                 key is present and meaning is:Kamble
1.insert
2.display
3.search
4.delete
5.exit
Enter choice :4

Enter Key which u want to deleter

Enter Key is delete and meaning is :Radhika

1.insert
2.display
3.search
4.delete
5.exit
Enter choice :5







Assignment Name    : Write a program using object oriented programming features to implement doubly circular linked list with different manipulation facilities in c++.
#include<iostream>
using namespace std;

class node
{
public:
    int data;
    node *n,*p;
};

class dcll
{
private:
    node *header;
public:
    dcll()
{
        header=NULL;

}
    void accept()
    {
        node *nn=new node();
        cout<<"Enter new node :";
        cin>>nn->data;
        nn->n=nn->p=NULL;

        node *cn=header;
        if(header==NULL)
        {
            header=nn;
            nn->n=nn->p=header;
        }
        else
        {
            while(cn->n!=header)
            {
                cn=cn->n;
            }
            cn->n=nn;
            nn->p=cn;
            nn->n=header;
            header->p=nn;
        }
    }

    void display()
    {
    node *cn=header;
        if(header==NULL)
        {
            cout<<"Data dose not exit";
        }
        else{
            while(cn->n!=header)
            {
                cout<<endl<<cn->data;
                cn=cn->n;
            }
            cout<<endl<<cn->data;
        }
    }

    void delete1()
        {
        node *t=header;
        int val;
        cout<<"Enter data u want delete :";
        cin>>val;

        if(header==NULL)
        {
            cout<<"'List not present";
        }
        else
        {
            while(t->data!=val)
            {
                t=t->n;
            }
            t->p->n=t->n;
            t->n->p=t->p;
            cout<<"\ndata "<<val<<" is deleted\n";
        }

        if(val==header->data)
        {
            header->n->p=header->p;
            header=header->n;
            cout<<"\ndata "<<val<<" is deleted\n";
        }
        }
};

int main()
{
    dcll d;
    int ch;
    do
    {
    cout<<"\n 1.Create \n 2.Display \n 3.Delete\n 4.Exit \n";
    cout<<"Enter a choice";
    cin>>ch;

    switch(ch)
    {
    case 1:
            d.accept();
            break;
    case 2:
            d.display();
            break;
    case 3:
            d.delete1();
            break;

    case 4:

            break;

    default :
            cout<<"wrong choice";

    }
}while(ch!=-1);
    return 0;

}


************************* OUTPUT ******************************

 1.Create
 2.Display
 3.Delete
 4.Exit
Enter a choice1
Enter new node :10

 1.Create
 2.Display
 3.Delete
 4.Exit
Enter a choice1
Enter new node :20

 1.Create
 2.Display
 3.Delete
 4.Exit
Enter a choice1
Enter new node :30

 1.Create
 2.Display
 3.Delete
 4.Exit
Enter a choice2

10
20
30
 1.Create
 2.Display
 3.Delete
 4.Exit
Enter a choice3
Enter data u want delete :20

data 20 is deleted

 1.Create
 2.Display
 3.Delete
 4.Exit
Enter a choice2

10
30
 1.Create
 2.Display
 3.Delete
 4.Exit
Enter a choice1
Enter new node :50

 1.Create
 2.Display
 3.Delete
 4.Exit
Enter a choice1
Enter new node :100

 1.Create
 2.Display
 3.Delete
 4.Exit
Enter a choice2

10
30
50
100
 1.Create
 2.Display
 3.Delete
 4.Exit
Enter a choice3
Enter data u want delete :10

data 10 is deleted

data 10 is deleted

 1.Create
 2.Display
 3.Delete
 4.Exit
Enter a choice2

30
50
100
 1.Create
 2.Display
 3.Delete
 4.Exit
Enter a choice



Assignment Name    : Write a program in python to perform bubble sort.
def main():
    print("Enter how many numbers do you want to sort? : ")
    n=(int)(input())
    print("Enter numbers %s to sort : " % n)
   
    i=0
    a=[]
   
    while(i<n):
        val=(int)(input())
        a.append(val)
        i=i+1
   
    pas=1
    while(pas<n):
        i=0
        print("pass no %s :" %pas)
       
        while(i<n-pas):
            print("comparison no %s :" % (i+1))
            if(a[i]>a[i+1]):
                temp=a[i]
                a[i]=a[i+1]
                a[i+1]=temp
               
            print(a)
            i=i+1
       
        pas=pas+1
    
    print("sorted numbers are : ")  
    print(a)
       
main()


***************************** OUTPUT ********************************

Enter how many numbers do you want to sort? :
8
Enter numbers 8 to sort :
45
-56
0
7
-5
435
55
72
pass no 1 :
comparison no 1 :
[-56, 45, 0, 7, -5, 435, 55, 72]
comparison no 2 :
[-56, 0, 45, 7, -5, 435, 55, 72]
comparison no 3 :
[-56, 0, 7, 45, -5, 435, 55, 72]
comparison no 4 :
[-56, 0, 7, -5, 45, 435, 55, 72]
comparison no 5 :
[-56, 0, 7, -5, 45, 435, 55, 72]
comparison no 6 :
[-56, 0, 7, -5, 45, 55, 435, 72]
comparison no 7 :
[-56, 0, 7, -5, 45, 55, 72, 435]
pass no 2 :
comparison no 1 :
[-56, 0, 7, -5, 45, 55, 72, 435]
comparison no 2 :
[-56, 0, 7, -5, 45, 55, 72, 435]
comparison no 3 :
[-56, 0, -5, 7, 45, 55, 72, 435]
comparison no 4 :
[-56, 0, -5, 7, 45, 55, 72, 435]
comparison no 5 :
[-56, 0, -5, 7, 45, 55, 72, 435]
comparison no 6 :
[-56, 0, -5, 7, 45, 55, 72, 435]
pass no 3 :
comparison no 1 :
[-56, 0, -5, 7, 45, 55, 72, 435]
comparison no 2 :
[-56, -5, 0, 7, 45, 55, 72, 435]
comparison no 3 :
[-56, -5, 0, 7, 45, 55, 72, 435]
comparison no 4 :
[-56, -5, 0, 7, 45, 55, 72, 435]
comparison no 5 :
[-56, -5, 0, 7, 45, 55, 72, 435]
pass no 4 :
comparison no 1 :
[-56, -5, 0, 7, 45, 55, 72, 435]
comparison no 2 :
[-56, -5, 0, 7, 45, 55, 72, 435]
comparison no 3 :
[-56, -5, 0, 7, 45, 55, 72, 435]
comparison no 4 :
[-56, -5, 0, 7, 45, 55, 72, 435]
pass no 5 :
comparison no 1 :
[-56, -5, 0, 7, 45, 55, 72, 435]
comparison no 2 :
[-56, -5, 0, 7, 45, 55, 72, 435]
comparison no 3 :
[-56, -5, 0, 7, 45, 55, 72, 435]
pass no 6 :
comparison no 1 :
[-56, -5, 0, 7, 45, 55, 72, 435]
comparison no 2 :
[-56, -5, 0, 7, 45, 55, 72, 435]
pass no 7 :
comparison no 1 :
[-56, -5, 0, 7, 45, 55, 72, 435]
sorted numbers are :
[-56, -5, 0, 7, 45, 55, 72, 435]