Основы программирования для автоматизированного проектирования и решения творческих задач - 34 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

указателей того же типа, что и сам структурный тип, связана с целым рядом новых свойств. На их осно-
ве строятся динамические структуры данных: списки, буферы, стеки, деревья.
12.1 Однонаправленный линейный список
Рассмотрим, какой эффект можно получить от включения в состав структуры указателя на саму
структуру:
struct lSp
{
struct lSP *next;
int key;
};
Определим в программе два указателя вышеописанного типа:
struct lSp *first, *other;
Создадим в основной памяти ЭВМ, не занятой нашей программой, ячейку памяти типа lSp и запом-
ним ее адрес в указателе first, а в поле next этой ячейки запишем NULL:
first = (struct lSp *) malloc(sizeof(struct lSp));
first->next = NULL;
Таким образом, появилась новая ячейка памяти, которая не занимает область сегмента данных про-
граммы, а вынесена в свободную память компьютера, называемую кучей.
Далее мы можем создать неограниченное количество подобных ячеек, каждая из которых будет
хранить свою информацию. Для того, чтобы программа не потеряла связь с этими ячейками, необходи-
мо объединить их в цепочку. В этом случае наша программа может обойтись всего двумя указателями
для работы с созданным списком: указатель first будет помнить адрес первой ячейки в списке, а указа-
тель other, переходя от ячейки к ячейке, может быть настроен на любую из них. Окончание списка по-
казывает ячейка, у которой в поле next находится значение NULL. Созданный таким образом список но-
сит название однонаправленного линейного списка. Процесс его создания приведен в примере 24, а уст-
ройство показано ни рис. 10.
П р и м е р 24
other = first;
while (other->next != NULL) other = other->next;
other->next = (struct lSp *) malloc(sizeof(struct lSp));
other = other->next;
other->next = NULL;
scanf("%d", &other->key);
Рис. 10 Устройство однонаправленного списка
Наиболее распространенными операциями, применяемыми к элементам динамических структур
данных, являются поиск элемента по некоторому ключевому полю, добавление нового элемента в спи-
NULL

Страницы