Алгоритмы и структуры данных
Одна из основ программирования
В конце концов, только знание инструментов и технологий обеспечит правильное решение поставленной задачи, и только определенный уровень опыта обеспечит устойчиво профессиональные результаты.Поиск
Ничто не сравнится с массивом, если нам нужно хранить статические табличные данные. Инициализация во время компиляции делает задачу конструирования таких массивов простой и легкой.Сортировка
Двоичный поиск работает только в том случае, если элементы отсортированы. Если по одному и тому же набору данных планируется неоднократный повторный поиск, то выгоднее один раз отсортировать данные, а затем использовать двоичный поиск.Библиотеки
В стандартные библиотеки языков С и C++ входят функции сортировки, которые устойчивы к неблагоприятным входным данным и настроены на предельно быструю работу. | Библиотечные функции написаны так, что они могут сортировать данные любого типа, но мы в свою очередь должны адаптироваться к их интерфейсу, что может быть несколько сложнее, чем в рассмотренном выше примере.Быстрая сортировка на языке Java
В Java ситуация другая. В ранних версиях не было стандартной функции сортировки, поэтому приходилось писать собственную. В последних версиях появилась такая функция, работающая с классами, реализующими интерфейс Comparable, поэтому теперь мы можем просить библиотеку сортировать то, что нам потребуется."О большое"
Мы описывали трудоемкость алгоритма в зависимости от n, количества входных элементов. Поиск в неотсортированных данных занимает время, пропорциональное n; при использовании двоичного поиска по отсортированным данным время будет пропорционально log n. Время сортировки пропорционально n2 или n logn.Динамически расширяемые массивы
Массивы, использованные в нескольких предыдущих разделах, были статическими, их размер и содержимое задавались во время компиляции. Если потребовать, чтобы некоторую таблицу слов или символов HTML можно было изменять во время выполнения, то хэш-таблица была бы для этой цели более подходящей структурой.Списки
По своей встречаемости в типичных программах списки занимают второе место после массивов. Многие языки имеют встроенные типы списков, некоторые, такие как Lisp, даже построены на них, но в языке С мы должны конструировать их самостоятельно.Деревья
Дерево – иерархическая структура данных, хранящая набор элементов. Каждый элемент имеет значение и может указывать на ноль или более других элементов. На каждый элемент указывает только один другой элемент. Единственным исключением является корень дерева, на который не указывает ни один элемент.Хэш-таблицы
Хэш-таблицы (hash tables) – одно из величайших изобретений информатики. Сочетание массивов и списков с небольшой добавкой математики позволило создать эффективную структуру для хранения и* получения динамических данных.Заключение. Дополнительная литература.
При выборе алгоритма нужно сделать несколько шагов. Во-первых, следует изучить существующие алгоритмы и структуры данных. Подумайте, какой объем данных может обработать программа. Если задача предполагает скромные размеры данных, то выбирайте простые технологии;