русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Линейный двусвязный список


Дата добавления: 2013-12-23; просмотров: 1201; Нарушение авторских прав


 

Этот список свободен от недостатков, присущих односвязному списку. Для этого в каждое звено добавлен еще один указатель на тип звена, значением которого является адрес предыдущего звена списка. Тип звена на языках Си/Си++:

 

struct Link2

{

int data;

Link2 *next, *prev;

};

 

Структура списка будет выглядеть следующим образом (значения нулевых указателей показаны для языка Паскаль):

 

Ведущее звено этого списка создаётся следующим набором операторов:

 

Link2 *L2 = new Link2;

L2->next = NULL;

L2->prev = NULL;

 

По операторам создания ведущего звена можно судить о том, является список, 1- или 2-связным, линейным или кольцевым. Нулевые значения указателей next и prev являются признаком линейного списка.

 

Графически состояние списка после создания ведущего звена может быть отображено следующим образом:

Преимущества двусвязного списка:

есть возможность перестроить поврежденный список;

проще выполняются некоторые операции (например, удаление).

 

Операции с 2-связным списком. Всё, что касалось операций добавления звена и его удаления для 1-связного списка, справедливо и для 2-связного. Так же должен соблюдаться правильный порядок проведения (или удаления) связей между звеньями, но таких операций стало больше, т.к. должны обрабатываться 2 указателя. Кроме того, каждая из операций обладает дополнительными особенностями:

 

1. При добавлении нового звена в пустой список, т.е. содержащий только ведущее звено (см. предыдущий рисунок), или при добавлении звена в конец списка (для пустого списка обе эти ситуации совпадают) необходимо проверять наличие звена, которое будет следующим за добавляемым (для пустого списка или конца списка такого звена нет, а значит нет и указателя, обозначающего связь). Такая же проверка должна выполняться при удалении звена.



 

2. Возможность перемещаться по списку в обоих направлениях позволяет напрямую задавать удаляемое звено (а не ему предшествующее, как в 1-связном списке). Следствием этого является упрощение как операции удаления, так и операции поиска.

 

Добавление звена в произвольную позицию за ведущим звеном

 

void Insert2(Link2* St,int data)

{

Link2* q=new Link2; // 1 Выделение памяти под звено

q->data=data; // 2 Ввод данных

q->next=St->next; // 3 Проведение связи от нового звена вперёд

q->prev=St; // 4 Проведение связи от нового звена назад

St->next=q; // 5 Проведение связи от предыдущего звена к новому

if(q->next) // Проверка наличия следующего звена

q->next->prev=q; // 6 Проведение связи от следующего звена к новому

}

 

Удаление звена из любого места списка за ведущим звеном

 

void Delete2(Link2* del)

{

del->prev->next=del->next; // 1 Обработка связи вперёд

if(del->next)

del->next->prev=del->prev; // 2 Обработка связи назад

delete del; // 3 Освобождение памяти

}

 

Поиск в 2-связном списке

 

int Search2(Link2* Start,Link2*& Find,int Key)

{

Link2* Cur=Start->next;

int Success=0;

while(Cur && !Success)

{

if(Cur->data==Key)

{

Find=Cur;

Success=1;

break;

}

Cur=Cur->next;

}

return Success;

}

 

Эта процедура поиска фактически является (за исключением типа данных Link2 вместо Link1) процедурой "обычного" поиска (т.е. не для удаления) в 1-связном списке.

 

Операция просмотра списка в прямом направлении ничем не отличается от просмотра 1-связного списка.

 



<== предыдущая лекция | следующая лекция ==>
Линейный односвязный список | Кольцевые списки


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.005 сек.