ВУЗ:
Составители:
Рубрика:
Устройство массивов и файлов привело к появлению часто возникающих задач в процессе хранения
информации с их помощью. При использовании массивов такой задачей является задача сортировки
хранимой информации, а при использовании файлов – задача поиска информации.
При хранении информации в массивах, используется три базовых алгоритма сортировки: метод
простых вставок, метод обменов и метод выбора.
Сортировка простыми вставками. Смысл алгоритма состоит в последовательном переносе элемен-
тов упорядочиваемого массива в уже упорядоченный массив на положенные им места.
Для осуществления сортировки одномерного массива А нужен второй массив B такого же размера.
Первый элемент массива А переносится в массив В без условий. Новая последовательность считается
упорядоченной. Каждый следующий элемент массива А последовательно сравнивается с элементами
массива В начиная с первого его элемента. В этом процессе устанавливается место для вставки нового
элемента в массив В. Элементы, расположенные справа от указанной позиции, сдвигаются на одну по-
зицию вправо. Новый элемент из массива А вставляется на освободившееся место.
Сортировка обменами (метод "пузырька"). Метод состоит в последовательном сравнении соседних
элементов в массиве А и замене их местами, если не выполняется требуемое условие сортировки. При
выполнении этой операции над всеми элементами массива больший из них (при сортировке по возрас-
танию) займет последнюю позицию. При многократном выполнении указанных действий соответст-
вующие элементы займут места с номерами n-1, n-2, n-3 и так далее, а массив будет упорядочен.
Усовершенствованный метод обмена с изменением направления предполагает найденный элемент,
который не удовлетворяет поставленному условию сортировки, сдвигать в направлении противополож-
ном направлению сортировки до тех пор, пока он не удовлетворит условию решения задачи.
Метод выбора. Сортировка выбором требует найти среди рассматриваемых элементов наибольший
(наименьший) и осуществить обмен его с последним элементом в массиве. Далее уменьшаем число рас-
сматриваемых элементов в массиве на один, так как последний элемент в массиве уже отсортирован.
Повторяя эти действия над наборами элементов массива уменьшающейся длины, мы получаем упоря-
доченную последовательность.
Для организации поиска информации в файле можно использовать два алгоритма: последователь-
ного перебора и бинарного поиска.
Для поиска информации с помощью алгоритма бинарного поиска, информация в файле должна
быть упорядочена по некоторому свойству. Алгоритм состоит в последовательном сравнении ключево-
го значения искомой информации и информации, находящейся в файле в центре рассматриваемого диа-
пазона с последовательным исключением из рассмотрения ненужной половины.
12 ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ
При программировании реальных задач очень часто программисты сталкиваются с проблемой ор-
ганизации гибкого подхода к объемам обрабатываемой информации, которая тесно взаимосвязана с за-
дачей создания эффективных программ. Эта проблема состоит в том, что во многих задачах нельзя за-
ранее предугадать точное количество данных, а следовательно, и количество переменных для их хране-
ния. Малоэффективным здесь оказывается и применение переменных сложных типов данных, так как в
момент компиляции в программе четко должны быть указаны размеры всех массивов, структур и
объединений. Поэтому при использовании переменных сложных типов данных стараются задать им
такие размеры, которых, исходя из здравого смысла, программе хватит всегда. С одной стороны, это
может повлечь за собой захват программой больших объемов оперативной памяти ЭВМ, которую
программа может и не использовать в данный конкретный момент, а держать "на всякий случай", что
негативно скажется на эффективности функционирования всей системы в целом. С другой стороны,
нельзя дать гарантию, что в процессе эксплуатации программы не возникнет ситуация, когда программе
не хватит выделенной оперативной памяти и она просто станет непригодной для решения задачи.
Выходом в этой ситуации стало создание целого класса динамических структур данных, которые
обладают всеми свойствами типов данных, но исходя из сложности их воплощения отдельно, они реа-
лизуются на базе уже существующих типов данных. Главной их отличительной особенностью является
возможность быстрого и гибкого видоизменения в процессе работы программы. Наиболее удобной ба-
зой для их построения стали структуры. Оказалось, что возможность использования в составе структур
Страницы
- « первая
- ‹ предыдущая
- …
- 31
- 32
- 33
- 34
- 35
- …
- следующая ›
- последняя »
