Динамические информационные структуры.

Динамические информационные структуры используются для постоянно изменяющихся данных. Например: добавлять элементы или удалять.

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

Список- структура данных, в которой каждый элемент сод-ит инф-ию о месте размещения другого (других) связанных элементов.

Линейный список- такой список, к-ый имеет начало и конец. Первый элемент – голова списка.

Кольцевой список- не имеет ни начала, ни конца, т.е. посл.элемент содержит информацию о первом.

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

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

Схема линейного односвязного списка:

Head(внешний указатель)--------> информационные поля(next)-----à информационные поля(next)--à инф.поля(NULL).

Next – содержит информацию о том, где размещен след.элемент.

NULL – нулевой адрес

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

Если список не содержит ни одного звена, то такой список называется пустым. Для него head=NULL.

Реализация линейного односвязного списка средствами языка СИ:

struct Student

{

char name[50];

int number;

};

Struct Cell

{

Struct Student info;

Struct Cell*next; //адрес след.звена

};

//предположим, что список уже существует, требуется напечатать значения его элементов. Определим функцию:

Void print_list(struct Cell*head)

{

Struct Cell*current;

If(head==NULL)

{

Puts(“Список пуст”);

Return;

}

Current=head;

While(current! =NULL)

{

Printf(“%20s%d”, current-> info.name, current-> info.number);

Current=current-> next;

}

}

Для работы с односвязным списком требуются следующие операции: добавление элемента в список; удаление элемента из списка; освобождение памяти, занятой элементом списка. Кроме этого, могут реализовываться и другие операции, например: вывод всех элементов списка; вывод заданного элемента списка; определение того, содержится ли в списке элемент. Число операций, определяемых для двусвязного списка, намного больше и может включать: Часто списки строят по иерархическому принципу. В этом случае элементы списка могут иметь внутреннюю структуру, организованную также по принципу списка (основной список оказывается состоящим из подсписков). Таким образом, сцепление элементов списка с помощью ссылок и наличие информационной части в каждом звене списка позволяют создать достаточно сложные структуры, пригодные для разных приложений. Реализация линейного односвязного списка средствами языка Си Линейный односвязный список представляет собой динамическую структуру, когда каждый элемент, кроме информационных полей, включает только указатель на следующий элемент списка. Доступ ко всему списку осуществляется через внешний указатель, который указывает на первый элемент списка. Под внешним указателем понимают тот, который не содержится внутри никакого элемента. Поле следующего адреса последнего элемента содержит нулевое значение, что означает конец списка.

Список, не содержащий элементов, называется пустым, или Поле следующего адреса последнего элемента содержит Поле следующего адреса последнего элемента содержит нулевое значение (Null), что означает конец списка.

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

