Completely Solved C, C++ Programs Assignment.
Showing posts with label C Assignments. Show all posts
Showing posts with label C Assignments. Show all posts

C program to implement Priority Queue using heap

Filed Under:

Program Statement :
Write a C program to implement Priority Queue using heap.

Theory :
A Priority Queue is an abstract data type to efficiently support finding an item with the highest priority across a series of operations. The basic operations are :
1. Insert,
2. Find - minimum (or maximum), and
3. Delete-minimum (or maximum).
Some implementations also efficiently support, join two priority queues (meld), delete an arbitrary item, and increase the priority of a item (decrease-key).
A heap is a specialized tree-based data structure that satisfies the heap property : if B is a child node of A, then key(A) ≥ key(B). This implies that an element with the greatest key is always in the root node, and so such a heap is sometimes called a max-heap. (Alternatively, if the comparison is reversed, the smallest element is always in the root node, which results in a min-heap). The several variants of heaps are the prototypical most efficient implementations of the abstract data type priority queues. Priority queues are useful in many applications. In particular, heaps are crucial in several efficient graph algorithms.
Heaps are usually implemented in an array, and don't require pointers between elements.
The operations commonly performed with a heap are :
 delete-max or delete-min : removing the root node of a max or min heap, respectively.
 increase-key or decrease-key : updating a key within a max or min heap, respectively.
 insert : adding a new key to the heap.
 merge : joining two heaps to form a valid new heap containing all the elements of both.

Algorithm :
 Insertion.
/*This algorithm inserts an element in the queue*/
Algo_insert(a[],int heapsize,data,lb)
{
if(heapsize==MAX)/*MAX denotes maximum size of queue*/
{
printf(Queue Is Full!);
exit from program;
}
i=lb+heapsize;
a[i]=data;
while(i>lb AND a[p=parent(i)]<a[i])
{
swap(a[p],a[i]);
i=p;
}
}
&#61548; Deletion.

/*This function deletes an element from the queue*/
int del_hi_priori(a[], heapsize, lb)
{
if(heapsize==1)
{
printf(Queue Is Empty!);
exit from program;
}
t=a[lb];
swap(a[lb],a[heapsize-1]);
i=lb;
heapsize=heapsize-1;
while(1)
{
if((l=left(i))>=heapsize)
exit;
if((r=right(i))>=heapsize)
max_child=l;
else
max_child=(a[l]>a[r])?l:r;
if(a[i]>=a[max_child])
exit;
swap(&a[i],&a[max_child]);
i=max_child;
}
return t;
}

Program listing :
/* C program to implement Priority Queue using heap */
#include<stdio.h>
#include<math.h>
#define MAX 100/*Declaring the maximum size of the queue*/
void swap(int*,int*);
main()
{
int choice,num,n,a[MAX],data,s;
void display(int[],int);
void insert(int[],int,int,int);
int del_hi_priori(int[],int,int);
n=0;/*Represents number of nodes in the queue*/
int lb=0;/*Lower bound of the array is initialized to 0*/
while(1)
{
printf(".....MAIN MENU.....n");
printf("n1.Insert.n");
printf("2.Delete.n");
printf("3.Display.n");
printf("4.Quit.n");
printf("nEnter your choice : ");
scanf("%d",&choice);
switch(choice)
{
case 1:/*choice to accept an elemnt and insert it in the queue*/
printf("Enter data to be inserted : ");
scanf("%d",&data);
insert(a,n,data,lb);
n++;
break;
case 2:
s=del_hi_priori(a,n+1,lb);
if(s!=0)
printf("nThe deleted value is : %d n",s);
if(n>0)
n--;
break;
case 3:/*choice to display the elements of the queue*/
printf("n");
display(a,n);
break;
case 4:/*choice to exit from the program*/
return;
default:
printf("Invalid choice.n");
}
printf("nn");
}
}
/*This function inserts an element in the queue*/
void insert(int a[],int heapsize,int data,int lb)
{
int i,p;
int parent(int);
if(heapsize==MAX)
{
printf("Queue Is Full!!n");
return;
}
i=lb+heapsize;
a[i]=data;
while(i>lb&&a[p=parent(i)]<a[i])
{
swap(&a[p],&a[i]);
i=p;
}
}
/*This function deletes an element from the queue*/
int del_hi_priori(int a[],int heapsize,int lb)
{
int data,i,l,r,max_child,t;
int left(int);
int right(int);
if(heapsize==1)
{
printf("Queue Is Empty!!n");
return 0;
}
t=a[lb];
swap(&a[lb],&a[heapsize-1]);
i=lb;
heapsize--;
while(1)
{
if((l=left(i))>=heapsize)
break;
if((r=right(i))>=heapsize)
max_child=l;
else
max_child=(a[l]>a[r])?l:r;
if(a[i]>=a[max_child])
break;
swap(&a[i],&a[max_child]);
i=max_child;
}
return t;
}
/*Returns parent index*/
int parent(int i)
{
float p;
p=((float)i/2.0)-1.0;
return ceil(p);
}
/*Returns leftchild index*/
int left(int i)
{
return 2*i+1;
}
/*Returns rightchild index*/
int right(int i)
{
return 2*i+2;
}
/*This function displays the queue*/
void display(int a[],int n)
{
int i;
if(n==0)
{
printf("Queue Is Empty!!n");
return;
}
for(i=0;i<n;i++)
printf("%d ",a[i]);
printf("n");
}
/*This function is used to swap two elements*/
void swap(int*p,int*q)
{
int temp;
temp=*p;
*p=*q;
*q=temp;
}

Output :
.....MAIN MENU.....

1.Insert.
2.Delete.
3.Display.
4.Quit.
Enter your choice : 1
Enter data to be inserted : 52

.....MAIN MENU.....
1.Insert.
2.Delete.
3.Display.
4.Quit.
Enter your choice : 1
Enter data to be inserted : 63

.....MAIN MENU.....
1.Insert.
2.Delete.
3.Display.
4.Quit.
Enter your choice : 1
Enter data to be inserted : 45

.....MAIN MENU.....
1.Insert.
2.Delete.
3.Display.
4.Quit.
Enter your choice : 1
Enter data to be inserted : 2

.....MAIN MENU.....
1.Insert.
2.Delete.
3.Display.
4.Quit.
Enter your choice : 1
Enter data to be inserted : 99

.....MAIN MENU.....
1.Insert.
2.Delete.
3.Display.
4.Quit.
Enter your choice : 3
99 63 45 2 52

.....MAIN MENU.....
1.Insert.
2.Delete.
3.Display.
4.Quit.
Enter your choice : 2
The deleted value is : 99

.....MAIN MENU.....
1.Insert.
2.Delete.
3.Display.
4.Quit.
Enter your choice : 3
63 52 45 2

.....MAIN MENU.....
1.Insert.
2.Delete.
3.Display.
4.Quit.
Enter your choice : 2
The deleted value is : 63

.....MAIN MENU.....
1.Insert.
2.Delete.
3.Display.
4.Quit.
Enter your choice : 2
The deleted value is : 52

.....MAIN MENU.....
1.Insert.
2.Delete.
3.Display.
4.Quit.
Enter your choice : 3
45 2

.....MAIN MENU.....
1.Insert.
2.Delete.
3.Display.
4.Quit.
Enter your choice : 4
Discussions :
 For pairing heaps, the insert and merge operations have O(1) complexity.
 Finding the min, max, both the min and max, median, or even the k-th largest element can be done in linear time using heaps.
 An advantage of heaps over trees in some applications is that construction of heaps can be done in linear time.
 One can imagine a priority queue as a modified queue, but when one would get the next element off the queue, the highest-priority one is retrieved first.
 Stacks and queues may be modeled as particular kinds of priority queues. In a stack, the priority of each inserted element is monotonically increasing; thus, the last element inserted is always the first retrieved. In a queue, the priority of each inserted element is monotonically decreasing; thus, the first element inserted is always the first retrieved.
 There are a variety of simple, usually inefficient, ways to implement a priority queue.
1. Sorted list implementation.
2. Unsorted list implementation.
To get better performance, priority queues typically use a heap as their backbone, giving O(log n) performance for inserts and removals.
 There are several applications of priority Queue :
1. Priority queuing can be used to manage limited resources such as bandwidth on a transmission line from a network router.
2. Another use of a priority queue is to manage the events in a discrete event simulation. The events are added to the queue with their simulation time used as the priority.
3. When the graph is stored in the form of adjacency list or matrix, priority queue can be used to extract minimum efficiently when implementing Dijkstra's algorithm.

 Back to main directory:  C Assignment    Software Practical
