DS Practicals

//For Educational Purpose Only 😅

// practical 1A
//Reverse array

#include <iostream.h>
#include <conio.h>
void main()
{
    clrscr();
    int arr[50], size, i, j, temp;
    cout << "Enter array size: ";
    cin >> size;
    cout << "Enter array elements:\n";
    for (i = 0; i < size; i++)
    {
        cin >> arr[i];
    }
    j = i - 1;
    i = 0;
    while (i < j)
    {
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        i++;
        j--;
    }
    cout << "\nReverse of the array is:\n";
    for (i = 0; i < size; i++)
    {
        cout << arr[i] << " ";
    }
    getch();
}

//--------------------------------------------------------------------------------------------------------------------------------


//Practical 1B
//Merging array
#include <iostream.h>
#include <conio.h>
void main()
{
    clrscr();
    int arr1[50], arr2[50], size1, size2, size, i, j, merge[100];
    cout << "Enter array1 size: ";
    cin >> size1;
    cout << "Enter array1 elements:\n";
    for (i = 0; i < size1; i++)
    {
        cin >> arr1[i];
    }
    cout << "Enter array2 size: ";
    cin >> size2;
    cout << "Enter array2 elements:\n";
    for (i = 0; i < size2; i++)
    {
        cin >> arr2[i];
    }
    for (i = 0; i < size1; i++)
    {
        merge[i] = arr1[i];
    }
    size = size1 + size2;
    for (i = 0, j = size1; j < size && i < size2; i++, j++)
    {
        merge[j] = arr2[i];
    }
    cout << "\nThe array after merging is:\n";
    for (i = 0; i < size; i++)
    {
        cout << merge[i] << " ";
    }
    getch();
}

//-----------------------------------------------------------------------------------------------------------------------








//Pracatical 1C
//Matrix operations

#include <iostream.h>
#include <conio.h>
void main()
{
    clrscr();
    int mat1[3][3], mat2[3][3], mat3[3][3], i, j;
    cout << "Enter Matrix1 elements:\n";
    for (i = 0; i < 3; i++)
    {
        for (j = 0; j < 3; j++)
        {
            cin >> mat1[i][j];
        }
    }
    cout << "Enter Matrix2 elements:\n";
    for (i = 0; i < 3; i++)
    {
        for (j = 0; j < 3; j++)
        {
            cin >> mat2[i][j];
        }
    }
    cout << "\nAdding two matrices to form third matrix....\n";
    for (i = 0; i < 3; i++)
    {
        for (j = 0; j < 3; j++)
        {
            mat3[i][j] = mat1[i][j] + mat2[i][j];
        }
    }
    cout << "The new matrix is:\n";
    for (i = 0; i < 3; i++)
    {
        for (j = 0; j < 3; j++)
        {
            cout << mat3[i][j] << " ";
        }
        cout << "\n";
    }
    cout << "\nSubtracting two matrices to form third matrix....\n";
    for (i = 0; i < 3; i++)
    {
        for (j = 0; j < 3; j++)
        {
            mat3[i][j] = mat1[i][j] - mat2[i][j];
        }
    }
    cout << "The resultant matrix is:\n";
    for (i = 0; i < 3; i++)
    {
        for (j = 0; j < 3; j++)
        {
            cout << mat3[i][j] << " ";
        }
        cout << "\n";
    }
    getch();
}






//Practical 2A
//Singly Linked List
#include <iostream.h>
#include <conio.h>
#include <process.h>
struct node
{
    int info;
    node *next;
}
    *start,
    *newptr, *save;
*np;
node *create_new_node(int);
void insert_at_beg(node *);
void display(node *);
void main()
{
    clrscr();
    start = NULL;
    int info;
    char ch = 'y';
    while (ch == 'y' || ch == 'Y')
    {
        cout << "\n Enter information for the new node:";
        cin >> info;
        cout << "\n Creating new node...Press any key to continue";
        getch();
        newptr = create_new_node(info);
        if (newptr != NULL)
        {
            cout << "\n New node created";
            getch();
        }
        else
        {
            cout << "\n Node not created";
            getch();
        }
        cout << "\n Now inserting new node";
        insert_at_beg(newptr);
        cout << "\n Node inserted successfully...Displaying the list\n";
        display(start);
        cout << "\n Want to enter new node?(y/n):";
        cin >> ch;
    }
    getch();
}
node *create_new_node(int n)
{
    node *np;
    np = new node;
    np->info = n;
    np->next = NULL;
    return np;
}
void insert_at_beg(node *np)
{
    if (start == NULL)
    {
        start = np;
    }
    else
    {
        save = start;
        save->next = np;
        save = np;
    }
}
void display(node *np)
{
    while (np != NULL)
    {
        cout << np->info << "->";
        np = np->next;
    }
}






