10)Динамические структуры данных в с. Абстрактные типы данных.

Структуры одного типа можно объединять не только в массивы. Их можно связывать между собой, создавая так называемые динамические структуры данных. Связь между отдельными структурами может быть организована по-разному, и именно поэтому среди динамических данных выделяют списки, стеки, очереди, деревья, графы и др.

Для динамических данных память выделяется и освобождается в процессе выполнения программы, а не в момент ее запуска. Так, например, если в программе объявлен массив из 100 элементов, то при запуске программы резервируется память для всех ста элементов, даже если в процессе работы программы всего будут использованы первые 10 элементов массива. С другой стороны, при использовании в программе динамических типов память под них заранее не выделяется. Лишь когда поступают новые данные, вызывается специальная функция, которая выделяет память, куда эти данные записываются.

С

Данные Null

Данные лллооооолд ****

Данные *

писок – это последовательность структур, каждая из которых содержит ссылку, связывающую её с другой структурой. Объявление списка.

H ead

struct Node {

char word[40]; // область данных

int count;

Node *next; // ссылка на следующий узел

};

typedef Node *PNode; // тип данных: указатель на узел

Каждый элемент содержит также ссылку на следующий за ним элемент. У последнего в списке элемента поле ссылки содержит NULL. Чтобы не потерять список, мы должны где-то (в переменной) хранить адрес его первого узла – он называется «головой» списка. В программе надо объявить два новых типа данных – узел списка Node и указатель на него PNode. Узел представляет собой структуру, которая содержит три поля - строку, целое число и указатель на такой же узел

Стек является простейшей динамической структурой. Добавление элементов в стек и выборка из него выполняются из одного конца, называемого вершиной стека. Другие операции со стеком не определены. При выборке элемент исключается из стека.

Говорят, что стек реализует принцип обслуживания LIFO (last in — first out, последним пришел — первым обслужен). Кстати, сегмент стека назван так именно потому, что память под локальные переменные выделяется по принципу LIFO.

const int MAXSIZE = 100;

struct Stack {

char data[MAXSIZE];

int size;

};

Для работы со стеком надо определить, как выполняются две операции – добавление элемента на вершину стека (Push) и снятие элемента с вершины стека (Pop).

void Push ( Stack &S, char x )

{

if ( S.size == MAXSIZE ) {

printf ("Стек переполнен");

return;

}

S.data[S.size] = x;

S.size ++;

}

Поскольку нумерация элементов массива data начинается с нуля, надо сначала записать новый элемент в S.data[S.size], а затем увеличить размер стека.

char Pop ( Stack &S )

{

if ( S.size == 0 ) {

printf ("Стек пуст");

return char(255);

}

S.size --;

return S.data[S.size];

}

Функция Pop возвращает символ, «снятый» с вершины стека, при этом размер стека уменьшается на единицу.

Очередь — это динамическая структура данных, добавление элементов в которую выполняется в один конец, а выборка — из другого конца. Другие операции с очередью не определены. При выборке элемент исключается из очереди. Говорят, что очередь реализует принцип обслуживания FIFO (first in — first out, первым пришел — первым обслужен).

Объявление очереди:

const int MAXSIZE = 100;

struct Queue {

int data[MAXSIZE];

int size, head, tail;

};

Обратите внимание, что очередь Q передается в процедуру по ссылке, то есть, фактически передается адрес этой структуры в памяти.

int Pop ( Queue &Q )

{

int temp;

if ( Q.size == 0 ) {

printf ("Очередь пуста\n");

return 32767; // сигнал об ошибке

}

temp = Q.data[Q.head];

Q.head ++;

if ( Q.head >= MAXSIZE ) Q.head = 0;

Q.size --;

return temp;

}

Функция Pop возвращает число, полученное с начала очереди, при этом размер очереди уменьшается на единицу. Если стек пуст, функция возвращает число 32767 (предполагается, что оно не может находиться в очереди по условию задачи и сигнализирует об ошибке).

Реализация очереди с помощью списка

struct Node {

int data;

Node *next, *prev;

};

typedef Node *PNode;

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

Корень – это начальный узел дерева, в который не ведет ни одной дуги.

Вершина дерева, как и узел любой динамической структуры, имеет две группы данных: полезную информацию и ссылки на узлы, связанные с ним. Для двоичного дерева таких ссылок будет две – ссылка на левого сына и ссылка на правого сына. В результате получаем структуру, описывающую вершину (предполагая, что полезными данными для каждой вершины является одно целое число):

struct Node {

int key; // полезные данные (ключ)

Node *left, *right; // указатели на сыновей

};

typedef Node *PNode; // указатель на вершину

Абстрактный тип данных (АТД) — это тип данных (набор значений и совокупность операций для этих значений), доступ к которому осуществляется только через интерфейс.

Абстрактные типы данных (abstract data type, в дальнейшем АТД) позволяют создавать программы с использованием высокоуровневых абстракций. За счет применения абстрактных типов данных появляется возможность отделять абстрактные (концептуальные) преобразования, которые программы выполняют над данными, от любого конкретного представления структуры данных и любой конкретной реализации алгоритма.

Class share

{

public:

share() {}

virtual void draw() {}

private:

};

Class circle: public share

{

circle () {}

void draw() {}

private:….};

Все методы должны функционировать нормально в производных классах, но не в классе share, поскольку невозможно создать экземпляр формы как таковой. Программа должна быть защищена от попытки пользователя создать объект этого класса. Класс share существует только для того, чтобы поддерживать интерфейс, общий для всех производных классов, поэтому об этом типе данных говорят как об абстрактном, или АТД.

Абстрактный тип данных представляет общую концепцию, такую как форма, а не отдельные объекты. В Си АТД по отношению к другим классам всегда выступает как базовый, для которого невозможно создать функциональный объект абстрактного класса.