DATA STRUCTURES LABORATORY – BCSL305

In this blog post, you will find solutions for the laboratory subject DATA STRUCTURES LABORATORY (BCSL305) course work for the III semester of VTU university. The solutions to the lab component are coded in C. We recommend using the Code:Blocks as the integrated development environment (IDE). Along with C programs for each question I have provided samples of program output as well.

You can find the lab syllabus here.

After getting the necessary development environment setup, Now lets focus on the solutions. Click on the appropriate hyperlink to go to your program of choice.

  1. Calendar Application
  2. String Operations
  3. Stack of Integers
  4. Infix to Postfix Conversion
  5. Stack Applications
  6. Circular Queue
  7. Singly Linked List of Student Data
  8. Doubly Linked List of Employee Data
  9. Polynomial Evaluation and Addition
  10. Binary Search Tree
  11. Graph Reachability using DFS/BFS
  12. Hashing & Linear Probing

Program 01 : Calendar Application

Develop a Program in C for the following:
a) Declare a calendar as an array of 7 elements (A dynamically Created array) to represent 7 days of a week. Each Element of the array is a structure having three fields. The first field is the name of the Day (A dynamically allocated String), The second field is the date of the Day (A integer), the third field is the description of the activity for a particular day (A dynamically allocated String).
b) Write functions create(), read() and display(); to create the calendar, to read the data from the keyboard and to print weeks activity details report on screen.

C Code

/***************************************************************************
*File		: 01Calender.c
*Description: Calendar operations
*Author		: Prabodh C P
*Compiler	: gcc compiler, Ubuntu 22.04
*Date		: 28 September 2023
***************************************************************************/

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

#define NUM_DAYS_IN_WEEK 7

// Structure to represent a day
typedef struct
{
    char *acDayName;    // Dynamically allocated string for the day name
    int iDate;         // Date of the day
    char *acActivity;   // Dynamically allocated string for the activity description
}DAYTYPE;

void fnFreeCal(DAYTYPE *); 
void fnDispCal(DAYTYPE *);
void fnReadCal(DAYTYPE *); 
DAYTYPE *fnCreateCal();

int main() 
{
    // Create the calendar
    DAYTYPE *weeklyCalendar = fnCreateCal();

    // Read data from the keyboard
    fnReadCal(weeklyCalendar);

    // Display the week's activity details
    fnDispCal(weeklyCalendar);

    // Free allocated memory
    fnFreeCal(weeklyCalendar);

    return 0;
}

DAYTYPE *fnCreateCal() 
{
    DAYTYPE *calendar = (DAYTYPE *)malloc(NUM_DAYS_IN_WEEK * sizeof(DAYTYPE));

    
    for(int i = 0; i < NUM_DAYS_IN_WEEK; i++) 
	{
        calendar[i].acDayName = NULL;
        calendar[i].iDate = 0;
        calendar[i].acActivity = NULL;
    }

    return calendar;
}

void fnReadCal(DAYTYPE *calendar) 
{
	char cChoice;
    for(int i = 0; i < NUM_DAYS_IN_WEEK; i++) 
	{
        printf("Do you want to enter details for day %d [Y/N]: ", i + 1);
        scanf("%c", &cChoice); getchar();
        
        if(tolower(cChoice) == 'n')
        	continue;
        
        printf("Day Name: ");
        char nameBuffer[50];
        scanf("%s", nameBuffer);
        calendar[i].acDayName = strdup(nameBuffer);  // Dynamically allocate and copy the string


        printf("Date: ");
        scanf("%d", &calendar[i].iDate);

        
        printf("Activity: ");
        char activityBuffer[100];
        scanf(" %[^n]", activityBuffer);  // Read the entire line, including spaces
        calendar[i].acActivity = strdup(activityBuffer); 

        printf("n");
        getchar();		//remove trailing enter character in input buffer
    }
}


void fnDispCal(DAYTYPE *calendar) 
{
    printf("nWeek's Activity Details:n");
    for(int i = 0; i < NUM_DAYS_IN_WEEK; i++) 
	{
        printf("Day %d:n", i + 1);
		if(calendar[i].iDate == 0)
		{
			printf("No Activitynn");
			continue;
		}
		
        printf("  Day Name: %sn", calendar[i].acDayName);
        printf("  Date: %dn", calendar[i].iDate);
        printf("  Activity: %snn", calendar[i].acActivity);
    }
}

void fnFreeCal(DAYTYPE *calendar) 
{
    for(int i = 0; i < NUM_DAYS_IN_WEEK; i++) 
	{
        free(calendar[i].acDayName);
        free(calendar[i].acActivity);
    }
    free(calendar);
}

Output

putta:~/.../Programs$ ./a.out 
Do you want to enter details for day 1 [Y/N]: N
Do you want to enter details for day 2 [Y/N]: Y 
Day Name: Monday
Date: 10
Activity: Meeting with Chairman.      

Do you want to enter details for day 3 [Y/N]: N
Do you want to enter details for day 4 [Y/N]: N
Do you want to enter details for day 5 [Y/N]: Y
Day Name: Thursday
Date: 13
Activity: Product Survey 

Do you want to enter details for day 6 [Y/N]: Y
Day Name: Friday
Date: 14
Activity: Budget Breakdown and Planning

Do you want to enter details for day 7 [Y/N]: Y
Day Name: Saturday
Date: 15
Activity: Outing with family


Week's Activity Details:
Day 1:
No Activity

Day 2:
  Day Name: Monday
  Date: 10
  Activity: Meeting with Chairman.
  
Day 3:
No Activity

Day 4:
No Activity

Day 5:
  Day Name: Thursday
  Date: 13
  Activity: Product Survey

Day 6:
  Day Name: Friday
  Date: 14
  Activity: Budget Breakdown and Planning

Day 7:
  Day Name: Saturday
  Date: 15
  Activity: Outing with family

Program 02 : String Operations

Develop a Program in C for the following operations on Strings.
a. Read a main String (STR), a Pattern String (PAT) and a Replace String (REP)
b. Perform Pattern Matching Operation: Find and Replace all occurrences of PAT in STR with REP if PAT exists in STR. Report suitable messages in case PAT does not exist in STR
Support the program with functions for each of the above operations. Don’t use Built-in functions.

C Code

/***************************************************************************
*File		: 02_SearchReplaceStringOps.c
*Description: Search for a pattern text in main text and replace it with replacement string
*Author		: Prabodh C P
*Compiler	: gcc compiler, Ubuntu 22.04
*Date		: 28 September 2023
***************************************************************************/

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

int main()
{
    char acMainStr[200], acSrchStr[30], acRepStr[30], acResStr[200], acCopyStr[200];
    int i=0, j=0 ,k=0, l, iMtchCnt, iStop, len, iNumOfMatch=0;

    printf("nEnter the main stringn");
	scanf(" %[^n]", acMainStr);
	
    printf("nEnter the Pattern stringn");
	scanf(" %[^n]", acSrchStr);

    printf("nEnter the Replace stringn");
	scanf(" %[^n]", acRepStr);    

    strcpy(acCopyStr, acMainStr);
    for(i=0;i<(strlen(acMainStr)-strlen(acSrchStr)+1);i++)
    {
        iMtchCnt = 0;
        for(j=0;j<strlen(acSrchStr);j++)
        {
            if(acMainStr[i+j] == acSrchStr[j])
            {
                iMtchCnt++;
            }
            else
            {
                break;
            }
            if(iMtchCnt == strlen(acSrchStr))   //Check if number of character matches equals length of pattern string
            {
                iNumOfMatch++;      //update number of total matches by 1
//                printf("nMatch occured at %d position in textn", i+1);
                for(k=0;k<i;k++)
                {
                    acResStr[k] = acMainStr[k];     //copy till the ith character where the match occured
                }
                iStop = k + strlen(acSrchStr); //point from where rest of the original string has to be copied
                acResStr[k] = '';
                strcat(acResStr, acRepStr); // append the replacement string
                len = strlen(acResStr);
                for(k=iStop, l=0; acMainStr[k] != '';k++, l++) //copy rest of original string
                {
                    acResStr[len+l] = acMainStr[k];
                }
                acResStr[len+l] = '';
//                printf("n%s",acResStr);
                strcpy(acMainStr,acResStr);
            }
        }

    }
    printf("nInput Textn");
    printf("%sn",acCopyStr);

    if(iNumOfMatch > 0)
    {
        printf("n%d matches occurednnText after replacing matched patterns is shown belown", iNumOfMatch);
        printf("n%sn",acResStr);
    }
    else
    {
        printf("nPattern String not found in Textn");
    }
    return 0;
}

Output

putta:~/.../Programs$ ./a.out 

Enter the main string
Raju and Ramu went to shop to buy milk and cakes.

Enter the Pattern string
and

Enter the Replace string
&

Input Text
Raju and Ramu went to shop to buy milk and cakes.

2 matches occured

Text after replacing matched patterns is shown below

Raju & Ramu went to shop to buy milk & cakes.

Program 03 : Stack of Integers

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

C Code

