глава

Структуры данных

Цели

Научиться создавать связные структуры данных, используя указатели, классы с самоадресацией и рекурсию.

Научиться динамически выделять и освобождать память для создания и уничтожения объектов со структурами данных.

Научиться создавать и манипулировать динамическими структурами данных, такими, как связные списки, очереди, стеки и бинарные деревья.

Понять работу различных приложений со связными структурами данных.

Понять, каким образом следует создавать многократно используемые структуры данных с помощью шаблонов классов, наследования и композиции.

Резюме Терминология Типичные ошибки программирования Хороший стиль программирования Советы по повышению эффективности Замечания по мобильности Упражнения для самопроверки Ответы на упражнения для самопроверки Упражнения Специальный раздел: создание вашего собственного компилятора

15.1. Введение

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

План

15.1. Введение

15.2. Классы с самоадресацией

15.3. Динамическое выделение памяти

15.4. Связные списки

15.5. Стеки

15.6. Очереди

15.7. Деревья

Мы обсудим каждый из этих основных типов структур данных и их применение в программах, создающих и манипулирующих этими структурами данных. Для создания и упаковки этих структур данных, для их многократного использования и сопровождения мы будем применять классы, шаблоны классов, механизм наследования и композицию.

Примеры этой главы являются практическими программами, которые вы можете использовать в курсах повышенной сложности и в промышленных приложениях. Эти программы являются особенно мощными благодаря использованию указателей. Упражнения данной главы включают обширный набор полезных приложений.

Мы воодушевляем вас на смелую попытку создать сложный проект, описанный в специальном разделе этой главы Создание вашего собственного компилятора . Вы постоянно пользуетесь компилятором для трансляции ваших программ, написанных на языке С-Н-, в машинный код и выполнения этих программ на вашем компьютере. А в этом проекте вы действительно построите ваш собственный компилятор. Он будет читать файл из операторов, записанных на элементарном, но тем не менее мощном языке высокого уровня, аналогичном ранним версиям популярного языка БЕЙСИК. Ваш компилятор будет транслировать эти операторы в файл инструкций машинного языка Простотрона (ЯМП), который вы изучали в специальном разделе главе 5 Создание вашего собственного компьютера . Ваша программа, моделирующая Простотрон, будет выполнять программу на ЯМП, созданную вашим же компилятором! Реализация этого проекта, интенсивно использующего объектно-ориентированный подход, даст вам замечательную возможность наилучшего использования всего того, что вы изучили в этой области. В этом специальном разделе мы пройдемся по спецификациям языка высокого уровня и рассмотрим алгоритмы, необходимые для преобразования каждого типа оператора на языке высокого уровня в язык машинных команд. Если вы отважитесь принять брошенный вам вызов, то вы можете внести множество различных новшеств как в компилятор, так и в программу, моделирующую Простотрон и используемую в упражнениях.

15.2. Классы с самоадресацией

Классы с самоадресацией содержат элемент указатель, который указывает на объект того же типа класса. Например, описание

class Node { public:

Node(int);

void setData(int) ;

int getDataO const;

void setNextPtr(const Node *);

const Node *getNextPtr() const; private:

int data;

Node *nextPtr;

определяет тип класса Node. Тип Node имеет два закрытых данных-элементов: целый элемент data и элемент указатель nextPtr. Элемент указатель nextPtr указывает на объект типа Node - объект того же типа, который здесь