Двунаправленные (двусвязные) спискиДля ускорения многих операций целесообразно применять переходы между элементами списка в обоих направлениях. Это реализуется с помощью двунаправленных списков, которые являются сложной динамической структурой. Двунаправленный (двусвязный) список – это структура данных, состоящая из последовательности элементов, каждый из которых содержит информационную часть и два указателя на соседние элементы (рис. 29.4). При этом два соседних элемента должны содержать взаимные ссылки друг на друга. В таком списке каждый элемент (кроме первого и последнего) связан с предыдущим и следующим за ним элементами. Каждый элемент двунаправленного списка имеет два поля с указателями: одно поле содержит ссылку на следующий элемент, другое поле – ссылку на предыдущий элемент и третье поле – информационное. Наличие ссылок на следующее звено и на предыдущее позволяет двигаться по списку от каждого звена в любом направлении: от звена к концу списка или от звена к началу списка, поэтому такой список называют двунаправленным.
Описание простейшего элемента такого списка выглядит следующим образом: struct имя_типа { информационное поле; адресное поле 1; адресное поле 2; }; где информационное поле – это поле любого, ранее объявленного или стандартного, типа; адресное поле 1 – это указатель на объект того же типа, что и определяемая структура, в него записывается адрес следующего элемента списка; адресное поле 2 – это указатель на объект того же типа, что и определяемая структура, в него записывается адрес предыдущего элемента списка. Например: struct list { type elem; list *next, *pred; } list *headlist; где type – тип информационного поля элемента списка; *next, *pred – указатели на следующий и предыдущий элементы этой структуры соответственно. Переменная-указатель headlist задает список как единый программный объект, ее значение – указатель на первый (или заглавный) элемент списка. Основные операции, выполняемые над двунаправленным списком, те же, что и для однонаправленного списка. Так как двунаправленный список более гибкий, чем однонаправленный, то при включении элемента в список, нужно использовать указатель как на элемент, за которым происходит включение, так и указатель на элемент, перед которым происходит включение. При исключении элемента из списка нужно использовать как указатель на сам исключаемый элемент, так и указатели на предшествующий или следующий за исключаемым элементы. Но так как элемент двунаправленного списка имеет два указателя, то при выполнении операций включения/исключения элемента надо изменять больше связей, чем в однонаправленном списке. Рассмотрим основные операции, осуществляемые с двунаправленными списками, такие как:
Особое внимание следует обратить на то, что в отличие от однонаправленного списка здесь нет необходимости обеспечивать позиционирование какого-либо указателя именно на первый элемент списка, так как благодаря двум указателям в элементах можно получить доступ к любому элементу списка из любого другого элемента, осуществляя переходы в прямом или обратном направлении. Однако по правилам хорошего тона программирования указатель желательно ставить на заголовок списка. Для описания алгоритмов этих основных операций используется следующее объявление: struct Double_List {//структура данных int Data; //информационное поле Double_List *Next, //адресное поле *Prior; //адресное поле }; .......... Double_List *Head; //указатель на первый элемент списка .......... Double_List *Current; //указатель на текущий элемент списка (при необходимости)
|
