R20 DATA STRUCTURES LAB

DATA STRUCTURES LAB

Data Structures LAB

Exercise-1
  • a) Write C program that use both recursive and non recursive functions to perform Linear search for a Key value in a given list.
//non recursive functions to perform Linear search
#include<stdio.h>
void main()
{
    int n,a[100],se,i;
    void linear(int ,int [],int);
    printf("Enter searching element:");
    scanf("%d",&se);
    printf("Enter no of elements:");
    scanf("%d",&n);
    printf("Enter elements into the array:");
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    linear(n,a,se);
}
void linear(int n,int a[100],int se)
{
    int i,flag=0;
    for(i=0;i<n;i++)
    {
        if(a[i]==se)
        {
            flag=1;
            printf("Element %d found at %d",se,i);
        }
    }
    if(flag==0)
    {
        printf("%d was not found",se);
    }
}

  • b) Write C program that use both recursive and non recursive functions to perform Binary search for a Key value in a given list.
//Binary search without recursion
#include<stdio.h>
void main()
{
    int n,a[100],se,i;
    void binarysearch(int ,int [],int);
    printf("Enter the no of elements:");
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        printf("Enter %d elements:",i+1);
        scanf("%d",&a[i]);
    }
    printf("Enter searching elements");
    scanf("%d",&se);
    binarysearch(n,a,se);

}
void binarysearch(int n,int a[100],int se)
{
    int low,high,mid,flag=0;
    low=0;
    high=(n-1);
    mid=(low+high)/2;
    while(low<high)
    {
        if(se==a[mid])
        {
            flag=1;
            printf("The element %d is found at %d",se,mid);
            break;
        }
        else if(se<a[mid])
        {
            low=0;
            high=mid-1;

        }
        else if(se<a[mid])
        {
            low=mid+1;
            high=high;
        
        }
    }
    if(flag==0)
    {
        printf("Element %d is not found",se);
    }
}

Exercise-2(Sorting-I)
  • a) Write C program that implement Bubble sort, to sort a given list of integers in ascending order.
//Bubble sort
#include<stdio.h>
void main()
{
    int i,n,a[100],j,temp;
    printf("Enter size:");
    scanf("%d",&n);
    printf("Enter elements into the array:");
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(i=0;i<n-1;i++)
    {
        for(j=0;j<n-1-i;j++)
        {
            if(a[j]>a[j+1])
            {
                temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;

            }
        }
    }
    printf("Elements after sorting are:");
    for(i=0;i<n;i++)
    {
        printf("%d,",a[i]);
    }
}

  • c) Write C program that implement Insertion sort, to sort a given list of integers in ascending order
//Insertion sort
#include<stdio.h>
void main()
{
    int n,a[100],i,j,temp;
    printf("Enter size:");
    scanf("%d",&n);
    printf("Enter elements into the array:");
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(i=1;i<n;i++)
    {
        temp=a[i];
        j=i-1;
        while((j>=0)&&(temp<a[j]))
        {
            a[j+1]=a[j];
            j--;

        }
        a[j+1]=temp;
    }
    printf("Elements after sorting:");
    for(i=0;i<n;i++)
    {
        printf("%d,",a[i]);
    }
}

Exercise - 3
  • b) Write C program that implement merge sort, to sort a given list of integers in ascending order.
//Merge sort
#include<stdio.h>
void mergesort(int a[],int lb,int ub);
void merge(int a[],int lb,int mid,int ub);
void main()
{
    int a[100],i,n;
    printf("Enter array size:");
    scanf("%d",&n);
    printf("Enter elements into the array:\n");
    for(i=0;i<n;i++)
    {
        printf("Enter %d element:",i+1);
        scanf("%d",&a[i]);
    }
    mergesort(a,0,n-1);
    printf("The array elements after sorting are:");
    for(i=0;i<n;i++)
    {
        printf("%d,",a[i]);
    }
}
void mergesort(int a[],int lb,int ub)
{
    int mid;
    if(lb<ub)
    {
        mid=(lb+ub)/2;
        mergesort(a,lb,mid);
        mergesort(a,mid+1,ub);
        merge(a,lb,mid,ub);
    }
}
void merge(int a[],int lb,int mid,int ub)
{
    int i,j,k;
    int b[100];
    i=lb;
    j=mid+1;
    k=lb;
    while (i<=mid&&j<=ub)
    {
        if(a[i]<a[j])
        {
            b[k]=a[i];
            i++;
            k++;
        }
        else
        {
            b[k]=a[j];
            j++;
           k++;
        }
    }
    if(i>mid)
    {
        while(j<=ub)
        {
            b[k]=a[i];
            i++;
            k++;
        }
    }
    else
    {
        while(i<=mid)
        {
            b[k]=a[i];
            i++;
            k++;
        }
    }
    for(i=lb;i<=ub;i++)
    {
        a[i]=b[i];
    }
    
}