Read more »


C program to perform different operations on a singly linked list

Filed Under:

Program Statement : 
Write a C program to perform the following operations on a singly linked list :-
● Insertion.
● Deletion.
● Display.
● Sort.
● Reverse
● Split

Theory :
In computer science, a linked list is a data structure that consists of a sequence of data records such that in each record there is a field that contains a reference (i.e., a link) to the next record in the sequence.
Linked list is called a dynamic data structure where the amount of memory required can be varied during its use. In the linked list, adjacency between the elements is maintained by means of links or pointers. A link or pointer is the address (memory location) of the subsequent element.
An element in a linked list is specially termed as node which consists of two fields :
1. Data-to store the actual information.
2. Link-to point to the next node.
Linked list can be classified in three major groups :
Algorithm:
&#9679; Insertion
/*getnode(), which is used in all insertion algorithms, is a function which allocates the required memory space for creating a node*/
/*In all insertion algorithms address of the head pointer and the data to be inserted are passed as parameters; Algo_insgen which inserts a node at any position takes one extra parameter - the position where a node is to be inserted.*/
/*Algorithm to insert a node in the starting position of the linked list*/
Algo_insbeg(head,data)
{
/*The address of the newly created node is assigned to a node type pointer t*/
Step1: t = getnode();
Step2: t->data = data;
Step3: t->next = head;
Step4: head = t;
}

/*Algorithm to insert a node in the ending position of the linked list*/
Algo_insend(head,data)
{
if(head=NULL) /*The list is empty*/
{
Algo_insbeg(head,data);
exit;
}
Step1: Traverse the list until last node is reached;
/*The address of the newly created node is assigned to a node type pointer t*/
Step 2: t = getnode();
Step 3: t->data = data;
Step 4: t->next = NULL;
}

/*Algorithm to insert a node at any position of the linked list*/
Algo_insgen(head,data,pos)
{
Step1: Traverse the list until the previous node of the required position is reached;
Step 2: tmp = getnode();
Step 3: tmp->data = data;
Step 4: tmp->next = t;
Step 5: t = tmp;
}
&#9679; Deletion
/*In all deletion algorithms address of the head pointer is passed as parameter; Algo_deleteany which inserts a node at any position takes one extra parameter - the position of the node is to be deleted.*/
/*Algorithm to delete a node from the starting position of the linked list*/
Algo_deletebegin(head)
{
if(head=NULL)
exit;
Step1: p = head; /*p is a node type pointer*/
Step2: data = p->data;
Step3: head = p->next;
Step4: Deallocate the allocated memory space held by p;
return data;
}
/*Algorithm to delete a node from the ending position of the linked list*/
Algo_deleteend(head)
{
if(head=NULL)
exit;
Step1: Traverse the list until previous node of the last node is reached; Step2: p = t; /*p is a node type pointer*/
Step3: data = p->data;
Step4: t = NULL;
Step5: Deallocate the allocated memory space held by p;
return data;
}
/*Algorithm to delete a node from any position of the linked list*/
Algo_deleteany(head,position)
{
Step1: Traverse the list until the previous node of the required position is reached;
Step2: p = t; /*p is a node type pointer*/
Step3: data = p->data;
Step4: t = p->next;
Step5: Deallocate the allocated memory space held by p;
return data;
}
&#9679; Display
/*Algorithm to display all the nodes of the linked list*/
disp(head) /*Address of the head pointer is passed as parameter*/
{
print(Start->);
for(t=head;t!=NULL;t=t->next)
print(t->data);
print(NULL);
}
&#9679; Sort
/*Algorithm to sort all the nodes of the linked list in ascending order*/
Algo_sort(head) /*Address of the head pointer is passed as parameter*/
{
while(head!=NULL)
{
Step1: Find a node m with maximum data;
Step2: p = m;
Step3: m = m->next;
/*new is a newly created list where deleted maximum node from the
original list is inserted at each iteration*/
Step4: p->next = new;
Step5: new = p;
}
head = new;
}
&#9679; Reverse
/*Algorithm to reverse all the nodes of the linked list*/
Algo_reverse(head)
{
/*p, q, r are all node type pointers*/
q = head;
r = NULL;
while(q!=NULL)
{
Step1: head = r;
Step2: r = q;
Step3: q = q->next;
Step4: r->next = s;
}
head = r;
}
&#9679; Split

/* THIS ALGORITHM SPLIT THE LINK LIST */

void split(head)
{
struct node *p=head,head1;
int i,non=0;
if(head==NULL)
{
printf("n**********LINK LIST IS EMPTY**********");
return;
}
while(p!=NULL)
{
non++;
p=p->next;
}
for(p=head,i=1;i<non/2;i++)
{
p=p->next;
}
head1=p->next;
p->next=NULL;
printf("n 1st LINK LIST :- n");
disp (head);
printf("n 2nd LINK LIST :-n ");
disp (head1);
}

Program listing :
/*C program to perform insert, delete, display, sort, split and reverse operations on a singly linked list*/
#include<stdio.h>
#include<stdlib.h>
/*A node of the linked list is defined as a structure*/
typedef struct node
{
int data;
struct node*next;
}
node;
void main()
{
node*s=NULL;/*Initially the linked list is empty*/
void disp(node*);
void insbeg(node**,int);
void insend(node**,int);
int insgen(node**,int,int);
int deleteany(node**,int);
int deletebegin(node**);
int deleteend(node**);
void reverse(node**);
void sort(node**);
void split(node*);
int i,n,data,pos,ch,ch_ins,ch_del,con_op,nc,tmp;
nc=0;/*This variable is used to keep track of number of nodes in the linked list*/
printf("..........Linked list operation..........n");
while(1)
{
printf("n..........Main menu..........n");
printf("1.Insertn2.Deleten3.Displayn4.Sortn5.Reversen6.Splitn7.Exit.n");
printf("nEnter choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1:
{
con_op=1;
while(con_op!=0)
{
printf("Give data : ");
scanf("%d",&data);
printf("n..........List insertion submenu..........n");
printf("1.Insbeg.n2.Insend.n3.Any position.n");
printf("nEnter choice : ");
scanf("%d",&ch_ins);
switch(ch_ins)
{
case 1:
{
insbeg(&s,data);
nc++;
break;
}
case 2:
{
insend(&s,data);
nc++;
break;
}
case 3:
{
nc++;
printf("Enter position : ");
scanf("%d",&pos);
if(pos<0)
{
printf("nInvalid position.n");
nc--;
break;
}
if(insgen(&s,data,pos)==0)
{
printf("nInvalid position");
nc--;
}
break;
}
default:
{
printf("nInvalid choicen");
}
}
printf("nDo you want to continue insertion(if not insert 0) : ");
scanf("%d",&con_op);
}
break;
}
case 2:
{
con_op=1;
while(con_op!=0)
{
if(nc==0)
{
printf("nList is empty.n");
printf("Insert some elements first..!!n");
break;
}
printf("n..........List deletion submenu..........n");
printf("1.Delbeg.n2.Delend.n3.Any position.n");
printf("nEnter choice : ");
scanf("%d",&ch_del);
switch(ch_del)
{
case 1:
{
tmp=deletebegin(&s);
nc--;
break;
}
case 2:
{
tmp=deleteend(&s);
nc--;
break;
}
case 3:
{
nc--;
printf("Enter position to delete : ");
scanf("%d",&pos);
if(pos>=(nc+1)||pos<0)
{
printf("nInvalid position.n");
tmp=-1;
nc++;
break;
}
if((tmp=deleteany(&s,pos))==-1)
{
printf("Invalid position");
nc++;
}
break;
}
default:
{
printf("nInvalid choicen");
}
}
if(tmp!=-1)
printf("Deleted data is : %d",tmp);
printf("nDo you want to continue deletion(if not insert 0) : ");
scanf("%d",&con_op);
}
break;
}
case 3:
{ disp(s);
break;
}
case 4:
{
sort(&s);
printf("Sorted list is : n");
disp(s);
break;
}
case 5:
{
if(nc<2)
{
printf("Two elements must be inserted to visualize reverse operation : n");
break;
}
reverse(&s);
printf("Reversed list is : n");
disp(s);
break;
}
case 6:
{
split(s);
break;
}
case 7:
{
if(nc!=0)/*When list is not empty all the nodes will be deleted*/
{
printf("WARNING!!!!!!!!List is not empty....Nodes will be destroyed.");
while(s!=NULL)
deletebegin(&s);
}
disp(s);
return;
}
default:
printf("Invalid choice givenn");
}
}
}
/*Function to insert a node in the starting position of the linked list*/
void insbeg(node**s,int data)
{
node*t;
t=(node*)malloc(sizeof(node));
t->data=data;
t->next=*s;
*s=t;
}
/*Function to insert a node in the ending position of the linked list*/
void insend(node**s,int data)
{
node**t;
if(*s==NULL)/*The list is empty*/
{
insbeg(s,data);
return;
}
for(t=s;(*t)!=NULL;t=&((*t)->next));
*t=(node*)malloc(sizeof(node));
(*t)->data=data;
(*t)->next=NULL;
}
/*Function to display all the nodes of the linked list*/
void disp(node*s)
{
node*t;
printf("nStart->");
for(t=s;t!=NULL;t=t->next)
printf("%d->",t->data);
printf("NULLn");
}
/**Function to insert a node at any position of the linked list*/
int insgen(node**s,int data,int pos)
{
int i;
node**t;
node*tmp;
for(i=0,t=s;i<pos;i++,t=&((*t)->next))
{
if((*t)==NULL)
return 0;
}
tmp=(node*)malloc(sizeof(node));
tmp->data=data;
tmp->next=(*t);
(*t)=tmp;
}
/*Function to delete a node from the ending position of the linked list*/
int deleteend(node**s)
{
node*p;
node**t;
int dt;
if(*s==NULL)
return -1;
for(t=s;(*t)->next!=NULL;t=&((*t)->next));
p=(*t);
dt=p->data;
(*t)=NULL;
free(p);
return dt;
}
/*Function to delete a node from the starting position of the linked list*/
int deletebegin(node**s)
{
node*p;
int dt;
if(*s==NULL)
return -1;
p=*s;
dt=p->data;
*s=p->next;
free(p);
return dt;
}
/*Function to delete a node from any position of the linked list*/
int deleteany(node**s,int position)
{
node**t;
node*p;
int c=0;
int dt;
for(t=s,c=0;c<position;t=&((*t)->next),c++)
{
if((*t)==NULL)
return -1;
}
p=(*t);
dt=p->data;
(*t)=p->next;
free(p);
return dt;
}
/*Function to reverse all the nodes of the linked list*/
void reverse(node**x)
{
node*q;
node*r;
node*s;
q=*x;
r=NULL;
while(q!=NULL)
{
s=r;
r=q;
q=q->next;
r->next=s;
}
*x=r;
}
/*Function to sort all the nodes of the linked list in ascending order*/
void sort(node**s)
{
node**t;
node**m;
node*p;
node*new=NULL;
while(*s!=NULL)
{
for(t=s,m=s;(*t)!=NULL;t=&((*t)->next))
{
if((*m)->data<(*t)->data)
m=t;
}
p=(*m);
*m=(*m)->next;
p->next=new;
new=p;
}
*s=new;
}
/*Function to split the linked list*/
void split(node *s)
{

struct node *p=s,*s1;
int i,non=0;
if(s==NULL)
{
printf("n**********LINK LIST IS EMPTY**********");
return;
}
while(p!=NULL)
{
non++;
p=p->next;
}
for(p=s,i=1;i<non/2;i++)
{
p=p->next;
}
s1=p->next;
p->next=NULL;
printf("n 1st LINK LIST :- n");
disp(s);
printf("n 2nd LINK LIST :-n ");
disp(s1);
}

