PRACTICAL FILE
DATA STRUCTURES
BCA 3RD SEMESTER
DEPARTMENT OF COMPUTER SCIENCE AND
APPLICATIONS
KAMLA LOHTIA SANATAN DHARAM COLLEGE,
LUDHIANA
SUBMITTED TO SUBMITTED BY
PROF. ISHPREET SINGH
PROF. DRISHTI NAME:
UNIV ROLLNO:
CLASS ROLLNO:
Program to traverse and insert an element in 1-Dimensional array
#include <stdio.h>
#include <conio.h>
#define SIZE 20
int insert(int[],int,int,int);
void traverse(int[],int);
void main()
{
int i=0,A[SIZE],n,pos,item;
clrscr();
printf(“\n\n\t\t Program to insert element in 1-Dimensional array:”);
printf(“\n\n\t\tHow many number you want to store in the array:”);
scanf(“%d”,&n);
while(i<n)
{
printf(“\nEnter value A[%d]:”,i);
scanf(“%d”,&A[i]);
i++;
}
traverse(A,n);
printf(“\nEnter the index to insert new number:”);
scanf(“%d”,&pos);
printf(“\nEnter the number:”);
scanf(“%d”,&item);
n = insert(A,n,pos,item);
traverse(A,n);
getch();
}
void traverse(int A[], int n)
{
int i=0;
printf(“\n\n\t\t elements of array are:\n”);
while(i<n)
{
printf(“A[%d]:”,i);
printf(“%d\n”,A[i]);
i++;
}
printf(“\n”);
}
int insert(int A[], int n, int pos, int item)
{
int i;
for(i=n;i>=pos;i—)
A[i+1] = A[i];
A[pos] = item;
n= n+1;
return n;
}
Program to delete an element from an array
#include<stdio.h>
int main(){
int a[50],i,pos,size;
printf("\nEnter size of the array: ");
scanf("%d",&size);
printf("\nEnter %d elements in to the array: ",size);
for(i=0;i<size;i++)
scanf("%d",&a[i]);
printf("\nEnter position where to delete: ");
scanf("%d",&pos);
i=0;
while(i!=pos-1)
i++;
while(i<10){
a[i]=a[i+1];
i++;
}
size--;
for(i=0;i<size;i++)
printf(" %d",a[i]);
return 0;
}
Program for inserting, deleting node and traversing elements in a linked
list
#include"stdio.h"
struct node
{
int data;
struct node *next;
}*p;
delnode(int num)
{
struct node *temp, *m;
temp=p;
while(temp!=NULL)
{
if(temp->data==num)
{
if(temp==p)
{
p=temp->next;
free(temp);
return;
}
else
{
m->next=temp->next;
free(temp);
return;
}
}else
{
m=temp;
temp= temp->next;
}
}
printf("
ELEMENT %d NOT FOUND
", num);
append( int num )
{
struct node *temp,*r;
temp= (struct node *)malloc(sizeof(struct node));
temp->data=num;
r=(struct node *)p;
if (p == NULL) {
p=temp;
p->next =NULL;
}
else
{
while( r->next != NULL)
r=r->next;
r->next =temp;
r=temp;
r->next=NULL;
}
}
addbeg( int num )
{
struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));
temp->data=num;
if ( p== NULL)
{
p=temp;
p->next=NULL;
}
else
{
temp->next=p;
p=temp;
}
}
addafter(int num, int loc)
{
int i;
struct node *temp,*t,*r;
r=p;
if(loc > count()+1 || loc <= 0)
{
printf(" insertion is not possible :");
return;
}
if (loc == 1)
{
addbeg(num);
return;
}
else
{
for(i=1;i<loc;i++)
{
t=r;
r=r->next;
}
temp=(struct node *)malloc(sizeof(struct node));
temp->data=num;
t->next=temp;
t=temp;
t->next=r;
return;
}
}
display(struct node *r)
{
r=p;
if(r==NULL)
{
printf("NO ELEMENT IN THE LIST :");
return;
}
while(r!=NULL)
{
printf(" -> %d ",r->data);
r=r->next;
}
printf("
");
}
count()
{
struct node *n;
int c=0;
n=p;
while(n!=NULL)
{
n=n->next;
c++;
}
return(c);
}
reverse(struct node *q)
{
struct node *m, *n,*l,*s;
m=q;
n=NULL;
while(m!=NULL)
{
s=n;
n=m;
m=m->next;
n->next=s;
}
p=n;
}
main()
{
int i;
p=NULL;
while(1)
{
printf("
[Link] A NUMBER AT BEGINNING;
");
printf("
[Link] A NUMBER AT LAST:
");
printf("
[Link] A NUMBER AT A PARTICULAR LOCATION INlIST:
");
printf("
[Link] THE ELEMENTS IN THE LIST :
");
printf("
[Link] THE NUMBER OF ELEMENTS IN THE LIST
");
printf("
[Link] A NODE IN THE LINKED LIST:
");
printf("
[Link] A LINKED LIST :
");
printf("
[Link] OUT OF LINKED LIST (BYEE BYEE):
");
printf("
PLEASE, ENTER THE NUMBER:");
scanf("%d",&i); /* ENTER A VALUE FOR SWITCH */
switch(i)
{
case 1:
{
int num;
printf("
PLEASE ENTER THE NUMBER :-");
scanf("%d",&num);
addbeg(num);
break;
}
case 2:
{
int num;
printf("
PLEASE ENTER THE NUMBER :-");
scanf("%d",&num);
append(num);
break;
}
case 3:
{
int num, loc,k;
printf("
PLEASE ENTER THE NUMBER :-");
scanf("%d",&num);
printf("
PLEASE ENTER THE LOCATION NUMBER :-");
scanf("%d",&loc);
addafter(num,loc);
break;
} case 4:
{
struct node *n;
printf("
THE ELEMENTS IN THE LIST ARE :
");
display(n);
break;
}
case 5:
{
struct node *n;
display(n);
printf(" TOTAL NO OF ELEMENTS IN THE LSIT ARE
%d",count());
break;
} case 6:
{
int num;
printf("
PLEASE ENTER A NUMBER FROM THE LIST :");
scanf("%d",&num);
delnode(num);
break;
}
case 7:
{
reverse(p);
display(p);
break;
}
case 8:
{
exit();
}
Program of push and pop operation on stack implementing Array
# include< stdio.h>
# include< string.h>
# define size 3
int tos= -1;
/*this variable will keep track of the top of the stack */
int flag = 0;
/* this variable will determine whether push or pop will be granted. */
int stack[size];
/* array , within this array stack will grow and shrink. */
void push(int s[], int d)
{
if(tos==size-1)
{
/* this condition becomes true when the stack can not grow further */
flag=0;
}
else
{
flag = 1;
++tos;
s[tos] = d;
}
}
int pop(int s[])
{
int p;
if(tos == -1)
{
p = 0;
flag = 0;
}
else
{
flag = 1;
p = s[tos];
--tos;
}
return p;
}
void display(int s[])
{
int i;
if(tos == -1)
{
printf("\n Stack is empty");
}
else
{
for(i = tos; i >= 0; --i)
printf("\n %d", s[i] );
}
}
void main()
{
int data;
char choice;
int q = 0;
clrscr();
do
{
printf(" \nPush->i Pop->p Quit->q:");
printf("\nInput the choice : ");
do
{
choice = getchar();
choice =tolower(choice);
}while(strchr("ipq",choice)==NULL);
printf("Your choice is: %c",choice);
switch(choice)
{
case 'i' :
printf("\n Input the element to push:");
scanf("%d", &data);
push(stack, data);
if(flag)
{
printf("\n After inserting ");
display(stack);
if(tos == (size-1))
printf("\n Stack is full");
}
else
printf("\n capacity is exhausted");
break;
case 'p' :
data = pop(stack);
if(flag)
{
printf("\n Data is popped: %d", data);
printf("\n Rest data in stack is as follows:\n");
display(stack);
}
else
printf("\n No popping took place" );
break;
case 'q':
q = 1;
}
} while(!q);
getch();
}
Program for push and pop operation on stack using linked list
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
void push();
void pop();
void display();
struct stack //Define the <span id="IL_AD3"
class="IL_AD">structure</span>
{
int info;
struct stack *next;
}*top=NULL;
typedef struct stack stackVar;
int main()
{
char choice;
do{
int option;
<span id="IL_AD2" class="IL_AD">printf</span>("\
n*******MAIN MENU*********");
printf("\[Link] into the stack");
printf("\[Link] from the stack");
printf("\[Link] the element of the stack");
printf("\[Link]");
printf("\nEnter ur choice::");
scanf("%d",&option);
switch(option)
{
case 1: push();
break;
case 2: pop();
break;
case 3: display();
break;
case 4: exit(0);
break;
default: printf("Invalid <span id="IL_AD5"
class="IL_AD">Selection</span>");
break;
};
printf("\n\nWant 2 continue(press y to yes)");
fflush(stdin);
scanf("%c",&choice);
while(choice=='y' || choice=='Y');
getch();
return 0;
}
void push()
{
stackVar *node;
node=(stackVar *)malloc(sizeof(stackVar)); //Allocate memeory for
the new node
printf("\nEnter element ::");
scanf("%d",&node->info);
if(top!=NULL) //check whether element is empty or not
{ node->next=top; //make node next pointer point to top of the
stack
top=node; // make Top as node
}
else // stack is empty
{ node->next=NULL; //Make node next pointer point to null as
it is only node available
top=node; //Make top as node
}
}
void pop()
{
stackVar *temp;
int item;
temp=top;
if(temp==NULL) //Check for empty stack
{
printf("\nStack is already empty");
return;
}
item=temp->info; // Put top element in the temporary variable
top=top->next; //Move top point to one level down in the stack
free(temp); //Free top element
printf("Deleted element is:%d",item);
}
void display()
{
stackVar *temp;
temp=top;
if(temp!=NULL)
printf("\nElement in the stacks are");
else
printf("\nStack is already empty");
while(temp!=NULL)
{
printf("\n%d",temp->info);
temp=temp->next;
}
}
PROGRAM FOR INSERTION AND DELETION IN QUEUE
#include<stdio.h>
#include<conio.h>
void insert(int);
int delet(int);
void display(void);
int queue[3];
int rear=-1;
int front=-1;
void main()
{
int n=3;
char op;
clrscr();
do
{
printf("\nOptions");
printf("\nPress i for insertion");
printf("\nPress d for deletion");
printf("\nPress p for display");
printf("\nPress e for exit");
op=getche();
switch(op)
{
case 'i':insert(n);break;
case 'd':delet(n);break;
case 'p':display(); break;
default:printf("\nWrong operator");
}
}
while(op!='e');
getch();
}
void insert(int n)
{
int item;
if((front==0&&rear==n)||(front==rear+1))
{ printf("\nQueue over flow");
return;
}
if(front==-1)
{
front=0;
rear=0;
}
else if(rear==n)
rear=0;
else
rear=rear+1;
printf("\nEnter the item to be inserted");
scanf("%d",&item);
queue[rear]=item;
}
int delet(int n)
{
int item;
if(front==-1)
{ printf("\nQueue is empty");
return;
}
printf("\nYou have deleted %d",queue[front]);
queue[front]=0;
if(front==rear)
{
front=-1;
rear=-1;
}
else if(front==n)
front=0;
else
front=front+1;
return;
}
void display(void)
{
int i;
printf("\nDisplaying Queue\n");
for(i=0;i<3;i++)
printf("\n%d",queue[i]);
}
Program for insertion sort
#include<stdio.h>
#include<conio.h>
void insertion_sort(int a[], int length)
{
int i;
for (i=0; i < length; i++)
{
int j, v = a[i];
for (j = i - 1; j >= 0; j--)
{
if (a[j] <= v) break;
a[j + 1] = a[j];
}
a[j + 1] = v;
}
}
void checkThatArrayIsSorted (int array[], int length)
{
int i;
for (i = 1; i < length; i+=1)
{
if (array[i-1] > array[i])
{
printf("The array is not in sorted order at position %d\n", i-1);
}
}
}
int main(void)
{
unsigned int i;
int a[] = {5,1,9,3,2};
insertion_sort(a, sizeof(a)/sizeof(*a));
for(i=0; i<sizeof(a)/sizeof(*a); i++)
{
printf("%d\n", a[i]);
}
checkThatArrayIsSorted(a, sizeof(a)/sizeof(*a));
return 0;
}
Program for selection sort in array
#include<stdio.h>
#include<conio.h>
void selection_sort(int a[],int size);
void main()
{
int a[20],i,size;
clrscr();
printf("Enter size of an array = ");
scanf("%d",&size);
printf("\nEnter array data:\n");
for(i=0;i<size;i++)
{
printf("a[%d]=",i);
scanf("%d",&a[i]);
}
printf("\nUnsorted array data:\n");
for(i=0;i<size;i++)
{
printf("a[%d]=%d\n",i,a[i]);
}
printf("\nSorted array data:\n");
selection_sort(a,size);
for(i=0;i<size;i++)
{
printf("a[%d]=%d\n",i,a[i]);
}
getch();
}
void selection_sort(int a[],int size)
{
int i,j,t;
for(i=0;i<size-1;i++)
{
for(j=i+1;j<size;j++)
{
if(a[i]>a[j])
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
}
}
Program for merge sort in array
#include <time.h>
#include <stdlib.h>
#include <stdio.h>
#define MIN_MERGESORT_LIST_SIZE 32
void mergesort_array(int a[], int size, int temp[]) {
int i1, i2, tempi;
if (size < MIN_MERGESORT_LIST_SIZE) {
int i;
for (i=0; i < size; i++) {
int j, v = a[i];
for (j = i - 1; j >= 0; j--) {
if (a[j] <= v) break;
a[j + 1] = a[j];
}
a[j + 1] = v;
}
return;
}
mergesort_array(a, size/2, temp);
mergesort_array(a + size/2, size - size/2, temp);
i1 = 0;
i2 = size/2;
tempi = 0;
while (i1 < size/2 && i2 < size) {
if (a[i1] < a[i2]) {
temp[tempi] = a[i1];
i1++;
} else {
temp[tempi] = a[i2];
i2++;
}
tempi++;
}
while (i1 < size/2) {
temp[tempi] = a[i1];
i1++;
tempi++;
}
while (i2 < size) {
temp[tempi] = a[i2];
i2++;
tempi++;
}
memcpy(a, temp, size*sizeof(int));
}
int main(int argc, char* argv[]) {
int size = atoi(argv[1]);
int* a = malloc(sizeof(int)*size);
int* temp = malloc(sizeof(int)*size);
int i;
srand(time(NULL));
for(i=0; i<size; i++) {
a[i] = rand() % size;
}
mergesort_array(a, size, temp);
for(i=1; i<size; i++) {
if (!(a[i-1] <= a[i])) {
puts("ERROR");
return -1;
}
}
puts("SUCCESS");
return 0;
}
Program for bubble sort in array
#include<stdio.h>
#include<conio.h>
main()
{
int arr[50],temp,i,j,n;
clrscr();
printf("\nEnter any Value less Than 50");
scanf("%d",&n);
printf("\n\tEnter The Values into ARRAY ");
for(i=0;i<n;i++)
{
printf("\n\n Enter Element no %d: ",i+1);
scanf("%d",&arr[i]);
}
for(i=0;i<n-1;i++)
{
for(j=0;j<n-i-1;j++)
{
if(arr[j] >arr[j+1])
{
temp=arr[j];
arr[j]=arr[j+1];
arr[j+1]=temp;
}
}
}
printf("\n\n-- Sorted Series --");
for(i=0;i<n;i++)
{
printf("\n \n \t %d",arr[i]);
}
getch();
}
Program for linear search in array
#include<stdio.h>
int main(){
int a[10],i,n,m,c=0;
printf("Enter the size of an array");
scanf("%d",&n);
printf("\nEnter the elements of the array");
for(i=0;i<=n-1;i++){
scanf("%d",&a[i]);
}
printf("\nThe elements of an array are");
for(i=0;i<=n-1;i++){
printf(" %d",a[i]);
}
printf("\nEnter the number to be search");
scanf("%d",&m);
for(i=0;i<=n-1;i++){
if(a[i]==m){
c=1;
break;
}
}
if(c==0)
printf("\nThe number is not in the list");
else
printf("\nThe number is found");
return 0;
}
Program for binary search in array
#include<stdio.h>
#include<conio.h>
void main()
{
int array[10];
int i, j, n, temp, num;
int low,mid,high;
clrscr();
printf("Enter the value of the array\t");
scanf("%d",&n);
printf("Enter the elements one by one:\n");
for(i=0;i<n;i++)
{
scanf("%d",&array[i]);
}
printf("Input array elements\n");
for(i=0;i<n;i++)
{
printf("%d\n",array[i]);
}
for(i=0;i<n;i++)
{
for(j=0;j<(n-i-1);j++)
{
if(array[j]>array[j+1])
{
temp=array[j];
array[j]=array[j+1];
array[j+1]=temp;
}
}
}
printf("Sorted array is...\n");
for(i=0;i<n;i++)
{
printf("%d\n",array[i]);
}
printf("Enter the element to be searched\n");
scanf("%d",&num);
low=1;
high=n;
do
{
mid=(low+high)/2;
if(num<array[mid])
high=mid-1;
else if(num>array[mid])
low=mid+1;
}
while(num!=array[mid] && low<=high);
if(num==array[mid])
{
printf("\n\tis present at position %d",array[i],i+1);
}
else
{
printf("Search is FAILED\n");
}
getch();
}