![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Стандартные функции для двусвязного списка
Рассмотрим несколько стандартных функций для двусвязного списка. Функция push добавляет новый элемент в i-ую позицию списка. Функция выполняет следующие действия: 1. создаёт новый элемент; 2. копируем значение информационного поля; 3. если данный элемент является единственным: · оба указателя (next и pred) ссылаются на этот элемент, · указатель first указывает на единственный элемент в списке. 4. иначе сдвигаем указатель на i-ый элемент и добавляем новый элемент перед i-ым. Добавим новое значение в двусвязный список (push 4), новый элемент будем добавлять после первого. После операции push список содержит один элемент (Рисунок 6). Рисунок 6 - После операции push Добавим ещё несколько значений (push 6 и push 7), каждый новый элемент будем добавлять после первого. Список содержит три элемента (Рисунок 7) в следующей последовательности. Рисунок 7- Добавление новых значений Функция pop выталкивает i-ый элемент из списка. Функция выполняет следующие действия: 1)если список пуст, выходим из функции; 2) если в список содержит единственный элемент: копируем значение информационного поля удаляем элемент из списка присваиваем заголовку пусто 3)иначе сдвигаем указатель на i-ый элемент: если заголовок указывает на i-ый элемент (first==t), тогда перемещаем заголовок на следующий элемент (First=t-> next) копируем значение информационного поля удаляем i-ый элемент из списка 4) возвращаем значение информационного поля. Выполнив функцию pop над линейным списком (выталкиваем 3-ий элемент), получим следующее состояние связного списка (Рисунок 8). Рисунок 8 - Выталкивание элемента. Функция view пробегает по всем элементам и выводит в консоль значение информационного поля. Просмотр элементов осуществляется слева направо, но легко можно переписать функцию и изменить просмотр элементов справа налево (заменить a=a-> next на a=a-> pred). Функция clean удаляет все элементы в списке и присваивает заголовку пусто (first=null). После данной операции список возвращается в исходное состояние.
|