Lab Program 12 Hashing 15CSL38 Data Structures in C Lab

Lab program 12

Given a File of N employee records with a set K of Keys(4-digit) which uniquely determine the records in file F.
Assume that file F is maintained in memory by a Hash Table(HT) of m memory locations with L as the set of memory addresses (2-digit) of locations in HT.
Let the keys in K and addresses in L are integers.
Design and develop a Program in C that uses Hash function H: K -> L as H(K)=K mod m (remainder method), and implement hashing technique to map a given key K to the address space L.
Resolve the collision (if any) using linear probing.

#include<stdio.h>
#include<stdlib.h>

int key[20],n,m;
int *ht,index;
int count = 0;

void insert(int key)
{
            index = key % m;
            while(ht[index] != -1)
            {
                         index = (index+1)%m;
            }
            ht[index] = key;
            count++;
 }

void display()
{
           int i;
           if(count == 0)
          {
                         printf("\nHash Table is empty");
                         return;
           }

           printf("\nHash Table contents are:\n ");
           for(i=0; i<m; i++)
                      printf("\n T[%d] --> %d ", i, ht[i]);
}


void main()
{
         int i;
         printf("\nEnter the number of employee  records (N) :   ");
         scanf("%d", &n);

         printf("\nEnter the two digit memory locations (m) for hash table:   ");
         scanf("%d", &m);

         ht = (int *)malloc(m*sizeof(int));
         for(i=0; i<m; i++)
                     ht[i] = -1;

         printf("\nEnter the four digit key values (K) for N Employee Records:\n  ");
         for(i=0; i<n; i++)
                    scanf("%d", &key[i]);

         for(i=0;i<n;i++)
        {
                   if(count == m)
                   {
                        printf("\n~~~Hash table is full. Cannot insert the record %d key~~~",i+1);
                        break;
                   }
                   insert(key[i]);
    }

            //Displaying Keys inserted into hash table
             display();
}

Output:

Enter the number of employee  records (N) :   12

Enter the two digit memory locations (m) for hash table:   15

Enter the four digit key values (K) of 'N' Employee Records:

1234

5678

3456

2345

6799

1235

7890

3214

3456

1235

5679

2346

Hash Table contents are:

 T[0] --> 7890

 T[1] --> -1

 T[2] --> -1

 T[3] --> -1

 T[4] --> 1234

 T[5] --> 2345

 T[6] --> 3456

 T[7] --> 6799

 T[8] --> 5678

 T[9] --> 1235

 T[10] --> 3214

 T[11] --> 3456

 T[12] --> 1235

 T[13] --> 5679

 T[14] --> 2346

Lab Program 7 Singly Linked List 15CSL38 Data Structures in C Lab

Lab Program 7:

Design, Develop and Implement a menu driven Program in C for the following operations on Singly Linked List (SLL) of Student Data with the fields: USN, Name, Branch, Sem, PhNo

a. Create a SLL of N Students Data by using front insertion.
b. Display the status of SLL and count the number of nodes in it
c. Perform Insertion / Deletion at End of SLL
d. Perform Insertion / Deletion at Front of SLL(Demonstration of stack)
e. Exit

#include<stdio.h>
#include<stdlib.h>

struct node
{
    char usn[25],name[25],branch[25];
    int sem;
    long int phone;
    struct node *link;
};
typedef struct node * NODE;

NODE start = NULL;
int count=0;


NODE create()
{
    NODE snode;
    snode = (NODE)malloc(sizeof(struct node));

    if(snode == NULL)
    {
        printf("\nMemory is not available");
        exit(1);
    }
    printf("\nEnter the usn,Name,Branch, sem,PhoneNo of the student:");
    scanf("%s %s %s %d %ld",snode->usn, snode->name, snode->branch, &snode->sem, &snode->phone);
    snode->link=NULL;
    count++;
    return snode;
}

NODE insertfront()
{
    NODE temp;
    temp = create();
    if(start == NULL)
    {
           return temp;
    }

    temp->link = start;
    return temp;
}


