Data Structures Laboratory BCSL305

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

CODE:1(a)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Define the structure for a calendar day

struct CalendarDay {
char* dayName; // Dynamically allocated string for day name
int date; // Date as an integer
char* activity; // Dynamically allocated string for activity description
};

int main() {
// Declare an array of 7 calendar days
struct CalendarDay calendar[7];

// Initialize each day

for (int i = 0; i < 7; i++) {
// Allocate memory for dayName and activity
calendar[i].dayName = (char*)malloc(20 * sizeof(char)); // Assuming day names are no
longer than 19 characters
calendar[i].activity = (char*)malloc(100 * sizeof(char)); // Assuming activity descriptions
are no longer than 99 characters

// Set values for each field

strcpy(calendar[i].dayName, "Day Name"); // You should replace this with the actual day
calendar[i].date = i + 1; // You can set the date accordingly
strcpy(calendar[i].activity, "Activity Description"); // You should replace this with the
actual activity description
}

// Access and print the calendar

for (int i = 0; i < 7; i++) {
printf("Day %d: %s, Date: %d, Activity: %s\n", i + 1, calendar[i].dayName,
calendar[i].date, calendar[i].activity);

Dept of CSE DSTAM 1

Data Structures Laboratory BCSL305

// Free dynamically allocated memory

for (int i = 0; i < 7; i++) {
free(calendar[i].dayName);
free(calendar[i].activity);
}

return 0;
}

CODE:1(b)

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

// Define the structure for a calendar day

struct CalendarDay {
char* dayName; // Dynamically allocated string for day name
int date; // Date as an integer
char* activity; // Dynamically allocated string for activity description
};

// Function to create the calendar

void create(struct CalendarDay calendar[7]) {
for (int i = 0; i < 7; i++) {
calendar[i].dayName = (char*)malloc(20 * sizeof(char)); // Assuming day names are no
longer than 19 characters
calendar[i].activity = (char*)malloc(100 * sizeof(char)); // Assuming activity descriptions
are no longer than 99 characters
}
}

// Function to read data from the keyboard

void read(struct CalendarDay calendar[7]) {
for (int i = 0; i < 7; i++) {
printf("Enter the day name for Day %d: ", i + 1);
scanf("%s", calendar[i].dayName);

printf("Enter the date for Day %d: ", i + 1);

scanf("%d", &calendar[i].date);

printf("Enter the activity description for Day %d: ", i + 1);

Dept of CSE DSTAM 2

Data Structures Laboratory BCSL305

scanf(" %99[^\n]", calendar[i].activity); // Read up to 99 characters for the activity

description
}
}

// Function to display the weekly activity details

void display(struct CalendarDay calendar[7]) {
printf("\nWeekly Activity Details:\n");
for (int i = 0; i < 7; i++) {
printf("Day %d: %s, Date: %d, Activity: %s\n", i + 1, calendar[i].dayName,
calendar[i].date, calendar[i].activity);
}
}

int main() {
struct CalendarDay calendar[7];

create(calendar); // Create the calendar

read(calendar); // Read data from the keyboard
display(calendar); // Display the weekly activity details

// Free dynamically allocated memory

for (int i = 0; i < 7; i++) {
free(calendar[i].dayName);
free(calendar[i].activity);
}

return 0;
}

Dept of CSE DSTAM 3

Data Structures Laboratory BCSL305

Program - 02

Design, Develop and Implement 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. Repost 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.

ABOUT THE EXPERIMENT:

Strings are actually one-dimensional array of characters terminated by a null character '\0'. Thus
a null-terminated string contains the characters that comprCSE the string followed by a null.

The following declaration and initialization create a string consisting of the word "Hello". To
hold the null character at the end of the array, the size of the character array containing the string
is one more than the number of characters in the word "Hello."

char greeting[6] = {'H', 'e', 'l', 'l', 'o', '\0'};

If you follow the rule of array initialization then you can write the above statement as follows:

char greeting[] = "Hello";

C language supports a wide range of built-in functions that manipulate null-terminated strings as
follows:

strcpy(s1, s2); Copies string s2 into string s1.

strcat(s1, s2); Concatenates string s2 onto the end of string s1.
strlen(s1); Returns the length of string s1.
strcmp(s1, s2); Returns 0 if s1 and s2 are the same; less than 0 if s1<s2; greater than 0 if s1>s2.
strchr(s1, ch); Returns a pointer to the first occurrence of character ch in string s1.
strstr(s1, s2); Returns a pointer to the first occurrence of string s2 in string s1.

ALGORITHM:
Step 1: Start.

Step 2: Read main string STR, pattern string PAT and replace stringREP.

Dept of CSE DSTAM 4

Data Structures Laboratory BCSL305

Step 3: Search / find the pattern string PAT in the main string STR.

Step 4: if PAT is found then replace all occurrences of PAT in main string STR with REP string.
Step 5: if PAT is not found give a suitable error message.

Step 6: Stop.

PROGRAM CODE:

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

//Declarations

char str[100], pat[50], rep[50], ans[100]; int i, j, c, m, k, flag=0;

void stringmatch()
{
i = m = c = j = 0;
while(str[c] ! = '\0')
{
if(str[m] = = pat[i])
{
i++;
m++;

if(pat[i] = = '\0')
{
flag = 1;
for(k = 0; rep[k] != '\0'; k++, j++)
ans[j] = rep[k];
i = 0;
c = m;
}
}
else
{
ans[j] = str[c]; j++;
c++;
m = c;
i = 0;
}
}
ans[j] = '\0';
}

Dept of CSE DSTAM 5

Data Structures Laboratory BCSL305

void main()
{
clrscr();

printf("\nEnter a main string \n");

gets(str);

printf("\nEnter a pattern string \n");

flushall();

gets(pat);

printf("\nEnter a replace string \n");

flushall();

gets(rep);

stringmatch();
if(flag = = 1)
printf("\nThe resultant string is\n %s" , ans);
else
printf("\nPattern string NOT found\n"); getch();

}// end of main

SAMPLE OUTPUT:

RUN 1:
Enter a main string

Test
Enter a pattern string
Te
Enter a replace string
Re

The resultant string is

Rest

RUN 2:
Enter a main string

This is Data Structure lab

Dept of CSE DSTAM 6

Data Structures Laboratory BCSL305

Enter a pattern string

Data Structure
Enter a replace string
Data structure with C

The resultant string is

This is Data structure with C lab

RUN 3:
Enter a main string

This is Data Structure lab

Enter a pattern string
Date
Enter a replace string
DATA

Pattern string NOT found

Dept of CSE DSTAM 7

Data Structures Laboratory BCSL305

Program - 03

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 how stack can be used to check palindrome.
d. Demonstrate Overflow and Underflow situations on stack.
e. Display the status of stack.
f. Exit.
Support the program with appropriate functions for each of the above operations.

ABOUT THE EXPERIMENT:

A stack is an abstract data type (ADT), commonly used in most programming languages.
It is named stack as it behaves like a real-world stack, for example − deck of cards or pile of
plates etc.

A real-world stack allows operations at one end only. For example, we can place or
remove a card or plate from top of the stack only. LikewCSE, Stack ADT allows all data
operations at one end only. At any given time, we can only access the top element of a stack.
This feature makes it LIFO data structure. LIFO stands for Last-in-first-out. Here, the
element which is placed (inserted or added) last is accessed first. In stack terminology, insertion
operation is called PUSH operation and removal operation is called POP operation.

Below given diagram tries to depict a stack and its operations −

A stack can be implemented by means of Array, Structure, Pointer and Linked-List.

Stack can either be a fixed size one or it may have a sense of dynamic resizing. Here, we are
going to implement stack using arrays which makes it a fixed size stack implementation.
Basic Operations:
 push() - pushing (storing) an element on the stack.
 pop() - removing (accessing) an element from the stack.

Dept of CSE DSTAM 8

Data Structures Laboratory BCSL305

To use a stack efficiently we need to check status of stack as well. For the same purpose, the
following functionality is added to stacks;
 peek() − get the top data element of the stack, without removing it.
 isFull() − check if stack is full.
 CSEmpty() − check if stack is empty.

ALGORITHM:
Step 1: Start.
Step 2: Initialize stack size MAX and top of stack -1.
Step 3: Push integer element on to stack and display the contents of the stack.
if stack is full give a message as ‘Stack is Overflow’.
Step 3: Pop element from stack along with display the stack contents.
if stack is empty give a message as ‘Stack is Underflow’.
Step 4: Check whether the stack contents are Palindrome or not.
Step 5: Stop.

PROGRAM CODE:
#include<stdio.h>
#include<conio.h>
#define MAX 4
int stack[MAX], item;
int ch, top = -1, count = 0;

/*PUSH FUNCTION*/
void push( )
{
if (top == (MAX-1))
printf("\n\nStack is Overflow");
else
{
stack[++top] = item;

}
}

int pop( )
{
int ret;
if(top == -1)
printf("\n\nStack is Underflow");
else
{
ret = stack[top--];
printf("\nPopped element is %d", ret);

Dept of CSE DSTAM 9

Data Structures Laboratory BCSL305

}
return ret;
}

void palindrome( )
{
int i, j ;
int flag=1;
for(i=0, j=top;i<j;i++,j--)
{
if(stack[i] ==stack[j])
flag = 1;
else
{
flag =0;
break;
}
}
if(flag==1)
printf("\nStack contents are Palindrome");

else
printf("\nStack contents are not palindrome");
}

void display( )
{
int i;
printf("\nThe stack contents are:");
if(top == -1)
printf("\nStack is Empty");
else
{
for(i=top; i>=0; i--)
printf("\n ------\n| %d |", stack[i]);
printf("\n");
}
}

void main( )
{
clrscr();
do{
printf("\n\n----MAIN MENU----\n");
printf("\n1. PUSH (Insert) in the Stack");
printf("\n2. POP (Delete) from the Stack");

Dept of CSE DSTAM 10

Data Structures Laboratory BCSL305

printf("\n3. PALINDROME check using Stack");

printf("\n4. Exit (End the Execution)");
printf("\nEnter Your Choice: ");
scanf("%d", &ch);

switch(ch)
{
case 1: printf("\nEnter a element to be pushed: ");
scanf("%d", &item);
push( );
display( );
break;

case 2: temp=pop( );
display( );
break;
case 3:
palindrome( );
break;
case 4:
exit(0);
break;
default:
printf("\nEND OF EXECUTION");
}
}while (ch != 4);
getch();
}

SAMPLE OUTPUT:
----MAIN MENU----
1.PUSH (Insert) in the Stack
2.POP (Delete) from the Stack
3.PALINDROME check using Stack
4.Exit (End the Execution)

Enter Your Choice: 1

Enter an element to be pushed: 1
The stack contents are:
-----
|1|

----MAIN MENU----
1. PUSH (Insert) in the Stack
2. POP (Delete) from the Stack
3. PALINDROME check using Stack
4. Exit (End the Execution)

Dept of CSE DSTAM 11

Data Structures Laboratory BCSL305

Enter Your Choice: 1

Enter an element to be pushed: 2
The stack contents are:
2
1

----MAIN MENU----
1.PUSH (Insert) in the Stack
2.POP (Delete) from the Stack
3.PALINDROME check using Stack
4.Exit (End the Execution)

Enter Your Choice: 1

Enter an element to be pushed: 3
The stack contents are:
3
2
1

----MAIN MENU----
1.PUSH (Insert) in the Stack
2.POP (Delete) from the Stack
3.PALINDROME check using Stack
4.Exit (End the Execution)

Enter Your Choice: 1

Enter an element to be pushed: 4
The stack contents are:
4
3
2
1

----MAIN MENU----
1.PUSH (Insert) in the Stack
2.POP (Delete) from the Stack
3.PALINDROME check using Stack
4.Exit (End the Execution)

Enter Your Choice: 1

Enter an element to be pushed: 9
Stack is Overflow
The stack contents are:
4
3
2
1

Dept of CSE DSTAM 12

Data Structures Laboratory BCSL305

----MAIN MENU----
1.PUSH (Insert) in the Stack
2.POP (Delete) from the Stack
3.PALINDROME check using Stack
4.Exit (End the Execution)

Enter Your Choice: 2

The popped element is: 4
The stack contents are:
3
2
1

----MAIN MENU----
1.PUSH (Insert) in the Stack
2.POP (Delete) from the Stack
3.PALINDROME check using Stack
4.Exit (End the Execution)

Enter Your Choice:3

The stack contents are not palindrome.

----MAIN MENU----
1.PUSH (Insert) in the Stack
2.POP (Delete) from the Stack
3.PALINDROME check using Stack
4.Exit (End the Execution)

Enter Your Choice:2

The popped element is:3

The stack contents are:
2
1
----MAIN MENU----
1.PUSH (Insert) in the Stack
2.POP (Delete) from the Stack
3.PALINDROME check using Stack
4.Exit (End the Execution)

Enter Your Choice:1

Enter the element to be pushed:2

The stack contents are:

Dept of CSE DSTAM 13

Data Structures Laboratory BCSL305

2
2
1

MAIN MENU----
1.PUSH (Insert) in the Stack
2.POP (Delete) from the Stack
3.PALINDROME check using Stack
4.Exit (End the Execution)

Enter Your Choice:1

Enter the element to be pushed:1

The stack contents are:

1
2
2
1
1
MAIN MENU----
1.PUSH (Insert) in the Stack
2.POP (Delete) from the Stack
3.PALINDROME check using Stack
4.Exit (End the Execution)

Enter Your Choice:3

The stack contents are palindrome.

MAIN MENU----
1.PUSH (Insert) in the Stack
2.POP (Delete) from the Stack
3.PALINDROME check using Stack
4.Exit (End the Execution)

Enter Your Choice:4

Program - 04

Dept of CSE DSTAM 14

Data Structures Laboratory BCSL305

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.

ABOUT THE EXPERIMENT:

Infix: Operators are written in-between their operands. Ex: X + Y

Prefix: Operators are written before their operands. Ex: +X Y
Postfix: Operators are written after their operands. Ex: XY+

Infix to prefix conversion

Expression = (A+B^C)*D+E^5
Step 1. Reverse the infix expression.
5^E+D*)C^B+A(
Step 2. Make Every '(' as ')' and every ')' as '('
5^E+D*(C^B+A)
Step 3. Convert expression to postfix form.
Step 4. Reverse the expression.
+*+A^BCD^E
Step 5. Result
+*+A^BCD^E5

A+(B*C-(D/E-F)*G)*H

Expression Stack Output Comment

5^E+D*(C^B+A) Empty - Initial
^E+D*(C^B+A) Empty 5 Print
E+D*(C^B+A) ^ 5 Push
+D*(C^B+A) ^ 5E Push
D*(C^B+A) + 5E^ Pop And Push
*(C^B+A) + 5E^D Print
(C^B+A) +* 5E^D Push
C^B+A) +*( 5E^D Push
^B+A) +*( 5E^DC Print
B+A) +*(^ 5E^DC Push
+A) +*(^ 5E^DCB Print
A) +*(+ 5E^DCB^ Pop And Push
) +*(+ 5E^DCB^A Print
End +* 5E^DCB^A+ Pop Until '('
End Empty 5E^DCB^A+*+ Pop Every element

PROGRAM CODE:

#include<stdio.h>

Dept of CSE DSTAM 15

Data Structures Laboratory BCSL305

#include<string.h>
#include<conio.h>

int F(char symbol)

{
switch(symbol)
{
case '+' :
case '-':
return 2;

case '*':
case '/':
return 4;

case '^':
case '$':
return 5;

case '(':return 0;

case '#': return -1;

default: return 8;

}
}

int G(char symbol)

{
switch(symbol)
{
case '+':
case '-':
return 1;

case '*':
case '/':
return 3;

case '^':
case '$':
return 6;

case '(': return 9;

case ')': return 0;

Dept of CSE DSTAM 16

Data Structures Laboratory BCSL305

default: return 7;
}
}

void infix_postfix(char infix[], char postfix[])

{
int top, j, i;
char s[30], symbol;

top = -1;
s[++top] = '#';
j = 0;

for(i=0; i < strlen(infix); i++)

{
symbol = infix[i];
while(F(s[top]) > G(symbol))
{
postfix[j] = s[top--];
j++;
}

if(F(s[top]) !=G(symbol))
s[++top] = symbol;
else
top--;
}

while(s[top] != '#')
{
postfix[j++] = s[top--];
}
postfix[j] = '\0';
}

void main()
{
char infix[20], postfix[20];
clrscr();

printf("\nEnter a valid infix expression\n");

flushall();
gets(infix);
infix_postfix(infix,postfix);
printf("\nThe infix expression is:\n");
printf ("%s",infix);
printf("\nThe postfix expression is:\n");

Dept of CSE DSTAM 17

Data Structures Laboratory BCSL305

printf ("%s",postfix);
getch();
}

SAMPLE OUTPUT:

Enter a valid infix expression (a+(b-c)*d)

The infix expression is: (a+(b-c)*d)
The postfix expression is: abc-d*+

Program - 05

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.

Dept of CSE DSTAM 18

Data Structures Laboratory BCSL305

ABOUT THE EXPERIMENT:

a. Evaluation of Suffix expression with single digit operands and operators: +, -, *, /, %, ^
Postfix/Suffix Expression: Operators are written after their operands. Ex: XY+
In normal algebra we use the infix notation like a+b*c. The corresponding postfix notation is
abc*+

Example: Postfix String: 123*+4-

Initially the Stack is empty. Now, the first three characters scanned are 1,2 and 3, which are
operands. Thus they will be pushed into the stack in that order.

Expression

Stack
Next character scanned is "*", which is an operator. Thus, we pop the top two elements from the
stack and perform the "*" operation with the two operands. The second operand will be the first
element that is popped.

Expression

Stack
The value of the expression(2*3) that has been evaluated(6) is pushed into the stack.

Expression

Stack
Next character scanned is "+", which is an operator. Thus, we pop the top two elements from
the stack and perform the "+" operation with the two operands. The second operand will be the
first element that is popped.

Expression

Dept of CSE DSTAM 19

Data Structures Laboratory BCSL305

Stack
The value of the expression(1+6) that has been evaluated(7) is pushed into the stack.

Expression

Stack
Next character scanned is "4", which is added to the stack.

Expression

Stack
Next character scanned is "-", which is an operator. Thus, we pop the top two elements from the
stack and perform the "-" operation with the two operands. The second operand will be the first
element that is popped.

Expression
Stack
The value of the expression(7-4) that has been evaluated(3) is pushed into the stack.

Expression

Stack
Now, since all the characters are scanned, the remaining element in the stack (there will be only
one element in the stack) will be returned.

End result:
Postfix String: 123*+4-
Result: 3

ALGORITHM:

Dept of CSE DSTAM 20

Data Structures Laboratory BCSL305

Step 1: Start.
Step 2: Read the postfix/suffix expression.
Step 3: Evaluate the postfix expression based on the precedence of the operator.
Step 4: Stop.

b. Solving Tower of Hanoi problem with n disks.

The Tower of Hanoi is a mathematical game or puzzle. It consists of three rods, and a
number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks
in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a
conical shape. The objective of the puzzle is to move the entire stack to another rod, obeying the
following simple rules:
 Only one disk can be moved at a time.
 Each move consists of taking the upper disk from one of the stacks and placing it on top
of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
 No disk may be placed on top of a smaller disk.
o With three disks, the puzzle can be solved in seven moves. The minimum number
of moves required to solve a Tower of Hanoi puzzle is 2 n - 1, where n is the
number of disks.

ALGORITHM:
Step 1: Start.
Step 2: Read N number of discs.
Step 3: Move all the discs from source to destination by using temp rod.
Step 4: Stop.

PROGRAM CODE:

PROGRAM 5A:
#include<stdio.h>
#include<conio.h>
#include<math.h>
#include<string.h>

double compute(char symbol, double op1, double op2)

{

Dept of CSE DSTAM 21

Data Structures Laboratory BCSL305

switch(symbol)
{
case '+': return op1 + op2;
case' -': return op1 - op2;
case '*': return op1 * op2;
case '/': return op1 / op2;
case '$':
case '^': return pow(op1,op2);
default: return 0;
}
}

void main()
{
double s[20], res, op1, op2;
int top, i;
char postfix[20], symbol;
clrscr();
printf("\nEnter the postfix expression:\n");
flushall();
gets(postfix);
top=-1;
for(i=0; i<strlen(postfix); i++)
{
symbol = postfix[i];
if(isdigit(symbol))
s[++top] = symbol - '0';
else
{
op2 = s[top--];
op1 = s[top--];
res = compute(symbol, op1, op2);
s[++top] = res;
}
}
res = s[top--];
printf("\nThe result is : %f\n", res);
getch();
}

SAMPLE OUTPUT:

RUN1:

Dept of CSE DSTAM 22

Data Structures Laboratory BCSL305

Enter the postfix

expression: 23+
The result is: 5.000000

RUN2:

Enter the postfix

expression: 23+7*
The result is: 35.000000

PROGRAM 5B:

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

void tower(int n, int source, int temp,int destination)

{
if(n == 0) return;
tower(n-1, source, destination, temp);
printf("\nMove disc %d from %c to %c", n, source, destination);
tower(n-1, temp, source, destination);

void main()
{
int n;
clrscr();
printf("\nEnter the number of discs: \n");
scanf("%d", &n);
tower(n, 'A', 'B', 'C');
printf("\n\nTotal Number of moves are: %d", (int)pow(2,n)-1);
getch();
}

SAMPLE OUTPUT:

Enter the number of discs: 3

Move disc 1 from A to C Move
disc 2 from A to B Move disc 1
from C to B Move disc 3 from A
to C Move disc 1 from B to A
Move disc 2 from B to C Move
disc 1 from A to C

Dept of CSE DSTAM 23

Data Structures Laboratory BCSL305

Total Number of moves are: 7"

Program - 06
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

Dept of CSE DSTAM 24

Data Structures Laboratory BCSL305

ABOUT THE EXPERIMENT:

Circular queue is a linear data structure. It follows FIFO principle. In circular queue the last node
is connected back to the first node to make a circle. Circular linked list fallow the First In First
Out principle. Elements are added at the rear end and the elements are deleted at front end of the
queue. The queue is considered as a circular queue when the positions 0 and MAX-1 are
adjacent. Any position before front is also after rear.

A circular queue looks like

Consider the example with Circular Queue implementation:

ALGORITHM:
Step 1: Start.
Step 2: Initialize queue size to MAX.
Step 3: Insert the elements into circular queue. If queue is full give a message as ‘queue is
overflow”
Step 4: Delete an element from the circular queue. If queue is empty give a message as
‘queue is underflow’.
Step 5: Display the contents of the
queue. Step 6: Stop.

PROGRAM :

Dept of CSE DSTAM 25

Data Structures Laboratory BCSL305

#include<stdio.h>
#include<conio.h>
#define MAX 4

int ch, front = 0, rear = -1, count=0;

char q[MAX], item;

void insert()
{
if(count == MAX)
printf("\nQueue is Full");
else
{
rear = (rear + 1) % MAX;
q[rear]=item;
count++;
}
}

void del()
{
if(count == 0)
printf("\nQueue is Empty");
else
{
if(front > rear && rear==MAX-1)
{
front=0;rear=-1;count=0;
}
else
{
item=q[front];
printf("\nDeleted item is: %c",item);
front = (front + 1) % MAX;
count--;

}
}
}

void display()
{
int i, f=front, r=rear;
if(count == 0)
printf("\nQueue is Empty");

Dept of CSE DSTAM 26

Data Structures Laboratory BCSL305

else
{
printf("\nContents of Queue is:\n");
for(i=f; i!=r; i=(i+1)%max)
{
putch(q[i]);
}
printf(“%c\t”,q[i]);
}
}

void main()
{
clrscr();
do
{
printf("\n1. Insert\n2. Delete\n3. Display\n4. Exit");
printf("\nEnter the choice: ");
scanf("%d", &ch);
flushall();
switch(ch)
{
case 1: printf("\nEnter the character / item to be inserted: ");
item=getche();
insert();
break;
case 2: del(); break;
case 3: display(); break;
case 4: exit(0); break;
}
}while(ch!=4);
getch();
}

SAMPLE POUTPUT:

1. Insert 2. Delete 3. Display 4. Exit

Enter the choice: 1
Enter the character / item to be inserted: A
1. Insert 2. Delete 3. Display 4. Exit
Enter the choice: 1
Enter the character / item to be inserted: B

1. Insert 2. Delete 3. Display 4. Exit

Dept of CSE DSTAM 27
Data Structures Laboratory BCSL305

Enter the choice: 1

Enter the character / item to be inserted: C
1. Insert 2. Delete 3. Display 4. Exit
Enter the choice: 1
Enter the character / item to be inserted: D
1. Insert 2. Delete 3. Display 4. Exit
Enter the choice: 3

Contents of Queue is:

A B C D

1. Insert 2. Delete 3. Display 4. Exit

Enter the choice: 1
Enter the character / item to be inserted: F

Queue is full.

1. Insert 2. Delete 3. Display 4. Exit

Enter the choice: 2
Deleted item is: A

1. Insert 2. Delete 3. Display 4. Exit

Enter the choice:3

Contents of Queue is:

B C D

1. Insert 2. Delete 3. Display 4. Exit

Enter the choice: 1
Enter the character / item to be inserted: F

1. Insert 2. Delete 3. Display 4. Exit

Enter the choice: 3

Contents of Queue is:

B C D F

1. Insert 2. Delete 3. Display 4. Exit

Enter the choice:4

Dept of CSE DSTAM 28

Data Structures Laboratory BCSL305

Program - 07

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 and Deletion at End of SLL
d. Perform Insertion and Deletion at Front of SLL
e. Demonstrate how this SLL can be used as STACK and QUEUE
f. Exit

ABOUT THE EXPERIMENT:

Dept of CSE DSTAM 29

Data Structures Laboratory BCSL305

Linked List is a linear data structure and it is very common data structure which consists of
group of nodes in a sequence which is divided in two parts. Each node consists of its own data
and the address of the next node and forms a chain. Linked Lists are used to create trees and
graphs.

 They are a dynamic in nature which allocates the memory when required.
 Insertion and deletion operations can be easily implemented.
 Stacks and queues can be easily executed.
 Linked List reduces the access time.
 Linked lists are used to implement stacks, queues, graphs, etc.
 Linked lists let you insert elements at the beginning and end of the list.
 In Linked Lists we don’t need to know the size in advance.

Types of Linked List:

Singly Linked List: Singly linked lists contain nodes which have a data part as well as an
address part i.e. next, which points to the next node in sequence of nodes. The operations we can
perform on singly linked lists are insertion, deletion and traversal.

Doubly Linked List: In a doubly linked list, each node contains two links the first link points to
the previous node and the next link points to the next node in the sequence.

Circular Linked List: In the circular linked list the last node of the list contains the address
of the first node and forms a circular chain.

ALGORITHM:
Step 1: Start.
Step 2: Read the value of N. (N student’s information)
Step 2: Create a singly linked list. (SLL)
Step 3: Display the status of SLL.
Step 4: Count the number of nodes.
Step 5: Perform insertion at front of list.

Dept of CSE DSTAM 30

Data Structures Laboratory BCSL305

Step 6: Perform deletion at the front of the list.

Step 7: Perform insertion at end of the list.
Step 8: Perform deletion at the end of the list.
Step 9: Demonstrate how singly linked list can be used as stack.
Step 10: Demonstrate how singly linked list can be used as queue.
Step 11: Stop.

PROGRAM CODE:
#include<stdio.h>
#include<conio.h>
int MAX=4, count;
struct student
{
char usn[10];
char name[30];
char branch[5];
int sem;
char phno[10];
struct student *next;
};

typedef struct student NODE;

NODE*head;

int countnodes( )
{
NODE *p;
count=0;
p=head;
while(p!=NULL)
{
p=p->next;
count++;

}
return count;
}

NODE* getnode( )
{
NODE *newnode;
newnode=(NODE*)malloc(sizeof(NODE));
printf("\nEnter USN, Name, Branch, Sem, Ph.No\n");
flushall();
gets(newnode->usn);
flushall();

Dept of CSE DSTAM 31

Data Structures Laboratory BCSL305

gets(newnode->name);
flushall();
gets(newnode->branch);
scanf("%d",&(newnode->sem));
flushall();
gets(newnode->phno);
newnode->next=NULL;
return newnode;

NODE* display( )
{
NODE *p;
if(head == NULL)
printf("\nNo student data\n");
else
{
p=head;
printf("\n----STUDENT DATA----\n"); printf("\nUSN\
tNAME\t\tBRANCH\tSEM\tPh.NO.");
while(p!=NULL)
{
printf("\n%s\t%s\t\t%s\t%d\t%s", p->usn, p->name, p->branch, p->sem,
p->phno);
p = p->next; //Go to next node...

}
printf("\nThe no. of nodes in list is: %d",countnodes(head));
}
return head;
}

NODE* create( )
{
NODE *newnode;

if(head==NULL)
{
newnode=getnode( );
head=newnode;
}
else
{
newnode=getnode( );

Dept of CSE DSTAM 32

Data Structures Laboratory BCSL305

newnode->next=head;
head=newnode;
}
return head;
}

void insert_front( )
{
if(countnodes(head)==MAX)
printf("\nList is Full / Overflow!!");
else
head=create( );
}

void insert_rear( )
{
NODE *p, *newnode;
p=head;
if(countnodes(head) == MAX)
printf("\nList is Full(QUEUE)!!");
else
{
if(head == NULL)
{
newnode=getnode( );
head=newnode; //set first node to be head
}
else
{
newnode=getnode(head);
while(p->next!=NULL)
{
p=p->next;
}
p->next=newnode;
}
}
}

void insert( )
{
int ch;
do
{
printf("\n1.Insert at Front(First)\t2.Insert at End(Rear/Last)\t3.Exit");
printf("\nEnter your choice: ");
scanf("%d", &ch);

Dept of CSE DSTAM 33

Data Structures Laboratory BCSL305

switch(ch)
{
case 1: insert_front( ); break;
case 2: insert_rear( ); break;
case 3: break;
}
display( );
}while(ch!=3);
}

void delete_front( )
{
NODE *p;
if(head==NULL)
printf("\nList is Empty/Underflow (STACK/QUEUE)");
else
{
p=head;
head=head->next;
free(p);
printf("\nFront(first)node is deleted");
}
}

void delete_rear( )
{
NODE *p, *q;
p=head;
if(count==1)
{
delete_front();
return;
}
while(p->next!=NULL)
{
q=p;
p=p->next;
}
free(p);
q->next=NULL;
printf("\nLast(end) entry is deleted");
}

void del( )
{
int ch;
do

Dept of CSE DSTAM 34

Data Structures Laboratory BCSL305

{
printf("\n1.Delete from Front(First)\t2. Delete from End(Rear/Last))\t3.Exit");
printf("\nEnter your choice: ");
scanf("%d",&ch);
switch(ch)
{
case 1: delete_front( );
break;

case 2: delete_rear( );
break;

case 3: break;

}
display( );
}while(ch!=3);
}

NODE* stack( )
{
int ch;
do
{
printf("\nSSL used as Stack...");
printf("\n 1.Insert at Front(PUSH) \t 2.Delete from Front(POP))\t3.Exit");
printf("\nEnter your choice: ");
scanf("%d", &ch);
switch(ch)
{
case 1: insert_front( );
break;
case 2: delete_front( );
break;
case 3: break;

}
display( );
}while(ch!=3);
}

void queue( )
{
int ch;
do
{
printf("\nSSL used as Queue...");

Dept of CSE DSTAM 35

Data Structures Laboratory BCSL305

printf("\n 1.Insert at Rear(INSERT) \t 2.Delete from Front(DELETE))\t3.Exit");

printf("\nEnter your choice: ");
scanf("%d", &ch);
switch(ch)
{
case 1: insert_rear( ); break;
case 2: delete_front( ); break;
case 3: break;
}
display( );
}while(ch!=3);
}

void main()
{
int ch, i, n;
head=NULL;
clrscr();
printf("\n*----------Studednt Database-----------*");
do
{
printf("\n 1.Create\t 2.Display\t 3.Insert\t 4.Delete\t 5.Stack\t 6.Queue\t 7.Exit");
printf("\nEnter your choice: ");
scanf("%d", &ch);
switch(ch)
{
case 1: printf("\nHow many student data you want to create: ");
scanf("%d", &n);
for(i=0;i<n;i++)
create( );
break;
case 2: display( );
break;
case 3: insert( );
break;
case 4: del( );
break;
case 5: stack( );
break;
case 6: queue( );
break;
case 7: exit();
}
}while(ch!=7);
}

SAMPLE OUTPUT:

Dept of CSE DSTAM 36

Data Structures Laboratory BCSL305

1. Create 2. Display 3. Insert 4. Delete 5. Stack 6.Queue 7. Exit

Enter your choice: 1
How many student data you want to create: 2
Enter USN, Name, Branch, Sem, Ph.No
1kt12cs001 kumar cs 3 9900099000
Enter USN, Name, Branch, Sem, Ph.No
1kt12is002 ravi is 3 9900099111
1. Create 2. Display 3. Insert 4. Delete 5. Stack 6.Queue 7. Exit
Enter your choice: 2

----STUDENT DATA----
USN NAME BRANCH SEM Ph.NO.
1kt12is002 ravi is 3 9900099111
1kt12cs001 kumar cs 3 9900099000
The no. of nodes in list is: 2
1. Create 2. Display 3. Insert 4. Delete 5. Stack 6.Queue 7. Exit
Enter your choice: 3
1.Insert at Front(First)2.Insert at End(Rear/Last) 3.Exit
Enter your choice: 1
Enter USN, Name, Branch, Sem, Ph.No
1kt12cs003 suresh cs 3 99000992222

----STUDENT DATA----
USN NAME BRANCH SEM Ph.NO.
1kt12cs003 suresh cs 3 99000992222
1kt12is002 ravi is 3 9900099111
1kt12cs001 kumar cs 3 9900099000
The no. of nodes in list is: 3
1.Insert at Front(First)2.Insert at End(Rear/Last) 3.Exit
Enter your choice: 2
Enter USN, Name, Branch, Sem, Ph.No
1kt12is004 naresh is 3 99000993333

----STUDENT DATA----
USN NAME BRANCH SEM Ph.NO.
1kt12cs003 suresh cs 3 99000992222
1kt12is002 ravi is 3 9900099111
1kt12cs001 kumar cs 3 9900099000
1kt12is004 naresh is 3 99000993333
The no. of nodes in list is: 4

1.Insert at Front(First)2.Insert at End(Rear/Last) 3.Exit

Enter your choice: 3
1. Create 2. Display 3. Insert 4. Delete 5. Stack 6.Queue 7. Exit
Enter your choice: 4
1. Delete from Front (First) 2. Delete from End (Rear/Last) 3.Exit
Enter your choice: 1
Front (first) node is deleted

Dept of CSE DSTAM 37

Data Structures Laboratory BCSL305

----STUDENT DATA----
USN NAME BRANCH SEM Ph.NO.
1kt12is002 ravi Is 3 9900099111
1kt12cs001 kumar Cs 3 9900099000
1kt12is004 naresh Is 3 99000993333
The no. of nodes in list is: 3
1. Delete from Front (First) 2. Delete from End (Rear/Last) 3.Exit
Enter your choice: 2
Last (end) node is deleted

----STUDENT DATA----
USN NAME BRANCH SEM Ph.NO.
1kt12is002 ravi is 3 9900099111
1kt12cs001 kumar cs 3 9900099000
The no. of nodes in list is: 2
1. Delete from Front (First) 2. Delete from End (Rear/Last) 3.Exit
Enter your choice: 3
1. Create 2. Display 3. Insert 4. Delete 5. Stack 6.Queue 7. Exit
Enter your choice: 5
SSL used as Stack...
1.Insert at Front(PUSH) 2.Delete from Front(POP)) 3.Exit
Enter your choice: 1
Enter USN, Name, Branch, Sem, Ph.No
1kt12is010 vikky is 3 9900011111

----STUDENT DATA----
USN NAME BRANCH SEM Ph.NO.
1kt12is010 vikky is 3 9900011111
1kt12is002 ravi is 3 9900099111
1kt12cs001 kumar cs 3 9900099000
1. Create 2. Display 3. Insert 4. Delete 5. Stack 6.Queue 7. Exit
Enter your choice: 7

Program - 08
Design, Develop and Implement 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
ABOUT THE EXPERIMENT:

Dept of CSE DSTAM 38

Data Structures Laboratory BCSL305

Doubly Linked List: In a doubly linked list, each node contains two links the first link points
to the previous node and the next link points to the next node in the sequence.

In computer science, a doubly linked list is a linked data structure that consists of a set of
sequentially linked records called nodes. Each node contains two fields, called links, that
are references to the previous and to the next node in the sequence of nodes. The beginning and
ending nodes' previous and next links, respectively, point to some kind of terminator, typically a
sentinel node or null, to facilitate traversal of the list. If there is only one sentinel node, then the
list is circularly linked via the sentinel node. It can be conceptualized as two singly linked lists
formed from the same data items, but in opposite sequential orders.

A doubly linked list whose nodes contain three fields: an integer value, the link to the next node,
and the link to the previous node.
The two node links allow traversal of the list in either direction. While adding or removing a
node in a doubly linked list requires changing more links than the same operations on a singly
linked list, the operations are simpler and potentially more efficient (for nodes other than first
nodes) because there is no need to keep track of the previous node during traversal or no need to
traverse the list to find the previous node, so that its link can be modified.

ALGORITHM:
Step 1: Start.
Step 2: Read the value of N. (N student’s information)
Step 3: Create a doubly linked list. (DLL)
Step 4: Display the status of DLL.
Step 5: Count the number of nodes.
Step 6: Perform insertion at front of list.
Step 7: Perform deletion at the front of the list.
Step 8: Perform insertion at end of the list.
Step 9: Perform deletion at the end of the list.
Step 10: Demonstrate how doubly linked list can be used as double ended queue.
Step 11: Stop.

PROGRAM :
#include<stdio.h>
#include<conio.h>

int MAX=4, count;

struct emp
{
int ssn;

Dept of CSE DSTAM 39

Data Structures Laboratory BCSL305

char name[20];
char dept[10];
char desig[15];
int sal;
char phno[10];
struct emp *left;
struct emp *right;
};

typedef struct emp NODE;

int countnodes(NODE *head)

{
NODE *p; count=0; p=head;
while(p!=NULL)
{
p=p->right;
count++;
}
return count;
}
NODE* getnode(NODE *head)
{
NODE *newnode;
newnode=(NODE*)malloc(sizeof(NODE));
newnode->right=newnode->left=NULL;
printf("\nEnter SSN, Name, Dept, Designation, Sal, Ph.No\n");
scanf("%d",&newnode->ssn);
flushall();
gets(newnode->name);
flushall();
gets(newnode->dept);
flushall();
gets(newnode->desig);
scanf("%d",&newnode->sal);
flushall();
gets(newnode->phno);
head=newnode;
return head;
}
NODE* display(NODE *head)
{
NODE *p;
if(head==NULL)
printf("\nNo Employee data\n");

Dept of CSE DSTAM 40

Data Structures Laboratory BCSL305

else
{
p=head;
printf("\n----EMPLOYEE DATA----\n"); printf("\nSSN\tNAME\tDEPT\
tDESINGATION\tSAL\t\tPh.NO.");
while(p!=NULL)
{
printf("\n%d\t%s\t%s\t%s\t\t%d\t\t%s", p->ssn, p->name, p->dept,
p->desig,p->sal, p->phno);
p = p->right;
}
printf("\nThe no. of nodes in list is: %d",countnodes(head));
}
return head;
}

NODE* create(NODE *head) // creating & inserting at end.

{
NODE *p, *newnode;
p=head;
if(head==NULL)
{
newnode=getnode(head);
head=newnode;
}
else
{
newnode=getnode(head);
while(p->right!=NULL)
{
p=p->right;
}
p->right=newnode;
newnode->left=p;
}
return head;
}

NODE* insert_end(NODE *head)

{
if(countnodes(head)==MAX)
printf("\nList is Full!!");
else
head=create(head);
return head;
}

Dept of CSE DSTAM 41

Data Structures Laboratory BCSL305

NODE* insert_front(NODE *head)

{
NODE *p, *newnode;
if(countnodes(head)==MAX)
printf("\nList is Full!!");
else
{
if(head==NULL)
{
newnode=getnode(head);
head=newnode; //set first node to be head
}
else
{
newnode=getnode(head);
newnode->right=head;
head->left=newnode;
head=newnode;
}
}
return head;
}

NODE* insert(NODE *head)

{
int ch;
do
{
printf("\n 1.Insert at Front(First) \t 2.Insert at End(Rear/Last)\t3.Exit");
printf("\nEnter your choice: ");
scanf("%d", &ch);
switch(ch)
{
case 1: head=insert_front(head);
break;
case 2: head=insert_end(head);
break;
case 3: break;
}
head=display(head);
}while(ch!=3);
return head;
}

Dept of CSE DSTAM 42

Data Structures Laboratory BCSL305

NODE* delete_front(NODE *head)

{
NODE *p;
if(head==NULL)
printf("\nList is Empty (QUEUE)");
else
{
p=head;
head=head->right;
head->right->left=NULL;
free(p);
printf("\nFront(first)node is deleted");
}
return head;
}

NODE* delete_end(NODE *head)

{
NODE *p, *q;
p=head;
while(p->right!=NULL)
{
p=p->right;
}
q=p->left;
q->right=NULL;
p->left=NULL;
free(p);
printf("\nLast(end) entry is deleted");
return head;
}

NODE *del(NODE *head)

{
int ch;
do {
printf("\n1.Delete from Front(First)\t2. Delete from End(Rear/Last))\t3.Exit");
printf("\nEnter your choice: ");
scanf("%d", &ch);
switch(ch)
{

case 1: head=delete_front(head); break;

case 2: head=delete_end(head); break;
case 3: break;
}

Dept of CSE DSTAM 43

Data Structures Laboratory BCSL305

head=display(head);
}while(ch!=3);
return head;
}

NODE* queue(NODE *head)

{
int ch, ch1, ch2;
do
{
printf("\nDLL used as Double Ended Queue");
printf("\n1.QUEUE- Insert at Rear & Delete from Front");
printf("\n2.QUEUE- Insert at Front & Delete from Rear");
printf("\n3.Exit");
printf("\nEnter your choice: ");
scanf("%d", &ch);
switch(ch)
{
case 1: do
{
printf("\n1.Insert at Rear\t2.Delete from From Front\
t3.Exit");
printf("\nEnter your choice: ");
scanf("%d", &ch1);
switch(ch1)
{
case 1: head=insert_end(head); break;
case 2: head=delete_front(head); break;
case 3: break;
}
}while(ch1!=3);
break;

case 2: do
{
printf("\n1.Insert at Front\t2.Delete from Rear\t3.Exit"); printf("\
nEnter your choice: ");
scanf("%d", &ch2);
switch(ch2)
{
case 1: head=insert_front(head); break;
case 2: head=delete_end(head); break;
case 3: break;
}
}while(ch2!=3);
break;

Dept of CSE DSTAM 44

Data Structures Laboratory BCSL305

case 3: break;
}
}while(ch!=3);
head=display(head);
return head;
}

void main()
{
int ch, i, n;
NODE *head;
head=NULL;
clrscr();
printf("\n----------Employee Database-----------");
do
{
printf("\n1.Create\t2.Display\t3.Insert\t4.Delete\t5.Queue\t6.Exit"); printf("\
nEnter your choice: ");
scanf("%d", &ch);
switch(ch)
{
case 1: printf("\nHow many employees data you want to create: ");
scanf("%d", &n);
for(i=0;i<n;i++)
head=create(head);//Call to Create node...
break;
case 2: head=display(head); //Call to Display...
break;
case 3: head=insert(head); //Call to Insert...
break;
case 4: head=del(head); //Call to delete
break;
case 5: head=queue(head);
break;
case 6: exit(0); //Exit...
break;
}
}while(ch!=6);
}

SAMPLE OUTPUT:

----------Employee Database-----------
1. Create 2. Display 3. Insert 4. Delete 5. Queue 7. Exit
Enter your choice: 1
How many employees data you want to create: 2
Enter SSN, Name, Dept, Designation, Sal, Ph.No

Dept of CSE DSTAM 45

Data Structures Laboratory BCSL305

1 KUMAR CSE INSTRUCTOR 8000 900099000

Enter SSN, Name, Dept, Designation, Sal, Ph.No

2 RAVI CSE INSTRUCTOR 9000 900099111

1. Create 2. Display 3. Insert 4. Delete 5. Queue 7. Exit

Enter your choice: 2
----EMPLOYEE DATA----
SSN NAME DEPT DESINGATION SAL Ph.NO.
1 KUMAR CSE INSTRUCTOR 8000 900099000
2 RAVI CSE INSTRUCTOR 9000 900099111
The no. of nodes in list is: 2

1. Create 2. Display 3. Insert 4. Delete 5. Queue 7. Exit

Enter your choice: 3
1. Insert at Front (First) 2.Insert at End (Rear/Last) 3.Exit
Enter your choice: 1
Enter SSN, Name, Dept, Designation, Sal, Ph.No
3 JIM CSE ATTENDER 6000 900099333
----EMPLOYEE DATA----
SSN NAME DEPT DESINGATION SAL Ph.NO.
3 JIM CSE ATTENDER 6000 900099333
1 KUMAR CSE INSTRUCTOR 8000 900099000
2 RAVI CSE INSTRUCTOR 9000 900099111
The no. of nodes in list is: 3
1. Insert at Front (First) 2.Insert at End (Rear/Last) 3.Exit
Enter your choice: 3

1. Create 2. Display 3. Insert 4. Delete 5. Queue 7. Exit

Enter your choice: 5
DLL used as Double Ended Queue
1.QUEUE- Insert at Rear & Delete from Front
2.QUEUE- Insert at Front & Delete from Rear
3.Exit
Enter your choice: 3
1. Create 2. Display 3. Insert 4. Delete 5. Queue 7. Exit
Enter your choice: 7

Dept of CSE DSTAM 46

Data Structures Laboratory BCSL305

Program - 09

Design, Develop and Implement a Program in C for the following operations on 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

ABOUT THE EXPERIMENT:

Circular Linked List:

In the circular linked list the last node of the list contains the address of the first node and
forms a circular chain.

Dept of CSE DSTAM 47

Data Structures Laboratory BCSL305

Polynomial:
A polynomial equation is an equation that can be written in the form. axn + bxn-1 + . . . + rx + s
= 0, where a, b, . . . , r and s are constants. We call the largest exponent of x appearing in a non-
zero term of a polynomial the degree of that polynomial.

As with polynomials with one variable, you must pay attention to the rules of exponents and
the order of operations so that you correctly evaluate an expression with two or more
variables.
Evaluate x2 + 3y3 for x = 7 and y = −2. Substitute the given values for x and y.
Evaluate 4x2 y – 2xy2 + x – 7 for x = 3 and y = −1.
When a term contains both a number and a variable part, the number part is called the
"coefficient". The coefficient on the leading term is called the "leading" coefficient.

In the above example, the coefficient of the leading term is 4; the coefficient of the
second term is 3; the constant term doesn't have a coefficient.
Here are the steps required for Evaluating Polynomial Functions:

Step 1: Replace each x in the expression with the given value.

Step 2: Use the order of operation to simplify the expression.
Example 1 –

Step 1: Replace each x in the expression

with the given value. In this case, we
replace each x with 3.

Step 2: Use the order of operation to

simplify the expression.

Here are the steps required for addition of two polynomials.

Step1

Dept of CSE DSTAM 48

Data Structures Laboratory BCSL305

 Arrange the Polynomial in standard form

 Standard form of a polynomial just means that the term with highest degree is first and
each of the following terms
Step2
 Arrange the like terms in columns and add the like terms

Example 1: Let's find the sum of the following two polynomials

5 4 3 5 3
(3y − 2y + y + 2y + 5) and (2y + 3y + 2+ 7)

ALGORITHM:
Step 1: Start.
Step 2: Read a polynomial.
Step 3: Represent the polynomial using singly circular linked list.
Step 3: Evaluate the given polynomial
Step 4: Read two polynomials and find the sum of the polynomials.
Step 5: Stop

PROGRAM :
#include<stdio.h>
#include<alloc.h>
#include<math.h>

struct node
{
int cf, px, py, pz;

Dept of CSE DSTAM 49

Data Structures Laboratory BCSL305

int flag;
struct node *link;
};
typedef struct node NODE;

NODE* getnode()
{
NODE *x;
x=(NODE*)malloc(sizeof(NODE));
if(x==NULL)
{
printf("Insufficient memory\n");
exit(0);
}
return x;
}

void display(NODE *head)

{
NODE *temp;
if(head->link==head)
{
printf("Polynomial does not exist\n");
return;
}
temp=head->link;
printf("\n");
while(temp!=head)
{
printf("%d x^%d y^%d z^%d",temp->cf,temp->px,temp->py,temp->pz);

if(temp->link != head)
printf(" + ");
temp=temp->link;
}
printf("\n");
}

NODE* insert_rear(int cf,int x,int y,int z,NODE *head)

{
NODE *temp,*cur;
temp=getnode();
temp->cf=cf;
temp->px=x;
temp->py=y;
temp->pz=z;

Dept of CSE DSTAM 50

Data Structures Laboratory BCSL305

temp->flag=0;
cur=head->link;
while(cur->link!=head)
{
cur=cur->link;
}
cur->link=temp;
temp->link=head;
return head;
}

NODE* read_poly(NODE *head)

{
int px, py, pz, cf, ch;
do
{
printf("\nEnter coeff: ");
scanf("%d",&cf);
printf("\nEnter x, y, z powers(0-indiacate NO term): ");
scanf("%d%d%d", &px, &py, &pz);
head=insert_rear(cf,px,py,pz,head);
printf("\nIf you wish to continue press 1 otherwCSE 0: ");
scanf("%d", &ch);
}while(ch!=0);
return head;
}

NODE* add_poly(NODE *h1,NODE *h2,NODE *h3)

{
NODE *p1,*p2;
int x1,x2,y1,y2,z1,z2,cf1,cf2,cf;
p1=h1->link;
while(p1!=h1)
{
x1=p1->px;
y1=p1->py;
z1=p1->pz;
cf1=p1->cf;
p2=h2->link;
while(p2!=h2)
{
x2=p2->px;
y2=p2->py;
z2=p2->pz;
cf2=p2->cf;
if(x1==x2 && y1==y2 && z1==z2)

Dept of CSE DSTAM 51

Data Structures Laboratory BCSL305

break;
p2=p2->link;
}
if(p2!=h2)
{
cf=cf1+cf2;
p2->flag=1;
if(cf!=0)
h3=insert_rear(cf,x1,y1,z1,h3);
}
else
h3=insert_rear(cf1,x1,y1,z1,h3);
p1=p1->link;
}

p2=h2->link;
while(p2!=h2)
{
if(p2->flag==0)
h3=insert_rear(p2->cf,p2->px,p2->py,p2->pz,h3);
p2=p2->link;
}
return h3;
}

void evaluate(NODE *h1)

{
NODE *head;
int x, y, z;
float result=0.0;
head=h1;
printf("\nEnter x, y, z, terms to evaluate:\n");
scanf("%d%d%d", &x, &y, &z);
while(h1->link != head)
{
h1=h1->link;
result = result + (h1->cf * pow(x,h1->px) * pow(y,h1->py) * pow(z,h1->pz));
h1=h1->link;
}
result = result + (h1->cf * pow(x,h1->px) * pow(y,h1->py) * pow(z,h1->pz));
printf("\nPolynomial result is: %f", result);
}

void main()
{
NODE*h1,*h2,*h3;

Dept of CSE DSTAM 52

Data Structures Laboratory BCSL305

int ch;
clrscr();
h1=getnode();
h2=getnode();
h3=getnode();
h1->link=h1;
h2->link=h2;
h3->link=h3;
while(1)
{
printf("\n\n1.Evaluate polynomial\n2.Add two polynomials\n3.Exit\n");
printf("Enter your choice: ");
scanf("%d", &ch);
switch(ch)
{
case 1:
printf("\nEnter polynomial to evaluate:\n");
h1=read_poly(h1);
display(h1);
evaluate(h1);
h1->link=h1;
break;
case 2:
printf("\nEnter the first polynomial:");
h1=read_poly(h1);
printf("\nEnter the second polynomial:");
h2=read_poly(h2);
h3=add_poly(h1,h2,h3);
printf("\nFirst polynomial is: ");
display(h1);
printf("\nSecond polynomial is: ");
display(h2);
printf("\nThe sum of 2 polynomials is: ");
display(h3);
h1->link=h1;
h2->link=h2;
h3->link=h3;
break;
case 3:
exit(0);
break;
default:
printf("\nInvalid entry");
break;
}
getch();
}

Dept of CSE DSTAM 53

Data Structures Laboratory BCSL305

SAMPLE OUTPUT:

1.Evaluate polynomial P(x,y,z) = 6x2y2z-4yz5+3x3yz+2xy5z-2xyz3

2.Add two polynomials
3.Exit
Enter your choice: 1

Enter polynomial to evaluate:

Enter coeff: 6
Enter x, y, z powers (0-indiacate
NO term: 2 2 1
If you wish to continue press 1
otherwCSE 0: 1
Enter coeff:-4
Enter x, y, z powers (0-indiacate
NO term: 0 1 5
If you wish to continue press 1
otherwCSE 0: 1
Enter coeff:3
Enter x, y, z powers (0-indiacate
NO term: 3 1 1
If you wish to continue press 1
otherwCSE 0: 1
Enter coeff:2
Enter x, y, z powers (0-indiacate
NO term: 1 5 1
If you wish to continue press 1 otherwCSE 0: 1
Enter coeff: -2
Enter x, y, z powers (0-indiacate NO
term: 1 1 3
If you wish to continue press 1
otherwCSE 0: 0

Polynomial is:
6 x^2 y^2 z^1 + -4 x^0 y^1 z^5 + 3 x^3 y^1 z^1 + 2 x^1 y^5 z^1 + -2 x^1 y^1 z^3

Enter x, y, z, terms to
evaluate: 1 1 1

Polynomial result is: 5.000000

1.Evaluate polynomial P(x,y,z) = 6x2y2z-4yz5+3x3yz+2xy5z-2xyz3

2.Add two polynomials
3.Exit
Enter your choice: 2

Enter 1st polynomial:

Dept of CSE DSTAM 54

Data Structures Laboratory BCSL305

Enter
coeff: 4
Enter x, y, z powers (0-indiacate
NO term: 2 2 2

If you wish to continue press 1 otherwCSE 0: 1

Enter coeff: 3
Enter x, y, z powers (0-indiacate
NO term: 1 1 2
If you wish to continue press 1 otherwCSE 0: 0
Enter 2nd polynomial:
Enter
coeff: 6

Enter x, y, z powers (0-indiacate

NO term: 2 2 2
If you wish to continue press 1
otherwCSE 0: 0

Polynomial is: 1st Polynomial is:

4 x^2 y^2 z^2 + 3 x^1 y^1 z^2

2nd Polynomial is: 6 x^2 y^2 z^2

Added polynomial: 10 x^2 y^2 z^2 + 3 x^1 y^1 z^2

1.Evaluate polynomial P(x,y,z) = 6x2y2z-4yz5+3x3yz+2xy5z-2xyz3
2.Add two polynomials
3.Exit
Enter your choice: 3

Program - 10
Design, Develop and Implement 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. Delete an element (ELEM) from BST
e. Exit

ABOUT THE EXPERIMENT:

A binary search tree (BST) is a tree in which all nodes follows the below mentioned
properties
 The left sub-tree of a node has key less than or equal to its parent node's key.
 The right sub-tree of a node has key greater than or equal to its parent node's key.
Thus, a binary search tree (BST) divides all its sub-trees into two segments; left sub-tree
and right sub-tree and can be defined as

Dept of CSE DSTAM 55

Data Structures Laboratory BCSL305

left_subtree (keys) ≤ node (key) ≤ right_subtree (keys)

Fig: An example of BST

Following are basic primary operations of a tree which are following.

 Search − search an element in a tree.
 Insert − insert an element in a tree.
 Preorder Traversal − traverse a tree in a preorder manner.
 Inorder Traversal − traverse a tree in an inorder manner.
 Postorder Traversal − traverse a tree in a postorder manner.

Node definition: Define a node having some data, references to its left and right child
nodes.
struct node
{
int data;
struct node *leftChild;
struct node *rightChild;
};

ALGORITHM:
Step 1: Start.
Step 2: Create a Binary Search Tree for N elements.
Step 3: Traverse the tree in inorder.
Step 4: Traverse the tree in preorder
Step 6: Traverse the tree in postorder.
Step 7: Search the given key element in the BST.
Step 8: Delete an element from BST.
Step 9: Stop

PROGRAM CODE:
#include <stdio.h>
#include <stdlib.h>
struct BST
{
int data;

Dept of CSE DSTAM 56

Data Structures Laboratory BCSL305

struct BST *left;

struct BST *right;
};
typedef struct BST NODE;
NODE *node;

NODE* createtree(NODE *node, int data)

{
if (node == NULL)
{
NODE *temp;
temp= (NODE*)malloc(sizeof(NODE));
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
if (data < (node->data))
{
node->left = createtree(node->left, data);
}
else if (data > node->data)
{
node -> right = createtree(node->right, data);
}
return node;
}

NODE* search(NODE *node, int data)

{
if(node == NULL)

printf("\nElement not found");

else if(data < node->data)
{
node->left=search(node->left, data);
}
else if(data > node->data)
{
node->right=search(node->right, data);
}
else
printf("\nElement found is: %d", node->data);
return node;
}

void inorder(NODE *node)

Dept of CSE DSTAM 57

Data Structures Laboratory BCSL305

{
if(node != NULL)
{
inorder(node->left);
printf("%d\t", node->data);
inorder(node->right);
}
}

void preorder(NODE *node)

{
if(node != NULL)
{
printf("%d\t", node->data);
preorder(node->left);
preorder(node->right);
}
}
void postorder(NODE *node)
{
if(node != NULL)
{
postorder(node->left);
postorder(node->right);
printf("%d\t", node->data);
}
}

void main()
{
int data, ch, i, n;
NODE *root=NULL;
clrscr();
while (1)
{
printf("\n1.Insertion in Binary Search Tree");
printf("\n2.Search Element in Binary Search Tree");
printf("\n4.Inorder\n5.Preorder\n6.Postorder\n7.Exit");
printf("\nEnter your choice: ");
scanf("%d", &ch);
switch (ch)
{
case 1: printf("\nEnter N value: " );
scanf("%d", &n);

Dept of CSE DSTAM 58

Data Structures Laboratory BCSL305

printf("\nEnter the values to create BST like(6,9,5,2,8,15,24,14,7,8,5,2)\n");

for(i=0; i<n; i++)
{
scanf("%d", &data);
root=createtree(root, data);
}
break;
case 2: printf("\nEnter the element to search: ");
scanf("%d", &data);
root=search(root, data);
break;
case 3: printf("\nInorder Traversal: \n");
inorder(root);
break;
case 4: printf("\nPreorder Traversal: \n");
preorder(root);
break;
case 5: printf("\nPostorder Traversal: \n");
postorder(root);
break;
case 7: exit(0);
default:printf("\nWrong option");
break;
}
}
getch();
}

SAMPLE OUTPUT:
1.Insertion in Binary Search Tree
2.Search Element in Binary Search Tree
3.Delete Element in Binary Search Tree
4.Inorder
5.Preorder
6.Postorder
7.Exit
Enter your choice: 1
Enter N
value: 12
Enter the values to create BST
like(6,9,5,2,8,15,24,14,7,8,5,2)
6 9 5 2 8 15 24 14 7 8 5 2

1.Insertion in Binary Search Tree

2.Search Element in Binary Search Tree
3.Delete Element in Binary Search Tree

Dept of CSE DSTAM 59

Data Structures Laboratory BCSL305

4.Inorder
5.Preorder
6.Postorder
7.Exit
Enter your choice: 4
Inorder
Traversal:
2 5 6 7 8 9 14 15 24

1.Insertion in Binary Search Tree

2.Search Element in Binary Search Tree
3.Delete Element in Binary Search Tree
4.Inorder
5.Preorder
6.Postorder
7.Exit
Enter your choice: 5
Preorder
Traversal:
6 5 2 9 8 7 15 14 24

1.Insertion in Binary Search Tree

2.Search Element in Binary Search Tree
3.Delete Element in Binary Search Tree
4.Inorder
5.Preorder
6.Postorder
7.Exit
Enter your choice: 6
Postorder
Traversal:
2 5 7 8 14 24 15 9 6

1.Insertion in Binary Search Tree

2.Search Element in Binary Search Tree
3.Delete Element in Binary Search Tree
4.Inorder
5.Preorder
6.Postorder
7.Exit
Enter your choice: 2
Enter the element to search: 24
Element found is:
24
1.Insertion in Binary Search Tree
2.Search Element in Binary Search Tree
3.Delete Element in Binary Search Tree

Dept of CSE DSTAM 60

Data Structures Laboratory BCSL305

4.Inorder
5.Preorder
6.Postorder
7.Exit
Enter your choice: 2
Enter the element to search: 50

Element not found

1.Insertion in Binary Search Tree

2.Search Element in Binary Search Tree
3.Delete Element in Binary Search Tree
4.Inorder
5.Preorder
6.Postorder
7.Exit
Enter your choice: 3
Enter the element to search: 15

1.Insertion in Binary Search Tree

2.Search Element in Binary Search Tree
3.Delete Element in Binary Search Tree
4.Inorder
5.Preorder
6.Postorder
7.Exit
Enter your choice: 4
Inorder
Traversal:
2 5 6 7 8 9 14 24

1.Insertion in Binary Search Tree

2.Search Element in Binary Search Tree
3.Delete Element in Binary Search Tree
4.Inorder
5.Preorder
6.Postorder
7.Exit
Enter your choice: 5
Preorder
Traversal:
6 5 2 9 8 7 24 14

1.Insertion in Binary Search Tree

2.Search Element in Binary Search Tree
3.Delete Element in Binary Search Tree
4.Inorder
5.Preorder

Dept of CSE DSTAM 61

Data Structures Laboratory BCSL305

6.Postorder
7.Exit
Enter your choice: 7

Program - 11

Design, Develop and Implement 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 BFS
method
c. Check whether a given graph is connected or not using DFS method.

ABOUT THE EXPERIMENT:

Adjacency Matrix
In graph theory, computer science, an adjacency matrix is a square matrix used to
represent a finite graph. The elements of the matrix indicate whether pairs of vertices are
adjacent or not in the graph. In the special case of a finite simple graph, the adjacency matrix
is a (0, 1)-matrix with zeros on its diagonal.

Dept of CSE DSTAM 62

Data Structures Laboratory BCSL305

A graph G = (V, E) where v= {0, 1, 2, . . .n-1} can be represented using two dimensional integer
array of size n x n.
a[20][20] can be used to store a graph with 20 vertices.
a[i][j] = 1, indicates presence of edge between two vertices i and
j. a[i][j] = 0, indicates absence of edge between two vertices i
and j.
 A graph is represented using square matrix.
 Adjacency matrix of an undirected graph is always a symmetric matrix, i.e. an edge (i, j)
implies the edge (j, i).
 Adjacency matrix of a directed graph is never symmetric, adj[i][j] = 1 indicates a directed
edge from vertex i to vertex j.
An example of adjacency matrix representation of an undirected and directed graph is given
below:

BFS
Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data
structures. It starts at the tree root and explores the neighbor nodes first, before moving to the
next level neighbors. Breadth First Search algorithm (BFS) traverses a graph in a breadth wards
motion and uses a queue to remember to get the next vertex to start a search when a dead end
occurs in any iteration.

As in example given above, BFS algorithm traverses from A to B to E to F first then to C

and G lastly to D. It employs following rules.
 Rule 1 − Visit adjacent unvisited vertex. Mark it visited. Display it. Insert it in a queue.
 Rule 2 − If no adjacent vertex found, remove the first vertex from queue.

Dept of CSE DSTAM 63

Data Structures Laboratory BCSL305

 Rule 3 − Repeat Rule 1 and Rule 2 until queue is empty.

DFS
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data
structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph)
and explores as far as possible along each branch before backtracking.
Depth-first search, or DFS, is a way to traverse the graph. Initially it allows visiting
vertices of the graph only, but there are hundreds of algorithms for graphs, which are based on
DFS. Therefore, understanding the principles of depth-first search is quite important to move
ahead into the graph theory. The principle of the algorithm is quite simple: to go forward (in
depth) while there is such possibility, otherwCSE to backtrack.

Algorithm
In DFS, each vertex has three possible colors representing its state:

white: vertex is unvisited;

gray: vertex is in progress;

black: DFS has finished processing the vertex.

NB. For most algorithms Boolean classification unvisited / visited is quite enough, but we
show general case here.
Initially all vertices are white (unvisited). DFS starts in arbitrary vertex and runs as follows:
 Mark vertex u as gray (visited).
 For each edge (u, v), where u is white, run depth-first search for u recursively.
 Mark vertex u as black and backtrack to the parent.

Example. Traverse a graph shown below, using DFS. Start from a vertex with number 1 .

Source Graph

Mark a vertex 1 as gray.

There is an edge (1, 4) and a vertex 4 is

unvisited. Go there.

Dept of CSE DSTAM 64

Data Structures Laboratory BCSL305

Mark the vertex 4 as gray

There is an edge (4, 2) and vertex a 2 is

unvisited. Go there

Mark the vertex 2 as gray.

There is an edge (2, 5) and a vertex 5 is

unvisited. Go there

Mark the vertex 5 as gray.

There is an edge (5, 3) and a vertex 3 is

unvisited. Go there

Mark the vertex 3 as gray.

There are no ways to go from the vertex 3.

Mark it as black and backtrack to the vertex 5.

Dept of CSE DSTAM 65

Data Structures Laboratory BCSL305

There is an edge (5, 4), but the vertex 4 is

gray

There are no ways to go from the

vertex 5. Mark it as black and backtrack to the
vertex 2.

There are no more edges, adjacent to vertex 2.

Mark it as black and backtrack to the vertex 4.

There is an edge (4, 5), but the vertex 5 is

black.

There are no more edges, adjacent to the

vertex 4. Mark it as black and backtrack to the
vertex 1.

There are no more edges, adjacent to the

vertex 1. Mark it as black. DFS is over

ALGORITHM:
Step 1: Start.
Step 2: Input the value of N nodes of the graph
Step 3: Create a graph of N nodes using adjacency matrix representation.
Step 3: Print the nodes reachable from the starting node using BFS.
Step 4: Check whether graph is connected or not using DFS.
Step 5: Stop.

PROGRAM CODE:

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

int a[10][10], n, m, i, j, source, s[10], b[10];

int visited[10];

Dept of CSE DSTAM 66

Data Structures Laboratory BCSL305

void create()
{
printf("\nEnter the number of vertices of the digraph: "); scanf("%d", &n);
printf("\nEnter the adjacency matrix of the graph:\n"); for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
scanf("%d", &a[i][j]);
}

void bfs()
{
int q[10], u, front=0, rear=-1;
for(i=0;i<=n;i++)
visited[i]=0;

printf("\nEnter the source vertex to find other nodes reachable or not: ");
scanf("%d", &source);
q[++rear] = source;
visited[source] = 1;

printf("\nThe reachable vertices are: ");

while(front<=rear)
{

u = q[front++];
for(i=1; i<=n; i++)
{
if(a[u][i] == 1 && visited[i] == 0)
{
q[++rear] = i; visited[i] = 1; printf("\n%d", i);
}
}
}
}

void dfs(int source)

{
int v, top = -1;
s[++top] = 1;
b[source] = 1;

for(v=1; v<=n; v++)

{
if(a[source][v] == 1 && b[v] == 0)
{
printf("\n%d -> %d", source, v);

Dept of CSE DSTAM 67

Data Structures Laboratory BCSL305

dfs(v);

}
}
}

void main()
{
int ch;
clrscr();
while(1)
{
printf("\n1.Create Graph\n2.BFS\n3.Check graph connected or not(DFS)\
n4.Exit");
printf("\nEnter your choice: ");
scanf("%d", &ch);
switch(ch)
{
case 1: create(); break;
case 2: bfs();
for(i=1;i<=n;i++)
if(visited[i]==0)
printf("\nThe vertex that is not rechable %d" ,i);
break;

case 3: for(i=0;i<=n;i++)
b[i]=0;
printf("\nEnter the source vertex to find the connectivity: ");
scanf("%d",&source);
m=1;
dfs(source);
for(i=1;i<=n;i++)
{
if(b[i]==0)
m=0;
}
if(m==1)
printf("\nGraph is Connected");
else
printf("\nGraph is not Connected");

break;
default: exit(0);
}
}
}

Dept of CSE DSTAM 68

Data Structures Laboratory BCSL305

SAMPLE OUTPUT:

1. Create Graph 2.BFS 3.Check graph connected or not (DFS) 4.Exit

Enter your choice: 1

Enter the number of vertices of the digraph: 4

Enter the adjacency matrix of the graph:

0 0 1 1
0 0 0 0
0 1 0 0
0 1 0 0

1. Create Graph 2.BFS 3.Check graph connected or not (DFS) 4.Exit

Enter your choice: 2

Enter the source vertex to find other nodes reachable or not: 1 3 4 2

1. Create Graph 2.BFS 3.Check graph connected or not (DFS) 4.Exit

Enter your choice: 3

Enter the source vertex to find the connectivity: 1 1 -> 3 3 -> 2 1 -> 4

Graph is Connected

1. Create Graph 2.BFS 3.Check graph connected or not (DFS) 4.Exit

Enter your choice: 4

Dept of CSE DSTAM 69

Data Structures Laboratory BCSL305

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.

ABOUT THE EXPERIMENT:

Hash Table is a data structure which store data in associative manner. In hash table, data is stored
in array format where each data values has its own unique index value. Access of data becomes
very fast if we know the index of desired data.

Thus, it becomes a data structure in which insertion and search operations are very fast
irrespective of size of data. Hash Table uses array as a storage medium and uses
hash technique to generate index where an element is to be inserted or to be located
from.

Dept of CSE DSTAM 70

Data Structures Laboratory BCSL305

Hashing: Hashing is a technique to convert a range of key values into a range of indexes of an
array. We're going to use modulo operator to get a range of key values. Consider an example of
hashtable of size 20, and following items are to be stored. Item are in (key, value) format.

(1,20) (2,70) (42,80) (4,25) (12,44) (14,32)(17,11)(13,78)

(37,98)

S.n. Key Hash Array Index After Linear

Probing,
Array Index

1 1 1% 20 = 1 1 1
2 2 2% 20 = 2 2 2
3 42 42%20 = 2 2 3
4 4 4% 20 = 4 4 4
5 12 12%20 = 12 12 12
6 14 14%20 = 14 14 14
7 17 17%20 = 17 17 17
8 13 13%20 = 13 13 13
9 37 37%20 = 17 17 18

Basic Operations

Following are basic primary operations of a hashtable which are following.

 Search − search an element in a hashtable.

 Insert − insert an element in a hashtable.

 delete − delete an element from a hashtable.

DataItem

Define a data item having some data, and key based on which search is to be conducted in
hashtable.

struct DataItem
{

Dept of CSE DSTAM 71

Data Structures Laboratory BCSL305

int data;
int key;
};

Hash Method

Define a hashing method to compute the hash code of the key of the data item.

int hashCode(int key)

{
return key % SIZE;
}

ALGORITHM:
Step 1: Start.
Step 2: Given a File of N employee records with a set K of Keys (4-digit) which uniquely
determine the records in file F.
Step 3: 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.
Step 3: Let the keys in K and addresses in L are Integers
Step 4: Hash function H: K ®L as H(K)=K mod m (remainder method)
Step 5: Hashing as to map a given key K to the address space L, Resolve the collision (if
any) is using linear probing.
Step6: Stop.

PROGRAM CODE:

#include <stdio.h>
#include <stdlib.h>
#define MAX 10

struct employee
{
int id;
char name[15];
};

typedef struct employee EMP;

EMP emp[MAX];
int a[MAX];

int create(int num)

{
int key;
key = num % 10;
return key;
}

Dept of CSE DSTAM 72

Data Structures Laboratory BCSL305

int getemp(EMP emp[],int key)

{
printf("\nEnter emp id: ");
scanf("%d",&emp[key].id);
printf("\nEnter emp name: ");
flushall();
gets(emp[key].name);
return key;
}

void display()
{
int i, ch;
printf("\n1.Display ALL\n2.Filtered Display");
printf("\nEnter the choice: ");
scanf("%d",&ch);
if(ch == 1)
{
printf("\nThe hash table is:\n");
printf("\nHTKey\tEmpID\tEmpName");
for(i=0; i<MAX; i++)
printf("\n%d\t%d\t%s", i, emp[i].id, emp[i].name);
}

else
{
printf("\nThe hash table is:\n");
printf("\nHTKey\tEmpID\tEmpName");
for(i=0; i<MAX; i++)
if(a[i] != -1)
{
printf("\n%d\t%d\t%s", i, emp[i].id, emp[i].name);
continue;
}
}
}

void linear_prob(int key,int num)

{
int flag,i;//count=0;
flag=0;
for(i=key+1;i<=MAX;i++)
{
if(a[i]==-1)
{

Dept of CSE DSTAM 73

Data Structures Laboratory BCSL305

a[i]=getemp(emp,i);
flag=1;
break;
}
}
for(i=0;i<key&&flag==0;i++)
{
if(a[i]==-1)
{
a[i]=getemp(emp,i);
flag=1;
break;
}
}
if(!flag)
printf("hash tabl full:");
}

void main()
{
int num,key,i;
int ans=1;
clrscr();
printf("\nCollision handling by linear probing:");
for(i=0;i<MAX;i++)
{
a[i]=-1;
printf("%d",a[i]);
}
do
{
printf("\nEnter the data:\n");
scanf("%d",&num);
key=create(num);
if(a[key]==-1)
a[key]=getemp(emp,key);
else
{
printf("collision detected\n");
linear_prob(key,num);
}
printf("\nDo you wish to continue?(1/0): ");
scanf("%d",&ans);
}while(ans);
display();
getch();

Dept of CSE DSTAM 74

Data Structures Laboratory BCSL305

SAMPLE OUTPUT:

RUN1:
Enter the data: 2
Enter emp id: 100
Enter emp name: Anand
Do you wish to continue? (1/0):
1
Enter the data:
4
Enter emp id: 101
Enter emp name: Kumar
Do you wish to continue? (1/0):
0

1.Display ALL
2.Filtered Display
Enter the choice:
1
The hash table is:
EmpNa
HTKey EmpID me
0 0
1 0
2 100 Anand
3 0
4 101 Kumar
5 0
6 0
7 0
8 0
9 0
RUN2:
Enter the data: 2
Enter emp id: 100
Enter emp name: Anand
Do you wish to continue? (1/0):
1
Enter the data: 4
Enter emp id: 101
Enter emp name: Kumar
Do you wish to continue? (1/0):
0
1.Display ALL
2.Filtered Display
Enter the choice:
1
The hash table is:
HTKey EmpID EmpName

Dept of CSE DSTAM 75

Data Structures Laboratory BCSL305

2 100 Anand
4 101 Kumar

VIVA QUESTIONS AND ANSWERS

1) What is data structure?

Data structures refers to the way data is organized and manipulated. It seeks to find ways to
make data access more efficient. When dealing with data structure, we not only focus on one
piece of data, but rather different set of data and how they can relate to one another in an
organized manner.

2) Differentiate file structure from storage structure.

Basically, the key difference is the memory area that is being accessed. When dealing with the
structure that resides the main memory of the computer system, this is referred to as storage
structure. When dealing with an auxiliary structure, we refer to it as file structures.

3) When is a binary search best applied?

A binary search is an algorithm that is best applied to search a list when the elements are already
in order or sorted. The list is search starting in the middle, such that if that middle value is not the
target search key, it will check to see if it will continue the search on the lower half of the list or
the higher half. The split and search will then continue in the same manner.

4) What is a linked list?

A linked list is a sequence of nodes in which each node is connected to the node following it.
This forms a chain-like link of data storage.

Dept of CSE DSTAM 76

Data Structures Laboratory BCSL305

5) How do you reference all the elements in a one-dimension array?

To do this, an indexed loop is used, such that the counter runs from 0 to the array size minus one.
In this manner, we are able to reference all the elements in sequence by using the loop counter as
the array subscript.

6) In what areas do data structures applied?

Data structures is important in almost every aspect where data is involved. In general, algorithms
that involve efficient data structure is applied in the following areas: numerical analysis,
operating system, A.I., compiler design, database management, graphics, and statistical analysis,
to name a few.

7) What is LIFO?
LIFO is short for Last In First Out, and refers to how data is accessed, stored and retrieved.
Using this scheme, data that was stored last , should be the one to be extracted first. This also
means that in order to gain access to the first data, all the other data that was stored before this
first data must first be retrieved and extracted.

8 ) What is a queue?
A queue is a data structures that can simulates a list or stream of data. In this structure, new
elements are inserted at one end and existing elements are removed from the other end.

9) What are binary trees?

A binary tree is one type of data structure that has two nodes, a left node and a right node. In
programming, binary trees are actually an extension of the linked list structures.

10) Which data structures is applied when dealing with a recursive function?
Recursion, which is basically a function that calls itself based on a terminating condition, makes
use of the stack. Using LIFO, a call to a recursive function saves the return address so that it
knows how to return to the calling function after the call terminates.

11) What is a stack?

A stack is a data structure in which only the top element can be accessed. As data is stored in the
stack, each data is pushed downward, leaving the most recently added data on top.

12) Explain Binary Search Tree

