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

Для базовых типов данных (int, float и т.д.) требования к памяти и диапазоны значений определяются конкретной реализацией языка (компилятора). Для производных типов такие требования заложены в их определениях.

Например, определения: double mass[8];

struct complex { float x; float y; } array[10];

позволяют выделить в памяти 8*sizeof(double) байт под массив mass и 10*(sizeof(float)+ sizeof(float)) байт под массив array.

Вводимые таким образом объекты позволяют представлять статические данные.

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

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

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

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

Структура связанного однонаправленного списка:

	Начало списка
	Конец списка

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

Каждая структурная переменная из списка носит название звено.

#include “stdlib.h”

#include “stdio.h”

struct abiturient { char Name[10];

char LastName[10];

struct abiturient *next; };

main()

{ struct abiturient *curr; //указатель для перебора звеньев

struct abiturient *beg=NULL; //указатель на начало списка

struct abiturient *end=NULL; //указатель на конец списка

struct abiturient *prev; //указатель на конец списка

puts(“Ввоод информации о студентах”);

do //выделение памяти для очередного эл-та

{ curr = (struct abiturient *) malloc (sizeof (struct abiturient));

printf (“Введите фамилию: ”);

gets (curr->Name);

printf (“Введите имя: ”);

gets (curr->LastName);

if (strcmp (curr->Name, ”*”) == 0) // условие выхода из цикла

{ free (curr);

break;

}

if (beg == NULL && end == NULL) //список пуст

beg = curr; //включить звено в новый список

else

end->next = curr; //включить звено в список

end = curr;

end->next = NULL;

}

while(1);

puts (“Содержимое списка: ”);

curr=beg;

while (curr!= NULL)

{ printf (“ Студент: %s %s”, curr->Name, curr->LastName)

curr = curr->next;

}

puts (“ Выборочное удаление из списка”);

curr=beg;

char ch;

do

{ printf (“ Студент: %s %s”, curr->Name, curr->LastName)

puts (“ Удалить? (Y / N)”);

ch=getchar();

if (ch==’y’|| ch==’Y’)

{ if (beg==NULL && curr-> next ==NULL) //список пуст

return;

if(curr->next==curr)

curr=curr-> next; //первый эл-т списка

prev=beg; //поиск предыдущего эл-та

while((prev->next)!=curr)

prev=prev-> next;

prev->next=curr-> next;

free(curr);

}

while (curr!= NULL);

}

В программе условием окончания ввода данных является ввод символа * вместо фамилии студента. Формирование списка структур происходит динамически.

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