NODE deletefront()
{
    NODE temp;
    if(start == NULL)
    {
        printf("\nLinked list is empty");
        return NULL;
    }

    if(start->link == NULL)
    {
            printf("\nThe Student node with usn:%s is deleted ",start->usn);
            count--;
            free(start);
            return NULL;
    }
    temp = start;
    start = start->link;
    printf("\nThe Student node with usn:%s is deleted",temp->usn);
    count--;
    free(temp);
    return start;
}

NODE insertend()
{
    NODE cur,temp;
    temp = create();

    if(start == NULL)
    {
      return temp;
    }
    cur = start;
    while(cur->link !=NULL)
    {
         cur = cur->link;
    }
    cur->link = temp;
    return start;
}

NODE deleteend()
{
     NODE cur,prev;
     if(start == NULL)
     {
        printf("\nLinked List is empty");
        return NULL;
     }

     if(start->link == NULL)
     {
        printf("\nThe student node with the usn:%s is deleted",start->usn);
        free(start);
        count--;
        return NULL;
     }

     prev = NULL;
     cur = start;
     while(cur->link!=NULL)
     {
         prev = cur;
         cur = cur->link;
     }

      printf("\nThe student node with the usn:%s is deleted",cur->usn);
      free(cur);
      prev->link = NULL;
      count--;
      return start;
}

void display()
{
    NODE cur;
    int num=1;


    if(start == NULL)
    {

        printf("\nNo Contents to display in SLL \n");
        return;
    }
    printf("\nThe contents of SLL: \n");
    cur = start;
    while(cur!=NULL)
    {
       printf("\n||%d|| USN:%s| Name:%s| Branch:%s| Sem:%d| Ph:%ld|",num,cur->usn, cur->name,cur->branch, cur->sem,cur->phone);
       cur = cur->link;
       num++;
    }
    printf("\n No of student nodes is %d \n",count);
}

void stackdemo()
{
   int ch;
   while(1)
   {
     printf("\n~~~Stack Demo using SLL~~~\n");
     printf("\n1:Push operation \n2: Pop operation \n3: Display \n4:Exit \n");
     printf("\nEnter your choice for stack demo");
     scanf("%d",&ch);

     switch(ch)
     {
        case 1: start = insertfront();
                break;
        case 2: start = deletefront();
                break;
        case 3: display();
               break;
       default : return;
     }
   }
   return;
}

int main()
{
    int ch,i,n;
    while(1)
    {
        printf("\n~~~Menu~~~");
        printf("\nEnter your choice for SLL operation \n");
        printf("\n1:Create SLL of Student Nodes");
        printf("\n2:DisplayStatus");
        printf("\n3:InsertAtEnd");
        printf("\n4:DeleteAtEnd");
        printf("\n5:Stack Demo using SLL(Insertion and Deletion at Front)");
        printf("\n6:Exit \n");
        printf("\nEnter your choice:");
        scanf("%d",&ch);

        switch(ch)
        {
        case 1 : printf("\nEnter the no of students:    ");
                 scanf("%d",&n);
                 for(i=1;i<=n;i++)
                    start = insertfront();
                 break;

        case 2: display();
                break;

        case 3: start = insertend();
                break;

        case 4: start = deleteend();
                break;

        case 5: stackdemo();
                break;

        case 6: exit(0);

        default: printf("\nPlease enter the valid choice");

        }
    }
}

Output:

~~~Menu~~~

Enter your choice for SLL operation

1:Create SLL of Student Nodes

2:DisplayStatus

3:InsertAtEnd

4:DeleteAtEnd

5:Stack Demo using SLL(Insertion and Deletion at Front)

6:Exit

Enter your choice:1

Enter the no of students:    3

Enter the usn,Name,Branch, sem,PhoneNo of the student:

111

aaa

cs

1

111111

Enter the usn,Name,Branch, sem,PhoneNo of the student:

222

bbb

ec

2

222222

Enter the usn,Name,Branch, sem,PhoneNo of the student:

333

ccc

ec