Exercise - 4(Singly Linked List)
  • a) Write a C program that uses functions to create a singly linked list
  • b) Write a C program that uses functions to perform insertion operation on a singly linked list
  • c) Write a C program that uses functions to perform deletion operation on a singly linked list
 #include<stdio.h>
#include<stdlib.h>
struct node
{
    int data;
    struct node *next;
};
struct node *head=NULL;
void insert_begin();
void insert_end();
void insert_loc();
void delete_begin();
void delete_end();
void delete_loc();
void search();
void display();

void main()
{
    int ch;
    while(1)
    {
        printf("1.Insert at beginning");
        printf("\n2.Insert at end");
        printf("\n3.Insert at location");
        printf("\n4.delete at beginning");
        printf("\n5.delete at end");
        printf("\n6.delete at location");
        printf("\n7.search");
        printf("\n8.display");
        printf("\n9.exit");
        printf("\nEnter your choice:");
        scanf("%d",&ch);
    
    switch(ch)
    {
        case 1:
                insert_begin();
                break;
        case 2:
                insert_end();
                break;
        case 3:
                insert_loc();
                break;
        case 4:
                delete_begin();
                break;
        case 5:
                delete_end();
                break;
        case 6:
                delete_loc();
                break;
        case 7:
                search();
                break;
        case 8:
                display();
                break;
        case 9:
                exit(0);
                break;
        default:
                printf("No choice found");
                break;
    
    }
    }

}

void insert_begin()
{
    int data;
    struct node *newnode=(struct node*)malloc(sizeof(struct node*));
    printf("Enter a value to insert:");
    scanf("%d",&data);
    if(newnode==NULL)
        printf("Memmory is full");
    else if(head==NULL)
    {
        newnode->data=data;
        newnode->next=NULL;
        head=newnode;
    }
    else
    {
        newnode->data=data;
        newnode->next=head;
        head=newnode;
    }
    

    
    
}
void insert_end()
{
        int data;
        struct node *newnode=(struct node*)malloc(sizeof(struct node*));
        printf("Enter value to insert:");
        scanf("%d",&data);
        if(newnode==NULL)
                printf("Memory is full");
        else if(head==NULL)
        {
                newnode->data=data;
                newnode->next=NULL;
                head=newnode;
        }
       else
       {
                newnode->data=data;
                newnode->next=NULL;
                struct node *temp;
                temp=head;
                while(temp->next!=NULL)
                {
                        temp=temp->next;

                }
                temp->next=newnode;
       }
}
void insert_loc()
{
        int data,loc;
        struct node *newnode=(struct node*)malloc(sizeof(struct node*));
        printf("Enter a value to enter:");
        scanf("%d",&data);
        if(newnode==NULL)
                printf("Memory is full");
        else if(head==NULL)
        {
                newnode->data=data;
                newnode->next=NULL;
                head=newnode;
        }
        else
        {
                printf("Enter a location:");
                scanf("%d",&loc);
                struct node *temp;
                temp=head;
                while(temp->next!=loc)
                {
                        temp=temp->next;
                }
                newnode->data=data;
                newnode->next=temp->next;
                temp->next=newnode;

        }
        
        
}
void delete_begin()
{
        if(head=NULL)
                printf("Linked List is empty");
        else
        {
                struct node*temp;
                temp=head;
                head=head->next;
                temp->next=NULL;
                free(temp);
        }
}
void delete_end()
{
        if(head==NULL)
                printf("Linked List is empty");
        else
        {
                struct node *temp;
                struct node *prev;
                prev=head;
                temp=head->next;
                while(temp->next!=NULL)
                {
                        temp=temp->next;
                        prev=prev->next;
                }
                prev->next=NULL;
                free(temp);
        }
}
void delete_loc()
{
        int loc;
         if(head=NULL)
                printf("Linked List is empty");
        else
        {
                struct node *temp;
                struct node *prev;
                prev=head;
                temp=head->next;
                printf("Enter a location:");
                scanf("%d",&loc);
                while(temp->next!=loc)
                {
                        temp=temp->next;
                        prev=prev->next;
                }
                prev->next=temp->next;
                temp->next=NULL;
                free(temp);
                
        }
}
void search()
{
        int se,count=0;
        if(head==NULL)
                printf("Linked List is empty");
        else
        {
                printf("Enter a searching element");
                scanf("%d",&se);
                struct node *temp;
                temp=head;
                while(temp->next!=NULL)
                {
                        if(se==temp->data)
                                count++;
                }
                temp=temp->next;
                if(count==0)
                        printf("Element is not found");
                else
                        printf("Element is found %d times",count);

        }
}
void display()
{
        if(head==NULL)
                printf("Linked List is empty");
        else
        {
                struct node *temp;
                temp=head;
                while(temp->next!=NULL)
                {
                        printf("%d->",temp->data);
                        temp=temp->next;
                }
                printf("%d\n",temp->data);
        }
}
        



No comments

JavaFX Scene Builder

  This is an article about the JavaFX Scene Builder. You will get a short introduction about the installation and usage of the software. The...