русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Линейный поиск


Дата добавления: 2013-12-23; просмотров: 3086; Нарушение авторских прав


Поиск

Поиск и Сортировка

Задачи поиска и сортировки возникают в самых разных контекстах. Рассмотрим задачу поиска в следующей постановке. Дан массив Items c элементами типа (класса) T и элемент pattern типа T, называемый образцом. Необходимо определить, встречается ли образец в массиве и, если да, определить индекс его вхождения.

Задача сортировки состоит в том, чтобы отсортировать массив Items. Предполагается, что тип T является упорядоченным типом, так что его элементы можно сравнивать. Задачу можно конкретизировать, полагая, например, что T - это тип string, и рассматривать поиск и сортировку строковых массивов. Поскольку алгоритмы поиска и сортировки практически не зависят от типа T, то отложим конкретизацию типа настолько, насколько это возможно.

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

Алгоритм линейного поиска предельно ясен. В цикле по числу элементов сравнивается очередной элемент массива с образцом. При нахождении элемента, совпадающего с образцом, поиск прекращается. Если цикл завершается без нахождения совпадений, то это означает, что в массиве нет искомого элемента. Время работы такого алгоритма линейно. В худшем случае придется сравнить образец со всеми элементами, в лучшем - с одним, в среднем - число сравнений равно n/2, где n - число элементов массива. У линейного поиска есть один недостаток: если образец не присутствует в массиве, то без принятия предохранительных мер поиск может выйти за границы массива, вследствие чего может возникнуть исключительная ситуация. В классическом варианте линейного поиска приходится на каждом шаге дополнительно проверять корректность значения текущего индекса.



Чтобы эта простая задача смотрелась интереснее, рассмотрим параметризованный алгоритм с параметром T, задающим тип элементов, и его реализацию на языке C#. Построим универсальный класс (класс с родовыми параметрами):

public class Service<T> where T:IComparable<T>{}

Класс Service имеет параметр T, на который наложено ограничение - класс T должен быть наследником интерфейса IComparable, следовательно, должен реализовать метод CompareTo этого интерфейса. Содержательно это означает, что T является упорядоченным классом.

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

/// <summary> /// Линейный поиск образца в массиве /// </summary> /// <param name="massiv">искомый массив</param> /// <param name="pattern">образец поиска</param> /// <returns> /// индекс первого элемента, совпадающего с образцом /// или -1, если образец не встречается в массиве /// </returns> public static int SearchPattern(T[] massiv, T pattern) { for (int i = 0; i < massiv.Length; i++) if (massiv[i].CompareTo(pattern)==0) return (i); return (-1); } /// <summary> /// Вариация линейного поиска образца в массиве /// </summary> /// <param name="massiv">искомый массив</param> /// <param name="pattern">образец поиска</param> /// <returns> /// индекс первого элемента, совпадающего с образцом /// или -1, если образец не встречается в массиве /// </returns> public static int SearchPattern1(T[] massiv, T pattern) { int i = 0; while((i<massiv.Length)&& (massiv[i].CompareTo(pattern)!=0)) i++; if (i == massiv.Length) return (-1); else return (i); }

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



<== предыдущая лекция | следующая лекция ==>
Проекты | Бинарный поиск


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Полезен материал? Поделись:

Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.001 сек.