3

333333

~~~Menu~~~

Enter your choice for SLL operation

1:Create SLL of Student Nodes

2:DisplayStatus

3:InsertAtEnd

4:DeleteAtEnd

5:Stack Demo using SLL(Insertion and Deletion at Front)

6:Exit

Enter your choice:2

The contents of SLL:

||1|| USN:333| Name:ccc| Branch:ec| Sem:3| Ph:333333|

||2|| USN:222| Name:bbb| Branch:ec| Sem:2| Ph:222222|

||3|| USN:111| Name:aaa| Branch:cs| Sem:1| Ph:111111|

 No of student nodes is 3

~~~Menu~~~

Enter your choice for SLL operation

1:Create SLL of Student Nodes

2:DisplayStatus

3:InsertAtEnd

4:DeleteAtEnd

5:Stack Demo using SLL(Insertion and Deletion at Front)

6:Exit

Enter your choice:3

Enter the usn,Name,Branch, sem,PhoneNo of the student:

444

ddd

ec

4

444444

~~~Menu~~~

Enter your choice for SLL operation

1:Create SLL of Student Nodes

2:DisplayStatus

3:InsertAtEnd

4:DeleteAtEnd

5:Stack Demo using SLL(Insertion and Deletion at Front)

6:Exit

Enter your choice:2

The contents of SLL:

||1|| USN:333| Name:ccc| Branch:ec| Sem:3| Ph:333333|

||2|| USN:222| Name:bbb| Branch:ec| Sem:2| Ph:222222|

||3|| USN:111| Name:aaa| Branch:cs| Sem:1| Ph:111111|

||4|| USN:444| Name:ddd| Branch:ec| Sem:4| Ph:444444|

 No of student nodes is 4

~~~Menu~~~

Enter your choice for SLL operation

1:Create SLL of Student Nodes

2:DisplayStatus

3:InsertAtEnd

4:DeleteAtEnd

5:Stack Demo using SLL(Insertion and Deletion at Front)

6:Exit

Enter your choice:4

The student node with the usn: 444 is deleted

~~~Menu~~~

Enter your choice for SLL operation

1:Create SLL of Student Nodes

2:DisplayStatus

3:InsertAtEnd

4:DeleteAtEnd

5:Stack Demo using SLL(Insertion and Deletion at Front)

6:Exit

Enter your choice:2

The contents of SLL:

||1|| USN:333| Name:ccc| Branch:ec| Sem:3| Ph:333333|

||2|| USN:222| Name:bbb| Branch:ec| Sem:2| Ph:222222|

||3|| USN:111| Name:aaa| Branch:cs| Sem:1| Ph:111111|

 No of student nodes is 3

~~~Menu~~~

Enter your choice for SLL operation

1:Create SLL of Student Nodes

2:DisplayStatus

3:InsertAtEnd

4:DeleteAtEnd

5:Stack Demo using SLL(Insertion and Deletion at Front)

6:Exit

Enter your choice:4

The student node with the usn: 111 is deleted

~~~Menu~~~
Enter your choice for SLL operation

1:Create SLL of Student Nodes

2:DisplayStatus

3:InsertAtEnd

4:DeleteAtEnd

5:Stack Demo using SLL(Insertion and Deletion at Front)

6:Exit

Enter your choice:5

~~~Stack Demo using SLL~~~

1:Push operation

2: Pop operation

3: Display

4:Exit

Enter your choice for stack demo: 1

Enter the usn,Name,Branch, sem,PhoneNo of the student:

555

eee

cs

1

555555

~~~Stack Demo using SLL~~~

1:Push operation

2: Pop operation

3: Display

4:Exit

Enter your choice for stack demo:3

The contents of SLL:

||1|| USN:555| Name:eee| Branch:cs| Sem:1| Ph:555555|

||2|| USN:333| Name:ccc| Branch:ec| Sem:3| Ph:333333|

||3|| USN:222| Name:bbb| Branch:ec| Sem:2| Ph:222222|

 No of student nodes is 3

