Алгоритмы и структуры данных. Рекурсивная обработка списков

1.

Алгоритмы и структуры данных
Лекция 3
(часть 1)
Рекурсивная обработка списков
1. Представление и реализация линейных
списков на С++
2. Иерархические (нелинейные) списки
21.09.2015
Рекурсивная обработка списков
1

2.

•В прошлой лекции использовалась
абстрактная (не зависимая от конкретного
языка программирования) форма записи
рекурсивных функций над линейными
списками.
•Далее будут рассмотрены представление и
реализация на С++
21.09.2015
Рекурсивная обработка списков
3

3.

Реализация линейных списков (С++)
typedef char base; // базовый тип элементов списка
struct node {
hd
base *hd;
node *tl;
// constructor
node ()
{ hd = NULL; tl = NULL;
}
tl
};
typedef node *list;
21.09.2015
Рекурсивная обработка списков
4

4.

Реализация линейных списков
base head (list s);
/*селектор «голова» списка;
отказ, если S – пустой список*/
list tail (list s);
/*селектор «хвост» списка;
отказ, если S – пустой список */
list cons (base x, list s);
/*конструктор списка;
отказ, если исчерпана память */
21.09.2015
Рекурсивная обработка списков
5

5.

Реализация линейных списков
base head (list s)
{ // PreCondition: not null (s)
if (s != NULL) return *s->hd;
else
{
cerr << "Error: head(nil) \n";
exit(1);
}
}
21.09.2015
Рекурсивная обработка списков
6

6.

Реализация линейных списков
list tail (list s)
{ // PreCondition: not null (s)
if (s != NULL) return s->tl;
else
{
cerr << "Error: tail(nil) \n";
exit(1);
}
}
21.09.2015
Рекурсивная обработка списков
7

7.

list cons (base x, list s)
{ list p;
Реализация
p = new node;
линейных
if ( p != NULL) {
списков
p->hd = new char;
*p->hd = x;
p->tl = s;
return p;
}
else {cerr << "Memory not enough\n";
exit(1);
}
}
21.09.2015
Рекурсивная обработка списков
8

8.

Замечание к реализации Cons
Остается доступ к части нового списка через ссылку y.
y = Cons (x, y); и z = Cons (x, y);
Ср.
x:
г
y:
л
p:
г
а
з
Cons:
21.09.2015
Рекурсивная обработка списков
9

9.

Выполняются ли аксиомы для базовых функций при
такой реализации?
A3) Head (Cons (x, y)) = x;
x:
б
о
y:
Cons:
21.09.2015
р
б
Рекурсивная обработка списков
10

10.

A4) Tail (Cons (x, y)) = y;
x:
б
о
y:
Cons:
р
б
Tail:
Пусть z = Tail (Cons (x, y)).
Значения z и y совпадают.
21.09.2015
Рекурсивная обработка списков
11

11.

A5) Cons (Head (z), Tail (z)) = z.
z:
Cons:
б
о
р
бб
Tail:
Значения z и Cons не совпадают !
Списки z и Cons идентичны.
21.09.2015
Рекурсивная обработка списков
12

12.

Особенности реализации
Из лекции 2
Concat (y, z) = if Null (y) then z
else Cons (Head (y), Concat (Tail (y), z)).
Пример
Concat ((a b), (c d)) = Cons (a, Concat ((b), (c d))).
Concat ((b), (c d)) = Cons (b, Concat (Nil, (c d))).
Concat (Nil, (c d)) = (c d).
Concat ((b), (c d)) = Cons (b, (c d)) = (b c d).
Concat ((a b), (c d)) = Cons (a, (b c d)) = (a b c d) .
Замечания: 1. Список y разбирается и затем собирается
даже если список z пуст.
2. Функция Cons вызывается Size (y) раз.
21.09.2015
Рекурсивная обработка списков
13

13.

Функция Concat на языке C++
list concat_list (list s1, list s2)
{
if (s1 == NULL) return s2;
else return cons ( head (s1),
concat_list ( tail (s1), s2));
}
21.09.2015
Рекурсивная обработка списков
14

14.

Пример Concat ((a b), (c d))
y (s1):
a
b
z (s2):
Concat:
c
a
d
b
Другой вариант: Concat с Copy
Concat2:
21.09.2015
a
b
c
Рекурсивная обработка списков
d
15

15.

Copy (x) if Null (x) then Nil
else Cons (Head (x), Copy (Tail(x)));
list copy_list (list s)
{ if (s != NULL) return cons ( head (s),
copy_list (tail(s)));
else return NULL;
}
Concat_list с copy см. сл.22
21.09.2015
Рекурсивная обработка списков
16

16.

Деструктор
void destroy (list s)
{
if ( s != NULL)
{
destroy ( tail(s));
delete s->hd;
delete s;
};
}
21.09.2015
Рекурсивная обработка списков
17

17.

Reverse (y) = if Null (y) then Nil
else Concat (Reverse (Tail (y)),
Cons (Head (y), Nil) ).
list reverse1 ( list s)
{
if (s == NULL) return NULL;
else return concat_list ( reverse1 ( tail (s)),
cons ( head(s), NULL) );
}
21.09.2015
Рекурсивная обработка списков
18

18.

Rev (y, z) = if Null (y) then z
else Rev (Tail (y), Cons (Head (y), z));
list reverse2 ( list s)
{
return rev2 ( s, NULL);
}
//...................................................................
list rev2 ( list s, list w)
{
if (s == NULL) return w;
else return rev2 (tail (s), cons ( head(s), w));
}
21.09.2015
Рекурсивная обработка списков
19

19.

Процедура печати списка
void print_list ( list s )
{
if (s != NULL)
{
cout << *s->hd << " (" << int(*s->hd) << ") : " ;
print_list ( s->tl );
}
else { // s = nil
cout << "nil\n";
}
}
21.09.2015
Рекурсивная обработка списков
20

20.

Процедура ввода списка
list input_list (ifstream &infile)
// ввод списка из файла - рекурсивно
{
char s;
if (infile >> s) return cons (s, input_list(infile));
else return NULL;
}
21.09.2015
Рекурсивная обработка списков
21

21.

list concat_list (const list y, const list z)
// функция concat без копирования второго списка
{ if (y == NULL) return z;
else return cons ( head (y),
concat_list ( tail (y), z));
} // end concat_list
list concat_list (const list y, const list z)
// функция concat c копированием второго списка
{ if (y == NULL) return copy_list(z);
else return cons (head (y),
concat_list (tail (y), z));
} // end concat_list
21.09.2015
Рекурсивная обработка списков
22

22.

Процедура Conc2 – аналог операции y := y z
Обратить внимание на
// процедура conc2 (y := y*z)
передачу параметра y
void conc2 ( list &y, const list z)
{ if (y==NULL) y = z; else conc2 ( y->tl, z);
}
// процедура conc3 (y := y*z) – не рекурсивная !
void conc3 ( list &y, const list z)
{ if (y==NULL) y = z;
От рекурсии к
else { list q;
итерации (!)
q = y;
while (q->tl != NULL) q = q->tl ;
q->tl = z;
}
}
21.09.2015
Рекурсивная обработка списков
23

23.

См. папку «1 программы к части 1»
21.09.2015
Рекурсивная обработка списков
24

24.

КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
21.09.2015
Рекурсивная обработка списков
25