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

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

struct lSP1 *next, *last;
int key;
};
В этом случае можно связать указатель next со следующим элементом списка, а указатель last с предыдущим.
При создании списка возможны два варианта организации цепочки. Можно при создании первого элемента обоим ука-
зателям присвоить константу NULL. При этом получится линейная структура списка (рис. 11, а). Если же обоим указателям
присвоить адрес созданного элемента, то получится кольцевая структура списка (рис. 11, б).
а)
б)
Рис. 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;

Страницы