4.3. МЕТОДЫ ПОСТРОЕНИЯ АЛГОРИТМОВ, ОРИЕНТИРОВАННЫЕ НА СТРУКТУРЫ ДАННЫХ
Часто на технологию разработки алгоритма влияют структуры данных, используемых в программе. Удачный выбор структур данных позволяет зачастую легко строить эффективные алгоритмы. Методы программирования, в которых такое влияние доминирует, называют методами, ориентированными на структуры данных.
Рассмотрим некоторые классы задач, где полезны такие структуры как связные списки, очереди, стеки, деревья.Сортировка массивов данных, т.е. расположение их элементов в определенном порядке, являясь одной из важнейших прикладных задач при эксплуатации информационных систем, требует больших временных затрат и ресурсов памяти ЭВМ. Легко представить возникающие трудности, когда в массиве данных происходят удаления и внесения новых записей. Обычные подходы заставят нас осуществлять заново сортировку измененного массива с физическими перестановками записей согласно известным процедурам упорядочивания.
Попробуем проблему решить с помощью линейного связанного списка. Массив преобразуют в двумерный, в котором по второму индексу (целые неотрицательные числа, называемые связями или указателями) располагают номера элементов массива.
Info
| Link
|
|
1 Петров 2 Смирнов 3 Алексеев
| 3 4 1
| Линейный связанный список - это конечный набор пар, состоящих из информационной части (Info) и указующей части (Link).
|
N Кузнецов
| 2
|
|
Линейные связанные списки являются эффективной структурой данных для моделирования ситуаций, в которых подвергаются изменениям упорядоченные массивы элементов данных. Особенно важно их использование при процедурах внесения или удаления элементов из середины массива.
Когда модификации касаются лишь начала или/и конца, то необходимость в связанных списках отпадает, и становится достаточным использование одномерного исходного массива. Здесь на помощь приходят стеки и очереди.Пусть, например, задано арифметическое выражение. Требуется определить, правильно ли расставлены в выражении скобки.
Для решения подобных задач используют стековую память (называемую просто «стек»). Стек представляет последовательность данных и имеет лишь одну границу для добавления и удаления элементов. В нашем случае в стек помещаются и удаляются скобки.
Первым необходимым условием правильности расстановок скобок является совпадение количества левых и правых скобок. Такой контроль легко осуществить введя счетчик top, который при просмотре выражения и обнаружении левой скобки (допустим, что имеем только круглые скобки '(' ) увеличивается на +1. Если на очередном месте встретилась правая скобка, то значение счетчика уменьшается на 1. Тогда правильность расстановки определяется по итоговому значению top.
Программа 36
program skobkal; (*проверка скобок по количеству*)
var top, i, n: integer; slovo: string[100]; skob: string[100];
begin
write('введи арифметическое выражение: ');
readln(slovo); n:length(slovo);
top:=0; skob:=''; i:=l;
while (i
Еще по теме 4.3. МЕТОДЫ ПОСТРОЕНИЯ АЛГОРИТМОВ, ОРИЕНТИРОВАННЫЕ НА СТРУКТУРЫ ДАННЫХ:
- 3.3.4. Методы обработки и анализа данных
- 3.3.2. Обоснование методов сбора эмпирических данных
- I. 3. ОБЩАЯ ХАРАКТЕРИСТИКА СИСТЕМНЫХ ОПИСАНИЙ И МЕТОДОВ ИХ ПОСТРОЕНИЯ
- I. 3. 2. Методы построения системных описаний.
- 13.1. Понятие, содержание, структура допроса (опроса) по методу когнитивного интервью
- Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
- Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
- ТЕСТ КРИТЕРИАЛЬНО - ОРИЕНТИРОВАННЫЙ
- АЛГОРИТМ
- АЛГОРИТМ УДАЧИ
- Г.С.Иванова, Т.Н.Ничушкина, Е.К.Пугачев. Объектно- ориентированное программирование, 2001