A binary search tree stores data in such a way that they can be retrieved very efficiently. The left
subtree contains nodes whose keys are less than the node’s key value, while the right subtree
contains nodes whose keys are greater than or equal to the node’s key value. Moreover, both
subtrees are also binary search trees.

13) What are multidimensional arrays?

Multidimensional arrays make use of multiple indexes to store data. It is useful when storing
data that cannot be represented using a single dimensional indexing, such as data representation
in a board game, tables with data stored in more than one column.

Dept of CSE DSTAM 77

Data Structures Laboratory BCSL305

14) Are linked lists considered linear or non-linear data structures?

It actually depends on where you intend to apply linked lists. If you based it on storage, a linked
list is considered non-linear. On the other hand, if you based it on access strategies, then a linked
list is considered linear.

15) How does dynamic memory allocation help in managing data?

Aside from being able to store simple structured data types, dynamic memory allocation can
combine separately allocated structured blocks to form composite structures that expand and
contract as needed.

16) What is FIFO?

FIFO is short for First-in, First-out, and is used to represent how data is accessed in a queue.
Data has been inserted into the queue list the longest is the one that is removed first.

17) What is an ordered list?

An ordered list is a list in which each node’s position in the list is determined by the value of its
key component, so that the key values form an increasing sequence, as the list is traversed.

