Динамические структуры

В вычислительной машине программы обычно оперируют с табли­цами информации. В большинстве случаев это не просто аморфные массы числовых величин: в таблицах присутствуют важные струк­турные отношения между элементами данных. В простейшей форме таблица может быть линейным списком элементов. Тогда присущие ей структурные свойства содержат в себе ответы на такие вопросы, как: "Какой элемент является первым в списке? какой — последним? какой элемент предшествует данному или следует за данным?" Можно много говорить о структуре даже в этом совершенно очевидном случае.

В более сложных ситуациях таблица может быть двумерным массивом (т. е. матрицей, имеющей структуру строк и столбцов), либо может быть n -мерным массивом при весьма больших значениях n, либо она может иметь структуру дерева, представляющего отношения иерархии или ветвления, либо это может быть сложная многосвязная структура с огром­ным множеством взаимных соединений, такая, например, которую можно найти в человеческом мозгу. Чтобы правильно использовать машину, важно добиться хороше­го понимания структурных отношений, существующих между дан­ными, способов представления таких структур в машине и методов работы с ними.

В настоящей главе кратко рассматриваются наиболее важные факты, касающиеся информационных структур:

- статические и ди­намические свойства разного рода структур;

- средства распределения памяти и представления структурных данных;

- эффективные алгоритмы для создания, изменения, разрушения структурной ин­формации и доступа к ней.

Структуры будут нас интересовать не только с точки зрения внешнего, но и их внутреннего представления в машине. Мы увидим, что нет ничего мистического или трудного в методах работы со сложными структурами; эти методы являются важной частью репертуара каждого программиста, и он легко может ими воспользоваться, программируя на различных языках. Обычно в данных присутствует значительно больше структурной информации, чем мы хотим непосредственно представить в маши­не. Можно себе представить, что такая структурная информация была бы уместна в некоторых машинных приложениях, но, очевидно, нам никогда не придется в каждой из ситуаций хранить о структуре все, что существует. Из сказанного ясно, что в каждом конкретном случае мы должны решить, насколько подробно в наших данных должна быть пред­ставлена структура и как организовать доступ к любой части ин­формации. Чтобы принять такое решение, необходимо знать, какие операции будут выполняться с данными. Вот почему в этой главе в связи с каждой задачей мы будем рассматривать не только струк­туру данных, но и класс операций, которые выполняются с этими данными; разработка машинного представления в равной мере определяется требуемыми функциями от данных и присущими им свойствами. Вообще в задачах прием проектирования такое выделение "функции" наравне с "формой" является основополагающим.

Дата добавления: 2014-01-11