2.2.Рекурсия при обработке двусвязного списка
Как и в случае односвязного списка, задача может быть решена с использованием рекурсивных функций, как показано в нижеприведенной программе.
#include <iostream>
#include <conio.h>
using namespace std;
//описание структуры "Звено списка"
struct cell2
{ char sign[10];
int weight;
cell2 *pc1;
cell2 *pc2;
};
cell2 *end; //объявление глобальной переменной
//функция ввода и формирования списка
cell2 *f_input(cell2 *r)
{ //выделить память для очередного звена списка
cell2 *p = new cell2;
//ввести значения элементов звена
cout << "sign = ";
cin >> p->sign;
cout << "weight = ";
cin >> p->weight;
if(p->weight == 0)
{ delete [] p;
end = r; //формирование указателя на предшествующий элемент
return NULL;
}
p->pc1 = r;
p->pc2 = f_input(p); //рекурсивный вызов, формирование
//указателя на следующий элемент
return p; //возвращение адреса включенного в список элемента
}
//функция печати списка
void f_output(cell2 *p)
{ if(p == NULL)
{ cout << "\nEnd of listing!"; //Список исчерпан
return;
}
cout << "\nsign = " << p->sign
<< "\tweight = " << p->weight;
f_output(p->pc2); //рекурсивный вызов
}
void main()
{ cell2 *beg = NULL; //начало списка
cout << "Input value struct\n"; //введите значения списка
beg = f_input(beg); //ввод списка
cout << "\nContent of list"; //Содержимое списка
f_output(beg);
getch();
}
Рекурсивные решения для односвязного и для двусвязного списков почти идентичны. Отличие состоит в следующем. Вместо структур типа struct cell, естественно, используется структурный тип struct cell2. Прототип рекурсивной функции ввода и формирования списка имеет вид
struct cell * input(struct cell2 * r);
указывающий на наличие аргумента. При рекурсивном вызове значением аргумента является ссылка на последний включенный в список элемент (последним этот элемент является только в текущий момент времени). Этот адрес-ссылка необходим для заполнения поля указателя на предыдущее звено списка при формировании следующего звена. Комментарии в тексте программы поясняют остальные особенности обработки двусвязных списков.
Функция рекурсивного просмотра и печати списка имеет прототип
void output(struct cell2 *p). Здесь отличий еще меньше: использование структурного типа struct cell2 и указателя на следующее звено p -> рс2 вместо (p -> рс для односвязного списка.
Обратите внимание на наличие кроме указателя beg дополнительно указателя end, объявленного как глобальная переменная. Этот указатель ссылается на последний элемент списка. Наличие двух указателей объясняется особенностями двусвязного списка: в нем обязательно наличие указателей как на начало, так и на конец списка. Значение указателя end формирует функция output() при каждом рекурсивном вызове функции. В качестве значения указателя end выступает адрес последнего сформированного звена списка (последним этот элемент является только в текущий момент времени). При завершении работы функции output() в указателе end окажется адрес завершающего (физически последнего) элемента списка. Вышеописанные отличия формирования двусвязного списка проявляются и в основной функции main, что видно из приведенной программы.
Результаты выполнения программ для варианта двусвязного списка не будут отличаться от результатов выполнения программы для односвязного списка.