Главная Обратная связь

Дисциплины:






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



Если до начала работы с данными невозможно определить, сколько памяти потребуется для их хранения, память выделяется по мере необходимости отдельными блоками, связанными друг с другом при помощи указателей. Такой способ организации данных называется динамическими структурами данных, поскольку их размер изменяется во время выполнения программы. Из динамических структур в программах чаще всего используются различные линейные списки, стеки, очереди и бинарные деревья. Они различаются способами связи отдельных элементов и допустимыми операциями над ними. Динамическая структура может занимать несмежные участки оперативной памяти. В процессе работы программы элементы структуры могут по мер необходимости добавляться и удаляться.

Элемент любой динамической структуры данных состоит из полей, часть из которых предназначена для связи с соседними элементами. Вот, например, как выглядит описание элемента линейного списка для хранения целых чисел:

struct Node {

1Пt д.

Node *р:

В зависимости от решаемой задачи в программах применяются различные виды динамических структур.

Рассмотрим на примере односвязного списка.

Динамические структуры данных имеют следующие характеристики.

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

2. Отсутствие физической смежности элементов структуры в памяти. Логическая последовательность элементов задается в явном виде с помощью одного или нескольких указателей, или связок, хранящихся в самих элементах.

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

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

В качестве информационной части может быть данное любого типа: целого, вещественного, символьного, строкового, структуры и т.п.

Элемент списка на С++ может быть описан так:

structnode{

int a; // информационное поле

structnode* next;// указатель на следующий элемент

};

Доступ к элементам списка. Для доступа к элементу списка используется оператор ->:

Переменная-указатель_на_элемент_списка ->имя_поля

Например: node *p; p->a;

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

Список можно сформировать следующими способами:

- по принципу стека: первый созданный элемент будет последним в списке,



- по принципу очереди: первый созданный элемент будет первым в списке.

Формирование списка по принципу стека. Последовательность действий при формировании списка

по принципу стека следующая.

1. Пусть указатель на ранее созданный элемент pred=NULL (т.е. до формирования списка нет такого

элемента).

2. Выделить память под текущий элемент списка p.

3. Занести значение в информационное поле.

4. Занести значение в поле next равное pred.

5. Сохранить в pred значение p текущего элемента.

6. Повторять п. 2 – 5, пока не будет сформировано нужное количество элементов списка.

7. В p будет указатель на первый элемент списка.

Функция формирования односвязного списка имеет вид

struct node{

int a;

struct node* next;

};

typedefstruct node *Node_ptr;

Node_ptrinput(int n)

{

Node_ptr p=NULL,pred=NULL;

for(inti=0;i<n;i++)

{

p=new struct node;

p->a=rand()/1000-100;

p->next=pred;

pred=p;

}

return p;

}

Здесь был определен собственный тип Node_ptr как указатель на структуру node. Параметром функции

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

элемент списка. В теле функции информационная часть элемента списка заполняется случайным числом.

Формирование списка по принципу очередь. Последовательность действий при формировании списка

по принципу очередь следующая.

1. Задать начальное значение указателя на первый элемент списка равный NULL (т.е. до формирования

списка нет такого элемента).

2. Если указатель на первый элемент списка равен NULL, выделить память под элемент списка p и со-

хранить адрес в head.

3. Занести значение в информационное поле.

4. Занести значение в поле next равное NULL.

5. Сохранить в pred значение p текущего элемента.

6. Повторять п. 2 – 5, пока не будет сформировано нужное количество элементов списка.

7. В head будет указатель на первый элемент списка.

Функция формирования односвязного списка имеет вид

Node_ptr input_1(int n)

{

Node_ptr p=NULL,head=NULL, pred=NULL;

for(inti=0;i<n;i++)

{

if(head==NULL)

{

head=new struct node;

head->a=rand()/100-100;

head->next=NULL;

pred=head;

}

else

{

p=new struct node;

p->a=rand()/100-100;

p->next=NULL;

pred->next=p;

pred=p;

}

}

returnhead;

}

В данной функции, так же как и в предыдущей, единственным параметром является количество эле-

ментов списка, который необходимо сформировать. Функция возвращает указатель на первый элемент спи-

ска. В отличие от предыдущей функции здесь осуществляется проверка: создан ли первый элемент списка

(head==NULL) и если нет, то создается элемент, адрес которого сохраняется в переменной head.

 





sdamzavas.net - 2019 год. Все права принадлежат их авторам! В случае нарушение авторского права, обращайтесь по форме обратной связи...