В настоящее время признанным фактом является то, что успех программ во многом зависит от системного и научного подхода к их построению, особенно это очевидно в случае больших программ со сложными данными. Поэтому методы программирования включают в себя и все варианты структурирования данных. В конечном счете, программы представляют собой конкретные формулировки абстрактных алгоритмов, основанные на определенных представлениях и структурах данных. Выяснилось, что решения о структурировании данных нельзя принимать без знания алгоритмов, применяемых к этим данным, и наоборот, выбор алгоритмов существенным образом зависит от структуры данных. Следовательно, строение программ и структуры данных неразрывно связаны между собой.
В пособии изложены структуры данных и алгоритмы, которые являются основой современного программирования. Для описания и реализации алгоритмов были использованы абстрактные типы данных, являющиеся удобным инструментом при разработке программ независимо от применяемого языка программирования. Для представления алгоритмов и структур данных был выбран язык Delphi, что объясняется его следующими особенностями:
|
|
- компактностью, делающей язык достаточно несложным для изучения;
- возможностью отражать фундаментальные концепции алгоритмов в легко воспринимаемой форме;
- способностью четко реализовывать идеи структурного программирования и осуществлять переход к объектно-ориентированному программированию.
В пособии рассматриваются динамические структуры данных, а также применяемые к ним алгоритмы. Работа состоит из семи частей, посвященных основным линейным и нелинейным структурам данных.
В разделах с первого по четвертый рассматриваются такие структуры данных, как списки, очереди и стеки, их разновидности и выполняемые операции. Предложен способ построения словарей с реализацией быстрого доступа к данным на основе их открытого хеширования. Рассмотрены три формы записи арифметических выражений, а также их преобразования на базе стека.
В разделах с пятого по седьмой рассмотрены структуры данных в виде деревьев и ориентированных графов. Выполнены три основных обхода бинарного дерева, введено понятие бинарного дерева поиска и показаны основные операции с данными на нем. Определено прошитое бинарное дерево, методы его прошивки и особенности выполнения операций с данными. Введена терминология ориентированных графов и способы их представления. Приведены алгоритмы решения базовых задач на ориентированных графах: поиск кратчайшего пути, поиск всех путей, центр графа.
В конце каждого раздела предложено задание для лабораторной работы, позволяющей студентам закрепить теоретические знания и получить практические навыки по изучаемой теме.