Output :
..........Linked list operation..........

..........Main menu..........
1.Insert
2.Delete
3.Display
4.Sort
5.Reverse
6.Split
7.Exit.

Enter choice : 1
Give data : 45

..........List insertion submenu..........
1.Insbeg.
2.Insend.
3.Any position.

Enter choice : 1

Do you want to continue insertion(if not insert 0) : 1
Give data : 22

..........List insertion submenu..........
1.Insbeg.
2.Insend.
3.Any position.

Enter choice : 2

Do you want to continue insertion(if not insert 0) : 1
Give data : 15

..........List insertion submenu..........
1.Insbeg.
2.Insend.
3.Any position.

Enter choice : 3
Enter position : 1

Do you want to continue insertion(if not insert 0) : 1
Give data : 89

..........List insertion submenu..........
1.Insbeg.
2.Insend.
3.Any position.

Enter choice : 3
Enter position : 2

Do you want to continue insertion(if not insert 0) : 1
Give data : 51

..........List insertion submenu..........
1.Insbeg.
2.Insend.
3.Any position.

Enter choice : 3
Enter position : 0

Do you want to continue insertion(if not insert 0) : 1
Give data : 77

..........List insertion submenu..........
1.Insbeg.
2.Insend.
3.Any position.

Enter choice : 3
Enter position : 6

Invalid position
Do you want to continue insertion(if not insert 0) : 1
Give data : 56

..........List insertion submenu..........
1.Insbeg.
2.Insend.
3.Any position.

Enter choice : 3
Enter position : 5

Do you want to continue insertion(if not insert 0) : 1
Give data : 78

..........List insertion submenu..........
1.Insbeg.
2.Insend.
3.Any position.

Enter choice : 3
Enter position : 4

Do you want to continue insertion(if not insert 0) : 1
Give data : 12

..........List insertion submenu..........
1.Insbeg.
2.Insend.
3.Any position.

Enter choice : 3
Enter position : 5

Do you want to continue insertion(if not insert 0) : 0

..........Main menu..........
1.Insert
2.Delete
3.Display
4.Sort
5.Reverse
6.Split
7.Exit.

Enter choice : 3

Start->51->45->15->89->78->12->22->56->NULL

..........Main menu..........
1.Insert
2.Delete
3.Display
4.Sort
5.Reverse
6.Split
7.Exit.

Enter choice : 2

..........List deletion submenu..........
1.Delbeg.
2.Delend.
3.Any position.

Enter choice : 1
Deleted data is : 51
Do you want to continue deletion(if not insert 0) : 1

..........List deletion submenu..........
1.Delbeg.
2.Delend.
3.Any position.

Enter choice : 2
Deleted data is : 56
Do you want to continue deletion(if not insert 0) : 1

..........List deletion submenu..........
1.Delbeg.
2.Delend.
3.Any position.

Enter choice : 3
Enter position to delete : 2
Deleted data is : 89
Do you want to continue deletion(if not insert 0) : 1

..........List deletion submenu..........
1.Delbeg.
2.Delend.
3.Any position.

Enter choice : 3
Enter position to delete : 6

Invalid position.

Do you want to continue deletion(if not insert 0) : 0

..........Main menu..........
1.Insert
2.Delete
3.Display
4.Sort
5.Reverse
6.Split
7.Exit.

Enter choice : 3

Start->45->15->78->12->22->NULL

..........Main menu..........
1.Insert
2.Delete
3.Display
4.Sort
5.Reverse
6.Split
7.Exit.

Enter choice : 4
Sorted list is :

Start->12->15->22->45->78->NULL

..........Main menu..........
1.Insert
2.Delete
3.Display
4.Sort
5.Reverse
6.Split
7.Exit.

Enter choice : 5
Reversed list is :

Start->78->45->22->15->12->NULL

..........Main menu..........
1.Insert
2.Delete
3.Display
4.Sort
5.Reverse
6.Split
7.Exit.

Enter choice : 6
Enter choice : 6

1st LINK LIST :-

Start->78->45->NULL

2nd LINK LIST :-

Start->22->15->12->NULL

..........Main menu..........
1.Insert
2.Delete
3.Display
4.Sort
5.Reverse
6.Split
7.Exit.

Enter choice :7
WARNING!!!!!!!!List is not empty....Nodes will be destroyed.
Start->NULL
Discussions :
● In the program, pointers should be manipulated carefully or pointer related errors (such as segmentation fault) may occur.
● The memory which is allocated during the program should be deallocated before exiting from the program.
● To obtain advantages of both doubly and circular linked lists the above program can be implemented using doubly-circular linked list.
● Insertion of an element at a specific point of a list is a constant-time operation, whereas insertion in a dynamic array may require moving half of the elements, or more.
● Linked lists by themselves do not allow random access to the data, or any form of efficient indexing. Thus, many basic operations - such as obtaining the last node of the list, or finding a node that contains a given data, or locating the place where a new node should be inserted - may require scanning most of the list elements.
● Dynamic arrays (as well as fixed-size array data structures) allow constant-time random access, while linked lists allow only sequential access to elements.
● Singly-linked lists, in fact, can only be traversed in one direction.
● Another disadvantage of linked lists is the extra storage needed for references, which often makes them impractical for lists of small data items.


