<<
>>

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

<< | >>
Источник: А.В.Могилев, Н.И.Пак, Е.К.Хённер. Информатика. 2016

Еще по теме 4.3. МЕТОДЫ ПОСТРОЕНИЯ АЛГОРИТМОВ, ОРИЕНТИРОВАННЫЕ НА СТРУКТУРЫ ДАННЫХ:

  1. 3.3.4. Методы обработки и анализа данных
  2. 3.3.2. Обоснование методов сбора эмпирических данных
  3. I. 3. ОБЩАЯ ХАРАКТЕРИСТИКА СИСТЕМНЫХ ОПИСАНИЙ И МЕТОДОВ ИХ ПОСТРОЕНИЯ
  4. I. 3. 2. Методы построения системных описаний.
  5. 13.1. Понятие, содержание, структура допроса (опроса) по методу когнитивного интервью
  6. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  7. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  8. ТЕСТ КРИТЕРИАЛЬНО - ОРИЕНТИРОВАННЫЙ
  9. АЛГОРИТМ
  10. АЛГОРИТМ УДАЧИ
  11. Г.С.Иванова, Т.Н.Ничушкина, Е.К.Пугачев. Объектно- ориентированное программирование, 2001