18) What is merge sort?

Merge sort takes a divide-and-conquer approach to sorting data. In a sequence of data, adjacent
ones are merged and sorted to create bigger sorted lists. These sorted lists are then merged again
to form an even bigger sorted list, which continuous until you have one single sorted list.

19) Differentiate NULL and VOID.

Null is actually a value, whereas Void is a data type identifier. A variable that is given a Null
value simply indicates an empty value. Void is used to identify pointers as having no initial size.

20) What is the primary advantage of a linked list?

A linked list is a very ideal data structure because it can be modified easily. This means that
modifying a linked list works regardless of how many elements are in the list.

21) What is the difference between a PUSH and a POP?

Pushing and popping applies to the way data is stored and retrieved in a stack. A push denotes
data being added to it, meaning data is being “pushed” into the stack. On the other hand, a pop
denotes data retrieval, and in particular refers to the topmost data being accessed.

22) What is a linear search?

A linear search refers to the way a target key is being searched in a sequential data structure.
Using this method, each element in the list is checked and compared against the target key, and
is repeated until found or if the end of the list has been reached.

23) How does variable declaration affect memory allocation?

The amount of memory to be allocated or reserved would depend on the data type of the variable
being declared. For example, if a variable is declared to be of integer type, then 32 bits of
memory storage will be reserved for that variable.