/***************************************************************************
*File		: 03_Stack.c
*Description: Stack Operations
*Author		: Prabodh C P
*Compiler	: gcc compiler, Ubuntu 22.04
*Date		: 28 September 2023
***************************************************************************/

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

#define MAX 4

bool fnStkFull(int);
bool fnStkEmpty(int);
void fnPush(int [], int, int*);
int fnPop(int [], int*);
void fnDisplay(int[], int);
int fnPeek(int [], int);
bool fnChkPalindrome(int);

int main(void)
{
	int stkArray[MAX];
	int top = -1;
	int iElem, iChoice;

	for(;;)
	{
		printf("nSTACK OPERATIONSn");
		printf("====================");
		printf("n1.Pushn2.Popn3.Displayn4.Peekn5.Check Palindromen6.Demonstarte Overflown7.Demonstarte Underflown8.EXITn");
		printf("Enter your choicen");
		scanf("%d",&iChoice);
		switch(iChoice)
		{
			case 1: if(!fnStkFull(top))
                    {
                        printf("nEnter element to be pushed onto the stackn");
                        scanf("%d", &iElem);
                        fnPush(stkArray, iElem, &top);
                    }
                    else
                    {
                        printf("nStack Overflown");
                    }
					break;

			case 2: if(!fnStkEmpty(top))
                    {
                        iElem = fnPop(stkArray, &top);
                        printf("nPopped Element is %dn", iElem);
                    }
                    else
                    {
                        printf("nStack Underflown");
                    }
					break;

			case 3: if(fnStkEmpty(top))
                    {
                        printf("nStack Emptyn");
                    }
                    else
                    {
                        fnDisplay(stkArray, top);
                    }
					break;

			case 4: if(!fnStkEmpty(top))
					{
						iElem = fnPeek(stkArray, top);
						printf("nElement at the  top of the stack is %dn", iElem);
					}
					else
						printf("nEmpty Stackn");
					break;

			case 5: printf("nEnter number to be checked for a palindrome : ");
                    scanf("%d", &iElem);
                    if(fnChkPalindrome(iElem))
                    {
                        printf("n%d is a palindromen", iElem);
                    }
                    else
                    {
                        printf("n%d is not a palindromen", iElem);
                    }
                    break;

			case 6: if(!fnStkFull(top))
                        printf("nThere are currently %d elements in StacknPush %d elemnts for Stack to overflow", top+1, MAX - (top+1));
                    while(!fnStkFull(top))
                    {
                        printf("nEnter an element : ");
                        scanf("%d", &iElem);
                        fnPush(stkArray, iElem, &top);
                    }
                    printf("nStack Overflow cannot push elements onto the stackn");
                    break;

			case 7: if(!fnStkEmpty(top))
                        printf("nThere are currently %d elements in StacknPop out %d elemnts for Stack to Underflow", top+1, MAX - (top+1));
                    while(!fnStkEmpty(top))
                    {
                        iElem = fnPop(stkArray, &top);
                        printf("nPopped Element is %dn", iElem);
                    }
                    printf("nStack Underflow cannot pop elements from the stackn");
                    break;

			case 8: exit(1);

			default: printf("nWrong choicen");
		}
	}
	return 0;
}

bool fnStkFull(int t)
{
	return ((t == MAX-1) ? true : false);
}

bool fnStkEmpty(int t)
{
	return ((t == -1) ? true : false);
}

void fnPush(int stk[], int iElem, int *t)
{
	*t = *t + 1;
	stk[*t] = iElem;
}

int fnPop(int stk[], int *t)
{
	int iElem;
	iElem = stk[*t];
	*t = *t - 1;

	return iElem;
}

void fnDisplay(int stk[], int t)
{
	int i;

	printf("nStack Contents are: n");
	for(i = t ; i > -1; --i)
	{
		printf("t%dn", stk[i]);
	}
	printf("Stack has %d elementsn", t+1);
}

int fnPeek(int stk[], int t)
{
	return stk[t];
}

bool fnChkPalindrome(int iVal)
{
    int palStk[10];
    int t = -1, iDig, iRev = 0;

    int iCopy = iVal;

    while(iCopy != 0)
    {
        iDig = iCopy % 10;
        fnPush(palStk, iDig, &t);
        iCopy /= 10;
    }
    int p = 0;
    while(p <= t)
    {
        iDig = palStk[p];
        iRev = iRev *10 + iDig;
        p++;
    }
    if(iRev == iVal)
        return true;
    else
        return false;
}

Output

putta:~/.../Programs$ ./a.out 

STACK OPERATIONS
====================
1.Push
2.Pop
3.Display
4.Peek
5.Check Palindrome
6.Demonstarte Overflow
7.Demonstarte Underflow
8.EXIT
Enter your choice
5

Enter number to be checked for a palindrome : 456

456 is not a palindrome

STACK OPERATIONS
====================
1.Push
2.Pop
3.Display
4.Peek
5.Check Palindrome
6.Demonstarte Overflow
7.Demonstarte Underflow
8.EXIT
Enter your choice
5

Enter number to be checked for a palindrome : 5665

5665 is a palindrome

STACK OPERATIONS
====================
1.Push
2.Pop
3.Display
4.Peek
5.Check Palindrome
6.Demonstarte Overflow
7.Demonstarte Underflow
8.EXIT
Enter your choice
6

There are currently 0 elements in Stack
Push 4 elemnts for Stack to overflow
Enter an element : 4

Enter an element : 5

Enter an element : 6

Enter an element : 7

Stack Overflow cannot push elements onto the stack

STACK OPERATIONS
====================
1.Push
2.Pop
3.Display
4.Peek
5.Check Palindrome
6.Demonstarte Overflow
7.Demonstarte Underflow
8.EXIT
Enter your choice
3

Stack Contents are: 
	7
	6
	5
	4
Stack has 4 elements

STACK OPERATIONS
====================
1.Push
2.Pop
3.Display
4.Peek
5.Check Palindrome
6.Demonstarte Overflow
7.Demonstarte Underflow
8.EXIT
Enter your choice
2

Popped Element is 7

STACK OPERATIONS
====================
1.Push
2.Pop
3.Display
4.Peek
5.Check Palindrome
6.Demonstarte Overflow
7.Demonstarte Underflow
8.EXIT
Enter your choice
7

There are currently 3 elements in Stack
Pop out 1 elemnts for Stack to Underflow
Popped Element is 6

Popped Element is 5

Popped Element is 4

Stack Underflow cannot pop elements from the stack

STACK OPERATIONS
====================
1.Push
2.Pop
3.Display
4.Peek
5.Check Palindrome
6.Demonstarte Overflow
7.Demonstarte Underflow
8.EXIT
Enter your choice
1

Enter element to be pushed onto the stack
12

STACK OPERATIONS
====================
1.Push
2.Pop
3.Display
4.Peek
5.Check Palindrome
6.Demonstarte Overflow
7.Demonstarte Underflow
8.EXIT
Enter your choice
1

Enter element to be pushed onto the stack
13

STACK OPERATIONS
====================
1.Push
2.Pop
3.Display
4.Peek
5.Check Palindrome
6.Demonstarte Overflow
7.Demonstarte Underflow
8.EXIT
Enter your choice
3

Stack Contents are: 
	13
	12
Stack has 2 elements

STACK OPERATIONS
====================
1.Push
2.Pop
3.Display
4.Peek
5.Check Palindrome
6.Demonstarte Overflow
7.Demonstarte Underflow
8.EXIT
Enter your choice
4

Element at the  top of the stack is 13

STACK OPERATIONS
====================
1.Push
2.Pop
3.Display
4.Peek
5.Check Palindrome
6.Demonstarte Overflow
7.Demonstarte Underflow
8.EXIT
Enter your choice
8

Program 04 : Infix to Postfix Conversion

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

C Code

/***************************************************************************
*File		: 04_Infix_Postfix.c
*Description: Infix to Postfix conversion
*Author		: Prabodh C P
*Compiler	: gcc compiler, Ubuntu 22.04
*Date		: 28 September 2023
***************************************************************************/

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

#define STK_SIZE 10

void fnPush(char [], int*, char);
char fnPop(char [], int*);
int fnPrecd(char);

int main()
{
	int i, j=0;
	char acExpr[50], acStack[50], acPost[50], cSymb;
	int top = -1;

	printf("nEnter a valid infix expressionn");
	scanf("%s", acExpr);

	fnPush(acStack, &top, '#');
	for(i=0;acExpr[i]!=''; ++i)
	{
		cSymb = acExpr[i];
		if(isalnum(cSymb))
		{
			acPost[j++] = cSymb;
		}
		else if(cSymb == '(')
		{
			fnPush(acStack, &top, cSymb);
		}
		else if(cSymb == ')')
		{
			while(acStack[top] != '(')
			{
				acPost[j++] = fnPop(acStack, &top);
			}
			fnPop(acStack, &top);
		}
		else
		{
			while(fnPrecd(acStack[top]) >= fnPrecd(cSymb))
			{
				if((cSymb == '^') && (acStack[top] == '^'))
					break;
                acPost[j++] = fnPop(acStack, &top);
			}
			fnPush(acStack, &top, cSymb);
		}

	}
	while(acStack[top] != '#')
	{
		acPost[j++] = fnPop(acStack, &top);
	}
	acPost[j] = '';

	printf("nInfix Expression is %sn", acExpr);
	printf("nPostfix Expression is %sn", acPost);
	return 0;
}

