Библиотека функций поиска в массивах

/*

Функции поиска в массивах

*/

 

#pragma once

 

#include "stdafx.h"

 

//

// Прототипы функций

//

 

int Find1_1(int A[], int n, int Val);

// Последовательный поиск значения Val в массиве А из n целых значений (вариант 1)

// Возвращает индекс найденного элемента или -1, если искомое значение отсутствует

 

int Find1_2(int A[], int n, int Val);

// Последовательный поиск значения Val в массиве А из n целых значений (вариант 2)

// Возвращает индекс найденного элемента или -1, если искомое значение отсутствует

 

int Find2(int A[], int n, int Val);

// Бинарный поиск значения Val в отсортированном по возрастанию массиве А из n целых значений

// Возвращает индекс найденного элемента или -1, если искомое значение отсутствует

 

//

// Реализация

//

 

int Find1_1(int A[], int n, int Val)

// Последовательный поиск значения Val в массиве А из n целых значений (вариант 1)

{

int i = 0;

while (i < n)

{

if (A[i] == Val)

return i;

++i;

}

return -1;

}

 

int Find1_2(int A[], int n, int Val)

// Последовательный поиск значения Val в массиве А из n целых значений (вариант 2)

// Возвращает индекс найденного элемента или -1, если искомое значение отсутствует

{

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

if (A[i] == Val)

return i;

return -1;

}

 

int Find2(int A[], int n, int Val)

// Бинарный поиск значения Val в отсортированном по возрастанию массиве А из n целых значений

// Возвращает индекс найденного элемента или -1, если искомое значение отсутствует

{

if ((Val < A[0]) || (Val > A[n - 1])) // Отсеиваем заведомо не входящие в массив значения

return -1;

int a = 0, b = n - 1, c;

while (b >= a)

{

c = (a + b) / 2; // Находим в интервале [а, b] индекс срединного элемента - с

if (Val > A[c]) // Искомое значение справа от с

a = c + 1; // Заменяем левую границу интервала поиска

else

if (Val < A[c]) // Искомое значение слева от с

b = c - 1; // Заменяем правую границу интервала поиска

else // Val == A[c]

return c; // Индекс искомого элемента - с

}

return -1;

}

 

Программа для проверки функций поиска в массивах:

 

/*

Find.cpp: определяет точку входа для консольного приложения.

Заголовочные файлы arr_common.h, arr_sort.h и my_rand.h должны находиться в папке этого проекта, либо путь к ним должен быть указан в настройках параметров проекта:

Меню среды: Проект – Свойства – Свойства конфигурации – Каталоги VC++ - Каталоги включения и добавляем здесь путь к нашим заголовочным файлам

*/

 

#include "stdafx.h"

#include <iostream>

#include <conio.h>

#include "arr_common.h"

#include "arr_sort.h"

#include "arr_find.h"

using namespace std;

 

 

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(0, "");

const int N = 1000;

int M[N], V, Ind;

setlocale(0, "");

RandInit(); // Инициализируем датчик случайных чисел (#include "my_rand.h")

cout << " Проверка алгоритма бинарного поиска.\n";

cout << " ------------------------------------\n";

RandMakeArr(M, N, 1, 1000); // Заполняем массив случайными чиселами (#include "my_rand.h")

Sort2(M, N, 1); // Сортируем массив М из N элементов (#include "arr_sort.h")

ArrOut(M, N); // Выводим отсортированный массив на экран

for (char b = '1'; b!= 27; cout << "\n\t\t\tПродолжим? (нет - Esc)",

b = _getch(), cout << endl)

{

cout << "\nКакое значение надо найти? ";

cin >> V; // Вводим значение для поиска

Ind = Find2(M, N, V); // Поиск V в массиве М из N элементов бинарным поиском

if (Ind!= -1)

cout << "Индекс значения " << V << " равен " << Ind << endl;

else

cout << "Значение " << V << " не найдено" << endl;

}

return 0;

}

 

 

Приложение 2. Функции стандартного ввода/вывода в стиле C (printf, scanf)

Автор: Бардин П.Б.

Введение

Стандартная библиотека C/C++ включает ряд функций для чтения и записи на консоли (клавиатура и монитор). Эти функции читают и пишут данные, как простой поток символов.

Понятие потока (stream), использованное в программировании, тесно связано с обычным, бытовым пониманием этого слова. Поток ввода можно сравнить с трубой, по которой вода (информация) поступает в бассейн (память компьютера), поток вывода - с трубой, по которой вода выходит из бассейна. Важной особенностью этой трубы является то, что в каждый момент времени данные могут двигаться только в одном направлении. Даже если одна и та же труба используется для ввода и вывода, это не может происходить одновременно: для переключения направления потока его нужно остановить, выполнить некие действия и лишь затем направить поток в обратном направлении. Другой особенностью потока является то, что он почти никогда не иссякает. Иногда он высыхает, но этот период не может быть долгим, если система функционирует нормально.