Dept of CSE DSTAM 78

Data Structures Laboratory BCSL305

24) What is the advantage of the heap over a stack?

Basically, the heap is more flexible than the stack. That’s because memory space for the heap
can be dynamically allocated and de-allocated as needed. However, memory of the heap can at
times be slower when compared to that stack.

25) What is a postfix expression?

A postfix expression is an expression in which each operator follows its operands. The advantage
of this form is that there is no need to group sub-expressions in parentheses or to consider
operator precedence.

26) Describe the data structures of a double-linked list.

(Solution: A double-linked list structure contains one pointer to the previous record in the list
and a pointer to the next record in the list plus the record data.)

27) How do you insert a record between two nodes in double-linked list?
(Solution: Previous R; Data R; Next R; To insert a record (B) between two others (A and C):
Previous.B = A; Next.B = C; Next.A = B; Previous.C = B;)

28) In which data structure, elements can be added or removed at either end, but not in the
middle?
(Solution: queue)

29) Which one is faster? A binary search of an orderd set of elements in an array or a sequential
search of the elements.
(Solution: binary search)

30) What is a balanced tree?

(Solution: A binary tree is balanced if the depth of two subtrees of every node never differ by
more than one)

31) Which data structure is needed to convert infix notations to post fix notations?
(Solution: stack)

32) What is data structure or how would you define data structure?
(Solution: In programming the term data structure refers to a scheme for organizing related piece
of information. Data Structure = Organized Data + Allowed Operations.)

33) Which data structures we can implement using link list?

(Solution: queue and stack)

34) List different types of data structures?

(Solution: Link list, queue, stack, trees, files, graphs)

Dept of CSE DSTAM 79