~~~Stack Demo using SLL~~~

1:Push operation

2: Pop operation

3: Display

4:Exit

Enter your choice for stack demo: 1

Enter the usn,Name,Branch, sem,PhoneNo of the student:

666

fff

cs

6

666666

~~~Stack Demo using SLL~~~

1:Push operation

2: Pop operation

3: Display

4:Exit

Enter your choice for stack demo: 3

The contents of SLL:

||1|| USN:666| Name:fff| Branch:cs| Sem:6| Ph:666666|

||2|| USN:555| Name:eee| Branch:cs| Sem:1| Ph:555555|

||3|| USN:333| Name:ccc| Branch:ec| Sem:3| Ph:333333|

||4|| USN:222| Name:bbb| Branch:ec| Sem:2| Ph:222222|

 No of student nodes is 4

~~~Stack Demo using SLL~~~

1:Push operation

2: Pop operation

3: Display

4:Exit

Enter your choice for stack demo: 2

The Student node with usn: 666 is deleted

~~~Stack Demo using SLL~~~

1:Push operation

2: Pop operation

3: Display

4:Exit

Enter your choice for stack demo: 3

The contents of SLL:

||1|| USN:555| Name:eee| Branch:cs| Sem:1| Ph:555555|

||2|| USN:333| Name:ccc| Branch:ec| Sem:3| Ph:333333|

||3|| USN:222| Name:bbb| Branch:ec| Sem:2| Ph:222222|

 No of student nodes is 3

~~~Stack Demo using SLL~~~

1:Push operation

2: Pop operation

3: Display

4:Exit

Enter your choice for stack demo: 4

~~~Menu~~~

Enter your choice for SLL operation

1:Create SLL of Student Nodes

2:DisplayStatus

3:InsertAtEnd

4:DeleteAtEnd

5:Stack Demo using SLL(Insertion and Deletion at Front)

6:Exit

Enter your choice:6

Also Credits to: 

Manoj Taleka  (manoj89biet@gmail.com)

Yashaswini Jogi (jogi.yash@gmail.com)

Lab Program 6 Circular Queue 15CSL38 Data Structures in C Lab

Lab Program 6:

Design, Develop and Implement a menu driven Program in C for the following operations on Circular QUEUE of Characters (Array Implementation of Queue with maximum size MAX)
a. Insert an Element on to Circular QUEUE
b. Delete an Element from Circular QUEUE
c. Demonstrate Overflow and Underflow situations on Circular QUEUE
d. Display the status of Circular QUEUE
e. Exit
Support the program with appropriate functions for each of the above operations

#include <stdio.h>
#include<stdlib.h>
#include<stdio_ext.h>
#define MAX 3

char cq[MAX];
int front = -1, rear = -1;

void insert(char);
void delete();
void display();

void main()
{
             int ch;
             char item;
             while(1)
             {
                            printf("\n\n~~Main Menu~~");
                            printf("\n==> 1. Insertion and Overflow Demo");
                            printf("\n==> 2. Deletion and Underflow Demo");
                            printf("\n==> 3. Display");
                            printf("\n==> 4. Exit");
                            printf("\nEnter Your Choice: ");
                            scanf("%d", &ch);
                            __fpurge(stdin);
                           switch(ch)
                          {
                                           case 1:        printf("\n\nEnter the element to be inserted: ");
                                                              scanf("%c", &item);
                                                              insert(item);
                                                              break;
                                           case 2:        delete();
                                                              break;
                                           case 3:        display();
                                                              break;
                                            case 4:       exit(0);
                                            default:      printf("\n\nPlease enter a valid choice");
                            }
               }
}

void insert(char item)
{
                 if(front == (rear+1)%MAX)
                 {
                              printf("\n\n~~Circular Queue Overflow~~");
                 }
                 else
                 {
                             if(front == -1)
                                             front = rear = 0;
                             else
                                              rear = (rear+1)%MAX;
                             cq[rear] = item;
                  }
}

