Методические указания. Поиск данных в массиве

Поиск данных в массиве

Защита от "дурака" спасает только от неизобретательного дурака

Закон Мерфи

Цель работы – освоить обработку числового массива, разработку собственных функций и включение в проект дополнительных файлов (4 час.).

Задание. Разработайте алгоритм и программу в соответствии с приведенными ниже методическими указаниями, выполните отладку и тестирование разработанной программы.

Шаг 1. Генерация каркаса приложения.

С помощью мастера ИС MVS создайте консольное приложение и включите в него поддержку библиотеки MFC (как и в работе «Разработка типового консольного приложения»).

Шаг 2. Включение в проект дополнительного файла.

Так как далее в этой работе предполагается разрабатывать собственные функции, то имеет смысл поместить их в отдельный файл, который в дальнейшем можно будет легко использовать в других проектах путем его простого добавления в проект. В таких файлах программист может собирать свои собственные функции, используемые в разных проектах. Из соображений удобства принято создавать два файла: заголовочный файл (.h) и файл реализации (.cpp). Этим файлам удобно дать одинаковые имена с тем, чтобы никого не запутывать. В заголовочный файл принято помещать прототипы функций и, возможно, другие описания, а в файл реализации – определения функций.

Замечание. При использовании классов в заголовочный файл принято помещать описание класса, а в файл реализации – реализацию методов классов.

Для добавления в проект дополнительного файла проделайте следующие действия.

Выполните команду ProjectÞAdd New Item, в появившемся окне в дереве Categories выберите Code, на панели Templates выберите Header File(.h), задайте в поле File Name имя файла, например MyLib. Перед нажатием кнопки Add убедитесь в том, что в поле Location указано имя каталога с Вашим проектом. Мастер MVS создаст пустой заголовочный файл mylib.h и включит его в проект, о чем будет свидетельствовать появление имени файла в ветви дерева Header Files на вкладке Solution рабочего пространства.

Аналогичным образом добавьте в проект файл mylib.cpp, выбрав на панели Templates элемент C++ File(.cpp). Как и в случае с заголовочным файлом, файл реализации mylib.cpp должен появиться в ветви дерева Source Files на вкладке Solution рабочего пространства.

Шаг 3. Подключение созданных дополнительных файлов к другим файлам проекта.

Хотя созданный на предыдущем шаге заголовочный файл и файл реализации и включены в проект, для фактического их использования надо с помощью директивы препроцессора include подключить заголовочный к тому файлу (файлам), где будут вызываться разрабатываемые функции. В данном случае необходимо добавить директиву препроцессора

#include "mylib.h"

в начало файла.cpp (следом за уже имеющимися там директивами include), имя которого совпадает с именем проекта. Для справки: именно в этом файле находится главная функция _tmain().

Еще одно необходимое действие на этом этапе: в начало файла реализации mylib.cpp добавьте ту же директиву

#include "mylib.h"

Для того чтобы минимизировать время компиляции программы, полезно сохранить возможность использования так называемых предварительно откомпилированных заголовочных файлов (precompiled headers files). Для этого убедитесь в том, что в ИС сделаны соответствующие установки. Выполните команду ProjectÞ<имя проекта> Properties (Alt+F7), в появившемся окне в левой панели выберите опцию Configuration Properties|C/C++|Precompiled Header и убедитесь в том, что в правой панели выбрано значение Use Precompiled Header (/Yu) (рис. 1).

Рис. 1. Установки проекта

Кроме того, в самое что ни на есть начало файла MyLib.cpp добавьте директиву #include "stdafx.h". А если этого не сделать? При попытке построения проекта будем получать сообщение об ошибке

fatal error C1010: unexpected end of file while looking for precompiled header. Did you forget to add '#include "stdafx.h"' to your source?

На этом этапе приложение должно строиться и выполняться, хотя оно еще ничего нового не делает по сравнению с изначально сгенерированной мастером программой.

Шаг 4. Разработка собственных функций генерации и вывода данных.

В качестве иллюстрации разработаем функцию, которая будет генерировать массив псевдослучайных вещественных чисел.

В собственноручно созданный заголовочный файл mylib.h добавим прототип функции, которая будет заполнять переданный ей в качестве параметра массив псевдослучайными числами с плавающей запятой:

void GenArr(double Arr[],int Num);

В простейшем случае заголовочный файл может состоять из одной приведенной строки, однако обычно в любой заголовочный файл добавляют директивы препроцессора, препятствующие ошибочному повторному включению одного и того же файла в проект. Другими словами, содержимое заголовочного файла лучше сделать подобным следующему:

#pragma once

void GenArr(double Arr[],int Num);

Пока еще практически пустой файл mylib.cpp отредактируем, добавив в него определение функции GenArr() и необходимые для ее реализации заголовочные файлы. Содержимое файла mylib.cpp может быть, например, таким:

Дадим некоторые пояснения кода функции GenArr(). Функция srand() (аналог процедуры Randomize языка Pascal) инициализирует датчик псевдослучайных чисел, вследствие чего при каждом новом вызове функции GenArr() будет генерироваться новая последовательность псевдослучайных чисел. Достигается это благодаря тому, что в качестве параметра srand() получает значение, возвращаемое функцией time(). Функция time(), в свою очередь, возвращает число секунд, прошедшее после полуночи 1.01.1970г. до настоящего времени. Настоящее время предоставляет таймер операционной системы. Функция rand() возвращает целое псевдослучайное число из диапазона от 0 до RAND_MAX==0x7fff. Итак, какие возможные значения могут иметь элементы массива, из какого диапазона?

Наконец, где-то должен появиться вызов функции GenArr(). В нашем случае таким местом может быть главная функция _tmain(). Отредактируем код этой функции примерно так:

Заметьте, что для использования функции _ getch() необходимо включить в файл с главной функцией заголовочный файл conio.h. Кроме того, как Вы несомненно заметили, в главной функции вызывается функция PrintArr(). Откуда она возьмется? Вы ее напишите сами, включите в файл mylib.h ее прототип, а в файл mylib.cpp – ее реализацию. Назначение этой функции должно быть ясно из ее названия – вывод значений элементов массива на монитор в подобающем хаевца виде.

Кроме того, так программы пишут только туполобые, с позволения сказать, программисты, так как дотошный пользователь программы не имеет возможности задать фактическое число элементов массива на этапе выполнения программы. Вы, конечно, добавите в программу запрос фактического числа элементов массива и еще добавите цикл, чтобы за один запуск программы можно было выполнить несколько опытов по доказательству ее неработоспособности.

Шаг 5. Реализация алгоритмов поиска значений в массиве.

На этом шаге у нас имеется программа, которая генерирует массив псевдослучайных вещественных чисел и выводит его значения на монитор. Убедитесь в том, что при каждом новом запуске программы на выполнение получаются новые значения элементов массива.

Следующая задача, которую необходимо решить ­– это поиск заданного значения в массиве. Если значения элементов массива неупорядочены и в нем не встречаются одинаковые значения, то единственным выходом является простой линейный поиск, заключающийся в последовательном сравнении искомого значения со значениями элементов массива. Так как сравнение вещественных значений может преподнести сюрприз, то имеет смысл ввести некоторое малое число Eps>0.0 и считать, что искомое значение X найдено, если выражение (X>(A[i]-Eps)) && (X<(A[i]+Eps)) истинно (А[i] – значение элемента массива). Другими словами, линейный поиск заключается в последовательном переборе элементов массива до тех пор, пока не будет найдено искомое значение или не будет достигнут конец массива.

Если же элементы массива имеют произвольные значения, но упорядочены по величине, например, в порядке возрастания, то линейный поиск менее эффективен, чем, например, двоичный поиск.

Суть двоичного поиска, называемого еще дихотомическим поиском, состоит в следующем. Пусть в массиве A[] имеется N элементов и требуется найти среди них некоторое значение Х. На первом шаге значение центрального элемента массива A[] сравнивается с искомым значением Х. Если N нечетное, то значение центрального элемента массива есть A[N/2]. Если N четное, то в качестве значения центрального элемента массива можно принять значение выражения A[N/2-1]. Если значение центрального элемента массива совпадает с искомым значением Х (с точностью до заданного Eps), то задача решена и остается только вывести индекс и значение центрального элемента массива.

В противном случае возможны два варианта. Если значение Х больше значения центрального элемента массива, то, значит, оно может находиться только во второй половине массива, а в противном случае – только в первой. Тогда на следующем шаге в соответствующей половине массива вновь отыскивается центральный элемент и его значение сравнивается с искомым значением Х. Поиск центрального элемента массива в его половине выполняется так же, как и на первом шаге. Описанное деление массива пополам выполняется до тех пор, пока не будет найдено искомое значение или если на очередном шаге останется всего один элемент, т.е. делить уже будет нечего. Нетрудно заметить, что алгоритму присуща рекурсивность и этот факт можно использовать в реализации соответствующей функции поиска.

Если искомое значение в массиве отсутствует, но встречаются два таких смежных элемента массива, что (X>A[i]) && (X<A[i+1]), то поиск надо считать завершимся успешно. В этом случае в качестве результата поиска надо вывести значения A[i] и A[i+1].

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

· в массиве есть элемент с искомым значением и он находится на первом месте, на последнем или в средней части массива;

· в массиве нет элемента с искомым значением;

· искомое значение меньше значения первого элемента массива или больше последнего;

· число элементов массива N четное или нечетное, равное 0, 1 или 2

Алгоритмы поиска значений в массиве используются, в частности, при поиске значений функций, заданных в табличной форме.

Не забудьте реализовать интерфейс программы таким образом, чтобы разработанные вами алгоритмы (или поцупленные у соседней бригады) было удобно тестировать.

Дата добавления: 2014-12-26