struct < имя структурного типа> (

< информационные поля (данные)>

struct < имя структурного типа> ~ < указатель>;

Рассмотрим реализацию линейного односвязного списка в динамической памяти. Пусть объявлен шаблон:

struct Student {

char name{80); //ФИО студента

int number; //Номер зачетной книжки

Тогда элемент списка может иметь следующую структуру:

struct Cell (

struct Student~ next; //Указатель на следующий элемент

списка

struct Student info; //Поле данных)'

Предполагается, что память, отводимая под элементы списка, выделяется динамически. Поэтому при реализации списка в памяти его длина ограничивается только доступным объемом памяти.

/» Функция формирует в динамической памяти структуру по шаблону Cell, запрашивая данные для информационных полей с клавиатуры, возвращает указатель на созданную структуру.»'/

struct Cell* cell new()

{

struct Cell new;

new=(struct Cell~)malloc(sizeof(struct Cell));

puts(" Vvedite F.I.о studenta");

scanf(" %s", & new-> info.namе);

puts(" Vvedite nomer zachetki");

'scanf(" %d", а new-> info пот)> ег)р

new-> next=NULL;

return new; }

/* Функция добавляет новое звено (структуру new) к концу

списка head. Возвращает начало полученного списка.; I

struct Cell*add to end(struct Cell»head, struct Cell» new)

(

struct Cell»last head;

last head=last cell(head);

last head-> next= new;

last head= new;

return head;

/ Функция возвращает количество звеньев в списке head.

int count cell(struct Cell*head)

(

int count=0;

struct Cell+current=NULL;

if(head =NULL)

return 0;

current=head;

while(current! NULL)

(

count++;

current=current-> next;

)

return count;

// Функция удаляет первое звено списка head.

struct Cell*delete first cell(struct Cell head)

(

if(head==NULL)) head-> next=-NULL)

return NULL;

struct Се11*весоп»);

second=head-> next;

free(head);

return second;

//Функция возвращает указатель на последнее звено списка.

struct Cell*last cell(struct Cell'head)

(

struct Се11 сиггеп1;

if(head =NULL)

return NULL;

if(head-> next~=NULL)

return head;

current/cad;

while(current-> next! =NULL)

current=current-> next;

return current;

)

Стек - дин-ая структура данных, в кот-ой добавление новых элементов осуществляется с конца. Для реализации стека необходимы 3 операции:

Pop()-извлечение элементов стека

Push()- помещение элементов в стек

Peek()- просмотреть содержимое.

struct Cell { struct Inf info; struct Cell * next; };

Функция push – добавляет элемент new_elem в стек с вершиной top и возвращает новую вершину стека.

Struct Cell* push (struct Cell* top, struct Cell* new_elem)

{//заполняем поле нового элемента new_elem, как ук. на след.

New_elem -> next=top;

//делаем новую вершину

Top=new_elem;

Return top; };

Pop – освобождает память, занятую этим звеном и возвращает указатель на новую вершину стека.

Struct Cell* pop (struct Cell* top)

{if(top==NULL)

Return top;

Else{

New_elem -> next=top;

//делаем новую вершину

Top= top -> next; Tmp=top; free(tmp);

Return top; } };

Очереди – это динамическая структура; представляющ-я собой набор данных, в которой добавление осущ-ся с 1-го конца, а извлечение с другого конца.

м 68. Классы и объекты в ООП

Класс - это тип данных, созданный программистом, представляющий собой набор данных, возможно различных типов, и множество операций манипулирования этими данными.

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

Определение класса

Рассмотрим для примера концепцию " строка символов". Реализуем, например, вывод строки на экран в заданной позиции. Для этого создадим новый тип String. Набор данных, описывающих объект типа String, должен состоять, как минимум, из собственно символьной строки и двух переменных, определяющих позицию для размещения строки на экране. Определим основные операции: задание строки, установка координат строки, а также вывод строки в указанное место экрана. Простейшее определение класса String может выглядеть так:

class String

{

private:

char str[80];

int row, col;

public:

void setStr (char *);

void setCoord (int, int);

void printStr (int = 0, int = 0);

};

Определение класса включает две части: заголовок класса, состоящий из ключевого слова class и имени класса; тело класса., заключенное в фигурные скобки и заканчивающееся точкой с запятой. Имя типа (у нас это String), которое следует за ключевым словом class, будет представлять новый тип, введенный пользователем. Это имя затем может быть использовано для объявления переменных (объектов) данного типа: String s1;

Тело класса содержит определение членов класса. Члены класса включают данные (в нашем примере саму строку и координаты) и функции - операции, которые могут быть выполнены над объектами типа String (задание строки, установка координат строки, печать строки).

Объявление данных-членов класса аналогично объявлению переменных, за исключением того, что не разрешается явная инициализация, Как и при объявлении переменных, данные-члены класса одного типа можно объявить одним оператором объявления: int max_len, top;

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

Обратите внимание, что в нашем примере (класс String) в теле класса расположены объявления (но не определения) функций-членов класса. В этом случае предполагается, что определения этих функций находятся где-то в другом месте программы. Такие функции называются внешними. Определение функций-членов класса могут находиться и в теле класса. Такие функции называются встраиваемыми.

Доступ к членам класса

В примере описания класса String использованы ключевые слова private и public. Кроме этих слов, может быть также использовано ключевое слово protected. Эти ключевые слова называются метками, они управляют доступом к членам класса и делят тело класса части, различающиеся по уровню доступа, - " личную" (private или protected) и " общую" (public). Если члены класса объявлены после ключевого слова public, то они считаются общими, т.е. открытыми для доступа из любой точки программы в области видимости. Ключевые слова private и protected говорят о том, что следующие за ними члены класса доступны только для функций-членов класса (либо для привилегированных функций).

Обычно личная часть содержит данные, а общая — объявления (или определения) функций, но каких-либо ограничений на это не накладывается. Тем не менее, хорошим стилем программирования считается объявление данных-членов класса в части private, а функций-членов класса - в части public. Это обеспечивает следующие преимущества:

• при необходимости корректировки данных-членов класса в определении класса изменения надо проводить только в функциях, являющихся членами этого класса;

• обеспечена защита данных-членов класса от случайных изменений и несанкционированного доступа.

Если при определении класса ключевые слова private, public, protected опущены, то подразумевается доступ private (все поля класса считаются личными). Поэтому приведенное выше определение класса String эквивалентно следующему:

class String {

char str [80];

int row, col;

public:

void setStr (char *);

void setCoord (int, int);

void printStr (int = 0, int = 0);

};