//Practical 2B
//Doubly Linked List

#include <iostream.h>
#include <conio.h>
#include <process.h>
struct node
{
    int info;
    node *next;
    node *prev;
};

node *start, *newptr, *save, *np;

node *create_new_node(int);
void insert_at_beg(node *);
void display(node *);

int main()
{
    clrscr();
    start = NULL;
    int info;
    char ch = 'y';
    while (ch == 'y' || ch == 'Y')
    {
        cout << "Enter information for the new node";
        cin >> info;
        cout << "\n Creating new node...press any key to continue:";
        getch();

        newptr = create_new_node(info);
        if (newptr != NULL)
        {
            cout << "\n New node created";
            getch();
        }
        else
        {
            cout << "\n Node not created";
            getch();
        }
        cout << "\n Now inserting a new node";
        insert_at_beg(newptr);
        cout << "\n Node created successfully and displaying the list \n";
        display(start);
        cout << "\n Want to enter the new node?(y/n)";
        cin >> ch;
    }
    getch();
    return 0;
}

node *create_new_node(int n)
{
    node *np;
    np = new node;
    np->info = n;
    np->next = NULL;
    np->prev = NULL;
    return np;
}

void insert_at_beg(node *np)
{
    if (start == NULL)
    {
        start = np;
    }
    else
    {
        save = start;
        save->next = np;
        np->prev = save;
        save = np;
    }
}

void display(node *np)
{
    while (np != NULL)
    {
        cout << np->info << "->";
        np = np->next;
    }
}