void fnPush(char Stack[], int *t , char elem)
{
	*t = *t + 1;
	Stack[*t] = elem;

}

char fnPop(char Stack[], int *t)
{
	char elem;
	elem = Stack[*t];
	*t = *t -1;
	return elem;
}

int fnPrecd(char ch)
{
	int iPrecdVal;
	switch(ch)
	{
		case '#' : 	iPrecdVal = -1;	break;
		case '(' : 	iPrecdVal = 0;	break;
		case '+' :
		case '-' : 	iPrecdVal = 1;	break;
		case '%' :
		case '*' :
		case '/' : 	iPrecdVal = 2;	break;
		case '^' :	iPrecdVal = 3;	break;
	}
	return iPrecdVal;
}

Output

putta:~/.../Programs$ ./a.out 

Enter a valid infix expression
a^b^c

Infix Expression is a^b^c

Postfix Expression is abc^^

putta:~/.../Programs$ ./a.out 

Enter a valid infix expression
(A^B)^C      

Infix Expression is (A^B)^C

Postfix Expression is AB^C^

putta:~/.../Programs$ ./a.out 

Enter a valid infix expression
(A+B*C)-(D/E^F)

Infix Expression is (A+B*C)-(D/E^F)

Postfix Expression is ABC*+DEF^/-

Program 05 : Stack Applications

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

a. Evaluation of Suffix expression

C Code

/***************************************************************************
*File		: 05A_Eval_Postfix.c
*Description: Evaluaion of Postfix expression
*Author		: Prabodh C P
*Compiler	: gcc compiler, Ubuntu 22.04
*Date		: 28 September 2023
***************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <ctype.h>


#define STK_SIZE 10

void fnPush(int [], int*, int);
int fnPop(int [], int*);

int main()
{
	int iaStack[50], i, iOp1, iOp2, iRes;
	char acExpr[50], cSymb;
	int top = -1;

	printf("nEnter a valid postfix expressionn");
	scanf("%s", acExpr);

	for(i=0; i<strlen(acExpr); i++)
	{
		cSymb = acExpr[i];
		if(isdigit(cSymb))
		{
			fnPush(iaStack, &top, cSymb-'0');
		}
		else
		{
			iOp2 = fnPop(iaStack, &top);
			iOp1 = fnPop(iaStack, &top);
			switch(cSymb)
			{
				case '+' : 	iRes = iOp1 + iOp2;
							break;
				case '-' : 	iRes = iOp1 - iOp2;
							break;
				case '*' : 	iRes = iOp1 * iOp2;
							break;
				case '/' : 	iRes = iOp1 / iOp2;
							break;
				case '%' : 	iRes = iOp1 % iOp2;
							break;
				case '^' : 	iRes = (int)pow(iOp1 , iOp2);
							break;
			}
			fnPush(iaStack, &top, iRes);
		}

	}
	iRes = fnPop(iaStack, &top);
	printf("nValue of %s expression is %dn", acExpr, iRes);
	return 0;
}

void fnPush(int Stack[], int *t , int elem)
{
	*t = *t + 1;
	Stack[*t] = elem;

}

int fnPop(int Stack[], int *t)
{
	int elem;
	elem = Stack[*t];
	*t = *t -1;
	return elem;
}

Output

putta:~/.../Programs$ gcc -Wall 05A_Eval_Postfix.c -lm
putta:~/.../Programs$ ./a.out 

Enter a valid postfix expression
45+95-*

Value of 45+95-* expression is 36

putta:~/.../Programs$ ./a.out 

Enter a valid postfix expression
459*+62-+

Value of 459*+62-+ expression is 53

b. Tower of Hanoi problem

C Code

/***************************************************************************
*File		: 05B_TowerOfHanoi.c
*Description: Solution to Tower of Hanoi Problem
*Author		: Prabodh C P
*Compiler	: gcc compiler, Ubuntu 22.04
*Date		: 28 September 2023
***************************************************************************/

#include <stdio.h>

void towers(int, char, char, char);

int main()
{

    int num;
    printf("Enter the number of disks : ");

    scanf("%d", &num);

    printf("The sequence of moves involved in the Tower of Hanoi are :n");

    towers(num, 'A', 'C', 'B');

    printf("n");

    return 0;

}

void towers(int num, char frompeg, char topeg, char auxpeg)
{
    if (num == 1)
    {
        printf("n Move disk 1 from peg %c to peg %c", frompeg, topeg);
        return;
    }

    towers(num - 1, frompeg, auxpeg, topeg);

    printf("n Move disk %d from peg %c to peg %c", num, frompeg, topeg);

    towers(num - 1, auxpeg, topeg, frompeg);

}

Output

Enter the number of disks : 4
The sequence of moves involved in the Tower of Hanoi are :

 Move disk 1 from peg A to peg B
 Move disk 2 from peg A to peg C
 Move disk 1 from peg B to peg C
 Move disk 3 from peg A to peg B
 Move disk 1 from peg C to peg A
 Move disk 2 from peg C to peg B
 Move disk 1 from peg A to peg B
 Move disk 4 from peg A to peg C
 Move disk 1 from peg B to peg C
 Move disk 2 from peg B to peg A
 Move disk 1 from peg C to peg A
 Move disk 3 from peg B to peg C
 Move disk 1 from peg A to peg B
 Move disk 2 from peg A to peg C
 Move disk 1 from peg B to peg C

Program 06 : Circular Queue

Develop 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

C Code

/***************************************************************************
*File		: 06_CircQueue.c
*Description: Circular Queue operations
*Author		: Prabodh C P
*Compiler	: gcc compiler, Ubuntu 22.04
*Date		: 28 September 2023
***************************************************************************/

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

#define QUEUE_SIZE 5

void fnInsertRear(char [], int*, int*, char);
char fnDeleteFront(char[], int*, int*);
void fnDisplay(char [], int, int);
bool fnQueueFull(int, int);
bool fnQueueEmpty(int, int);

int main()
{
    char myQueue[QUEUE_SIZE];
    int iFront = -1, iRear = -1;
    int iChoice;
    char cElem;
    
    for(;;)
    {
	    printf("nQueue Operationsn");
	    printf("=====================");
	    printf("n1.Qinsertn2.Qdeleten3.Qdisplayn4.Exitn");
	    printf("Enter your choicen");
	    scanf("%d",&iChoice);
	    getchar();	//read trialing enter character
	    switch(iChoice)
	    {
		    case 1: if(!fnQueueFull(iFront, iRear))
		            {
		                printf("nEnter an element : ");
		                scanf("%c", &cElem);
		                fnInsertRear(myQueue, &iFront, &iRear, cElem);
		            }
		            else
		            {
		                printf("nQueue is Fulln");
		            }

			    break;
		    case 2: if(!fnQueueEmpty(iFront, iRear))
		            {
		                cElem = fnDeleteFront(myQueue, &iFront, &iRear);
		                printf("nDeleted element is %cn", cElem);
		            }
		            else
		            {
		                printf("nQueue is Emptyn");
		            }

			    break;
		    case 3: if(!fnQueueEmpty(iFront, iRear))
		            {
		                printf("nContents of the Queue is n");
		                fnDisplay(myQueue, iFront, iRear);
		            }
		            else
		            {
		                printf("nQueue is Emptyn");
		            }

			    break;
			
		    case 4: exit(0);
		
		    default: printf("nInvalid choicen");

			    break;
	    }
    }
    return 0;
}

bool fnQueueFull(int f, int r)
{
    if((r+1) % QUEUE_SIZE == f)
        return true;
    else
        return false;
}

bool fnQueueEmpty(int f, int r)
{
    if(f == -1)
        return true;
    else
        return false;
}

void fnInsertRear(char queue[], int *f, int *r, char cVal)
{
    if(*r == -1)
    {
        *f = *f + 1;
        *r = *r + 1;
    }
    else
        *r = (*r + 1)%QUEUE_SIZE;
        
    queue[*r] = cVal;
}

char fnDeleteFront(char queue[], int *f, int *r)
{
    char cElem;
    cElem = queue[*f];
    
    if(*f == *r)
    {
        *f = -1;
        *r = -1;
    }
    else
    {
        *f = (*f + 1)%QUEUE_SIZE;
    }
    return cElem;
}

void fnDisplay(char queue[], int f, int r)
{
    int i;
    if(f<=r)
    {
        for(i=f; i<=r; i++)
        {
            printf("%ct", queue[i]);
        }
        printf("n");    
    }
    else
    {
        for(i=f; i<=QUEUE_SIZE-1; i++)
        {
            printf("%ct", queue[i]);
        }
        for(i=0; i<=r; i++)
        {
            printf("%ct", queue[i]);
        }
        printf("n");    
    }
}

Output

putta:~/.../Programs$ ./a.out 

Queue Operations
=====================
1.Qinsert
2.Qdelete
3.Qdisplay
4.Exit
Enter your choice
2

