Рекурсия при обработке двусвязного списка
Как и в случае односвязного списка, задача может быть решена с использованием рекурсивных функций, как показано в нижеприведенной программе.
#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, что видно из приведенной программы.
Результаты выполнения программ для варианта двусвязного списка не будут отличаться от результатов выполнения программы для односвязного списка.
Методика выполнения лабораторной работы
1. Написать программу, реализующую заданный преподавателем алгоритм обработки данных.
2. Отобразить алгоритм решения задачи в виде схемы программы ( см. /3/).
3. Протестировать разработанную Вами программу.
4. Оформить отчет по лабораторной работе.
Содержание отчета
1. Сформулировать цель работы (цель Вашей работы не совпадает с целью лабораторной работы вообще, она, Ваша цель, более конкретна и определяется заданной преподавателем задачей обработки информации).
2. Описать в виде таблицы структуру содержательной информации списка с указанием последовательности и размерности полей элементов структуры.
3. Описать терминальные данные для поставленной задачи.
4. Записать программу решения поставленной Вам задачи.
5. Отобразить схему программы.
6. Привести результаты тестирования программы.
7. Сделать выводы по результатам тестирования программы.
Литература
1. Подбельский В.В., Фомин С.С. Программирование на языке СИ: Учеб. пособие. – 2-е доп. изд. – М.: Финансы и статистика, 1999. – 600 с.: ил.
2. Костин А.Е., Шаньгин В.Ф. Организация и обработка структур данных в вычислительных системах: Учеб. пособие для вузов.- М.: Высш. шк., 1987.- 248 с.: ил.
3. Валеева Р.Г. Методические указания к выполнению схем при документировании программного обеспечения (электронный вариант).