void delete()
{
                char item;
                if(front == -1)
                {
                              printf("\n\n~~Circular Queue Underflow~~");
                }
                else
                {
                               item = cq[front];
                               printf("\n\nDeleted element from the queue is: %c ",item );
                               

                               if(front == rear) //only one element
                                                front = rear = -1;
                               else
                                               front = (front+1)%MAX;
                 }
}


void display ()
{
                   int i ;
                   if(front == -1)
                   {
                                 printf("\n\nCircular Queue Empty");
                   }
                   else
                   {
                                printf("\nCircular Queue contents are:\n");
                                printf("Front[%d]-> ", front);
                               for(i = front; i != rear ; i = (i+1)%MAX)
                               {
                                                   printf(" %c", cq[i]);
                               }
                               printf(" %c", cq[i]);
                               printf(" <-[%d]Rear", rear);
                    }
}


Output:
~~Main Menu~~
==> 1. Insertion and Overflow Demo
==> 2. Deletion and Underflow Demo
==> 3. Display
==> 4. Exit
Enter Your Choice: 1

Enter the element to be inserted: A

~~Main Menu~~
==> 1. Insertion and Overflow Demo
==> 2. Deletion and Underflow Demo
==> 3. Display
==> 4. Exit
Enter Your Choice: 1
Enter the element to be inserted: B

~~Main Menu~~
==> 1. Insertion and Overflow Demo
==> 2. Deletion and Underflow Demo
==> 3. Display
==> 4. Exit
Enter Your Choice: 1
Enter the element to be inserted: C

~~Main Menu~~
==> 1. Insertion and Overflow Demo
==> 2. Deletion and Underflow Demo
==> 3. Display
==> 4. Exit
Enter Your Choice: 1

Enter the element to be inserted: D
~~Circular Queue Overflow~~

~~Main Menu~~
==> 1. Insertion and Overflow Demo
==> 2. Deletion and Underflow Demo
==> 3. Display
==> 4. Exit
Enter Your Choice: 3

Circular Queue contents are:
Front[0]-> A B C <-[2]Rear

~~Main Menu~~
==> 1. Insertion and Overflow Demo
==> 2. Deletion and Underflow Demo
==> 3. Display
==> 4. Exit
Enter Your Choice: 2

Deleted element from the queue is: A

~~Main Menu~~
==> 1. Insertion and Overflow Demo
==> 2. Deletion and Underflow Demo
==> 3. Display
==> 4. Exit
Enter Your Choice: 3

Circular Queue contents are:
Front[1]-> B C <-[2]Rear

~~Main Menu~~
==> 1. Insertion and Overflow Demo
==> 2. Deletion and Underflow Demo
==> 3. Display
==> 4. Exit
Enter Your Choice: 1

Enter the element to be inserted: E

~~Main Menu~~
==> 1. Insertion and Overflow Demo
==> 2. Deletion and Underflow Demo
==> 3. Display
==> 4. Exit
Enter Your Choice: 3

Circular Queue contents are:
Front[1]-> B C E <-[0]Rear

~~Main Menu~~
==> 1. Insertion and Overflow Demo
==> 2. Deletion and Underflow Demo
==> 3. Display
==> 4. Exit
Enter Your Choice: 4


Also Credits to: 
Manoj Taleka  (manoj89biet@gmail.com)
Yashaswini Jogi (jogi.yash@gmail.com)

Lab Program 5a Evaluation of Suffix Expression 15CSL38 Data Structures in C Lab

Lab Program 5a:

Design, Develop and Implement a Program in C for the following Stack Applications
a. Evaluation of Suffix expression with single digit operands and operators: +, -, *, /, %, ^

 #include<stdio.h>

#include<stdlib.h>

#include<math.h>

int i, top = -1;

int op1, op2, res, s[20];

char postfix[90], symb;

void push(int item)

{

            top = top+1;

            s[top] = item;

}

int pop()

{

            int item;

            item  =  s[top];

            top = top-1;

            return item;

}

void main()

