Рекурсия при обработке односвязного списка.
Лабораторная работа №2
Методические указания к лабораторной работе
“создание списковых структур данных”
по дисциплине “технология программирования”
Цель работы
Усвоение студентами рекурсивных процедур программирования на примере создания списков данных.
Краткие теоретические сведения
Во многих задачах требуется использовать данные, представление которых (конфигурация, размеры, состав) может изменяться в процессе выполнения программы. О таких изменяемых данных говорят, используя принятый в информатике термин "динамические информационные структуры ". Динамические структуры имеют следующие основные особенности:
• непостоянство и непредсказуемость размера (числа элементов) структуры в процессе ее обработки. Число элементов структуры может изменяться от нуля до значений, определяемых спецификой решения задачи или доступным размером памяти;
• отсутствие физической смежности элементов структуры в физической памяти. Логическая последовательность элементов задается в явном виде с помощью одного или нескольких указателей или связок, хранящихся в самих элементах. Следовательно, память, занимаемая динамической структурой, не является непрерывной и может быть хаотически разбросана в области памяти.
Часто динамические структуры физически представляются в форме связных списков. Связный список – такая структура данных, элементами которой служат записи с одним и тем же форматом, связанные друг с другом с помощью указателей, хранящихся в самих элементах списка.
Односвязный список
Наиболее простая динамическая информационная структура - это односвязный список, элементами (звеньями) которого служат объекты, например, такого структурного типа:
struct имя_структурного_типа
{
элементы _структуры; /* данные */
struct имя_структурного_типа * указатель;
};
В каждую структуру такого типа входят: содержательные элементы структуры которые хранят информацию об однотипных объектах предметной области ( будем их называть просто ”данные” и обозначать D), и указатель на другой объект того же типа, что и определяемая структура ( будем обозначать эту часть структуры L).
Чтобы продемонстрировать некоторые особенности обработки простых динамических информационных структур, разработаем программу, в которой определим структурный тип для представления звеньев односвязного списка и решим такую простейшую задачу: "Ввести с клавиатуры произвольное количество структур, объединяя их в односвязный список, а затем вывести на экран дисплея содержимое введенного списка в порядке формирования его звеньев".
Анализ динамических информационных структур удобнее всего выполнять с помощью их графического изображения. На рисунке 1 приведены схема односвязного списка и обозначения, которые будут использованы в программе. Для работы со списком понадобятся три указателя: beg - на начало списка; end - на последний элемент, уже включенный в список; rex - указатель для "перебора" элементов списка от его начала.
Рисунок 1. Односвязный динамический список
Содержательные данные списка представляют собой наименование объекта и его вес. Признаком окончания содержательной информации при ее вводе является нулевое значение веса. Следующая программа решает сформулированную задачу.
#include <iostream>
#include <conio.h>
using namespace std;
//описание структуры "Звено списка"
struct cell
{ char sign[10];
int weight;
cell *pc;
};
void main()
{ cell *rex; //указатель для перебора звеньев списка
cell *beg = NULL; //начало списка
cell *end = NULL; //конец списка
cout << "Input value struct\n"; //введите значения списка
//цикл ввода и формирования списка
do
{ //выделить память для очередного звена списка
cell *rex = new cell;
//ввести значения элементов звена
cout << "sign = ";
cin >> rex->sign;
cout << "weight = ";
cin >> rex->weight;
if(rex->weight == 0)
{ delete [] rex;
break; //выход из цикла ввода списка
}
//включить звено в список
if(beg == NULL && end == NULL)
beg = rex; //список пуст - включить введенный элемент в список первым
else
end->pc = rex; //включить звено в уже существующий список
end = rex;
end->pc = NULL;
}
while(1); //конец ввода списка
//напечатать список
cout << "\nContent of list"; //Содержимое списка
rex = beg;
while(rex != NULL)
{ cout << "\nsign = " << rex->sign
<< "\tweight = " << rex->weight;
rex = rex->pc;
}
getch();
}
Пример выполнения программы:
Введите данные о структурах:
Sign=sigma
weight=16
Sign=omega
weight=44
Sign=alfa
weight=0
Содержимое списка:
Sign=sigma weight=16
Sign=omega weight=44
Обратите внимание, что при вводе данных о третьем элементе списка введено нулевое значение переменной weight и соответствующий элемент в список не включен.
В программе ввод данных, т.е. заполнение односвязного списка структур, выполняется в цикле. Условием окончания цикла служит нулевое значение, введенное для элементаint weight очередной структуры.
Формирование списка структур происходит динамически. Указатели-beg, end инициализированы нулевыми значениями - вначале список пуст.
Обратите внимание на преобразование типов(struct cell *) при выделении памяти для структуры типаstruct cell. Функция malloc() независимо от типа параметров всегда возвращает указатель типаvoid *, а слева от знака присваивания находится указатель rex типаstruct cell *. Используется явное приведение типов, хотя это не обязательно - типvoid * совместим по операции присваивания с указателем на объект любого типа.
Остальные особенности программы поясняются комментариями в ее тексте.
Рекурсия при обработке односвязного списка.
Даже такая простая структура, как динамический односвязный список, представляет собой конструкцию вложенных списков, как показано на рисунке 2. На нем собственно данные или содержательные элементы обозначены D, а связи между записями или указатели обозначены L.
Рисунок 2 Рекурсивное представление односвязного списка
Вложенные структуры удобно обрабатывать с помощью рекурсивных процедур. Рассмотрим ту же задачу об односвязном списке, но оформим формирование списка и вывод списка на экран дисплея в виде рекурсивных функций. Сделаем это с целью показать на этом простом примере особенности рекурсивной обработки динамических информационных структур.
В каждом звене списка содержатся полезная информация (данные) и ссылка (адрес) на следующее звено списка. Если такая ссылка нулевая, то список пройден до конца. Для начала просмотра списка нужно знать только адрес его первого элемента.
Рассмотрим, какие действия должны выполнять функция рекурсивного формирования списка и функция его рекурсивного просмотра с выводом данных о звеньях списка на экран дисплея.
Функция рекурсивного заполнения списка ниже в программе имеет прототип:
struct cell * input (void) ;
Она возвращает указатель на сформированный динамический список, заполненный вводимыми с клавиатуры дисплея данными. Предполагается, что при каждом вызове этой функции формируется новый список. Функция заканчивает работу, если для очередного звена списка введено нулевое значение переменной weight. В противном случае заполненная с клавиатуры структура подключается к списку, а ее элементуstruct cell *рс присваивается значение, которое вернет функция input(), рекурсивно вызванная из тела функции. После этого функция возвращает адрес очередного звена списка, т.е. значение указателяstruct cell * рс.
Прежде чем рассматривать текст функции input( ), помещенный в приведенной ниже программе, еще раз сформулируем использованные в ней конструктивные решения.
1. При каждом обращении к функции input( ) в основной памяти формируется новый список, указатель на начало которого возвращает функция.
2. Выделение памяти для звеньев списка и заполнение значениями элементов звеньев (структур) зависит от тех значений, которые пользователь присваивает элементам.
3. Если для очередного звена списка вводится нулевое значение элемента weight, то звено не подключается к списку, процесс формирования списка заканчивается. Такой набор данных, введенных для элемента очередного звена, считается терминальным.
4. Если нулевое значение элемента weight введено для первого звена списка, то функция input( ) возвращает значение NULL.
5. Список определяется рекурсивно как первое (головное) звено, за которым следует присоединяемый к нему список.
6. Псевдокод рекурсивного алгоритма формирования списка:
Если введены терминальные данные для звена
Освободить память, выделенную для звена
Вернуть нулевой указатель
Иначе:
Элементу связи звена присвоить результат формирования продолжения списка (использовать тот же алгоритм)
Все-если
Вернуть указатель на звено.
Обратите особое внимание на то, что первым оператором рекурсивных алгоритмов является проверка на окончание рекурсии; без этого программа с рекурсией неизбежно будет зацикливаться.
Текст функции input() на языке Си почти полностью соответствует приведенному псевдокоду и учитывает перечисленные конструктивные решения. Для структуры типаstruct cell выделяется память. После того как пользователь введет значения данных, выполняется их анализ. В случае терминальных значений библиотечная функция free(p) освобождает память от ненужного звена списка и выполняется операторreturn NULL;. В противном случае элементу связи (указательstruct cell * р) присваивается результат рекурсивного вызова функции input(). Далее все повторяется для нового экземпляра этой функции. Когда при очередном вызове input() пользователь введет терминальные данные, функция input() вернет значениеNULL,которое будет присвоено указателю связи предыдущего звена списка, и выполнение функции будет завершено.
Функция рекурсивного просмотра и печати списка имеет такой прототип:
void output (struct cell * р) ;
Исходными данными для ее работы служит адрес начала списка (или адрес любого его звена), передаваемый как значение указателя - параметраstruct cell * р. Если параметр имеет значениеNULL - список исчерпан, исполнение функции прекращается. В противном случае выводятся на .экран значения элементов той структуры, которую адресует параметр, и функция output() рекурсивно вызывается с параметром р->рс. Тем самым выполняется продвижение к следующему элементу списка. Конец известен - функция печатает "Список исчерпан!" и больше не вызывает сама себя, а завершает работу.
Текст программы с рекурсивными функциями:
/* Определение структурного типа "Звено списка";*/
#include <iostream>
#include <conio.h>
using namespace std;
//описание структуры "Звено списка"
struct cell
{ char sign[10];
int weight;
cell *pc;
};
//функция ввода и формирования списка
cell *f_input(void)
{ //выделить память для очередного звена списка
cell *p = new cell;
//ввести значения элементов звена
cout << "sign = ";
cin >> p->sign;
cout << "weight = ";
cin >> p->weight;
if(p->weight == 0)
{ delete [] p;
return NULL;
}
p->pc = f_input(); //рекурсивный вызов
return p;
}
//функция печати списка
void f_output(cell *p)
{ if(p == NULL)
{ cout << "\nEnd of listing!"; //Список исчерпан
return;
}
cout << "\nsign = " << p->sign
<< "\tweight = " << p->weight;
f_output(p->pc); //рекурсивный вызов
}
void main()
{ cell *beg = NULL; //начало списка
cout << "Input value struct\n"; //введите значения списка
beg = f_input(); //ввод списка
cout << "\nContent of list"; //Содержимое списка
f_output(beg);
getch();
}
Возможный результат выполнения программы:
Введите данные структур:
Sign=Zoro
weight=l938
Sign=Zodiac
weight=1812
Sign=0
weight=0
Содержимое списка:
Sign==Zoro weight=1938
Sign=Zodiac weight=1812
Список исчерпан!
Двусвязный список
Во многих задачах возникает необходимость организовать эффективное перемещение по списку как в прямом, так и в обратном направлениях или заданным признакам элемента найти предшествующий и последующий элементы списка. Для решения подобных задач можно каждому элементу списка приписать указатели на следующий и предыдущий элементы, т,е. организовать двусвязный список.. Таким образом, линейный двусвязный список отличается от односвязного тем, что каждое звено списка помимо содержательной информации включает два указателя. Один из которых (прямой указатель) адресует следующий элемент списка, а другой – обратный указатель – предыдущий элемент списка, как показано на рисунке 3.
| |||
Элементы такого структурного типа описываются следующим образом:
struct имя_структурного_типа
{
элементы _структуры; /* данные */
struct имя_структурного_типа * указатель;
struct имя_структурного_типа * указатель;
};
Продемонстрируем некоторые особенности обработки двусвязных списков на примере рассмотренной выше задачи. Для работы с двусвязными списками будем, как и ранее, использовать три указателя : beg – на начало списка, end – на последний элемент, уже включенный в список и rex – указатель для “перебора” элементов списка. Приведенная ниже программа формирует двусвязный список для поставленной задачи.
#include <iostream>
#include <conio.h>
using namespace std;
//описание структуры "Звено списка"
struct cell2
{ char sign[10];
int weight;
cell2 *pc1;
cell2 *pc2;
};
void main()
{ cell2 *rex; //указатель для перебора звеньев списка
cell2 *beg = NULL; //начало списка
cell2 *end = NULL; //конец списка
cout << "Input value struct\n"; //введите значения списка
//цикл ввода и формирования списка
do
{ //выделить память для очередного звена списка
cell2 *rex = new cell2;
//ввести значения элементов звена
cout << "sign = ";
cin >> rex->sign;
cout << "weight = ";
cin >> rex->weight;
if(rex->weight == 0)
{ delete [] rex;
break; //выход из цикла ввода списка
}
//включить звено в список
if(beg == NULL && end == NULL)
{ beg = rex; //список пуст - включить введенный элемент в список первым
beg->pc1 = NULL;
}
else
{ end->pc2 = rex; //включить звено в уже существующий список
rex->pc1 = end;
}
end = rex;
end->pc2 = NULL;
}
while(1); //конец ввода списка
//напечатать список
cout << "\nContent of list"; //Содержимое списка
rex = beg;
while(rex != NULL)
{ cout << "\nsign = " << rex->sign
<< "\tweight = " << rex->weight;
rex = rex->pc2;
}
getch();
}
Обратите внимание на то, что вместо структур типа struct cell используется структурный тип struct cell2, имеющий дополнительное поле для второго указателя. Остальные особенности программы поясняются комментариями в тексте программы.