//Program Name: Slip 1 BinarySearch.c #include<stdio.h>
int main()
{
int c, first, last, middle, n, search, array[100];
printf("Enter number of elements\n");
scanf("%d",&n);
printf("Enter %d integers\n", n);
for ( c = 0 ; c < n ; c++ )
scanf("%d",&array[c]);
printf("Enter value to find\n");
scanf("%d",&search);
first = 0;
last = n - 1;
middle = (first+last)/2;
while( first <= last )
{
if ( array[middle] < search )
first = middle + 1;
else if ( array[middle] == search )
{
printf("%d found at location %d.\n", search, middle+1);
break;
}
else
last = middle - 1;
middle = (first + last)/2;
}
if ( first > last )
printf("Not found! %d is not present in the list.\n", search);
return 0;
}
#include<stdio.h>
int stack[100],choice,n,top,x,i;
void push(void);
void pop(void);
void display(void);
int main()
{
top=-1;
printf("\n Enter the size of STACK[MAX=100]:");
scanf("%d",&n);
printf("\n\t STACK OPERATIONS USING ARRAY");
printf("\n\t--------------------------------");
printf("\n\t 1.PUSH\n\t 2.POP\n\t 3.DISPLAY\n\t 4.EXIT");
do
{
printf("\n Enter the Choice:");
scanf("%d",&choice);
switch(choice)
{
case 1:
{
push();
break;
}
case 2:
{
pop();
break;
}
case 3:
{
display();
break;
}
case 4:
{
printf("\n\t EXIT POINT ");
break;
}
default:
{
printf ("\n\t Please Enter a Valid Choice(1/2/3/4)");
}
}
}
while(choice!=4);
return 0;
}
void push()
{
if(top>=n-1)
{
printf("\n\tSTACK is over flow");
}
else
{
printf(" Enter a value to be pushed:");
scanf("%d",&x);
top++;
stack[top]=x;
}
}
void pop()
{
if(top<=-1)
{
printf("\n\t Stack is under flow");
}
else
{
printf("\n\t The popped elements is %d",stack[top]);
top--;
}
}
void display()
{
if(top>=0)
{
printf("\n The elements in STACK \n");
for(i=top; i>=0; i--)
printf("\n%d",stack[i]);
printf("\n Press Next Choice");
}
else
{
printf("\n The STACK is empty");
}
}
/slip 2 *Write a C program to accept and sort n elements in ascending order by
using bubble sort.*/
#include<stdio.h>
void bubble_sort(int a[20],int n);
void main()
{
int i,a[20],n;
int time_com=0;
printf("enter the element in array=");
scanf("%d",&n);
printf("enter the elememt=");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
bubble_sort(a,n);
printf("the sorted list=");
for(i=0;i<n;i++)
printf("%d\n",a[i]);
}
void bubble_sort(int a[20],int n)
{
int time_com=0;
int i,j,t;
for(i=0;i<n;i++)
{
for(j=0;j<n-i-1;j++)
{
time_com++;
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
printf("the timecom=%d",time_com);
}
// Binary Search Tree operations in C
#include <stdio.h>
#include <stdlib.h>
struct node {
int key;
struct node *left, *right;
};
// Create a node
struct node *newNode(int item) {
struct node *temp = (struct node *)malloc(sizeof(struct node));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
// Inorder Traversal
void inorder(struct node *root) {
if (root != NULL) {
// Traverse left
inorder(root->left);
// Traverse root
printf("%d -> ", root->key);
// Traverse right
inorder(root->right);
}
}
// Insert a node
struct node *insert(struct node *node, int key) {
// Return a new node if the tree is empty
if (node == NULL) return newNode(key);
// Traverse to the right place and insert the node
if (key < node->key)
node->left = insert(node->left, key);
else
node->right = insert(node->right, key);
return node;
}
// Find the inorder successor
struct node *minValueNode(struct node *node) {
struct node *current = node;
// Find the leftmost leaf
while (current && current->left != NULL)
current = current->left;
return current;
}
// Deleting a node
struct node *deleteNode(struct node *root, int key) {
// Return if the tree is empty
if (root == NULL) return root;
// Find the node to be deleted
if (key < root->key)
root->left = deleteNode(root->left, key);
else if (key > root->key)
root->right = deleteNode(root->right, key);
else {
// If the node is with only one child or no child
if (root->left == NULL) {
struct node *temp = root->right;
free(root);
return temp;
} else if (root->right == NULL) {
struct node *temp = root->left;
free(root);
return temp;
}
// If the node has two children
struct node *temp = minValueNode(root->right);
// Place the inorder successor in position of the node to be deleted
root->key = temp->key;
// Delete the inorder successor
root->right = deleteNode(root->right, temp->key);
}
return root;
}
// Driver code
int main() {
struct node *root = NULL;
root = insert(root, 8);
root = insert(root, 3);
root = insert(root, 1);
root = insert(root, 6);
root = insert(root, 7);
root = insert(root, 10);
root = insert(root, 14);
root = insert(root, 4);
printf("Inorder traversal: ");
inorder(root);
printf("\nAfter deleting 10\n");
root = deleteNode(root, 10);
printf("Inorder traversal: ");
inorder(root);
}
/* slip 3 Write a C program to accept and sort n elements in ascending order by
using insertion sort.*/
#include<stdio.h>
#define MAX 20
void main()
{
int A[MAX],i,n;
printf("Enter how many numbers\n");
scanf("%d",&n);
printf("Enter the unsorted elements:\n");
for(i=0;i<n;i++)
scanf("%d",&A[i]);
insertionsort(A,n);
printf("Sorted elements are:\n");
for(i=0;i<n;i++)
printf("%d\t",A[i]);
}
void insertionsort(int A[MAX],int n)
{
int i,j,key;
for(i=1;i<n;i++)
{
key=A[i];
for(j=i-1;(j>=0) && (key<A[j]);j--)
A[j+1]=A[j];
A[j+1]=key;
}
}
// C program to get intersection point of two linked list
#include <stdio.h>
#include <stdlib.h>
/* Link list node */
typedef struct Node {
int data;
struct Node* next;
} Node;
/* function to get the intersection point of two linked
lists head1 and head2 */
Node* getIntesectionNode(Node* head1, Node* head2)
{
while (head2) {
Node* temp = head1;
while (temp) {
// if both Nodes are same
if (temp == head2)
return head2;
temp = temp->next;
}
head2 = head2->next;
}
// intersection is not present between the lists
return NULL;
}
// Driver Code
int main()
{
/*
Create two linked lists
1st 3->6->9->15->30
2nd 10->15->30
15 is the intersection point
*/
Node* newNode;
// Addition of new nodes
Node* head1 = (Node*)malloc(sizeof(Node));
head1->data = 10;
Node* head2 = (Node*)malloc(sizeof(Node));
head2->data = 3;
newNode = (Node*)malloc(sizeof(Node));
newNode->data = 6;
head2->next = newNode;
newNode = (Node*)malloc(sizeof(Node));
newNode->data = 9;
head2->next->next = newNode;
newNode = (Node*)malloc(sizeof(Node));
newNode->data = 15;
head1->next = newNode;
head2->next->next->next = newNode;
newNode = (Node*)malloc(sizeof(Node));
newNode->data = 30;
head1->next->next = newNode;
head1->next->next->next = NULL;
Node* intersectionPoint
= getIntesectionNode(head1, head2);
if (!intersectionPoint)
printf(" No Intersection Point \n");
else
printf("Intersection Point: %d\n",
intersectionPoint->data);
}
// This code is contributed by Aditya Kumar (adityakumar12
slip4
q1
#include <stdio.h>
int main()
{
int array[100], search, c, number;
printf("Enter the number of elements in array\n");
scanf("%d",&number);
printf("Enter %d numbers\n", number);
for ( c = 0 ; c < number ; c++ )
scanf("%d",&array[c]);
printf("Enter the number to search\n");
scanf("%d",&search);
for ( c = 0 ; c < number ; c++ )
{
if ( array[c] == search ) /* if required element found */
{
printf("%d is present at location %d.\n", search, c+1);
break;
}
}
if ( c == number )
printf("%d is not present in array.\n", search);
return 0;
}
#include <stdio.h>
#include <stdlib.h>
struct node
{
int num; //Data of the node
struct node *nextptr; //Address of the next node
}*stnode;
void createNodeList(int n); // function to create the list
void displayList(); // function to display the list
int main()
{
int n;
printf("\n\n Linked List : To create and display Singly Linked
List :\n");
printf("------------------------------------------------------
-------\n");
printf(" Input the number of nodes : ");
scanf("%d", &n);
createNodeList(n);
printf("\n Data entered in the list : \n");
displayList();
return 0;
}
void createNodeList(int n)
{
struct node *fnNode, *tmp;
int num, i;
stnode = (struct node *)malloc(sizeof(struct node));
if(stnode == NULL) //check whether the fnnode is NULL and if so no
memory allocation
{
printf(" Memory can not be allocated.");
}
else
{
// reads data for the node through keyboard
printf(" Input data for node 1 : ");
scanf("%d", &num);
stnode->num = num;
stnode->nextptr = NULL; // links the address field to NULL
tmp = stnode;
// Creating n nodes and adding to linked list
for(i=2; i<=n; i++)
{
fnNode = (struct node *)malloc(sizeof(struct node));
if(fnNode == NULL)
{
printf(" Memory can not be allocated.");
break;
}
else
{
printf(" Input data for node %d : ", i);
scanf(" %d", &num);
fnNode->num = num; // links the num field of fnNode
with num
fnNode->nextptr = NULL; // links the address field of
fnNode with NULL
tmp->nextptr = fnNode; // links previous node i.e. tmp to
the fnNode
tmp = tmp->nextptr;
}
}
}
}
void displayList()
{
struct node *tmp;
if(stnode == NULL)
{
printf(" List is empty.");
}
else
{
tmp = stnode;
while(tmp != NULL)
{
printf(" Data = %d\n", tmp->num); // prints the data of
current node
tmp = tmp->nextptr; // advances the
position of current node
}
}
}
slip5
q1
#include<stdio.h>
int stack[20];
int top = -1;
void push(int x)
{
stack[++top] = x;
}
int pop()
{
return stack[top--];
}
int main()
{
char exp[20];
char *e;
int n1,n2,n3,num;
printf("Enter the expression :: ");
scanf("%s",exp);
e = exp;
while(*e != '\0')
{
if(isdigit(*e))
{
num = *e - 48;
push(num);
}
else
{
n1 = pop();
n2 = pop();
switch(*e)
{
case '+':
{
n3 = n1 + n2;
break;
}
case '-':
{
n3 = n2 - n1;
break;
}
case '*':
{
n3 = n1 * n2;
break;
}
case '/':
{
n3 = n2 / n1;
break;
}
}
push(n3);
}
e++;
} printf("\nThe result of expression %s = %d\n\n",exp,pop());
return 0;
}
slip no 6.
q1
/*C program to Reverse String using STACK*/
#include <stdio.h>
#include <string.h>
#define MAX 100 /*maximum no. of characters*/
/*stack variables*/
int top=-1;
int item;
/***************/
/*string declaration*/
char stack_string[MAX];
/*function to push character (item)*/
void pushChar(char item);
/*function to pop character (item)*/
char popChar(void);
/*function to check stack is empty or not*/
int isEmpty(void);
/*function to check stack is full or not*/
int isFull(void);
int main()
{
char str[MAX];
int i;
printf("Input a string: ");
scanf("%[^\n]s",str); /*read string with spaces*/
/*gets(str);-can be used to read string with spaces*/
for(i=0;i<strlen(str);i++)
pushChar(str[i]);
for(i=0;i<strlen(str);i++)
str[i]=popChar();
printf("Reversed String is: %s\n",str);
return 0;
}
/*function definition of pushChar*/
void pushChar(char item)
{
/*check for full*/
if(isFull())
{
printf("\nStack is FULL !!!\n");
return;
}
/*increase top and push item in stack*/
top=top+1; stack_string[top]=item;
}
/*function definition of popChar*/
char popChar()
{
/*check for empty*/
if(isEmpty())
{
printf("\nStack is EMPTY!!!\n");
return 0;
}
/*pop item and decrease top*/
item = stack_string[top];
top=top-1;
return item;
}
/*function definition of isEmpty*/
int isEmpty()
{
if(top==-1)
return 1;
else
return 0;
}
/*function definition of isFull*/
int isFull()
{
if(top==MAX-1)
return 1;
else
return 0;
}
q.2nd
#include<stdio.h>
typedef struct employee
{
char name[10];
int age;
}record;
record employee[100];
int readfile(record *a)
{
int i=0;
FILE *fp;
if((fp=fopen("emp.txt","r"))!=NULL)
{
while(!feof(fp))
{
fscanf(fp,"%d%s",&a[i].age,a[i].name);
i++;
}
}
return(i-1);
}
void writefile(record *a,int n)
{
int i=0;
FILE *fp;
if((fp=fopen("bubble.txt","w+"))!=NULL)
{
for(i=0;i<n;i++)
fprintf(fp,"%d%s\n",a[i].age,a[i].name);
}
}
void bubble_sort(record *a,int n)
{
int i,j; record t;
for(i=1;i<n;i++)
{
for(j=0;j<n-i;j++)
{
if(strcmp(a[j].name,a[j+1].name)>=0)
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}
}
main()
{
int n;
n=readfile(employee);
bubble_sort(employee,n);
writefile(employee,n);
}
slip 7
q1
#include <stdio.h>
#include <stdlib.h>
/* Link list node */
struct Node {
int data;
struct Node* next;
};
/* Given a reference (pointer to pointer) to the head
of a list and an int, push a new node on the front
of the list. */
void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node
= (struct Node*)malloc(sizeof(struct Node));
/* put in the data */
new_node->data = new_data;
/* link the old list of the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* Counts no. of nodes in linked list */
int getCount(struct Node* head)
{
int count = 0; // Initialize count
struct Node* current = head; // Initialize current
while (current != NULL) {
count++;
current = current->next;
}
return count;
}
/* Driver code*/
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
/* Use push() to construct below list
1->2->1->3->1 */
push(&head, 1);
push(&head, 3);
push(&head, 1);
push(&head, 2);
push(&head, 1);
// Function call
printf("Length of nodes is %d", getCount(head));
return 0;
}
slip 6
Q.1) Write a C program to reverse a string using Stack .
#include<stdio.h>
#include<string.h>
#define size 20
int top=-1;
char stack[size];
char push(char ch)
{
if(top==(size-1))
printf("\nStack is Overflow !!");
else
stack[++top]=ch;
return 0;
}
char pop()
{
if(top==-1)
printf("\nStack is Underflow !!");
else
return stack[top--];
return 0;
}
void main()
{
char str[20];
int i;
clrscr();
printf("\nEnter the string :\n" );
gets(str);
for(i=0;i<strlen(str);i++)
{
push(str[i]);
}
for(i=0;i<strlen(str);i++)
{
str[i]=pop();
}
printf("\nReversed string is : ");
puts(str);
}
Q.2) Write a C program to read the data from the file “employee.txt” which contains empno and
empname and sort the data on names alphabetically (use strcmp) using Bubble Sort.
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct employee
{
int age;
};
void bubble(struct employee *emp, int n)
{
int i,j;
for(i=0;i<n-1;i++)
{
for(j=0;j<n-i-1;j++)
{
struct employee temp;
if(emp[j].age <emp[j+1].age)
{
temp = emp[j+1];
emp[j+1]=emp[j];
emp[j]=temp;
}
}
}
}
void main()
{
struct employee *emp=NULL, temp;
FILE *fp;
int i,j,age,n;
clrscr();
fp=fopen("emploee.txt","r");
while(fscanf(fp,"%d",&age)!=EOF)
n++;
emp=malloc(sizeof(struct employee)*n);
n=0;
rewind(fp);
while(fscanf(fp,"%d", &emp[n].age)!=EOF)
n++;
fclose(fp);
bubble(emp,n);
fp=fopen("employee.txt", "w");
for(i=0;i<n;i++)
fprintf(fp,"%d\n", emp[i].age);
fclose(fp);
getch();
}
slip7
Q1)write a c program to find the length of singly linked list
#include<stdio.h>
typedef struct node
{
int info;
struct node *next;
}NODE;
void createlist(NODE *head)
{
int n , count ;
NODE *last, *newnode;
printf("How many nodes:");
scanf("%d", &n);
last = head;
for(count = 1 ; count<=n; count++)
{
newnode = (NODE *) malloc(sizeof(NODE));
newnode->next = NULL;
printf("\n Enter the node data:");
scanf("%d", &newnode->info);
last->next = newnode;
last = newnode;
}
}
void display(NODE *head)
{
NODE *temp;
for(temp=head->next; temp!=NULL; temp=temp->next)
{
printf("%d\t", temp->info);
}
}
void length_sll(struct node *head)
{
int length=0;
while(head!=NULL)
{
head=head->next;
length++;
}
printf("\nlength of above SLL is %d",length-1);
}
void main()
{
NODE* head;
int choice , n , pos;
head=(NODE*)malloc(sizeof (NODE));
head->next=NULL;
do
{
printf("\n1:CREATE");
printf("\n2:DISPLAY") ;
printf("\n3:FIND LENGTH OF SLL");
printf("\n4:EXIT");
printf("\nENTER YOUR CHOICE: ");
scanf("%d",&choice) ;
switch(choice)
{
case 1 :
createlist(head);
break;
case 2 :
display(head);
break;
case 3:
length_sll(head);
break;
case 4: exit(1);
break;
}
} while (choice!=8);
}
Q2) write a c program to implement dynamic implementation of
stack of integer with following operations
push,pop,isempty,isfull
#include<stdio.h>
typedef struct node
{
int info;
struct node *next;
}NODE;
void createlist(NODE *head)
{
int n , count ;
NODE *last, *newnode;
printf("How many nodes:");
scanf("%d", &n);
last = head;
for(count = 1 ; count<=n; count++)
{
newnode = (NODE *) malloc(sizeof(NODE));
newnode->next = NULL;
printf("\n Enter the node data:");
scanf("%d", &newnode->info);
last->next = newnode;
last = newnode;
}
}
void display(NODE *head)
{
NODE *temp;
for(temp=head->next; temp!=NULL; temp=temp->next)
{
printf("%d\t", temp->info);
}
}
void length_sll(struct node *head)
{
int length=0;
while(head!=NULL)
{
head=head->next;
length++;
}
printf("\nlength of above SLL is %d",length-1);
}
void main()
{
NODE* head;
int choice , n , pos;
head=(NODE*)malloc(sizeof (NODE));
head->next=NULL;
do
{
printf("\n1:CREATE");
printf("\n2:DISPLAY") ;
printf("\n3:FIND LENGTH OF SLL");
printf("\n4:EXIT");
printf("\nENTER YOUR CHOICE: ");
scanf("%d",&choice) ;
switch(choice)
{
case 1 :
createlist(head);
break;
case 2 :
display(head);
break;
case 3:
length_sll(head);
break;
case 4: exit(1);
break;
}
} while (choice!=8);
}
slip8
Q.1) Write a C program to create and display doubly linked list.
#include <stdio.h>
#include <stdlib.h>
struct node
{
int num;
struct node * preptr;
struct node * nextptr;
}*stnode, *ennode;
void DlListcreation(int n);
void displayDlList();
int main()
{
int n;
clrscr();
stnode = NULL;
ennode = NULL;
printf("\n\n Doubly Linked List : Create and display a doubly linked list :\n");
printf("-------------------------------------------------------------------\n");
printf("\nInput the number of nodes:\n");
scanf("%d",&n);
DlListcreation(n);
displayDlList();
return 0;
}
void DlListcreation(int n)
{
int i,num;
struct node *fnNode;
if(n >= 1)
{
stnode = (struct node *)malloc(sizeof(struct node));
if(stnode != NULL)
{
printf("\n\nInput data for node 1 : "); // assigning data in the first node
scanf("%d", &num);
stnode->num = num;
stnode->preptr = NULL;
stnode->nextptr = NULL;
ennode = stnode;
// putting data for rest of the nodes
for(i=2;i<=n;i++)
{
fnNode = (struct node *)malloc(sizeof(struct node));
if(fnNode != NULL)
{
printf("\nInput data for node %d : ", i);
scanf("%d", &num);
fnNode->num = num;
fnNode->preptr = ennode; // new node is linking with the previous node
fnNode->nextptr = NULL;
ennode->nextptr = fnNode; // previous node is linking with the new node
ennode = fnNode; // assign new node as last node
}
else
{
printf("\nMemory can not be allocated !\n");
break;
}
}
}
else
{
printf("\nMemory can not be allocated !\n");
}
}
}
void displayDlList()
{
struct node * tmp;
int n=1;
if(stnode == NULL)
{
printf("\nNo data found in the List yet.\n");
}
else
{
tmp = stnode;
printf("\n\nData entered on the list are :\n");
while(tmp != NULL)
{
printf("node %d : %d\n",n,tmp->num);
n++;
tmp = tmp->nextptr; // current pointer moves to the next node
}
}
}
2.Write a C program to concatenate two singly linked list.
#include<stdio.h>
#include<stdlib.h>
struct node
{
int info;
struct node *link;
};
struct node *create_list(struct node *);
struct node *concat( struct node *start1,struct node *start2);
struct node *addatbeg(struct node *start, int data);
struct node *addatend(struct node *start,int data);
void display(struct node *start);
int main()
{
struct node *start1=NULL,*start2=NULL;
clrscr();
start1=create_list(start1);
start2=create_list(start2);
printf("\n\n\nFirst list is : ");
display(start1);
printf("\nSecond list is : ");
display(start2);
start1=concat(start1, start2);
printf("\nConcatenated list is : ");
display(start1);
return 0;
}
struct node *concat( struct node *start1,struct node *start2)
{
struct node *ptr;
if(start1==NULL)
{
start1=start2;
return start1;
}
if(start2==NULL)
return start1;
ptr=start1;
while(ptr->link!=NULL)
ptr=ptr->link;
ptr->link=start2;
return start1;
}
struct node *create_list(struct node *start)
{
int i,n,data;
printf("\n\n\nEnter the number of nodes : ");
scanf("%d",&n);
start=NULL;
if(n==0)
return start;
printf("\nEnter the element to be inserted : ");
scanf("%d",&data);
start=addatbeg(start,data);
for(i=2;i<=n;i++)
{
printf("\nEnter the element to be inserted : ");
scanf("%d",&data);
start=addatend(start,data);
}
return start;
}
void display(struct node *start)
{
struct node *p;
if(start==NULL)
{
printf("\nList is EMPTY !!\n");
return;
}
p=start;
while(p!=NULL)
{
printf("%d ", p->info);
p=p->link;
}
printf("\n");
}
struct node *addatbeg(struct node *start,int data)
{
struct node *tmp;
tmp=(struct node *)malloc(sizeof(struct node));
tmp->info=data;
tmp->link=start;
start=tmp;
return start;
}
struct node *addatend(struct node *start, int data)
{
struct node *p,*tmp;
tmp= (struct node *)malloc(sizeof(struct node));
tmp->info=data;
p=start;
while(p->link!=NULL)
p=p->link;
p->link=tmp;
tmp->link=NULL;
return start;
}
slip 9
Q.1) Write a C program to reverse a singly linked list.
#include<stdio.h>
#include<malloc.h>
struct node
{
int data;
struct node* next;
};
//Globally initialized head pointer
struct node* head = NULL;
//function prototyping
struct node* create_node(int);
void insert_begin(int);
void reverse_list();
void print();
int main()
{
clrscr();
/*Create some nodes and insert data into them*/
insert_begin(10);
insert_begin(90);
insert_begin(31);
insert_begin(78);
insert_begin(99);
printf("\n\nLinked List before reversed:\n");
print();
reverse_list();
printf("\nLinked List after reversed:\n");
print();
return 0;
}
/*Creates a new node using the malloc function*/
struct node* create_node(int data)
{
struct node* new_node = (struct node*) malloc (sizeof(struct node));
if(new_node == NULL)
{
printf("\nMemory can't be allocated for new node !!\n");
return NULL;
}
else
{
new_node -> data = data;
new_node -> next = NULL;
return new_node;
}
}
/*insert a new node at the beginning of the list*/
void insert_begin(int data)
{
struct node* new_node = create_node(data);
if(new_node != NULL)
{
new_node -> next = head;
head = new_node;
}
}
/*reverse the linked list*/
void reverse_list()
{
struct node* temp = head;
struct node* new_head = NULL;
if(head == NULL)
{
return;
}
// create new nodes and insert them beginning
while(temp != NULL)
{
struct node* new_node = create_node(temp->data);
new_node->next = new_head;
new_head = new_node;
temp = temp->next;
}
// update the head with the new head
head = new_head;
}
/*prints the linked list*/
void print()
{
struct node* temp = head;
while(temp != NULL)
{
printf("%d --> ", temp->data);
temp = temp->next;
}
printf("NULL \n");
}
Q.2) Write a menu driven program using C for implementation of singly linked list.
Menu should have the following options –
#include<stdio.h>
#include<stdlib.h>
void create();
void display();
void insert_begin();
void insert_end();
void insert_pos();
void delete_begin();
void delete_end();
void delete_pos();
struct node* head = NULL;
struct node
{
int data;
struct node* next;
};
int main()
{
int choice;
while(1)
{
printf("\n*****\n");
printf("0. Create\n");
printf("1. display\n");
printf("2. Insert Node at beginning\n");
printf("3. Insert Node in specific position\n");
printf("4. Insert Node at end of LinkedList\n");
printf("5. Delete Node at beginning\n");
printf("6. Delete Node at end\n");
printf("7. Delete Node at position\n");
printf("8. ** To exit **");
printf("\n Enter your choice: ");
scanf("%d",&choice);
switch(choice)
{
case 0: create();
break;
case 1: display();
break;
case 2: insert_begin();
break;
case 3: insert_pos();
break;
case 4: insert_end();
break;
case 5: delete_begin();
break;
case 6: delete_end();
break;
case 7: delete_pos();
break;
case 8: exit(0);
default:printf("\n Wrong Choice");
break;
}
}
}
//creates a node
void create()
{
struct node* temp;
//creating new node
temp = (struct node*)malloc(sizeof(struct node));
printf("Enter node data: ");
scanf("%d",&temp->data);
temp->next = NULL;
if(head==NULL) {
head = temp;
}
else{
struct node* ptr = head;
while(ptr->next!=NULL)
{
ptr = ptr->next;
}
ptr->next = temp; //inserting at end of List
}
}
// prints the entire LinkedList
void display()
{
struct node* ptr = head;
if(head==NULL)
{
printf("Linked List is Empty\n");
return;
}
printf("LinkedList: ");
while(ptr!=NULL) // start from first node
{
printf("%d ",ptr->data);
ptr = ptr->next;
}
printf("\n");
}
// to insert node at start of LinkedList
void insert_begin()
{
struct node* temp;
// creating a new node
temp = (struct node*)malloc(sizeof(struct node));
printf("Enter node data: ");
scanf("%d",&temp->data);
temp->next = NULL;
if(head==NULL)
{
head = temp;
return;
}
else
{
temp->next = head; //point it to old head node
head = temp; //point head to new first node
}
}
// to insert node at given position
void insert_pos()
{
struct node* temp;
// creating a new node
temp = (struct node*)malloc(sizeof(struct node));
printf("Enter node data: ");
scanf("%d",&temp->data);
temp->next = NULL;
if(head==NULL) // if list empty we return
{
head = temp;
return;
}
else
{
struct node* prev_ptr;
struct node* ptr = head;
int pos,i;
printf("Enter position: ");
scanf("%d",&pos);
for(i=0;i<pos;i++)
{
prev_ptr = ptr;
ptr = ptr->next;
}
//new node pointing to node in that pos
temp->next = ptr;
//prevptr pointing to new node
prev_ptr->next = temp;
}
}
// to insert node at end of LinkedList
void insert_end()
{
struct node* temp;
//creating new node
temp = (struct node*)malloc(sizeof(struct node));
printf("Enter node data: ");
scanf("%d",&temp->data);
temp->next = NULL;
if(head==NULL)
{
head = temp; //if list is empty, we return
return;
}
else{
struct node* ptr = head;
while(ptr->next!=NULL)
{
ptr = ptr->next;
}
// tail node pointing to new node
ptr->next = temp;
}
}
// to delete first node of LinkedList
void delete_begin()
{
if(head==NULL) //if List is empty we return
{
printf("Linked List is empty | Nothing to delete \n");
return;
}
else
{
struct node* ptr = head;
head = head->next; // head node pointing to second node
free(ptr); // deleting prev head node
printf("Node Deleted \n");
}
}
// to delete last node of LinkedList
void delete_end()
{
if(head==NULL) //if List is empty we return
{
printf("Linked List is empty | Nothing to delete \n");
return;
}
else if(head->next==NULL)
{
struct node* ptr = head;
head = ptr->next;
free(ptr);
}
else
{
struct node* ptr = head;
struct node* prev_ptr = NULL;
while(ptr->next!=NULL)// traverse till last but one node
{
prev_ptr = ptr;
ptr = ptr->next;
}
prev_ptr->next = NULL; // next field of last but one field is made as NULL
free(ptr); // deleting last node
}
}
// to delete node at given position
void delete_pos()
{
struct node* ptr=head;
int pos,i;
printf("Enter node position to delete: ");
scanf("%d",&pos);
if(head==NULL) //we return if List is empty
{
printf("Linked List is empty \n");
return;
}
else if(pos == 0)
{
ptr = head;
head=ptr->next; // head pointing to second node
free(ptr); // deleting old first node
}
else
{
struct node* prev_ptr;
for(i=0;i<pos;i++)
{
prev_ptr = ptr;
ptr = ptr->next;
}
prev_ptr->next = ptr->next; //prev node pointing to pos+1 node
free(ptr); //deleting node at pos
}
}
slip10
q2
#include<stdio.h>
#include<stdlib.h>
struct node
{
struct node *prev;
struct node *next;
int data;
};
struct node *head;
void insertion_beginning();
void insertion_last();
void deletion_beginning();
void deletion_last();
void display();
void search();
void main ()
{
int choice =0;
while(choice != 9)
{
printf("\n*********Main Menu*********\n");
printf("\nChoose one option from the following list ...\n");
printf("\n===============================================\n");
printf("\n1.Insert in Beginning\n2.Insert at last\n3.Delete from Beginning\n4.Delete from last\n5.Search\n6.Show\n7.Exit\n");
printf("\nEnter your choice?\n");
scanf("\n%d",&choice);
switch(choice)
{
case 1:
insertion_beginning();
break;
case 2:
insertion_last();
break;
case 3:
deletion_beginning();
break;
case 4:
deletion_last();
break;
case 5:
search();
break;
case 6:
display();
break;
case 7:
exit(0);
break;
default:
printf("Please enter valid choice..");
}
}
}
void insertion_beginning()
{
struct node *ptr,*temp;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter Item value");
scanf("%d",&item);
ptr->data=item;
if(head==NULL)
{
head = ptr;
ptr -> next = head;
ptr -> prev = head;
}
else
{
temp = head;
while(temp -> next != head)
{
temp = temp -> next;
}
temp -> next = ptr;
ptr -> prev = temp;
head -> prev = ptr;
ptr -> next = head;
head = ptr;
}
printf("\nNode inserted\n");
}
}
void insertion_last()
{
struct node *ptr,*temp;
int item;
ptr = (struct node *) malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter value");
scanf("%d",&item);
ptr->data=item;
if(head == NULL)
{
head = ptr;
ptr -> next = head;
ptr -> prev = head;
}
else
{
temp = head;
while(temp->next !=head)
{
temp = temp->next;
}
temp->next = ptr;
ptr ->prev=temp;
head -> prev = ptr;
ptr -> next = head;
}
}
printf("\nnode inserted\n");
}
void deletion_beginning()
{
struct node *temp;
if(head == NULL)
{
printf("\n UNDERFLOW");
}
else if(head->next == head)
{
head = NULL;
free(head);
printf("\nnode deleted\n");
}
else
{
temp = head;
while(temp -> next != head)
{
temp = temp -> next;
}
temp -> next = head -> next;
head -> next -> prev = temp;
free(head);
head = temp -> next;
}
}
void deletion_last()
{
struct node *ptr;
if(head == NULL)
{
printf("\n UNDERFLOW");
}
else if(head->next == head)
{
head = NULL;
free(head);
printf("\nnode deleted\n");
}
else
{
ptr = head;
if(ptr->next != head)
{
ptr = ptr -> next;
}
ptr -> prev -> next = head;
head -> prev = ptr -> prev;
free(ptr);
printf("\nnode deleted\n");
}
}
void display()
{
struct node *ptr;
ptr=head;
if(head == NULL)
{
printf("\nnothing to print");
}
else
{
printf("\n printing values ... \n");
while(ptr -> next != head)
{
printf("%d\n", ptr -> data);
ptr = ptr -> next;
}
printf("%d\n", ptr -> data);
}
}
void search()
{
struct node *ptr;
int item,i=0,flag=1;
ptr = head;
if(ptr == NULL)
{
printf("\nEmpty List\n");
}
else
{
printf("\nEnter item which you want to search?\n");
scanf("%d",&item);
if(head ->data == item)
{
printf("item found at location %d",i+1);
flag=0;
}
else
{
while (ptr->next != head)
{
if(ptr->data == item)
{
printf("item found at location %d ",i+1);
flag=0;
break;
}
else
{
flag=1;
}
i++;
ptr = ptr -> next;
}
}
if(flag != 0)
{
printf("Item not found\n");
}
}
}
Q2
#include <stdio.h>
struct node {
int data;
struct node *left;
struct node *right;
};
struct node* getNewNode(int data) {
/* dynamically allocate memory for a new node */
struct node* newNode = (struct node*)malloc(sizeof(struct node));
/* populate data in new Node */
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
/*
This function returns below tree
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ \
8 9 10
*/
struct node* generateBTree(){
// Root Node
struct node* root = getNewNode(1);
root->left = getNewNode(2);
root->right = getNewNode(3);
root->left->left = getNewNode(4);
root->left->right = getNewNode(5);
root->right->left = getNewNode(6);
root->right->right = getNewNode(7);
root->left->left->left = getNewNode(8);
root->left->left->right = getNewNode(9);
root->right->right->right = getNewNode(10);
return root;
}
/*
Prints level of all nodes. It does pre Order
traversal and keeps track of the current level and prints it.
*/
void printLevelOfNode(struct node* root, int currentLevel, int num) {
if(root == NULL) {
return;
}
if(root->data == num) {
printf("Level of %d is %d \n", num, currentLevel);
}
printLevelOfNode(root->left, currentLevel+1, num);
printLevelOfNode(root->right, currentLevel+1, num);
}
int main() {
struct node *root = generateBTree();
/*Printing level of nodes */
printLevelOfNode(root, 0, 1);
printLevelOfNode(root, 0, 5);
printLevelOfNode(root, 0, 7);
printLevelOfNode(root, 0, 9);
getchar();
return 0;
}
Slip11
Q.1) Write a C program to sort n elements using QuickSort.
#include<stdio.h>
void quicksort (int x[20], int first, int last)
{
int pivot, j, temp, i;
if(first < last)
{
pivot=first;
i=first;
j=last;
while(i < j)
{
while(x[i] <= x[pivot] && i<last)
i++;
while( x[j] > x[pivot] )
j--;
if(i<j)
{
temp = x[i];
x[i] = x[j];
x[j] = temp;
}
}
temp = x[pivot];
x[pivot] = x[j];
x[j] = temp;
quicksort(x,first,j-1);
quicksort(x,j+1,last);
}
}
int main()
{
int x[20], size, i;
clrscr();
printf("\tQuick sort\n");
printf("-----------------------------------\n");
printf("How many numbers you want to sort?\n");
scanf("%d",&size);
printf("\nEnter %d elements:\n",size);
for(i=0;i<size;i++)
{
scanf("%d",&x[i]);
}
quicksort(x,0,size-1);
printf("\nSorted elements after applying quick sort: \n\n");
for(i=0;i<size;i++)
{
printf( " %d", x[i] );
}
return 0;
}
Q2. Create Binary Search Tree of integers and display its in-order and post order.
#include <stdio.h>
#include <stdlib.h>
// structure of a node
struct node
{
int data;
struct node *left;
struct node *right;
};
// globally initialized root pointer
struct node *root = NULL;
// function prototyping
struct node *create_node(int);
void insert(int);
void inorder(struct node *);
void postorder();
void preorder();
int get_data();
int main()
{
int userChoice;
int userActive = 'Y';
int data;
clrscr();
while (userActive == 'Y' || userActive == 'y')
{
printf("\n1. Insert");
printf("\n2. Inorder ");
printf("\n3. Post Order ");
printf("\n4. Pre Oder ");
printf("\n4. Exit");
printf("\n\nEnter Your Choice: ");
scanf("%d", &userChoice);
printf("\n");
switch(userChoice)
{
case 1:
data = get_data();
insert(data);
break;
case 2:
inorder(root);
break;
case 3:
postorder(root);
break;
case 4:
preorder(root);
break;
case 5:
printf("\n\nProgram was terminated\n");
break;
default:
printf("\n\tInvalid Choice\n");
break;
}
printf("\n__________\nDo you want to continue? ");
fflush(stdin);
scanf(" %c", &userActive);
}
return 0;
}
// creates a new node
struct node *create_node(int data)
{
struct node *new_node = (struct node *)malloc(sizeof(struct node));
if (new_node == NULL)
{
printf("\nMemory for new node can't be allocated");
return NULL;
}
new_node->data = data;
new_node->left = NULL;
new_node->right = NULL;
return new_node;
}
// inserts the data in the BST
void insert(int data)
{
struct node *new_node = create_node(data);
struct node *temp = root;
struct node *prev = NULL;
if (new_node != NULL)
{
// if the root is empty then make a new node as the root node
if (root == NULL)
{
root = new_node;
printf("\n* node having data %d was inserted\n", data);
return;
}
while (temp != NULL)
{
prev = temp;
if (data > temp->data)
{
temp = temp->right;
}
else
{
temp = temp->left;
}
}
// found the last node where the new node should insert
if (data > prev->data)
{
prev->right = new_node;
}
else
{
prev->left = new_node;
}
printf("\n* node having data %d was inserted\n", data);
}
}
// inorder traversal of the BST
void inorder(struct node *root)
{
if (root == NULL)
{
return;
}
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
// preorder traversal of the BST
void preorder(struct node *root)
{
if (root == NULL)
{
return;
}
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
// postorder travsersal of the BST
void postorder(struct node *root)
{
if (root == NULL)
{
return;
}
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}
// getting data from the user
int get_data()
{
int data;
printf("\nEnter Data: ");
scanf("%d", &data);
return data;
}
Slip12
Q.1) Write a C program to accept two polynomials and display the addition of polynomials.
#include<stdio.h>
#include<stdlib.h>
typedef struct link
{
int coeff;
int pow;
struct link * next;
} my_poly;
void my_create_poly(my_poly **);
void my_show_poly(my_poly *);
void my_add_poly(my_poly **, my_poly *, my_poly *);
int main(void)
{
int ch;
clrscr();
do
{
my_poly * poly1, * poly2, * poly3;
printf("\nCreate 1st expression:\n");
my_create_poly(&poly1);
printf("\nStored the 1st expression !!");
my_show_poly(poly1);
printf("\nCreate 2nd expression:\n");
my_create_poly(&poly2);
printf("\nStored the 2nd expression !!");
my_show_poly(poly2);
my_add_poly(&poly3, poly1, poly2);
my_show_poly(poly3);
printf("\nAdd two more expressions? (Y = 1 / N = 0): ");
scanf("%d", &ch);
}while(ch);
return 0;
}
void my_create_poly(my_poly ** node)
{
int flag;
int coeff,pow;
my_poly * tmp_node;
tmp_node = (my_poly *) malloc(sizeof(my_poly));
*node = tmp_node;
do
{
printf("\nEnter Coeff:");
scanf("%d",&coeff);
tmp_node->coeff = coeff;
printf("\nEnter Pow:");
scanf("%d", &pow);
tmp_node->pow = pow;
tmp_node->next = NULL;
printf("\nContinue adding more terms to the polynomial list?(Y = 1/N = 0): ");
scanf("%d", &flag);
if(flag)
{
tmp_node->next = (my_poly *) malloc(sizeof(my_poly));
tmp_node = tmp_node->next;
tmp_node->next = NULL;
}
}while(flag);
}
void my_show_poly(my_poly * node)
{
printf("\n\nThe polynomial expression is:\n");
while(node != NULL)
{
printf("%dx^%d", node->coeff, node->pow);
node = node->next;
if(node != NULL)
printf(" + ");
}
}
void my_add_poly(my_poly ** result, my_poly * poly1, my_poly * poly2)
{
my_poly * tmp_node; //Temporary storage for the linked list
tmp_node = (my_poly *) malloc(sizeof(my_poly));
tmp_node->next = NULL;
*result = tmp_node;
while(poly1 && poly2)
{
if(poly1->pow > poly2->pow)
{
tmp_node->pow = poly1->pow;
tmp_node->coeff = poly1->coeff;
poly1 = poly1->next;
}
else if(poly1->pow < poly2->pow)
{
tmp_node->pow = poly2->pow;
tmp_node->coeff = poly2->coeff;
poly2 = poly2->next;
}
else
{
tmp_node->pow = poly1->pow;
tmp_node->coeff = poly1->coeff + poly2->coeff;
poly1 = poly1->next;
poly2 = poly2->next;
}
if(poly1 && poly2)
{
tmp_node->next = (my_poly *) malloc(sizeof(my_poly));
tmp_node = tmp_node->next;
tmp_node->next = NULL;
}
}
while(poly1 || poly2)
{
tmp_node->next = (my_poly *) malloc(sizeof(my_poly));
tmp_node = tmp_node->next;
tmp_node->next = NULL;
if(poly1)
{
tmp_node->pow = poly1->pow;
tmp_node->coeff = poly1->coeff;
poly1 = poly1->next;
}
if(poly2)
{
tmp_node->pow = poly2->pow;
tmp_node->coeff = poly2->coeff;
poly2 = poly2->next;
}
}
printf("\n\n\nAddition Complete !!");
printf("---------------------------------------------------------------------------------");
Q.2) Write a C program to implement static implementation of Circular Queue with operations:
#include<stdio.h>
#define MAX 5
int cqueue_arr[MAX];
int front = -1;
int rear = -1;
/*Begin to insert*/
void insert(int item)
{
if((front==0 && rear==MAX-1) || (front==rear+1))
{
printf("\nQueue OVERFLOW !!\n");
return;
}
if(front==-1) /*If queue is empty*/
{
front=0;
rear=0;
}
else
{
if(rear == MAX-1)
rear=0;
else
rear=rear+1;
}
cqueue_arr[rear]=item;
}
/*End of insert*/
/*Begin of delete*/
void del()
{
if(front==-1)
{
printf("\nQueue UNDERFLOW !!\n");
return;
}
printf("\nElement deleted from circular queue is: %d\n",cqueue_arr[front]);
if(front==rear)
{
front=-1;
rear=-1;
}
else
{
if(front==MAX-1)
front=0;
else
front=front+1;
}
}
/*End of delete*/
/*Begin of display*/
void display()
{
int front_pos=front,rear_pos=rear;
if(front==-1)
{
printf("\nQueue is EMPTY !!\n");
return;
}
printf("\nQueue elements:\n");
if(front_pos <= rear_pos)
while(front_pos <= rear_pos)
{
printf("%d\t",cqueue_arr[front_pos]);
front_pos++;
}
else
{
while(front_pos <= MAX-1)
{
printf("%d\t",cqueue_arr[front_pos]);
front_pos++;
}
front_pos=0;
while(front_pos <= rear_pos)
{
printf("%d\t",cqueue_arr[front_pos]);
front_pos++;
}
}
printf("\n");
}
/*End of display*/
/*Main Program*/
void main()
{
int ch,item;
clrscr();
do
{
printf("\n1 : Insert\n2 : Delete\n3 : Display\n4 : Quit\n");
printf("\n\nEnter your choice:\n");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("\nInput the element for insertion in queue:\n");
scanf("%d",&item);
insert(item);
break;
case 2: del();
break;
case 3: display();
break;
case 4:
break;
default: printf("\nWrong Choice !!\n");
}
}while(ch!=4);
}
Slip13
Q.1) Write a program to sort n elements using Merge Sort.
#include<stdio.h>
void disp();
void mergesort(int,int,int);
void msortdiv(int,int);
int a[50],n;
void main()
{
int i;
clrscr();
printf("\n\nEnter the value of n:\n");
scanf("%d",&n);
printf("\nEnter the elements for an array:\n\n");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
printf("\nArray before sorting:\n");
for(i=0;i<n;i++)
{
printf("%d\t",a[i]);
}
msortdiv(0,n-1);
printf("\n\n\nArray after sorting:\n");
for(i=0;i<n;i++)
{
printf("%d\t",a[i]);
}
}
void mergesort(int low,int mid,int high)
{
int t[50],i,j,k;
i=low;
j=mid+1;
k=low;
while((i<=mid) && (j<=high))
{
if(a[i]>=a[j])
{
t[k++]=a[j++];
}
else
{
t[k++]=a[i++];
}
}
while(i<=mid)
t[k++] = a[i++];
while(j<=high)
t[k++] = a[j++];
for(i=low;i<=high;i++)
{
a[i]=t[i];
}
}
void msortdiv(int low,int high)
{
int mid;
if(low!=high)
{
mid=((low+high)/2);
msortdiv(low,mid);
msortdiv(mid+1,high);
mergesort(low,mid,high);
}
}
Q.2) Write a C program to implement static implementation of Linear Queue with operations:
#include<stdio.h>
#define MAX 5
struct queue //structure of queue
{
int data[MAX];
int front,rear;
};
void initQ(struct queue *q) //initialization
{
q->front = q->rear = -1;
}
int isEmptyQ(struct queue *q)
{
if(q->front == q->rear)
return 1;
else
return 0;
}
int isFullQ(struct queue *q)
{
if(q->rear == MAX - 1)
return 1;
else
return 0;
}
void insertQ(struct queue *q, int x)
{
q ->data[++(q->rear)] = x;
}
int deleteQ(struct queue *q)
{
return (q->data[++(q->front)]);
}
void display(struct queue *q)
{
int i;
printf("\nQueue contents are:\t");
for(i = q->front+1;i <= q->rear;i++)
printf("%d\t", q -> data[i]);
}
/* main program */
void main()
{
struct queue q1;
int ch,x;
clrscr();
do
{
printf("\n1 : Initialization\n2 : IsEmpty\n3 : IsFull\n4 : Insert\n5 : Delete\n6 : Display\n");
printf("Enter your choice\n");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("\nInitialization of QUEUE !!\n");
initQ(&q1);
break;
case 2: if(isEmptyQ(&q1))
printf("\nQueue is EMPYTY !!");
else
{
printf("\nQueue is NOT EMPTY !!\n");
}
break;
case 3: if(isFullQ(&q1))
printf("\nQueue is FULL !!");
else
{
printf("\nQueue is NOT FULL !!\n");
}
break;
case 4: if(isFullQ(&q1))
printf("\nQueue is FULL !!");
else
{
printf("\nEnter the element to be inserted:\n");
scanf("%d",&x);
insertQ(&q1,x);
}
break;
case 5: if(isEmptyQ(&q1))
printf("\nQueue is EMPYTY !!");
else
{
printf("\nDeleted element is %d\n",deleteQ(&q1));
}
break;
case 6: printf("\nThe QUEUE is as follows :\n");
display(&q1);
break;
}
}while(ch>0 && ch<7);
}
Slip14
Q.1) Write a C program to search an element using binary search method using recursion.
#include <stdio.h>
int main()
{
int i, low, high, mid, n, key, array[100];
clrscr();
printf("\n\nEnter number of elements:\n");
scanf("%d",&n);
printf("\nEnter %d integers:\n", n);
for(i = 0; i < n; i++)
scanf("%d",&array[i]);
printf("\nEnter value to find:\n");
scanf("%d", &key);
low = 0;
high = n - 1;
mid = (low+high)/2;
while (low <= high)
{
if(array[mid] < key)
low = mid + 1;
else if (array[mid] == key)
{
printf("\n\n%d found at position %d\n", key, mid+1);
break;
}
else
high = mid - 1;
mid = (low + high)/2;
}
if(low > high)
printf("\nNot found! %d isn't present in the list\n", key);
return 0;
}
Q2. Write a C program to traverse graph by using BFS.
#include<stdio.h>
#include<stdlib.h>
struct q
{
int data[20];
int front,rear;
}q1;
struct node
{
int vertex;
struct node * next;
}*v[10];
void add(int n)
{
q1.rear++;
q1.data[q1.rear] = n;
}
int del()
{
q1.front++;
return q1.data[q1.front];
}
void initq()
{
q1.front = q1.rear = -1;
}
int emptyq()
{
return (q1.rear == q1.front);
}
void create(int m[10][10], int n)
{
int i,j;
char ans;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
m[i][j] = 0;
if(i!=j)
{
printf("\nIs there an edge between %d and %d:",i+1,j+1);
scanf("%d",&m[i][j]);
}
}
}
void disp(int m[10][10],int n)
{
int i,j;
printf("\nThe adjacency matrix is:\n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
printf("%d",m[i][j]);
printf("\n");
}
}
void create1(int m[10][10],int n)
{
int i,j;
struct node *temp, *newnode;
for(i=0;i<n;i++)
{
v[i] = NULL;
for(j=0;j<n;j++)
{
if(m[i][j] == 1)
{
newnode=(struct node *)malloc(sizeof(struct node));
newnode->next = NULL;
newnode->vertex = j+1;
if(v[i]==NULL)
v[i] = temp = newnode;
else
{
temp->next = newnode;
temp=newnode;
}
}
}
}
}
void displist(int n)
{
struct node *temp;
int i;
for(i=0;i<n;i++)
{
printf("\n%d | ",i+1);
temp=v[i];
while(temp)
{
printf("\n%d | ",temp->vertex);
temp = temp->next;
}
printf("NULL !");
}
}
void bfs(int m[10][10], int n)
{
int i,j,v,w;
int visited[20];
initq();
for(i=0;i<n;i++)
visited[i] = 0;
printf("\nThe BFS Traversal is:\n");
v=0;
visited[v] = 1;
add(v);
while(!emptyq())
{
v=del();
printf("\n%d",v+1);
printf("\n");
for(w=0;w<n;w++)
if((m[10][10] == 1) && (visited[w] == 0))
{
add(w);
visited[w]=1;
}
}
}
void main()
{
int m[10][10],n;
clrscr();
printf("\nEnter no. of vertices:\n");
scanf("%d",&n);
create(m,n);
disp(m,n);
create1(m,n);
displist(n);
bfs(m,n);
}
Slip15
Q1. Write a C program to sort n numbers using merge sort.
#include<stdio.h>
void disp();
void mergesort(int,int,int);
void msortdiv(int,int);
int a[50],n;
void main()
{
int i;
clrscr();
printf("\n\nEnter the value of n:\n");
scanf("%d",&n);
printf("\nEnter the elements for an array:\n\n");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
printf("\nArray before sorting:\n");
for(i=0;i<n;i++)
{
printf("%d\t",a[i]);
}
msortdiv(0,n-1);
printf("\n\n\nArray after sorting:\n");
for(i=0;i<n;i++)
{
printf("%d\t",a[i]);
}
}
void mergesort(int low,int mid,int high)
{
int t[50],i,j,k;
i=low;
j=mid+1;
k=low;
while((i<=mid) && (j<=high))
{
if(a[i]>=a[j])
{
t[k++]=a[j++];
}
else
{
t[k++]=a[i++];
}
}
while(i<=mid)
t[k++] = a[i++];
while(j<=high)
t[k++] = a[j++];
for(i=low;i<=high;i++)
{
a[i]=t[i];
}
}
void msortdiv(int low,int high)
{
int mid;
if(low!=high)
{
mid=((low+high)/2);
msortdiv(low,mid);
msortdiv(mid+1,high);
mergesort(low,mid,high);
}
}
Q2. Write a C program to convert infix expression into Postfix.
#include<stdio.h>
#include<ctype.h>
struct stack
{
char data[20];
int top;
};
/* initialization of the stack */
void init(struct stack *s)
{
s->top=-1;
}
/* checking stack empty or not */
int isempty(struct stack *s)
{
if(s->top==-1)
return 1;
else
return 0;
}
/* insert element onto the stack */
void push(struct stack *s,char x)
{
s->top++;
s->data[s->top] = x;
}
/* delete element from the stack */
char pop(struct stack *s)
{
if(s->top == -1)
return -1;
else
return s->data[s->top--];
}
/* finding precedence of an operator */
int priority(char x)
{
if( x == '(' )
return 0;
else if( x == '+' || x == '-' )
return 1;
else if( x == '*' || x == '/' )
return 2;
else if( x == '^' || x == '$' )
return 3;
else
return -1;
}
int main()
{
struct stack s1;
char exp[20],x;
int i;
clrscr();
init(&s1);
printf("\n\nEnter the infix expression:\n");
scanf("%s",exp);
i=0;
while(exp[i] != '\0')
{
if(isalnum(exp[i]))
printf("%c",exp[i]);
else if( exp[i] == '(' )
push(&s1,exp[i]);
else if( exp[i] == ')' )
{
while((x = pop(&s1)) != '(' )
printf("%c",x);
}
else
{
while(priority(s1.data[s1.top]) >= priority(exp[i]))
printf("%c",pop(&s1));
push(&s1,exp[i]);
}
i++;
}
while(!isempty(&s1))
{
printf("%c",pop(&s1));
}
return 0;
}
Slip16
Q.1) Write a C program to sort an integer array using a recursive binary search method.
#include <stdio.h>
int main()
{
int i, low, high, mid, n, key, array[100];
clrscr();
printf("\n\nEnter number of elements:\n");
scanf("%d",&n);
printf("\nEnter %d integers:\n", n);
for(i = 0; i < n; i++)
scanf("%d",&array[i]);
printf("\nEnter value to find:\n");
scanf("%d", &key);
low = 0;
high = n - 1;
mid = (low+high)/2;
while (low <= high)
{
if(array[mid] < key)
low = mid + 1;
else if (array[mid] == key)
{
printf("\n\n%d found at position %d\n", key, mid+1);
break;
}
else
high = mid - 1;
mid = (low + high)/2;
}
if(low > high)
printf("\nNot found! %d isn't present in the list\n", key);
return 0;
}
Q2. Write a C program to convert infix expression into Postfix.
#include<stdio.h>
#include<ctype.h>
struct stack
{
char data[20];
int top;
};
/* initialization of the stack */
void init(struct stack *s)
{
s->top=-1;
}
/* checking stack empty or not */
int isempty(struct stack *s)
{
if(s->top==-1)
return 1;
else
return 0;
}
/* insert element onto the stack */
void push(struct stack *s,char x)
{
s->top++;
s->data[s->top] = x;
}
/* delete element from the stack */
char pop(struct stack *s)
{
if(s->top == -1)
return -1;
else
return s->data[s->top--];
}
/* finding precedence of an operator */
int priority(char x)
{
if( x == '(' )
return 0;
else if( x == '+' || x == '-' )
return 1;
else if( x == '*' || x == '/' )
return 2;
else if( x == '^' || x == '$' )
return 3;
else
return -1;
}
int main()
{
struct stack s1;
char exp[20],x;
int i;
clrscr();
init(&s1);
printf("\n\nEnter the infix expression:\n");
scanf("%s",exp);
i=0;
while(exp[i] != '\0')
{
if(isalnum(exp[i]))
printf("%c",exp[i]);
else if( exp[i] == '(' )
push(&s1,exp[i]);
else if( exp[i] == ')' )
{
while((x = pop(&s1)) != '(' )
printf("%c",x);
}
else
{
while(priority(s1.data[s1.top]) >= priority(exp[i]))
printf("%c",pop(&s1));
push(&s1,exp[i]);
}
i++;
}
while(!isempty(&s1))
{
printf("%c",pop(&s1));
}
return 0;
}
slip 17
Q.Q.1) Write a C program to read the data from the file “employee.txt” which contains empno and
empname and sort the data on names alphabetically (use strcmp) using Bubble Sort.
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct employee
{
int age;
};
void bubble(struct employee *emp, int n)
{
int i,j;
for(i=0;i<n-1;i++)
{
for(j=0;j<n-i-1;j++)
{
struct employee temp;
if(emp[j].age <emp[j+1].age)
{
temp = emp[j+1];
emp[j+1]=emp[j];
emp[j]=temp;
}
}
}
}
void main()
{
struct employee *emp=NULL, temp;
FILE *fp;
int i,j,age,n;
clrscr();
fp=fopen("emploee.txt","r");
while(fscanf(fp,"%d",&age)!=EOF)
n++;
emp=malloc(sizeof(struct employee)*n);
n=0;
rewind(fp);
while(fscanf(fp,"%d", &emp[n].age)!=EOF)
n++;
fclose(fp);
bubble(emp,n);
fp=fopen("employee.txt", "w");
for(i=0;i<n;i++)
fprintf(fp,"%d\n", emp[i].age);
fclose(fp);
getch();
}
q2
#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<stdlib.h>
#define MAX 100
int top=-1;
char stack[MAX];
int check_balance(char *s);
int match_char(char,char);
void push(char s);
int pop();
int isFull();
int isEmpty();
int check_balance(char *s)
{
char temp;
int i;
for(i=0;i<strlen(s);i++)
{
if(s[i]=='{'||s[i]=='['||s[i]=='(')
push(s[i]);
if(s[i]=='}'||s[i]==']'||s[i]==')')
{
if(isEmpty())
{
printf("\nRight brackets are more than left brackets");
return 0;
}
else
{
temp=pop();
if(!match_char(temp,s[i]))
{
printf("\nmismatched brackets");
return 0;
}
}
}
}
if(isEmpty())
{
printf("\nbrackets are well balanced");
return 1;
}
else
{
printf("\nleft brackets are more than right");
return 0;
}
}
int match_char(char a,char b)
{
if(a=='['&&b==']')
return 1;
else if(a=='{'&&b=='}')
return 1;
else if(a=='('&&b==')')
return 1;
else
return 0;
}
int isEmpty()
{
if(top==NULL)
return 1;
else
return 0;
}
int isFull()
{
if(top==MAX-1)
return 1;
else
return 0;
}
void push(char s)
{
if(isFull())
{
printf("\nstack overflow");
exit(1);
}
top++;
stack[top]=s;
}
int pop()
{
char c;
if(isEmpty())
{
printf("\nstack underflow");
exit(1);
}
c=stack[top];
top--;
return c;
}
void main()
{
char expr[MAX];
int balance;
clrscr();
printf("enter the algebric expression:\n");
gets(expr);
balance=check_balance(expr);
if(balance==1)
printf("\nthe expression is valid");
else
printf("\ninvalid expression");
getch();
}
sli 18
q2
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
struct node{
int data;
struct node *next;
};
struct node *front=0;
struct node *rear=0;
void enqueue(int x)
{
struct node *newnode;
newnode=(struct node *)malloc(sizeof(struct node));
newnode->data=x;
newnode->next=0;
if(front==0&&rear==0)
{
front=rear=newnode;
}
else
{
rear->next=newnode;
rear=newnode;
}
}
void dequeue()
{
struct node *temp;
temp=front;
if(front==0&&rear==0)
{
printf("\nempty queue");
}
else
{
printf("\ndeleted element from queue is %d",front->data);
front=front->next;
free(temp);
}
}
void display()
{
struct node *temp;
if(front==0&&rear==0)
{
printf("\nempty stack");
}
else
{
temp=front;
while(temp!=0)
{
printf("%d\t",temp->data);
temp=temp->next;
}
}
}
void peek()
{
if(front==0&&rear==0)
{
printf("\nempty stack");
}
else
{
printf("\n%d",front->data);
}
}
void main()
{
int choice,val;
clrscr();
while(1)
{
printf("\npress 1:to insert element in an queue");
printf("\npress 2:to delete element from an queue");
printf("\npress 3:to display");
printf("\npress 4:to display front element");
printf("\npress 5:to quit");
printf("\nenter your choice");
scanf("%d",&choice);
switch(choice)
{
case 1:printf("\nenter an queue data:");
scanf("%d",&val);
enqueue(val);
break;
case 2:dequeue();
break;
case 3:display();
break;
case 4:peek();
break;
case 5:exit(1);
break;
default:printf("\nwrong choice");
break;
}
}
}
Slip19
Q.1) Write a C program to create and display singly Linked List.
#include <stdio.h>
#include <stdlib.h>
/* Structure of a node */
struct node
{
int data; // Data
struct node *next; // Address
}*head;
/*Functions to create and display list*/
void createList(int n);
void traverseList();
int main()
{
int n;
clrscr();
printf("\n\nEnter the total number of nodes:\n");
scanf("%d", &n);
createList(n);
printf("\nData in the list:\n");
traverseList();
return 0;
}
/*Create a list of n nodes*/
void createList(int n)
{
struct node *newNode, *temp;
int data,i;
head = (struct node *)malloc(sizeof(struct node));
if(head == NULL)
{
printf("\nUnable to allocate memory !!\n");
exit(0);
}
printf("\nEnter the data of node 1: ");
scanf("%d", &data);
head->data = data; // Link data field with data
head->next = NULL; // Link address field to NULL
// Create n - 1 nodes and add to list
temp = head;
for(i=2; i<=n; i++)
{
newNode = (struct node *)malloc(sizeof(struct node));
if(newNode == NULL)
{
printf("\nUnable to allocate memory !!\n");
break;
}
printf("\nEnter the data of node %d: ", i);
scanf("%d", &data);
newNode->data = data; // Link data field of newNode
newNode->next = NULL; // Make sure new node points to NULL
temp->next = newNode; // Link previous node with newNode
temp = temp->next; // Make current node as previous node
}
}
/*Display entire list*/
void traverseList()
{
struct node *temp;
if(head == NULL)
{
printf("\nList is EMPTY !!");
return;
}
temp = head;
while(temp != NULL)
{
printf("Data = %d\n", temp->data); // Print data of current node
temp = temp->next; // Move to next node
}
}
Q2.Write a C program to display addition of two polynomials using singly linked list.
#include<stdio.h>
#include<stdlib.h>
typedef struct link
{
int coeff;
int pow;
struct link * next;
} my_poly;
void my_create_poly(my_poly **);
void my_show_poly(my_poly *);
void my_add_poly(my_poly **, my_poly *, my_poly *);
int main(void)
{
int ch;
clrscr();
do
{
my_poly * poly1, * poly2, * poly3;
printf("\nCreate 1st expression:\n");
my_create_poly(&poly1);
printf("\nStored the 1st expression !!");
my_show_poly(poly1);
printf("\nCreate 2nd expression:\n");
my_create_poly(&poly2);
printf("\nStored the 2nd expression !!");
my_show_poly(poly2);
my_add_poly(&poly3, poly1, poly2);
my_show_poly(poly3);
printf("\nAdd two more expressions? (Y = 1 / N = 0): ");
scanf("%d", &ch);
}while(ch);
return 0;
}
void my_create_poly(my_poly ** node)
{
int flag;
int coeff,pow;
my_poly * tmp_node;
tmp_node = (my_poly *) malloc(sizeof(my_poly));
*node = tmp_node;
do
{
printf("\nEnter Coefficient:");
scanf("%d",&coeff);
tmp_node->coeff = coeff;
printf("\nEnter Power:");
scanf("%d", &pow);
tmp_node->pow = pow;
tmp_node->next = NULL;
printf("\nContinue adding more terms to the polynomial list?(Y = 1/N = 0): ");
scanf("%d", &flag);
if(flag)
{
tmp_node->next = (my_poly *) malloc(sizeof(my_poly));
tmp_node = tmp_node->next;
tmp_node->next = NULL;
}
}while(flag);
}
void my_show_poly(my_poly * node)
{
printf("\n\nThe polynomial expression is:\n");
while(node != NULL)
{
printf("%dx^%d", node->coeff, node->pow);
node = node->next;
if(node != NULL)
printf(" + ");
}
}
void my_add_poly(my_poly ** result, my_poly * poly1, my_poly * poly2)
{
my_poly * tmp_node; //Temporary storage for the linked list
tmp_node = (my_poly *) malloc(sizeof(my_poly));
tmp_node->next = NULL;
*result = tmp_node;
while(poly1 && poly2)
{
if(poly1->pow > poly2->pow)
{
tmp_node->pow = poly1->pow;
tmp_node->coeff = poly1->coeff;
poly1 = poly1->next;
}
else if(poly1->pow < poly2->pow)
{
tmp_node->pow = poly2->pow;
tmp_node->coeff = poly2->coeff;
poly2 = poly2->next;
}
else
{
tmp_node->pow = poly1->pow;
tmp_node->coeff = poly1->coeff + poly2->coeff;
poly1 = poly1->next;
poly2 = poly2->next;
}
if(poly1 && poly2)
{
tmp_node->next = (my_poly *) malloc(sizeof(my_poly));
tmp_node = tmp_node->next;
tmp_node->next = NULL;
}
}
while(poly1 || poly2)
{
tmp_node->next = (my_poly *) malloc(sizeof(my_poly));
tmp_node = tmp_node->next;
tmp_node->next = NULL;
if(poly1)
{
tmp_node->pow = poly1->pow;
tmp_node->coeff = poly1->coeff;
poly1 = poly1->next;
}
if(poly2)
{
tmp_node->pow = poly2->pow;
tmp_node->coeff = poly2->coeff;
poly2 = poly2->next;
}
}
printf("\n\n\nAddition Complete !!\n");
printf("---------------------------------------------------------------------------------");
}
Slip20
Q.1) Write a C program to sort an array using insertion sort method..
#include <stdio.h>
int main(void)
{
int n, i, j, temp;
int arr[64];
clrscr();
printf("\n\nEnter number of elements:\n");
scanf("%d",&n);
printf("Enter %d integers\n",n);
for(i=0;i<n;i++)
{
scanf("%d",&arr[i]);
}
for(i=1;i<n;i++)
{
j=i;
while(j>0 && arr[j-1] > arr[j])
{
temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
j--;
}
}
printf("\nSorted list in ascending order:\n");
for(i= 0;i<n;i++)
{
printf("%d\t",arr[i]);
}
return 0;
}
2 Write a C program to construct a binary search tree and traverse using pre-order traversal.
#include <stdio.h>
#include <stdlib.h>
// structure of a node
struct node
{
int data;
struct node *left;
struct node *right;
};
// globally initialized root pointer
struct node *root = NULL;
// function prototyping
struct node *create_node(int);
void insert(int);
void inorder(struct node *);
void postorder();
void preorder();
int get_data();
int main()
{
int userChoice;
int userActive = 'Y';
int data;
clrscr();
while (userActive == 'Y' || userActive == 'y')
{
printf("\n1. Insert");
printf("\n2. Inorder ");
printf("\n3. Post Order ");
printf("\n4. Pre Oder ");
printf("\n4. Exit");
printf("\n\nEnter Your Choice: ");
scanf("%d", &userChoice);
printf("\n");
switch(userChoice)
{
case 1:
data = get_data();
insert(data);
break;
case 2:
inorder(root);
break;
case 3:
postorder(root);
break;
case 4:
preorder(root);
break;
case 5:
printf("\n\nProgram was terminated\n");
break;
default:
printf("\n\tInvalid Choice\n");
break;
}
printf("\n__________\nDo you want to continue? ");
fflush(stdin);
scanf(" %c", &userActive);
}
return 0;
}
// creates a new node
struct node *create_node(int data)
{
struct node *new_node = (struct node *)malloc(sizeof(struct node));
if (new_node == NULL)
{
printf("\nMemory for new node can't be allocated");
return NULL;
}
new_node->data = data;
new_node->left = NULL;
new_node->right = NULL;
return new_node;
}
// inserts the data in the BST
void insert(int data)
{
struct node *new_node = create_node(data);
struct node *temp = root;
struct node *prev = NULL;
if (new_node != NULL)
{
// if the root is empty then make a new node as the root node
if (root == NULL)
{
root = new_node;
printf("\n* node having data %d was inserted\n", data);
return;
}
while (temp != NULL)
{
prev = temp;
if (data > temp->data)
{
temp = temp->right;
}
else
{
temp = temp->left;
}
}
// found the last node where the new node should insert
if (data > prev->data)
{
prev->right = new_node;
}
else
{
prev->left = new_node;
}
printf("\n* node having data %d was inserted\n", data);
}
}
// inorder traversal of the BST
void inorder(struct node *root)
{
if (root == NULL)
{
return;
}
inorder(root->left);
printf("%d ", root->data);
inorder(root->right);
}
// preorder traversal of the BST
void preorder(struct node *root)
{
if (root == NULL)
{
return;
}
printf("%d ", root->data);
preorder(root->left);
preorder(root->right);
}
// postorder travsersal of the BST
void postorder(struct node *root)
{
if (root == NULL)
{
return;
}
postorder(root->left);
postorder(root->right);
printf("%d ", root->data);
}
// getting data from the user
int get_data()
{
int data;
printf("\nEnter Data: ");
scanf("%d", &data);
return data;
}
Write, Run & Share C Language code online using OneCompiler's C online compiler for free. It's one of the robust, feature-rich online compilers for C language, running the latest C version which is C18. Getting started with the OneCompiler's C editor is really simple and pretty fast. The editor shows sample boilerplate code when you choose language as 'C' and start coding!
OneCompiler's C online editor supports stdin and users can give inputs to programs using the STDIN textbox under the I/O tab. Following is a sample C program which takes name as input and print your name with hello.
#include <stdio.h>
int main()
{
char name[50];
printf("Enter name:");
scanf("%s", name);
printf("Hello %s \n" , name );
return 0;
}
C language is one of the most popular general-purpose programming language developed by Dennis Ritchie at Bell laboratories for UNIX operating system. The initial release of C Language was in the year 1972. Most of the desktop operating systems are written in C Language.
When ever you want to perform a set of operations based on a condition if-else is used.
if(conditional-expression) {
// code
} else {
// code
}
You can also use if-else for nested Ifs and if-else-if ladder when multiple conditions are to be performed on a single variable.
Switch is an alternative to if-else-if ladder.
switch(conditional-expression) {
case value1:
// code
break; // optional
case value2:
// code
break; // optional
...
default:
// code to be executed when all the above cases are not matched;
}
For loop is used to iterate a set of statements based on a condition.
for(Initialization; Condition; Increment/decrement){
// code
}
While is also used to iterate a set of statements based on a condition. Usually while is preferred when number of iterations are not known in advance.
while(condition) {
// code
}
Do-while is also used to iterate a set of statements based on a condition. It is mostly used when you need to execute the statements atleast once.
do {
// code
} while (condition);
Array is a collection of similar data which is stored in continuous memory addresses. Array values can be fetched using index. Index starts from 0 to size-1.
data-type array-name[size];
data-type array-name[size][size];
Function is a sub-routine which contains set of statements. Usually functions are written when multiple calls are required to same set of statements which increases re-usuability and modularity.
Two types of functions are present in C
Library functions are the in-built functions which are declared in header files like printf(),scanf(),puts(),gets() etc.,
User defined functions are the ones which are written by the programmer based on the requirement.
return_type function_name(parameters);
function_name (parameters)
return_type function_name(parameters) {
//code
}