{

            printf("\nEnter a valid postfix expression:\n");

            scanf("%s", postfix);

            for(i=0; postfix[i]!='\0'; i++)

            {

                        symb = postfix[i];

                        if(isdigit(symb))

                        {

                                    push(symb - '0');

                        }

                        else

                        {

                                    op2 = pop();

                                    op1 = pop();

                                    switch(symb)

                                    {

                                                case '+':            push(op1+op2);

                                                                        break;

                                                case '-':             push(op1-op2);

                                                                        break;

                                                case '*':            push(op1*op2);

                                                                        break;

                                                case '/':             push(op1/op2);

                                                                        break;

                                                case '%':           push(op1%op2);

                                                                        break;

                                                case '$':

                                                case '^':            push(pow(op1, op2));

                                                                        break;

                                                default :   push(0);

                                    }

                        }

            }

            res = pop();

            printf("\n Result = %d", res);

}

Output:

To compile in Linux: gcc –lm 5.c

Enter a valid postfix expression:

623+-382/+*2$3+

Result = 52

Enter a valid postfix expression:

42$3*3-84/11+/+

Result = 46

Also Credits to: 

Manoj Taleka  (manoj89biet@gmail.com)

Yashaswini Jogi (jogi.yash@gmail.com)

Lab Program 4 Infix to Postfix 15CSL38 Data Structures in C Lab

Lab Program 4: 

Design, Develop and Implement a Program in C for converting an Infix Expression to Postfix Expression. Program should support for both parenthesized and free parenthesized expressions with the operators: +, -, *, /, %(Remainder), ^(Power) and alphanumeric operands.

#include<stdio.h>

#include<stdlib.h>

void evaluate();

void push(char);

char pop();

int prec(char);

char infix[30], postfix[30], stack[30];

int top = -1;

void main()

{

            printf("\nEnter the valid infix expression:\t");

            scanf("%s", infix);

            evaluate();

            printf("\nThe entered infix expression is :\n %s \n", infix);

            printf("\nThe corresponding postfix expression is :\n %s \n", postfix);

}

void evaluate()

{

            int i = 0, j = 0;

            char symb, temp;

            push('#');

            for(i=0; infix[i] != '\0'; i++)

            {

                        symb = infix[i];

                        switch(symb)

                        {

                                    case '(' :            push(symb);

                                                            break;

                                    case ')' :            temp = pop();

                                                            while(temp != '(' )

                                                            {

                                                                        postfix[j] = temp;

                                                                        j++;

                                                                        temp = pop();

                                                            }

                                                            break;

                                    case '+' :

                                    case '-' :

                                    case '*' :

                                    case '/' :

                                    case '%' :

                                    case '^' :

                                    case '$'  :          while( prec(stack[top]) >= prec(symb) )

                                                            {

                                                                        temp = pop();

                                                                        postfix[j] = temp;

                                                                        j++;

                                                            }

                                                            push(symb);

                                                            break;

                                    default:            postfix[j] = symb;

                                                            j++;

                         }

            }

            while(top > 0)

            {

                        temp = pop();

                        postfix[j] = temp;

                        j++;

            }

            postfix[j] = '\0';

}

 void push(char item)

{

            top = top+1;

            stack[top] = item;

}

 char pop()

{

            char item;

            item = stack[top];

            top = top-1;

            return item;

}

int prec(char symb)

{

            int p;

            switch(symb)

            {

                        case '#' :           p = -1;

                                                break;

                        case '(' :

                        case ')' :            p = 0;

                                                break;

                        case '+' :

                        case '-' :            p = 1;

                                                break;

                        case '*' :

                        case '/' :

                        case '%' :          p = 2;

                                                break;

                        case '^' :

                        case '$' :           p = 3;

                                                break;

            }

            return p;

}

Output:

Enter the valid infix expression:       (a+b)+c/d*e

The entered infix expression is :

 (a+b)+c/d*e

The corresponding postfix expression is :

 ab+cd/e*+

Also Credits to: 

Manoj Taleka  (manoj89biet@gmail.com)

Yashaswini Jogi (jogi.yash@gmail.com)