Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Добавление элементов в двусвязный список
|
|
Двусвязный список
Двусвязный список позволяет двигаться по цепочке элементов в обоих направлениях, имея доступными следующий и предыдущий элементы.
Формирование двусвязного списка:
struct List
{
int info;
struct List *next;
struct List *prev;
};
Циклический список позволяет моделировать линейные цепочки элементов, исключив постоянные проверки на «первый» и «последний». В таком списке поле next последнего элемента ссылается на первый элемент, а поле pred первого - на последний элемент списка. Единственный элемент списка ссылается сам на себя (l-> next = l; l-> pred = l). Операции включения элемента в начало и конец списка идентичны за исключением того, что в первом случае меняется указатель на первый элемент списка.
На рис. 1, 2 приведены примеры двусвязного и циклического списков.
Рис. 1 – Двусвязный список
Рис. 2 – Циклический двусвязный список
Добавление элементов в двусвязный список
Определена структура, которая будет использоваться в последующих примерах:
#define LIST struct List
LIST
{
char info;
LIST *next;
LIST *prev;
};
Функция добавления элементов в двусвязный список:
| void add(LIST **current, char item) { LIST *new_node; new_node = new LIST; new_node-> info = item; if (*current == NULL) { *current=new_node; new_node-> next=NULL; new_node-> prev=NULL; } if ((*current)-> next! =NULL) { new_node-> next=(*current)-> next; (*current)-> next-> prev=new_node; new_node-> prev=*current; (*current)-> next=new_node; } else { (*current)-> next=new_node; new_node-> prev=*current; new_node-> next=NULL; (*current)=new_node; } } | //current – указатель на текущий элемент списка //новый элемент двусвязного списка //создаем новый элемент двусвязного списка //заполняем поле info //добавление первого элемента двусвязного списка //текущим элементом становится новый элемент //указатель на следующий элемент после нового равен нулю (т.е. элемент не существует) //указатель на предыдущий элемент по отношению к новому равен нулю (т.е. элемент не существует) //добавление элемента в середину двусвязного списка (после текущего элемента) //следующим по отношению к новому элементу становится элемент списка следующий после текущего //предыдущим по отношению к элементу следующего после текущего становится новый элемент //предыдущим по отношению к новому становится текущий элемент //следующим по отношению к текущему элементу становится новый элемент //добавление элемента в конец двусвязного списка //следующим по отношению к текущему становится новый элемент //предыдущим по отношению к новому становится текущий элемент списка //указатель на следующий элемент после нового равен нулю (т.е. элемента не существует) //текущим элементом становится новый элемент списка |
Пример. Пусть необходимо сформировать двусвязный список, представленный в программе переменной l, состоящий из трех элементов (‘a’, ’c’, ’b’) (элементы указаны в порядке их добавления в список), упорядоченный по алфавиту. Для этого необходимо использовать функцию add:
LIST *l = 0;
add(& l, ’a’);
add(& l, ’c’);
l = l-> prev;
add(& l, ’b’);
На рис. 3, 4, 5 показаны примеры добавления элементов в начало, середину и конец двусвязного списка соответственно.
Рис.3 – Добавление первого элемента двусвязного списка
Рис. 4 – Добавление элемента в конец двусвязного списка
Рис. 5 – Добавление элемента в середину двусвязного списка