Двусвязные линейные списки
Для описания элементов односвязного линейного списка использовался тип PNode
struct Node
{
int data; //информационное поле, данные, любой порядковый тип
Node *next; //указатель на следующий элемент
};
typedef Node * PNode;
Если в записи Node вставить поле-указатель prev на предыдущий элемент списка, то таким образом можно получить так называемый двусвязный список:
struct Node2
{
int inf; //информационное поле, любой порядковый тип
Node2 *prev; //указатель на предыдующий элемент
Node2 *next; //указатель на следующий элемент
}
typedef Node2* PNode2;
В таком списке к предшествующему элементу можно обратиться через значение указателя prev. Движение по списку от элемента к элементу можно выполнять в обоих направлениях. У первого элемента списка first поле prev установлено в NULL. Оно будет сигнализировать о достижении начала (головы) списка. По-прежнему у последнего элемента last поле next установлено в NULL. При движении вперед оно будет сигнализировать о достижении конца (хвоста) списка.
Операции над двусвязным списком
1. Вставка элемента.
Операция вставки элемента в двусвязный список после заданного q мало чем отличается от подобной операции для односвязного списка. В этом случае несколько расширена работа с указателями, поскольку требуется корректно установить значение нового поля prev :
PNode2 p;
p = new Node2; //p – переменная типа PNode2
p -> next = q -> next;
p -> prev = q;
q -> next -> prev = p; //новый порядок у q^.next
q -> next = p;
q = p;
Опишем функцию вставки элемента в двусвязный список после заданного q.
void Ins_q2(PNode2 &q, int a )
{
PNode2 p;
p = new Node2;
p -> inf = a;
p -> next = q -> next;
p -> prev = q;
q -> next -> prev = p //новый порядок у q^.next
q -> next =p;
q = p; //q – заданный элемент
}
2. Удаление элемента.
Удаление текущего элемента q двусвязного списка происходит несколько проще в сравнении с односвязным списком, потому что не требуется производить поиск предшествующего элемента:
p = q -> prev;
p -> next = q -> next;
q -> next -> prev = p;
delete q;
q = p; //предшествующий элемент станет текущим
Опишем функцию удаления текущего элемента двусвязного списка:
void Del_q2(PNode2 &q, int a )
{
PNode2 p;
p = q -> prev;
a = q -> inf;
p -> next = q ->next;
q -> next -> prev = p;
delete q;
q = p; //предшествующий элемент станет текущим}
}
Эти же действия можно описать с помощью функции типа int:
int Del_q2(Pnode2 &q) //функция вернет символ
{
int a;
PNode2 p;
p = q -> prev;
a = q -> inf;
p -> next = q -> next;
q -> next -> prev = p;
delete q;
q = p; //предшествующий элемент станет текущим
return a;
}
3. Последовательный поиск в списке.
Пусть требуется вставить новый элемент p, причем p должен иметь четко определенное место в списке по конкретному значению поля inf. Последовательный поиск места в списке для вставки можно организовать следующим образом:
PNode2 q;
bool fsearch;
q = first;
do
{
fsearch = q -> inf > p ->inf; //проверка порядка информационного поля
if (!fsearch) //поиск не увенчался успехом
if (q -> next != NULL) //не последний элемент
q = q -> next;
else fsearch = true; //последний элемент, выход из цикла
else q = q -> prev; //поиск успешен, новое состояние q
} while (!fsearch);
После этих действий новый элемент p следует просто вставить в список после текущего элемента q. Если при этом значение q установлено в NULL, то это значит, что элемент должен быть вставлен в начало списка. После этого новый элемент следует сделать текущим.
Опишем функцию поиска места для вставляемого элемента двусвязного списка:
void Search_in_list2( PNode2 &q, PNode2 first, int a )
{
bool fsearch;
q = first;
do
{
fsearch = q -> inf > p ->inf; //проверка порядка информационного поля
if (!fsearch) //поиск не увенчался успехом
if (q -> next != NULL) //не последний элемент
q = q -> next;
else fsearch = true; //последний элемент, выход из цикла
else q = q -> prev; //поиск успешен, новое состояние q
} while (!fsearch);
Ins_q2(q, a); //вставка нового элемента после q
}
Комментариев нет:
Отправить комментарий