Similar presentations:
Алгоритмы и структуры данных. Рекурсивная обработка списков
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 Nilelse 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 Nilelse 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 zelse 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