Some Data Structure Programs in C++

1. WAP to implement searching in a linked list Link to heading

#include<iostream.h> 
#include<conio.h> 
#include<process.h>

class node {
    int data;
    node * next;
    public:
    void insert();
    void search(int);
    void display();
};

node *start, *head, *temp;

void node::insert() {
    head = new node;
    cout<<"\n Enter the data item: ";
    cin>>head->data;
    head->next = NULL;
    if (start == NULL) {
        start = head;
    } else {
        temp = start;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = head;
    }
}

void node::display() {
    temp = start;
    if (start == NULL)
        cout<<"\n Data list is empty ";
    else {
        cout<<"\n DATA LIST: ";
        while (temp != NULL) {
            cout<<temp->data<<" ";
            temp = temp->next;
        }
    }
}

void node::search(int data) {
    temp = start;
    if (start == NULL)
        cout<<"\n Data list is empty ";
    else {
        int flag = 0;
        while (temp != NULL) {
            if (data == temp->data) {
                cout<<"\n The data item is present in the list ";
                flag = 1;
                break;
            }
            temp = temp->next;
        }
        if (flag != 1)
            cout<<"\n The data item is not found to be present ";
    }
}

void main() {
    int ch, data;
    node ob;
    start = NULL;
    clrscr();
    do {
        cout<<"\n\n\n ... SINGLY LINKED LIST - SEARCH ... ";
        cout<<"\n\n 1.Insert\n 2.Display\n 3.Search\n 4. Exit\n ";
        cout<<"\n Enter your choice: ";
        cin>>ch;

        switch (ch) {
            case 1:
                ob.insert();
                break;
            case 2:
                ob.display();
                break;
            case 3:
                cout<<"\n Enter the data item to be searched: ";
                cin>>data;
                ob.search(data);
                break;
            case 4:
                cout<<"\n .... Thanking You! ....";
                getch();
                exit(0);
            default:
                cout<<"\n Invalid key-in ";
        }
    } while (1);

}

2. WAP to implement sorting in a linked list Link to heading

#include<iostream.h> 
#include<conio.h> 
#include<process.h>

class node {
    int data;
    node * next;
    public:
	void insert();
    void sort();
    void display();
};

node * start, * head, * temp;

void node::insert() {
    head = new node;
    cout<<"\n Enter the data item: ";
    cin>>head->data;
    head->next = NULL;
    if (start == NULL) {
        start = head;
    } else {
        temp = start;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = head;
    }
}

void node::display() {
    temp = start;
    if (start == NULL)
        cout<<"\n Data list is empty ";
    else {
        cout<<"\n DATA LIST: ";
        while (temp != NULL) {
            cout<<temp->data<<" ";
            temp = temp->next;
        }
    }
}

void node::sort() {
    if (start == NULL)
        cout<<"\n Data list is empty ";
    else {
        node * t1, * t2, * temp;
        for (t1 = start; t1 != NULL; t1 = t1->next) {
            for (t2 = t1->next; t2 != NULL; t2 = t2->next) {
                if (t1->data > t2->data) {
                    temp->data = t1->data;
                    t1->data = t2->data;
                    t2->data = temp->data;
                }
            }
        }

        cout<<"\n List is sorted ";
    }
}

void main() {
    int ch, data;
    node ob;
    start = NULL;
    clrscr();
    do {
        cout<<"\n\n\n ... SINGLY LINKED LIST - SORT ... ";
        cout<<"\n\n 1.Insert\n 2.Display\n 3.Sort\n 4. Exit\n ";
        cout<<"\n Enter your choice: ";
        cin>>ch;

        switch (ch) {
            case 1:
                ob.insert();
                break;
            case 2:
                ob.display();
                break;
            case 3:
                ob.sort();
                break;
            case 4:
                cout<<"\n .... Thanking You! ....";
                getch();
                exit(0);
            default:
                cout<<"\n Invalid key-in ";
        }
    } while (1);

}

3.WAP to reverse a linked list, start pointer is given Link to heading

#include<iostream.h> 
#include<conio.h> 
#include<process.h>

class node {
    int data;
    node * next;
    public:
    void insert();
    void reverse(node * );
    void display();
};

node * start, * head, * temp;

void node::insert() {
    head = new node;
    cout<<"\n Enter the data item: ";
    cin>>head->data;
    head->next = NULL;
    if (start == NULL) {
        start = head;
    } else {
        temp = start;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = head;
    }
}

void node::display() {
    temp = start;
    if (start == NULL)
        cout<<"\n Data list is empty ";
    else {
        cout<<"\n DATA LIST: ";
        while (temp != NULL) {
            cout<<temp->data<<" ";
            temp = temp->next;
        }
    }
}

void node::reverse(node * start) {
    if (start == NULL)
        cout<<"\n Data list is empty ";
    else {
        int a[50], i = 0, n;
        temp = start;
        //storing the data items to an array
        while (temp != NULL) {
            a[i] = temp->data;
            temp = temp->next;
            n = i++;
        }
        i = n;
        temp = start;
        //forming linked list in reversed order
        while (temp != NULL) {
            temp->data = a[i];
            temp = temp->next;
            i--;
        }

        cout<<"\n List is reversed ";
    }
}