Back to main directory:  C Assignment    Software Practical
Read more »


C program to find a particular element from an array using binary search method

Filed Under:

Program Statement :
Write a C program to find a particular element from an array using binary search method.

Theory :
Searching is an operation which finds the location of a given element in a list. The search is said to be successful or unsuccessful depending on whether the element that is to be searched is found or not.
Binary search method is very fast and efficient. This method requires that the list of elements be in sorted order. In this method, to search an element we compare it with the element present at the center of the list. If it matches the search is successful. Otherwise the list divided into two halves :-
1. One from 0th element to the center element (whose elements are smaller than the center element).
2. Another one is from center element to the last element (whose elements are greater than the center element).
Now if the searching element is smaller than the center element then searching will be done in the first half, otherwise in the second half.
This procedure is repeated till the element is found or division of half parts gives one element.
Suppose an array consists of 10 elements and 52 is the element that is to be searched.
It works as follows:-

Algorithm :
/* Lower bound and upper bound of the input array, searching element and the input array are passed as parameters */
Algo_bsrch(lb, ub,key, arr[])
{
while(lb<=ub)
{
mid_index = (lb+ub)/2;
If(key = arr[mid_index]) /* Searching element is at the mid-index */
Return mid_index;
Else If(key<arr[mid_index])
ub = mid_index-1;
Else
lb = mid_index+1;
}
Return False; /* Search is unsucessful */
}
/* End of Algo_bsrch */

Program listing :
/* C program to find a particular element from an array of elements using binary search method */

#include<stdio.h>
#define max 50 /*Defining maximum size of the array*/
void main()
{
int i,j,n,mid_index,a[max],lb,ub,s;
int bsrch(int,int,int,int[]);
printf("Give number of elements in the array : ");
scanf("%d",&n);
printf("nEnter the elements in ascending order : ");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
if(i!=0 && a[i]<a[i-1])
{
printf("!!!!!Invalid input!!!!!n");
printf("Enter an element greater than %dn",a[i-1]);
i--;
}
}
printf("nThe sorted array(in ascending order)is : ");
for(i=0;i<n;i++)
printf("%4dn",a[i]);
lb=0; /*Defining lower bound of the array*/
ub=n-1; /*Defining upper bound of the array*/
printf("nGive the value to search for : ");
scanf("%d",&s); /*Read the element to search from user*/
if((i=bsrch(lb,ub,s,a))==-1)
printf("nSearch unsuccessful.n");
else
printf("Search successful.nValue found at position : %dn",i+1); /*Search is successful and position where the element is found is printed*/
}

/*Lower bound and upper bound of the input array ,searching element and the input array are passed as parameters*/

int bsrch(int lb,int ub,int s,int a[]) /*function for binary search.
{
int mid_index;
while(lb<=ub)
{
mid_index=(lb+ub)/2;
/*Searching element is at the mid-index*/
if(s==a[mid_index])
return mid_index;
else if(s<a[mid_index])
ub=mid_index-1;
else
lb=mid_index+1;
}
return -1; /*Search is unsucessful*/
}

Output :
SET 1 :
Give number of elements in the array : 10
Enter the elements in ascending order : 12 31 33 41 55 67 72 91 112 158
The sorted array(in ascending order)is :
12
31
33
41
55
67
72
91
112
158

Give the value to search for : 91
Search successful.
Value found at position : 8


SET 2 :
Give number of elements in the array : 8
Enter the elements in ascending order : 15 21 55 61 77 81 97 118
The sorted array(in ascending order)is :
15
21
55
61
77
81
97
118
Give the value to search for : 41
Search unsuccessful.

Discussions :
● COMPLEXCITY OF BINARY SEARCH :
In the best possible case, the ITEM may occur at middle position. In this case, the search operation terminates in success with just one comparison.
After each comparison either the search terminates successfully or the size of the array remaining to be searched is about one half of the original size. So after j comparisons the array remaining to be examined is of size at most N/2j . In the worst case the search terminates when there are only one element remaining to be searched. Hence,
N/2j = 1
Or, N = 2j
Or, N = log2N
Thus in worst case, this method requires O(log2N) comparisons to search an element in the array. The maximum number of comparisons in binary search is limited to log n.
● ADVANTAGE :
The advantage of binary search method is that, in each iteration it reduces the number of elements to be searched from n to n/2. On the other hand, linear search method checks sequentially for every element, which makes it inefficient.
● DISADVANTAGE :
The disadvantage of binary search is that it works only on sorted lists. So when searching is to be performed on unsorted list then linear search is the only option.
● Alternatively if user input is an unsorted list then it can be made sorted by using any sorting method and after that we can imply binary search method on the list. But it is not feasible as complexity of the program will become much higher.


Back to main directory:  C Assignment    Software Practical
Read more »


C program to add, subtract and multiply two 2D matrix.

Filed Under:

PROBLEM STATEMENT:
Write a C program to add, subtract and multiply two 2D matrix.

THEORY:
In mathematics, a matrix is a rectangular array of numbers, such as

An item in a matrix is called an entry or an element. The example has entries 1, 9, 13, 20, 55, and 6. Entries are often denoted by a variable with two subscripts. Thus in the matrix above, a2,1 = 20. Matrices of the same size can be added and subtracted entry-wise and matrices of compatible sizes can be multiplied. These operations have many of the properties of ordinary arithmetic, except that matrix multiplication is not commutative, that is, AB and BA are not equal in general.

The sum A+B of two m-by-n matrices A and B is calculated entry-wise:
(A + B)i,j = Ai,j + Bi,j, where 1 ≤ i ≤ m and 1 ≤ j ≤ n.

The sum A+B of two m-by-n matrices A and B is calculated entry-wise:
(A - B)i,j = Ai,j - Bi,j, where 1 ≤ i ≤ m and 1 ≤ j ≤ n.

Multiplication of two matrices is defined only if the number of columns of the left matrix is the same as the number of rows of the right matrix. If A is an m-by-n matrix and B is an n-by-p matrix, then their matrix product AB is the m-by-p matrix whose entries are given by dot-product of the corresponding row of A and the corresponding column of B:

Matrix multiplication satisfies the rules (AB)C = A(BC) (associativity), and (A+B)C = AC+BC as well as C(A+B) = CA+CB (left and right distributivity).

ALGORITHM:
Begin
Begin function main
Read r1 //Row size of Array 1
Read c1 //Column size of Array 1
Read r2 //Row size of Array 2
Read c2 //Column size of Array 2

Allocate r1 and c1 to array a[ ][ ] and r2 and c2 to array b[ ][ ]

Print ’Enter elements of Matrix 1’
for i&#61663;0 to less than r1, increment i by 1
for j&#61663;0 to less than c1, increment j by 1
Read a[i][j]

Print ‘Enter elements of Matrix 2’
for i&#61663;0 to less than r2, increment i by 1
for j&#61663;0 to less than c2, increment j by 1
Read b[i][j]

Display Menu

do
Read ch
switch(ch)//Switching through the different functions according to choice
case 1:add(a,b,r1,c1,r2,c2)
break
case 2:sub(a,b,r1,c1,r2,c2)
break
case 3:mul(a,b,r1,c1,r2,c2)
break
case 4:Print ‘Terminating program’
break
if ch is not equal to any of the mentioned cases
Print ‘Wrong choice entered’
While ch is not equal to 4
End of function main

Begin function add(int **a,int **b,int r1,int c1,int r2,int c2)
if r1 is equal to r2 and c1 is equal to c2)
Print ‘The summation matrix is’
for i&#61663;0 to less than r1,increment i by 1
for j&#61663;0 to less than c1, increment j by 1
temp&#61663;a[i][j]+b[i][j]
Print temp
New Line
else
Print ‘The matrices cannot be added as we have different row and column no.s for the two matrices’
End function add

Begin function sub(int **a,int **b,int r1,int c1,int r2,int c2)
if r1 is equal to r2 and c1 is equal to c2)
Print ‘The difference matrix is’
for i&#61663;0 to less than r1,increment i by 1
for j&#61663;0 to less than c1, increment j by 1
temp&#61663;absolute value of (a[i][j]-b[i][j])
Print temp
New Line
else
Print ‘The difference cannot be found out as we have different row and column no.s for the two matrices’
End function sub

