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

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

· линейные списки;

· стеки;

· очереди;

· бинарные деревья;

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

Наиболее простой динамической структурой является линейный однонаправленный список, элементами которого служат объекты структурного типа (рис.7).

Рис. 11. Линейный однонаправленный список

Описание простейшего элемента такого списка выглядит следующим образом:

struct имя_типа

{

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

адресное поле;

};

· информационное поле – это поле любого, ранее объявленного или стандартного, типа;

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

Информационных полей может быть несколько.

//пример 1

struct point

{

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

point* next; //адресное поле

};

//пример 2

struct person

{

char* name; //информационное поле

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

person* next; //адресное поле

};

Каждый элемент списка содержит ключ, который идентифицирует этот элемент. Ключ обычно бывает либо целым числом (пример 1), либо строкой (пример 2).

Над списками можно выполнять следующие операции:

· начальное формирование списка (создание первого элемента);

· добавление элемента в конец списка;

· добавление элемента в начало списка;

· поиск элемента с заданным ключом;

· удаление элемента с заданным ключом;

· удаление элемента с заданным номером;

· добавление элемента с заданным номером;

· и т. д.

Рассмотрим основные операции над списком из примера 1.

Создание элемента списка

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

#include <iostream.h>

//описание структуры

struct point

{

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

point* next;    //адресное поле

};

//создание элемента

point* make_point()

{

point*p=new(point);//выделить память под элемент списка

cout<<"\nEnter the key";

cin>>p->key;//заполнить информационное поле

p->next=0;//сформировать адресное поле

return p;//вернуть указатель на созданный элемент

}

Создание списка из n элементов

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

/*формирование списка из n элементов путем добавления элементов в начало списка*/

point* make_list(int n)

{

point* beg=make_point();//сформировать первый элемент

point*r;//вспомогательная переменная для добавления

for(int i=1;i<n;i++)

{

r=make_point(); //сформировать следующий элемент

//добавление в начало списка

r->next=beg; //сформировать адресное поле

beg=r; //изменить адрес первого элемента списка

}

return beg; //вернуть адрес начала списка

}

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

/*формирование списка из n элементов путем добавления элементов в конец списка*/

point* make_list(int n)

{

If(n==0) return 0;//список пустой

point* beg=make_point();//сформировать первый элемент

if (n==1) return beg;//список из одного элемента

point*r,//новый элемент списка

//указатель для хранения адреса последнего элемента списка

*q;

q=beg;//поставили указатель q на первый элемент

for(int i=1;i<n;i++)

{

r=make_point(); //сформировали следующий элемент

//добавление в конец списка

q->next=r; //связали список с новым элементом

q=r; //изменить адрес последнего элемента списка

}

return beg; //вернуть адрес начала списка

}

Перебор элементов списка

Чтобы перебрать элементы списка нужно встать на первый элемент p=beg и переходить от одного элемента к следующему, используя адресное поле next: p=p->next, до тех пор, пока список не закончится, т. е. p не станет равно нулевому значению. При обходе выполняется обработка ключевого поля списка. Рассмотрим перебор элементов списка на примере функции печати.

void print_list(point*beg)//печать списка

{

point* p=beg;//встали на начало списка

//проверка наличия элементов в списке

if (!p) {cout<<"\nThe list is empty!"; return;}

while(p)//пока значение p не станет равно нулю

{

    cout<<p->key<<" ";//вывод ключевого поля

    p=p->next;//переход к следующему элементу списка

}

}