DATA STRUCTURE AND APPLICATION[BCS304]
AIM: 1A) 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). PROGRAM CODE:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct Day
{
char *dayName;
int d, m, y;
char *activityDescription;
};
void create(struct Day *calendar)
{
char *dayNames[] = {"Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday", "Sunday"};
for (int i = 0; i < 7; ++i)
{
calendar[i].dayName = strdup(dayNames[i]);
size_t bufferSize = 256;
calendar[i].activityDescription = (char*)malloc(bufferSize * sizeof(char));
}
}
void read(struct Day *calendar)
{
for (int i = 0; i < 7; ++i)
{
printf("Enter date for %s in dd/mm/yy:", calendar[i].dayName);
scanf("%d%d%d", &calendar[i].d, &calendar[i].m, &calendar[i].y);
printf("Enter activity for %s:", calendar[i].dayName);
while (getchar() != '\n');
size_t bufferSize = 256;
getline(&calendar[i].activityDescription, &bufferSize, stdin);
}
}
void display(struct Day *calendar)
{
printf("%-10s %-10s %-10s\n", "Day", "Date", "Activity");
for (int i = 0; i < 7; ++i)
printf("%-10s %d/%d/%d %-10s\n", calendar[i].dayName, calendar[i].d, calendar[i].m, calendar[i].y, calendar[i].activityDescription);
}
int main()
{
struct Day *calendar = (struct Day *)malloc(7 * sizeof(struct Day));
if (calendar == NULL)
{
fprintf(stderr, "Memory allocation failed\n");
return 1;
}
create(calendar);
read(calendar);
display(calendar);
for (int i = 0; i < 7; ++i)
{
free(calendar[i].dayName);
free(calendar[i].activityDescription);
}
free(calendar);
return 0;
}
Program 2:
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.
Code:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char STR[100], PAT[100], REP[100], ANS[100];
int i, j, c, m, k, flag = 0;
void read() {
printf("\nEnter the main string: \n");
scanf(" %[^\n]", STR);
printf("\nEnter the pattern string: \n");
scanf(" %[^\n]", PAT);
printf("\nEnter the replace string: \n");
scanf(" %[^\n]", REP);
}
void replace() {
i = m = c = j = 0;
while (STR[c] != '\0') {
if (STR[m] == PAT[i]) {
i++;
m++;
if (PAT[i] == '\0') {
for (k = 0; REP[k] != '\0'; k++, j++)
ANS[j] = REP[k];
i = 0;
c = m;
flag = 1;
}
} else {
ANS[j] = STR[c];
j++;
c++;
m = c;
i = 0;
}
}
if (flag == 0)
printf("Pattern is not found!!!\n");
else {
ANS[j] = '\0';
printf("\nThe resultant string is %s\n", ANS);
}
}
int main() {
read();
replace();
return 0;
}
Output:
Program 4:
Develop 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.
PROGRAM CODE:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int F (char symbol)
{
switch(symbol)
{
case '+':
case '-': return 2;
case '*':
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 '%':
case '/': return 3;
case '^':
case '$': return 6;
case '(': return 9;
case ')': return 0;
default: return 7;
}
}
void infix_postfix(char infix[], char postfix[])
{
int top, i, j;
char s[30];
char 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--];
if (F(s[top]) != G(symbol))
s[++top] = symbol;
else
top--;
}
while (s[top] != '#')
postfix[j++] = s[top--];
postfix[j] = '\0';
}
int main()
{
char infix[50];
char postfix[50];
printf("Enter a valid infix expression:\n");
fgets(infix, sizeof(infix), stdin);
infix_postfix(infix, postfix);
printf("The postfix expression is:\n");
printf("%s\n", postfix);
return 0;
}
Program 5:
A. Develop a program in c for the following stack
applications
a.
Evaluation
of suffix expression with single digit operands and operators: +, -, *, /, %, ^
Code:
#include <stdio.h>
#include <string.h>
#include <math.h>
int count = 0, top = -1;
int operate(char symb, int op1, int op2) {
switch (symb) {
case '+': return op1 + op2;
case '-': return op1 - op2;
case '/': return op1 / op2;
case '*': return op1 * op2;
case '%': return op1 % op2;
case '^': return (int)pow(op1, op2);
}
}
void push(int stack[], int d) {
stack[++top] = d;
}
int pop(int stack[]) {
return (stack[top--]);
}
void tower(int n, char src, char intr, char des) {
if (n) {
tower(n - 1, src, des, intr);
printf("disk %d moved from %c to %c\n", n, src, des);
count++;
tower(n - 1, intr, src, des);
}
}
int main() {
int n, choice, i, op1, op2, ans, stack[50];
char expr[20], symb;
while (1) {
printf("\nProgram to perform evaluation of suffix expression and Tower of Hanoi problem\n");
printf("\n1. Evaluate suffix expression\n2. Tower of Hanoi\n3. Exit\n");
printf("\nEnter the choice\n");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("Enter the suffix expression: ");
scanf("%s", expr);
for (i = 0; expr[i] != '\0'; i++) {
symb = expr[i];
if (symb >= '0' && symb <= '9')
push(stack, symb - '0');
else {
op2 = pop(stack);
op1 = pop(stack);
printf("Given expr is %d %d %c\n", op1, op2, symb);
ans = operate(symb, op1, op2);
push(stack, ans);
}
}
ans = pop(stack);
printf("The result of the suffix expression is %d\n", ans);
break;
case 2:
printf("Enter the number of disks: ");
scanf("%d", &n);
count = 0; // Reset count
tower(n, 'A', 'B', 'C');
printf("Number of moves taken to move disks from source to destination: %d\n", count);
break;
case 3:
return 0;
}
}
}
B. Solving Tower of Hanoi problem with n disks
CODE
#include <stdio.h>
#include <math.h>
void tower(int n, char source, char temp, char 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);
}
int main() {
int n;
printf("\nEnter the number of discs: ");
scanf("%d", &n);
tower(n, 'A', 'B', 'C');
printf("\n\nTotal Number of moves are: %d", (int)pow(2, n) - 1);
return 0;
}
Program 6:
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.
#include <stdio.h>
#include <stdlib.h>
#define max 5
int front = -1, rear = -1, count = 0;
char cq[max];
void cqinsert()
{
char ele;
if (count == max)
{
printf("Queue is full\n");
return;
}
printf("Enter the element to be inserted\n");
scanf(" %c", &ele);
rear = (rear + 1) % max;
cq[rear] = ele;
count++;
}
void cqdelete()
{
if (count == 0)
{
printf("Queue is empty\n");
return;
}
printf("Element deleted is = %c\n\n", cq[front]);
front = (front + 1) % max;
count--;
}
void cqdisplay()
{
int j = front, i;
if (count == 0)
{
printf("Queue is empty\n");
return;
}
printf("Circular Queue content is \n");
for (i = 0; i < count; i++)
{
printf("%c\t", cq[j]);
j = (j + 1) % max;
}
printf("\n\n");
}
int main()
{
int ch;
do
{
printf("1:Insert\t 2:Delete\t 3:Display\t 4:Exit\n");
printf("Enter your choice\n");
scanf("%d", &ch);
switch (ch)
{
case 1:
cqinsert();
break;
case 2:
cqdelete();
break;
case 3:
cqdisplay();
break;
case 4:
exit(0);
default:
printf("invalid choice\n");
break;
}
} while (1);
return 0;
}
Program 11:
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.
Code:
#include<stdio.h>
#include<stdlib.h>
void dfs(int src, int adj[10][10], int visited[10],
int n)
{
int k;
visited[src]=1;
printf("%d",src);
for(k=0;k<n;k++)
{
if(adj[src][k]==1 && visited[k]==0)
{
dfs(k,adj,visited,n);
}
}
}
void bfs(int src, int adj[10][10], int n)
{
int q[20], front=0, rear=-1, v, u, visited[10]={0};
q[++rear]=src;
visited[src]=1;
printf("%d",src);
while(front<=rear)
{
u=q[front++];
for(v=0;v<n;v++)
{
if(adj[u][v]==1 && visited[v]==0)
{
q[++rear]=v;
printf("%d",v);
visited[v]=1;
}
}
}
}
void main()
{
int choice, i, j, src, flag=0;
int adj[10][10], visited[10]={0}, n;
while(1)
{
printf("\n\n\t program to perform graph
operations\n\n");
printf("\n\t 1=> Create a graph of N
cities\n\t");
printf("\n\t 2=> To print reachable nodes from
source using BFS\n");
printf("\n\t 3=> To check graph connected or
not using DFS\n\n");
printf("\n\t 4=> Exit\n");
printf("\n Enter the choice\n");
scanf("%d",&choice);
switch(choice)
{
case 1:printf("\nenter the number of
cities\n");
scanf("%d",&n);
printf("\nenter the adjacency matrix\n");
for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&adj[i][j]);
break;
case 2:printf("Enter the source vertex to start
traversal\n");
scanf("%d",&src);
printf("vertices visited are\n");
bfs(src,adj,n);
break;
case 3:printf("Enter the source vertex to start
traversal\n");
scanf("%d",&src);
for(i=0;i<n;i++)
visited[i]=0;
dfs(src,adj,visited,n);
for(i=0;i<n;i++)
if(visited[i]==0)
flag=1;
if(flag==1)
printf("the graph is not connected\n");
else
printf("the graph is connected\n");
break;
case 4:return;
}
}
}
Program 12:
Given a file of N employee records with a set of 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.
Code:
#include<stdio.h>
#define m 10
void store(int key, int hk);
void display();
int HT[100];
int main()
{
int key;
int hk;
int ch,i;
for(i=0;i<m;i++)
HT[i]=-1;
for(;;)
{
printf("\n 1.Insert Key 2.Display 3.Exit \n");
printf("Choice: ");
scanf("%d",&ch);
switch(ch)
{
case 1:printf("Enter key: ");
scanf("%4d",&key);
hk=key%m;
store(key,hk);
break;
case 2:display();
break;
default:printf("\n Thank you");
return 0;
}
}
}
void store(int key, int hk)
{
int i;
int pos=-1;
int flag=0;
if(HT[hk]==-1)
{
HT[hk]=key;
return;
}
for(i=hk+1;i<m;i++)
{
if(HT[i]==-1)
{
pos=i;
flag=1;
break;
}
}
if(flag==0)
{
for(i=0;i<hk;i++)
{
if(HT[i]==-1)
{
pos=i;
flag=1;
break;
}
}
}
if(flag==0)
printf("Hash Table Overflow.\n\n");
else
HT[pos]=key;
}
void display()
{
int i;
printf("\nHash Table:\n");
for(i=0;i<m;i++)
{
printf("%2d|%4d|\n",i, HT[i]);
}
}
Comments
Post a Comment