ГЛАВА 2. ОЧЕРЕДИ, СТЕКИ, СВЯЗАННЫЕ СПИСКИ И ДЕРЕВЬЯ
Программы состоят из алгоритмов и структур данных. Хорошие программы используют преимущества их обоих. Выбор и разработка структуры данных столь же важна, как и разработка процедуры, ко- торая манипулирует ими. Организация информации и методы доступа к ней обычно определяются характером стоящей перед программистом задачи. Поэтому каждый программист должен иметь в своем "багаже" соответствующие методы представления и поиска данных, которые можно применить в каждой конкретной ситуации.
В действительности структуры данных в ЭВМ строятся на основе базовых типов данных, таких как "char", "integer", "real". На следующем уровне находятся массивы, представляющие собой наборы базовых типов данных. Затем идут записи, представляющие собой группы типов данных, доступ к которым осуществляется по одному из данных. а последнем уровне, когда уже не рассматриваются физичес- кие аспекты представления данных, внимание обращается на порядок, в котором данные хранятся и в котором делается их поиск. По су- ществу физические данные связаны с "машиной данных", которая уп- равляет способом доступа к информации в вашей программе. Имеется четыре такие "машины":
- очередь;- стек;
- связанный список;
- двоичное дерево.
Каждый метод используется при решении определенного класса задач. Каждый метод по существу является неким "устройством", ко- торое обеспечивает для заданной информации определенный способ хранения и при запросе выполняет определенные операции поиска данных. В каждом из этих методов используется две операции: доба- вить элемент и найти элемент /под элементом понимается некоторая информационная единица/. В этой главе будет показано, как эти ме- тоды можно использовать в ваших программах.
