Dawood University of Engineering and Technology Data Structures and Algorithm

Data Structures & Algorithm

Sardar sami ullah

Batch 2019-Fall
Submitted toEngr. Majid Ahmed

1
Sardar sami (19f-es-91)
Dawood University of Engineering and Technology Data Structures and Algorithm

Lab 01
Objective:
Introduction to Data Types & Programming Concepts
Task 1
Design a program for employ record using structure

#include <stdio.h>
struct employee{
char name[30];
int empId;
float salary;
};
int main()
{
struct employee emp;
printf("\nEnter details :\n");
printf("Name ?:");
gets([Link]);
printf("\nID ?:");
scanf("%d",&[Link]);
printf("\nSalary ?:");
scanf("%f",&[Link]);
printf("\nEntered detail is:");
printf("Name: %s" ,[Link]);
printf("\nId: %d" ,[Link]);
printf("\nSalary: %f\n",[Link]);
return 0;
}

2
Sardar sami (19f-es-91)
Dawood University of Engineering and Technology Data Structures and Algorithm

3
Sardar sami (19f-es-91)
Dawood University of Engineering and Technology Data Structures and Algorithm

Task 02
Design a program which can access admission committee to maintain record
Data fields are
 Name
 Father name
 CNIC number
 Roll #

#include<stdio.h>
int main()
{
inti ;
struct student
{
char name [30];
char Fathername[30];
int rollno;
float Position; };
struct student s[10];
{
printf("\nEnter Name: ");
scanf("%s",&s[i].name);
printf("\nEnter Father Name: ");
scanf("%s",&s[i].Fathername);
printf("\nEnter roll no: ");
scanf("%d",&s[i].rollno);
printf("\nEnter Position: ");
scanf("%f",&s[i].Position);
printf("\nName: %s \n Father Name: %s \t Roll no: %d\t Position:
%.2f\n", s[i].name, s[i].Fathername ,s[i].rollno,s[i].Position);
}

4
Sardar sami (19f-es-91)
Dawood University of Engineering and Technology Data Structures and Algorithm

Lab 02
Objective
Linear Search Algorithm
Task
To search an element in two-dimensional array using linear search

#include<stdio.h>
int main ()
{
int a[10],i,item,flag=0;
printf("Enter the data in the array");
for(i=0;i<5 ;i++)
{
scanf("%d",&a[i]); }
printf("\nEnter the element to be searched");
scanf("%d",&item);
for(i=0;i<5;i++)
{ if(item==a[i])
{ flag=1; break;
}
}
if(flag==0)
printf("Element Not Found");
else
printf("\nElement Found at Position =%d",i);
}

5
Sardar sami (19f-es-91)
Dawood University of Engineering and Technology Data Structures and Algorithm

6
Sardar sami (19f-es-91)
Dawood University of Engineering and Technology Data Structures and Algorithm

Lab 03
Objective
Binary Search Algorithm
Task 01
Design a code and flowchart for Binary search algorithm .

#include <stdio.h>
int main()
{
int c, first, last, middle, n, search, array[100];
printf("Enter number of elements:\n");
scanf("%d",&n);
printf("Enter %d integers:\n", n);
for(c = 0; c < n; c++) {
scanf("%d",&array[c]);
}
printf("Enter the value to find:\n");
scanf("%d", &search);
first = 0; last= n -1; middle = (first+last)/2;
while(first <= last)
{
if (array[middle] < search)
first = middle + 1; else
if (array[middle] == search)
{
printf("%d is present at index %d.\n", search, middle+1);
break;
}
else last = middle -1;
middle = (first + last)/2;
}
if (first > last)
printf("Not found! %d is not present in the list.\n", search);
return 0;
}

7
Sardar sami (19f-es-91)
Dawood University of Engineering and Technology Data Structures and Algorithm

8
Sardar sami (19f-es-91)
Dawood University of Engineering and Technology Data Structures and Algorithm

Lab 04
Objective
To Search An Element In A Unsorted Array Using The Bubble Sort Algorithm.
Task 1
Write a program and draw flowchart to sort the following numbers using the above algorithm.
44, 33, 11, 55, 77, 90, 40, 60, 99, 22, 88, 66

#include <stdio.h>
void bubbleSort(int array[], int size) {
int (step = 0; step < size-1; ++step)
{ for (inti = 0; i< size-step-1; ++i)
{ if (array[i] > array[i + 1])
{
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
}}}}
void printArray(int array[], int size)
{ for (inti = 0; i< size; ++i)
{
printf("%d ", array[i]);}
printf("\n");
}
int main()
{
int data[] = {44, 33, 11, 55, 77, 90, 40, 60, 99, 22, 88, 66};
int size = sizeof(data)/sizeof(data[0]);
bubbleSort(data, size);
printf("Sorted Array in Ascending Order:\n");
printArray(data, size);
}

9
Sardar sami (19f-es-91)
Dawood University of Engineering and Technology Data Structures and Algorithm

10
Sardar sami (19f-es-91)
Dawood University of Engineering and Technology Data Structures and Algorithm

Lab # 5
Objective
To Sort Arrays Using SELECTION SORT.
Task 01
Write the C++ code to sort the following numbers using Selection sort algorithms.
22, 20, 38, 55, 45, 33, 50, 66, 50

#include<stdio.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void selectionSort(int array[], int size) {
for (int step = 0; step < size - 1; step++) {
int min_idx = step;
for (int i = step + 1; i< size; i++) {
if (array[i] < array[min_idx])
min_idx = i;
}
swap(&array[min_idx], &array[step]);
}
}
void printArray(int array[], int size) {
for (inti = 0; i< size; ++i) {
printf("%d ", array[i]);
}
printf("\n");
}

int main() {
int data[] = {22,20,38,55,45,33,50,66,50};
int size = sizeof(data) / sizeof(data[0]);
selectionSort(data, size);
printf("Sorted array in Ascending Order:\n");
printArray(data, size);
}

11
Sardar sami (19f-es-91)
Dawood University of Engineering and Technology Data Structures and Algorithm

12
Sardar sami (19f-es-91)
Dawood University of Engineering and Technology Data Structures and Algorithm

Lab 6
Objective
To Search an Element In A Unsorted Array Using The Merge Sort Algorithm.
Task
Write a program to sort the following numbers using the above algorithm.
40, 23, 81, 65, 70, 97, 40, 64, 29, 92, 86, 66

#include <stdio.h>
void merge(int arr[], int p, int q, int r) {
int n1 = q - p + 1;
int n2 = r - q;
int L[n1], M[n2];
for (inti = 0; i< n1; i++)
L[i] = arr[p + i];
for (int j = 0; j < n2; j++)
M[j] = arr[q + 1 + j];

13
Sardar sami (19f-es-91)
Dawood University of Engineering and Technology Data Structures and Algorithm

inti, j, k;
i = 0; j = 0;k = p;
while (i< n1 && j < n2) {
if (L[i] <= M[j]) {
arr[k] = L[i];i++;
} else {
arr[k] = M[j]; j++;
}
k++;
}
while (i< n1) {
arr[k] = L[i]; i++; k++;
} while (j < n2) {
arr[k] = M[j];j++; k++;
}
}
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
void printArray(int arr[], int size) {
for (inti = 0; i< size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = { 40, 23, 81, 65, 70, 97, 40, 64, 29, 92, 86, 66};
int size = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, size - 1);
printf("Sorted array: \n");
printArray(arr, size);
}

14
Sardar sami (19f-es-91)
Dawood University of Engineering and Technology Data Structures and Algorithm

15
Sardar sami (19f-es-91)