void main() {
    int ch, data;
    node ob;
    start = NULL;
    clrscr();
    do {
        cout<<"\n\n\n ... SINGLY LINKED LIST - REVERSE ... ";
        cout<<"\n\n 1.Insert\n 2.Display\n 3.Reverse\n 4. Exit\n ";
        cout<<"\n Enter your choice: ";
        cin>>ch;

        switch (ch) {
            case 1:
                ob.insert();
                break;
            case 2:
                ob.display();
                break;
            case 3:
                ob.reverse(start);
                break;
            case 4:
                cout<<"\n .... Thanking You! ....";
                getch();
                exit(0);
            default:
                cout<<"\n Invalid key-in ";
        }
    } while (1);

}

4. WAP to reverse a linked list within the list Link to heading

#include<iostream.h> 
#include<conio.h> 
#include<process.h>

class node {
    int data;
    node * next;
    node * prev;
    public:
    void insert();
    void reverse();
    void display();
};

node * start, * head, * temp, * last;

void node::insert() {
    head = new node;
    cout<<"\n Enter the data item: ";
    cin>>head->data;
    head->next = head->prev = NULL;
    if (start == NULL) {
        start = head;
        last = head;
    } else {
        last->next = head;
        head->prev = last;
        last = head;
    }
}

void node::display() {
    temp = start;
    if (start == NULL)
        cout<<"\n Data list is empty ";
    else {
        cout<<"\n DATA LIST: ";
        while (temp != NULL) {
            cout<<temp->data<<" ";
            temp = temp->next;
        }
    }
}

void node::reverse() {
    if (start == NULL)
        cout<<"\n Data list is empty ";
    else {
        int len = 0, lenM = 0;
        temp = start;
        while (temp != NULL) {
            len++;
            temp = temp->next;
        }
        node * t1, * t2, * temp;
        t1 = start;
        t2 = last;
        while (lenM < len / 2) {
            temp->data = t1->data;
            t1->data = t2->data;
            t2->data = temp->data;
            t1 = t1->next;
            t2 = t2->prev;
            lenM++;
        }
        cout<<"\n List is reversed ";
    }
}

void main() {
    int ch, data;
    node ob;
    start = last = NULL;
    clrscr();
    do {
        cout<<"\n\n\n ... SINGLY LINKED LIST - REVERSE WITHIN THE LIST ... ";
        cout<<"\n\n 1.Insert\n 2.Display\n 3.Reverse\n 4.Exit\n ";
        cout<<"\n Enter your choice: ";
        cin>>ch;

        switch (ch) {
            case 1:
                ob.insert();
                break;
            case 2:
                ob.display();
                break;
            case 3:
                ob.reverse();
                break;
            case 4:
                cout<<"\n .... Thanking You! ....";
                getch();
                exit(0);
            default:
                cout<<"\n Invalid key-in ";
        }
    } while (1);

}

5. WAP to remove first & last occurence of an element in a linked list Link to heading

#include<iostream.h> 
#include<conio.h> 
#include<process.h>

class node {
    int data;
    node * next;
    public:
    void insert();
    void delet(int);
    void display();
};

node * start, * head, * temp;

void node::insert() {
    head = new node;
    cout<<"\n Enter the data item: ";
    cin>>head->data;
    head->next = NULL;
    if (start == NULL) {
        start = head;
    } else {
        temp = start;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = head;
    }
}

void node::display() {
    temp = start;
    if (start == NULL)
        cout<<"\n Data list is empty ";
    else {
        cout<<"\n DATA LIST: ";
        while (temp != NULL) {
            cout<<temp->data<<" ";
            temp = temp->next;
        }
    }
}

void node::delet(int data) {
    temp = start;
    if (start == NULL)
        cout<<"\n Data list is empty ";
    else {
        //counting no. of occurence
        int count = 0;
        while (temp != NULL) {
            if (data == temp->data) {
                count++;
            }
            temp = temp->next;
        }

        //storing the position of occurence into an array
        int a[50], i = 1, n, p = 0;
        int pos[20];
        temp = start;
        while (temp != NULL) {
            if (data == temp->data && i <= count) {
                pos[i] = p;
                i++;
            }
            temp = temp->next;
            p++;
        }

        //deleting first and last occurence
        int fst = pos[1];
        int lst = pos[count];
        node * t;
        temp = start;
        p = 0;
        while (temp != NULL) {
            if (data == temp->data && (fst == p || lst == p)) {
                if (temp == start) {
                    start = temp->next;
                } else {
                    t->next = temp->next;
                }
            }
            t = temp;
            temp = temp->next;
            p++;
        }

    }
}

void main() {
    int ch, data;
    node ob;
    start = NULL;
    clrscr();
    do {
        cout<<"\n\n\n ... SINGLY LINKED LIST - DELETE ... ";
        cout<<"\n\n 1.Insert\n 2.Display\n 3.Delete\n 4.Exit\n ";
        cout<<"\n Enter your choice: ";
        cin>>ch;

        switch (ch) {
            case 1:
                ob.insert();
                break;
            case 2:
                ob.display();
                break;
            case 3:
                cout<<"\n Enter the data item to be deleted: ";
                cin>>data;
                ob.delet(data);
                break;
            case 4:
                cout<<"\n .... Thanking You! ....";
                getch();
                exit(0);
            default:
                cout<<"\n Invalid key-in ";
        }
    } while (1);

}