Queue is Empty

Queue Operations
=====================
1.Qinsert
2.Qdelete
3.Qdisplay
4.Exit
Enter your choice
1

Enter an element : I

Queue Operations
=====================
1.Qinsert
2.Qdelete
3.Qdisplay
4.Exit
Enter your choice
1

Enter an element : N

Queue Operations
=====================
1.Qinsert
2.Qdelete
3.Qdisplay
4.Exit
Enter your choice
1

Enter an element : D

Queue Operations
=====================
1.Qinsert
2.Qdelete
3.Qdisplay
4.Exit
Enter your choice
1

Enter an element : I

Queue Operations
=====================
1.Qinsert
2.Qdelete
3.Qdisplay
4.Exit
Enter your choice
1

Enter an element : A

Queue Operations
=====================
1.Qinsert
2.Qdelete
3.Qdisplay
4.Exit
Enter your choice
3

Contents of the Queue is 
I	N	D	I	A	

Queue Operations
=====================
1.Qinsert
2.Qdelete
3.Qdisplay
4.Exit
Enter your choice
1

Queue is Full

Queue Operations
=====================
1.Qinsert
2.Qdelete
3.Qdisplay
4.Exit
Enter your choice
2

Deleted element is I

Queue Operations
=====================
1.Qinsert
2.Qdelete
3.Qdisplay
4.Exit
Enter your choice
2

Deleted element is N

Queue Operations
=====================
1.Qinsert
2.Qdelete
3.Qdisplay
4.Exit
Enter your choice
2

Deleted element is D

Queue Operations
=====================
1.Qinsert
2.Qdelete
3.Qdisplay
4.Exit
Enter your choice
2

Deleted element is I

Queue Operations
=====================
1.Qinsert
2.Qdelete
3.Qdisplay
4.Exit
Enter your choice
2

Deleted element is A

Queue Operations
=====================
1.Qinsert
2.Qdelete
3.Qdisplay
4.Exit
Enter your choice
2

Queue is Empty

Queue Operations
=====================
1.Qinsert
2.Qdelete
3.Qdisplay
4.Exit
Enter your choice
3

Queue is Empty

Queue Operations
=====================
1.Qinsert
2.Qdelete
3.Qdisplay
4.Exit
Enter your choice
4

Program 07 : Singly Linked List of Student Data

Develop a menu driven Program in C for the following operations on Singly Linked List (SLL) of Student Data with the fields: USN, Name, Programme, 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

C Code

/***************************************************************************
*File		: 07_SLL.c
*Description: SLL of N Students Data
*Author		: Prabodh C P
*Compiler	: gcc compiler, Ubuntu 22.04
*Date		: 28 September 2023
***************************************************************************/

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

struct node
{
	char cUSN[11], cName[40], cProgram[4];
	int iSem;
	char cPhNo[11];
	struct node *link;
};

typedef struct node* NODEPTR;

NODEPTR fnGetNode(void);
void fnFreeNode(NODEPTR);
NODEPTR fnInsRear(NODEPTR);
NODEPTR fnDelFront(NODEPTR);
NODEPTR fnInsFront(NODEPTR);
NODEPTR fnDelRear(NODEPTR);
void fnDisplay(NODEPTR);

int main()
{
	NODEPTR first = NULL;
	int iChoice, iNum, i;

    printf("nEnter the number of Students N : "); scanf("%d", &iNum);
	for(i=0;i<iNum;i++)
	{
		printf("nEnter Data for Node %d :n", i+1);
		first = fnInsFront(first);
	}
	for(;;)
	{
		printf("nQUEUE OPERATIONSn");
		printf("====================");
		printf("n1.Insert Frontn2.Insert Rearn3.Delete Frontn4.Delete  Rearn5.Displayn6.Exitn");
		printf("nEnter your choicen");
		scanf("%d",&iChoice);

		switch(iChoice)
		{
			case 1:
				first = fnInsFront(first);
				break;
			case 2:
				first = fnInsRear(first);
				break;

			case 3: first = fnDelFront(first);
				break;

			case 4: first = fnDelRear(first);
				break;

			case 5: fnDisplay(first);
				break;

			case 6: exit(0);
		}
	}
    return 0;
}

NODEPTR fnGetNode()
{
	NODEPTR newborn;
	newborn = (NODEPTR)malloc(sizeof(struct node));

	if(newborn == NULL)
	{
		printf("nMemory Overflow");
		exit(0);
	}

	printf("nEnter USN : ");
	scanf("%s",newborn->cUSN);
	printf("nEnter name : ");
	scanf("%s",newborn->cName);
	printf("nEnter Program name : ");
	scanf("%s", newborn->cProgram);
	printf("nEnter semester : ");
	scanf("%d",&newborn->iSem);
	printf("nEnter Phone no : ");
	scanf("%d",&newborn->iPhNo);

	return newborn;
}


void fnFreeNode(NODEPTR x)
{
	free(x);
}


