ASSIGNMENT QUESTIONS ON DS WITH ANSWERS
DAY-2
STACK:
1. Infix to prefix implementation in c : with Pointer
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <ctype.h>
#define MAX 50
struct infix
{
char target[MAX] ;
char stack[MAX] ;
char *s, *t ;
int top, l ;
} ;
void initinfix ( struct infix * ) ;
void setexpr ( struct infix *, char * ) ;
void push ( struct infix *, char ) ;
char pop ( struct infix * ) ;
void convert ( struct infix * ) ;
int priority ( char c ) ;
void show ( struct infix ) ;
void main( )
{
struct infix q ;
char expr[MAX] ;
clrscr( ) ;
initinfix ( &q ) ;
printf ( "\nEnter an expression in infix form: " ) ;
gets ( expr ) ;
setexpr ( &q, expr ) ;
convert ( &q ) ;
printf ( "The Prefix expression is: " ) ;
show ( q ) ;
getch( ) ;
}
/* initializes elements of structure variable */
void initinfix ( struct infix *pq )
{
pq -> top = -1 ;
strcpy ( pq -> target, "" ) ;
strcpy ( pq -> stack, "" ) ;
pq -> l = 0 ;
}
/* reverses the given expression */
void setexpr ( struct infix *pq, char *str )
{
pq -> s = str ;
strrev ( pq -> s ) ;
pq -> l = strlen ( pq -> s ) ;
*( pq -> target + pq -> l ) = '\0' ;
pq -> t = pq -> target + ( pq -> l - 1 ) ;
}
/* adds operator to the stack */
void push ( struct infix *pq, char c )
{
if ( pq -> top == MAX - 1 )
printf ( "\nStack is full.\n" ) ;
else
{
pq -> top++ ;
pq -> stack[pq -> top] = c ;
}
}
/* pops an operator from the stack */
char pop ( struct infix *pq )
{
if ( pq -> top == -1 )
{
printf ( "Stack is empty\n" ) ;
return -1 ;
}
else
{
char item = pq -> stack[pq -> top] ;
pq -> top-- ;
return item ;
}
}
/* converts the infix expr. to prefix form */
void convert ( struct infix *pq )
{
char opr ;
while ( *( pq -> s ) )
{
if ( *( pq -> s ) == ' ' || *( pq -> s ) == '\t' )
{
pq -> s++ ;
continue ;
}
if ( isdigit ( *( pq -> s ) ) || isalpha ( *( pq -> s ) ) )
{
while ( isdigit ( *( pq -> s ) ) || isalpha ( *( pq -> s ) ) )
{
*( pq -> t ) = *( pq -> s ) ;
pq -> s++ ;
pq -> t-- ;
}
}
if ( *( pq -> s ) == ')' )
{
push ( pq, *( pq -> s ) ) ;
pq -> s++ ;
}
if ( *( pq -> s ) == '*' || *( pq -> s ) == '+' || *( pq -> s ) == '/' || *( pq -> s ) == '%' || *( pq -> s ) == '-' || *( pq -> s ) == '$' )
{
if ( pq -> top != -1 )
{
opr = pop ( pq ) ;
while ( priority ( opr ) > priority ( *( pq -> s ) ) )
{
*( pq -> t ) = opr ;
pq -> t-- ;
opr = pop ( pq ) ;
}
push ( pq, opr ) ;
push ( pq, *( pq -> s ) ) ;
}
else
push ( pq, *( pq -> s ) ) ;
pq -> s++ ;
}
if ( *( pq -> s ) == '(' )
{
opr = pop ( pq ) ;
while ( opr != ')' )
{
*( pq -> t ) = opr ;
pq -> t-- ;
opr = pop ( pq ) ;
}
pq -> s++ ;
}
}
while ( pq -> top != -1 )
{
opr = pop ( pq ) ;
*( pq -> t ) = opr ;
pq -> t-- ;
}
pq -> t++ ;
}
/* returns the priotity of the operator */
int priority ( char c )
{
if ( c == '$' )
return 3 ;
if ( c == '*' || c == '/' || c == '%' )
return 2 ;
else
{
if ( c == '+' || c == '-' )
return 1 ;
else
return 0 ;
}
}
/* displays the prefix form of given expr. */
void show ( struct infix pq )
{
while ( *( pq.t ) )
{
printf ( " %c", *( pq.t ) ) ;
pq.t++ ;
}
}
2. Infix to prefix implementation in c : without Pointer
#include<stdio.h>
#include<conio.h>
#include<string.h>
//Stack precedence function
int F(char symbol)
{
switch(symbol)
{
case '+' :
case '-' :
return 1;
case '*':
case '^':
return 6;
case ')':
return 0;
case '#':
return -1;
default:
return 8;
}
}
//Input precedence function
int G(char symbol)
{
switch(symbol)
{
case '+' :
case '-':
return 2;
case '*':
return 4;
case '^':
return 5;
case '(':
return 0;
case ')':
return 9;
case '#':
return -1;
default:
return 7;
}
}
void infix_prefix(char infix[], char prefix[])
{
int top, j, i;
char symbol, s[40];
top = -1;
s[++top] = '#';
j = 0;
strrev(infix);
for(i = 0;i < strlen(infix); i++)
{
symbol= infix[i];
while(F(s[top]) > G(symbol))
{
prefix[j] = s[top--];
j++;
}
if(F(s[top]) != G(symbol))
s[++top] = symbol;
else
top--;
}
while(s[top] != '#')
{
prefix[j++] = s[top--];
}
prefix[j] = '\0';
strrev(prefix);
}
void main()
{
char infix[20];
char prefix[20];
printf("/nEnter a valid infix expression\n");
scanf("%s",infix);
infix_prefix(infix, prefix);
printf("\n\nThe prefix expression is\n");
printf("%s\n",prefix);
}
3. Postfix to Infix implementation in c
#include <stdio.h>
#include <stdlib.h>
int top = 10;
struct node
{
char ch;
struct node *next;
struct node *prev;
} *stack[11];
typedef struct node node;
void push(node *str)
{
if (top <= 0)
printf("Stack is Full ");
else
{
stack[top] = str;
top--;
}
}
node *pop()
{
node *exp;
if (top >= 10)
printf("Stack is Empty ");
else
exp = stack[++top];
return exp;
}
void convert(char exp[])
{
node *op1, *op2;
node *temp;
int i;
for (i=0;exp[i]!='\0';i++)
if (exp[i] >= 'a'&& exp[i] <= 'z'|| exp[i] >= 'A' && exp[i] <= 'Z')
{
temp = (node*)malloc(sizeof(node));
temp->ch = exp[i];
temp->next = NULL;
temp->prev = NULL;
push(temp);
}
else if (exp[i] == '+' || exp[i] == '-' || exp[i] == '*' || exp[i] == '/' ||
exp[i] == '^')
{
op1 = pop();
op2 = pop();
temp = (node*)malloc(sizeof(node));
temp->ch = exp[i];
temp->next = op1;
temp->prev = op2;
push(temp);
}
}
void display(node *temp)
{
if (temp != NULL)
{
display(temp->prev);
printf("%c", temp->ch);
display(temp->next);
}
}
void main()
{
char exp[50];
clrscr();
printf("Enter the postfix expression :");
scanf("%s", exp);
convert(exp);
printf("\nThe Equivalant Infix expression is:");
display(pop());
printf("\n\n");
getch();
}
QUEUE:
1.C Program for String insertion and deletion over queue
# include < stdio.h >
# include < conio.h >
# include < string.h >
# define max 5
void main()
{
char queue[max][80], data[80];
int front, rear, reply, option;
clrscr();
//... Initialise a Queue
front = rear = -1;
do
{
printf("\n C Language program to implement the basic operations on String Queue \n");
printf("\n 1. Insert String in a Queue");
printf("\n 2. Delete String from a Queue");
printf("\n 3. Exit");
printf("\n Select proper option ( 1 / 2 / 3 ) : ");
scanf("%d", &option);
switch(option)
{
case 1 : // insert
printf("\n Enter the String to be insert in a Queue : ");
flushall();
gets(data);
reply = insq(queue, &rear, data);
if( reply == -1 )
printf("\n Queue is Full \n");
else
printf("\n Entered String is Inserted in a Queue \n");
break;
case 2 : // delete
reply = delq(queue, &front, &rear, data);
if( reply == -1 )
printf("\n Queue is Empty \n");
else
printf("\n Deleted String from Queue is : %s", data);
printf("\n");
break;
case 3 : exit(0);
} // switch
}while(1);
} // main
int insq(char queue[max][80], int *rear, char data[80])
{
if(*rear == max -1)
return(-1);
else
{
*rear = *rear + 1;
strcpy(queue[*rear], data);
return(1);
} // else
} // insq
int delq(char queue[max][80], int *front, int *rear, char data[80])
{
if(*front == *rear)
return(-1);
else
{
(*front)++;
strcpy(data, queue[*front]);
return(1);
} // else
} // delq
2. C Program for Insertion and deletion over multiple queue
# include < stdio.h >
# include < conio.h >
# define max 20
void main()
{
int queue[max], data;
int bott[10], limit[10], f[10], r[10];
int i, n, qno, size, option, reply;
clrscr();
printf("\n C Language program to implement the Multiple Queues \n");
printf("\n How Many Queues ? : ");
scanf("%d", &n);
size = max / n; //... Get Max. size for each Queue
//... Initialize bottom for each Queue
bott[0] = -1; //... Bottom of first Queue is -1
for(i = 1; i < n; i++)
bott[i] = bott[i-1] + size;
//... Initialize Limit of each Queue
for(i = 0; i < n; i++) //... Limit of i'th Queue is equal to bottom of i'th Queue + Size
limit[i] = bott[i] + size;
//... Initialize Front & Rear of each Queue
//... Initial value of Front & Rear of each Queue is same as its Bottom Value
for(i = 0; i < n; i++)
f[i] = r[i] = bott[i];
//... Process the Queues
do
{
printf("\n C Language program to implement the Multiple Queues \n");
printf("\n 1. Insert in a Queue");
printf("\n 2. Delete from a Queue");
printf("\n 3. Exit \n");
printf("\n Select proper option ( 1 / 2 / 3 ) : ");
scanf("%d", &option);
switch(option)
{
case 1 : //... Insert
printf("\n Enter a Logical Queue Number (0 to %d) : ", n-1);
scanf("%d", &qno);
printf("\n Enter Data : ");
scanf("%d", &data);
reply = insq(queue, qno, r, limit, &data);
if( reply == -1)
printf("\n Queue %d is Full \n", qno);
else
printf("\n %d is inserted in a Queue No. %d \n", data, qno);
break;
case 2 : //... Delete
printf("\n Enter a Logical Queue Number (0 to %d) : ", n-1);
scanf("%d", &qno);
reply = delq(queue, qno, f, r, &data);
if( reply == -1)
printf("\n Queue %d is Empty \n", qno);
else
printf("\n %d is deleted from Queue No. %d \n", data, qno);
break;
case 3 : exit(0);
} // switch
}while(1);
} // main
int insq( int queue[max], int qno, int rear[], int limit[], int *data )
{
if( rear[qno] == limit[qno] )
return(-1);
else
{
rear[qno]++; //... rear[qno] = rear[qno] + 1;
queue[ rear[qno] ] = *data;
return(1);
} // else
} // insq
int delq( int queue[max], int qno, int front[], int rear[], int *data)
{
if( front[qno] == rear[qno] )
return(-1);
else
{
front[qno]++; //... front[qno] = front[qno] + 1;
*data = queue[ front[qno] ];
return(1);
} // else
} // delq
3. C Program for Insertion and deletion over circular queue
# include < stdio.h >
# include < conio.h >
# define max 10
void main()
{
int cqueue[max], data;
int front, rear, reply, option;
clrscr();
//... Initialise Circular Queue
front = rear = 0;
do
{
printf("\n C Language program to implement basic operations on a Circular Queue \n");
printf("\n 1. Insert number in a Circular Queue");
printf("\n 2 .Delete number from Circular Queue");
printf("\n 3. Exit \n");
printf("\n Select proper option ( 1 / 2 / 3 ) : ");
scanf("%d", &option);
switch(option)
{
case 1 : // insert
printf("\n Enter number: ");
scanf("%d", &data);
reply = insq(cqueue, &front, &rear, &data);
if(reply == -1)
printf("\n Circular Queue is Full \n");
else
printf("\n Number %d is inserted in a Circular Queue \n", data);
break;
case 2 : // delete
reply = delq(cqueue, &front, &rear,&data);
if(reply == -1)
printf("\n Circular Queue is Empty \n");
else
printf("\n %d is deleted from Circular Queue \n", data);
printf("\n");
break;
case 3 : exit(0);
} // switch
}while(1);
} // main
int insq(int cqueue[max], int *front, int *rear, int *data)
{
if((*rear + 1) % max == *front)
return(-1);
else
{
*rear = (*rear + 1) % max;
cqueue[*rear] = *data;
return(1);
} // else
} // insq
int delq(int cqueue[max], int *front, int *rear, int *data)
{
if(*front == *rear)
return(-1);
else
{
*front = (*front + 1) % max;
*data = cqueue[*front];
return(1);
} // else
} // delq
DAY-3
Linked list :
1.Count the number of nodes in a link list using C
#include <stdio.h>
#include <conio.h>
#include <alloc.h>
struct linklist
{
int number;
struct linklist *next;
};
typedef struct linklist node;
void create(node *);
void count(node *);
node *head;
void main()
{
clrscr();
head=(node *) malloc(sizeof(node));
create(head);
printf("\n");
count(head);
getch();
}
void create(node *list)
{
char conf='y';
int i;
printf("\nENTER A NUMBER: ");
scanf("%d",&list->number);
printf("\nWANT TO CONTINUE[Y/N]: ");
conf=getche();
printf("\n");
if(conf=='n' || conf=='N')
list->next=NULL;
else
{
list->next=(node *) malloc(sizeof(node));
create(list->next);
}
}
void count(node *first)
{
int i=0;
while(first!=NULL)
{
first=first->next;
i++;
}
printf("THERE ARE %d NODES IN THE LINK LIST",i);
}
2. C program for Searching in Linked List
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct node
{
int data;
struct node *next;
}
first, *nw;
int search(int);
void main()
{
int no,i,item,pos;
clrscr();
first.next=NULL;
nw=&first;
printf("Enter The No of nodes, you want in linked list: ");
scanf("%d",&no);
printf("\n");
for(i=0;i< no;i++)
{
nw->next=(struct node *)malloc(sizeof(struct node));
printf("Enter element in node %d: ",i+1);
scanf("%d",&nw->data);
nw=nw->next;
}
nw->next=NULL;
printf("Linked list is:\n");
nw=&first;
while(nw->next!=NULL)
{
printf("%d\t",nw->data);
nw=nw->next;
}
printf("\n");
printf("Enter item to be searched : ");
scanf("%d",&item);
pos=search(item);
if(pos<=no)
printf("Your item is at node=%d",pos);
else
printf("Sorry! your item is not in linked list.");
getch();
}
int search(int item)
{
int count=1;
nw=&first;
while(nw->next!=NULL)
{
if(nw->data==item)
break;
else
count++;
nw=nw->next;
}
return count;
}
3. C program for Sorting in Linked List
#include <stdio.h>
#include <conio.h>
#include <malloc.h>
struct node
{
int data;
struct node *next;
};
void main()
{
int i;
int num ;
struct node *first, *nw, *pre, *new1, *count;
clrscr();
printf("\n Enter the number of node you want to create: ");
scanf("%d", &num );
first->next = NULL;
nw = first;
for (i = 0; i < num ; i++)
{
nw->next = (struct node* ) malloc(sizeof(struct node));
nw = nw->next;
printf("\n Enter the node: %d: ", i+1);
scanf("%d", &nw->data);
nw->next = NULL;
}
new1 = first;
for( ; new1->next != NULL; new1 = new1->next)
{
for(count = new1->next; count != NULL; count = count->next)
{
if(new1->data > count->data)
{
int temp = new1->data;
new1->data = count->data;
count->data = temp;
}
}
}
nw = first->next;
printf("\n After sorting the Linked list is as follows:\n");
while (nw)
{
printf("%d\t", nw->data);
nw = nw->next;
}
getch();
}
DAY-4
Doubly linked list:
1.Program To Sort A Doubly Linked List (in C):
#include<stdio.h>
#include<stdlib.h>
struct dllNode {
int data;
struct dllNode *previous, *next;
};
struct dllNode *head = NULL;
static int totNodes = 0;
struct dllNode *createNode(int);
void insertNode(int);
void deleteNode(int);
void insertionSort();
void traverseList();
/* creating a new node */
struct dllNode* createNode(int data) {
struct dllNode *nPtr = (struct dllNode *)malloc(sizeof (struct dllNode));
nPtr->data = data;
nPtr->previous = NULL;
nPtr->next = NULL;
return (nPtr);
}
/* Insert a newnode at the end of the list */
void insertNode(int data) {
struct dllNode *tmp, *nPtr = createNode(data);
if (!head) {
head = nPtr;
totNodes++;
return;
} else {
tmp = head;
while (tmp) {
if (tmp->next == NULL) {
tmp->next = nPtr;
nPtr->previous = tmp;
totNodes++;
return;
}
tmp=tmp->next;
}
}
}
/* delete the node with given data */
void deleteNode(int data) {
struct dllNode *nPtr, *tmp = head;
if (head == NULL) {
printf(“Data unavailable\n”);
return;
} else if (tmp->data == data) {
nPtr = tmp->next;
tmp->next = NULL;
free(tmp);
head = nPtr;
totNodes--;
} else {
while (tmp->next != NULL && tmp->data != data) {
nPtr = tmp;
tmp = tmp->next;
}
if (tmp->next == NULL && tmp->data != data) {
printf(“Given data unvavailable in list\n”);
return;
} else if (tmp->next != NULL && tmp->data == data) {
nPtr->next = tmp->next;
tmp->next->previous = tmp->previous;
tmp->next = NULL;
tmp->previous = NULL;
free(tmp);
printf(“Data deleted successfully\n”);
totNodes--;
} else if (tmp->next == NULL && tmp->data == data) {
nPtr->next = NULL;
tmp->next = tmp->previous = NULL;
free(tmp);
printf(“Data deleted successfully\n”);
totNodes--;
}
}
}
/* sort the given list – insertNode sort*/
void insertionSort() {
struct dllNode *nPtr1, *nPtr2;
int i, j, tmp;
nPtr1 = nPtr2 = head;
for (i = 0; i < totNodes; i++) {
tmp = nPtr1->data;
for (j = 0; j < i; j++)
nPtr2 = nPtr2->next;
for (j = i; j > 0 && nPtr2->previous->data < tmp; j--) {
nPtr2->data = nPtr2->previous->data;
nPtr2 = nPtr2->previous;
}
nPtr2->data = tmp;
nPtr2 = head;
nPtr1 = nPtr1->next;
}
}
/* traverse the doubly linked list and print data in each node */
void traverseList() {
struct dllNode *nPtr = head;
int i = 0;
while (nPtr) {
printf(“%d “, nPtr->data);
nPtr = nPtr->next;
i++;
}
}
int main() {
int ch, data;
while (1) {
printf(“1.Insertion\t2.Delete Operation\n”);
printf(“3.Sort List\t4.Display\t”);
printf(“5.Exit\nEnter ur choice:”);
scanf(“%d”, &ch);
switch (ch) {
case 1:
printf(“Enter data to insert:”);
scanf(“%d”, &data);
insertNode(data);
break;
case 2:
printf(“Enter data to delete:”);
scanf(“%d”, &data);
deleteNode(data);
break;
case 3:
insertionSort();
break;
case 4:
traverseList();
printf(“\n”);
break;
case 5:
exit(0);
default:
printf(“Wrong Option!!\n”);
break;
}
}
2. Program to create Doubly Linked List in C
#include <stdio.h>
#include <conio.h>
#include <alloc.h>
struct linklist
{
struct linklist *prev;
int num;
struct linklist *next;
};
typedef struct linklist node;
void create(node *);
void display(node *);
void main()
{
node *head;
clrscr();
head=(node *) malloc(sizeof(node));
head->prev=NULL;
create(head);
printf(“\n”);
display(head);
getch();
}
void create(node *list)
{
char conf=’y’;
int i;
printf(“\Nenter A NUMBER: “);
scanf(“%d”,&list->num);
list->next->prev=list;
printf(“\Nwant TO CONTINUE[Y/N]: “);
conf=getche();
printf(“\n”);
if(conf==’n’ || conf==’N’)
list->next=NULL;
else
{
list->next=(node *) malloc(sizeof(node));
create(list->next);
}
}
void display(node *disp)
{
printf(“THE ADDRESS-PREVIOUS ADDRESS-VALUE-NEXT ADDRESS OF THE LINK LIST ARE:\n”);
while(disp!=NULL)
{
printf(“%u-%u-%u-%u\n”,disp,disp->prev,disp->num,disp->next);
disp=disp->next;
}
}
DAY-5
SORTING:
1. C Program to Sort the N Names in an Alphabetical Order
#include <stdio.h>
#include <string.h>
void main()
{
char name[10][8], tname[10][8], temp[8];
int i, j, n;
printf("Enter the value of n \n");
scanf("%d", &n);
printf("Enter %d names n", \n);
for (i = 0; i < n; i++)
{
scanf("%s", name[i]);
strcpy(tname[i], name[i]);
}
for (i = 0; i < n - 1 ; i++)
{
for (j = i + 1; j < n; j++)
{
if (strcmp(name[i], name[j]) > 0)
{
strcpy(temp, name[i]);
strcpy(name[i], name[j]);
strcpy(name[j], temp);
}
}
}
printf("\n----------------------------------------\n");
printf("Input NamestSorted names\n");
printf("------------------------------------------\n");
for (i = 0; i < n; i++)
{
printf("%s\t\t%s\n", tname[i], name[i]);
}
printf("------------------------------------------\n");
}
2. C Program to Implement Selection Sort Recursively
#include <stdio.h>
void selection(int [], int, int, int, int);
int main()
{
int list[30], size, temp, i, j;
printf("Enter the size of the list: ");
scanf("%d", &size);
printf("Enter the elements in list:\n");
for (i = 0; i < size; i++)
{
scanf("%d", &list[i]);
}
selection(list, 0, 0, size, 1);
printf("The sorted list in ascending order is\n");
for (i = 0; i < size; i++)
{
printf("%d ", list[i]);
}
return 0;
}
void selection(int list[], int i, int j, int size, int flag)
{
int temp;
if (i < size - 1)
{
if (flag)
{
j = i + 1;
}
if (j < size)
{
if (list[i] > list[j])
{
temp = list[i];
list[i] = list[j];
list[j] = temp;
}
selection(list, i, j + 1, size, 0);
}
selection(list, i + 1, 0, size, 1);
}
}
3. C Program to Perform Quick Sort on a set of Entries from a File using Recursion
#include <stdio.h>
void quicksort (int [], int, int);
int main()
{
int list[50];
int size, i;
printf("Enter the number of elements: ");
scanf("%d", &size);
printf("Enter the elements to be sorted:\n");
for (i = 0; i < size; i++)
{
scanf("%d", &list[i]);
}
quicksort(list, 0, size - 1);
printf("After applying quick sort\n");
for (i = 0; i < size; i++)
{
printf("%d ", list[i]);
}
printf("\n");
return 0;
}
void quicksort(int list[], int low, int high)
{
int pivot, i, j, temp;
if (low < high)
{
pivot = low;
i = low;
j = high;
while (i < j)
{
while (list[i] <= list[pivot] && i <= high)
{
i++;
}
while (list[j] > list[pivot] && j >= low)
{
j--;
}
if (i < j)
{
temp = list[i];
list[i] = list[j];
list[j] = temp;
}
}
temp = list[j];
list[j] = list[pivot];
list[pivot] = temp;
quicksort(list, low, j - 1);
quicksort(list, j + 1, high);
}
}
DAY-6
SEARCHING:
#include <stdio.h>
#include <conio.h>
#include <alloc.h>
void main()
{
int n,*p,i,num,flag=0;
clrscr();
printf("\nHOW MANY NUMBER: ");
scanf("%d",&n);
p=(int *) malloc(n*2);
if(p==NULL)
{
printf("\nMEMORY ALLOCATION UNSUCCESSFUL");
exit();
}
for(i=0;i<n;i++)
{
printf("\nENTER NUMBER %d: ",i+1);
scanf("%d",p+i);
}
printf("\nENTER A NUMBER TO SEARCH: ");
scanf("%d",&num);
for(i=0;i<n;i++)
{
if(num==*(p+i))
flag=1;
}
if(flag==1)
printf("\nTHE NUMBER %d IS FOUND",num);
else
printf("\nTHE NUMBER %d DOES NOT EXIST",num);
getch();
}
#include <stdio.h>
void binary_search(int [], int, int, int);
void bubble_sort(int [], int);
int main()
{
int key, size, i;
int list[25];
printf("Enter size of a list: ");
scanf("%d", &size);
printf("Generating random numbers\n");
for(i = 0; i < size; i++)
{
list[i] = rand() % 100;
printf("%d ", list[i]);
}
bubble_sort(list, size);
printf("\n\n");
printf("Enter key to search\n");
scanf("%d", &key);
binary_search(list, 0, size, key);
}
void bubble_sort(int list[], int size)
{
int temp, i, j;
for (i = 0; i < size; i++)
{
for (j = i; j < size; j++)
{
if (list[i] > list[j])
{
temp = list[i];
list[i] = list[j];
list[j] = temp;
}
}
}
}
void binary_search(int list[], int lo, int hi, int key)
{
int mid;
if (lo > hi)
{
printf("Key not found\n");
return;
}
mid = (lo + hi) / 2;
if (list[mid] == key)
{
printf("Key found\n");
}
else if (list[mid] > key)
{
binary_search(list, lo, mid - 1, key);
}
else if (list[mid] < key)
{
binary_search(list, mid + 1, hi, key);
}
}}
DAY-7
TREE:
#include <stdio.h>
#include <stdlib.h>
struct btnode {
int value;
struct btnode *l;
struct btnode *r;
}
*root = NULL;
typedef struct btnode N;
N* new(int);
void create();
void preorder(N *t);
void min_max(N *t);
void main() {
int choice;
create();
while (1) {
printf("Enter the choice\n");
printf("1-Display : 2-Min & Max element : 3-Exit\n");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("preorder preorder of tree elements\n");
preorder(root);
printf("\n");
break;
case 2:
min_max(root);
break;
case 3:
exit(0);
default:
printf("Enter the right choice\n");
}
}
}
/* creating temporary node */
N* new(int data) {
N* temp = (N*)malloc(sizeof(N));
temp->value = data;
temp->l = NULL;
temp->r = NULL;
return(temp);
}
/* Creating the binary search tree */
void create() {
root = new(40);
root->l = new(20);
root->r = new(60);
root->l->l = new(10);
root->l->r = new(30);
root->r->r = new(80);
root->r->r->r = new(90);
}
/* To display preorder traversal of the tree */
void preorder(N *temp) {
printf("%d->", temp->value);
if (temp->l != NULL)
preorder(temp->l);
if (temp->r != NULL)
preorder(temp->r);
}
/* TO find the minimum and maximum values in the given tree */
void min_max(N *temp) {
while (temp->l != NULL)
temp = temp->l;
printf("Minimum value = %d\n", temp->value);
temp = root;
while (temp->r != NULL)
temp = temp->r;
printf("Maximum value = %d\n", temp->value);
}
2. WAP to Implement Binary Tree using Linked List
#include <stdio.h>
#include <malloc.h>
struct node {
struct node * left;
char data;
struct node * right;
}
;
struct node *constructTree( int );
void inorder(struct node *);
char array[ ] = {
'A', 'B', 'C', 'D', 'E', 'F', 'G', '', '', 'H'
}
;
int leftcount[ ] = {
1, 3, 5, -1, 9, -1, -1, -1, -1, -1
}
;
int rightcount[ ] = {
2, 4, 6, -1, -1, -1, -1, -1, -1, -1
}
;
void main() {
struct node *root;
root = constructTree( 0 );
printf("In-order Traversal: \n");
inorder(root);
}
struct node * constructTree( int index ) {
struct node *temp = NULL;
if (index != -1) {
temp = (struct node *)malloc( sizeof ( struct node ) );
temp->left = constructTree( leftcount[index] );
temp->data = array[index];
temp->right = constructTree( rightcount[index] );
}
return temp;
}
void inorder( struct node *root ) {
if (root != NULL) {
inorder(root->left);
printf("%c\t", root->data);
inorder(root->right);
}
}
3. WAP for Depth First Binary Tree Search using Recursion
#include <stdio.h>
#include <stdlib.h>
struct node {
int a;
struct node *left;
struct node *right;
}
;
void generate(struct node **, int);
void DFS(struct node *);
void delete(struct node **);
int main() {
struct node *head = NULL;
int choice = 0, num, flag = 0, key;
do {
printf("\nEnter your choice:\n1. Insert\n2. Perform DFS Traversal\n3. Exit\nChoice: ");
scanf("%d", &choice);
switch(choice) {
case 1:
printf("Enter element to insert: ");
scanf("%d", &num);
generate(&head, num);
break;
case 2:
DFS(head);
break;
case 3:
delete(&head);
printf("Memory Cleared\nPROGRAM TERMINATED\n");
break;
default:
printf("Not a valid input, try again\n");
}
}
while (choice != 3);
return 0;
}
void generate(struct node **head, int num) {
struct node *temp = *head, *prev = *head;
if (*head == NULL) {
*head = (struct node *)malloc(sizeof(struct node));
(*head)->a = num;
(*head)->left = (*head)->right = NULL;
} else {
while (temp != NULL) {
if (num > temp->a) {
prev = temp;
temp = temp->right;
} else {
prev = temp;
temp = temp->left;
}
}
temp = (struct node *)malloc(sizeof(struct node));
temp->a = num;
if (num >= prev->a) {
prev->right = temp;
} else {
prev->left = temp;
}
}
}
void DFS(struct node *head) {
if (head) {
if (head->left) {
DFS(head->left);
}
if (head->right) {
DFS(head->right);
}
printf("%d ", head->a);
}
}
void delete(struct node **head) {
if (*head != NULL) {
if ((*head)->left) {
delete(&(*head)->left);
}
if ((*head)->right) {
delete(&(*head)->right);
}
free(*head);
}
}