Begin function mul(int **a,int **b,int r1,int c1,int r2,int c2)
if c1 is equal to r2 //if row of 1st array and column of 2nd array is equal
for i&#61663;0 to less than r1,increment I by 1
for j&#61663;0 to less than c2, increment j by 1
sum&#61663;0
for k&#61663;0 to less than r2, increment k by 1 //loop to generate column of 1st and row of 2nd array
sum&#61663;sum+(a[i][k]*b[k][j])
Print sum
Newline
else
Print ’The matrices could not be multiplied because no. of columns in first matrix is not equal to no. of rows in second matrix’
End of function mul
End


PROGRAM LISTING:
//Program to add, subtract or multiply two 2D matrices.

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

void main()
{
int **a,**b,r1,r2,c1,c2,i,j,ch;
//Function prototypes
void add(int **,int **,int,int,int,int);
void sub(int **,int **,int,int,int,int);
void mul(int **,int **,int,int,int,int);

//Accepting row and column sizes from user
printf("Enter row and column sizes of Matrix 1 n");
printf("Row ");
scanf("%d",&r1);
printf("Column ");
scanf("%d",&c1);
printf("Enter row and column sizes of Matrix 2 n");
printf("Row ");
scanf("%d",&r2);
printf("Column ");
scanf("%d",&c2);

//Allocating memory to the 2D arrays
a=(int **)malloc(r1*sizeof(int *));
for(i=0;i<r1;i++)
a[i]=(int *)malloc(c1*sizeof(int));

b=(int **)malloc(r2*sizeof(int *));
for(i=0;i<r2;i++)
b[i]=(int *)malloc(c2*sizeof(int));

//Accepting array elements
printf("Enter elements of Matrix 1n");

for(i=0;i<r1;i++)
for(j=0;j<c1;j++)
scanf("%d",&a[i][j]);

printf("Enter elements of Matrix 2n");

for(i=0;i<r2;i++)
for(j=0;j<c2;j++)
scanf("%d",&b[i][j]);

clrscr();

//Displaying inputted arrays
printf("Array 1 is : n");

for(i=0;i<r1;i++)
{
for(j=0;j<c1;j++)
printf("%d ",a[i][j]);
printf("n");
}//end of loop i

printf("Array 2 is : n");

for(i=0;i<r2;i++)
{
for(j=0;j<c2;j++)
printf("%d ",b[i][j]);
printf("n");
}//end of loop i

printf("n");
printf(" MENU n");
printf(" 1.ADDITION n");
printf(" 2.DIFFERENCE n");
printf(" 3.MULTIPLICATION n");
printf(" 4.EXIT n");
printf("n");


do
{
printf("n");
printf("Enter choice n");
scanf("%d",&ch);//Accepting users choice
switch(ch)//Switching through the different functions according to choice
{
case 1:add(a,b,r1,c1,r2,c2);
break;
case 2:sub(a,b,r1,c1,r2,c2);
break;
case 3:mul(a,b,r1,c1,r2,c2);
break;
case 4:printf("Terminating program n");
break;
default:printf("Wrong choice entered n");
}//end of switch
}//end of do
while(ch!=4);
}//end of main

void add(int **a,int **b,int r1,int c1,int r2,int c2)
{
int i,j,temp;
if(r1==r2 && c1==c2)//If row and column sizes of both arrays match
{
printf("The summation matrix is :n");
for(i=0;i<r1;i++)
{
for(j=0;j<c1;j++)
{
temp=a[i][j]+b[i][j];
printf("%d ",temp);
}//end of loop j
printf("n");
}//end of loop i
}//end of if
else
printf("The matrices cannot be added as we have different row and column no.s for the two matrices n");
}//end of add

void sub(int **a,int **b,int r1,int c1,int r2,int c2)
{
int i,j,temp;
if(r1==r2 && c1==c2)//If row and column sizes of both arrays match
{
printf("The difference matrix is :n");
for(i=0;i<r1;i++)
{
for(j=0;j<c1;j++)
{
temp=abs(a[i][j]-b[i][j]);
printf("%d ",temp);
}//end of loop j
printf("n");
}//end of loop i
}//end of if
else
printf("The difference cannot be found as we have different row and column no.s for the two matrices n");
}//end of sub

void mul(int **a,int **b,int r1,int c1,int r2,int c2)
{
int i,j,k,sum;
if(c1==r2)//if row of 1st and column of 2nd array is equal
{
for(i=0;i<r1;i++)
{
for(j=0;j<c2;j++)
{
sum=0;
for(k=0;k<r2;k++)//loop to generate column of 1st and row of 2nd array
sum=sum+(a[i][k]*b[k][j]);
printf("%d ",sum);
}//end of loop j
printf("n");
}//end of loop i
}//end of if
else
printf("The matrices could not be multiplied because no. of columns in first matrix is not equal to no of rows in second matrix");
}//end of mul

OUTPUT:
Enter row and column sizes of Matrix 1
Row 3
Column 3
Enter row and column sizes of Matrix 2
Row 3
Column 3
Enter elements of Matrix 1
1
2
3
4
5
6
7
8
9
Enter elements of Matrix 2
1
2
3
4
5
6
7
8
9

Array 1 is :
1 2 3
4 5 6
7 8 9
Array 2 is :
1 2 3
4 5 6
7 8 9

MENU
1.ADDITION
2.DIFFERENCE
3.MULTIPLICATION
4.EXIT


Enter choice
1
The summation matrix is :
2 4 6
8 10 12
14 16 18

Enter choice
2
The difference matrix is :
0 0 0
0 0 0
0 0 0

Enter choice
3
30 36 42
66 81 96
102 126 150

Enter choice
4
Terminating program

DISCUSSION:
Matrix addition and subtraction can only be performed if the row and columns sizes of the two matrices are equal.
Matrix multiplication is not commutative. The size of the column of the first matrix should be equal to the size of the row of the second matrix.
Function prototypes should be defined before declaration of the functions
Keep a check for choice entered not in the list of options in the menu.



Back to main directory:  C Assignments    Software Practical
Read more »


C program to sort all the elements in a column of a 2D matrix in ascending order.

Filed Under:

PROBLEM STATEMENT: 
Write a C program to sort all the elements in a column of a 2D matrix in ascending order.

THEORY:
In the 2D array the elements are stored in row-major form. To traverse the array, column-major wise, the variable pointing to the column is kept constant and the variable pointing to the row is incremented. In this way the columns are traversed one by one and the content of each column is sorted using the Bubble Sort technique accordingly. The variable pointing to the column is incremented and the one pointing to the row is re-initialized with 0, to start of operations with a new column.