NODEPTR fnInsRear(NODEPTR first)
{
	NODEPTR temp,cur;

	temp = fnGetNode();
	temp->link = NULL;

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

NODEPTR fnDelFront(NODEPTR first)
{
	NODEPTR temp;
	if(first == NULL)
	{
		printf("nSLL is empty cannot deleten");
		return first;
	}
	temp = first;
	first = first->link;
	printf("nNode deleted is %sn",temp->cName);
	fnFreeNode(temp);
	return first;
}

void fnDisplay(NODEPTR first)
{
	NODEPTR curr;
    int count = 0;
	if(first == NULL)
	{
		printf("nSLL is emptyn");
		return;
	}

	printf("nThe contents of SLL are :n");
	curr = first;
//	printf("n");
    printf("nUSNttNametProgramtSemtPhone num");
	while(curr != NULL)
	{
		printf("n%10st%st%st%dt%d",curr->cUSN, curr->cName, curr->cProgram, curr->iSem, curr->iPhNo);
		curr = curr->link;
		count++;
	}
	printf("nnSLL has %d nodesn", count);
}

NODEPTR fnInsFront(NODEPTR first)
{
    NODEPTR temp;

	temp = fnGetNode();
    temp->link = NULL;

    temp->link = first;
    first = temp;
    return first;

}

NODEPTR fnDelRear(NODEPTR first)
{
	NODEPTR cur, prev;
	if(first == NULL)
	{
		printf("nSLL is empty cannot deleten");
		return first;
	}

	prev = NULL;
	cur = first;
	if(cur->link == NULL)
	{
        printf("nNode deleted for %sn",cur->cName);
        fnFreeNode(cur);
        return NULL;
	}
    while(cur->link != NULL)
    {
    	prev = cur;
        cur = cur->link;
    }

    prev->link = cur->link;
	printf("nNode deleted for %sn",cur->cName);
	fnFreeNode(cur);
	return first;
}

/*CPP*/

Output


putta:~/.../Programs$ gcc -Wall 07_SLL.c 
putta:~/.../Programs$ ./a.out 

Enter the number of Students N : 2

Enter Data for Node 1 :

Enter USN : 1CR22CS045

Enter name : Babu

Enter Program name : CSE

Enter semester : 3

Enter Phone no : 9836345382

Enter Data for Node 2 :

Enter USN : 1SI23EC059

Enter name : Amar

Enter Program name : ECE

Enter semester : 1

Enter Phone no : 9233348255

QUEUE OPERATIONS
====================
1.Insert Front
2.Insert Rear
3.Delete Front
4.Delete  Rear
5.Display
6.Exit

Enter your choice
5

The contents of SLL are :

USN		Name	Program	Sem	Phone num
1SI23EC059	Amar	ECE	1	9233348255
1CR22CS045	Babu	CSE	3	9836345382

SLL has 2 nodes

QUEUE OPERATIONS
====================
1.Insert Front
2.Insert Rear
3.Delete Front
4.Delete  Rear
5.Display
6.Exit

Enter your choice
1

Enter USN : 1KT22ME096

Enter name : Ramu

Enter Program name : ME

Enter semester : 3

Enter Phone no : 8989657422

QUEUE OPERATIONS
====================
1.Insert Front
2.Insert Rear
3.Delete Front
4.Delete  Rear
5.Display
6.Exit

Enter your choice
2

Enter USN : 1PE23EE021

Enter name : Maya

Enter Program name : EEE

Enter semester : 1

Enter Phone no : 8712658824

QUEUE OPERATIONS
====================
1.Insert Front
2.Insert Rear
3.Delete Front
4.Delete  Rear
5.Display
6.Exit

Enter your choice
5

The contents of SLL are :

USN		Name	Program	Sem	Phone num
1KT22ME096	Ramu	ME	3	8989657422
1SI23EC059	Amar	ECE	1	9233348255
1CR22CS045	Babu	CSE	3	9836345382
1PE23EE021	Maya	EEE	1	8712658824

SLL has 4 nodes

QUEUE OPERATIONS
====================
1.Insert Front
2.Insert Rear
3.Delete Front
4.Delete  Rear
5.Display
6.Exit

Enter your choice
4

Node deleted for Maya

QUEUE OPERATIONS
====================
1.Insert Front
2.Insert Rear
3.Delete Front
4.Delete  Rear
5.Display
6.Exit

Enter your choice
3

Node deleted is Ramu

QUEUE OPERATIONS
====================
1.Insert Front
2.Insert Rear
3.Delete Front
4.Delete  Rear
5.Display
6.Exit

Enter your choice
3

Node deleted is Amar

QUEUE OPERATIONS
====================
1.Insert Front
2.Insert Rear
3.Delete Front
4.Delete  Rear
5.Display
6.Exit

Enter your choice
5

The contents of SLL are :

USN		Name	Program	Sem	Phone num
1CR22CS045	Babu	CSE	3	9836345382

SLL has 1 nodes

QUEUE OPERATIONS
====================
1.Insert Front
2.Insert Rear
3.Delete Front
4.Delete  Rear
5.Display
6.Exit

Enter your choice
4

Node deleted for Babu

QUEUE OPERATIONS
====================
1.Insert Front
2.Insert Rear
3.Delete Front
4.Delete  Rear
5.Display
6.Exit

Enter your choice
3

SLL is empty cannot delete

QUEUE OPERATIONS
====================
1.Insert Front
2.Insert Rear
3.Delete Front
4.Delete  Rear
5.Display
6.Exit

Enter your choice
5

SLL is empty

QUEUE OPERATIONS
====================
1.Insert Front
2.Insert Rear
3.Delete Front
4.Delete  Rear
5.Display
6.Exit

Enter your choice
6

Program 08 : Doubly Linked List of Employee Data

Develop a menu driven Program in C for the following operations on Doubly Linked List(DLL) of Employee Data with the fields: SSN, Name, Dept, Designation, Sal, PhNo
a. Create a DLL of N Employees Data by using end insertion.
b. Display the status of DLL and count the number of nodes in it
c. Perform Insertion and Deletion at End of DLL
d. Perform Insertion and Deletion at Front of DLL
e. Demonstrate how this DLL can be used as Double Ended Queue.
f. Exit

C Code

/***************************************************************************
*File		: 08_DLL.c
*Description: DLL of N Employees Data
*Author		: Prabodh C P
*Compiler	: gcc compiler, Ubuntu 22.04
*Date		: 28 September 2023
***************************************************************************/

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

struct node
{
	int iSSN;
	char cName[30], cDept[4], cDesignation[30], cPhNo[11];
    int iSalary;
	struct node *plink;
	struct node *nlink;
};

typedef struct node* NODEPTR;

NODEPTR fnGetNode(void);
void fnFreeNode(NODEPTR);
NODEPTR fnInsRear(NODEPTR);
NODEPTR fnDelFront(NODEPTR);
NODEPTR fnInsFront(NODEPTR);
NODEPTR fnDelRear(NODEPTR);
void fnDisplay(NODEPTR);

int main()
{
	NODEPTR first = NULL;
	int iChoice, iNum, i;

    printf("nEnter the number of Employees N : "); scanf("%d", &iNum);
	for(i=0;i<iNum;i++)
	{
		printf("nEnter Data for Node %d :n", i+1);
		first = fnInsRear(first);
	}


	for(;;)
	{
		printf("nDLL OPERATIONSn");
		printf("====================");
		printf("n1.Insert Rearn2.Delete Frontn3.Insert Frontn4.Delete Rearn5.Displayn6.Exitn");
		printf("nEnter your choicen");
		scanf("%d",&iChoice);

		switch(iChoice)
		{
			case 1: first = fnInsRear(first);
				break;

			case 2: first = fnDelFront(first);
				break;

			case 3: first = fnInsFront(first);
				break;

			case 4: first = fnDelRear(first);
				break;

			case 5: fnDisplay(first);
				break;

			case 6: exit(0);
		}
	}
    return 0;
}

NODEPTR fnGetNode()
{
	NODEPTR newborn;

	newborn = (NODEPTR)malloc(sizeof(struct node));

	if(newborn == NULL)
	{
		printf("nMemory Overflow");
		exit(0);
	}
	printf("nEnter SSN : ");
    scanf("%d",&newborn->iSSN);
    printf("nEnter name : ");
	scanf("%s",newborn->cName);
    printf("nEnter Department : ");
    scanf("%s", newborn->cDept);
    printf("nEnter Designation : ");
    scanf("%s", newborn->cDesignation);
	printf("nEnter Salary : ");
    scanf("%d",&newborn->iSalary);
	printf("nEnter Phone no : ");
    scanf("%s",newborn->cPhNo);

	return newborn;
}


void fnFreeNode(NODEPTR x)
{
	free(x);
}


NODEPTR fnInsRear(NODEPTR first)
{
	NODEPTR temp,cur;

	temp = fnGetNode();

	temp->plink = temp->nlink = NULL;

    if(first == NULL)
        return temp;
    cur = first;
    while(cur->nlink != NULL)
    {
        cur = cur->nlink;
    }
    cur->nlink = temp;
    temp->plink = cur;
    return first;
}

NODEPTR fnInsFront(NODEPTR first)
{
    NODEPTR temp;

	temp = fnGetNode();
    temp->plink = temp->nlink = NULL;

    temp->nlink = first;
    first = temp;
    return first;

}

NODEPTR fnDelRear(NODEPTR first)
{
	NODEPTR cur, prev;
	if(first == NULL)
	{
		printf("nDLL is emptyn");
		return first;
	}

	cur = first;
	if(cur->nlink == NULL)
	{
        printf("nNode deleted for %sn",cur->cName);
        fnFreeNode(cur);
        return NULL;
	}
    while(cur->nlink != NULL)
    {
        cur = cur->nlink;
    }

    prev = cur->plink;
    prev->nlink = NULL;
	printf("nNode deleted for %sn",cur->cName);
	fnFreeNode(cur);
	return first;
}

NODEPTR fnDelFront(NODEPTR first)
{
	NODEPTR temp;
	if(first == NULL)
	{
		printf("nDLL is emptyn");
		return first;
	}
	if(first->nlink == NULL)
	{
		printf("nNode deleted for %sn",first->cName);
		fnFreeNode(first);
		return NULL;
	}
	temp = first;
	first = first->nlink;
	first->plink = NULL;
	printf("nNode deleted for %sn",temp->cName);
	fnFreeNode(temp);
	return first;
}

void fnDisplay(NODEPTR first)
{
	NODEPTR curr;
	int count = 0;
	if(first == NULL)
	{
		printf("nDLL is emptyn");
		return;
	}

	printf("nThe contents of DLL are :n");
	curr = first;
//	printf("n");
    printf("nSSNtNametDepttDesignationtSalaryttPhone No");
	while(curr != NULL)
	{
		printf("n%-5dt%st%st%stt%-7dtt%-11s",curr->iSSN, curr->cName, curr->cDept, curr->cDesignation, curr->iSalary, curr->cPhNo);
		curr = curr->nlink;
		count++;
	}
	printf("nnDLL has %d nodesn", count);

}

/*CPP*/

Output

putta:~/.../Programs$ gcc -Wall 08_DLL.c 
putta:~/.../Programs$ ./a.out 

Enter the number of Employees N : 2

Enter Data for Node 1 :

Enter SSN : 1234

Enter name : Raju

Enter Department : CSE

Enter Designation : Clerk

Enter Salary : 34000

Enter Phone no : 8798987523

Enter Data for Node 2 :

Enter SSN : 1235

Enter name : Stan

Enter Department : PWD

Enter Designation : Driver

Enter Salary : 29000

Enter Phone no : 8232489410

DLL OPERATIONS
====================
1.Insert Rear
2.Delete Front
3.Insert Front
4.Delete Rear
5.Display
6.Exit

Enter your choice
5

The contents of DLL are :

SSN	Name	Dept	Designation	Salary		Phone No
1234 	Raju	CSE	Clerk		34000  		8798987523 
1235 	Stan	PWD	Driver		29000  		8232489410 

DLL has 2 nodes

DLL OPERATIONS
====================
1.Insert Rear
2.Delete Front
3.Insert Front
4.Delete Rear
5.Display
6.Exit

Enter your choice
1

Enter SSN : 1236

Enter name : Tara

Enter Department : EEE

Enter Designation : Peon

Enter Salary : 20000

Enter Phone no : 8397338933

DLL OPERATIONS
====================
1.Insert Rear
2.Delete Front
3.Insert Front
4.Delete Rear
5.Display
6.Exit

Enter your choice
3

Enter SSN : 1233

Enter name : Babu

Enter Department : RLW

Enter Designation : Manager

Enter Salary : 45000

Enter Phone no : 9956726282

DLL OPERATIONS
====================
1.Insert Rear
2.Delete Front
3.Insert Front
4.Delete Rear
5.Display
6.Exit

Enter your choice
5

The contents of DLL are :

SSN	Name	Dept	Designation	Salary		Phone No
1233 	Babu	RLW	Manager		  45000  		9956726282 
1234 	Raju	CSE	Clerk		    34000  		8798987523 
1235 	Stan	PWD	Driver		  29000  		8232489410 
1236 	Tara	EEE	Peon		    20000  		8397338933 

DLL has 4 nodes

DLL OPERATIONS
====================
1.Insert Rear
2.Delete Front
3.Insert Front
4.Delete Rear
5.Display
6.Exit

Enter your choice
4

Node deleted for Tara

DLL OPERATIONS
====================
1.Insert Rear
2.Delete Front
3.Insert Front
4.Delete Rear
5.Display
6.Exit

Enter your choice
5

The contents of DLL are :

SSN	Name	Dept	Designation	Salary		Phone No
1233 	Babu	RLW	Manager		  45000  		9956726282 
1234 	Raju	CSE	Clerk		    34000  		8798987523 
1235 	Stan	PWD	Driver		  29000  		8232489410 

DLL has 3 nodes

DLL OPERATIONS
====================
1.Insert Rear
2.Delete Front
3.Insert Front
4.Delete Rear
5.Display
6.Exit

Enter your choice
4

Node deleted for Stan

DLL OPERATIONS
====================
1.Insert Rear
2.Delete Front
3.Insert Front
4.Delete Rear
5.Display
6.Exit

Enter your choice
2

Node deleted for Babu

DLL OPERATIONS
====================
1.Insert Rear
2.Delete Front
3.Insert Front
4.Delete Rear
5.Display
6.Exit

Enter your choice
5

The contents of DLL are :

SSN	Name	Dept	Designation	Salary		Phone No
1234 	Raju	CSE	Clerk		    34000  		8798987523 

DLL has 1 nodes

DLL OPERATIONS
====================
1.Insert Rear
2.Delete Front
3.Insert Front
4.Delete Rear
5.Display
6.Exit

Enter your choice
2

Node deleted for Raju

DLL OPERATIONS
====================
1.Insert Rear
2.Delete Front
3.Insert Front
4.Delete Rear
5.Display
6.Exit

Enter your choice
2

DLL is empty

DLL OPERATIONS
====================
1.Insert Rear
2.Delete Front
3.Insert Front
4.Delete Rear
5.Display
6.Exit

Enter your choice
5

DLL is empty

DLL OPERATIONS
====================
1.Insert Rear
2.Delete Front
3.Insert Front
4.Delete Rear
5.Display
6.Exit

Enter your choice
6

Program 09 : Polynomial Evaluation and Addition

Develop a Program in C for the following operationson Singly Circular Linked List (SCLL)
with header nodes
a. Represent and Evaluate a Polynomial P(x,y,z) = 6x2y2z-4yz5+3x3yz+2xy5z-2xyz3
b. Find the sum of two polynomials POLY1(x,y,z) and POLY2(x,y,z) and store the result in POLYSUM(x,y,z)
Support the program with appropriate functions for each of the above operations

C Code

/***************************************************************************
*File		: 09_Polynomial.c
*Description: Addition and Evaluation of Polynomials
*Author		: Prabodh C P
*Compiler	: gcc compiler, Ubuntu 22.04
*Date		: 28 September 2023
***************************************************************************/

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

// Node structure for a term in the polynomial
struct PolyTerm{
    int coefficient;
    int pow_x;
    int pow_y;
    int pow_z;
    struct PolyTerm* next;
};

typedef struct PolyTerm* POLYPTR;

POLYPTR fnInsertTerm(POLYPTR poly, int coef, int pow_x, int pow_y, int pow_z)
{
	POLYPTR cur;
    POLYPTR newNode = (POLYPTR)malloc(sizeof(struct PolyTerm));
    newNode->coefficient = coef;
    newNode->pow_x = pow_x;
    newNode->pow_y = pow_y;
    newNode->pow_z = pow_z;
    newNode->next = NULL;

    cur = poly;
    while(cur->next != poly)
    {
    	cur = cur->next;
    }
	cur->next = newNode;
	newNode->next = poly;
	return poly;
}

void fnDispPolynomial(POLYPTR poly)
{
    if (poly->next == poly)
    {
        printf("Polynomial is empty.n");
        return;
    }

    POLYPTR cur = poly->next;
    do
    {
        printf("%dx^%dy^%dz^%d ", cur->coefficient, cur->pow_x, cur->pow_y, cur->pow_z);
        cur = cur->next;
        if (cur != poly)
        {
            printf("+ ");
        }
    } while (cur != poly);
    printf("n");
}


int fnEvaluatePolynomial(POLYPTR poly, int x, int y, int z)
{
    int result = 0;
    if (poly->next == poly)
    {
        return result;
    }

    POLYPTR cur = poly->next;
    do
    {
        int termValue = cur->coefficient;
        termValue *= pow(x, cur->pow_x);
        termValue *= pow(y, cur->pow_y);
        termValue *= pow(z, cur->pow_z);

        result += termValue;

        cur = cur->next;
    } while (cur != poly);

    return result;
}

bool fnMatchTerm(POLYPTR p1, POLYPTR p2)
{
	bool bMatches = true;
	if(p1->pow_x != p2->pow_x)
		bMatches = false;
	if(p1->pow_y != p2->pow_y)
		bMatches = false;
	if(p1->pow_z != p2->pow_z)
		bMatches = false;
	return bMatches;
}

POLYPTR fnAddPolynomials(POLYPTR poly1, POLYPTR poly2, POLYPTR polySum)
{
    POLYPTR cur1 = poly1->next;
    POLYPTR cur2 = poly2->next;

    do
    {
    	polySum = fnInsertTerm(polySum, cur1->coefficient, cur1->pow_x, cur1->pow_y, cur1->pow_z);
    	cur1 = cur1->next;
    }while(cur1 != poly1);

    do
    {
        cur1 = polySum->next;
        bool bMatchFound = false;
        do
        {
            if(fnMatchTerm(cur1, cur2))
            {
                cur1->coefficient += cur2->coefficient;
                bMatchFound = true;
                break;
            }
            cur1 = cur1->next;

        }while(cur1 != polySum);
        if(!bMatchFound)
        {
            polySum = fnInsertTerm(polySum, cur2->coefficient, cur2->pow_x, cur2->pow_y, cur2->pow_z);
        }

        cur2 = cur2->next;

    }while(cur2 != poly2);

    return polySum;

}

int main()
{
    POLYPTR poly1 = (POLYPTR)malloc(sizeof(struct PolyTerm));
    poly1->next = poly1;
    POLYPTR poly2 = (POLYPTR)malloc(sizeof(struct PolyTerm));
    poly2->next = poly2;
    POLYPTR polySum = (POLYPTR)malloc(sizeof(struct PolyTerm));
    polySum->next = polySum;

    // Represent and evaluate the polynomial P(x, y, z) = 6x^2y^2z - 4yz^5 + 3x^3yz + 2xy^5z - 2xyz^3
    poly1 = fnInsertTerm(poly1, 6, 2, 2, 1);
    poly1 = fnInsertTerm(poly1, 4, 0, 1, 5);
    poly1 = fnInsertTerm(poly1, 3, 3, 1, 1);
    poly1 = fnInsertTerm(poly1, 2, 1, 5, 1);
    poly1 = fnInsertTerm(poly1, 2, 1, 1, 3);

    // Display the polynomial P(x, y, z)
    printf("POLY1(x, y, z) = ");
    fnDispPolynomial(poly1);

    // Read and evaluate the second polynomial POLY2(x, y, z)
    // Represent the polynomial P(x, y, z) = xyz + 4x^3yz
    poly2 = fnInsertTerm(poly2, 1, 1, 1, 1);  // Example term
    poly2 = fnInsertTerm(poly2, 4, 3, 1, 1);


    // Display the second polynomial POLY2(x, y, z)
    printf("POLY2(x, y, z) = ");
    fnDispPolynomial(poly2);

    // Add POLY1(x, y, z) and POLY2(x, y, z) and store the result in POLYSUM(x, y, z)
    polySum = fnAddPolynomials(poly1, poly2, polySum);

    // Display the sum POLYSUM(x, y, z)
    printf("nPOLYSUM(x, y, z) = ");
    fnDispPolynomial(polySum);

    // Evaluate POLYSUM(x, y, z) for specific values
    int x = 1, y = 2, z = 3;
    int iRes = fnEvaluatePolynomial(polySum, x, y, z);
    printf("nResult of POLYSUM(%d, %d, %d): %dn", x, y, z, iRes);

    return 0;
}

Output

putta:~/.../Programs$ gcc -Wall 09_Polynomial.c -lm
putta:~/.../Programs$ ./a.out 

POLY1(x, y, z) = 6x^2y^2z^1 + 4x^0y^1z^5 + 3x^3y^1z^1 + 2x^1y^5z^1 + 2x^1y^1z^3 
POLY2(x, y, z) = 1x^1y^1z^1 + 4x^3y^1z^1 

POLYSUM(x, y, z) = 6x^2y^2z^1 + 4x^0y^1z^5 + 7x^3y^1z^1 + 2x^1y^5z^1 + 2x^1y^1z^3 + 1x^1y^1z^1 

Result of POLYSUM(1, 2, 3): 2364

Program 10 : Binary Search Tree

Develop a menu driven Program in C for the following operations on Binary Search Tree (BST) of Integers .
a. Create a BST of N Integers: 6, 9, 5, 2, 8, 15, 24, 14, 7, 8, 5, 2
b. Traverse the BST in Inorder, Preorder and Post Order
c. Search the BST for a given element (KEY) and report the appropriate message
d. Exit

C Code

/***************************************************************************
*File		: 10_BST.c
*Description: Binary Search Tree Operations
*Author		: Prabodh C P
*Compiler	: gcc compiler, Ubuntu 22.04
*Date		: 28 September 2023
***************************************************************************/

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

struct node
{
	int info;
	struct node *lbranch;
	struct node *rbranch;
};
typedef struct node* NODEPTR;

/* FUNCTION PROTOTYPES */
NODEPTR fnGetNode(void);
void fnFreeNode(NODEPTR x);
NODEPTR fnInsertNode(int, NODEPTR);
void fnInOrder(NODEPTR);
void fnPreOrder(NODEPTR);
void fnPostOrder(NODEPTR);
void fnSearchBST(NODEPTR, int);

int main()
{
	NODEPTR root = NULL;
	int iChoice, iItem, i, iNum;

    printf("Create a BST of N Integers n");
    printf("nEnter the number N : ");
    scanf("%d", &iNum);
    printf("nEnter %d numbersn", iNum);
    for(i=0;i<iNum;i++)
    {
        scanf("%d", &iItem);
        root = fnInsertNode(iItem,root);
    }

	for(;;)
	{
		printf("n1.Inorder traversaln2.Preorder traversal");
		printf("n3.Postorder traversaln4.Searchn5.Exitn");
		printf("nEnter your choice : ");
		scanf("%d",&iChoice);

		switch(iChoice)
		{
			case 1: if(root ==NULL)
					{
						printf("nTree is Emptyn");
					}
					else
					{
						printf("nInorder Traversal is :n");
						fnInOrder(root);
						printf("n");
					}
					break;

			case 2: if(root ==NULL)
					{
						printf("nTree is Emptyn");
					}
					else
					{
						printf("nPreorder Traversal is :n");
						fnPreOrder(root);
						printf("n");
					}
					break;

			case 3: if(root ==NULL)
					{
						printf("nTree is Emptyn");
					}
					else
					{
						printf("nPostorder Traversal is :n");
						fnPostOrder(root);
						printf("n");
					}
					break;

			case 4: printf("nEnter the element to be searched : ");
					scanf("%d", &iItem);
					fnSearchBST(root, iItem);
					break;
					
			case 5: exit(0);

			default: printf("Wrong choicen");
					 break;

		}

	}
	return 0;
}

NODEPTR fnGetNode(void)
{
	NODEPTR x;
	x = ( NODEPTR ) malloc (sizeof(struct node));
	if(x == NULL)
	{
		printf("nOut of Memory");
		exit(0);
	}
	return x;
}

void fnFreeNode(NODEPTR x)
{
	free(x);
}

NODEPTR fnInsertNode(int iItem,NODEPTR root)
{
	NODEPTR temp,prev,cur;

	temp = fnGetNode();
	temp->info = iItem;
	temp->lbranch = NULL;
	temp->rbranch = NULL;

	if(root == NULL)
	return temp;

	prev = NULL;
	cur = root;

	while(cur != NULL)
	{
		prev = cur;

		if(iItem == cur->info)
		{
			printf("nDuplicate items not allowedn");
			fnFreeNode(temp);
			return root;
		}

		cur = (iItem < cur->info)? cur->lbranch: cur->rbranch;
	}

	if(iItem < prev->info)
		prev->lbranch = temp;
	else
		prev->rbranch = temp;

	return root;

}

void fnPreOrder(NODEPTR root)
{
	if(root != NULL)
	{
		printf("%dt",root->info);
		fnPreOrder(root->lbranch);
		fnPreOrder(root->rbranch);
	}
}

void fnInOrder(NODEPTR root)
{
	if(root != NULL)
	{
		fnInOrder(root->lbranch);
		printf("%dt",root->info);
		fnInOrder(root->rbranch);
	}
}

void fnPostOrder(NODEPTR root)
{
	if(root != NULL)
	{
		fnPostOrder(root->lbranch);
		fnPostOrder(root->rbranch);
		printf("%dt",root->info);
	}
}

void fnSearchBST(NODEPTR root, int iElem)
{
	if(root != NULL)
	{
		if(iElem < root->info)
			fnSearchBST(root->lbranch, iElem);
		else if(iElem > root->info)
			fnSearchBST(root->rbranch, iElem);
		else
			printf("n%d is found in the BSTn",iElem);
	}
	else
	{
		printf("n%d is not found in the BSTn",iElem);
	}
}

Output

putta:~/.../Programs$ gcc -Wall 10_BST.c 
putta:~/.../Programs$ ./a.out 
Create a BST of N Integers 

Enter the number N : 6

Enter 6 numbers
50
30
70
40
60
20

1.Inorder traversal
2.Preorder traversal
3.Postorder traversal
4.Search
5.Exit

Enter your choice : 1

Inorder Traversal is :
20	30	40	50	60	70	

1.Inorder traversal
2.Preorder traversal
3.Postorder traversal
4.Search
5.Exit

Enter your choice : 2

Preorder Traversal is :
50	30	20	40	70	60	

1.Inorder traversal
2.Preorder traversal
3.Postorder traversal
4.Search
5.Exit

Enter your choice : 3

Postorder Traversal is :
20	40	30	60	70	50	

1.Inorder traversal
2.Preorder traversal
3.Postorder traversal
4.Search
5.Exit

Enter your choice : 4

Enter the element to be searched : 30

30 is found in the BST

1.Inorder traversal
2.Preorder traversal
3.Postorder traversal
4.Search
5.Exit

Enter your choice : 4

Enter the element to be searched : 80

80 is not found in the BST

1.Inorder traversal
2.Preorder traversal
3.Postorder traversal
4.Search
5.Exit

Enter your choice : 5

Program 11 : Graph Reachability using DFS/BFS

Develop a Program in C for the following operations on Graph(G) of Cities
a. Create a Graph of N cities using Adjacency Matrix.
b. Print all the nodes reachable from a given starting node in a digraph using DFS/BFS method

C Code (BFS method)

/***************************************************************************
*File		: 11_GraphBFS.c
*Description: Program to find all nodes reachable from a given node using BFS
*Author		: Prabodh C P
*Compiler	: gcc compiler, Ubuntu 22.04
*Date		: 28 September 2023
***************************************************************************/

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

const int MAX = 100;
const int SIZE = 10;
void fnBreadthFirstSearchReach(int vertex, int g[MAX][MAX], int v[MAX], int n);

typedef struct
{
	int iaItems[10];
	int iFront;
	int iRear;
}QUEUE;

void fnQInsert(QUEUE *stQueue, int elem);
int fnQDelete(QUEUE *stQueue);
int fnQFull(QUEUE *stQueue);
int fnQEmpty(QUEUE *stQueue);

/******************************************************************************
*Function	: main
*Input parameters: no parameters
*RETURNS	: 0 on success
******************************************************************************/
int main(void)
{
	int graph[MAX][MAX];
	int visited[MAX];
	int numVert, startVert, i,j;

	printf("Enter the number of vertices : ");
	scanf("%d", &numVert);
	printf("Enter the adjacency matrix :\n");
	for (i=0; i<numVert; i++)
		visited[i] = 0;
	for (i=0; i<numVert; i++)
		for (j=0; j<numVert; j++)
			scanf("%d", &graph[i][j]);
	printf("Enter the starting vertex : ");
	scanf("%d", &startVert);
	fnBreadthFirstSearchReach(startVert-1,graph,visited,numVert);
	printf("Vertices which can be reached from vertex %d are :-\n",startVert);
	for (i=0; i<numVert; i++)
		if (visited[i])
			printf("%d ",i+1);
	printf("\n");
	return 0;
}

/******************************************************************************
*Function	: fnBreadthFirstSearchReach
*Description	: Function to perform BFS traversal and mark visited vertices
*Input parameters:
*	int vertex - source vertex
*	int g[][]	- adjacency matrix of the graph
*	int v[]	- vector to store visited information
*	int n	- no of vertices
*RETURNS	: void
******************************************************************************/
void fnBreadthFirstSearchReach(int vertex, int g[MAX][MAX], int v[MAX], int n)
{
	QUEUE stQueue;
	stQueue.iFront = 0;
	stQueue.iRear = -1;
	int frontVertex, i;
	v[vertex] = 1;
	fnQInsert(&stQueue, vertex);
	while (!fnQEmpty(&stQueue))
	{
		frontVertex = fnQDelete(&stQueue);
		for (i=0; i<n; i++)
		{
			if (g[frontVertex][i] && !v[i])
			{
				v[i] = 1;
				fnQInsert(&stQueue, i);
			}
		}
	}
}

/***************************************************************************
*Function	: 	fnQInsert
*Description:   inserts an element at the rear of the queue
*Input parameters: a structure queue
*RETURNS	:	updated queue
***************************************************************************/

void fnQInsert(QUEUE *stQueue, int iItem)
{
	if(fnQFull(stQueue))
		printf("\nQueue Overflow\n");
	else
	{
		stQueue->iRear++;
		stQueue->iaItems[stQueue->iRear] = iItem;
	}
}

/***************************************************************************
*Function	: 	fnQDelete
*Description:   deletes an element from the front of the queue
*Input parameters: a structure queue
*RETURNS	:	updated queue
***************************************************************************/

int fnQDelete(QUEUE *stQueue)
{
	int item;
	if(fnQEmpty(stQueue))
	printf("\nQueue Underflow\n");
	else
	if(stQueue->iRear == stQueue->iFront)
	{
		item = stQueue->iaItems[stQueue->iFront];
		stQueue->iRear=-1;
		stQueue->iFront=0;
	}
	else
	{
		item = stQueue->iaItems[stQueue->iFront++];
	}
	return item;
}

/***************************************************************************
*Function	: 	fnQFull
*Description:   checks wheteher the queue is full or not
*Input parameters: a structure queue
*RETURNS	:	1 if the queue is full or 0 otherwise
***************************************************************************/
int fnQFull(QUEUE *stQueue)
{
	if(stQueue->iRear == SIZE-1)
		return 1;
	else
		return 0;
}

/***************************************************************************
*Function	: 	fnQEmpty
*Description:   checks wheteher the queue is empty or not
*Input parameters: a structure queue
*RETURNS	:	1 if the queue is empty or 0 otherwise
***************************************************************************/
int fnQEmpty(QUEUE *stQueue)
{
	if(stQueue->iRear == stQueue->iFront-1)
		return 1;
	else
		return 0;
}

Output

putta:~/.../Programs$ gcc -Wall 11_GraphBFS.c 

putta:~/.../Programs$ ./a.out 
Enter the number of vertices : 4
Enter the adjacency matrix :
0 1 0 0
1 0 0 0
0 0 0 1
0 0 1 0
Enter the starting vertex : 1
Vertices which can be reached from vertex 1 are :-
1 2 

putta:~/.../Programs$ ./a.out 
Enter the number of vertices : 4
Enter the adjacency matrix :
0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0
Enter the starting vertex : 1
Vertices which can be reached from vertex 1 are :-
1 2 3 4 

putta:~/.../Programs$ ./a.out 
Enter the number of vertices : 4
Enter the adjacency matrix :
0 1 0 0
1 0 0 0
0 0 0 1
0 0 1 0
Enter the starting vertex : 3
Vertices which can be reached from vertex 3 are :-
3 4 

C Code (DFS method)

/***************************************************************************
*File		: 11_GraphDFS.c
*Description: Program to find all nodes reachable from a given node using DFS 
*Author		: Prabodh C P
*Compiler	: gcc compiler, Ubuntu 22.04
*Date		: 28 September 2023
***************************************************************************/

#include <stdio.h>
const int MAX = 100;
void fnDepthFirstSearch(int currentVertex, int v[MAX], int g[MAX][MAX], int n);
/******************************************************************************
*Function:	 main
*Input parameters: no parameters
*RETURNS:	0 on success
******************************************************************************/
int main(void)
{
	int i,j,k;
	int visited[MAX];
	int graph[MAX][MAX];
	int numVert, Vert;
	printf("Enter the number of vertices : ");
	scanf("%d", &numVert);
	for (i=0; i<numVert; i++)
		visited[i] = 0;
	printf("Enter the adjacency matrix :n");
	for (i=0; i<numVert; i++)
		for (j=0; j<numVert; j++)
			scanf("%d", &graph[i][j]);
	printf("Enter the source vertex : ");
	scanf("%d", &Vert);
	fnDepthFirstSearch(Vert,visited,graph,numVert);
	for (k=0; k<numVert; k++)
	{
		if(visited[k])
		{
			printf("nVertex %d is reachablen", k+1);
		}
		else
		{
			printf("nVertex %d is not reachablen", k+1);
		}
	}

	return 0;
}
/******************************************************************************
*Function:	 fnDepthFirstSearch
*Description:	 Function to perform DFS traversal and mark visited vertices
*Input parameters:
*	int currentVertex - source vertex
*	int v[] - vector to store visited information
*	int g[][] - adjacency matrix of the graph
*	int n - no of vertices
*RETURNS:	 void
******************************************************************************/
void fnDepthFirstSearch(int currentVertex, int v[MAX], int g[MAX][MAX], int n)
{
	int i;
	v[currentVertex] = 1;
	for (i=0; i<n; i++)
	{
		if (g[currentVertex][i] && !v[i])
			fnDepthFirstSearch(i,v,g,n);
	}
}

Output

putta:~/.../Programs$ gcc -Wall 11_GraphDFS.c 
putta:~/.../Programs$ ./a.out 
Enter the number of vertices : 4
Enter the adjacency matrix :
0 1 0 0
1 0 0 0
0 0 0 1
0 0 1 0
Enter the source vertex : 3

Vertex 1 is not reachable

Vertex 2 is not reachable

Vertex 3 is reachable

Vertex 4 is reachable

putta:~/.../Programs$ ./a.out 
Enter the number of vertices : 4
Enter the adjacency matrix :
0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0
Enter the source vertex : 1

Vertex 1 is reachable

Vertex 2 is reachable

Vertex 3 is reachable

Vertex 4 is reachable

putta:~/.../Programs$ ./a.out 
Enter the number of vertices : 4
Enter the adjacency matrix :
0 1 0 0
1 0 0 0
0 0 0 1
0 0 1 0
Enter the source vertex : 1

Vertex 1 is reachable

Vertex 2 is reachable

Vertex 3 is not reachable

Vertex 4 is not reachable

Program 12 : Hashing & Linear Probing

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. 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.

C Code

/***************************************************************************
*File		: 12_HashCollision.c
*Description: Hashing with Linear Probing
*Author		: Prabodh C P
*Compiler	: gcc compiler, Ubuntu 22.04
*Date		: 28 September 2023
***************************************************************************/

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

#define MAX_NUM_EMPLOYEES 100  // Maximum number of employees
#define MAX_HASH_TABLE_SIZE 50  // Maximum size of the hash table

// Define the structure for an employee record
typedef struct 
{
    int iKey;  // 4-digit key
    char cName[50]; 
}EMPLOYEE;

// Define the hash table as an array of employee pointers
EMPLOYEE* stHashTable[MAX_HASH_TABLE_SIZE];

int fnCompHash(int, int);
void fnInsRecord(EMPLOYEE*, int);
EMPLOYEE* fnSrchRecord(int, int);

int main()
{
    int m;  // Size of the hash table
    printf("Enter the size of the hash table (m): ");
    scanf("%d", &m);

    // Initialize the hash table with NULL pointers
    for (int i = 0; i < m; i++)
	{
        stHashTable[i] = NULL;
    }

    FILE* file = fopen("employee.txt", "r");
    if(file == NULL)
	{
        printf("Error opening file.n");
        return 1;
    }

    int n = 0;  
    EMPLOYEE emp;
    while(fscanf(file, "%d %s", &emp.iKey, emp.cName) != EOF)
	{
        EMPLOYEE* newEmp = (EMPLOYEE*)malloc(sizeof(EMPLOYEE));
        newEmp->iKey = emp.iKey;
        strcpy(newEmp->cName, emp.cName);
        fnInsRecord(newEmp, m);
        n++;
    }

    fclose(file);

    int iSrchKey;
    printf("Enter a key to search for an employee record: ");
    scanf("%d", &iSrchKey);

    EMPLOYEE* found = fnSrchRecord(iSrchKey, m);
    if(found != NULL)
	{
        printf("Employee found with key %d:n", found->iKey);
        printf("Name: %sn", found->cName);
    }
    else
	{
        printf("Employee with key %d not found.n", iSrchKey);
    }

    return 0;
}

void fnInsRecord(EMPLOYEE* emp, int m)
{
    int index = fnCompHash(emp->iKey, m);

    // Linear probing if collisions happen
    while(stHashTable[index] != NULL)
	{
        index = (index + 1) % m;
    }

    stHashTable[index] = emp;
}

int fnCompHash(int iKey, int m)
{
    return iKey % m;
}

EMPLOYEE* fnSrchRecord(int iKey, int m)
{
    int index = fnCompHash(iKey, m);

    // Linear probing
    while(stHashTable[index] != NULL)
	{
        if(stHashTable[index]->iKey == iKey)
		{
            return stHashTable[index];
        }
        index = (index + 1) % m;
    }
    return NULL; // Employee record not found
}

Download the employee.dat file used in the program here

Output

putta:~/.../Programs$ gcc -Wall 12_HashCollision.c 

putta:~/.../Programs$ ./a.out 
Enter the size of the hash table (m): 50
Enter a key to search for an employee record: 5216
Employee found with key 5216:
Name: sanjay

putta:~/.../Programs$ ./a.out 
Enter the size of the hash table (m): 50
Enter a key to search for an employee record: 4327
Employee found with key 4327:
Name: nahar

Prabodh C P is a faculty in the Dept of CSE SIT, Tumkur and also currently a Research Scholar pursuing PhD in IIT Hyderabad. He conducts online classes for C, C++, Python. For more info call +919392302100

Leave a Reply

Your email address will not be published. Required fields are marked *