Динамические структуры данных
В языках программирования данные различаются на статические и динамические. Отличие статических заключается в том, что переменная (массив) имеет имя, по которому к ней можно обращаться, ее размер заранее известен и его нельзя увеличить во время программы, а также память выделяется при объявлении. Отличие динамических заключается в том, что размер переменной неизвестен и он определяется во время работы программы, память выделяется в процессе работы и переменная не имеет четкого идентификатора. Для работы с динамическими данными необходимо пользоваться указателями.
Отличие динамических структур данных от статических заключается в том, что размер переменной неизвестен и он определяется во время работы программы, память выделяется в процессе работы и переменная не имеет четкого идентификатора. Для работы с динамическими данными необходимо пользоваться указателями.
Непосредственное назначение динамических структур данных заключается в формировании таких структур, как списки, деревья, графы. С помощью ДСД появляется возможность решать прикладные задачи такого плана, как нахождение оптимальных путей, расположения сетей для достижения больших благ и т.д.
Списки
Списком называется структура данных, каждый элемент которой посредством указателя связывается со следующим элементом. Каждый элемент списка имеет поля данных, и поля-ссылки на следующий/предыдущий элемент. Поле ссылки последнего элемента списка должно содержать пустой указатель. Списки классифицируются на односвязные, двусвязные и циклические списки – кольца. Для того, чтобы иметь доступ к элементам списка, необходим головной элемент – указатель на первоначальный элемент списка.
Реализация списков
struct comp {
char name[20]; // Имя переменной
char value[10]; // Значение переменной
comp* next; //Ссылка на следущий элемент списка
}; //описание структуры списка
struct dyn_list {
comp* head; // Первый элемент (голова) списка
comp* tail; // Последний элемент (хвост) списка
}; // описание самого динамического списка
// Создание пустого списка
void constr_list(dyn_list &l)
{
l.head = NULL;
}
// Проверка списка на пустоту
bool chk_empty(dyn_list l)
{
return (l.head==NULL);
}
dyn_list vars; // Динамический список
constr_list(vars);
// Включение в список нового компонента
void comp_in(dyn_list &l, char* n, char* v)
{
comp* c = new comp();
strcpy_s(c->name, 20, n);
strcpy_s(c->value, 10, v);
c->next = NULL;
if (chk_empty(l))
l.head = c;
else
l.tail->next = c;
l.tail = c;
}
// Поиск компонента в списке по имени
comp* search(dyn_list l, char *n)
{
while (l.head != NULL)
{
if (!strcmp(l.head->name,n))
return l.head;
l.head = l.head->next;
}
return l.head;
}
// Удаление компонента из списка
void comp_del(dyn_list &l, comp* c)
{
if (c == l.head)
{
l.head = c->next;
return;
}
comp* r = new comp();
r = l.head;
while (r->next != c)
r = r->next;
r->next = c->next;
delete c;
}