ALGORITHM:
Begin
Read r //Size of row
Read c //Size of column
Allocate row and column sizes to array
Print ‘Enter array elements’
for iß0 to less than r, increment i
for(jß0 to less than c, increment j
Read a[i][j]
Print ’The array is ‘
for iß0 to less than r, increment i by 1
for jß0 to less than c, increment j by 1
Print a[i][j]
Newline
//Sorting columns
for iß0 to less than c, increment i by 1 //Loop to traverse through different columns
for jß0 to less than r, increment j by 1 //Bubble sorting technique
for kß0 to less than (r-1), increment k by 1
//Swapping elements
if a[k][i] is greater than a[k+1][i]
tempßa[k][i]
a[k][i]ßa[k+1][i]
a[k+1][i]temp

Print ‘The array with sorted column’
for iß0 to less than r, increment i by 1
for jß0 to less than c, increment j by 1
Print a[i][j]
Newline
End

PROGRAM LISTING:
//Program to sort columns of a given 2D matrix

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

void main()
{
int **a,r,c,i,j,k,temp;
clrscr();
//Accepting row and column sizes from user
printf("Enter size of row n");
scanf("%d",&r);
printf("Enter size of column n");
scanf("%d",&c);

//Allocating memory to array
a=(int **)malloc(r*sizeof(int *));
for(i=0;i<r;i++)
a[i]=(int *)malloc(c*sizeof(int));

printf("Enter array elements n");
//Accepting array elements from user
for(i=0;i<r;i++)
for(j=0;j<c;j++)
scanf("%d",&a[i][j]);

printf("The array is : n");
//Displaying inputted array
for(i=0;i<r;i++)
{
for(j=0;j<c;j++)
printf("%d ",a[i][j]);
printf("n");
}

//Sorting columns
for(i=0;i<c;i++) //Loop to traverse through different columns
{
for(j=0;j<r;j++) //Bubble sorting technique
{
for(k=0;k<(r-1);k++)
{
if(a[k][i]>a[k+1][i])
{
//Swapping elements
temp=a[k][i];
a[k][i]=a[k+1][i];
a[k+1][i]=temp;
}//end of if
}//end of loop k
}//end of loop j
}//end of loop i

//Printing array with columns sorted
printf("The array with sorted column : n");

for(i=0;i<r;i++)
{
for(j=0;j<c;j++)
printf("%d ",a[i][j]);
printf("n");
}//end of loop i
}//end of main

OUTPUT:
Enter size of row
4
Enter size of column
4
Enter array elements
12
25
35
27
56
55
41
24
34
39
89
75
45
14
35
65
The array is :
12 25 35 27
56 55 41 24
34 39 89 75
45 14 35 65
The array with sorted column :
12 14 35 24
34 25 35 27
45 39 41 65
56 55 89 75

DISCUSSION:
The outer loop in the code to sort the elements of the array is meant for changing the index of the column after each column has been sorted.
The elements of the array can be swapped by summation followed by the subtraction technique instead of using a temporary variable.
The columns can be swapped using any kind of sorting algorithm and not just the bubble sort technique.



Back to main directory:  C++ Assignment    Software Practical
Read more »


C program to add all the elements of a 2D matrix row-wise, and display the elements of the row with the highest sum.

Filed Under:

PROBLEM STATEMENT:
Write a C program to add all the elements of a 2D matrix row-wise, and display the elements of the row with the highest sum.

THEORY: 
In the 2D array the elements are stored in row-major form. To traverse the array, row-major wise, the variable pointing to the row is kept constant and the variable pointing to the column is incremented. In this way the rows are traversed one by one and the sum of the elements of a row is stored at the last location of the row. The variable pointing to the row is incremented and the one pointing to the column is re-initialized with 0, to start of operations with a new row. Meanwhile, a variable in maintained which is updated with the highest sum as soon as it is encountered. Lastly, this variable is matched with the last column of the array, and the particular row is printed whose sum of elements matches the content of this variable.

ALGORITHM:
Begin
Begin function main
Read r1 //Row size of Array 1
Read c1 //Column size of Array 1
Read r2 //Row size of Array 2
Read c2 //Column size of Array 2

Allocate r1 and c1 to array a[ ][ ] and r2 and c2 to array b[ ][ ]

Print ’Enter elements of Matrix 1’
for iß0 to less than r1, increment i by 1
for jß0 to less than c1, increment j by 1
Read a[i][j]

Print ‘Enter elements of Matrix 2’
for iß0 to less than r2, increment i by 1
for jß0 to less than c2, increment j by 1
Read b[i][j]

Display Menu

do
Read ch
switch(ch)//Switching through the different functions according to choice
case 1:add(a,b,r1,c1,r2,c2)
break
case 2:sub(a,b,r1,c1,r2,c2)
break
case 3:mul(a,b,r1,c1,r2,c2)
break
case 4:Print ‘Terminating program’
break
if ch is not equal to any of the mentioned cases
Print ‘Wrong choice entered’
While ch is not equal to 4
End of function main

Begin function add(int **a,int **b,int r1,int c1,int r2,int c2)
if r1 is equal to r2 and c1 is equal to c2)
Print ‘The summation matrix is’
for iß0 to less than r1,increment i by 1
for jß0 to less than c1, increment j by 1
tempßa[i][j]+b[i][j]
Print temp
New Line
else
Print ‘The matrices cannot be added as we have different row and column no.s for the two matrices’
End function add

Begin function sub(int **a,int **b,int r1,int c1,int r2,int c2)
if r1 is equal to r2 and c1 is equal to c2)
Print ‘The difference matrix is’
for iß0 to less than r1,increment i by 1
for jß0 to less than c1, increment j by 1
tempabsolute value of (a[i][j]-b[i][j])
Print temp
New Line
else
Print ‘The difference cannot be found out as we have different row and column no.s for the two matrices’
End function sub

Begin function mul(int **a,int **b,int r1,int c1,int r2,int c2)
if c1 is equal to r2 //if row of 1st array and column of 2nd array is equal
for iß0 to less than r1,increment I by 1
for jß0 to less than c2, increment j by 1
sumß0
for kß0 to less than r2, increment k by 1 //loop to generate column of 1st and row of 2nd array
sumßsum+(a[i][k]*b[k][j])
Print sum
Newline
else
Print ’The matrices could not be multiplied because no. of columns in first matrix is not equal to no. of rows in second matrix’
End of function mul
End


PROGRAM LISTING:
//Program to print the row with the highest sum
#include<stdio.h>
#include<conio.h>
#include<malloc.h>

void main()
{
int **a,r,c,i,j,ans,max;
clrscr();
//Accepting size of row and column
printf("Enter size of row n");
scanf("%d",&r);
printf("Enter size of column n");
scanf("%d",&c);

//Allocating memory to array
a=(int **)malloc(r*sizeof(int *));
for(i=0;i<r;i++)
a[i]=(int *)malloc((c+1)*sizeof(int));

printf("Enter array elements n");

for(i=0;i<r;i++)
for(j=0;j<c;j++)
scanf("%d",&a[i][j]); //Accepting array elements from user

printf("The array is : n");

for(i=0;i<r;i++)
{
for(j=0;j<c;j++)
printf("%d ",a[i][j]); //Printing inputted array
printf("n");
}

for(i=0;i<r;i++)
{
ans=0;
for(j=0;j<c;j++)
{
ans=ans+a[i][j];//Sum of 'i'th row
if(i==0)
max=ans;//initializing max for the very first iteration
if(ans>=max)

max=ans;
a[i][c]=max;
}//end of if
}//end of loop j
}//end of loop i

//Printing
printf("The row with the highest sum is : n");
for(i=0;i<r;i++)
{
if(a[i][c]==max) //Check for multiple rows with similar maximum values
{
for(j=0;j<c;j++)
printf(" %d ",a[i][j]);
printf("n");
}//end of if
}//end of loop i
}//end of main

OUTPUT:
Enter size of row
6
Enter size of column
6
Enter array elements
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
17
16
15
14
13
12
11
10
11
9
8
7
6
5
4
3
2
1
The array is :
1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18
17 16 15 14 13 12
11 10 11 9 8 7
6 5 4 3 2 1
The row with the highest sum is :
13 14 15 16 17 18

DISCUSSION:
The variable which stores the highest sum of rows is not initialized with 0 or with any arbitrary number but with the sum of the elements of the first row to prevent any error arising if the sum of elements of a particular row happens to be 0 or less than the value with which the variable has been initialized.
The sum of each row is stored in the last cell of a particular row so that it can be used for comparison later. This value is compared with the value of the variable storing the highest sum right at the end and the elements of the row are printed if there is a match. This is helpful if there are multiple rows with the same sum of their elements.




Back to main directory:  C++ Assignment    Software Practical
Read more »


C program to implement a Di-stack.

Filed Under:

PROBLEM STATEMENT: 
Write a C program to implement a Di-stack.

THEORY:
 In computer science, a stack is a last in, first out (LIFO) abstract data type and data structure. A stack can have any abstract data type as an element, but is characterized by only two fundamental operations: push and pop. The push operation adds an item to the top of the stack, hiding any items already on the stack, or initializing the stack if it is empty. The pop operation removes an item from the top of the stack, and returns this value to the caller. A pop either reveals previously concealed items, or results in an empty stack.
When two stacks are implemented with the help of a single array such that the user can perform both push and pop operations on both the stacks considering the stack base of the first and second stack to be the first and last index location of the array respectively, it is known to be a Di-Stack.

ALGORITHM:
Begin
Initialize globally variables top1,top2 & s
Begin function main()
Read s //Size of di-stack
Allocate size s into array a
Initialize stack top pointers top1&#61663;-1,top2&#61663;s
do
Print ‘1. PUSH 2. POP 3. DISPLAY 4. EXIT ‘
Read ch //Users choice
switch ch
case 1:push(a)
break
case 2:pop()
break
case 3:display(a)
break
case 4:Print’Terminating’
break
If ch does not match any of the cases mentioned Print’Wrong choice entered, Enter again !!’
while ch is not equal to 4
End main
Begin function push //Function to implement push operation
Read ch //Stack no.
if (top1+1) is equal to (top2)
Print ‘Stack overflow, please pop elements before you push
else
switch ch
case 1: Increment top1 by 1
Read e //Accepting element
a[top1]&#61663;e
break

case 2: Decrement top2 by 1
Read e //Accepting element
a[top2]&#61663;e
break
If ch does not match any of the cases mentioned
Print ‘Wrong choice entered, enter again’
End function push