//Practical 3A
//Selection Sort
#include <iostream.h>
#include <conio.h>
void main()
{
    clrscr();
    int size, arr[50], i, j, temp;
    cout << "Enter array size: ";
    cin >> size;
    cout << "Enter array elements:\n";
    for (i = 0; i < size; i++)
    {
        cin >> arr[i];
    }
    cout << "\nSorting array using Selection sort...\n";
    for (i = 0; i < size; i++)
    {
        for (j = i + 1; j < size; j++)
        {
            if (arr[i] > arr[j])
            {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
    cout << "Array after sorting:\n";
    for (i = 0; i < size; i++)
    {
        cout << arr[i] << " ";
    }
    getch();
}




// Practical 3B
//Insertion Sort

#include <iostream.h>
#include <conio.h>
void main()
{
    clrscr();
    int size, arr[50], i, j, temp;
    cout << "Enter array size: ";
    cin >> size;
    cout << "Enter array elements:\n";
    for (i = 0; i < size; i++)
    {
        cin >> arr[i];
    }
    cout << "\nSorting array using Insertion sort...\n";
    for (i = 1; i < size; i++)
    {
        temp = arr[i];
        j = i - 1;
        while ((temp < arr[j]) && (j >= 0))
        {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = temp;
    }
    cout << "Array after sorting:\n";
    for (i = 0; i < size; i++)
    {
        cout << arr[i] << " ";
    }
    getch();
}



//Practical 4A
//Sequential Search

#include <iostream.h>
#include <conio.h>
int main()
{
    clrscr();
    cout << "Enter the size of array: ";
    int size;
    cin >> size;
    int array[50], key, i;
    for (int j = 0; j < size; j++)
    {
        cout << "Enter " << j << " Element: ";
        cin >> array[j];
    }
    for (int a = 0; a < size; a++)
    {
        cout << "array[" << a << "] = ";
        cout << array[a] << endl;
    }
    cout << "\nEnter key to search in array: ";
    cin >> key;
    for (i = 0; i < size; i++)
    {
        if (key == array[i])
        {
            cout << "Key found at index number: " << i << endl;
            break;
        }
    }
    if (i != size)
    {
        cout << " ";
    }
    else
    {
        cout << "Key not found in array";
    }
    getch();
    return 0;

}






//Practical 4B
//Binary Search

#include <iostream.h>
#include <conio.h>
void main()
{
    clrscr();
    int n, i, a[50], search, first, last, middle;
    cout << "Enter total number of elements: ";
    cin >> n;
    cout << "Enter " << n << " numbers: " << endl;
    for (i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    cout << "\nEnter a number to find: ";
    cin >> search;
    first = 0;
    last = n - 1;
    middle = (first + last) / 2;
    while (first <= last)
    {
        if (a[middle] < search)
        {
            first = middle + 1;
        }
        else if (a[middle] == search)
        {
            cout << search << " found at location " << middle + 1 << endl;
            break;
        }
        else
        {
            last = middle - 1;
        }
        middle = (first + last) / 2;
    }
    if (first > last)
    {
        cout << "Not found! " << search << " is not present in the list.";
    }
    getch();
}





//Practical 5A
//Stack

#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
class stack
{
public:
    int stk[5], top;
    stack()
    {
        top = -1;
    }
    void push(int x)
    {
        if (top > 4)
        {
            cout << "Stack overflow\n";
            return;
        }
        stk[++top] = x;
        cout << x << "Inserted in the stack\n";
    }
    void pop()
    {
        if (top < 0)
        {
            cout << "Stack Underflow\n";
            return;
        }
        cout << stk[top--] << " Deleted from the stack\n";
    }
};
void display(stack s)
{
    if (s.top < 0)
    {
        cout << "Stack Empty\n";
        return;
    }
    for (int i = s.top; i >= 0; i--)
        cout << s.stk[i] << " \n";
}
void main()
{
    clrscr();
    int ch;
    stack st;
    while (1)
    {
        cout << "\n1.Push  2.Pop  3.Display";
        cout << "4.Exit \nEnter your choice:";
        cin >> ch;
        switch (ch)
        {
        case 1:
            cout << "Enter the element: ";
            cin >> ch;
            st.push(ch);
            break;
        case 2:
            st.pop();
            break;
        case 3:
            display(st);
            break;
        case 4:
            exit(0);
        }
    }
}





//Practical 6A
//Queue

#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
class queue
{
public:
    int que[5], rear, front;
    queue()
    {
        rear = -1;
        front = -1;
    }
    void insert(int x)
    {
        if (rear > 4)
        {
            cout << "Queue Overflow\n";
            front = rear = -1;
            return;
        }
        que[++rear] = x;
        cout << x << " Inserted\n";
    }
    void delet()
    {
        if (front == rear)
        {
            cout << "Queue Underflow\n";
            return;
        }
        cout << que[++front] << " Deleted\n";
    }
};
void display(queue q)
{
    if (q.rear == q.front)
    {
        cout << "Queue Empty\n";
        return;
    }
    for (int i = q.front + 1; i <= q.rear; i++)
        cout << q.que[i] << " ";
}
void main()
{
    clrscr();
    int ch;
    queue qu;
    while (1)
    {
        cout << "\n1.Insert 2.Delete 3.Display 4.Exit \nEnter your choice:";
        cin >> ch;
        switch (ch)
        {
        case 1:
            cout << "Enter the element:";
            cin >> ch;
            qu.insert(ch);
            break;
        case 2:
            qu.delet();
            break;
        case 3:
            display(qu);
            break;
        case 4:
            exit(0);
        }
    }
}


//Practical 7
//Max Heap

#include <iostream.h>
#include <conio.h>
void max_heapify(int *a, int i, int n)
{
    int j, temp;
    temp = a[i];
    j = 2 * i;
    while (j <= n)
    {
        if (j < n && a[j + 1] > a[j])
            j = j + 1;
        if (temp > a[j])
            break;
        else if (temp <= a[j])
        {
            a[j / 2] = a[j];
            j = 2 * j;
        }
    }
    a[j / 2] = temp;
    return;
}
void build_maxheap(int *a, int n)
{
    int i;
    for (i = n / 2; i >= 1; i--)
    {
        max_heapify(a, i, n);
    }
}
int main()
{
    clrscr();
    int n, i, x;
    cout << "Enter number of elements in array:\n";
    cin >> n;
    int a[20];
    for (i = 1; i <= n; i++)
    {
        cout << "Enter element " << i << endl;
        cin >> a[i];
    }
    build_maxheap(a, n);
    cout << "Max Heap\n";
    for (i = 1; i <= n; i++)
    {
        cout << a[i] << endl;
    }
    getch();
    return 0;
}








//Practical 8
//Adjacency Matrix

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

class adjacencyMatrix
{
  int n;
  int **adj;

public:
  adjacencyMatrix(int n)
  {
    this->n = n;
    adj = new int *[n];
    for (int i = 0; i < n; i++)
    {
      adj[i] = new int[n];
      for (int j = 0; j < n; j++)
      {
        adj[i][j] = 0;
      }
    }
  }
  void addEdge(int u, int v)
  {
    if (u > n || v > n || u < 0 || v < 0)
    {
      cout << "Invalid edges!" << endl;
    }
    else
    {
      adj[u - 1][v - 1] = 1;
    }
  }
  void display()
  {
    for (int i = 0; i < n; i++)
    {
      for (int j = 0; j < n; j++)
      {
        cout << adj[i][j] << " ";
      }
      cout << endl;
    }
  }
};

int main()
{
  int nodes, maxEdges, u, v;
  cout << "Enter number of nodes : ";
  cin >> nodes;

  adjacencyMatrix am(nodes);
  maxEdges = nodes * (nodes - 1);

  for (int i = 0; i < maxEdges; i++)
  {
    cout << "Enter edge (-1 -1 to exit) : ";
    cin >> u >> v;
    if (u == -1 && v == -1)
      break;

    am.addEdge(u, v);
  }

  am.display();
  getch();
  return 0;
}