Обзор стандартной библиотеки

МИНОБРНАУКИ РОССИИ

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ

ЭЛЕКТРОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

«ЛЭТИ» ИМ. В.И. УЛЬЯНОВА (ЛЕНИНА)

Кафедра МО ЭВМ

ОТЧЕТ

по лабораторной работе №1

по дисциплине «Программирование»

Тема: Обзор стандартной библиотеки

Санкт-Петербург

2022

1. Цель работы.

Изучить и применить на практике функции из стандартной библиотеки языка Си.

1. Задание.

Напишите программу, на вход которой подается массив целых чисел длины 1000, при этом число 0 либо встречается один раз, либо не встречается.

Программа должна совершать следующие действия:

• отсортировать массив, используя алгоритм быстрой сортировки (см.функции стандартной библиотеки)
• определить, присутствует ли в массиве число 0, используя алгоритм двоичного поиска (для реализации алгоритма двоичного поиска используйте функцию стандартной библиотеки)
• посчитать время, за которое совершен поиск числа 0, используя при этом функцию стандартной библиотеки
• вывести строку "exists", если ноль в массиве есть и "doesn't exist" в противном случае
• вывести время, за которое был совершен двоичный поиск
• определить, присутствует ли в массиве число 0, используя перебор всех чисел массива
• посчитать время, за которое совершен поиск числа 0 перебором, используя при этом функцию стандартной библиотеки
• вывести строку "exists", если 0 в массиве есть и "doesn't exist" в противном случае
• вывести время, за которое была совершен поиск перебором.

1. Выполнение работы.

Вначале работы импортируются библиотеки stdio.h, stdlib.h и time.h. Задается максимальный размер массива N = 1000. Далее создаётся массив a[N], отвечающий за хранение входных данных. Считываются данные из входного потока stdin. Для сортировки используется функция qsort(a, N, sizeof(int), cmp) из стандартной библиотеки stdlib.h, получающая на вход исходный массив, его длину, размер типа данных элементов и функцию cmp, сравнивающую их. После сортировки вызываются функции binarySearch и manualSearch.

1. Описание функции binarySearch.

Создаются две переменные: timer типа time_t и seconds типа double. Далее в timer записывается текущее время и вызывается функция bsearch(&key, a, N, sizeof(int), cmp) результатом которой будет Null, если элемент не найден, или указатель на найденный элемент. Если 0 найден в массиве, то выводится «exist», иначе «doesn’t exist». Далее в переменную second записывается время работы двоичного поиска и выводится на экран.

Описание функции manualSearch.

Функция manualSearch работает в точности как binarySearch, только вместо двоичного поиска используется обход массива с помощью цикла.