Begin function pop //Function to implement pop operation
Read ch //Accept stack no from user
Switch ch
case 1: if top1 is less than equal to -1
Print ‘There is no element in the stack to be popped’
else
Decrement top1 by 1
break

case 2: if top2 is less than equal to s
Print ‘There is no element in the stack to be popped’
else
Increment top2 by 1
break

If ch does not match any of the cases mentioned
Print ‘Wrong choice entered, enter again’
End function pop

Begin function display
Print ‘Stack 1 consists of ‘
for i&#61663;top1 is greater than equal to 0, Decrement i
Print a [i]
Print ‘Stack 2 consists of ‘
for i&#61663;top2 is less than s, Increment i
Print[i])
End function display
End

PROGRAM LISTING:
//Program to implement a push, pop and display operations for a DI-STACK
#include<stdio.h>
#include<conio.h>
#include<malloc.h>

//Global Variables
int top1,top2,s;

void main()
{
int *a;
int ch;
void push(int *);
void pop();
void display(int *);
clrscr();
//Accepting size of di-stack
printf("Enter size of di-stack n");
scanf("%d",&s);
a=(int *)malloc(s*sizeof(int));

top1=-1,top2=s;//Initializing stack pointers
do
{
printf("n");
printf(" 1. PUSH 2. POP 3.DISPLAY 4. EXIT n");
printf("n");
printf("Enter choice n");
scanf("%d",&ch);

//Switch through different operations according to users choice
switch(ch)
{
case 1:push(a);
break;
case 2:pop();
break;
case 3:display(a);
break;
case 4:printf("Terminating n");
break;
default:printf("Wrong choice entered,Enter again !! n");
}//end of switch
}//end of do
while(ch!=4);
}//end of main

//Function to implement push operation
void push(int *a)
{
int ch,e;
printf("Enter Stack No. n");
scanf("%d",&ch);

if((top1+1)==(top2))
printf("Stack overflow,please pop elements before you push n");
else
{
//switch operation to switch between the two stacks
switch(ch)
{
case 1: top1++;
printf("Enter element n");
scanf("%d",&e);
a[top1]=e;
break;

case 2: top2--;
printf("Enter element n");
scanf("%d",&e);
a[top2]=e;
break;

default:printf("Wrong choice entered,enter againn");
}//end of switch
}//end of else
}//end of push

//Function to implement pop operation
void pop()
{
int ch;
printf("Enter Stack No. n");
scanf("%d",&ch);

//switch operation to switch between the two stacks
switch(ch)
{
case 1: if(top1<=-1)
printf("There is no element in the stack to be popped n");
else
top1--;
break;

case 2: if(top2>=s)
printf("There is no element in the stack to be popped n");
else
top2++;
break;

default:printf("Wrong choice entered,enter againn");
}//end of switch
}//end of pop

//Function to implement display operation
void display(int *a)
{
int i;
clrscr();
//Printing stack 1
printf("Stack 1 consists of :n");
for(i=top1;i>=0;i--)
printf("%d n",a[i]);

//Printing stack 2
printf("Stack 2 consists of :n");
for(i=top2;i<s;i++)
printf("%d n",a[i]);
}//end of display

OUTPUT:
Enter size of di-stack
3

1. PUSH 2. POP 3.DISPLAY 4. EXIT

Enter choice
1
Enter Stack No.
1
Enter element
1

1. PUSH 2. POP 3.DISPLAY 4. EXIT

Enter choice
1
Enter Stack No.
1
Enter element
1

1. PUSH 2. POP 3.DISPLAY 4. EXIT

Enter choice
1
Enter Stack No.
1
Enter element
1

1. PUSH 2. POP 3.DISPLAY 4. EXIT

Enter choice
2
Enter Stack No.
1

1. PUSH 2. POP 3.DISPLAY 4. EXIT

Enter choice
2
Enter Stack No.
1

1. PUSH 2. POP 3.DISPLAY 4. EXIT

Enter choice
1
Enter Stack No.

2
Enter element
2

1. PUSH 2. POP 3.DISPLAY 4. EXIT

Enter choice
1
Enter Stack No.
2
Enter element
3

1. PUSH 2. POP 3.DISPLAY 4. EXIT

Enter choice
3

Stack 1 consists of :
1
Stack 2 consists of :
3
2

1. PUSH 2. POP 3.DISPLAY 4. EXIT

Enter choice
4
Terminating

DISCUSSION:
Keep a check for overflow and underflow conditions.
Keep a check for choice entered not in the list of options in the menu.
Define function prototypes before writing down the function itself.




Back to main directory:  C++ Assignment    Software Practical
Read more »


C program to implement Warshall's algorithm to produce reachability matrix of a directed graph.

Filed Under:

Program Statement :
Write a C program to implement Warshall's algorithm to produce reachability matrix of a directed graph.

Theory :
Warshall's algorithm is one of the shortest path algorithms in graph theory. By this classical algorithm we can determine whether there is a path from any vertex vi to another vertex vj either directly or through one or more intermediate vertices. In other words we can test the reachability of all pairs of vertices in a graph. A directed graph is taken as input in the form of a vertex by vertex binary matrix such that w(i,j) = 0 if vertices vi and vj has no direct path between them and w(i,j) = 1 if there is a direct path from vi to vj. The output of the algorithm is also a binary matrix of same order as input where we can find reachability between all pair of vertices. Three for loops are used in the program and the number of times the outermost loop iterates is same as the number of vertices in the graph. For example - if number of vertices are 5 then we get the output matrix after 5th iteration. For each iteration k, it decides whether there is a path from vi to vj either directly or via k i.e from vi to vk and then from vk to vj. It therefore sets the matrix entries to 0 or 1 accordingly.

Algorithm :
Algo_warshall(w[size][size], n) /* The input graph and no. of vertices n passed as parameters */
{
For(k=1 to n) /* k represents table no. */
{
For(i=1 to n) /* i represents row no. within a table */
{
For(j=1 to n) /* j represents column no. within a row */
{
/*Exsisting 1 entries will be kept and 0 entries may or maynot be changed*/ w[i][j] = w[i][j] OR (w[i][k] AND w[k][j]);
}
}
}
}
/* End of Algo_warshall */

Program listing :
/* C program to implement Warshall's algorithm which will produce reachability matrix of a directed graph */
#include<stdio.h>
#define size 10 /*Defining maximum size of the matrix*/
main()
{
int a[size][size];
int i,j,k,n;
void warshall(int[][j],int);
printf("Enter no. of vertices : ");/*Number of vertices should be less or equal to the defined size*/
scanf("%d",&n);
/*Enter 1 if ith vertex and jth vertex has directed path else enter 0*/
printf("Give the initial graph(in binary matrix form):n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
printf("Enter the value of a[%d][%d]:",i,j);
scanf("%d",&a[i][j]);
}
}
warshall(a,n);/* Function declaration*/
printf("The final matrix where we can find the presence of directed path :n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
printf("%5d",a[i][j]);
printf("n");
}
}
void warshall(int a[size][size],int n)/*Function definition*/
{
int k,i,j;
for(k=0;k<n;k++)/*n is the no.of vertices of the graph and k represents table no.*/
{
for(i=0;i<n;i++)/*i represents row no. within a table*/
{
for(j=0;j<n;j++)/*j represents column no. within a row*/
{
a[i][j]=a[i][j]||(a[i][k] && a[k][j]);/*Exsisting 1 entries will be kept and 0 entries may or maynot be changed*/
}
}
}
}

Output :
Enter no. of vertices : 5
Give the initial graph(in binary matrix form):
Enter the value of a[0][0]:0
Enter the value of a[0][1]:1
Enter the value of a[0][2]:1
Enter the value of a[0][3]:0
Enter the value of a[0][4]:0
Enter the value of a[1][0]:0
Enter the value of a[1][1]:0
Enter the value of a[1][2]:0
Enter the value of a[1][3]:1
Enter the value of a[1][4]:1
Enter the value of a[2][0]:0
Enter the value of a[2][1]:1
Enter the value of a[2][2]:0
Enter the value of a[2][3]:0
Enter the value of a[2][4]:0
Enter the value of a[3][0]:0
Enter the value of a[3][1]:0
Enter the value of a[3][2]:1
Enter the value of a[3][3]:0
Enter the value of a[3][4]:1
Enter the value of a[4][0]:0
Enter the value of a[4][1]:0
Enter the value of a[4][2]:0
Enter the value of a[4][3]:0
Enter the value of a[4][4]:0

The final matrix where we can find the presence of directed path :
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1
0 0 0 0 0

