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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

б)
Рис. 11 Устройство двунаправленного списка:
а – линейная структура; б – кольцевая структура
П р и м е р 31
struct lSp1 *first;
first = (struct lSp1 *) malloc(sizeof(struct lSp1));
// При создании линейного списка
first->next = first->last = NULL;
// При создании кольцевого списка
first->next = first->last = first;
Поиск элемента в двунаправленном списке осуществляется аналогично поиску в однонаправленном
списке.
Добавление и удаление элементов осуществляются проще, чем подобные операции для однона-
правленного списка. Это стало возможным благодаря наличию связей у любого элемента не только со
следующим, но и с предыдущим элементом списка.
Рассмотрим добавление элемента в двунаправленный список.
П р и м е р 32
struct lSp1 *other, *new;
scanf("%d", &key);
other = first;
while (other->key != key) other = other->next;
new = (struct lSp1 *) malloc(sizeof(struct lSp1));
new->next = other->next;
new->last = other;
other->next->last = new;
other->next = new;
Таким образом новый элемент встроен в структуру списка.
При удалении элемента необходимо его соседям слева и справа присвоить ссылки друг на друга.
Рассмотрим процедуру удаления заданного элемента списка подробнее.
П р и м е р 33
other = first;
while (other->key != key) other = other->next;
other->next->last = other->last;
other->last->next = other->next;
free(other);
Очистка памяти при окончании работы программы осуществляется аналогично удалению однона-
правленного линейного списка из памяти ЭВМ.

Страницы