NEP-SYBCS DS-I Assignment -I

Assignment 1:-  Searching Algorithms

Set A

a) Create a random array of n integers. Accept a value x from user and use linear search algorithm to check whether the number is present in the array or not and output the position if the number is present.

#include<stdio.h>

#define max 10

int main()

{

int a[max],k,i,n,flag=0,index;

printf("Enter n:");

scanf("%d",&n);

generate(a,n);

printf("Random elements are\n");

   for(i=0;i<n;i++)

      printf("%d\n",a[i]);

printf("Enter number to search: ");

   scanf("%d",&k);

linearsearch(a,n,k);

}

void generate(int a[],int n)

{

int i;

for(i=0;i<n;i++)

   a[i]=rand()%100;

}

void linearsearch(int a[],int n,int k)

{

int i,flag=0,index ;

for(i=0;i<n;i++)

if(a[i]==k)

{

flag=1;

index=i;

}

if(flag==1)

{

printf("Element found at index %d",index+1);

}

else

printf("Not Found");

}

b) Accept n sorted values in array from user. Accept a value x from user and use binary search algorithm to check whether the number is present in sorted array or not and output the position if the number is present.

#include<stdio.h>

#define max 10

int main()

{

int a[max],i,n,key,high,low=0,mid;

printf("how many array elements:");

scanf("%d",&n);

printf("Enter array:");

accept(a,n);//calling function

printf("Array elements are:\n");

for(i=0;i<n;i++)

printf("%d ",a[i]);//displaying array

printf("\nEnter number to search:");

scanf("%d",&key);

binarysearch(0,n-1,a,key);//calling function

}

//function binary

void binarysearch(int low,int high,int a[],int key)

{

 int mid;

 if(low>high)

 {

  printf("Search is not successful\n");

  return;

 }

 mid=(low+high)/2;

 if(key==a[mid])

 {

  printf("Search Found at index %d\n",mid+1);

  return;

 }

 else if(key<a[mid])

 {

  return binarysearch(low,mid-1,a,key);

 }

 else if(key>a[mid])

 {

  return binarysearch(mid+1,high,a,key);

 }

}

//Accept function to store element

void accept(int a[],int n)

{

int i;

for(i=0;i<n;i++)

scanf("%d",&a[i]);

}

Set B

a) Read the data from file 'student.txt' containing names of student and their class (FY, SY, TY). Accept a student name from user and use linear search algorithm to check whether the name is present in the file and output the Class of student otherwise output “Student not in the list”.

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define MAX_STUDENTS 100

#define NAME_LEN 50

#define CLASS_LEN 5

// Structure to store student records

typedef struct {

    char name[NAME_LEN];

    char s_class[CLASS_LEN];

} Student;

int main() {

    FILE *fp;

    Student s[MAX_STUDENTS];

    char search_name[NAME_LEN];

    int n = 0;

    int found = 0;

    fp = fopen("student.txt", "r");

    if (fp == NULL) {

        printf("Error: Could not open file student.txt\n");

        return 1;

    }

    while (fscanf(fp, "%s %s", s[n].name, s[n].s_class) != EOF) {

        n++;

        if (n >= MAX_STUDENTS) break; 

    }

    fclose(fp);

    printf("Enter the student name to search: ");

    scanf("%s", search_name);

    for (int i = 0; i < n; i++) {

        // Perform a case-sensitive string match

        if (strcmp(s[i].name, search_name) == 0) {

            printf("Class: %s\n", s[i].s_class);

            found = 1;

            break; // Stop looking once the item is found

        }

    }

    if (!found) {

        printf("Student not in the list\n");

    }

    return 0;

}

create student.txt file 

Amit FY

Rahul SY

Pooja TY

Sneha SY

b) Read the data from file 'student.txt' containing names of student and their class(FY, SY,TY). Accept a student name from user and use binary search algorithm to check whether the name is present in the file  and output the class of student otherwise output “Student not in the list”.

Create Student.txt file 

Amit FY

Kiran SY

Rahul TY

Zoya SY

Complete C Code Implementationc#include <stdio.h>

#include <stdlib.h>

#include <string.h>

typedef struct {

    char name[50];

    char s_class[10]; // Named s_class to avoid conflict with C++ keywords

} Student;

int read_file(Student s[]);

void sort_records(Student s[], int n);

void binary_search(Student s[], int n, char key[]);

int main() {

    Student s[100];

    int n;

    char search_name[50];

    n = read_file(s);

    if (n == 0) {

        printf("No records found or file error.\n");

        return 1;

    }

    sort_records(s, n);

     printf("Enter the name of the student to search: ");

    scanf("%s", search_name);

    binary_search(s, n, search_name);

    return 0;

}

int read_file(Student s[]) {

    FILE *fp;

    int i = 0;

    fp = fopen("student.txt", "r");

    if (fp == NULL) {

        printf("Error: Cannot open file 'student.txt'. Make sure it exists.\n");

        return 0;

    }

    while (fscanf(fp, "%s %s", s[i].name, s[i].s_class) != EOF) {

        i++;

    }

    fclose(fp);

    return i; // Returns total number of students read

}

void sort_records(Student s[], int n) {

    int i, j;

    Student temp;

    for (i = 0; i < n - 1; i++) {

        for (j = 0; j < n - i - 1; j++) {

            // Compare names using strcmp

            if (strcmp(s[j].name, s[j + 1].name) > 0) {

                temp = s[j];

                s[j] = s[j + 1];

                s[j + 1] = temp;

            }

        }

    }

}

void binary_search(Student s[], int n, char key[]) {

    int low = 0;

    int high = n - 1;

    int mid;

    int found = 0;

    while (low <= high) {

        mid = (low + high) / 2;

      int res = strcmp(s[mid].name, key);

        if (res == 0) {

                   printf("Class of student: %s\n", s[mid].s_class);

            found = 1;

            break;

        } 

        else if (res < 0) {

                    low = mid + 1;

        } 

        else {

                     high = mid - 1;

        }

    }

    if (!found) {

        printf("Student not in the list\n");

    }

}