|
Data Structure Using C
Question : Explain the Dynamic Memory Allocation and following function.
When we declare an array in out program, the compiler allocates memory to hold the array prior to providing it. Some times it is required to change the size of the array and in that case it is required to edit and compile the program. To reduce the number of changes, it is required to allocate required memory during the run-time. For example, suppose we want to read a file into memory from the disk. If the size of file is not known and we have to load it into memory and defining very large array, so that file can fit into the array. If the size of the array is larger than that of file then the space is wasted. If the size of file is larger then it is not possible to load the complete file into the array, leading to need for dynamic memory allocation. In the dynamic memory allocation we use a pointer variable and it’s size is allocated during the execution of the program. There are two principle functions in C which are used to allocate required memory to pointer variable.
1. malloc()
2. calloc()
Both the malloc() and calloc() functions performs the operations and checks memory availability, based on the memory block size requested. When a suitable segment of memory is located. A pointer to the address of the allocated block is returned by the function.
1. malloc()
This function is used to allocate a requested number of bytes from the free pool of memory, and returns a pointer to a block of contiguous memory of the size specified.
This function allocates a block of memory and returns a pointer which points the first byte of the allocated space or memory block and if memory allocation was not successful, it returns a NULL pointer.
Syntax :
<pointer> = (<cast type> *) malloc(<no. of bytes to be allocated>);
“Pointer” is the name of a pointer of type cast type.
The malloc() functions returns a pointer of cast type to an area of memory with size as no. of bytes to be allocated.
Example:
mpointer = (int *) malloc(50 * sizeof(int));
After the successful execution of the above statement, a memory space equivalent to “50 times the size of an int” is reserved, and the address of the first byte of this block of memory allocated is assigned to the pointer mpointer of type int.
If an integer takes 2 bytes of storage space, the above declaration will allocate 100 bytes of contiguous storage space.
The malloc() function always returns a pointer to the first byte of the block of memory that has been allocated. It allocates a contiguous block of memory. If the allocation fails, i.e. malloc() is not able to allocate the required bytes of memory as a contiguous block, it returns NULL pointer.
2. calloc()
‘C’ also provides the calloc() function for allocating memory.
This function is normally used to request memory allocation at run time for storing derived data types such as arrays and structures.
calloc() function allocates multiple blocks of storages, each block of the same size and then sets all the bytes of memory in the block to zero.
Syntax:
<pointer> = (<cast-type> *) calloc(<no. of blocks>, <size of element>);
The calloc() function allocates contiguous space of “no. of block”, each block being of size, “size of element”. All the bytes of memory allocated are then initialized to zero, and a pointer to the first byte of the allocated contiguous memory is returned. In case, there is not enough memory available in the free pool of memory, a NULL pointer is returned.
3. free()
When we are dynamically allocating memory for variables at run time, the memory is not automatically released to the system. It is responsibility of a programmer, who has dynamically allocated memory, to released the memory to the free pool of memory when the memory is not needed.
‘C’ provides the free() function to release a block of memory that was allocated and is no longer needed.
Syntax:
free(<pointer>);
“pointer” is a pointer to the memory block that was returned by either malloc() and calloc() function calls.
4. realloc()
After, memory has been allocated to variables at run time, there may be a need to change the size of block of memory that was allocated. ‘C’ provides the realloc() function, using which the memory can be reallocated to increase or decrease the size of allocated memory.
Syntax:
<pointer> = realloc(<pointer>, <new memory size>);
“pointer” is the pointer that points the first byte of the memory that was allocated using either malloc() or calloc() functions.
“new memory size” indicates the new size of memory that is to be allocated. This new size could be more or less than the original size.
It is important to note here that the new block of memory may or may not begin at the same place as the old block.
In case, the functions fails to reallocate a larger memory in contiguous block at the location, it will create the same as an entirely new region and move the contents of the old block into the new block. The function guarantees that the old data will remain intact.
If the realloc() function fails to allocates additional space, it returns the NULL pointer and the original block is lost. Therefore, it is necessary for a programmer to test for the success of the function before reallocating memory, so that, old data is not lost.
Question: Explain DATA STRUCTURE and types of DATA STRUCTURE.
DATA STRUCTURE is a collection of data elements whose organization is characterized by assessing operations that are used to store and retrieve the individual data elements; the implementation of the composite data members in an abstract data type. An abstract data type can be define as a data type whose properties are specified independently of any particular implementation.
The DATA STRUCTURE is classified in the following categories:
1. Linear Data Structures
In the linear Data Structures processing of data items is possible in linear fashion, i.e., data can be processed one by one sequentially. Linear data structures contains following types of data structures.
I. Array
II. Linked List
III. Stack and Queues
2. Nonlinear Data Structures
A Data Structures in which insertion and deletion is not possible in a linear fashion is called nonlinear DATA STRUCTURE. In this category of DATA STRUCTURE, we will discuss the following.
I. Tree
II. Graph
Question: What is Primitive and Non-primitive Datastructure (Datatypes)?
Primitive Datastructure:
This is the data structure that typically are directly operated upon by machine-level instructions. We will present storage representations for these data structures for a variety of machines. For example, declaration of variables with basic datatypes are the example of primitive data structure.
Non-Primitive Datastructure:
Non-primitive data structures can be classified as arrays, lists and files. As array is an ordered set which consists of a fixed number of objects. No deletion or insertion operations are performed on arrays. A list, on the other hand, is an ordered set consisting of a variable number of elements to which insertions and deletions can be made.
Question: What is STACK? Explain the operations of STACK with example.
A STACK is defined formally as a list (a linear DATA STRUCTURE) in which all insertion and deletions are made at one end called the Top Of Stack (TOS). The fundamental operations, which are possible on a stack, are:
1. Push à Insertion
2. Pop à Deletion
3. Peep à Extract Information
4. Update à Update information associated at some location in the stack.
The most recently pushed element can be checked prior to performing a pop operation. A stack is based on the Last In First Out algorithm (LIFO) in which insertion and deletion operations are performed at one end of a stack. Also, the information can only be removed in the opposite order in which it was added to the stack. The most accessible information in a stack is at the top of stack and least accessible information is at the bottom of the stack.
For example, consider a stack of plates on the counter in a cafeteria. During the dinner time customers take plates from the top of the stack and waiter puts the washed plates on the top of the stack. The plate that is put most recently on the stack is the first one to bed taken off. The plate at the bottom is the last one to be used. This discussion can further be understood with the help of following figure.
A pointer TOS keeps track of the top most information in the STACK. Initially when the stack is empty, TOS has a value zero and when the stack contains a single information TOS has a value one and so on. Before an item is pushed onto the stack, the pointer is incremented by one. The pointer is decrement by one each time a deletion is made from the stack.
The Use Of STACK.
We have already discussed that a stack is a list and hence any of the list implementation techniques may be used to implement a stack. Two common use of stack are through:
1. Pinter (Linked List)
2. Array
The Algorithm Of STACK.
1. Push Operation:
Push means to insert an item onto the stack. The push algorithm is illustrated below. The algorithm illustrated inserts an item to the top of stack, which is represented by array S and containing Size number of items with a pointer Tos denoting the position of top most item in the stack.
Step 1 : [check for stack overflow]
If Tos >= Size
Output “Stack is Overflow” and exit
Step 2 : [Increment the Pointer value by one]
Tos = Tos + 1
Step 3 : [perform insertion]
S[Tos] = Value
Step 4 : Exit
2. Pop Operation:
The pop operation deletes or removes the topmost item from the stack. After removal of top most information, new value of the pointer Tos becomes the previous value of Tos that is Tos = Tos – 1 and freed position is allocated to free space. The algorithm to remove an item from the stack is illustrated below.
Step 1 :[check whether the stack is empty]
If Tos = 0
Output “Stack underflow” and exit
Step 2 :[Remove the Tos information]
Value = S[Tos]
Tos = Tos – 1
Step 3 :[Return the former information of the stack]
Return (Value)
/*USE OF THE STACK USING ARRAYS */
#include<stdio.h>
#define SIZE 5
int arr[SIZE];
int tos=0;
main()
{
int ans;
clrscr();
do
{
printf("1. Enter the New Element :\n");
printf("2. Remove The Element :\n");
printf("3. Display Stack :\n");
printf("4. Exit :\n");
printf("Enter Your Choice :");
scanf("%d",&ans);
switch(ans)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
break;
default:
printf("You Have Entered Wronge Choice...\n");
}
}while(ans != 3);
getch();
return;
}
push()
{
int newitem;
if(tos >= SIZE)
{
printf("The STACK is Full....\n");
return;
}
else
{
printf("Enter the New Value :");
scanf("%d",&newitem);
arr[tos]=newitem;
tos++;
}
getch();
return;
}
pop()
{
int remitem;
if(tos <= 0)
{
printf("The STACK is Empty....\n");
return;
}
else
{
tos--;
remitem = arr[tos];
printf("The Removeble item is %d.\n",remitem);
}
getch();
return;
}
display()
{
int x;
if(tos<=0)
{
printf("Your STACK is Empty....\n");
return;
}
else
{
while(tos>=0)
printf("%d ",arr[--tos]);
}
getch();
return;}
/* USE OF STACK USING POINTER AND STRUCTURE. */
#include<stdio.h>
#define SIZE 5
struct library
{
int b_no[SIZE];
}*book;
int cnt=0;
main()
{
int ans;
clrscr();
do
{
printf("1. Enter the New Element :\n");
printf("2. Remove The Element :\n");
printf("3. Exit :\n");
printf("Enter Your Choice :");
scanf("%d",&ans);
switch(ans)
{
case 1:
push(book);
break;
case 2:
pop(book);
break;
case 3:
break;
default:
printf("You Have Entered Wronge Choice...\n");
}
}while(ans != 3);
getch();
return;
}
push(struct library *bk)
{
int newitem;
if(cnt >= SIZE)
{
printf("The STACK is full...\n");
return;
}
else
{
printf("Enter the New Value :");
scanf("%d",&newitem);
bk->b_no[cnt++] = newitem;
}
getch();
return;
}
pop(struct library *bk)
{
int remitem;
if(cnt <= 0)
{
printf("The STACK is empty...\n");
return;
}
else
{
remitem = bk->b_no[--cnt];
printf("The Removeble item is %d\n",remitem);
}
getch();
return;
}
Question: Explain the Applications of STACK.
There are three applications in which stacks are used. The first application deals with recursion. Recursion is an important facility in many programming languages such as ALGOL 60 and PASCAL. There are many problems whose algorithmic description is best described in a recursive manner.
The second application of a stack is classical; it deals with the compilation of infix expressions into object code.
The third application of a stack is stack machine. Certain computers perform stack operations at the hardware or machine level, and these operations enable insertions to and deletions from a stack to be made very rapidly.
1. Recursion:
The natural numbers have been defined recursively through the process of induction. Recursion is the name given to the technique of defining a set or a process in terms or itself.
1, if N = 0
N * FACTORIAL(N-1), otherwise
The factorial function, whose domain is the natural numbers, can be recursively defined as,
FACTORIAL(N) =
Here the FACTORIAL(N) is defined in terms of FACTORIAL(N-1), which in turn is defined in terms of FACTORIAL(N-2), etc. until finally FACTORIAL(0) is reached, whose value is given as “one”. The basic idea is to define a function for all its argument values in a constructive manner by using induction. The value of a function for a particular argument value can be computed in a finite number of steps using the recursive definition, where at each step of recursion we get nearer to the solution.
2. Classical (Polish Expression and Their Compilation) :
In this section we shall primarily concerned with the mechanical evaluation or compilation of infix expressions. We shall find it to be more efficient to evaluate an infix arithmetical expression by first converting it to a suffix expression and then evaluating the latter. This approach will eliminate the repeated scanning of an infix expression in order to obtain its value.
3. Stack Machines:
One of the main problems with using machines which have a very limited number of registers is how to handle the storage of intermediate results. In particulars, we must be very cognizant of the generation of wasted store/load instruction sequences. In this sections we illustrate how the presence of the simple stack operations of POP and PUSH can enhance the process of generating code from a reverse-polish string. The instructions available for this machine are given in mnemonic form as follows:
1. PUSH<name> - Load from memory onto stack. This instructions loads an operand from the memory location named <name> and places the contents of <name> on the stack.
2. POP <name> - Store top of stack in memory. The contents of the top of the stack are removed and stored in the memory location referenced by <name>.
3. ADD, SUM, MUL, DIV – Arithmetic operation.
Question: Explain Polish Notation.
The process of writing the operators of an expression either before their operands or after them is called the Polish notation in honor of its discoverer, the Polish mathematician jan Luksiewicz. The fundamental property of Polish notation is that the order in which the operations are to be performed is completely determined by the position of the operators and operands in the expression. Accordingly, one never needs parenthesis when writing expression in Polish notation. The Polish notations are classified into three categories. These are:
1. Infix
2. Prefix
3. Postfix
1. Infix:
When the operators exist between two operands then the expression is called Infix expression. For example, let a + b * c is an expression, by inspecting we find that the operator + exists between the operands a and b, and operator * exists between the operands b and c, hence we say that a + b * c is an infix expression.
2. Prefix:
When the operators are written before their operands then the resulting expression is called the prefix Polish notation. Suppose we want to change the infix expression a + b * c it’s prefix form. First of all we consider the precedence of the operators present in the infix expression. Here in the given infix expression there are two operands + and *. The precedence of the * is higher than that of the +. The step which are required to change infix expression a + b * c into it’s equivalent prefix form are as follows:
Step 1 : a + * b c
Step 2 : + a * b c
3. Postfix:
When the operators come after their operands the resulting expression is called the reverse Polish notation or postfix expression.
For example, suppose a + b * c is an infix expression then after changing this expression into post form we get
Step 1 : a + b c *
Step 2 : a b c * +
Question: Explain Linear queues with algorithm and example.
This is a linear list DATA STRUCTURE used to represent a linear list and permits deletion to be performed at one end of the list and the insertion at the other end. The information in such a list is processed in the same order as it was received, that is on first-come-first-out (FIFO) basis. The Railway Reservation counter is an example of queue where the people collect their tickets on the first-come-first-serve (FIFS) basis. There are two types of operations possible on the linear queue.
1. Insertion (from rear side)
2. Deletion (from front side)
USE OF QUEUE :
Two common ways in which queues may be implemented are as follows:
1. Arrays
2. Pointers
(Draw the figure)
A queue has two pointers front and rear, pointing to the front and rear elements of the queue, respectively. Consider a queue Q consisting of n elements and an elements Value, which we have no insert into the Q. The value NULL (0) of front pointer implies an empty queue and the MAXVALUE implies the queue is full.
ALGORITHM OF QUEUE:
1. Insert Operation:
Insert operation inserting the new value from the rear side (right hand side). The first value is arranged in the queue as a left most value (in queue as first value) and second value is also inserted on rear side and set behind first value. Thus, each new value is set behind the previous entered value.
Step 1: [Check overflow condition]
if rear >= size
Output “Overflow” and return
Step 2: [Increment rear pointer]
Rear = rear + 1
Step 3: [Insert an element]
Q [rear] = value
Step 4: [Set the front pointer]
If front = 0
front = 1
Step 5: return
(here draw the box figure of inserting of node.)
2. Deletion Operation:
Deletion Operation is used to remove the values in the queue. It is works on the first-in-first-out (FIFO) basis, means, it is removed item from the front side (at the right hand side of the queue). This operation is removed first entered item after second entered item and so on in the queue.
Step 1: [Check underflow condition]
if front = 0
Output “Underflow” and return
Step 2: [Remove an element]
Value = Q [front]
Step 3: [Check for empty queue]
If front = rear
front = 0
rear = 0
else
front = front + 1
(Here draw the box figure of Deletion Operation.)
/*USE OF QUEUE IN THE ARRAY.*/
#include<stdio.h>
#define SIZE 3
int arr[SIZE];
int front = 0;
int rear = 0;
main()
{
int ans;
clrscr();
do
{
printf("1. Enter New Element.\n");
printf("2. Remove New Element.\n");
printf("3. Exit.\n");
printf("Enter Your Choice :");
scanf("%d",&ans);
switch(ans)
{
case 1:
insert();
break;
case 2:
rem();
break;
case 3:
break;
default:
printf("You Have Enter Wronge Choice...\n");
}
}while(ans!=3);
getch();
return;
}
insert()
{
int newitem;
if(rear>=SIZE)
{
printf("Your QUEUE is FULL...\n");
return;
}
else
{
printf("Enter New Value :");
scanf("%d",&newitem);
arr[++rear]=newitem;
}
if(front==0)
front=1;
getch();
return;
}
rem()
{
int remitem;
if(front>rear)
{
printf("Your QUEUE is EMPTY...\n");
front=0;
rear=0;
return;
}
else
{
remitem=arr[front++];
printf("The Removed Item Is %d.\n",remitem);
}
getch();
return;
}
Question : Explain the Dynamic Memory Allocation and following function.
When we declare an array in out program, the compiler allocates memory to hold the array prior to providing it. Some times it is required to change the size of the array and in that case it is required to edit and compile the program. To reduce the number of changes, it is required to allocate required memory during the run-time. For example, suppose we want to read a file into memory from the disk. If the size of file is not known and we have to load it into memory and defining very large array, so that file can fit into the array. If the size of the array is larger than that of file then the space is wasted. If the size of file is larger then it is not possible to load the complete file into the array, leading to need for dynamic memory allocation. In the dynamic memory allocation we use a pointer variable and it’s size is allocated during the execution of the program. There are two principle functions in C which are used to allocate required memory to pointer variable.
1. malloc()
2. calloc()
Both the malloc() and calloc() functions performs the operations and checks memory availability, based on the memory block size requested. When a suitable segment of memory is located. A pointer to the address of the allocated block is returned by the function.
1. malloc()
This function is used to allocate a requested number of bytes from the free pool of memory, and returns a pointer to a block of contiguous memory of the size specified.
This function allocates a block of memory and returns a pointer which points the first byte of the allocated space or memory block and if memory allocation was not successful, it returns a NULL pointer.
Syntax :
<pointer> = (<cast type> *) malloc(<no. of bytes to be allocated>);
“Pointer” is the name of a pointer of type cast type.
The malloc() functions returns a pointer of cast type to an area of memory with size as no. of bytes to be allocated.
Example:
mpointer = (int *) malloc(50 * sizeof(int));
After the successful execution of the above statement, a memory space equivalent to “50 times the size of an int” is reserved, and the address of the first byte of this block of memory allocated is assigned to the pointer mpointer of type int.
If an integer takes 2 bytes of storage space, the above declaration will allocate 100 bytes of contiguous storage space.
The malloc() function always returns a pointer to the first byte of the block of memory that has been allocated. It allocates a contiguous block of memory. If the allocation fails, i.e. malloc() is not able to allocate the required bytes of memory as a contiguous block, it returns NULL pointer.
2. calloc()
‘C’ also provides the calloc() function for allocating memory.
This function is normally used to request memory allocation at run time for storing derived data types such as arrays and structures.
calloc() function allocates multiple blocks of storages, each block of the same size and then sets all the bytes of memory in the block to zero.
Syntax:
<pointer> = (<cast-type> *) calloc(<no. of blocks>, <size of element>);
The calloc() function allocates contiguous space of “no. of block”, each block being of size, “size of element”. All the bytes of memory allocated are then initialized to zero, and a pointer to the first byte of the allocated contiguous memory is returned. In case, there is not enough memory available in the free pool of memory, a NULL pointer is returned.
3. free()
When we are dynamically allocating memory for variables at run time, the memory is not automatically released to the system. It is responsibility of a programmer, who has dynamically allocated memory, to released the memory to the free pool of memory when the memory is not needed.
‘C’ provides the free() function to release a block of memory that was allocated and is no longer needed.
Syntax:
free(<pointer>);
“pointer” is a pointer to the memory block that was returned by either malloc() and calloc() function calls.
4. realloc()
After, memory has been allocated to variables at run time, there may be a need to change the size of block of memory that was allocated. ‘C’ provides the realloc() function, using which the memory can be reallocated to increase or decrease the size of allocated memory.
Syntax:
<pointer> = realloc(<pointer>, <new memory size>);
“pointer” is the pointer that points the first byte of the memory that was allocated using either malloc() or calloc() functions.
“new memory size” indicates the new size of memory that is to be allocated. This new size could be more or less than the original size.
It is important to note here that the new block of memory may or may not begin at the same place as the old block.
In case, the functions fails to reallocate a larger memory in contiguous block at the location, it will create the same as an entirely new region and move the contents of the old block into the new block. The function guarantees that the old data will remain intact.
If the realloc() function fails to allocates additional space, it returns the NULL pointer and the original block is lost. Therefore, it is necessary for a programmer to test for the success of the function before reallocating memory, so that, old data is not lost.
Question: Explain DATA STRUCTURE and types of DATA STRUCTURE.
DATA STRUCTURE is a collection of data elements whose organization is characterized by assessing operations that are used to store and retrieve the individual data elements; the implementation of the composite data members in an abstract data type. An abstract data type can be define as a data type whose properties are specified independently of any particular implementation.
The DATA STRUCTURE is classified in the following categories:
1. Linear Data Structures
In the linear Data Structures processing of data items is possible in linear fashion, i.e., data can be processed one by one sequentially. Linear data structures contains following types of data structures.
I. Array
II. Linked List
III. Stack and Queues
2. Nonlinear Data Structures
A Data Structures in which insertion and deletion is not possible in a linear fashion is called nonlinear DATA STRUCTURE. In this category of DATA STRUCTURE, we will discuss the following.
I. Tree
II. Graph
Question: What is Primitive and Non-primitive Datastructure (Datatypes)?
Primitive Datastructure:
This is the data structure that typically are directly operated upon by machine-level instructions. We will present storage representations for these data structures for a variety of machines. For example, declaration of variables with basic datatypes are the example of primitive data structure.
Non-Primitive Datastructure:
Non-primitive data structures can be classified as arrays, lists and files. As array is an ordered set which consists of a fixed number of objects. No deletion or insertion operations are performed on arrays. A list, on the other hand, is an ordered set consisting of a variable number of elements to which insertions and deletions can be made.
Question: What is STACK? Explain the operations of STACK with example.
A STACK is defined formally as a list (a linear DATA STRUCTURE) in which all insertion and deletions are made at one end called the Top Of Stack (TOS). The fundamental operations, which are possible on a stack, are:
1. Push à Insertion
2. Pop à Deletion
3. Peep à Extract Information
4. Update à Update information associated at some location in the stack.
The most recently pushed element can be checked prior to performing a pop operation. A stack is based on the Last In First Out algorithm (LIFO) in which insertion and deletion operations are performed at one end of a stack. Also, the information can only be removed in the opposite order in which it was added to the stack. The most accessible information in a stack is at the top of stack and least accessible information is at the bottom of the stack.
For example, consider a stack of plates on the counter in a cafeteria. During the dinner time customers take plates from the top of the stack and waiter puts the washed plates on the top of the stack. The plate that is put most recently on the stack is the first one to bed taken off. The plate at the bottom is the last one to be used. This discussion can further be understood with the help of following figure.
A pointer TOS keeps track of the top most information in the STACK. Initially when the stack is empty, TOS has a value zero and when the stack contains a single information TOS has a value one and so on. Before an item is pushed onto the stack, the pointer is incremented by one. The pointer is decrement by one each time a deletion is made from the stack.
The Use Of STACK.
We have already discussed that a stack is a list and hence any of the list implementation techniques may be used to implement a stack. Two common use of stack are through:
1. Pinter (Linked List)
2. Array
The Algorithm Of STACK.
1. Push Operation:
Push means to insert an item onto the stack. The push algorithm is illustrated below. The algorithm illustrated inserts an item to the top of stack, which is represented by array S and containing Size number of items with a pointer Tos denoting the position of top most item in the stack.
Step 1 : [check for stack overflow]
If Tos >= Size
Output “Stack is Overflow” and exit
Step 2 : [Increment the Pointer value by one]
Tos = Tos + 1
Step 3 : [perform insertion]
S[Tos] = Value
Step 4 : Exit
2. Pop Operation:
The pop operation deletes or removes the topmost item from the stack. After removal of top most information, new value of the pointer Tos becomes the previous value of Tos that is Tos = Tos – 1 and freed position is allocated to free space. The algorithm to remove an item from the stack is illustrated below.
Step 1 :[check whether the stack is empty]
If Tos = 0
Output “Stack underflow” and exit
Step 2 :[Remove the Tos information]
Value = S[Tos]
Tos = Tos – 1
Step 3 :[Return the former information of the stack]
Return (Value)
/*USE OF THE STACK USING ARRAYS */
#include<stdio.h>
#define SIZE 5
int arr[SIZE];
int tos=0;
main()
{
int ans;
clrscr();
do
{
printf("1. Enter the New Element :\n");
printf("2. Remove The Element :\n");
printf("3. Display Stack :\n");
printf("4. Exit :\n");
printf("Enter Your Choice :");
scanf("%d",&ans);
switch(ans)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
break;
default:
printf("You Have Entered Wronge Choice...\n");
}
}while(ans != 3);
getch();
return;
}
push()
{
int newitem;
if(tos >= SIZE)
{
printf("The STACK is Full....\n");
return;
}
else
{
printf("Enter the New Value :");
scanf("%d",&newitem);
arr[tos]=newitem;
tos++;
}
getch();
return;
}
pop()
{
int remitem;
if(tos <= 0)
{
printf("The STACK is Empty....\n");
return;
}
else
{
tos--;
remitem = arr[tos];
printf("The Removeble item is %d.\n",remitem);
}
getch();
return;
}
display()
{
int x;
if(tos<=0)
{
printf("Your STACK is Empty....\n");
return;
}
else
{
while(tos>=0)
printf("%d ",arr[--tos]);
}
getch();
return;}
/* USE OF STACK USING POINTER AND STRUCTURE. */
#include<stdio.h>
#define SIZE 5
struct library
{
int b_no[SIZE];
}*book;
int cnt=0;
main()
{
int ans;
clrscr();
do
{
printf("1. Enter the New Element :\n");
printf("2. Remove The Element :\n");
printf("3. Exit :\n");
printf("Enter Your Choice :");
scanf("%d",&ans);
switch(ans)
{
case 1:
push(book);
break;
case 2:
pop(book);
break;
case 3:
break;
default:
printf("You Have Entered Wronge Choice...\n");
}
}while(ans != 3);
getch();
return;
}
push(struct library *bk)
{
int newitem;
if(cnt >= SIZE)
{
printf("The STACK is full...\n");
return;
}
else
{
printf("Enter the New Value :");
scanf("%d",&newitem);
bk->b_no[cnt++] = newitem;
}
getch();
return;
}
pop(struct library *bk)
{
int remitem;
if(cnt <= 0)
{
printf("The STACK is empty...\n");
return;
}
else
{
remitem = bk->b_no[--cnt];
printf("The Removeble item is %d\n",remitem);
}
getch();
return;
}
Question: Explain the Applications of STACK.
There are three applications in which stacks are used. The first application deals with recursion. Recursion is an important facility in many programming languages such as ALGOL 60 and PASCAL. There are many problems whose algorithmic description is best described in a recursive manner.
The second application of a stack is classical; it deals with the compilation of infix expressions into object code.
The third application of a stack is stack machine. Certain computers perform stack operations at the hardware or machine level, and these operations enable insertions to and deletions from a stack to be made very rapidly.
1. Recursion:
The natural numbers have been defined recursively through the process of induction. Recursion is the name given to the technique of defining a set or a process in terms or itself.
1, if N = 0
N * FACTORIAL(N-1), otherwise
The factorial function, whose domain is the natural numbers, can be recursively defined as,
FACTORIAL(N) =
Here the FACTORIAL(N) is defined in terms of FACTORIAL(N-1), which in turn is defined in terms of FACTORIAL(N-2), etc. until finally FACTORIAL(0) is reached, whose value is given as “one”. The basic idea is to define a function for all its argument values in a constructive manner by using induction. The value of a function for a particular argument value can be computed in a finite number of steps using the recursive definition, where at each step of recursion we get nearer to the solution.
2. Classical (Polish Expression and Their Compilation) :
In this section we shall primarily concerned with the mechanical evaluation or compilation of infix expressions. We shall find it to be more efficient to evaluate an infix arithmetical expression by first converting it to a suffix expression and then evaluating the latter. This approach will eliminate the repeated scanning of an infix expression in order to obtain its value.
3. Stack Machines:
One of the main problems with using machines which have a very limited number of registers is how to handle the storage of intermediate results. In particulars, we must be very cognizant of the generation of wasted store/load instruction sequences. In this sections we illustrate how the presence of the simple stack operations of POP and PUSH can enhance the process of generating code from a reverse-polish string. The instructions available for this machine are given in mnemonic form as follows:
1. PUSH<name> - Load from memory onto stack. This instructions loads an operand from the memory location named <name> and places the contents of <name> on the stack.
2. POP <name> - Store top of stack in memory. The contents of the top of the stack are removed and stored in the memory location referenced by <name>.
3. ADD, SUM, MUL, DIV – Arithmetic operation.
Question: Explain Polish Notation.
The process of writing the operators of an expression either before their operands or after them is called the Polish notation in honor of its discoverer, the Polish mathematician jan Luksiewicz. The fundamental property of Polish notation is that the order in which the operations are to be performed is completely determined by the position of the operators and operands in the expression. Accordingly, one never needs parenthesis when writing expression in Polish notation. The Polish notations are classified into three categories. These are:
1. Infix
2. Prefix
3. Postfix
1. Infix:
When the operators exist between two operands then the expression is called Infix expression. For example, let a + b * c is an expression, by inspecting we find that the operator + exists between the operands a and b, and operator * exists between the operands b and c, hence we say that a + b * c is an infix expression.
2. Prefix:
When the operators are written before their operands then the resulting expression is called the prefix Polish notation. Suppose we want to change the infix expression a + b * c it’s prefix form. First of all we consider the precedence of the operators present in the infix expression. Here in the given infix expression there are two operands + and *. The precedence of the * is higher than that of the +. The step which are required to change infix expression a + b * c into it’s equivalent prefix form are as follows:
Step 1 : a + * b c
Step 2 : + a * b c
3. Postfix:
When the operators come after their operands the resulting expression is called the reverse Polish notation or postfix expression.
For example, suppose a + b * c is an infix expression then after changing this expression into post form we get
Step 1 : a + b c *
Step 2 : a b c * +
Question: Explain Linear queues with algorithm and example.
This is a linear list DATA STRUCTURE used to represent a linear list and permits deletion to be performed at one end of the list and the insertion at the other end. The information in such a list is processed in the same order as it was received, that is on first-come-first-out (FIFO) basis. The Railway Reservation counter is an example of queue where the people collect their tickets on the first-come-first-serve (FIFS) basis. There are two types of operations possible on the linear queue.
1. Insertion (from rear side)
2. Deletion (from front side)
USE OF QUEUE :
Two common ways in which queues may be implemented are as follows:
1. Arrays
2. Pointers
(Draw the figure)
A queue has two pointers front and rear, pointing to the front and rear elements of the queue, respectively. Consider a queue Q consisting of n elements and an elements Value, which we have no insert into the Q. The value NULL (0) of front pointer implies an empty queue and the MAXVALUE implies the queue is full.
ALGORITHM OF QUEUE:
1. Insert Operation:
Insert operation inserting the new value from the rear side (right hand side). The first value is arranged in the queue as a left most value (in queue as first value) and second value is also inserted on rear side and set behind first value. Thus, each new value is set behind the previous entered value.
Step 1: [Check overflow condition]
if rear >= size
Output “Overflow” and return
Step 2: [Increment rear pointer]
Rear = rear + 1
Step 3: [Insert an element]
Q [rear] = value
Step 4: [Set the front pointer]
If front = 0
front = 1
Step 5: return
(here draw the box figure of inserting of node.)
2. Deletion Operation:
Deletion Operation is used to remove the values in the queue. It is works on the first-in-first-out (FIFO) basis, means, it is removed item from the front side (at the right hand side of the queue). This operation is removed first entered item after second entered item and so on in the queue.
Step 1: [Check underflow condition]
if front = 0
Output “Underflow” and return
Step 2: [Remove an element]
Value = Q [front]
Step 3: [Check for empty queue]
If front = rear
front = 0
rear = 0
else
front = front + 1
(Here draw the box figure of Deletion Operation.)
/*USE OF QUEUE IN THE ARRAY.*/
#include<stdio.h>
#define SIZE 3
int arr[SIZE];
int front = 0;
int rear = 0;
main()
{
int ans;
clrscr();
do
{
printf("1. Enter New Element.\n");
printf("2. Remove New Element.\n");
printf("3. Exit.\n");
printf("Enter Your Choice :");
scanf("%d",&ans);
switch(ans)
{
case 1:
insert();
break;
case 2:
rem();
break;
case 3:
break;
default:
printf("You Have Enter Wronge Choice...\n");
}
}while(ans!=3);
getch();
return;
}
insert()
{
int newitem;
if(rear>=SIZE)
{
printf("Your QUEUE is FULL...\n");
return;
}
else
{
printf("Enter New Value :");
scanf("%d",&newitem);
arr[++rear]=newitem;
}
if(front==0)
front=1;
getch();
return;
}
rem()
{
int remitem;
if(front>rear)
{
printf("Your QUEUE is EMPTY...\n");
front=0;
rear=0;
return;
}
else
{
remitem=arr[front++];
printf("The Removed Item Is %d.\n",remitem);
}
getch();
return;
}
/*USE OF QUEUE IN THE POINTER AND STRUCUTRE.*/
#include<stdio.h>
#define SIZE 10
struct queue
{
int item[SIZE];
}*q;
static int front = 0;
static int rear = 0;
main()
{
int ans;
do
{
clrscr();
printf("1. Enter the New Element.\n");
printf("2. Remove the Element.\n");
printf("3. Display the Queue.\n");
printf("4. Exit...\n");
printf("Enter your choice :");
scanf("%d",&ans);
switch(ans)
{
case 1:
insert(&q);
break;
case 2:
rem(&q);
break;
case 3:
display(&q);
break;
case 4:
break;
default:
printf("You have entered wronge choice....");
}
}while(ans != 4);
getch();
return;
}
insert(struct queue *temp)
{
int newitem;
if(front >= SIZE)
{
printf("QUEUE IS FULL....");
getch();
return;
}
else
{
printf("Enter a New Value :");
scanf("%d",&newitem);
temp->item[++rear] = newitem;
if(front <= 0)
front = 1;
}
getch();
return;
}
rem(struct queue *temp)
{
int remitem;
if (rear <= 0)
{
printf("THE QUEUE IS EMPTY....");
getch();
return;
}
else
{
temp->item[front++] = 0;
if(front > rear)
{
front = 0;
rear = 0;
}
}
getch();
return;}
display(struct queue *temp)
{
int fnt = 1;
if(front <= 0 || rear <=0)
{
printf("THE QUEUE IS EMPLTY....");
getch();
return;
}
else
{
while(fnt <= rear)
{
printf("%d ",temp->item[fnt]);
fnt++;
}
}
getch();
return;
}
Question : Explain CIRCULAR QUEUE with operations and examples.
Let we have an array Q that contains n elements in which Q[1] comes after Q[n] in the array. When this technique is used to construct a queue then the queue is called circular queue. In other word we can say that a queue is called circular when the last element comes just before the first element. Following figure illustrates a circular queue.
(Draw the figure)
There is types of pointer called front and rear is used to assume the front side and rear side of the circular queue. In a circular queue when rear = n, if we insert an element then this element is assigned to Q[1]. That is instead of increasing rear to n+1, we reset rear to 1. Similarly if front = n and an element of the queue is removed, we reset front to 1 instead of n + 1. Suppose queue contains only one element that is front=rear not equals to NULL and suppose that the element is removed then the front and rear pointer are now assigned NULL to indicate that the queue is empty.
OPERATIONS AND ALGORITHMS OF CIRCULAR QUEUE:
1. Insert Operation:
Step 1: [Check for the Overflow]
If front = 1 and rear = n
Output “Overflow” and return
Step 2: [Insert element in the queue.]
Else if front = 0
front = 1
rear = 1
Q [rear] = value
Step 3: [Check if the rear at the end of the queue]
Else if rear = n
rear = 1
Q [rear] = value
Step 4: [insert the element]
Else
Rear = rear + 1
Q [rear] = value
Step 5: return
2. Delete Operation:
Step 1: [Check for underflow]
If front = 0
Output “Underflow” and return
Step 2: [Remove the element]
Value = Q [front]
Step 3: [Check whether the queue is empty or not]
If front = rear
front = 0
rear = 0
Step 4: [Check the front pointer position]
Else if front = n
front = 1
Else
front = front + 1
Step 5: [Return the removed element]
Return [value]
/*USE OF CIRCULAR QUEUE USING ARRAY.*/
#include<stdio.h>
#define SIZE 3
int arr[SIZE];
int front = 0;
int rear = 0;
main()
{
int ans;
clrscr();
do
{
printf("1. Enter the New Element.\n");
printf("2. Remove the Element.\n");
printf("3. Exit...\n");
printf("Enter your choice :");
scanf("%d",&ans);
switch(ans)
{
case 1:
insert();
break;
case 2:
rem();
break;
case 3:
break;
default:
printf("You have entered wronge choice....");
}
}while(ans != 3);
getch();
return;
}
insert()
{
int newitem;
if(rear >= SIZE)
rear = 1;
else
rear++;
if(rear == front)
{
printf("Your QUEUE is FULL.\n");
rear--;
if(rear==0)
rear=SIZE;
return;
}
else
{
printf("Enter New Element :");
scanf("%d",&newitem);
arr[rear]=newitem;
if(front==0)
front=1;
}
getch();
return;
}
rem()
{
int remitem;
if(front < 1)
{
printf("Your QUEUE is EMPTY...\n");
return;
}
if(front>SIZE)
front=1;
remitem = arr[front];
printf("The Removed Item is : %d.\n",remitem);
if(front==rear)
{
front=0;
rear=0;
return;
}
else
front++;
getch();
return;
}
Question : Explain the Double Ended Queue with algorithm and example.
We know that in a stack insertion and deletion are possible only at one end (LIFO). While in a queue insertion at one end and deletion at other end. That is operations in queue is performed in (FIFO) basis. Double ended queue is a linear list in which insertions and deletions are possible at either end. Thus we can say that dqueue is more superior representations of linear list as compared to stack and simple queue. Other than the dqueue, there are other two forms of dqueue. Double ended queue is also known as dqueue. Following figure shows a dqueue.
1. Input restricted dqueue (Insertion at one end)
2. Output restricted dqueue (Deletion at one end)
(draw the figure of operation of dqueue)
ALGORITHM OF DOUBLE-ENDED QUEUE.
1. Insertion in Double-Ended Queue.
Step 1: [Check overflow condition]
If rear >= n and front = 0
Output “overflow” and return
Step 2: [Check front pointer value]
If front > 0
front = front – 1
else
return
Step 3: [Insert element at the front end]
Q [front] = value
Step 4: [Check rear pointer value]
If rear < n
rear = rear + 1
else
return
Step 5: [Insert element at the rear end]
Q [rear] = value
Step 6: return
2. Deletion in Double-Ended queue.
Step 1: [Check for underflow]
If front = 0 and rear = 0
Output “Underflow” and return
Step 2: [Delete element at front end]
If front > 0
Value = Q [front]
Return (value)
Step 3: [Check queue for empty]
If front = rear
front = rear = 0
else
front = front + 1
Step 4: [Delete element at the rear end]
If rear > 0
Value = Q [rear]
Return (value)
Step 5: [Check queue for empty]
If front = rear
front = rear = 0
else
rear = rear – 1
Step 6: return
/*USE OF DOUBLE-ENDED QUEUE USING ARRAY.*/
#include<stdio.h>
#define SIZE 3
int arr[SIZE];
int front=0;
int rear = 0;
main()
{
int ans;
clrscr();
do
{
printf("1.Enter New Element From Right :\n");
printf("2.Remove Element From Right :\n");
printf("3.Enter New Element From Left :\n");
printf("4.Remove Element From Left :\n");
printf("5.Exit :\n");
printf("Enter Your Choice :");
scanf("%d",&ans);
switch(ans)
{
case 1:
r_insert();
break;
case 2:
r_remove();
break;
case 3:
l_insert();
break;
case 4:
l_remove();
break;
case 5:
break;
default:
printf("You have entered wronge choice....");
}
}while(ans!=5);
getch();
return;
}
r_insert()
{
int newitem;
if(rear >= SIZE)
{
printf("Your QUEUE is full from RIGHT side....");
getch();
return;
}
else
{
printf("Enter the New item :");
scanf("%d",&newitem);
arr[++rear]=newitem;
}
if(front <= 0)
{
front = 1;
}
getch();
return;
}
r_remove()
{
int remitem;
if(rear <= 0)
{
rear = 0;
front = 0;
printf("Your QUEUE is EMPTY from RIGTH side...\n");
getch();
return;
}
else
{
remitem = arr[rear--];
printf("The removed item is : %d\n",remitem);
}
getch();
return;
}
l_remove()
{
int remitem;
if(front <= 0 )
{
printf("Your QUEUE is EMPTY from LEFT side...\n");
getch();
return;
}
else
{
remitem = arr[front++];
printf("The removed item is : %d\n",remitem);
}
if(front > rear)
{
front = 0;
}
getch(); return;}
l_insert()
{
int newitem;
if(front <= 1)
{
front = 0;
rear = 0;
printf("Your QUEUE is FULL from the LEFT side...\n");
getch();
return;
}
else
{
printf("Enter the New element :");
scanf("%d",&newitem);
arr[--front]=newitem;
}
getch();
return;
}
Question : Explain the Priority Queue with Example.
A queue in which it is possible to insert an element or remove and element at any position depending on some priority is called priority queue. In general way, we can say that a priority queue is a series of queues representing situations in which it is known a priori what priorities are associated with queue elements.
(here draw the figure)
Above figure illustrates how the single priority queue can be visualized as four separates queues; each follows a FIFO behavior. The elements in the second queue is removed only when the first queue is empty, elements from the third queue are removed when the first and second queues are empty and so on. When the elements are added, they are always added at the end of one of the queues as determined by priority. For example, let telephone department contains the list of telephones holders in their alphabetical order. Suppose some new users we have to add into the list at their proper place. It means we have to insert new users some where in middle, it will require more and more processing time if the list is very large. The remedies for it to divide the list into 26 sub-lists then the processing automatically will be reduced. If it is required to sort the list the radix technique for efficient processing. Following figure illustrates such type of representation.
(Draw the figure)
Question: Explain Linked List.
A linked list is defined as a collection of nodes. Each node has two parts.
1. Information
2. Pointer to next node
Information part may consists of one or more than one fields. In other words a linked list consists of series of structures, which are not necessarily contiguous. Each structure contains one or more than one contiguous information fields and a pointer to a structure containing its successor. The last node of the list contains NULL (‘\0’) in the pointer field. The pointer contains the address of the location where next information is stored.
There are following algorithms for the linked list.
1. Linked list creation algorithm
Step 1: [Initially list empty]
Start = NULL
Ste 2: [Allocate space to newly created node]
Node = Create a Node
Step 3: [Assign value to information part of a node]
Info[Node] = Data
Step 4: [Assign null to the address part for signaling end of the list]
Next[Node] = Start
Step 5: [Assign address of first node to start variable]
Start = Node
Step 6: [Return the created node]
Return [Start]
2. Algorithm to traverse nodes in a linked list
Step 1: [Initialize pointer variable current_node]
Current_node = First
Step 2: [Perform the traversing operational]
Repeat while Current_node [Not] NULL
Process Info [Current_node]
Step 3: [Move pointer to next node]
Current_node = Next [Current_node]
Step 4: Exit
3. Algorithm to insert a node at the beginning of a list
Step 1: [check for free space]
If New1 = NULL output “OVERFLOW” and Exit
Step 2: [Allocate free space]
New1 = Create new node
Step 3: [Read value of information part of a new node]
Info [New1] = Value
Step 4: [Link address part of the currently created node with the address of start]
Next [ New1] = Start
Step 5: [Now assign address of newly created node to the start]
Start = New1
Step 6: Exit
4. Algorithm to insert a node at the end of list
Step 1: [Check for free space]
If New1 = NULL output “OVERFLOW” and Exit
Step 2: [Allocate free space]
New1 = Create new node
Step 3: [Read value of information part of a new node]
Info [New1] = value
Step 4: [Move the pointer to the end of the list]
Repeat while node [Not] NULL
Node = next [Node]
Previous = next [Previous]
Step 5: [Link currently created node with the last node of the list]
Next [New1] = node
Next [previous] = New1
Step 6: Exit
5. Algorithm to insert a node in a linked list at a desired place.
Step 1: [check for availability space]
If New1 = NULL output “OVERFLOW” and Exit
Step 2: [Initialization]
Node_number = 0
Node = Start.Next [Points to first node of the list]
Previous = Address of Start [Assign address of start to previous]
Step 3: [Read information of new node number]
Insert_node = Value
Step 4: [perform insertion operation]
Repeat through Step 6 while Node <> NULL
Step 5: [Check place where new should be insert]
If Info [Nde] < Insert_node
Next [New1] = Node
Previous->Next = new1
Info [new1] = Insert_node
Return
Else [Move the pointer forward]
Node = Next [Node]
Previous = Next [Previous]
Step 6: Node_number = Node_number + 1
Step 7: Exit
6. Algorithm to delete a node in a linked list at a desired place.
Step 1:[ Initialization ]
Node = Start.next [Points to the first node in the linked list]
Previous = Address of Start
Step 2: [Initialize node counter]
Node_number = 1
Step 3: [Read information associated with a node]
Delete_node = Value
Step 4: [Check list is empty or not]
If Node = NULL
Output “OverFlow” and Exit
Step 5: [Perform deletion operation]
Repeat through 6 while Node <> NULL
If Info [Node] = Delete_node
(1) Next [Previous] = Next [Node] [Make link of previous node to the
next node]
(2) Delete (Node) [Delete current node]
(3) Exit
Step 6: Node_number = Node_number + 1
Step 7: Exit
Example :
#include<stdio.h>
#include<alloc.h>
struct list
{
int data;
struct list *next;
};
main()
{
struct list *node;
int ans;
node=NULL;
clrscr();
do
{
printf("\n\n1. Enter new element :\n");
printf("2.Display list :\n");
printf("3.exit:\n");
printf("4.Enter new node at bagin:\n");
printf("5.Enter new node at requird position:\n");
printf("6.Delete the node:\n");
printf("Enter your Choice:");
scanf("%d",&ans);
switch(ans)
{
case 1:create(&node);
break;
case 2:display(node);
break;
case 3:addatpos(&node);
break;
case 4:addatbag(&node);
break;
case 6:delnode(&node);
break;
default:
printf("you have enter wrong choice..\n");
}
}while(ans!=30);
getch();
return;
}
create(struct list **q)
{
struct list *temp;
int a;
temp= *q;
if(*q==NULL)
{
*q=(struct list*)malloc(sizeof(struct list));
temp=*q;
}
else
{
while(temp->next!=NULL)
temp=temp->next;
temp->next=(struct list*)malloc(sizeof(struct list));
temp=temp->next;
}
printf("Enter the value:");
scanf("%d",&a);
temp->data=a;
temp->next=NULL;
return;
}
display(struct list*q)
{
while(q!=NULL)
{ printf("%d",q->data);
q=q->next;
}
return;
}
addatbag(struct list **q)
{
struct list* temp;
int a;
temp=malloc(sizeof(struct list));
printf("Enter the value:");
scanf("%d",&a);
temp->data=a;
temp->next=*q;
*q=temp;
return;
}
addatpos(struct list *q)
{
int pos,a,flag=0;
struct list *temp;
printf("Enter the position:");
scanf("%d",&pos);
while(q!=NULL)
{
if(q->data==pos)
{
flag=1;
break;
}
q=q->next;
}
if(flag==0)
{
printf("Position is not proper;");
return;
}
printf("Enter the choice:");
scanf("%d",&a);
temp=malloc(sizeof(struct list));
temp->data=a;
temp->next=q->next;
q->next=temp;
return;
}
delnode(struct list **q)
{
struct list *temp,*old;
int pos;
temp=*q;
printf("enter the position for delete:");
scanf("%d",&pos);
while(temp!=NULL)
{
if(temp->data==pos)
{
if(temp==*q)
{
*q=temp->next;
free(temp);
return;
}
else
{
old->next=temp->next;
free(temp);
return;
}
}
else
{
old=temp;
temp=temp->next;
}
}
return;
}
Example of Sorted Linked List.
#include<stdio.h>
#include<malloc.h>
struct link
{
int data;
struct link *next;
};
int i;
int number;
struct link *start, *node, *previous, *new1, *counter;
void doubly_link_sort()
{
printf("\n Input the number of node we need to create:");
scanf("%d",&number);
start->next = NULL;
node = start;
for(i=0;i<number;i++)
{
node->next = (struct link*)malloc(sizeof(struct link));
node = node->next;
printf("\n Input the first node: %d; ", i+1);
scanf("%d", &node->data);
node->next = NULL;
}
for(new1 = start; new1->next != NULL; new1 = new1->next)
{
for(counter = new1->next; counter !=NULL; counter = counter->next)
{
if(new1->data > counter->data)
{
int temp = new1->data;
new1->data = counter->data;
counter->data = temp;
}
}
}
node = start->next;
printf("\n After sorting the list is as follows:\n");
while(node)
{
printf("%d", node->data);
node = node->next;
}
}
void main()
{
doubly_link_sort();
}
Question: Explain The Doubly Linked list.
Doubly linked list creation algorithm
Step 1 : [Initilization] 1) Start. Next = null
2) Previous. Next = null
Step 2 : [Assign address of start variable to node]
Node = address of start
Step 3 : [Make left and right links of a node]
1) Next [node] = node [make link to node]
2) Previous [node] = node [make link to node]
3) Node = Next [node] [Move pointer to next node]
4) Info [node] = value [Information value of a node]
5) Next [node] = NULL [Assign NULL to the address field]
Step 4 : [ Call Step 3]
Repeat Step 3 to create required number of nodes for linked list
Step 5 : End .
Algorithm for traversing a doubly inked list Step 1 : [initialization]
Node = start. Next [points to the first node in the list]
Step 2 : [Traverse the list in forward direction]
Repeat while Next [node] # NULL process Info [Node]
Step 3 : [Traverse the list in backward direction]
Repeat while Node # NULL Process Info [Node]
Step 4 : Exit.
Algorithm to insert a node at right of the right most node Step 1 : [Initialization]
Node =Start
Step 2 : [Create a new node] New = Create a Node
Step 3 : [Read information associated with newly created node]
Info [Newly] = value
Step 4 : [Perform the insertion]
I) Next [new] = node
II) Previous [New] = Previous [node]
III) Next [Previous[node]] = New
IV) Next [Node] = New
Step 5 : Exit
Algorithm to delete right most node Step 1 : [Initialization]
Node = Start
Step 2 : [Initialization counter]
Counter = 0
Step 3 : [check the list]
If Node = Null
Output “underflow” and exit
Step 4 : [count the number of nodes available in the list]
Repeat while Node # NULL
I) Node = Next [Node]
II) Counter = Counter + 1
Step 5 : [perform deletion]
Node = Start
Repeat through (II) while counter # 1
I) Node = Next [Node]
II) Counter = Counter – 1
III) Next [previous[node]] = Next [Node]
IV) Previous [Next [node]] = previous [node]
V) Delete (node)
Step 6 : Exit.
Algorithm to delete a desired node Step 1 : [Initialization]
Node = Start
Step 2 : [Check the list]
If node = NULL
Output “underflow” and Exit
Step 3 : [Set the counter ]
Search = 0
Step 4 : [Input the node number to which you want to delete]
Node delete = value
Step 5 : [Perform deletion]
Repeat while Node # NULL
If Search = Delete _Node
Next [Previous [Node]] = Next [Node]
Previous [Next[Node]] = Previous [Node]
Delete (Node)
Else
Node = Next [node]
Search = Search + 1
Step 6 : Exit
Example:
#include<stdio.h>
#include<malloc.h>
struct dnode
{
struct dnode *prv;
int data;
struct dnode *next;
};
main()
{
struct dnode *p;
int ans;
p=NULL;
clrscr();
do
{
printf("\n1:enter new node:\n");
printf("2:enter new node at begining:\n");
printf("3:enter new node at position:\n");
printf("4:display value:\n");
printf("5:delete node:\n");
printf("6:exit\n");
printf("enter your choice :");
scanf("%d",&ans);
switch(ans)
{
case 1:
append(&p);
break;
case 2:
addatbeg(&p);
break;
case 3:
addatpos(&p);
break;
case 4:
display(p);
break;
case 5:
deletatpos(&p);
break;
case 6:
exit(0);
break;
}
}while(ans!=6);
getch();
return;
}
append(struct dnode **q)
{
struct dnode *temp,*r;
int n;
temp=(*q);
if(*q==NULL)
{
*q=(struct dnode*)malloc(sizeof(struct dnode*));
(*q)->prv=NULL;
(*q)->next=NULL;
temp=(*q);
}
else
{
while(temp->next!=NULL)
temp=temp->next;
r=(struct dnode*)malloc(sizeof(struct dnode));
temp->next=r;
r->prv=temp;
r->next=NULL;
temp=temp->next;
}
printf("Enter value:");
scanf("%d",&n);
temp->data=n;
return;
}
addatbeg(struct dnode **q)
{
struct dnode *temp;
int n;
temp=(struct dnode*)malloc(sizeof(struct dnode));
temp->prv=NULL;
temp->next=*q;
(*q)->prv=temp;
printf("Enter value:\n");
scanf("%d",&n);
temp->data=n;
(*q) = (*q)->prv;
return;
}
addatpos(struct dnode **q)
{
struct dnode *temp;
int pos,n,flag=0;
printf("Enter position:\n");
scanf("%d",&pos);
while((*q)->next!=NULL)
{
if((*q)->data==pos)
{
flag=1;
break;
}
else
{
flag=0;
}
(*q)=(*q)->next;
}
if(flag==1)
{
printf("enter value :");
scanf("%d",&n);
temp=(struct dnode*)malloc(sizeof(struct dnode));
temp->prv=(*q)->prv->next;
(*q)->prv->next=temp;
temp->next=*q;
(*q)->prv=temp;
temp->data=n;
}
else
{
printf("element is not available:\n");
}
return;
}
deletatpos(struct dnode **q)
{
struct dnode *temp;
int n;
printf("Enter the position:\n");
scanf("%d",&n);
temp=*q;
while(temp->next!=NULL)
{
if(temp->data==n)
{
if(temp==*q)
{
(*q)=(*q)->next;
(*q)->prv=NULL;
}
else
{
if(temp->next==NULL)
temp->prv->next=NULL;
else
{
temp->prv->next=temp->next;
temp->next->prv=temp->prv;
free(temp);
}
}
}temp=temp->next;
}
return;
}
display(struct dnode *q)
{
while(q!=NULL)
{
printf("%d ",q->data);
q=q->next;
}
return;}
Question : Example of Circular Linked List.
#include<stdio.h>
#include<malloc.h>
struct node
{
int data;
struct node *next;
};
main()
{
struct node *front,*rear;
int ans;
front = rear = NULL;
do
{
printf("\n 1.insert node:\n");
printf("\n 2.delet node:\n");
printf("\n 3.display:\n");
printf("\n 4.exit\n");
printf("enter choice\n");
scanf("%d",&ans);
switch(ans)
{
case 1:
add(&front,&rear);
break;
case 2:
delet(&front,&rear);
break;
case 3:
display(front);
break;
case 4:
break;
}
}while(ans!=4);
return;
}
add(struct node **f,struct node **r)
{
struct node *q;
int a;
q=(struct node*)malloc(sizeof(struct node));
printf("\n enter the value:");
scanf("%d",&a);
q->data=a;
if(*f==NULL)
*f=q;
else
(*r)->next=q;
*r=q;
(*r)->next=*f;
return;
}
delet(struct node **f,struct node **r)
{
struct node *q;
int a;
if(*f==NULL)
printf("\n list empty");
else
{
if(*f==*r)
{
a=(*f)->data;
free(*f);
*f=NULL;
*r=NULL;
}
else
{
q=*f;
a=q->data;
(*f)=(*f)->next;
(*r)->next=*f;
free(q);
}
printf("\n deleted node %d",a);
return;
}
return;
}
display(struct node *f)
{
struct node *q=f,*p=NULL;
while(q!=p)
{
printf("%2d\t",q->data);
q=q->next;
p=f;
}
return;
}
Question: Explain the Binary Tree with Example.
A binary tree is an important type of data structure, which is very useful. A tree is a binary tree if each node of it can have at the most two branches. In other words we can say that if every node of a tree can have at most degree two, then this is called a binary tree. In a binary tree left and right sub-trees distinguish sub-trees of a node.
A binary tree T is a finite set of nodes, which is either empty or consists of special node called root R and two disjoint binary trees T1 and T2 (which are called the left sub-tree and right sub-trees, respectively). If T1 is non-empty then the root of T1 is called the left successor of R. If T2 is non-empty then the root of T2 is known as right successor of R.
Recursive algorithm for binary tree creation :
Create_Tree (Info, Node)
Where Info à Information for which we have to create node.
Node à structure type variable to points both left and right child.
Step 1: [Check whether the tree is empty]
If Node = NULL
Node = Create a node
Left_Child [Node] = NULL
Right_Child [Node]] = NULL
Step 2: [Test for the left child]
If Info [node] >= Info
Left_child [Node] = call Create_Tree
(Info, Left_child [Node])
Else
Right_child [Node] = call Create_Tree
(info, Right_child [Node])
Step 3: Return (Node)
Recursive algorithm of preorder traversing:
Preorder (Node)
Step 1: [Do through step 3]
If Node is not equal to NULL
Output Info [Node]
Step 2: Call Preorder (Left_child [Node])
Step 3: Call Preorder (Right_child Node])
Step 4: Exit
Recursive algorithm of inorder traversing: Inorder (Node)
Step 1: [Do through Step 4]
If Node is not equal to NULL
Step 2: Call Inorder (Left_Child [Node])
Step 3: Output Info [Node]
Step 4: Call Inorder (Right_child [Node])
Step 5: Exit
Recursive algorithm of postorder traversing:
Postorder (Node)
Step 1: [Do through step 4]
If Node is not equal to NULL
Step 2: Call Postorder (Left_Child [Node])
Step 3: Call Postorder (Right_Child Node)
Step 4: Output Info [Node]
Step 5: Exit
Example :
/*program for tree operation*/
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct tree
{
int no;
struct tree *r,*l;
};
void insert(struct tree *root,int x);
void preorder(struct tree *root);
void inorder(struct tree *root);
void postorder(struct tree *root);
void main()
{
struct tree *root = NULL;
int ch=1,x,level,info;
root=(struct tree *)malloc(sizeof(struct tree));
clrscr();
printf("\n enter the value of root:=");
scanf("%d",&root->no);
root->l = root->r=NULL;
while(ch!=0)
{
printf("\n 1:inert\t 2:preorder\t 3:inorder\t 4:postorder");
printf("\t 0:exit");
printf("\n\n enter the choice:=");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\n enter the no");
scanf("%d",&x);
insert(root,x);
break;
case 2:
preorder(root);
break;
case 3:
inorder(root);
break;
case 4:
postorder(root);
break;
}
}
}//main over
void insert(struct tree *root,int x)
{
if(x==root->no)
{
printf("\n duplicate no \n\n\n");
return;
}
if(x < root->no)
{
if(root->l!=NULL)
insert(root->l,x);
else
{
root->l=(struct tree*)malloc(sizeof(struct tree));
root->l->no=x;
root->l->l=root->l->r=NULL;
}
}
else
{
if(root->r!=NULL)
insert(root->r,x);
else
{
root->r=(struct tree*)malloc(sizeof(struct tree));
root->r->no=x;
root->r->r=root->r->l=NULL;
}
}
}//insert over
void inorder(struct tree *root)
{
if(root!=NULL)
{
inorder(root->l);
printf("\n %d",root->no);
inorder(root->r);
}
}//inorder over
void preorder(struct tree *root)
{
if(root !=NULL)
{
printf("\n %d",root->no);
preorder(root->l);
preorder(root->r);
}
}//preorder over
void postorder(struct tree *root)
{
if(root!=NULL)
{
postorder(root->l);
postorder(root->r);
printf("\n %d",root->no);
}
}//postorder over
Question: Explain the Bubble sort with algorithm and example.
Bubble_sort (n, list)
Where
N à Represents the number of elements in the list
L à Represents the list of elements
Step 1: [Initialize]
i = 0
Step 2: Repeat through step 5 while ( i < n )
Step 3 : j = 0;
Step 4: Repeat through step 5 while ( j < n-i)
Step 5: if (list[ j] < list [ j+1]
(i) temp = list[ j]
(ii) list[ j+1] = list[ j]
(iii) list[j] = temp
step 6: Exit
Example :
#include<stdio.h>
#include<stdio.h>
void bubble_sort (int array[], int size)
{
int temp, i, j;
for(i = 0; i < size; i++)
for( j=0;j < size-i-1;j++)
if (array[j] < array[ j+1] )
{
temp = array[j];
array[ j] = array[ j+1];
array[ j+1] = temp;
}
}
void main(void)
{
int values[30], i;
printf(“\n Unsorted list is as follows\n”);
for (i = 0; i < 10; i++)
{
values[i] = rand( ) %100;
printf(“%d”, values[i]);
}
bubble_sort (values , 10);
printf(“\n Sorted list is as follows\n”);
for(i = 0; i < 10;i++)
printf(“%d”,values[i]);
}
Question: Explain the Insertion sort with algorithm and example.
Insertion_sort (l,n)
Where l à Represents the list of elements.
N à Represents number of elementsin the list.
Step 1: [Initialize]
1[0] = -0
Step 2: Repeat through Step 3 to 5 for i=1,2,3,4..n
Step 3: (i) temp = l[i]
(ii) pointer = i – 1
Step 4: while(temp < l[pointer])
(i) l[pointer + 1] = l[pointer]
(ii) pointer = pointer – 1
Step 5: l[pointer] = temp
Step 6: Exit
Example:
#Include<stdio.h>
#include<stdlib.h>
int i, k;
void insertion_sort (int *, int);
void display(int *,int)
void insertion_sort(int l[], int n)
{
int pointer, temp;
l[0] = -0;
for(i = 1 ; i <= n ; i++)
{
pointer = i –1;
temp = l[i];
while(temp <l[ponter])
{
l[pointer+1] = l[pointer];
pointer -;
}
l[pointer+1] = temp;
printf(“Step = %d”,i);
for(k = 0; k <= n; k++)
printf(“%d”, l[k]);
printf(“\n”);
}
}
void display(int l[], int n)
{
printf(“\n Sorted list is as follows\n”);
for(i = 1;i <= n; i++)
printf(“%d”,l[i]);
}
void main()
{
int nember = 20;
int list[100];
int i;
printf(“\n Number of elements in the list : %i” , number);
printf(“\n Unsorted list is as follows \n”);
for(i = 1;i <= number; i++)
{
list[i] = rand() %100;
printf(“%d”,list[i]);
}
printf(“\n”);
printf(“\n Stepwise result is as follows \n\n”);
insertion_sort(list, number);
display(list, number);
}
Question: Explain the Quick sort with algorithm and example.
Q_SORT (Array, first, last)
Where array à Represents the list of elements;
First à Represents the position of the first elements in the list (Only at the starting point, it’s value changes during the excution of the function).
Last à Represents the position of the last elements in the list(Only at starting point the value of it’s changes during the execution of the function).
Step 1: [initially]
Low = first
High = last
Pivot = array[(low+high)/2] [middle elements of the elements of the list]
Step 2: Repeat through Step 7 while (low <= high)
Step 3: Repeat Step 4 while (array[low] < pivot)
Step 4: low = low +1
Step 5: Repeat Step 6 while (array[high] > pivot)
Step 6:high = high – 1
Step 7: if ( low<= high)
(i) temp = array[low]
(ii) array[low] = array[high]
(iii) array[high] = temp
(iv) low = low + 1
(v) high = high – 1
Step 8: if ( first < high ) Q_sort(array, first, high)
Step 9: if ( low < lase ) Q_sort(array, low, lase)
Step 10: exit
Example:
#include<stdio.h>
#include<stdlib.h>
void quick_sort(int array[], int first, int last)
{
int temp, low, high, pivot;
low = first;
high = last;
pivot = array[(first + lase) / 2];
do{
while (array[low] < pivot)
low++;
while (array[high] > pivot)
high-;
if(low <= high)
{
temp = array[low];
array[low++] = array[high];
array[high-] = temp;
}
}wihle(low <=high);
if(first < high)
quick_sort(arry, first, high);
if (low < last)
quick_sort(arry, low, last);
}
void main()
{
int values[100], i;
printf(“\n Unsorted list is as follows \n”);
for (i = 0; i < 20; i++)
{
values[i] = rand() % 100;
peintf(“%d”, values[i]);
}
quick_sort(values, 0, 19);
printf(“\n Sorted list as follows \n);
for(i = 0; i < 20; i++)
printf(“%d”, values[i]);
}
Question: Explain the Selection sort with algorithm and example.
Selection_sort (array, size)
Where array à Represents the list of elements
Size à Represents size of the list
Step 1: current = 0 [initially]
Step 2: Repeat through Step 7 while (current < size)
Step 3: j = current + 1;
Step 4: Repeat through Step 6 while (j < size)
Step 5: if (array [current] > array [j])
(i) temp = array[current]
(ii) arra[current] = array[j]
(iii) array[j] =temp
step 6: j = j + 1
Step 7: current = current + 1
Step 8: Exit
Example:
#include<stdio.h>
#include<stdlib.h>
void selection_sort[int array[], int size)
{
int temp, current, j;
for(current = 0; current < size; current++)
for(j = current +1; j < size; j++)
if(array[current] > array[j])
{
temp = array[current];
array[current] = array[j];
array[j] = temp;
}
}
void main()
{
int values[30], i;
printf(“\n Unsorted list is as follows\n”)
for(i = 0; i < 30; i++)
{
values[i] = rand() % 100;
printf(“%d”, values[i]);
}
selection_sort(values, 30 );
printf(“\n sorted list is as follows\n”);
for ( i = 0; i < 30; i++)
printf(“%d”, values[i]);
}
Question: Explain the Shell sort with algorithm and example.
Shell_sort(array, size)
Where array à Represents the list of elements
Size à Represents the size of the list
Step 1: [Initialize]
Gap = size / 2
Stpe 2: Repeat through Step 6 while(gap = gap / 2)
Step 3: swap = 0
Step 4: Repeat through Step 6 for i=0, 1, 2, 3…i <(size – gap)
Step 6:if (array[i] > array[i+gap]
(i) temp = array [i]
(ii) array[i] = array[i + gap]
(iii) array[i + gap]= temp
(iv) swap = 1
[ End of for loop]
[ End of inner while loop]
[ End of outer while loop]
Step 7: output arrayelements (sorted)
Step 8: Exit
Example:
#include<stdio.h>
#include<stdlib.h>
void shell_sort(int array[], int size)
{
int temp, gap, i, swap;
gap = size / 2;
do {
do {
swap = 0;
for (i = 0; i < size – gap; i++)
if(array[i] > array[i + gap])
{
temp = array[i];
array[i] = array[i + gap];
array[i + gap] = temp;
swap = 1;
}
}while (swap);
}while (gap = gap / 2);
}
void main(void)
{
int values[50], i;
print(“\n Unsorted list is as follows \n”);
for(i = 0; i < 50; i++)
{
values[i] = rand() % 100;
printf(“%d”, values[i]);
}
shell_sort(values, 50);
printf(“\n Sorted list is as follow \n”);
for(i = 0; i < 50; i++)
printf(“%d”, value[i]);
}
#include<stdio.h>
#define SIZE 10
struct queue
{
int item[SIZE];
}*q;
static int front = 0;
static int rear = 0;
main()
{
int ans;
do
{
clrscr();
printf("1. Enter the New Element.\n");
printf("2. Remove the Element.\n");
printf("3. Display the Queue.\n");
printf("4. Exit...\n");
printf("Enter your choice :");
scanf("%d",&ans);
switch(ans)
{
case 1:
insert(&q);
break;
case 2:
rem(&q);
break;
case 3:
display(&q);
break;
case 4:
break;
default:
printf("You have entered wronge choice....");
}
}while(ans != 4);
getch();
return;
}
insert(struct queue *temp)
{
int newitem;
if(front >= SIZE)
{
printf("QUEUE IS FULL....");
getch();
return;
}
else
{
printf("Enter a New Value :");
scanf("%d",&newitem);
temp->item[++rear] = newitem;
if(front <= 0)
front = 1;
}
getch();
return;
}
rem(struct queue *temp)
{
int remitem;
if (rear <= 0)
{
printf("THE QUEUE IS EMPTY....");
getch();
return;
}
else
{
temp->item[front++] = 0;
if(front > rear)
{
front = 0;
rear = 0;
}
}
getch();
return;}
display(struct queue *temp)
{
int fnt = 1;
if(front <= 0 || rear <=0)
{
printf("THE QUEUE IS EMPLTY....");
getch();
return;
}
else
{
while(fnt <= rear)
{
printf("%d ",temp->item[fnt]);
fnt++;
}
}
getch();
return;
}
Question : Explain CIRCULAR QUEUE with operations and examples.
Let we have an array Q that contains n elements in which Q[1] comes after Q[n] in the array. When this technique is used to construct a queue then the queue is called circular queue. In other word we can say that a queue is called circular when the last element comes just before the first element. Following figure illustrates a circular queue.
(Draw the figure)
There is types of pointer called front and rear is used to assume the front side and rear side of the circular queue. In a circular queue when rear = n, if we insert an element then this element is assigned to Q[1]. That is instead of increasing rear to n+1, we reset rear to 1. Similarly if front = n and an element of the queue is removed, we reset front to 1 instead of n + 1. Suppose queue contains only one element that is front=rear not equals to NULL and suppose that the element is removed then the front and rear pointer are now assigned NULL to indicate that the queue is empty.
OPERATIONS AND ALGORITHMS OF CIRCULAR QUEUE:
1. Insert Operation:
Step 1: [Check for the Overflow]
If front = 1 and rear = n
Output “Overflow” and return
Step 2: [Insert element in the queue.]
Else if front = 0
front = 1
rear = 1
Q [rear] = value
Step 3: [Check if the rear at the end of the queue]
Else if rear = n
rear = 1
Q [rear] = value
Step 4: [insert the element]
Else
Rear = rear + 1
Q [rear] = value
Step 5: return
2. Delete Operation:
Step 1: [Check for underflow]
If front = 0
Output “Underflow” and return
Step 2: [Remove the element]
Value = Q [front]
Step 3: [Check whether the queue is empty or not]
If front = rear
front = 0
rear = 0
Step 4: [Check the front pointer position]
Else if front = n
front = 1
Else
front = front + 1
Step 5: [Return the removed element]
Return [value]
/*USE OF CIRCULAR QUEUE USING ARRAY.*/
#include<stdio.h>
#define SIZE 3
int arr[SIZE];
int front = 0;
int rear = 0;
main()
{
int ans;
clrscr();
do
{
printf("1. Enter the New Element.\n");
printf("2. Remove the Element.\n");
printf("3. Exit...\n");
printf("Enter your choice :");
scanf("%d",&ans);
switch(ans)
{
case 1:
insert();
break;
case 2:
rem();
break;
case 3:
break;
default:
printf("You have entered wronge choice....");
}
}while(ans != 3);
getch();
return;
}
insert()
{
int newitem;
if(rear >= SIZE)
rear = 1;
else
rear++;
if(rear == front)
{
printf("Your QUEUE is FULL.\n");
rear--;
if(rear==0)
rear=SIZE;
return;
}
else
{
printf("Enter New Element :");
scanf("%d",&newitem);
arr[rear]=newitem;
if(front==0)
front=1;
}
getch();
return;
}
rem()
{
int remitem;
if(front < 1)
{
printf("Your QUEUE is EMPTY...\n");
return;
}
if(front>SIZE)
front=1;
remitem = arr[front];
printf("The Removed Item is : %d.\n",remitem);
if(front==rear)
{
front=0;
rear=0;
return;
}
else
front++;
getch();
return;
}
Question : Explain the Double Ended Queue with algorithm and example.
We know that in a stack insertion and deletion are possible only at one end (LIFO). While in a queue insertion at one end and deletion at other end. That is operations in queue is performed in (FIFO) basis. Double ended queue is a linear list in which insertions and deletions are possible at either end. Thus we can say that dqueue is more superior representations of linear list as compared to stack and simple queue. Other than the dqueue, there are other two forms of dqueue. Double ended queue is also known as dqueue. Following figure shows a dqueue.
1. Input restricted dqueue (Insertion at one end)
2. Output restricted dqueue (Deletion at one end)
(draw the figure of operation of dqueue)
ALGORITHM OF DOUBLE-ENDED QUEUE.
1. Insertion in Double-Ended Queue.
Step 1: [Check overflow condition]
If rear >= n and front = 0
Output “overflow” and return
Step 2: [Check front pointer value]
If front > 0
front = front – 1
else
return
Step 3: [Insert element at the front end]
Q [front] = value
Step 4: [Check rear pointer value]
If rear < n
rear = rear + 1
else
return
Step 5: [Insert element at the rear end]
Q [rear] = value
Step 6: return
2. Deletion in Double-Ended queue.
Step 1: [Check for underflow]
If front = 0 and rear = 0
Output “Underflow” and return
Step 2: [Delete element at front end]
If front > 0
Value = Q [front]
Return (value)
Step 3: [Check queue for empty]
If front = rear
front = rear = 0
else
front = front + 1
Step 4: [Delete element at the rear end]
If rear > 0
Value = Q [rear]
Return (value)
Step 5: [Check queue for empty]
If front = rear
front = rear = 0
else
rear = rear – 1
Step 6: return
/*USE OF DOUBLE-ENDED QUEUE USING ARRAY.*/
#include<stdio.h>
#define SIZE 3
int arr[SIZE];
int front=0;
int rear = 0;
main()
{
int ans;
clrscr();
do
{
printf("1.Enter New Element From Right :\n");
printf("2.Remove Element From Right :\n");
printf("3.Enter New Element From Left :\n");
printf("4.Remove Element From Left :\n");
printf("5.Exit :\n");
printf("Enter Your Choice :");
scanf("%d",&ans);
switch(ans)
{
case 1:
r_insert();
break;
case 2:
r_remove();
break;
case 3:
l_insert();
break;
case 4:
l_remove();
break;
case 5:
break;
default:
printf("You have entered wronge choice....");
}
}while(ans!=5);
getch();
return;
}
r_insert()
{
int newitem;
if(rear >= SIZE)
{
printf("Your QUEUE is full from RIGHT side....");
getch();
return;
}
else
{
printf("Enter the New item :");
scanf("%d",&newitem);
arr[++rear]=newitem;
}
if(front <= 0)
{
front = 1;
}
getch();
return;
}
r_remove()
{
int remitem;
if(rear <= 0)
{
rear = 0;
front = 0;
printf("Your QUEUE is EMPTY from RIGTH side...\n");
getch();
return;
}
else
{
remitem = arr[rear--];
printf("The removed item is : %d\n",remitem);
}
getch();
return;
}
l_remove()
{
int remitem;
if(front <= 0 )
{
printf("Your QUEUE is EMPTY from LEFT side...\n");
getch();
return;
}
else
{
remitem = arr[front++];
printf("The removed item is : %d\n",remitem);
}
if(front > rear)
{
front = 0;
}
getch(); return;}
l_insert()
{
int newitem;
if(front <= 1)
{
front = 0;
rear = 0;
printf("Your QUEUE is FULL from the LEFT side...\n");
getch();
return;
}
else
{
printf("Enter the New element :");
scanf("%d",&newitem);
arr[--front]=newitem;
}
getch();
return;
}
Question : Explain the Priority Queue with Example.
A queue in which it is possible to insert an element or remove and element at any position depending on some priority is called priority queue. In general way, we can say that a priority queue is a series of queues representing situations in which it is known a priori what priorities are associated with queue elements.
(here draw the figure)
Above figure illustrates how the single priority queue can be visualized as four separates queues; each follows a FIFO behavior. The elements in the second queue is removed only when the first queue is empty, elements from the third queue are removed when the first and second queues are empty and so on. When the elements are added, they are always added at the end of one of the queues as determined by priority. For example, let telephone department contains the list of telephones holders in their alphabetical order. Suppose some new users we have to add into the list at their proper place. It means we have to insert new users some where in middle, it will require more and more processing time if the list is very large. The remedies for it to divide the list into 26 sub-lists then the processing automatically will be reduced. If it is required to sort the list the radix technique for efficient processing. Following figure illustrates such type of representation.
(Draw the figure)
Question: Explain Linked List.
A linked list is defined as a collection of nodes. Each node has two parts.
1. Information
2. Pointer to next node
Information part may consists of one or more than one fields. In other words a linked list consists of series of structures, which are not necessarily contiguous. Each structure contains one or more than one contiguous information fields and a pointer to a structure containing its successor. The last node of the list contains NULL (‘\0’) in the pointer field. The pointer contains the address of the location where next information is stored.
There are following algorithms for the linked list.
1. Linked list creation algorithm
Step 1: [Initially list empty]
Start = NULL
Ste 2: [Allocate space to newly created node]
Node = Create a Node
Step 3: [Assign value to information part of a node]
Info[Node] = Data
Step 4: [Assign null to the address part for signaling end of the list]
Next[Node] = Start
Step 5: [Assign address of first node to start variable]
Start = Node
Step 6: [Return the created node]
Return [Start]
2. Algorithm to traverse nodes in a linked list
Step 1: [Initialize pointer variable current_node]
Current_node = First
Step 2: [Perform the traversing operational]
Repeat while Current_node [Not] NULL
Process Info [Current_node]
Step 3: [Move pointer to next node]
Current_node = Next [Current_node]
Step 4: Exit
3. Algorithm to insert a node at the beginning of a list
Step 1: [check for free space]
If New1 = NULL output “OVERFLOW” and Exit
Step 2: [Allocate free space]
New1 = Create new node
Step 3: [Read value of information part of a new node]
Info [New1] = Value
Step 4: [Link address part of the currently created node with the address of start]
Next [ New1] = Start
Step 5: [Now assign address of newly created node to the start]
Start = New1
Step 6: Exit
4. Algorithm to insert a node at the end of list
Step 1: [Check for free space]
If New1 = NULL output “OVERFLOW” and Exit
Step 2: [Allocate free space]
New1 = Create new node
Step 3: [Read value of information part of a new node]
Info [New1] = value
Step 4: [Move the pointer to the end of the list]
Repeat while node [Not] NULL
Node = next [Node]
Previous = next [Previous]
Step 5: [Link currently created node with the last node of the list]
Next [New1] = node
Next [previous] = New1
Step 6: Exit
5. Algorithm to insert a node in a linked list at a desired place.
Step 1: [check for availability space]
If New1 = NULL output “OVERFLOW” and Exit
Step 2: [Initialization]
Node_number = 0
Node = Start.Next [Points to first node of the list]
Previous = Address of Start [Assign address of start to previous]
Step 3: [Read information of new node number]
Insert_node = Value
Step 4: [perform insertion operation]
Repeat through Step 6 while Node <> NULL
Step 5: [Check place where new should be insert]
If Info [Nde] < Insert_node
Next [New1] = Node
Previous->Next = new1
Info [new1] = Insert_node
Return
Else [Move the pointer forward]
Node = Next [Node]
Previous = Next [Previous]
Step 6: Node_number = Node_number + 1
Step 7: Exit
6. Algorithm to delete a node in a linked list at a desired place.
Step 1:[ Initialization ]
Node = Start.next [Points to the first node in the linked list]
Previous = Address of Start
Step 2: [Initialize node counter]
Node_number = 1
Step 3: [Read information associated with a node]
Delete_node = Value
Step 4: [Check list is empty or not]
If Node = NULL
Output “OverFlow” and Exit
Step 5: [Perform deletion operation]
Repeat through 6 while Node <> NULL
If Info [Node] = Delete_node
(1) Next [Previous] = Next [Node] [Make link of previous node to the
next node]
(2) Delete (Node) [Delete current node]
(3) Exit
Step 6: Node_number = Node_number + 1
Step 7: Exit
Example :
#include<stdio.h>
#include<alloc.h>
struct list
{
int data;
struct list *next;
};
main()
{
struct list *node;
int ans;
node=NULL;
clrscr();
do
{
printf("\n\n1. Enter new element :\n");
printf("2.Display list :\n");
printf("3.exit:\n");
printf("4.Enter new node at bagin:\n");
printf("5.Enter new node at requird position:\n");
printf("6.Delete the node:\n");
printf("Enter your Choice:");
scanf("%d",&ans);
switch(ans)
{
case 1:create(&node);
break;
case 2:display(node);
break;
case 3:addatpos(&node);
break;
case 4:addatbag(&node);
break;
case 6:delnode(&node);
break;
default:
printf("you have enter wrong choice..\n");
}
}while(ans!=30);
getch();
return;
}
create(struct list **q)
{
struct list *temp;
int a;
temp= *q;
if(*q==NULL)
{
*q=(struct list*)malloc(sizeof(struct list));
temp=*q;
}
else
{
while(temp->next!=NULL)
temp=temp->next;
temp->next=(struct list*)malloc(sizeof(struct list));
temp=temp->next;
}
printf("Enter the value:");
scanf("%d",&a);
temp->data=a;
temp->next=NULL;
return;
}
display(struct list*q)
{
while(q!=NULL)
{ printf("%d",q->data);
q=q->next;
}
return;
}
addatbag(struct list **q)
{
struct list* temp;
int a;
temp=malloc(sizeof(struct list));
printf("Enter the value:");
scanf("%d",&a);
temp->data=a;
temp->next=*q;
*q=temp;
return;
}
addatpos(struct list *q)
{
int pos,a,flag=0;
struct list *temp;
printf("Enter the position:");
scanf("%d",&pos);
while(q!=NULL)
{
if(q->data==pos)
{
flag=1;
break;
}
q=q->next;
}
if(flag==0)
{
printf("Position is not proper;");
return;
}
printf("Enter the choice:");
scanf("%d",&a);
temp=malloc(sizeof(struct list));
temp->data=a;
temp->next=q->next;
q->next=temp;
return;
}
delnode(struct list **q)
{
struct list *temp,*old;
int pos;
temp=*q;
printf("enter the position for delete:");
scanf("%d",&pos);
while(temp!=NULL)
{
if(temp->data==pos)
{
if(temp==*q)
{
*q=temp->next;
free(temp);
return;
}
else
{
old->next=temp->next;
free(temp);
return;
}
}
else
{
old=temp;
temp=temp->next;
}
}
return;
}
Example of Sorted Linked List.
#include<stdio.h>
#include<malloc.h>
struct link
{
int data;
struct link *next;
};
int i;
int number;
struct link *start, *node, *previous, *new1, *counter;
void doubly_link_sort()
{
printf("\n Input the number of node we need to create:");
scanf("%d",&number);
start->next = NULL;
node = start;
for(i=0;i<number;i++)
{
node->next = (struct link*)malloc(sizeof(struct link));
node = node->next;
printf("\n Input the first node: %d; ", i+1);
scanf("%d", &node->data);
node->next = NULL;
}
for(new1 = start; new1->next != NULL; new1 = new1->next)
{
for(counter = new1->next; counter !=NULL; counter = counter->next)
{
if(new1->data > counter->data)
{
int temp = new1->data;
new1->data = counter->data;
counter->data = temp;
}
}
}
node = start->next;
printf("\n After sorting the list is as follows:\n");
while(node)
{
printf("%d", node->data);
node = node->next;
}
}
void main()
{
doubly_link_sort();
}
Question: Explain The Doubly Linked list.
Doubly linked list creation algorithm
Step 1 : [Initilization] 1) Start. Next = null
2) Previous. Next = null
Step 2 : [Assign address of start variable to node]
Node = address of start
Step 3 : [Make left and right links of a node]
1) Next [node] = node [make link to node]
2) Previous [node] = node [make link to node]
3) Node = Next [node] [Move pointer to next node]
4) Info [node] = value [Information value of a node]
5) Next [node] = NULL [Assign NULL to the address field]
Step 4 : [ Call Step 3]
Repeat Step 3 to create required number of nodes for linked list
Step 5 : End .
Algorithm for traversing a doubly inked list Step 1 : [initialization]
Node = start. Next [points to the first node in the list]
Step 2 : [Traverse the list in forward direction]
Repeat while Next [node] # NULL process Info [Node]
Step 3 : [Traverse the list in backward direction]
Repeat while Node # NULL Process Info [Node]
Step 4 : Exit.
Algorithm to insert a node at right of the right most node Step 1 : [Initialization]
Node =Start
Step 2 : [Create a new node] New = Create a Node
Step 3 : [Read information associated with newly created node]
Info [Newly] = value
Step 4 : [Perform the insertion]
I) Next [new] = node
II) Previous [New] = Previous [node]
III) Next [Previous[node]] = New
IV) Next [Node] = New
Step 5 : Exit
Algorithm to delete right most node Step 1 : [Initialization]
Node = Start
Step 2 : [Initialization counter]
Counter = 0
Step 3 : [check the list]
If Node = Null
Output “underflow” and exit
Step 4 : [count the number of nodes available in the list]
Repeat while Node # NULL
I) Node = Next [Node]
II) Counter = Counter + 1
Step 5 : [perform deletion]
Node = Start
Repeat through (II) while counter # 1
I) Node = Next [Node]
II) Counter = Counter – 1
III) Next [previous[node]] = Next [Node]
IV) Previous [Next [node]] = previous [node]
V) Delete (node)
Step 6 : Exit.
Algorithm to delete a desired node Step 1 : [Initialization]
Node = Start
Step 2 : [Check the list]
If node = NULL
Output “underflow” and Exit
Step 3 : [Set the counter ]
Search = 0
Step 4 : [Input the node number to which you want to delete]
Node delete = value
Step 5 : [Perform deletion]
Repeat while Node # NULL
If Search = Delete _Node
Next [Previous [Node]] = Next [Node]
Previous [Next[Node]] = Previous [Node]
Delete (Node)
Else
Node = Next [node]
Search = Search + 1
Step 6 : Exit
Example:
#include<stdio.h>
#include<malloc.h>
struct dnode
{
struct dnode *prv;
int data;
struct dnode *next;
};
main()
{
struct dnode *p;
int ans;
p=NULL;
clrscr();
do
{
printf("\n1:enter new node:\n");
printf("2:enter new node at begining:\n");
printf("3:enter new node at position:\n");
printf("4:display value:\n");
printf("5:delete node:\n");
printf("6:exit\n");
printf("enter your choice :");
scanf("%d",&ans);
switch(ans)
{
case 1:
append(&p);
break;
case 2:
addatbeg(&p);
break;
case 3:
addatpos(&p);
break;
case 4:
display(p);
break;
case 5:
deletatpos(&p);
break;
case 6:
exit(0);
break;
}
}while(ans!=6);
getch();
return;
}
append(struct dnode **q)
{
struct dnode *temp,*r;
int n;
temp=(*q);
if(*q==NULL)
{
*q=(struct dnode*)malloc(sizeof(struct dnode*));
(*q)->prv=NULL;
(*q)->next=NULL;
temp=(*q);
}
else
{
while(temp->next!=NULL)
temp=temp->next;
r=(struct dnode*)malloc(sizeof(struct dnode));
temp->next=r;
r->prv=temp;
r->next=NULL;
temp=temp->next;
}
printf("Enter value:");
scanf("%d",&n);
temp->data=n;
return;
}
addatbeg(struct dnode **q)
{
struct dnode *temp;
int n;
temp=(struct dnode*)malloc(sizeof(struct dnode));
temp->prv=NULL;
temp->next=*q;
(*q)->prv=temp;
printf("Enter value:\n");
scanf("%d",&n);
temp->data=n;
(*q) = (*q)->prv;
return;
}
addatpos(struct dnode **q)
{
struct dnode *temp;
int pos,n,flag=0;
printf("Enter position:\n");
scanf("%d",&pos);
while((*q)->next!=NULL)
{
if((*q)->data==pos)
{
flag=1;
break;
}
else
{
flag=0;
}
(*q)=(*q)->next;
}
if(flag==1)
{
printf("enter value :");
scanf("%d",&n);
temp=(struct dnode*)malloc(sizeof(struct dnode));
temp->prv=(*q)->prv->next;
(*q)->prv->next=temp;
temp->next=*q;
(*q)->prv=temp;
temp->data=n;
}
else
{
printf("element is not available:\n");
}
return;
}
deletatpos(struct dnode **q)
{
struct dnode *temp;
int n;
printf("Enter the position:\n");
scanf("%d",&n);
temp=*q;
while(temp->next!=NULL)
{
if(temp->data==n)
{
if(temp==*q)
{
(*q)=(*q)->next;
(*q)->prv=NULL;
}
else
{
if(temp->next==NULL)
temp->prv->next=NULL;
else
{
temp->prv->next=temp->next;
temp->next->prv=temp->prv;
free(temp);
}
}
}temp=temp->next;
}
return;
}
display(struct dnode *q)
{
while(q!=NULL)
{
printf("%d ",q->data);
q=q->next;
}
return;}
Question : Example of Circular Linked List.
#include<stdio.h>
#include<malloc.h>
struct node
{
int data;
struct node *next;
};
main()
{
struct node *front,*rear;
int ans;
front = rear = NULL;
do
{
printf("\n 1.insert node:\n");
printf("\n 2.delet node:\n");
printf("\n 3.display:\n");
printf("\n 4.exit\n");
printf("enter choice\n");
scanf("%d",&ans);
switch(ans)
{
case 1:
add(&front,&rear);
break;
case 2:
delet(&front,&rear);
break;
case 3:
display(front);
break;
case 4:
break;
}
}while(ans!=4);
return;
}
add(struct node **f,struct node **r)
{
struct node *q;
int a;
q=(struct node*)malloc(sizeof(struct node));
printf("\n enter the value:");
scanf("%d",&a);
q->data=a;
if(*f==NULL)
*f=q;
else
(*r)->next=q;
*r=q;
(*r)->next=*f;
return;
}
delet(struct node **f,struct node **r)
{
struct node *q;
int a;
if(*f==NULL)
printf("\n list empty");
else
{
if(*f==*r)
{
a=(*f)->data;
free(*f);
*f=NULL;
*r=NULL;
}
else
{
q=*f;
a=q->data;
(*f)=(*f)->next;
(*r)->next=*f;
free(q);
}
printf("\n deleted node %d",a);
return;
}
return;
}
display(struct node *f)
{
struct node *q=f,*p=NULL;
while(q!=p)
{
printf("%2d\t",q->data);
q=q->next;
p=f;
}
return;
}
Question: Explain the Binary Tree with Example.
A binary tree is an important type of data structure, which is very useful. A tree is a binary tree if each node of it can have at the most two branches. In other words we can say that if every node of a tree can have at most degree two, then this is called a binary tree. In a binary tree left and right sub-trees distinguish sub-trees of a node.
A binary tree T is a finite set of nodes, which is either empty or consists of special node called root R and two disjoint binary trees T1 and T2 (which are called the left sub-tree and right sub-trees, respectively). If T1 is non-empty then the root of T1 is called the left successor of R. If T2 is non-empty then the root of T2 is known as right successor of R.
Recursive algorithm for binary tree creation :
Create_Tree (Info, Node)
Where Info à Information for which we have to create node.
Node à structure type variable to points both left and right child.
Step 1: [Check whether the tree is empty]
If Node = NULL
Node = Create a node
Left_Child [Node] = NULL
Right_Child [Node]] = NULL
Step 2: [Test for the left child]
If Info [node] >= Info
Left_child [Node] = call Create_Tree
(Info, Left_child [Node])
Else
Right_child [Node] = call Create_Tree
(info, Right_child [Node])
Step 3: Return (Node)
Recursive algorithm of preorder traversing:
Preorder (Node)
Step 1: [Do through step 3]
If Node is not equal to NULL
Output Info [Node]
Step 2: Call Preorder (Left_child [Node])
Step 3: Call Preorder (Right_child Node])
Step 4: Exit
Recursive algorithm of inorder traversing: Inorder (Node)
Step 1: [Do through Step 4]
If Node is not equal to NULL
Step 2: Call Inorder (Left_Child [Node])
Step 3: Output Info [Node]
Step 4: Call Inorder (Right_child [Node])
Step 5: Exit
Recursive algorithm of postorder traversing:
Postorder (Node)
Step 1: [Do through step 4]
If Node is not equal to NULL
Step 2: Call Postorder (Left_Child [Node])
Step 3: Call Postorder (Right_Child Node)
Step 4: Output Info [Node]
Step 5: Exit
Example :
/*program for tree operation*/
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct tree
{
int no;
struct tree *r,*l;
};
void insert(struct tree *root,int x);
void preorder(struct tree *root);
void inorder(struct tree *root);
void postorder(struct tree *root);
void main()
{
struct tree *root = NULL;
int ch=1,x,level,info;
root=(struct tree *)malloc(sizeof(struct tree));
clrscr();
printf("\n enter the value of root:=");
scanf("%d",&root->no);
root->l = root->r=NULL;
while(ch!=0)
{
printf("\n 1:inert\t 2:preorder\t 3:inorder\t 4:postorder");
printf("\t 0:exit");
printf("\n\n enter the choice:=");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\n enter the no");
scanf("%d",&x);
insert(root,x);
break;
case 2:
preorder(root);
break;
case 3:
inorder(root);
break;
case 4:
postorder(root);
break;
}
}
}//main over
void insert(struct tree *root,int x)
{
if(x==root->no)
{
printf("\n duplicate no \n\n\n");
return;
}
if(x < root->no)
{
if(root->l!=NULL)
insert(root->l,x);
else
{
root->l=(struct tree*)malloc(sizeof(struct tree));
root->l->no=x;
root->l->l=root->l->r=NULL;
}
}
else
{
if(root->r!=NULL)
insert(root->r,x);
else
{
root->r=(struct tree*)malloc(sizeof(struct tree));
root->r->no=x;
root->r->r=root->r->l=NULL;
}
}
}//insert over
void inorder(struct tree *root)
{
if(root!=NULL)
{
inorder(root->l);
printf("\n %d",root->no);
inorder(root->r);
}
}//inorder over
void preorder(struct tree *root)
{
if(root !=NULL)
{
printf("\n %d",root->no);
preorder(root->l);
preorder(root->r);
}
}//preorder over
void postorder(struct tree *root)
{
if(root!=NULL)
{
postorder(root->l);
postorder(root->r);
printf("\n %d",root->no);
}
}//postorder over
Question: Explain the Bubble sort with algorithm and example.
Bubble_sort (n, list)
Where
N à Represents the number of elements in the list
L à Represents the list of elements
Step 1: [Initialize]
i = 0
Step 2: Repeat through step 5 while ( i < n )
Step 3 : j = 0;
Step 4: Repeat through step 5 while ( j < n-i)
Step 5: if (list[ j] < list [ j+1]
(i) temp = list[ j]
(ii) list[ j+1] = list[ j]
(iii) list[j] = temp
step 6: Exit
Example :
#include<stdio.h>
#include<stdio.h>
void bubble_sort (int array[], int size)
{
int temp, i, j;
for(i = 0; i < size; i++)
for( j=0;j < size-i-1;j++)
if (array[j] < array[ j+1] )
{
temp = array[j];
array[ j] = array[ j+1];
array[ j+1] = temp;
}
}
void main(void)
{
int values[30], i;
printf(“\n Unsorted list is as follows\n”);
for (i = 0; i < 10; i++)
{
values[i] = rand( ) %100;
printf(“%d”, values[i]);
}
bubble_sort (values , 10);
printf(“\n Sorted list is as follows\n”);
for(i = 0; i < 10;i++)
printf(“%d”,values[i]);
}
Question: Explain the Insertion sort with algorithm and example.
Insertion_sort (l,n)
Where l à Represents the list of elements.
N à Represents number of elementsin the list.
Step 1: [Initialize]
1[0] = -0
Step 2: Repeat through Step 3 to 5 for i=1,2,3,4..n
Step 3: (i) temp = l[i]
(ii) pointer = i – 1
Step 4: while(temp < l[pointer])
(i) l[pointer + 1] = l[pointer]
(ii) pointer = pointer – 1
Step 5: l[pointer] = temp
Step 6: Exit
Example:
#Include<stdio.h>
#include<stdlib.h>
int i, k;
void insertion_sort (int *, int);
void display(int *,int)
void insertion_sort(int l[], int n)
{
int pointer, temp;
l[0] = -0;
for(i = 1 ; i <= n ; i++)
{
pointer = i –1;
temp = l[i];
while(temp <l[ponter])
{
l[pointer+1] = l[pointer];
pointer -;
}
l[pointer+1] = temp;
printf(“Step = %d”,i);
for(k = 0; k <= n; k++)
printf(“%d”, l[k]);
printf(“\n”);
}
}
void display(int l[], int n)
{
printf(“\n Sorted list is as follows\n”);
for(i = 1;i <= n; i++)
printf(“%d”,l[i]);
}
void main()
{
int nember = 20;
int list[100];
int i;
printf(“\n Number of elements in the list : %i” , number);
printf(“\n Unsorted list is as follows \n”);
for(i = 1;i <= number; i++)
{
list[i] = rand() %100;
printf(“%d”,list[i]);
}
printf(“\n”);
printf(“\n Stepwise result is as follows \n\n”);
insertion_sort(list, number);
display(list, number);
}
Question: Explain the Quick sort with algorithm and example.
Q_SORT (Array, first, last)
Where array à Represents the list of elements;
First à Represents the position of the first elements in the list (Only at the starting point, it’s value changes during the excution of the function).
Last à Represents the position of the last elements in the list(Only at starting point the value of it’s changes during the execution of the function).
Step 1: [initially]
Low = first
High = last
Pivot = array[(low+high)/2] [middle elements of the elements of the list]
Step 2: Repeat through Step 7 while (low <= high)
Step 3: Repeat Step 4 while (array[low] < pivot)
Step 4: low = low +1
Step 5: Repeat Step 6 while (array[high] > pivot)
Step 6:high = high – 1
Step 7: if ( low<= high)
(i) temp = array[low]
(ii) array[low] = array[high]
(iii) array[high] = temp
(iv) low = low + 1
(v) high = high – 1
Step 8: if ( first < high ) Q_sort(array, first, high)
Step 9: if ( low < lase ) Q_sort(array, low, lase)
Step 10: exit
Example:
#include<stdio.h>
#include<stdlib.h>
void quick_sort(int array[], int first, int last)
{
int temp, low, high, pivot;
low = first;
high = last;
pivot = array[(first + lase) / 2];
do{
while (array[low] < pivot)
low++;
while (array[high] > pivot)
high-;
if(low <= high)
{
temp = array[low];
array[low++] = array[high];
array[high-] = temp;
}
}wihle(low <=high);
if(first < high)
quick_sort(arry, first, high);
if (low < last)
quick_sort(arry, low, last);
}
void main()
{
int values[100], i;
printf(“\n Unsorted list is as follows \n”);
for (i = 0; i < 20; i++)
{
values[i] = rand() % 100;
peintf(“%d”, values[i]);
}
quick_sort(values, 0, 19);
printf(“\n Sorted list as follows \n);
for(i = 0; i < 20; i++)
printf(“%d”, values[i]);
}
Question: Explain the Selection sort with algorithm and example.
Selection_sort (array, size)
Where array à Represents the list of elements
Size à Represents size of the list
Step 1: current = 0 [initially]
Step 2: Repeat through Step 7 while (current < size)
Step 3: j = current + 1;
Step 4: Repeat through Step 6 while (j < size)
Step 5: if (array [current] > array [j])
(i) temp = array[current]
(ii) arra[current] = array[j]
(iii) array[j] =temp
step 6: j = j + 1
Step 7: current = current + 1
Step 8: Exit
Example:
#include<stdio.h>
#include<stdlib.h>
void selection_sort[int array[], int size)
{
int temp, current, j;
for(current = 0; current < size; current++)
for(j = current +1; j < size; j++)
if(array[current] > array[j])
{
temp = array[current];
array[current] = array[j];
array[j] = temp;
}
}
void main()
{
int values[30], i;
printf(“\n Unsorted list is as follows\n”)
for(i = 0; i < 30; i++)
{
values[i] = rand() % 100;
printf(“%d”, values[i]);
}
selection_sort(values, 30 );
printf(“\n sorted list is as follows\n”);
for ( i = 0; i < 30; i++)
printf(“%d”, values[i]);
}
Question: Explain the Shell sort with algorithm and example.
Shell_sort(array, size)
Where array à Represents the list of elements
Size à Represents the size of the list
Step 1: [Initialize]
Gap = size / 2
Stpe 2: Repeat through Step 6 while(gap = gap / 2)
Step 3: swap = 0
Step 4: Repeat through Step 6 for i=0, 1, 2, 3…i <(size – gap)
Step 6:if (array[i] > array[i+gap]
(i) temp = array [i]
(ii) array[i] = array[i + gap]
(iii) array[i + gap]= temp
(iv) swap = 1
[ End of for loop]
[ End of inner while loop]
[ End of outer while loop]
Step 7: output arrayelements (sorted)
Step 8: Exit
Example:
#include<stdio.h>
#include<stdlib.h>
void shell_sort(int array[], int size)
{
int temp, gap, i, swap;
gap = size / 2;
do {
do {
swap = 0;
for (i = 0; i < size – gap; i++)
if(array[i] > array[i + gap])
{
temp = array[i];
array[i] = array[i + gap];
array[i + gap] = temp;
swap = 1;
}
}while (swap);
}while (gap = gap / 2);
}
void main(void)
{
int values[50], i;
print(“\n Unsorted list is as follows \n”);
for(i = 0; i < 50; i++)
{
values[i] = rand() % 100;
printf(“%d”, values[i]);
}
shell_sort(values, 50);
printf(“\n Sorted list is as follow \n”);
for(i = 0; i < 50; i++)
printf(“%d”, value[i]);
}
When we declare an array in out program, the compiler allocates memory to hold the array prior to providing it. Some times it is required to change the size of the array and in that case it is required to edit and compile the program. To reduce the number of changes, it is required to allocate required memory during the run-time. For example, suppose we want to read a file into memory from the disk. If the size of file is not known and we have to load it into memory and defining very large array, so that file can fit into the array. If the size of the array is larger than that of file then the space is wasted. If the size of file is larger then it is not possible to load the complete file into the array, leading to need for dynamic memory allocation. In the dynamic memory allocation we use a pointer variable and it’s size is allocated during the execution of the program. There are two principle functions in C which are used to allocate required memory to pointer variable.
1. malloc()
2. calloc()
Both the malloc() and calloc() functions performs the operations and checks memory availability, based on the memory block size requested. When a suitable segment of memory is located. A pointer to the address of the allocated block is returned by the function.
1. malloc()
This function is used to allocate a requested number of bytes from the free pool of memory, and returns a pointer to a block of contiguous memory of the size specified.
This function allocates a block of memory and returns a pointer which points the first byte of the allocated space or memory block and if memory allocation was not successful, it returns a NULL pointer.
Syntax :
<pointer> = (<cast type> *) malloc(<no. of bytes to be allocated>);
“Pointer” is the name of a pointer of type cast type.
The malloc() functions returns a pointer of cast type to an area of memory with size as no. of bytes to be allocated.
Example:
mpointer = (int *) malloc(50 * sizeof(int));
After the successful execution of the above statement, a memory space equivalent to “50 times the size of an int” is reserved, and the address of the first byte of this block of memory allocated is assigned to the pointer mpointer of type int.
If an integer takes 2 bytes of storage space, the above declaration will allocate 100 bytes of contiguous storage space.
The malloc() function always returns a pointer to the first byte of the block of memory that has been allocated. It allocates a contiguous block of memory. If the allocation fails, i.e. malloc() is not able to allocate the required bytes of memory as a contiguous block, it returns NULL pointer.
2. calloc()
‘C’ also provides the calloc() function for allocating memory.
This function is normally used to request memory allocation at run time for storing derived data types such as arrays and structures.
calloc() function allocates multiple blocks of storages, each block of the same size and then sets all the bytes of memory in the block to zero.
Syntax:
<pointer> = (<cast-type> *) calloc(<no. of blocks>, <size of element>);
The calloc() function allocates contiguous space of “no. of block”, each block being of size, “size of element”. All the bytes of memory allocated are then initialized to zero, and a pointer to the first byte of the allocated contiguous memory is returned. In case, there is not enough memory available in the free pool of memory, a NULL pointer is returned.
3. free()
When we are dynamically allocating memory for variables at run time, the memory is not automatically released to the system. It is responsibility of a programmer, who has dynamically allocated memory, to released the memory to the free pool of memory when the memory is not needed.
‘C’ provides the free() function to release a block of memory that was allocated and is no longer needed.
Syntax:
free(<pointer>);
“pointer” is a pointer to the memory block that was returned by either malloc() and calloc() function calls.
4. realloc()
After, memory has been allocated to variables at run time, there may be a need to change the size of block of memory that was allocated. ‘C’ provides the realloc() function, using which the memory can be reallocated to increase or decrease the size of allocated memory.
Syntax:
<pointer> = realloc(<pointer>, <new memory size>);
“pointer” is the pointer that points the first byte of the memory that was allocated using either malloc() or calloc() functions.
“new memory size” indicates the new size of memory that is to be allocated. This new size could be more or less than the original size.
It is important to note here that the new block of memory may or may not begin at the same place as the old block.
In case, the functions fails to reallocate a larger memory in contiguous block at the location, it will create the same as an entirely new region and move the contents of the old block into the new block. The function guarantees that the old data will remain intact.
If the realloc() function fails to allocates additional space, it returns the NULL pointer and the original block is lost. Therefore, it is necessary for a programmer to test for the success of the function before reallocating memory, so that, old data is not lost.
Question: Explain DATA STRUCTURE and types of DATA STRUCTURE.
DATA STRUCTURE is a collection of data elements whose organization is characterized by assessing operations that are used to store and retrieve the individual data elements; the implementation of the composite data members in an abstract data type. An abstract data type can be define as a data type whose properties are specified independently of any particular implementation.
The DATA STRUCTURE is classified in the following categories:
1. Linear Data Structures
In the linear Data Structures processing of data items is possible in linear fashion, i.e., data can be processed one by one sequentially. Linear data structures contains following types of data structures.
I. Array
II. Linked List
III. Stack and Queues
2. Nonlinear Data Structures
A Data Structures in which insertion and deletion is not possible in a linear fashion is called nonlinear DATA STRUCTURE. In this category of DATA STRUCTURE, we will discuss the following.
I. Tree
II. Graph
Question: What is Primitive and Non-primitive Datastructure (Datatypes)?
Primitive Datastructure:
This is the data structure that typically are directly operated upon by machine-level instructions. We will present storage representations for these data structures for a variety of machines. For example, declaration of variables with basic datatypes are the example of primitive data structure.
Non-Primitive Datastructure:
Non-primitive data structures can be classified as arrays, lists and files. As array is an ordered set which consists of a fixed number of objects. No deletion or insertion operations are performed on arrays. A list, on the other hand, is an ordered set consisting of a variable number of elements to which insertions and deletions can be made.
Question: What is STACK? Explain the operations of STACK with example.
A STACK is defined formally as a list (a linear DATA STRUCTURE) in which all insertion and deletions are made at one end called the Top Of Stack (TOS). The fundamental operations, which are possible on a stack, are:
1. Push à Insertion
2. Pop à Deletion
3. Peep à Extract Information
4. Update à Update information associated at some location in the stack.
The most recently pushed element can be checked prior to performing a pop operation. A stack is based on the Last In First Out algorithm (LIFO) in which insertion and deletion operations are performed at one end of a stack. Also, the information can only be removed in the opposite order in which it was added to the stack. The most accessible information in a stack is at the top of stack and least accessible information is at the bottom of the stack.
For example, consider a stack of plates on the counter in a cafeteria. During the dinner time customers take plates from the top of the stack and waiter puts the washed plates on the top of the stack. The plate that is put most recently on the stack is the first one to bed taken off. The plate at the bottom is the last one to be used. This discussion can further be understood with the help of following figure.
A pointer TOS keeps track of the top most information in the STACK. Initially when the stack is empty, TOS has a value zero and when the stack contains a single information TOS has a value one and so on. Before an item is pushed onto the stack, the pointer is incremented by one. The pointer is decrement by one each time a deletion is made from the stack.
The Use Of STACK.
We have already discussed that a stack is a list and hence any of the list implementation techniques may be used to implement a stack. Two common use of stack are through:
1. Pinter (Linked List)
2. Array
The Algorithm Of STACK.
1. Push Operation:
Push means to insert an item onto the stack. The push algorithm is illustrated below. The algorithm illustrated inserts an item to the top of stack, which is represented by array S and containing Size number of items with a pointer Tos denoting the position of top most item in the stack.
Step 1 : [check for stack overflow]
If Tos >= Size
Output “Stack is Overflow” and exit
Step 2 : [Increment the Pointer value by one]
Tos = Tos + 1
Step 3 : [perform insertion]
S[Tos] = Value
Step 4 : Exit
2. Pop Operation:
The pop operation deletes or removes the topmost item from the stack. After removal of top most information, new value of the pointer Tos becomes the previous value of Tos that is Tos = Tos – 1 and freed position is allocated to free space. The algorithm to remove an item from the stack is illustrated below.
Step 1 :[check whether the stack is empty]
If Tos = 0
Output “Stack underflow” and exit
Step 2 :[Remove the Tos information]
Value = S[Tos]
Tos = Tos – 1
Step 3 :[Return the former information of the stack]
Return (Value)
/*USE OF THE STACK USING ARRAYS */
#include<stdio.h>
#define SIZE 5
int arr[SIZE];
int tos=0;
main()
{
int ans;
clrscr();
do
{
printf("1. Enter the New Element :\n");
printf("2. Remove The Element :\n");
printf("3. Display Stack :\n");
printf("4. Exit :\n");
printf("Enter Your Choice :");
scanf("%d",&ans);
switch(ans)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
break;
default:
printf("You Have Entered Wronge Choice...\n");
}
}while(ans != 3);
getch();
return;
}
push()
{
int newitem;
if(tos >= SIZE)
{
printf("The STACK is Full....\n");
return;
}
else
{
printf("Enter the New Value :");
scanf("%d",&newitem);
arr[tos]=newitem;
tos++;
}
getch();
return;
}
pop()
{
int remitem;
if(tos <= 0)
{
printf("The STACK is Empty....\n");
return;
}
else
{
tos--;
remitem = arr[tos];
printf("The Removeble item is %d.\n",remitem);
}
getch();
return;
}
display()
{
int x;
if(tos<=0)
{
printf("Your STACK is Empty....\n");
return;
}
else
{
while(tos>=0)
printf("%d ",arr[--tos]);
}
getch();
return;}
/* USE OF STACK USING POINTER AND STRUCTURE. */
#include<stdio.h>
#define SIZE 5
struct library
{
int b_no[SIZE];
}*book;
int cnt=0;
main()
{
int ans;
clrscr();
do
{
printf("1. Enter the New Element :\n");
printf("2. Remove The Element :\n");
printf("3. Exit :\n");
printf("Enter Your Choice :");
scanf("%d",&ans);
switch(ans)
{
case 1:
push(book);
break;
case 2:
pop(book);
break;
case 3:
break;
default:
printf("You Have Entered Wronge Choice...\n");
}
}while(ans != 3);
getch();
return;
}
push(struct library *bk)
{
int newitem;
if(cnt >= SIZE)
{
printf("The STACK is full...\n");
return;
}
else
{
printf("Enter the New Value :");
scanf("%d",&newitem);
bk->b_no[cnt++] = newitem;
}
getch();
return;
}
pop(struct library *bk)
{
int remitem;
if(cnt <= 0)
{
printf("The STACK is empty...\n");
return;
}
else
{
remitem = bk->b_no[--cnt];
printf("The Removeble item is %d\n",remitem);
}
getch();
return;
}
Question: Explain the Applications of STACK.
There are three applications in which stacks are used. The first application deals with recursion. Recursion is an important facility in many programming languages such as ALGOL 60 and PASCAL. There are many problems whose algorithmic description is best described in a recursive manner.
The second application of a stack is classical; it deals with the compilation of infix expressions into object code.
The third application of a stack is stack machine. Certain computers perform stack operations at the hardware or machine level, and these operations enable insertions to and deletions from a stack to be made very rapidly.
1. Recursion:
The natural numbers have been defined recursively through the process of induction. Recursion is the name given to the technique of defining a set or a process in terms or itself.
1, if N = 0
N * FACTORIAL(N-1), otherwise
The factorial function, whose domain is the natural numbers, can be recursively defined as,
FACTORIAL(N) =
Here the FACTORIAL(N) is defined in terms of FACTORIAL(N-1), which in turn is defined in terms of FACTORIAL(N-2), etc. until finally FACTORIAL(0) is reached, whose value is given as “one”. The basic idea is to define a function for all its argument values in a constructive manner by using induction. The value of a function for a particular argument value can be computed in a finite number of steps using the recursive definition, where at each step of recursion we get nearer to the solution.
2. Classical (Polish Expression and Their Compilation) :
In this section we shall primarily concerned with the mechanical evaluation or compilation of infix expressions. We shall find it to be more efficient to evaluate an infix arithmetical expression by first converting it to a suffix expression and then evaluating the latter. This approach will eliminate the repeated scanning of an infix expression in order to obtain its value.
3. Stack Machines:
One of the main problems with using machines which have a very limited number of registers is how to handle the storage of intermediate results. In particulars, we must be very cognizant of the generation of wasted store/load instruction sequences. In this sections we illustrate how the presence of the simple stack operations of POP and PUSH can enhance the process of generating code from a reverse-polish string. The instructions available for this machine are given in mnemonic form as follows:
1. PUSH<name> - Load from memory onto stack. This instructions loads an operand from the memory location named <name> and places the contents of <name> on the stack.
2. POP <name> - Store top of stack in memory. The contents of the top of the stack are removed and stored in the memory location referenced by <name>.
3. ADD, SUM, MUL, DIV – Arithmetic operation.
Question: Explain Polish Notation.
The process of writing the operators of an expression either before their operands or after them is called the Polish notation in honor of its discoverer, the Polish mathematician jan Luksiewicz. The fundamental property of Polish notation is that the order in which the operations are to be performed is completely determined by the position of the operators and operands in the expression. Accordingly, one never needs parenthesis when writing expression in Polish notation. The Polish notations are classified into three categories. These are:
1. Infix
2. Prefix
3. Postfix
1. Infix:
When the operators exist between two operands then the expression is called Infix expression. For example, let a + b * c is an expression, by inspecting we find that the operator + exists between the operands a and b, and operator * exists between the operands b and c, hence we say that a + b * c is an infix expression.
2. Prefix:
When the operators are written before their operands then the resulting expression is called the prefix Polish notation. Suppose we want to change the infix expression a + b * c it’s prefix form. First of all we consider the precedence of the operators present in the infix expression. Here in the given infix expression there are two operands + and *. The precedence of the * is higher than that of the +. The step which are required to change infix expression a + b * c into it’s equivalent prefix form are as follows:
Step 1 : a + * b c
Step 2 : + a * b c
3. Postfix:
When the operators come after their operands the resulting expression is called the reverse Polish notation or postfix expression.
For example, suppose a + b * c is an infix expression then after changing this expression into post form we get
Step 1 : a + b c *
Step 2 : a b c * +
Question: Explain Linear queues with algorithm and example.
This is a linear list DATA STRUCTURE used to represent a linear list and permits deletion to be performed at one end of the list and the insertion at the other end. The information in such a list is processed in the same order as it was received, that is on first-come-first-out (FIFO) basis. The Railway Reservation counter is an example of queue where the people collect their tickets on the first-come-first-serve (FIFS) basis. There are two types of operations possible on the linear queue.
1. Insertion (from rear side)
2. Deletion (from front side)
USE OF QUEUE :
Two common ways in which queues may be implemented are as follows:
1. Arrays
2. Pointers
(Draw the figure)
A queue has two pointers front and rear, pointing to the front and rear elements of the queue, respectively. Consider a queue Q consisting of n elements and an elements Value, which we have no insert into the Q. The value NULL (0) of front pointer implies an empty queue and the MAXVALUE implies the queue is full.
ALGORITHM OF QUEUE:
1. Insert Operation:
Insert operation inserting the new value from the rear side (right hand side). The first value is arranged in the queue as a left most value (in queue as first value) and second value is also inserted on rear side and set behind first value. Thus, each new value is set behind the previous entered value.
Step 1: [Check overflow condition]
if rear >= size
Output “Overflow” and return
Step 2: [Increment rear pointer]
Rear = rear + 1
Step 3: [Insert an element]
Q [rear] = value
Step 4: [Set the front pointer]
If front = 0
front = 1
Step 5: return
(here draw the box figure of inserting of node.)
2. Deletion Operation:
Deletion Operation is used to remove the values in the queue. It is works on the first-in-first-out (FIFO) basis, means, it is removed item from the front side (at the right hand side of the queue). This operation is removed first entered item after second entered item and so on in the queue.
Step 1: [Check underflow condition]
if front = 0
Output “Underflow” and return
Step 2: [Remove an element]
Value = Q [front]
Step 3: [Check for empty queue]
If front = rear
front = 0
rear = 0
else
front = front + 1
(Here draw the box figure of Deletion Operation.)
/*USE OF QUEUE IN THE ARRAY.*/
#include<stdio.h>
#define SIZE 3
int arr[SIZE];
int front = 0;
int rear = 0;
main()
{
int ans;
clrscr();
do
{
printf("1. Enter New Element.\n");
printf("2. Remove New Element.\n");
printf("3. Exit.\n");
printf("Enter Your Choice :");
scanf("%d",&ans);
switch(ans)
{
case 1:
insert();
break;
case 2:
rem();
break;
case 3:
break;
default:
printf("You Have Enter Wronge Choice...\n");
}
}while(ans!=3);
getch();
return;
}
insert()
{
int newitem;
if(rear>=SIZE)
{
printf("Your QUEUE is FULL...\n");
return;
}
else
{
printf("Enter New Value :");
scanf("%d",&newitem);
arr[++rear]=newitem;
}
if(front==0)
front=1;
getch();
return;
}
rem()
{
int remitem;
if(front>rear)
{
printf("Your QUEUE is EMPTY...\n");
front=0;
rear=0;
return;
}
else
{
remitem=arr[front++];
printf("The Removed Item Is %d.\n",remitem);
}
getch();
return;
}
Question : Explain the Dynamic Memory Allocation and following function.
When we declare an array in out program, the compiler allocates memory to hold the array prior to providing it. Some times it is required to change the size of the array and in that case it is required to edit and compile the program. To reduce the number of changes, it is required to allocate required memory during the run-time. For example, suppose we want to read a file into memory from the disk. If the size of file is not known and we have to load it into memory and defining very large array, so that file can fit into the array. If the size of the array is larger than that of file then the space is wasted. If the size of file is larger then it is not possible to load the complete file into the array, leading to need for dynamic memory allocation. In the dynamic memory allocation we use a pointer variable and it’s size is allocated during the execution of the program. There are two principle functions in C which are used to allocate required memory to pointer variable.
1. malloc()
2. calloc()
Both the malloc() and calloc() functions performs the operations and checks memory availability, based on the memory block size requested. When a suitable segment of memory is located. A pointer to the address of the allocated block is returned by the function.
1. malloc()
This function is used to allocate a requested number of bytes from the free pool of memory, and returns a pointer to a block of contiguous memory of the size specified.
This function allocates a block of memory and returns a pointer which points the first byte of the allocated space or memory block and if memory allocation was not successful, it returns a NULL pointer.
Syntax :
<pointer> = (<cast type> *) malloc(<no. of bytes to be allocated>);
“Pointer” is the name of a pointer of type cast type.
The malloc() functions returns a pointer of cast type to an area of memory with size as no. of bytes to be allocated.
Example:
mpointer = (int *) malloc(50 * sizeof(int));
After the successful execution of the above statement, a memory space equivalent to “50 times the size of an int” is reserved, and the address of the first byte of this block of memory allocated is assigned to the pointer mpointer of type int.
If an integer takes 2 bytes of storage space, the above declaration will allocate 100 bytes of contiguous storage space.
The malloc() function always returns a pointer to the first byte of the block of memory that has been allocated. It allocates a contiguous block of memory. If the allocation fails, i.e. malloc() is not able to allocate the required bytes of memory as a contiguous block, it returns NULL pointer.
2. calloc()
‘C’ also provides the calloc() function for allocating memory.
This function is normally used to request memory allocation at run time for storing derived data types such as arrays and structures.
calloc() function allocates multiple blocks of storages, each block of the same size and then sets all the bytes of memory in the block to zero.
Syntax:
<pointer> = (<cast-type> *) calloc(<no. of blocks>, <size of element>);
The calloc() function allocates contiguous space of “no. of block”, each block being of size, “size of element”. All the bytes of memory allocated are then initialized to zero, and a pointer to the first byte of the allocated contiguous memory is returned. In case, there is not enough memory available in the free pool of memory, a NULL pointer is returned.
3. free()
When we are dynamically allocating memory for variables at run time, the memory is not automatically released to the system. It is responsibility of a programmer, who has dynamically allocated memory, to released the memory to the free pool of memory when the memory is not needed.
‘C’ provides the free() function to release a block of memory that was allocated and is no longer needed.
Syntax:
free(<pointer>);
“pointer” is a pointer to the memory block that was returned by either malloc() and calloc() function calls.
4. realloc()
After, memory has been allocated to variables at run time, there may be a need to change the size of block of memory that was allocated. ‘C’ provides the realloc() function, using which the memory can be reallocated to increase or decrease the size of allocated memory.
Syntax:
<pointer> = realloc(<pointer>, <new memory size>);
“pointer” is the pointer that points the first byte of the memory that was allocated using either malloc() or calloc() functions.
“new memory size” indicates the new size of memory that is to be allocated. This new size could be more or less than the original size.
It is important to note here that the new block of memory may or may not begin at the same place as the old block.
In case, the functions fails to reallocate a larger memory in contiguous block at the location, it will create the same as an entirely new region and move the contents of the old block into the new block. The function guarantees that the old data will remain intact.
If the realloc() function fails to allocates additional space, it returns the NULL pointer and the original block is lost. Therefore, it is necessary for a programmer to test for the success of the function before reallocating memory, so that, old data is not lost.
Question: Explain DATA STRUCTURE and types of DATA STRUCTURE.
DATA STRUCTURE is a collection of data elements whose organization is characterized by assessing operations that are used to store and retrieve the individual data elements; the implementation of the composite data members in an abstract data type. An abstract data type can be define as a data type whose properties are specified independently of any particular implementation.
The DATA STRUCTURE is classified in the following categories:
1. Linear Data Structures
In the linear Data Structures processing of data items is possible in linear fashion, i.e., data can be processed one by one sequentially. Linear data structures contains following types of data structures.
I. Array
II. Linked List
III. Stack and Queues
2. Nonlinear Data Structures
A Data Structures in which insertion and deletion is not possible in a linear fashion is called nonlinear DATA STRUCTURE. In this category of DATA STRUCTURE, we will discuss the following.
I. Tree
II. Graph
Question: What is Primitive and Non-primitive Datastructure (Datatypes)?
Primitive Datastructure:
This is the data structure that typically are directly operated upon by machine-level instructions. We will present storage representations for these data structures for a variety of machines. For example, declaration of variables with basic datatypes are the example of primitive data structure.
Non-Primitive Datastructure:
Non-primitive data structures can be classified as arrays, lists and files. As array is an ordered set which consists of a fixed number of objects. No deletion or insertion operations are performed on arrays. A list, on the other hand, is an ordered set consisting of a variable number of elements to which insertions and deletions can be made.
Question: What is STACK? Explain the operations of STACK with example.
A STACK is defined formally as a list (a linear DATA STRUCTURE) in which all insertion and deletions are made at one end called the Top Of Stack (TOS). The fundamental operations, which are possible on a stack, are:
1. Push à Insertion
2. Pop à Deletion
3. Peep à Extract Information
4. Update à Update information associated at some location in the stack.
The most recently pushed element can be checked prior to performing a pop operation. A stack is based on the Last In First Out algorithm (LIFO) in which insertion and deletion operations are performed at one end of a stack. Also, the information can only be removed in the opposite order in which it was added to the stack. The most accessible information in a stack is at the top of stack and least accessible information is at the bottom of the stack.
For example, consider a stack of plates on the counter in a cafeteria. During the dinner time customers take plates from the top of the stack and waiter puts the washed plates on the top of the stack. The plate that is put most recently on the stack is the first one to bed taken off. The plate at the bottom is the last one to be used. This discussion can further be understood with the help of following figure.
A pointer TOS keeps track of the top most information in the STACK. Initially when the stack is empty, TOS has a value zero and when the stack contains a single information TOS has a value one and so on. Before an item is pushed onto the stack, the pointer is incremented by one. The pointer is decrement by one each time a deletion is made from the stack.
The Use Of STACK.
We have already discussed that a stack is a list and hence any of the list implementation techniques may be used to implement a stack. Two common use of stack are through:
1. Pinter (Linked List)
2. Array
The Algorithm Of STACK.
1. Push Operation:
Push means to insert an item onto the stack. The push algorithm is illustrated below. The algorithm illustrated inserts an item to the top of stack, which is represented by array S and containing Size number of items with a pointer Tos denoting the position of top most item in the stack.
Step 1 : [check for stack overflow]
If Tos >= Size
Output “Stack is Overflow” and exit
Step 2 : [Increment the Pointer value by one]
Tos = Tos + 1
Step 3 : [perform insertion]
S[Tos] = Value
Step 4 : Exit
2. Pop Operation:
The pop operation deletes or removes the topmost item from the stack. After removal of top most information, new value of the pointer Tos becomes the previous value of Tos that is Tos = Tos – 1 and freed position is allocated to free space. The algorithm to remove an item from the stack is illustrated below.
Step 1 :[check whether the stack is empty]
If Tos = 0
Output “Stack underflow” and exit
Step 2 :[Remove the Tos information]
Value = S[Tos]
Tos = Tos – 1
Step 3 :[Return the former information of the stack]
Return (Value)
/*USE OF THE STACK USING ARRAYS */
#include<stdio.h>
#define SIZE 5
int arr[SIZE];
int tos=0;
main()
{
int ans;
clrscr();
do
{
printf("1. Enter the New Element :\n");
printf("2. Remove The Element :\n");
printf("3. Display Stack :\n");
printf("4. Exit :\n");
printf("Enter Your Choice :");
scanf("%d",&ans);
switch(ans)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
break;
default:
printf("You Have Entered Wronge Choice...\n");
}
}while(ans != 3);
getch();
return;
}
push()
{
int newitem;
if(tos >= SIZE)
{
printf("The STACK is Full....\n");
return;
}
else
{
printf("Enter the New Value :");
scanf("%d",&newitem);
arr[tos]=newitem;
tos++;
}
getch();
return;
}
pop()
{
int remitem;
if(tos <= 0)
{
printf("The STACK is Empty....\n");
return;
}
else
{
tos--;
remitem = arr[tos];
printf("The Removeble item is %d.\n",remitem);
}
getch();
return;
}
display()
{
int x;
if(tos<=0)
{
printf("Your STACK is Empty....\n");
return;
}
else
{
while(tos>=0)
printf("%d ",arr[--tos]);
}
getch();
return;}
/* USE OF STACK USING POINTER AND STRUCTURE. */
#include<stdio.h>
#define SIZE 5
struct library
{
int b_no[SIZE];
}*book;
int cnt=0;
main()
{
int ans;
clrscr();
do
{
printf("1. Enter the New Element :\n");
printf("2. Remove The Element :\n");
printf("3. Exit :\n");
printf("Enter Your Choice :");
scanf("%d",&ans);
switch(ans)
{
case 1:
push(book);
break;
case 2:
pop(book);
break;
case 3:
break;
default:
printf("You Have Entered Wronge Choice...\n");
}
}while(ans != 3);
getch();
return;
}
push(struct library *bk)
{
int newitem;
if(cnt >= SIZE)
{
printf("The STACK is full...\n");
return;
}
else
{
printf("Enter the New Value :");
scanf("%d",&newitem);
bk->b_no[cnt++] = newitem;
}
getch();
return;
}
pop(struct library *bk)
{
int remitem;
if(cnt <= 0)
{
printf("The STACK is empty...\n");
return;
}
else
{
remitem = bk->b_no[--cnt];
printf("The Removeble item is %d\n",remitem);
}
getch();
return;
}
Question: Explain the Applications of STACK.
There are three applications in which stacks are used. The first application deals with recursion. Recursion is an important facility in many programming languages such as ALGOL 60 and PASCAL. There are many problems whose algorithmic description is best described in a recursive manner.
The second application of a stack is classical; it deals with the compilation of infix expressions into object code.
The third application of a stack is stack machine. Certain computers perform stack operations at the hardware or machine level, and these operations enable insertions to and deletions from a stack to be made very rapidly.
1. Recursion:
The natural numbers have been defined recursively through the process of induction. Recursion is the name given to the technique of defining a set or a process in terms or itself.
1, if N = 0
N * FACTORIAL(N-1), otherwise
The factorial function, whose domain is the natural numbers, can be recursively defined as,
FACTORIAL(N) =
Here the FACTORIAL(N) is defined in terms of FACTORIAL(N-1), which in turn is defined in terms of FACTORIAL(N-2), etc. until finally FACTORIAL(0) is reached, whose value is given as “one”. The basic idea is to define a function for all its argument values in a constructive manner by using induction. The value of a function for a particular argument value can be computed in a finite number of steps using the recursive definition, where at each step of recursion we get nearer to the solution.
2. Classical (Polish Expression and Their Compilation) :
In this section we shall primarily concerned with the mechanical evaluation or compilation of infix expressions. We shall find it to be more efficient to evaluate an infix arithmetical expression by first converting it to a suffix expression and then evaluating the latter. This approach will eliminate the repeated scanning of an infix expression in order to obtain its value.
3. Stack Machines:
One of the main problems with using machines which have a very limited number of registers is how to handle the storage of intermediate results. In particulars, we must be very cognizant of the generation of wasted store/load instruction sequences. In this sections we illustrate how the presence of the simple stack operations of POP and PUSH can enhance the process of generating code from a reverse-polish string. The instructions available for this machine are given in mnemonic form as follows:
1. PUSH<name> - Load from memory onto stack. This instructions loads an operand from the memory location named <name> and places the contents of <name> on the stack.
2. POP <name> - Store top of stack in memory. The contents of the top of the stack are removed and stored in the memory location referenced by <name>.
3. ADD, SUM, MUL, DIV – Arithmetic operation.
Question: Explain Polish Notation.
The process of writing the operators of an expression either before their operands or after them is called the Polish notation in honor of its discoverer, the Polish mathematician jan Luksiewicz. The fundamental property of Polish notation is that the order in which the operations are to be performed is completely determined by the position of the operators and operands in the expression. Accordingly, one never needs parenthesis when writing expression in Polish notation. The Polish notations are classified into three categories. These are:
1. Infix
2. Prefix
3. Postfix
1. Infix:
When the operators exist between two operands then the expression is called Infix expression. For example, let a + b * c is an expression, by inspecting we find that the operator + exists between the operands a and b, and operator * exists between the operands b and c, hence we say that a + b * c is an infix expression.
2. Prefix:
When the operators are written before their operands then the resulting expression is called the prefix Polish notation. Suppose we want to change the infix expression a + b * c it’s prefix form. First of all we consider the precedence of the operators present in the infix expression. Here in the given infix expression there are two operands + and *. The precedence of the * is higher than that of the +. The step which are required to change infix expression a + b * c into it’s equivalent prefix form are as follows:
Step 1 : a + * b c
Step 2 : + a * b c
3. Postfix:
When the operators come after their operands the resulting expression is called the reverse Polish notation or postfix expression.
For example, suppose a + b * c is an infix expression then after changing this expression into post form we get
Step 1 : a + b c *
Step 2 : a b c * +
Question: Explain Linear queues with algorithm and example.
This is a linear list DATA STRUCTURE used to represent a linear list and permits deletion to be performed at one end of the list and the insertion at the other end. The information in such a list is processed in the same order as it was received, that is on first-come-first-out (FIFO) basis. The Railway Reservation counter is an example of queue where the people collect their tickets on the first-come-first-serve (FIFS) basis. There are two types of operations possible on the linear queue.
1. Insertion (from rear side)
2. Deletion (from front side)
USE OF QUEUE :
Two common ways in which queues may be implemented are as follows:
1. Arrays
2. Pointers
(Draw the figure)
A queue has two pointers front and rear, pointing to the front and rear elements of the queue, respectively. Consider a queue Q consisting of n elements and an elements Value, which we have no insert into the Q. The value NULL (0) of front pointer implies an empty queue and the MAXVALUE implies the queue is full.
ALGORITHM OF QUEUE:
1. Insert Operation:
Insert operation inserting the new value from the rear side (right hand side). The first value is arranged in the queue as a left most value (in queue as first value) and second value is also inserted on rear side and set behind first value. Thus, each new value is set behind the previous entered value.
Step 1: [Check overflow condition]
if rear >= size
Output “Overflow” and return
Step 2: [Increment rear pointer]
Rear = rear + 1
Step 3: [Insert an element]
Q [rear] = value
Step 4: [Set the front pointer]
If front = 0
front = 1
Step 5: return
(here draw the box figure of inserting of node.)
2. Deletion Operation:
Deletion Operation is used to remove the values in the queue. It is works on the first-in-first-out (FIFO) basis, means, it is removed item from the front side (at the right hand side of the queue). This operation is removed first entered item after second entered item and so on in the queue.
Step 1: [Check underflow condition]
if front = 0
Output “Underflow” and return
Step 2: [Remove an element]
Value = Q [front]
Step 3: [Check for empty queue]
If front = rear
front = 0
rear = 0
else
front = front + 1
(Here draw the box figure of Deletion Operation.)
/*USE OF QUEUE IN THE ARRAY.*/
#include<stdio.h>
#define SIZE 3
int arr[SIZE];
int front = 0;
int rear = 0;
main()
{
int ans;
clrscr();
do
{
printf("1. Enter New Element.\n");
printf("2. Remove New Element.\n");
printf("3. Exit.\n");
printf("Enter Your Choice :");
scanf("%d",&ans);
switch(ans)
{
case 1:
insert();
break;
case 2:
rem();
break;
case 3:
break;
default:
printf("You Have Enter Wronge Choice...\n");
}
}while(ans!=3);
getch();
return;
}
insert()
{
int newitem;
if(rear>=SIZE)
{
printf("Your QUEUE is FULL...\n");
return;
}
else
{
printf("Enter New Value :");
scanf("%d",&newitem);
arr[++rear]=newitem;
}
if(front==0)
front=1;
getch();
return;
}
rem()
{
int remitem;
if(front>rear)
{
printf("Your QUEUE is EMPTY...\n");
front=0;
rear=0;
return;
}
else
{
remitem=arr[front++];
printf("The Removed Item Is %d.\n",remitem);
}
getch();
return;
}
/*USE OF QUEUE IN THE POINTER AND STRUCUTRE.*/
#include<stdio.h>
#define SIZE 10
struct queue
{
int item[SIZE];
}*q;
static int front = 0;
static int rear = 0;
main()
{
int ans;
do
{
clrscr();
printf("1. Enter the New Element.\n");
printf("2. Remove the Element.\n");
printf("3. Display the Queue.\n");
printf("4. Exit...\n");
printf("Enter your choice :");
scanf("%d",&ans);
switch(ans)
{
case 1:
insert(&q);
break;
case 2:
rem(&q);
break;
case 3:
display(&q);
break;
case 4:
break;
default:
printf("You have entered wronge choice....");
}
}while(ans != 4);
getch();
return;
}
insert(struct queue *temp)
{
int newitem;
if(front >= SIZE)
{
printf("QUEUE IS FULL....");
getch();
return;
}
else
{
printf("Enter a New Value :");
scanf("%d",&newitem);
temp->item[++rear] = newitem;
if(front <= 0)
front = 1;
}
getch();
return;
}
rem(struct queue *temp)
{
int remitem;
if (rear <= 0)
{
printf("THE QUEUE IS EMPTY....");
getch();
return;
}
else
{
temp->item[front++] = 0;
if(front > rear)
{
front = 0;
rear = 0;
}
}
getch();
return;}
display(struct queue *temp)
{
int fnt = 1;
if(front <= 0 || rear <=0)
{
printf("THE QUEUE IS EMPLTY....");
getch();
return;
}
else
{
while(fnt <= rear)
{
printf("%d ",temp->item[fnt]);
fnt++;
}
}
getch();
return;
}
Question : Explain CIRCULAR QUEUE with operations and examples.
Let we have an array Q that contains n elements in which Q[1] comes after Q[n] in the array. When this technique is used to construct a queue then the queue is called circular queue. In other word we can say that a queue is called circular when the last element comes just before the first element. Following figure illustrates a circular queue.
(Draw the figure)
There is types of pointer called front and rear is used to assume the front side and rear side of the circular queue. In a circular queue when rear = n, if we insert an element then this element is assigned to Q[1]. That is instead of increasing rear to n+1, we reset rear to 1. Similarly if front = n and an element of the queue is removed, we reset front to 1 instead of n + 1. Suppose queue contains only one element that is front=rear not equals to NULL and suppose that the element is removed then the front and rear pointer are now assigned NULL to indicate that the queue is empty.
OPERATIONS AND ALGORITHMS OF CIRCULAR QUEUE:
1. Insert Operation:
Step 1: [Check for the Overflow]
If front = 1 and rear = n
Output “Overflow” and return
Step 2: [Insert element in the queue.]
Else if front = 0
front = 1
rear = 1
Q [rear] = value
Step 3: [Check if the rear at the end of the queue]
Else if rear = n
rear = 1
Q [rear] = value
Step 4: [insert the element]
Else
Rear = rear + 1
Q [rear] = value
Step 5: return
2. Delete Operation:
Step 1: [Check for underflow]
If front = 0
Output “Underflow” and return
Step 2: [Remove the element]
Value = Q [front]
Step 3: [Check whether the queue is empty or not]
If front = rear
front = 0
rear = 0
Step 4: [Check the front pointer position]
Else if front = n
front = 1
Else
front = front + 1
Step 5: [Return the removed element]
Return [value]
/*USE OF CIRCULAR QUEUE USING ARRAY.*/
#include<stdio.h>
#define SIZE 3
int arr[SIZE];
int front = 0;
int rear = 0;
main()
{
int ans;
clrscr();
do
{
printf("1. Enter the New Element.\n");
printf("2. Remove the Element.\n");
printf("3. Exit...\n");
printf("Enter your choice :");
scanf("%d",&ans);
switch(ans)
{
case 1:
insert();
break;
case 2:
rem();
break;
case 3:
break;
default:
printf("You have entered wronge choice....");
}
}while(ans != 3);
getch();
return;
}
insert()
{
int newitem;
if(rear >= SIZE)
rear = 1;
else
rear++;
if(rear == front)
{
printf("Your QUEUE is FULL.\n");
rear--;
if(rear==0)
rear=SIZE;
return;
}
else
{
printf("Enter New Element :");
scanf("%d",&newitem);
arr[rear]=newitem;
if(front==0)
front=1;
}
getch();
return;
}
rem()
{
int remitem;
if(front < 1)
{
printf("Your QUEUE is EMPTY...\n");
return;
}
if(front>SIZE)
front=1;
remitem = arr[front];
printf("The Removed Item is : %d.\n",remitem);
if(front==rear)
{
front=0;
rear=0;
return;
}
else
front++;
getch();
return;
}
Question : Explain the Double Ended Queue with algorithm and example.
We know that in a stack insertion and deletion are possible only at one end (LIFO). While in a queue insertion at one end and deletion at other end. That is operations in queue is performed in (FIFO) basis. Double ended queue is a linear list in which insertions and deletions are possible at either end. Thus we can say that dqueue is more superior representations of linear list as compared to stack and simple queue. Other than the dqueue, there are other two forms of dqueue. Double ended queue is also known as dqueue. Following figure shows a dqueue.
1. Input restricted dqueue (Insertion at one end)
2. Output restricted dqueue (Deletion at one end)
(draw the figure of operation of dqueue)
ALGORITHM OF DOUBLE-ENDED QUEUE.
1. Insertion in Double-Ended Queue.
Step 1: [Check overflow condition]
If rear >= n and front = 0
Output “overflow” and return
Step 2: [Check front pointer value]
If front > 0
front = front – 1
else
return
Step 3: [Insert element at the front end]
Q [front] = value
Step 4: [Check rear pointer value]
If rear < n
rear = rear + 1
else
return
Step 5: [Insert element at the rear end]
Q [rear] = value
Step 6: return
2. Deletion in Double-Ended queue.
Step 1: [Check for underflow]
If front = 0 and rear = 0
Output “Underflow” and return
Step 2: [Delete element at front end]
If front > 0
Value = Q [front]
Return (value)
Step 3: [Check queue for empty]
If front = rear
front = rear = 0
else
front = front + 1
Step 4: [Delete element at the rear end]
If rear > 0
Value = Q [rear]
Return (value)
Step 5: [Check queue for empty]
If front = rear
front = rear = 0
else
rear = rear – 1
Step 6: return
/*USE OF DOUBLE-ENDED QUEUE USING ARRAY.*/
#include<stdio.h>
#define SIZE 3
int arr[SIZE];
int front=0;
int rear = 0;
main()
{
int ans;
clrscr();
do
{
printf("1.Enter New Element From Right :\n");
printf("2.Remove Element From Right :\n");
printf("3.Enter New Element From Left :\n");
printf("4.Remove Element From Left :\n");
printf("5.Exit :\n");
printf("Enter Your Choice :");
scanf("%d",&ans);
switch(ans)
{
case 1:
r_insert();
break;
case 2:
r_remove();
break;
case 3:
l_insert();
break;
case 4:
l_remove();
break;
case 5:
break;
default:
printf("You have entered wronge choice....");
}
}while(ans!=5);
getch();
return;
}
r_insert()
{
int newitem;
if(rear >= SIZE)
{
printf("Your QUEUE is full from RIGHT side....");
getch();
return;
}
else
{
printf("Enter the New item :");
scanf("%d",&newitem);
arr[++rear]=newitem;
}
if(front <= 0)
{
front = 1;
}
getch();
return;
}
r_remove()
{
int remitem;
if(rear <= 0)
{
rear = 0;
front = 0;
printf("Your QUEUE is EMPTY from RIGTH side...\n");
getch();
return;
}
else
{
remitem = arr[rear--];
printf("The removed item is : %d\n",remitem);
}
getch();
return;
}
l_remove()
{
int remitem;
if(front <= 0 )
{
printf("Your QUEUE is EMPTY from LEFT side...\n");
getch();
return;
}
else
{
remitem = arr[front++];
printf("The removed item is : %d\n",remitem);
}
if(front > rear)
{
front = 0;
}
getch(); return;}
l_insert()
{
int newitem;
if(front <= 1)
{
front = 0;
rear = 0;
printf("Your QUEUE is FULL from the LEFT side...\n");
getch();
return;
}
else
{
printf("Enter the New element :");
scanf("%d",&newitem);
arr[--front]=newitem;
}
getch();
return;
}
Question : Explain the Priority Queue with Example.
A queue in which it is possible to insert an element or remove and element at any position depending on some priority is called priority queue. In general way, we can say that a priority queue is a series of queues representing situations in which it is known a priori what priorities are associated with queue elements.
(here draw the figure)
Above figure illustrates how the single priority queue can be visualized as four separates queues; each follows a FIFO behavior. The elements in the second queue is removed only when the first queue is empty, elements from the third queue are removed when the first and second queues are empty and so on. When the elements are added, they are always added at the end of one of the queues as determined by priority. For example, let telephone department contains the list of telephones holders in their alphabetical order. Suppose some new users we have to add into the list at their proper place. It means we have to insert new users some where in middle, it will require more and more processing time if the list is very large. The remedies for it to divide the list into 26 sub-lists then the processing automatically will be reduced. If it is required to sort the list the radix technique for efficient processing. Following figure illustrates such type of representation.
(Draw the figure)
Question: Explain Linked List.
A linked list is defined as a collection of nodes. Each node has two parts.
1. Information
2. Pointer to next node
Information part may consists of one or more than one fields. In other words a linked list consists of series of structures, which are not necessarily contiguous. Each structure contains one or more than one contiguous information fields and a pointer to a structure containing its successor. The last node of the list contains NULL (‘\0’) in the pointer field. The pointer contains the address of the location where next information is stored.
There are following algorithms for the linked list.
1. Linked list creation algorithm
Step 1: [Initially list empty]
Start = NULL
Ste 2: [Allocate space to newly created node]
Node = Create a Node
Step 3: [Assign value to information part of a node]
Info[Node] = Data
Step 4: [Assign null to the address part for signaling end of the list]
Next[Node] = Start
Step 5: [Assign address of first node to start variable]
Start = Node
Step 6: [Return the created node]
Return [Start]
2. Algorithm to traverse nodes in a linked list
Step 1: [Initialize pointer variable current_node]
Current_node = First
Step 2: [Perform the traversing operational]
Repeat while Current_node [Not] NULL
Process Info [Current_node]
Step 3: [Move pointer to next node]
Current_node = Next [Current_node]
Step 4: Exit
3. Algorithm to insert a node at the beginning of a list
Step 1: [check for free space]
If New1 = NULL output “OVERFLOW” and Exit
Step 2: [Allocate free space]
New1 = Create new node
Step 3: [Read value of information part of a new node]
Info [New1] = Value
Step 4: [Link address part of the currently created node with the address of start]
Next [ New1] = Start
Step 5: [Now assign address of newly created node to the start]
Start = New1
Step 6: Exit
4. Algorithm to insert a node at the end of list
Step 1: [Check for free space]
If New1 = NULL output “OVERFLOW” and Exit
Step 2: [Allocate free space]
New1 = Create new node
Step 3: [Read value of information part of a new node]
Info [New1] = value
Step 4: [Move the pointer to the end of the list]
Repeat while node [Not] NULL
Node = next [Node]
Previous = next [Previous]
Step 5: [Link currently created node with the last node of the list]
Next [New1] = node
Next [previous] = New1
Step 6: Exit
5. Algorithm to insert a node in a linked list at a desired place.
Step 1: [check for availability space]
If New1 = NULL output “OVERFLOW” and Exit
Step 2: [Initialization]
Node_number = 0
Node = Start.Next [Points to first node of the list]
Previous = Address of Start [Assign address of start to previous]
Step 3: [Read information of new node number]
Insert_node = Value
Step 4: [perform insertion operation]
Repeat through Step 6 while Node <> NULL
Step 5: [Check place where new should be insert]
If Info [Nde] < Insert_node
Next [New1] = Node
Previous->Next = new1
Info [new1] = Insert_node
Return
Else [Move the pointer forward]
Node = Next [Node]
Previous = Next [Previous]
Step 6: Node_number = Node_number + 1
Step 7: Exit
6. Algorithm to delete a node in a linked list at a desired place.
Step 1:[ Initialization ]
Node = Start.next [Points to the first node in the linked list]
Previous = Address of Start
Step 2: [Initialize node counter]
Node_number = 1
Step 3: [Read information associated with a node]
Delete_node = Value
Step 4: [Check list is empty or not]
If Node = NULL
Output “OverFlow” and Exit
Step 5: [Perform deletion operation]
Repeat through 6 while Node <> NULL
If Info [Node] = Delete_node
(1) Next [Previous] = Next [Node] [Make link of previous node to the
next node]
(2) Delete (Node) [Delete current node]
(3) Exit
Step 6: Node_number = Node_number + 1
Step 7: Exit
Example :
#include<stdio.h>
#include<alloc.h>
struct list
{
int data;
struct list *next;
};
main()
{
struct list *node;
int ans;
node=NULL;
clrscr();
do
{
printf("\n\n1. Enter new element :\n");
printf("2.Display list :\n");
printf("3.exit:\n");
printf("4.Enter new node at bagin:\n");
printf("5.Enter new node at requird position:\n");
printf("6.Delete the node:\n");
printf("Enter your Choice:");
scanf("%d",&ans);
switch(ans)
{
case 1:create(&node);
break;
case 2:display(node);
break;
case 3:addatpos(&node);
break;
case 4:addatbag(&node);
break;
case 6:delnode(&node);
break;
default:
printf("you have enter wrong choice..\n");
}
}while(ans!=30);
getch();
return;
}
create(struct list **q)
{
struct list *temp;
int a;
temp= *q;
if(*q==NULL)
{
*q=(struct list*)malloc(sizeof(struct list));
temp=*q;
}
else
{
while(temp->next!=NULL)
temp=temp->next;
temp->next=(struct list*)malloc(sizeof(struct list));
temp=temp->next;
}
printf("Enter the value:");
scanf("%d",&a);
temp->data=a;
temp->next=NULL;
return;
}
display(struct list*q)
{
while(q!=NULL)
{ printf("%d",q->data);
q=q->next;
}
return;
}
addatbag(struct list **q)
{
struct list* temp;
int a;
temp=malloc(sizeof(struct list));
printf("Enter the value:");
scanf("%d",&a);
temp->data=a;
temp->next=*q;
*q=temp;
return;
}
addatpos(struct list *q)
{
int pos,a,flag=0;
struct list *temp;
printf("Enter the position:");
scanf("%d",&pos);
while(q!=NULL)
{
if(q->data==pos)
{
flag=1;
break;
}
q=q->next;
}
if(flag==0)
{
printf("Position is not proper;");
return;
}
printf("Enter the choice:");
scanf("%d",&a);
temp=malloc(sizeof(struct list));
temp->data=a;
temp->next=q->next;
q->next=temp;
return;
}
delnode(struct list **q)
{
struct list *temp,*old;
int pos;
temp=*q;
printf("enter the position for delete:");
scanf("%d",&pos);
while(temp!=NULL)
{
if(temp->data==pos)
{
if(temp==*q)
{
*q=temp->next;
free(temp);
return;
}
else
{
old->next=temp->next;
free(temp);
return;
}
}
else
{
old=temp;
temp=temp->next;
}
}
return;
}
Example of Sorted Linked List.
#include<stdio.h>
#include<malloc.h>
struct link
{
int data;
struct link *next;
};
int i;
int number;
struct link *start, *node, *previous, *new1, *counter;
void doubly_link_sort()
{
printf("\n Input the number of node we need to create:");
scanf("%d",&number);
start->next = NULL;
node = start;
for(i=0;i<number;i++)
{
node->next = (struct link*)malloc(sizeof(struct link));
node = node->next;
printf("\n Input the first node: %d; ", i+1);
scanf("%d", &node->data);
node->next = NULL;
}
for(new1 = start; new1->next != NULL; new1 = new1->next)
{
for(counter = new1->next; counter !=NULL; counter = counter->next)
{
if(new1->data > counter->data)
{
int temp = new1->data;
new1->data = counter->data;
counter->data = temp;
}
}
}
node = start->next;
printf("\n After sorting the list is as follows:\n");
while(node)
{
printf("%d", node->data);
node = node->next;
}
}
void main()
{
doubly_link_sort();
}
Question: Explain The Doubly Linked list.
Doubly linked list creation algorithm
Step 1 : [Initilization] 1) Start. Next = null
2) Previous. Next = null
Step 2 : [Assign address of start variable to node]
Node = address of start
Step 3 : [Make left and right links of a node]
1) Next [node] = node [make link to node]
2) Previous [node] = node [make link to node]
3) Node = Next [node] [Move pointer to next node]
4) Info [node] = value [Information value of a node]
5) Next [node] = NULL [Assign NULL to the address field]
Step 4 : [ Call Step 3]
Repeat Step 3 to create required number of nodes for linked list
Step 5 : End .
Algorithm for traversing a doubly inked list Step 1 : [initialization]
Node = start. Next [points to the first node in the list]
Step 2 : [Traverse the list in forward direction]
Repeat while Next [node] # NULL process Info [Node]
Step 3 : [Traverse the list in backward direction]
Repeat while Node # NULL Process Info [Node]
Step 4 : Exit.
Algorithm to insert a node at right of the right most node Step 1 : [Initialization]
Node =Start
Step 2 : [Create a new node] New = Create a Node
Step 3 : [Read information associated with newly created node]
Info [Newly] = value
Step 4 : [Perform the insertion]
I) Next [new] = node
II) Previous [New] = Previous [node]
III) Next [Previous[node]] = New
IV) Next [Node] = New
Step 5 : Exit
Algorithm to delete right most node Step 1 : [Initialization]
Node = Start
Step 2 : [Initialization counter]
Counter = 0
Step 3 : [check the list]
If Node = Null
Output “underflow” and exit
Step 4 : [count the number of nodes available in the list]
Repeat while Node # NULL
I) Node = Next [Node]
II) Counter = Counter + 1
Step 5 : [perform deletion]
Node = Start
Repeat through (II) while counter # 1
I) Node = Next [Node]
II) Counter = Counter – 1
III) Next [previous[node]] = Next [Node]
IV) Previous [Next [node]] = previous [node]
V) Delete (node)
Step 6 : Exit.
Algorithm to delete a desired node Step 1 : [Initialization]
Node = Start
Step 2 : [Check the list]
If node = NULL
Output “underflow” and Exit
Step 3 : [Set the counter ]
Search = 0
Step 4 : [Input the node number to which you want to delete]
Node delete = value
Step 5 : [Perform deletion]
Repeat while Node # NULL
If Search = Delete _Node
Next [Previous [Node]] = Next [Node]
Previous [Next[Node]] = Previous [Node]
Delete (Node)
Else
Node = Next [node]
Search = Search + 1
Step 6 : Exit
Example:
#include<stdio.h>
#include<malloc.h>
struct dnode
{
struct dnode *prv;
int data;
struct dnode *next;
};
main()
{
struct dnode *p;
int ans;
p=NULL;
clrscr();
do
{
printf("\n1:enter new node:\n");
printf("2:enter new node at begining:\n");
printf("3:enter new node at position:\n");
printf("4:display value:\n");
printf("5:delete node:\n");
printf("6:exit\n");
printf("enter your choice :");
scanf("%d",&ans);
switch(ans)
{
case 1:
append(&p);
break;
case 2:
addatbeg(&p);
break;
case 3:
addatpos(&p);
break;
case 4:
display(p);
break;
case 5:
deletatpos(&p);
break;
case 6:
exit(0);
break;
}
}while(ans!=6);
getch();
return;
}
append(struct dnode **q)
{
struct dnode *temp,*r;
int n;
temp=(*q);
if(*q==NULL)
{
*q=(struct dnode*)malloc(sizeof(struct dnode*));
(*q)->prv=NULL;
(*q)->next=NULL;
temp=(*q);
}
else
{
while(temp->next!=NULL)
temp=temp->next;
r=(struct dnode*)malloc(sizeof(struct dnode));
temp->next=r;
r->prv=temp;
r->next=NULL;
temp=temp->next;
}
printf("Enter value:");
scanf("%d",&n);
temp->data=n;
return;
}
addatbeg(struct dnode **q)
{
struct dnode *temp;
int n;
temp=(struct dnode*)malloc(sizeof(struct dnode));
temp->prv=NULL;
temp->next=*q;
(*q)->prv=temp;
printf("Enter value:\n");
scanf("%d",&n);
temp->data=n;
(*q) = (*q)->prv;
return;
}
addatpos(struct dnode **q)
{
struct dnode *temp;
int pos,n,flag=0;
printf("Enter position:\n");
scanf("%d",&pos);
while((*q)->next!=NULL)
{
if((*q)->data==pos)
{
flag=1;
break;
}
else
{
flag=0;
}
(*q)=(*q)->next;
}
if(flag==1)
{
printf("enter value :");
scanf("%d",&n);
temp=(struct dnode*)malloc(sizeof(struct dnode));
temp->prv=(*q)->prv->next;
(*q)->prv->next=temp;
temp->next=*q;
(*q)->prv=temp;
temp->data=n;
}
else
{
printf("element is not available:\n");
}
return;
}
deletatpos(struct dnode **q)
{
struct dnode *temp;
int n;
printf("Enter the position:\n");
scanf("%d",&n);
temp=*q;
while(temp->next!=NULL)
{
if(temp->data==n)
{
if(temp==*q)
{
(*q)=(*q)->next;
(*q)->prv=NULL;
}
else
{
if(temp->next==NULL)
temp->prv->next=NULL;
else
{
temp->prv->next=temp->next;
temp->next->prv=temp->prv;
free(temp);
}
}
}temp=temp->next;
}
return;
}
display(struct dnode *q)
{
while(q!=NULL)
{
printf("%d ",q->data);
q=q->next;
}
return;}
Question : Example of Circular Linked List.
#include<stdio.h>
#include<malloc.h>
struct node
{
int data;
struct node *next;
};
main()
{
struct node *front,*rear;
int ans;
front = rear = NULL;
do
{
printf("\n 1.insert node:\n");
printf("\n 2.delet node:\n");
printf("\n 3.display:\n");
printf("\n 4.exit\n");
printf("enter choice\n");
scanf("%d",&ans);
switch(ans)
{
case 1:
add(&front,&rear);
break;
case 2:
delet(&front,&rear);
break;
case 3:
display(front);
break;
case 4:
break;
}
}while(ans!=4);
return;
}
add(struct node **f,struct node **r)
{
struct node *q;
int a;
q=(struct node*)malloc(sizeof(struct node));
printf("\n enter the value:");
scanf("%d",&a);
q->data=a;
if(*f==NULL)
*f=q;
else
(*r)->next=q;
*r=q;
(*r)->next=*f;
return;
}
delet(struct node **f,struct node **r)
{
struct node *q;
int a;
if(*f==NULL)
printf("\n list empty");
else
{
if(*f==*r)
{
a=(*f)->data;
free(*f);
*f=NULL;
*r=NULL;
}
else
{
q=*f;
a=q->data;
(*f)=(*f)->next;
(*r)->next=*f;
free(q);
}
printf("\n deleted node %d",a);
return;
}
return;
}
display(struct node *f)
{
struct node *q=f,*p=NULL;
while(q!=p)
{
printf("%2d\t",q->data);
q=q->next;
p=f;
}
return;
}
Question: Explain the Binary Tree with Example.
A binary tree is an important type of data structure, which is very useful. A tree is a binary tree if each node of it can have at the most two branches. In other words we can say that if every node of a tree can have at most degree two, then this is called a binary tree. In a binary tree left and right sub-trees distinguish sub-trees of a node.
A binary tree T is a finite set of nodes, which is either empty or consists of special node called root R and two disjoint binary trees T1 and T2 (which are called the left sub-tree and right sub-trees, respectively). If T1 is non-empty then the root of T1 is called the left successor of R. If T2 is non-empty then the root of T2 is known as right successor of R.
Recursive algorithm for binary tree creation :
Create_Tree (Info, Node)
Where Info à Information for which we have to create node.
Node à structure type variable to points both left and right child.
Step 1: [Check whether the tree is empty]
If Node = NULL
Node = Create a node
Left_Child [Node] = NULL
Right_Child [Node]] = NULL
Step 2: [Test for the left child]
If Info [node] >= Info
Left_child [Node] = call Create_Tree
(Info, Left_child [Node])
Else
Right_child [Node] = call Create_Tree
(info, Right_child [Node])
Step 3: Return (Node)
Recursive algorithm of preorder traversing:
Preorder (Node)
Step 1: [Do through step 3]
If Node is not equal to NULL
Output Info [Node]
Step 2: Call Preorder (Left_child [Node])
Step 3: Call Preorder (Right_child Node])
Step 4: Exit
Recursive algorithm of inorder traversing: Inorder (Node)
Step 1: [Do through Step 4]
If Node is not equal to NULL
Step 2: Call Inorder (Left_Child [Node])
Step 3: Output Info [Node]
Step 4: Call Inorder (Right_child [Node])
Step 5: Exit
Recursive algorithm of postorder traversing:
Postorder (Node)
Step 1: [Do through step 4]
If Node is not equal to NULL
Step 2: Call Postorder (Left_Child [Node])
Step 3: Call Postorder (Right_Child Node)
Step 4: Output Info [Node]
Step 5: Exit
Example :
/*program for tree operation*/
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct tree
{
int no;
struct tree *r,*l;
};
void insert(struct tree *root,int x);
void preorder(struct tree *root);
void inorder(struct tree *root);
void postorder(struct tree *root);
void main()
{
struct tree *root = NULL;
int ch=1,x,level,info;
root=(struct tree *)malloc(sizeof(struct tree));
clrscr();
printf("\n enter the value of root:=");
scanf("%d",&root->no);
root->l = root->r=NULL;
while(ch!=0)
{
printf("\n 1:inert\t 2:preorder\t 3:inorder\t 4:postorder");
printf("\t 0:exit");
printf("\n\n enter the choice:=");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\n enter the no");
scanf("%d",&x);
insert(root,x);
break;
case 2:
preorder(root);
break;
case 3:
inorder(root);
break;
case 4:
postorder(root);
break;
}
}
}//main over
void insert(struct tree *root,int x)
{
if(x==root->no)
{
printf("\n duplicate no \n\n\n");
return;
}
if(x < root->no)
{
if(root->l!=NULL)
insert(root->l,x);
else
{
root->l=(struct tree*)malloc(sizeof(struct tree));
root->l->no=x;
root->l->l=root->l->r=NULL;
}
}
else
{
if(root->r!=NULL)
insert(root->r,x);
else
{
root->r=(struct tree*)malloc(sizeof(struct tree));
root->r->no=x;
root->r->r=root->r->l=NULL;
}
}
}//insert over
void inorder(struct tree *root)
{
if(root!=NULL)
{
inorder(root->l);
printf("\n %d",root->no);
inorder(root->r);
}
}//inorder over
void preorder(struct tree *root)
{
if(root !=NULL)
{
printf("\n %d",root->no);
preorder(root->l);
preorder(root->r);
}
}//preorder over
void postorder(struct tree *root)
{
if(root!=NULL)
{
postorder(root->l);
postorder(root->r);
printf("\n %d",root->no);
}
}//postorder over
Question: Explain the Bubble sort with algorithm and example.
Bubble_sort (n, list)
Where
N à Represents the number of elements in the list
L à Represents the list of elements
Step 1: [Initialize]
i = 0
Step 2: Repeat through step 5 while ( i < n )
Step 3 : j = 0;
Step 4: Repeat through step 5 while ( j < n-i)
Step 5: if (list[ j] < list [ j+1]
(i) temp = list[ j]
(ii) list[ j+1] = list[ j]
(iii) list[j] = temp
step 6: Exit
Example :
#include<stdio.h>
#include<stdio.h>
void bubble_sort (int array[], int size)
{
int temp, i, j;
for(i = 0; i < size; i++)
for( j=0;j < size-i-1;j++)
if (array[j] < array[ j+1] )
{
temp = array[j];
array[ j] = array[ j+1];
array[ j+1] = temp;
}
}
void main(void)
{
int values[30], i;
printf(“\n Unsorted list is as follows\n”);
for (i = 0; i < 10; i++)
{
values[i] = rand( ) %100;
printf(“%d”, values[i]);
}
bubble_sort (values , 10);
printf(“\n Sorted list is as follows\n”);
for(i = 0; i < 10;i++)
printf(“%d”,values[i]);
}
Question: Explain the Insertion sort with algorithm and example.
Insertion_sort (l,n)
Where l à Represents the list of elements.
N à Represents number of elementsin the list.
Step 1: [Initialize]
1[0] = -0
Step 2: Repeat through Step 3 to 5 for i=1,2,3,4..n
Step 3: (i) temp = l[i]
(ii) pointer = i – 1
Step 4: while(temp < l[pointer])
(i) l[pointer + 1] = l[pointer]
(ii) pointer = pointer – 1
Step 5: l[pointer] = temp
Step 6: Exit
Example:
#Include<stdio.h>
#include<stdlib.h>
int i, k;
void insertion_sort (int *, int);
void display(int *,int)
void insertion_sort(int l[], int n)
{
int pointer, temp;
l[0] = -0;
for(i = 1 ; i <= n ; i++)
{
pointer = i –1;
temp = l[i];
while(temp <l[ponter])
{
l[pointer+1] = l[pointer];
pointer -;
}
l[pointer+1] = temp;
printf(“Step = %d”,i);
for(k = 0; k <= n; k++)
printf(“%d”, l[k]);
printf(“\n”);
}
}
void display(int l[], int n)
{
printf(“\n Sorted list is as follows\n”);
for(i = 1;i <= n; i++)
printf(“%d”,l[i]);
}
void main()
{
int nember = 20;
int list[100];
int i;
printf(“\n Number of elements in the list : %i” , number);
printf(“\n Unsorted list is as follows \n”);
for(i = 1;i <= number; i++)
{
list[i] = rand() %100;
printf(“%d”,list[i]);
}
printf(“\n”);
printf(“\n Stepwise result is as follows \n\n”);
insertion_sort(list, number);
display(list, number);
}
Question: Explain the Quick sort with algorithm and example.
Q_SORT (Array, first, last)
Where array à Represents the list of elements;
First à Represents the position of the first elements in the list (Only at the starting point, it’s value changes during the excution of the function).
Last à Represents the position of the last elements in the list(Only at starting point the value of it’s changes during the execution of the function).
Step 1: [initially]
Low = first
High = last
Pivot = array[(low+high)/2] [middle elements of the elements of the list]
Step 2: Repeat through Step 7 while (low <= high)
Step 3: Repeat Step 4 while (array[low] < pivot)
Step 4: low = low +1
Step 5: Repeat Step 6 while (array[high] > pivot)
Step 6:high = high – 1
Step 7: if ( low<= high)
(i) temp = array[low]
(ii) array[low] = array[high]
(iii) array[high] = temp
(iv) low = low + 1
(v) high = high – 1
Step 8: if ( first < high ) Q_sort(array, first, high)
Step 9: if ( low < lase ) Q_sort(array, low, lase)
Step 10: exit
Example:
#include<stdio.h>
#include<stdlib.h>
void quick_sort(int array[], int first, int last)
{
int temp, low, high, pivot;
low = first;
high = last;
pivot = array[(first + lase) / 2];
do{
while (array[low] < pivot)
low++;
while (array[high] > pivot)
high-;
if(low <= high)
{
temp = array[low];
array[low++] = array[high];
array[high-] = temp;
}
}wihle(low <=high);
if(first < high)
quick_sort(arry, first, high);
if (low < last)
quick_sort(arry, low, last);
}
void main()
{
int values[100], i;
printf(“\n Unsorted list is as follows \n”);
for (i = 0; i < 20; i++)
{
values[i] = rand() % 100;
peintf(“%d”, values[i]);
}
quick_sort(values, 0, 19);
printf(“\n Sorted list as follows \n);
for(i = 0; i < 20; i++)
printf(“%d”, values[i]);
}
Question: Explain the Selection sort with algorithm and example.
Selection_sort (array, size)
Where array à Represents the list of elements
Size à Represents size of the list
Step 1: current = 0 [initially]
Step 2: Repeat through Step 7 while (current < size)
Step 3: j = current + 1;
Step 4: Repeat through Step 6 while (j < size)
Step 5: if (array [current] > array [j])
(i) temp = array[current]
(ii) arra[current] = array[j]
(iii) array[j] =temp
step 6: j = j + 1
Step 7: current = current + 1
Step 8: Exit
Example:
#include<stdio.h>
#include<stdlib.h>
void selection_sort[int array[], int size)
{
int temp, current, j;
for(current = 0; current < size; current++)
for(j = current +1; j < size; j++)
if(array[current] > array[j])
{
temp = array[current];
array[current] = array[j];
array[j] = temp;
}
}
void main()
{
int values[30], i;
printf(“\n Unsorted list is as follows\n”)
for(i = 0; i < 30; i++)
{
values[i] = rand() % 100;
printf(“%d”, values[i]);
}
selection_sort(values, 30 );
printf(“\n sorted list is as follows\n”);
for ( i = 0; i < 30; i++)
printf(“%d”, values[i]);
}
Question: Explain the Shell sort with algorithm and example.
Shell_sort(array, size)
Where array à Represents the list of elements
Size à Represents the size of the list
Step 1: [Initialize]
Gap = size / 2
Stpe 2: Repeat through Step 6 while(gap = gap / 2)
Step 3: swap = 0
Step 4: Repeat through Step 6 for i=0, 1, 2, 3…i <(size – gap)
Step 6:if (array[i] > array[i+gap]
(i) temp = array [i]
(ii) array[i] = array[i + gap]
(iii) array[i + gap]= temp
(iv) swap = 1
[ End of for loop]
[ End of inner while loop]
[ End of outer while loop]
Step 7: output arrayelements (sorted)
Step 8: Exit
Example:
#include<stdio.h>
#include<stdlib.h>
void shell_sort(int array[], int size)
{
int temp, gap, i, swap;
gap = size / 2;
do {
do {
swap = 0;
for (i = 0; i < size – gap; i++)
if(array[i] > array[i + gap])
{
temp = array[i];
array[i] = array[i + gap];
array[i + gap] = temp;
swap = 1;
}
}while (swap);
}while (gap = gap / 2);
}
void main(void)
{
int values[50], i;
print(“\n Unsorted list is as follows \n”);
for(i = 0; i < 50; i++)
{
values[i] = rand() % 100;
printf(“%d”, values[i]);
}
shell_sort(values, 50);
printf(“\n Sorted list is as follow \n”);
for(i = 0; i < 50; i++)
printf(“%d”, value[i]);
}
#include<stdio.h>
#define SIZE 10
struct queue
{
int item[SIZE];
}*q;
static int front = 0;
static int rear = 0;
main()
{
int ans;
do
{
clrscr();
printf("1. Enter the New Element.\n");
printf("2. Remove the Element.\n");
printf("3. Display the Queue.\n");
printf("4. Exit...\n");
printf("Enter your choice :");
scanf("%d",&ans);
switch(ans)
{
case 1:
insert(&q);
break;
case 2:
rem(&q);
break;
case 3:
display(&q);
break;
case 4:
break;
default:
printf("You have entered wronge choice....");
}
}while(ans != 4);
getch();
return;
}
insert(struct queue *temp)
{
int newitem;
if(front >= SIZE)
{
printf("QUEUE IS FULL....");
getch();
return;
}
else
{
printf("Enter a New Value :");
scanf("%d",&newitem);
temp->item[++rear] = newitem;
if(front <= 0)
front = 1;
}
getch();
return;
}
rem(struct queue *temp)
{
int remitem;
if (rear <= 0)
{
printf("THE QUEUE IS EMPTY....");
getch();
return;
}
else
{
temp->item[front++] = 0;
if(front > rear)
{
front = 0;
rear = 0;
}
}
getch();
return;}
display(struct queue *temp)
{
int fnt = 1;
if(front <= 0 || rear <=0)
{
printf("THE QUEUE IS EMPLTY....");
getch();
return;
}
else
{
while(fnt <= rear)
{
printf("%d ",temp->item[fnt]);
fnt++;
}
}
getch();
return;
}
Question : Explain CIRCULAR QUEUE with operations and examples.
Let we have an array Q that contains n elements in which Q[1] comes after Q[n] in the array. When this technique is used to construct a queue then the queue is called circular queue. In other word we can say that a queue is called circular when the last element comes just before the first element. Following figure illustrates a circular queue.
(Draw the figure)
There is types of pointer called front and rear is used to assume the front side and rear side of the circular queue. In a circular queue when rear = n, if we insert an element then this element is assigned to Q[1]. That is instead of increasing rear to n+1, we reset rear to 1. Similarly if front = n and an element of the queue is removed, we reset front to 1 instead of n + 1. Suppose queue contains only one element that is front=rear not equals to NULL and suppose that the element is removed then the front and rear pointer are now assigned NULL to indicate that the queue is empty.
OPERATIONS AND ALGORITHMS OF CIRCULAR QUEUE:
1. Insert Operation:
Step 1: [Check for the Overflow]
If front = 1 and rear = n
Output “Overflow” and return
Step 2: [Insert element in the queue.]
Else if front = 0
front = 1
rear = 1
Q [rear] = value
Step 3: [Check if the rear at the end of the queue]
Else if rear = n
rear = 1
Q [rear] = value
Step 4: [insert the element]
Else
Rear = rear + 1
Q [rear] = value
Step 5: return
2. Delete Operation:
Step 1: [Check for underflow]
If front = 0
Output “Underflow” and return
Step 2: [Remove the element]
Value = Q [front]
Step 3: [Check whether the queue is empty or not]
If front = rear
front = 0
rear = 0
Step 4: [Check the front pointer position]
Else if front = n
front = 1
Else
front = front + 1
Step 5: [Return the removed element]
Return [value]
/*USE OF CIRCULAR QUEUE USING ARRAY.*/
#include<stdio.h>
#define SIZE 3
int arr[SIZE];
int front = 0;
int rear = 0;
main()
{
int ans;
clrscr();
do
{
printf("1. Enter the New Element.\n");
printf("2. Remove the Element.\n");
printf("3. Exit...\n");
printf("Enter your choice :");
scanf("%d",&ans);
switch(ans)
{
case 1:
insert();
break;
case 2:
rem();
break;
case 3:
break;
default:
printf("You have entered wronge choice....");
}
}while(ans != 3);
getch();
return;
}
insert()
{
int newitem;
if(rear >= SIZE)
rear = 1;
else
rear++;
if(rear == front)
{
printf("Your QUEUE is FULL.\n");
rear--;
if(rear==0)
rear=SIZE;
return;
}
else
{
printf("Enter New Element :");
scanf("%d",&newitem);
arr[rear]=newitem;
if(front==0)
front=1;
}
getch();
return;
}
rem()
{
int remitem;
if(front < 1)
{
printf("Your QUEUE is EMPTY...\n");
return;
}
if(front>SIZE)
front=1;
remitem = arr[front];
printf("The Removed Item is : %d.\n",remitem);
if(front==rear)
{
front=0;
rear=0;
return;
}
else
front++;
getch();
return;
}
Question : Explain the Double Ended Queue with algorithm and example.
We know that in a stack insertion and deletion are possible only at one end (LIFO). While in a queue insertion at one end and deletion at other end. That is operations in queue is performed in (FIFO) basis. Double ended queue is a linear list in which insertions and deletions are possible at either end. Thus we can say that dqueue is more superior representations of linear list as compared to stack and simple queue. Other than the dqueue, there are other two forms of dqueue. Double ended queue is also known as dqueue. Following figure shows a dqueue.
1. Input restricted dqueue (Insertion at one end)
2. Output restricted dqueue (Deletion at one end)
(draw the figure of operation of dqueue)
ALGORITHM OF DOUBLE-ENDED QUEUE.
1. Insertion in Double-Ended Queue.
Step 1: [Check overflow condition]
If rear >= n and front = 0
Output “overflow” and return
Step 2: [Check front pointer value]
If front > 0
front = front – 1
else
return
Step 3: [Insert element at the front end]
Q [front] = value
Step 4: [Check rear pointer value]
If rear < n
rear = rear + 1
else
return
Step 5: [Insert element at the rear end]
Q [rear] = value
Step 6: return
2. Deletion in Double-Ended queue.
Step 1: [Check for underflow]
If front = 0 and rear = 0
Output “Underflow” and return
Step 2: [Delete element at front end]
If front > 0
Value = Q [front]
Return (value)
Step 3: [Check queue for empty]
If front = rear
front = rear = 0
else
front = front + 1
Step 4: [Delete element at the rear end]
If rear > 0
Value = Q [rear]
Return (value)
Step 5: [Check queue for empty]
If front = rear
front = rear = 0
else
rear = rear – 1
Step 6: return
/*USE OF DOUBLE-ENDED QUEUE USING ARRAY.*/
#include<stdio.h>
#define SIZE 3
int arr[SIZE];
int front=0;
int rear = 0;
main()
{
int ans;
clrscr();
do
{
printf("1.Enter New Element From Right :\n");
printf("2.Remove Element From Right :\n");
printf("3.Enter New Element From Left :\n");
printf("4.Remove Element From Left :\n");
printf("5.Exit :\n");
printf("Enter Your Choice :");
scanf("%d",&ans);
switch(ans)
{
case 1:
r_insert();
break;
case 2:
r_remove();
break;
case 3:
l_insert();
break;
case 4:
l_remove();
break;
case 5:
break;
default:
printf("You have entered wronge choice....");
}
}while(ans!=5);
getch();
return;
}
r_insert()
{
int newitem;
if(rear >= SIZE)
{
printf("Your QUEUE is full from RIGHT side....");
getch();
return;
}
else
{
printf("Enter the New item :");
scanf("%d",&newitem);
arr[++rear]=newitem;
}
if(front <= 0)
{
front = 1;
}
getch();
return;
}
r_remove()
{
int remitem;
if(rear <= 0)
{
rear = 0;
front = 0;
printf("Your QUEUE is EMPTY from RIGTH side...\n");
getch();
return;
}
else
{
remitem = arr[rear--];
printf("The removed item is : %d\n",remitem);
}
getch();
return;
}
l_remove()
{
int remitem;
if(front <= 0 )
{
printf("Your QUEUE is EMPTY from LEFT side...\n");
getch();
return;
}
else
{
remitem = arr[front++];
printf("The removed item is : %d\n",remitem);
}
if(front > rear)
{
front = 0;
}
getch(); return;}
l_insert()
{
int newitem;
if(front <= 1)
{
front = 0;
rear = 0;
printf("Your QUEUE is FULL from the LEFT side...\n");
getch();
return;
}
else
{
printf("Enter the New element :");
scanf("%d",&newitem);
arr[--front]=newitem;
}
getch();
return;
}
Question : Explain the Priority Queue with Example.
A queue in which it is possible to insert an element or remove and element at any position depending on some priority is called priority queue. In general way, we can say that a priority queue is a series of queues representing situations in which it is known a priori what priorities are associated with queue elements.
(here draw the figure)
Above figure illustrates how the single priority queue can be visualized as four separates queues; each follows a FIFO behavior. The elements in the second queue is removed only when the first queue is empty, elements from the third queue are removed when the first and second queues are empty and so on. When the elements are added, they are always added at the end of one of the queues as determined by priority. For example, let telephone department contains the list of telephones holders in their alphabetical order. Suppose some new users we have to add into the list at their proper place. It means we have to insert new users some where in middle, it will require more and more processing time if the list is very large. The remedies for it to divide the list into 26 sub-lists then the processing automatically will be reduced. If it is required to sort the list the radix technique for efficient processing. Following figure illustrates such type of representation.
(Draw the figure)
Question: Explain Linked List.
A linked list is defined as a collection of nodes. Each node has two parts.
1. Information
2. Pointer to next node
Information part may consists of one or more than one fields. In other words a linked list consists of series of structures, which are not necessarily contiguous. Each structure contains one or more than one contiguous information fields and a pointer to a structure containing its successor. The last node of the list contains NULL (‘\0’) in the pointer field. The pointer contains the address of the location where next information is stored.
There are following algorithms for the linked list.
1. Linked list creation algorithm
Step 1: [Initially list empty]
Start = NULL
Ste 2: [Allocate space to newly created node]
Node = Create a Node
Step 3: [Assign value to information part of a node]
Info[Node] = Data
Step 4: [Assign null to the address part for signaling end of the list]
Next[Node] = Start
Step 5: [Assign address of first node to start variable]
Start = Node
Step 6: [Return the created node]
Return [Start]
2. Algorithm to traverse nodes in a linked list
Step 1: [Initialize pointer variable current_node]
Current_node = First
Step 2: [Perform the traversing operational]
Repeat while Current_node [Not] NULL
Process Info [Current_node]
Step 3: [Move pointer to next node]
Current_node = Next [Current_node]
Step 4: Exit
3. Algorithm to insert a node at the beginning of a list
Step 1: [check for free space]
If New1 = NULL output “OVERFLOW” and Exit
Step 2: [Allocate free space]
New1 = Create new node
Step 3: [Read value of information part of a new node]
Info [New1] = Value
Step 4: [Link address part of the currently created node with the address of start]
Next [ New1] = Start
Step 5: [Now assign address of newly created node to the start]
Start = New1
Step 6: Exit
4. Algorithm to insert a node at the end of list
Step 1: [Check for free space]
If New1 = NULL output “OVERFLOW” and Exit
Step 2: [Allocate free space]
New1 = Create new node
Step 3: [Read value of information part of a new node]
Info [New1] = value
Step 4: [Move the pointer to the end of the list]
Repeat while node [Not] NULL
Node = next [Node]
Previous = next [Previous]
Step 5: [Link currently created node with the last node of the list]
Next [New1] = node
Next [previous] = New1
Step 6: Exit
5. Algorithm to insert a node in a linked list at a desired place.
Step 1: [check for availability space]
If New1 = NULL output “OVERFLOW” and Exit
Step 2: [Initialization]
Node_number = 0
Node = Start.Next [Points to first node of the list]
Previous = Address of Start [Assign address of start to previous]
Step 3: [Read information of new node number]
Insert_node = Value
Step 4: [perform insertion operation]
Repeat through Step 6 while Node <> NULL
Step 5: [Check place where new should be insert]
If Info [Nde] < Insert_node
Next [New1] = Node
Previous->Next = new1
Info [new1] = Insert_node
Return
Else [Move the pointer forward]
Node = Next [Node]
Previous = Next [Previous]
Step 6: Node_number = Node_number + 1
Step 7: Exit
6. Algorithm to delete a node in a linked list at a desired place.
Step 1:[ Initialization ]
Node = Start.next [Points to the first node in the linked list]
Previous = Address of Start
Step 2: [Initialize node counter]
Node_number = 1
Step 3: [Read information associated with a node]
Delete_node = Value
Step 4: [Check list is empty or not]
If Node = NULL
Output “OverFlow” and Exit
Step 5: [Perform deletion operation]
Repeat through 6 while Node <> NULL
If Info [Node] = Delete_node
(1) Next [Previous] = Next [Node] [Make link of previous node to the
next node]
(2) Delete (Node) [Delete current node]
(3) Exit
Step 6: Node_number = Node_number + 1
Step 7: Exit
Example :
#include<stdio.h>
#include<alloc.h>
struct list
{
int data;
struct list *next;
};
main()
{
struct list *node;
int ans;
node=NULL;
clrscr();
do
{
printf("\n\n1. Enter new element :\n");
printf("2.Display list :\n");
printf("3.exit:\n");
printf("4.Enter new node at bagin:\n");
printf("5.Enter new node at requird position:\n");
printf("6.Delete the node:\n");
printf("Enter your Choice:");
scanf("%d",&ans);
switch(ans)
{
case 1:create(&node);
break;
case 2:display(node);
break;
case 3:addatpos(&node);
break;
case 4:addatbag(&node);
break;
case 6:delnode(&node);
break;
default:
printf("you have enter wrong choice..\n");
}
}while(ans!=30);
getch();
return;
}
create(struct list **q)
{
struct list *temp;
int a;
temp= *q;
if(*q==NULL)
{
*q=(struct list*)malloc(sizeof(struct list));
temp=*q;
}
else
{
while(temp->next!=NULL)
temp=temp->next;
temp->next=(struct list*)malloc(sizeof(struct list));
temp=temp->next;
}
printf("Enter the value:");
scanf("%d",&a);
temp->data=a;
temp->next=NULL;
return;
}
display(struct list*q)
{
while(q!=NULL)
{ printf("%d",q->data);
q=q->next;
}
return;
}
addatbag(struct list **q)
{
struct list* temp;
int a;
temp=malloc(sizeof(struct list));
printf("Enter the value:");
scanf("%d",&a);
temp->data=a;
temp->next=*q;
*q=temp;
return;
}
addatpos(struct list *q)
{
int pos,a,flag=0;
struct list *temp;
printf("Enter the position:");
scanf("%d",&pos);
while(q!=NULL)
{
if(q->data==pos)
{
flag=1;
break;
}
q=q->next;
}
if(flag==0)
{
printf("Position is not proper;");
return;
}
printf("Enter the choice:");
scanf("%d",&a);
temp=malloc(sizeof(struct list));
temp->data=a;
temp->next=q->next;
q->next=temp;
return;
}
delnode(struct list **q)
{
struct list *temp,*old;
int pos;
temp=*q;
printf("enter the position for delete:");
scanf("%d",&pos);
while(temp!=NULL)
{
if(temp->data==pos)
{
if(temp==*q)
{
*q=temp->next;
free(temp);
return;
}
else
{
old->next=temp->next;
free(temp);
return;
}
}
else
{
old=temp;
temp=temp->next;
}
}
return;
}
Example of Sorted Linked List.
#include<stdio.h>
#include<malloc.h>
struct link
{
int data;
struct link *next;
};
int i;
int number;
struct link *start, *node, *previous, *new1, *counter;
void doubly_link_sort()
{
printf("\n Input the number of node we need to create:");
scanf("%d",&number);
start->next = NULL;
node = start;
for(i=0;i<number;i++)
{
node->next = (struct link*)malloc(sizeof(struct link));
node = node->next;
printf("\n Input the first node: %d; ", i+1);
scanf("%d", &node->data);
node->next = NULL;
}
for(new1 = start; new1->next != NULL; new1 = new1->next)
{
for(counter = new1->next; counter !=NULL; counter = counter->next)
{
if(new1->data > counter->data)
{
int temp = new1->data;
new1->data = counter->data;
counter->data = temp;
}
}
}
node = start->next;
printf("\n After sorting the list is as follows:\n");
while(node)
{
printf("%d", node->data);
node = node->next;
}
}
void main()
{
doubly_link_sort();
}
Question: Explain The Doubly Linked list.
Doubly linked list creation algorithm
Step 1 : [Initilization] 1) Start. Next = null
2) Previous. Next = null
Step 2 : [Assign address of start variable to node]
Node = address of start
Step 3 : [Make left and right links of a node]
1) Next [node] = node [make link to node]
2) Previous [node] = node [make link to node]
3) Node = Next [node] [Move pointer to next node]
4) Info [node] = value [Information value of a node]
5) Next [node] = NULL [Assign NULL to the address field]
Step 4 : [ Call Step 3]
Repeat Step 3 to create required number of nodes for linked list
Step 5 : End .
Algorithm for traversing a doubly inked list Step 1 : [initialization]
Node = start. Next [points to the first node in the list]
Step 2 : [Traverse the list in forward direction]
Repeat while Next [node] # NULL process Info [Node]
Step 3 : [Traverse the list in backward direction]
Repeat while Node # NULL Process Info [Node]
Step 4 : Exit.
Algorithm to insert a node at right of the right most node Step 1 : [Initialization]
Node =Start
Step 2 : [Create a new node] New = Create a Node
Step 3 : [Read information associated with newly created node]
Info [Newly] = value
Step 4 : [Perform the insertion]
I) Next [new] = node
II) Previous [New] = Previous [node]
III) Next [Previous[node]] = New
IV) Next [Node] = New
Step 5 : Exit
Algorithm to delete right most node Step 1 : [Initialization]
Node = Start
Step 2 : [Initialization counter]
Counter = 0
Step 3 : [check the list]
If Node = Null
Output “underflow” and exit
Step 4 : [count the number of nodes available in the list]
Repeat while Node # NULL
I) Node = Next [Node]
II) Counter = Counter + 1
Step 5 : [perform deletion]
Node = Start
Repeat through (II) while counter # 1
I) Node = Next [Node]
II) Counter = Counter – 1
III) Next [previous[node]] = Next [Node]
IV) Previous [Next [node]] = previous [node]
V) Delete (node)
Step 6 : Exit.
Algorithm to delete a desired node Step 1 : [Initialization]
Node = Start
Step 2 : [Check the list]
If node = NULL
Output “underflow” and Exit
Step 3 : [Set the counter ]
Search = 0
Step 4 : [Input the node number to which you want to delete]
Node delete = value
Step 5 : [Perform deletion]
Repeat while Node # NULL
If Search = Delete _Node
Next [Previous [Node]] = Next [Node]
Previous [Next[Node]] = Previous [Node]
Delete (Node)
Else
Node = Next [node]
Search = Search + 1
Step 6 : Exit
Example:
#include<stdio.h>
#include<malloc.h>
struct dnode
{
struct dnode *prv;
int data;
struct dnode *next;
};
main()
{
struct dnode *p;
int ans;
p=NULL;
clrscr();
do
{
printf("\n1:enter new node:\n");
printf("2:enter new node at begining:\n");
printf("3:enter new node at position:\n");
printf("4:display value:\n");
printf("5:delete node:\n");
printf("6:exit\n");
printf("enter your choice :");
scanf("%d",&ans);
switch(ans)
{
case 1:
append(&p);
break;
case 2:
addatbeg(&p);
break;
case 3:
addatpos(&p);
break;
case 4:
display(p);
break;
case 5:
deletatpos(&p);
break;
case 6:
exit(0);
break;
}
}while(ans!=6);
getch();
return;
}
append(struct dnode **q)
{
struct dnode *temp,*r;
int n;
temp=(*q);
if(*q==NULL)
{
*q=(struct dnode*)malloc(sizeof(struct dnode*));
(*q)->prv=NULL;
(*q)->next=NULL;
temp=(*q);
}
else
{
while(temp->next!=NULL)
temp=temp->next;
r=(struct dnode*)malloc(sizeof(struct dnode));
temp->next=r;
r->prv=temp;
r->next=NULL;
temp=temp->next;
}
printf("Enter value:");
scanf("%d",&n);
temp->data=n;
return;
}
addatbeg(struct dnode **q)
{
struct dnode *temp;
int n;
temp=(struct dnode*)malloc(sizeof(struct dnode));
temp->prv=NULL;
temp->next=*q;
(*q)->prv=temp;
printf("Enter value:\n");
scanf("%d",&n);
temp->data=n;
(*q) = (*q)->prv;
return;
}
addatpos(struct dnode **q)
{
struct dnode *temp;
int pos,n,flag=0;
printf("Enter position:\n");
scanf("%d",&pos);
while((*q)->next!=NULL)
{
if((*q)->data==pos)
{
flag=1;
break;
}
else
{
flag=0;
}
(*q)=(*q)->next;
}
if(flag==1)
{
printf("enter value :");
scanf("%d",&n);
temp=(struct dnode*)malloc(sizeof(struct dnode));
temp->prv=(*q)->prv->next;
(*q)->prv->next=temp;
temp->next=*q;
(*q)->prv=temp;
temp->data=n;
}
else
{
printf("element is not available:\n");
}
return;
}
deletatpos(struct dnode **q)
{
struct dnode *temp;
int n;
printf("Enter the position:\n");
scanf("%d",&n);
temp=*q;
while(temp->next!=NULL)
{
if(temp->data==n)
{
if(temp==*q)
{
(*q)=(*q)->next;
(*q)->prv=NULL;
}
else
{
if(temp->next==NULL)
temp->prv->next=NULL;
else
{
temp->prv->next=temp->next;
temp->next->prv=temp->prv;
free(temp);
}
}
}temp=temp->next;
}
return;
}
display(struct dnode *q)
{
while(q!=NULL)
{
printf("%d ",q->data);
q=q->next;
}
return;}
Question : Example of Circular Linked List.
#include<stdio.h>
#include<malloc.h>
struct node
{
int data;
struct node *next;
};
main()
{
struct node *front,*rear;
int ans;
front = rear = NULL;
do
{
printf("\n 1.insert node:\n");
printf("\n 2.delet node:\n");
printf("\n 3.display:\n");
printf("\n 4.exit\n");
printf("enter choice\n");
scanf("%d",&ans);
switch(ans)
{
case 1:
add(&front,&rear);
break;
case 2:
delet(&front,&rear);
break;
case 3:
display(front);
break;
case 4:
break;
}
}while(ans!=4);
return;
}
add(struct node **f,struct node **r)
{
struct node *q;
int a;
q=(struct node*)malloc(sizeof(struct node));
printf("\n enter the value:");
scanf("%d",&a);
q->data=a;
if(*f==NULL)
*f=q;
else
(*r)->next=q;
*r=q;
(*r)->next=*f;
return;
}
delet(struct node **f,struct node **r)
{
struct node *q;
int a;
if(*f==NULL)
printf("\n list empty");
else
{
if(*f==*r)
{
a=(*f)->data;
free(*f);
*f=NULL;
*r=NULL;
}
else
{
q=*f;
a=q->data;
(*f)=(*f)->next;
(*r)->next=*f;
free(q);
}
printf("\n deleted node %d",a);
return;
}
return;
}
display(struct node *f)
{
struct node *q=f,*p=NULL;
while(q!=p)
{
printf("%2d\t",q->data);
q=q->next;
p=f;
}
return;
}
Question: Explain the Binary Tree with Example.
A binary tree is an important type of data structure, which is very useful. A tree is a binary tree if each node of it can have at the most two branches. In other words we can say that if every node of a tree can have at most degree two, then this is called a binary tree. In a binary tree left and right sub-trees distinguish sub-trees of a node.
A binary tree T is a finite set of nodes, which is either empty or consists of special node called root R and two disjoint binary trees T1 and T2 (which are called the left sub-tree and right sub-trees, respectively). If T1 is non-empty then the root of T1 is called the left successor of R. If T2 is non-empty then the root of T2 is known as right successor of R.
Recursive algorithm for binary tree creation :
Create_Tree (Info, Node)
Where Info à Information for which we have to create node.
Node à structure type variable to points both left and right child.
Step 1: [Check whether the tree is empty]
If Node = NULL
Node = Create a node
Left_Child [Node] = NULL
Right_Child [Node]] = NULL
Step 2: [Test for the left child]
If Info [node] >= Info
Left_child [Node] = call Create_Tree
(Info, Left_child [Node])
Else
Right_child [Node] = call Create_Tree
(info, Right_child [Node])
Step 3: Return (Node)
Recursive algorithm of preorder traversing:
Preorder (Node)
Step 1: [Do through step 3]
If Node is not equal to NULL
Output Info [Node]
Step 2: Call Preorder (Left_child [Node])
Step 3: Call Preorder (Right_child Node])
Step 4: Exit
Recursive algorithm of inorder traversing: Inorder (Node)
Step 1: [Do through Step 4]
If Node is not equal to NULL
Step 2: Call Inorder (Left_Child [Node])
Step 3: Output Info [Node]
Step 4: Call Inorder (Right_child [Node])
Step 5: Exit
Recursive algorithm of postorder traversing:
Postorder (Node)
Step 1: [Do through step 4]
If Node is not equal to NULL
Step 2: Call Postorder (Left_Child [Node])
Step 3: Call Postorder (Right_Child Node)
Step 4: Output Info [Node]
Step 5: Exit
Example :
/*program for tree operation*/
#include<stdio.h>
#include<conio.h>
#include<malloc.h>
struct tree
{
int no;
struct tree *r,*l;
};
void insert(struct tree *root,int x);
void preorder(struct tree *root);
void inorder(struct tree *root);
void postorder(struct tree *root);
void main()
{
struct tree *root = NULL;
int ch=1,x,level,info;
root=(struct tree *)malloc(sizeof(struct tree));
clrscr();
printf("\n enter the value of root:=");
scanf("%d",&root->no);
root->l = root->r=NULL;
while(ch!=0)
{
printf("\n 1:inert\t 2:preorder\t 3:inorder\t 4:postorder");
printf("\t 0:exit");
printf("\n\n enter the choice:=");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("\n enter the no");
scanf("%d",&x);
insert(root,x);
break;
case 2:
preorder(root);
break;
case 3:
inorder(root);
break;
case 4:
postorder(root);
break;
}
}
}//main over
void insert(struct tree *root,int x)
{
if(x==root->no)
{
printf("\n duplicate no \n\n\n");
return;
}
if(x < root->no)
{
if(root->l!=NULL)
insert(root->l,x);
else
{
root->l=(struct tree*)malloc(sizeof(struct tree));
root->l->no=x;
root->l->l=root->l->r=NULL;
}
}
else
{
if(root->r!=NULL)
insert(root->r,x);
else
{
root->r=(struct tree*)malloc(sizeof(struct tree));
root->r->no=x;
root->r->r=root->r->l=NULL;
}
}
}//insert over
void inorder(struct tree *root)
{
if(root!=NULL)
{
inorder(root->l);
printf("\n %d",root->no);
inorder(root->r);
}
}//inorder over
void preorder(struct tree *root)
{
if(root !=NULL)
{
printf("\n %d",root->no);
preorder(root->l);
preorder(root->r);
}
}//preorder over
void postorder(struct tree *root)
{
if(root!=NULL)
{
postorder(root->l);
postorder(root->r);
printf("\n %d",root->no);
}
}//postorder over
Question: Explain the Bubble sort with algorithm and example.
Bubble_sort (n, list)
Where
N à Represents the number of elements in the list
L à Represents the list of elements
Step 1: [Initialize]
i = 0
Step 2: Repeat through step 5 while ( i < n )
Step 3 : j = 0;
Step 4: Repeat through step 5 while ( j < n-i)
Step 5: if (list[ j] < list [ j+1]
(i) temp = list[ j]
(ii) list[ j+1] = list[ j]
(iii) list[j] = temp
step 6: Exit
Example :
#include<stdio.h>
#include<stdio.h>
void bubble_sort (int array[], int size)
{
int temp, i, j;
for(i = 0; i < size; i++)
for( j=0;j < size-i-1;j++)
if (array[j] < array[ j+1] )
{
temp = array[j];
array[ j] = array[ j+1];
array[ j+1] = temp;
}
}
void main(void)
{
int values[30], i;
printf(“\n Unsorted list is as follows\n”);
for (i = 0; i < 10; i++)
{
values[i] = rand( ) %100;
printf(“%d”, values[i]);
}
bubble_sort (values , 10);
printf(“\n Sorted list is as follows\n”);
for(i = 0; i < 10;i++)
printf(“%d”,values[i]);
}
Question: Explain the Insertion sort with algorithm and example.
Insertion_sort (l,n)
Where l à Represents the list of elements.
N à Represents number of elementsin the list.
Step 1: [Initialize]
1[0] = -0
Step 2: Repeat through Step 3 to 5 for i=1,2,3,4..n
Step 3: (i) temp = l[i]
(ii) pointer = i – 1
Step 4: while(temp < l[pointer])
(i) l[pointer + 1] = l[pointer]
(ii) pointer = pointer – 1
Step 5: l[pointer] = temp
Step 6: Exit
Example:
#Include<stdio.h>
#include<stdlib.h>
int i, k;
void insertion_sort (int *, int);
void display(int *,int)
void insertion_sort(int l[], int n)
{
int pointer, temp;
l[0] = -0;
for(i = 1 ; i <= n ; i++)
{
pointer = i –1;
temp = l[i];
while(temp <l[ponter])
{
l[pointer+1] = l[pointer];
pointer -;
}
l[pointer+1] = temp;
printf(“Step = %d”,i);
for(k = 0; k <= n; k++)
printf(“%d”, l[k]);
printf(“\n”);
}
}
void display(int l[], int n)
{
printf(“\n Sorted list is as follows\n”);
for(i = 1;i <= n; i++)
printf(“%d”,l[i]);
}
void main()
{
int nember = 20;
int list[100];
int i;
printf(“\n Number of elements in the list : %i” , number);
printf(“\n Unsorted list is as follows \n”);
for(i = 1;i <= number; i++)
{
list[i] = rand() %100;
printf(“%d”,list[i]);
}
printf(“\n”);
printf(“\n Stepwise result is as follows \n\n”);
insertion_sort(list, number);
display(list, number);
}
Question: Explain the Quick sort with algorithm and example.
Q_SORT (Array, first, last)
Where array à Represents the list of elements;
First à Represents the position of the first elements in the list (Only at the starting point, it’s value changes during the excution of the function).
Last à Represents the position of the last elements in the list(Only at starting point the value of it’s changes during the execution of the function).
Step 1: [initially]
Low = first
High = last
Pivot = array[(low+high)/2] [middle elements of the elements of the list]
Step 2: Repeat through Step 7 while (low <= high)
Step 3: Repeat Step 4 while (array[low] < pivot)
Step 4: low = low +1
Step 5: Repeat Step 6 while (array[high] > pivot)
Step 6:high = high – 1
Step 7: if ( low<= high)
(i) temp = array[low]
(ii) array[low] = array[high]
(iii) array[high] = temp
(iv) low = low + 1
(v) high = high – 1
Step 8: if ( first < high ) Q_sort(array, first, high)
Step 9: if ( low < lase ) Q_sort(array, low, lase)
Step 10: exit
Example:
#include<stdio.h>
#include<stdlib.h>
void quick_sort(int array[], int first, int last)
{
int temp, low, high, pivot;
low = first;
high = last;
pivot = array[(first + lase) / 2];
do{
while (array[low] < pivot)
low++;
while (array[high] > pivot)
high-;
if(low <= high)
{
temp = array[low];
array[low++] = array[high];
array[high-] = temp;
}
}wihle(low <=high);
if(first < high)
quick_sort(arry, first, high);
if (low < last)
quick_sort(arry, low, last);
}
void main()
{
int values[100], i;
printf(“\n Unsorted list is as follows \n”);
for (i = 0; i < 20; i++)
{
values[i] = rand() % 100;
peintf(“%d”, values[i]);
}
quick_sort(values, 0, 19);
printf(“\n Sorted list as follows \n);
for(i = 0; i < 20; i++)
printf(“%d”, values[i]);
}
Question: Explain the Selection sort with algorithm and example.
Selection_sort (array, size)
Where array à Represents the list of elements
Size à Represents size of the list
Step 1: current = 0 [initially]
Step 2: Repeat through Step 7 while (current < size)
Step 3: j = current + 1;
Step 4: Repeat through Step 6 while (j < size)
Step 5: if (array [current] > array [j])
(i) temp = array[current]
(ii) arra[current] = array[j]
(iii) array[j] =temp
step 6: j = j + 1
Step 7: current = current + 1
Step 8: Exit
Example:
#include<stdio.h>
#include<stdlib.h>
void selection_sort[int array[], int size)
{
int temp, current, j;
for(current = 0; current < size; current++)
for(j = current +1; j < size; j++)
if(array[current] > array[j])
{
temp = array[current];
array[current] = array[j];
array[j] = temp;
}
}
void main()
{
int values[30], i;
printf(“\n Unsorted list is as follows\n”)
for(i = 0; i < 30; i++)
{
values[i] = rand() % 100;
printf(“%d”, values[i]);
}
selection_sort(values, 30 );
printf(“\n sorted list is as follows\n”);
for ( i = 0; i < 30; i++)
printf(“%d”, values[i]);
}
Question: Explain the Shell sort with algorithm and example.
Shell_sort(array, size)
Where array à Represents the list of elements
Size à Represents the size of the list
Step 1: [Initialize]
Gap = size / 2
Stpe 2: Repeat through Step 6 while(gap = gap / 2)
Step 3: swap = 0
Step 4: Repeat through Step 6 for i=0, 1, 2, 3…i <(size – gap)
Step 6:if (array[i] > array[i+gap]
(i) temp = array [i]
(ii) array[i] = array[i + gap]
(iii) array[i + gap]= temp
(iv) swap = 1
[ End of for loop]
[ End of inner while loop]
[ End of outer while loop]
Step 7: output arrayelements (sorted)
Step 8: Exit
Example:
#include<stdio.h>
#include<stdlib.h>
void shell_sort(int array[], int size)
{
int temp, gap, i, swap;
gap = size / 2;
do {
do {
swap = 0;
for (i = 0; i < size – gap; i++)
if(array[i] > array[i + gap])
{
temp = array[i];
array[i] = array[i + gap];
array[i + gap] = temp;
swap = 1;
}
}while (swap);
}while (gap = gap / 2);
}
void main(void)
{
int values[50], i;
print(“\n Unsorted list is as follows \n”);
for(i = 0; i < 50; i++)
{
values[i] = rand() % 100;
printf(“%d”, values[i]);
}
shell_sort(values, 50);
printf(“\n Sorted list is as follow \n”);
for(i = 0; i < 50; i++)
printf(“%d”, value[i]);
}