Discussions :
● Number of vertices of the graph must be less than the defined size (or dimension) of the input weight-matrix.
● Weights of edges of the graph given as input must be non-negative real numbers otherwise it will not produce desirable result.
● The complexity of this algorithm is O(n3) and can be solved in polynomial time.
● We can also check existence of a circuit in a directed graph by this algorithm. If we get atleast one diagonal entry 1 in the output matrix then the graph has atleast one circuit.



Back to main directory:  C++ Assignment    Software Practical
Read more »


C program to implement Prim's algorithm which generates a minimal spanning tree of a weighted connected graph given as input.

Filed Under:

Program Statement :
Write a C program to implement Prim's algorithm which generates a minimal spanning tree of a weighted connected graph given as input.

Theory :
In computer science, Prim's algorithm is an algorithm that finds a minimal spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in this newly constructed tree is minimized. Prim's algorithm is an example of a greedy algorithm. It constructs minimal spanning tree considering vertices of the graph one by one and any one vertex can be chosen as the starting vertex.
To implement this algorithm ,a graph is taken as input in the form of a vertex by vertex matrix such that:
● w(i,j) = 0 if vertices vi and vj has no path between them and
if vi and vj are connected by an edge then
● w(i,j) = weight of that edge.
We also need a selected[] array which keeps track of the state of the vertices.
● selected[i] = False denotes ith vertex is not yet visited or selected.
● selected[i] = True denotes ith vertex is already visited.
The limitation of this algorithm is it cannot generate all possible minimal spanning trees for a given graph.

Algorithm :
/* The input graph,number of vertices and the starting vertex are passed as parameters */
Algo_prim(a[size][size],n,vs)
{
Initially no vertices are included in selected[];
for(i = 1 to n)
{
for(j = 1 to n)
tree[i][j] = 0; /*Initially spanning tree is empty*/
}
vs is included in selected[]; /*Starting vertex is selected at first*/
while(all the vertices are not selected)
{
min=infinity;
for(i=1 to n)
{
if(ith vertex is already selected)
{
for(j = 1 to n)
{
if(jth vertex is not already selected)
{
if(there is a path between ith and jth vertex)
{
/*Search for an edge with minimum weight*/
if(min>a[i][j])
{
min=a[i][j];
x=i;
y=j;
}
}
}
}

}
}
/*Updation of previous cost by adding it to cost of newly selected edge*/
cost = cost+min;
/*The newly selected edge is included in the minimal spanning tree*/
tree[x][y] = min;
selected[y] = True;
}
print(tree);
return cost;
}/* End of Algo_prim */

Program listing :
/*C program to implement Prim's algorithm which generates a minimal spanning tree of a weighted connected graph given as input*/

#include<stdio.h>
#define inf 9999
#define size 10/*Defining maximum number of vertices of the input graph*/
#define True 1
#define False 0
void main()
{
int a[size][size],i,j,n,vs,min_weight;
int prim(int[][j],int,int);
printf("Enter the number of vertex : ");
scanf("%d",&n);
printf("Enter a weighted matrix(with weights) as input : n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
printf("Enter the value of a[%d][%d] : ",i,j);
scanf("%d",&a[i][j]);
}
}
printf("The entered matrix is : n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
printf("%dt",a[i][j]);
printf("n");
}
printf("Enter starting vertex: v");
scanf("%d",&vs);/*Read the starting vertex from user*/
if(vs<0||vs>n-1)/*Checking validity of the starting vertex given by the user*/
{
printf("!!!!!ERROR!!!!!n");
printf("!!!!!Invalid vertex given!!!!!");
return;
}
printf("nSelected order of edges : ");
min_weight=prim(a,n,vs); //call the prim function
printf("n");
printf("Minimum weight :%d",min_weight);/*The total weight of the minimal spanning tree is displayed in the output*/
}
/*The input graph,number of vertices and the starting vertex are passed as parameters*/
int prim(int a[size][size],int n,int vs)
{
int selected[size],tree[size][size],nv,i,j,x,y,cost=0,min;
for(i=0;i<n;i++)
selected[i]=False;/*Initially no vertices are selected*/
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
tree[i][j]=0;/*Initially spanning tree is empty*/
}
selected[vs]=True;/*Starting vertex is selected at first*/
nv=1;
while(nv<n)/*Iteration will be considered until all the vertices are selected*/
{
min=inf;/*min is initialized by a large value*/
for(i=0;i<n;i++)
{
if(selected[i]==True)/*Iteration will be considered iff i th vertex is already selected*/
{
for(j=0;j<n;j++)
{
if(selected[j]==False)/*Iteration will be considered iff j th vertex is not already selected*/


{
if(a[i][j]!=0)/*Iteration will be considered iff there is a path between i th and j th vertex*/
{
if(min>a[i][j])/*Search for an edge with minimum weight*/
{
min=a[i][j];
x=i;
y=j;
}
}
}
}
}
}
cost=cost+min;/*Updation of previous cost by adding it to cost of newly selected edge*/
tree[x][y]=min;/*The newly selected edge is included in the minimal spanning tree*/
selected[y]=True;
nv++;
printf("(v%d,v%d)->",x,y);
}
printf("b bb ");
printf("n");
printf("nThe spanning tree is(with weights) : n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
printf("%dt",tree[i][j]);
printf("n");
}
return cost;
}

Output (FOR GRAPH G):
Enter the number of vertex : 6
Enter a weighted matrix(with weights) as input :
Enter the value of a[0][0] : 0
Enter the value of a[0][1] : 3
Enter the value of a[0][2] : 11
Enter the value of a[0][3] : 0
Enter the value of a[0][4] : 0
Enter the value of a[0][5] : 0
Enter the value of a[1][0] : 3
Enter the value of a[1][1] : 0
Enter the value of a[1][2] : 5
Enter the value of a[1][3] : 4
Enter the value of a[1][4] : 2
Enter the value of a[1][5] : 0
Enter the value of a[2][0] : 11
Enter the value of a[2][1] : 5
Enter the value of a[2][2] : 0
Enter the value of a[2][3] : 1
Enter the value of a[2][4] : 0
Enter the value of a[2][5] : 0
Enter the value of a[3][0] : 0
Enter the value of a[3][1] : 4
Enter the value of a[3][2] : 1
Enter the value of a[3][3] : 0
Enter the value of a[3][4] : 10
Enter the value of a[3][5] : 8
Enter the value of a[4][0] : 0
Enter the value of a[4][1] : 2
Enter the value of a[4][2] : 0
Enter the value of a[4][3] : 10
Enter the value of a[4][4] : 0
Enter the value of a[4][5] : 9
Enter the value of a[5][0] : 0
Enter the value of a[5][1] : 0
Enter the value of a[5][2] : 0
Enter the value of a[5][3] : 8
Enter the value of a[5][4] : 9
Enter the value of a[5][5] : 0
The entered matrix is :
0 3 11 0 0 0
3 0 5 4 2 0
11 5 0 1 0 0
0 4 1 0 10 8
0 2 0 10 0 9
0 0 0 8 9 0
Enter starting vertex: v4
Selected order of edges : (v4,v1)->(v1,v0)->(v1,v3)->(v3,v2)->(v3,v5)
The spanning tree is(with weights) :
0 0 0 0 0 0
3 0 0 4 0 0
0 0 0 0 0 0
0 0 1 0 0 8
0 2 0 0 0 0
0 0 0 0 0 0
Minimum weight :18

Discussions :
● The time complexity of Prim's algorithm (using simple weighted matrix form) is O(n2), where n is the number of vertices of the graph.
● Using a simple binary heap data structure and an adjacency list representation, Prim's algorithm can be shown to run in time O(| E | log | V |) where | E | is the number of edges and | V | is the number of vertices. Using a more sophisticated Fibonacci heap, this can be brought down to O(| E | + | V | log | V |), which is significantly faster when the graph is dense enough that | E | is Ω(| V |).
● Prim's algorithm can also be used for generating maximal spanning tree of a weighted connected graph. In that case edges with maximum weights are to be included in the spanning tree.
● Minimal or maximal spanning tree can also be generated by Kruskal's algorithm which generates such a tree by including edges one by one, whereas Prim's algorithm considers vertices one by one.
● Prim's algorithm has less overhead than Kruskal's algorithm.
● Prim’s algorithm is advantageous over Kruskal’s algorithm in finding the shortest spanning tree in a graph. It is faster and more convenient to use Prim’s algorithm than Kruskal’s.




Back to main directory:  C++ Assignment    Software Practical
Read more »