6.WAP to create a tree from inorder & preorder traversal sequences Link to heading

#include<iostream.h> 
#include<conio.h> 
#include<process.h>

char inorder[20];
struct node {
    char data;
    int num;
    node * left;
    node * right;
};

node * root;

class bst {
    public:
    bst() {
        root = NULL;
    }
    node * insert(node * , int, char);
    node * create(char[]);
    void postorder(node * );

};

int pos(char a) {
    int p;
    for (int i = 0; inorder[i] != '\0'; i++) {
        if (inorder[i] == a) {
            p = i;
            break;
        }
    }
    return p;
}


node * bst::insert(node * root, int num, char data) {
    if (root == NULL) {
        root = new node;
        root->data = data;
        root->num = num;
        root->left = root->right = NULL;
    } else if (num < root->num)
        root->left = insert(root->left, num, data);
    else
        root->right = insert(root->right, num, data);

    return root;

}

node * bst::create(char pre[]) {
    const len = strlen(pre);
    char data;
    int num;
    for (int i = 0; i < len; i++) {
        data = pre[i];
        num = pos(pre[i]);
        root = this->insert(root, num, data);
    }
    return root;
}


void bst::postorder(node * root) {
    if (root != NULL) {
        postorder(root->left);
        postorder(root->right);
        cout<<root->data<<" ";
    }
}


void main() {
    clrscr();
    bst ob;
    char ino[25], pre[25];
    cout<<"\n Enter the inorder sequence: ";
    gets(ino);
    cout<<"\n Enter the preorder sequence: ";
    gets(pre);
    strcpy(inorder, ino);
    root = ob.create(pre);
    cout<<"\n The tree is created and the post order sequence is: ";
    ob.postorder(root);
    getch();

}

7.WAP to exchange right and left subtree of each node OR to produce mirror image of the tree Link to heading

#include<iostream.h> 
#include<conio.h> 
#include<process.h>

struct node {
    char data;
    node * lchild, * rchild;
};

node * head;

class tree {
    node * root;
    public:
    tree() {
        root = NULL;
    }
    node * read();
    node * makenode(char);
    void createtree(node * );
    void inorder(node * );
    void preorder(node * );
    void postorder(node * );
    void exchange(node * );
};

node * tree::read() {
    char item;
    cout<<"\n Enter data: ";
    cin>>item;
    root = makenode(item);
    createtree(root);
    return root;
}

node * tree::makenode(char x) {
    head = new node;
    head->data = x;
    head->lchild = head->rchild = NULL;
    return head;
}

void tree::createtree(node * root) {
    int ch;
    char item;
    if (root != NULL) {
        cout<<"\n Create left child for "<<root->data<<" (if so press \"1\")";
        cin>>ch;
        if (ch == 1) {
            cout<<"\n Enter data: ";
            cin>>item;
            root->lchild = makenode(item);
            createtree(root->lchild);
        }

        cout<<"\n Create right child for "<<root->data<<" (if so press \"1\")";
        cin>>ch;
        if (ch == 1) {
            cout<<"\n Enter data: ";
            cin>>item;
            root->rchild = makenode(item);
            createtree(root->rchild);
        }
    }
}

void tree::inorder(node * root) {
    if (root != NULL) {
        inorder(root->lchild);
        cout<<root->data<<" ";
        inorder(root->rchild);
    }
}

void tree::preorder(node * root) {
    if (root != NULL) {
        cout<<root->data<<" ";
        preorder(root->lchild);
        preorder(root->rchild);
    }
}

void tree::postorder(node * root) {
    if (root != NULL) {
        postorder(root->lchild);
        postorder(root->rchild);
        cout<<root->data<<" ";
    }
}

void tree::exchange(node * root) {
    if (root != NULL) {
        exchange(root->lchild);
        exchange(root->rchild);
        node * temp;
        temp = root->lchild;
        root->lchild = root->rchild;
        root->rchild = temp;
    }
}

void main() {
    tree ob;
    node * root;
    int ch;
    clrscr();
    do {
        cout<<"\n\n.... BINARY TREE ....\n\n";
        cout<<"\n1.Creation\n2.Inorder Traversal\n3.Preorder Traversal";
        cout<<"\n4.Postorder Traversal\n5.Exchange\n6.Exit";
        cout<<"\n\t Enter your choice: ";
        cin>>ch;
        switch (ch) {
            case 1:
                root = ob.read();
                break;
            case 2:
                ob.inorder(root);
                break;
            case 3:
                ob.preorder(root);
                break;
            case 4:
                ob.postorder(root);
                break;
            case 5:
                ob.exchange(root);
                break;
            case 6:
                cout<<"\n\n\t... Thanking You ...";
                getch();
                exit(0);
            default:
                cout<<"\n Invalid key-in ";
        }

    } while (1);

}