289.50K
Категория: ПрограммированиеПрограммирование

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

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
English     Русский Правила