Составители:
Рубрика:
В
ВЕДЕНИЕ
При обучении программированию особую трудность вызывает работа
с динамическими структурами данных. Как правило, такие структуры данных
являются "самодельными", и программист сам должен управлять их размеще-
нием в памяти машины: порождать, модифицировать и уничтожать их в про-
цессе выполнения программы. Все эти операции в конечном итоге реализуют-
ся на встроенных в вычислительную машину (ВМ) структурах данных (на
базе модели памяти данной ВМ). При этом встроенные структуры данных от-
ражают специфику организации ВМ (как совокупности программно-
аппаратных средств), в то время как "самодельные" структуры данных отра-
жают специфику решаемой задачи. Разрешение этого естественного противо-
речия может основываться на абстрагировании от деталей реализации дина-
мических структур данных, на определении этих структур данных через
базовые операции над ними с указанием их характерных свойств.
В рамках такого подхода в учебном пособии рассматриваются типовые
динамические структуры данных, используемые при решении многих про-
граммистских задач: списки, стеки и очереди, деревья и леса. Для каждой
структуры даются основные определения, формальная спецификация, пред-
ставление и реализация на языке Паскаль (в версии Турбо-Паскаль). Затем
следует набор упражнений для программирования.
При формулировке заданий для упражнений отражена лишь алго-
ритмическая суть задачи. Подразумевается, что должна быть написана про-
грамма, содержащая основной алгоритм (вычислительную часть) и модуль или
модули (в смысле языка Турбо-Паскаль) для работы с используемыми структу-
рами данных. Кроме того, программа должна выполнять тестирующие функции
по отношению к своей вычислительной части: должен быть предусмотрен
удобный при тестировании ввод исходных данных, вывод (визуализация) про-
межуточных данных и результатов в форме, удобной для анализа работы ос-
новного алгоритма. В случае динамических структур данных выполнение этих
не вполне формальных требований может составлять определенную проблему,
которую следует решать при консультации с преподавателем.
3
ВВЕДЕНИЕ
При обучении программированию особую трудность вызывает работа
с динамическими структурами данных. Как правило, такие структуры данных
являются "самодельными", и программист сам должен управлять их размеще-
нием в памяти машины: порождать, модифицировать и уничтожать их в про-
цессе выполнения программы. Все эти операции в конечном итоге реализуют-
ся на встроенных в вычислительную машину (ВМ) структурах данных (на
базе модели памяти данной ВМ). При этом встроенные структуры данных от-
ражают специфику организации ВМ (как совокупности программно-
аппаратных средств), в то время как "самодельные" структуры данных отра-
жают специфику решаемой задачи. Разрешение этого естественного противо-
речия может основываться на абстрагировании от деталей реализации дина-
мических структур данных, на определении этих структур данных через
базовые операции над ними с указанием их характерных свойств.
В рамках такого подхода в учебном пособии рассматриваются типовые
динамические структуры данных, используемые при решении многих про-
граммистских задач: списки, стеки и очереди, деревья и леса. Для каждой
структуры даются основные определения, формальная спецификация, пред-
ставление и реализация на языке Паскаль (в версии Турбо-Паскаль). Затем
следует набор упражнений для программирования.
При формулировке заданий для упражнений отражена лишь алго-
ритмическая суть задачи. Подразумевается, что должна быть написана про-
грамма, содержащая основной алгоритм (вычислительную часть) и модуль или
модули (в смысле языка Турбо-Паскаль) для работы с используемыми структу-
рами данных. Кроме того, программа должна выполнять тестирующие функции
по отношению к своей вычислительной части: должен быть предусмотрен
удобный при тестировании ввод исходных данных, вывод (визуализация) про-
межуточных данных и результатов в форме, удобной для анализа работы ос-
новного алгоритма. В случае динамических структур данных выполнение этих
не вполне формальных требований может составлять определенную проблему,
которую следует решать при консультации с преподавателем.
3
