Абстрактные типы данных

Август 19, 2022

Главная
Информатика
Абстрактные типы данных

Содержание

2. Абстрактный тип данных (АТД) это тип данных, который предоставляет для работы с элементами этого типа определенный
4. Суть абстракции Вся внутренняя структура спрятана от разработчика программного обеспечения. Абстрактный тип данных определяет набор функций,
5. Абстрактные структуры данных Конкретные реализации АТД называются абстрактными структурами данных.
6. Интерфейсы В программировании АТД обычно представляются в виде интерфейсов, которые скрывают соответствующие реализации типов. Программисты работают
7. Инкапсуляция Такой подход соответствует принципу инкапсуляции в объектно-ориентированном программировании. Пока структура данных поддерживает интерфейс, все программы,
8. Модульность АТД позволяют достичь модульности программных продуктов и иметь несколько альтернативных взаимозаменяемых реализаций отдельного модуля.
9. Примеры АТД Список Стек Очередь Очередь с приоритетом Ассоциативный массив
10. Список это абстрактный тип данных, представляющий собой упорядоченный набор значений, в котором некоторое значение может встречаться
11. Списки в функциональных языках являются фундаментальной структурой Большинство функциональных языков имеет встроенные средства для работы со
12. Стек структура данных, представляющая собой список элементов, организованных по принципу LIFO(англ. last in — first out,
13. Стек поместить элемент в стек push(…) извлечь элемент из стека pop(…) посмотреть не элемент на стеке
14. Стек на базе массива const int SIZE=50; struct stack { тип arr [SIZE]; тип * top;
15. тип top(stack s) { if (s.top == s.arr) { throw ("Stack Underflow"); } return *(s.top-1); }
16. Стек для рекурсивных алгоритмов Обход дерева в качестве тип используем t_ptr struct stack { t_ptr arr
17. init (st); p= tree; flag = 1; while ( flag ) { if (p) { push
18. Выражение, дерево трансляции, ПОЛИЗ (A+B)*(C+D)-E AB+CD+*E
19. ПОЛИЗ - форма записи математических выражений, в которой операнды расположены перед знаками операций. Вычисление выражения, записанного
21. Стек вычислений AB+CD+*E
22. Получение ПОЛИЗ из исходного выражения может выполняться с использованием стека на основе простого алгоритма, предложенного Дейкстpой.
23. Алгоритм Дейкстры Пpосматpивается исходная строка символов слева направо, операнды переписываются в выходную строку, а знаки операций
24. в) если очередной символ из исходной строки есть открывающая скобка, то он проталкивается в стек; г)
25. Трансляция в ПОЛИЗ (A+B)*(C+D)-E
26. struct stack { char arr [SIZE]; char * top; }; stack st; char v[ ] =―
27. while (*str) { if (is_letter(*str)) {*str1=*str; str1++;} else if (*str==‗(‗) push(st,*str); else { while (! empty(st)
28. while (!empty(st)) { c=pop(st); *str1=c; str1++; }
29. Очередь структура данных с дисциплиной доступа к элементам «первый пришел — первый вышел» (FIFO, First In
30. Дек (двусвязная очередь) (от англ. deque — double ended queue; двухсторонняя очередь, двусвязный список, очередь с
31. Очередь с приоритетом АТД, поддерживающий три операции: InsertWithPriority: добавить в очередь элемент с нaзначенным приоритетом. GetNext:
32. Реализация на базе массива const int N= . . .; //размер очереди struct Queue { int
33. Очередь на базе циклического массива const int N=. . .; //размер очереди struct Queue { int
34. Очередь на базе циклического массива void push ( Queue &Q, int value) { if ((Q.last%(N-1))+1==Q.first) throw("Overflow");
35. Множество тип данных, хранящий информацию о присутствии в множестве объектов любого счетного типа. Наиболее эффективная реализация
36. Ассоциативный массив (словарь) АТД, позволяющий хранить пары вида «(ключ, значение)» и поддерживающий операции добавления пары, а
37. Ассоциативный массив не может хранить две пары с одинаковыми ключами. Ассоциативный массив с точки зрения интерфейса
39. Скачать презентацию

Слайд 2

Абстрактный тип данных (АТД)
это тип данных, который предоставляет для работы с

элементами этого типа определенный набор операций (функций ), а также возможность создавать элементы этого типа
при помощи специальных функций (операций).

Слайд 3

Слайд 4

Суть абстракции
Вся внутренняя структура спрятана от
разработчика программного обеспечения.
Абстрактный тип данных определяет

набор функций, независимых от конкретной реализации типа, для оперирования его значениями.

Слайд 5

Абстрактные структуры данных
Конкретные реализации АТД называются
абстрактными структурами данных.

Слайд 6

Интерфейсы
В программировании АТД обычно представляются в виде интерфейсов, которые скрывают
соответствующие реализации

типов.
Программисты работают с АТД исключительно через их интерфейсы, поскольку реализация может в будущем измениться.

Слайд 7

Инкапсуляция
Такой подход соответствует принципу инкапсуляции
в объектно-ориентированном программировании.
Пока структура данных поддерживает интерфейс,
все

программы, работающие с заданной структурой
АТД, будут продолжать работать.
Разработчики структур данных стараются, не меняя
внешнего интерфейса и семантики функций,
постепенно дорабатывать реализации, улучшая
алгоритмы по скорости, надежности и используемой
Памяти.

Слайд 8

Модульность
АТД позволяют достичь модульности программных
продуктов и иметь несколько альтернативных
взаимозаменяемых реализаций отдельного

модуля.

Слайд 9

Примеры АТД
Список
Стек
Очередь
Очередь с приоритетом
Ассоциативный массив

Слайд 10

Список
это абстрактный тип данных, представляющий собой
упорядоченный набор значений, в котором некоторое
значение

может встречаться более одного раза.
Экземпляры значений, находящихся в списке,
называются элементами списка; если значение
встречается несколько раз, каждое вхождение
считается отдельным элементом.
Термином список также называется несколько
конкретных структур данных, применяющихся при
реализации абстрактных списков, особенно связных
списков

Слайд 11

Списки в функциональных языках
являются фундаментальной структурой
Большинство функциональных языков имеет
встроенные средства для

работы со списками:
получение длины списка, головы (первый элемент списка), хвоста (часть списка, идущая за первым элементом), применения функции к каждому элементу списка (Map), свертки списка и пр.

Слайд 12

Стек
структура данных, представляющая собой список элементов, организованных по принципу LIFO(англ. last

in — first out,
«последним пришел — первым вышел»).
В 1946 Алан Тьюринг ввел понятие стека.
А в 1957 году немцы Клаус Самельсон и Фридрих Л. Бауэр запатентовали идею.
Алан Тьюринг Фридрих Л. Бауэр

Слайд 13

Стек
поместить элемент в стек push(…)
извлечь элемент из стека pop(…)
посмотреть не элемент

на стеке без
извлечения top(…) или peek(…)
проверить стек на пустоту empty (…)
проверить стек на переполнение full (…)
подготовить стек к работе init (…)

Слайд 14

Стек на базе массива
const int SIZE=50;
struct stack {
тип arr [SIZE];
тип *

top;
};
void push(stack &s, тип x) {
if (s.top == (s.arr+SIZE)) { throw("Stack Overflow"); }
*s.top = x;
s.top++;
}
тип peek(stack &s) {
if (s.top == s.arr) { throw ("Stack Underflow"); }
s.top--;
return *s.top;
}

Слайд 15

тип top(stack s) {
if (s.top == s.arr) { throw ("Stack Underflow");

}
return *(s.top-1);
}
bool empty(stack s) {
return (s.top == s.arr);
}
bool full (stack s){
return (s.top == (s.arr+SIZE)) ;
}
void init(stack &s) {
s.top=s.arr;
}

Слайд 16

Стек для рекурсивных алгоритмов
Обход дерева
в качестве тип используем t_ptr
struct stack

{
t_ptr arr [SIZE];
t_ptr * top;
};
stack st;
t_ptr tree, p;
bool flag;

Слайд 17

init (st);
p= tree;
flag = 1;
while ( flag ) {
if (p) {
push

( st, p);
p = p->lt;
} else
if empty(st) flag = 0;
else {
p = pop(st);
cout << p->inf<< " ";
p = p->rt;}
}

Слайд 18

Выражение, дерево трансляции, ПОЛИЗ
(A+B)(C+D)-E
AB+CD+E

Слайд 19

ПОЛИЗ - форма записи математических выражений, в которой операнды расположены перед

знаками операций.
Вычисление выражения, записанного в ПОЛИЗ, может поводиться путем однократного пpосмотpа, что является весьма удобным при генерации объектного кода программы.

Слайд 20

Слайд 21

Стек вычислений
AB+CD+*E

Слайд 22

Получение ПОЛИЗ из исходного выражения может выполняться с использованием стека на

основе простого алгоритма, предложенного Дейкстpой.
Введем понятие стекового пpиоpитета операций

Слайд 23

Алгоритм Дейкстры
Пpосматpивается исходная строка символов слева направо, операнды переписываются в выходную

строку, а знаки операций заносятся в стек на основе приоритета:
а) если стек пуст, то операция из входной строки
переписывается в стек;
б) операция выталкивает из стека все операции с большим или равным пpиоpитетом в выходную строку, потом
записывается в стек;

Слайд 24

в) если очередной символ из исходной строки есть открывающая скобка, то

он проталкивается в стек;
г) закрывающая круглая скобка выталкивает все операции из стека до ближайшей открывающей скобки, сами скобки в выходную строку не переписываются, а уничтожают друг друга.

Слайд 25

Трансляция в ПОЛИЗ
(A+B)*(C+D)-E

Слайд 26

struct stack {
char arr [SIZE];
char * top;
};
stack st;
char v[ ] =―

(a+b)*(c+d)-e‖;
char poliz[20];
char *str = v, *srt1=poliz;
init (st);

Слайд 27

$while (str) { if (is_letter(str)) {str1=str; str1++;} else if (str==‗(‗) push(st,str);$

while (str) {
if (is_letter(str)) {str1=str; str1++;}
else
if (str==‗(‗) push(st,str);
else {
while (! empty(st)

&& prior(peek(st))>=prior(*str)) {
c=pop(st);
*str1=c; str1++;
}
if (*str <> ‗)‘ ) push(st, *str );
else if (! empty(st) && peek(st)==‗(‗)
c=pop(st);
}
str++;
}

Слайд 28

while (!empty(st)) {
c=pop(st);
*str1=c;
str1++;
}

Слайд 29

Очередь
структура данных с дисциплиной доступа к
элементам «первый пришел — первый вышел»
(FIFO,

First In — First Out).
Добавление элемента возможно лишь в конец
очереди (принято обозначать словом enqueue ),
выборка — только из начала очереди (что принято называть словом dequeue), при этом выбранный элемент из очереди удаляется.

Слайд 30

Дек (двусвязная очередь)
(от англ. deque — double ended queue; двухсторонняя очередь,

двусвязный список, очередь с двумя концами) — структура данных, в которой элементы
можно добавлять и удалять как в начало, так и в конец, то есть дисциплинами обслуживания
являются одновременно FIFO и LIFO

Слайд 31

Очередь с приоритетом
АТД, поддерживающий три операции:
InsertWithPriority: добавить в очередь элемент с
нaзначенным

приоритетом.
GetNext: извлечь из очереди и вернуть элемент с наивысшим приоритетом.
PeekAtNext (необязательная операция):
просмотреть элемент с наивысшим приоритетом без извлечения.

Слайд 32

Реализация на базе массива
const int N= . . .; //размер очереди
struct

Queue {
int data[N]; //массив данных
int first; //указатель на начало
int last; //указатель на конец
};
Проблема – образуется пустота в начале массива

Слайд 33

Очередь на базе циклического массива
const int N=. . .; //размер очереди
struct

Queue {
int data[N]; //массив данных
int first; //указатель на начало
int last; //указатель на конец
};
void create(Queue &Q) {
Q.first=Q.last=0;
}
bool isEmpty(const Queue &Q) {
if (Q.last==Q.first) return true;
else return false;
}
int getSize(const Queue &Q) {
if (Q.first >Q.last) return (N-1)-(Q.first - Q.last);
else return Q.last – Q.first;
}

Слайд 34

Очередь на базе циклического массива
void push ( Queue &Q, int value)

{
if ((Q.last%(N-1))+1==Q.first)
throw("Overflow");
else {
Q.data[ Q.last ] = value;
Q.last = (Q.last%(N-1))+1;
}
}
int peek(const Queue &Q) {
returnQ.data[Q.first];
}
void pop(Queue &Q) {
Q.first=(Q.first%(N-1))+1;
}

Слайд 35

Множество
тип данных, хранящий информацию о присутствии в
множестве объектов любого счетного типа.

Наиболее эффективная реализация для множеств
ограниченного размера (мощности) – битовая шкала.

Слайд 36

Ассоциативный массив (словарь)
АТД, позволяющий хранить пары вида «(ключ, значение)» и поддерживающий

операции добавления пары, а также поиска и удаления пары по ключу:
• INSERT(ключ, значение)
• FIND(ключ)
• REMOVE(ключ)

Слайд 37

Ассоциативный массив не может хранить две пары с одинаковыми ключами.
Ассоциативный массив

с точки зрения интерфейса удобно рассматривать как обычный массив, в котором в качестве индексов можно использовать не только целые числа, но и значения других типов — например, строки.

Абстрактные типы данных

Содержание

Абстрактный тип данных (АТД)это тип данных, который предоставляет для работы с

Суть абстракцииВся внутренняя структура спрятана отразработчика программного обеспечения.Абстрактный тип данных определяет

Абстрактные структуры данныхКонкретные реализации АТД называютсяабстрактными структурами данных.

ИнтерфейсыВ программировании АТД обычно представляются в виде интерфейсов, которые скрываютсоответствующие реализации

ИнкапсуляцияТакой подход соответствует принципу инкапсуляциив объектно-ориентированном программировании.Пока структура данных поддерживает интерфейс,все

МодульностьАТД позволяют достичь модульности программныхпродуктов и иметь несколько альтернативныхвзаимозаменяемых реализаций отдельного

Примеры АТДСписокСтекОчередьОчередь с приоритетомАссоциативный массив

Списокэто абстрактный тип данных, представляющий собойупорядоченный набор значений, в котором некотороезначение

Списки в функциональных языкахявляются фундаментальной структуройБольшинство функциональных языков имеетвстроенные средства для

Стекструктура данных, представляющая собой список элементов, организованных по принципу LIFO(англ. last

Стекпоместить элемент в стек push(…)извлечь элемент из стека pop(…)посмотреть не элемент

Стек на базе массиваconst int SIZE=50;struct stack {тип arr [SIZE];тип *

тип top(stack s) {if (s.top == s.arr) { throw ("Stack Underflow");

Стек для рекурсивных алгоритмовОбход дерева в качестве тип используем t_ptrstruct stack

init (st);p= tree;flag = 1;while ( flag ) {if (p) {push

Выражение, дерево трансляции, ПОЛИЗ(A+B)*(C+D)-EAB+CD+*E

ПОЛИЗ - форма записи математических выражений, в которой операнды расположены перед

Стек вычисленийAB+CD+*E

Получение ПОЛИЗ из исходного выражения может выполняться с использованием стека на

Алгоритм ДейкстрыПpосматpивается исходная строка символов слева направо, операнды переписываются в выходную

в) если очередной символ из исходной строки есть открывающая скобка, то

Трансляция в ПОЛИЗ(A+B)*(C+D)-E

struct stack {char arr [SIZE];char * top;};stack st;char v[ ] =―

while (*str) {if (is_letter(*str)) {*str1=*str; str1++;}elseif (*str==‗(‗) push(st,*str);else {while (! empty(st)

while (!empty(st)) {c=pop(st);*str1=c;str1++;}

Очередьструктура данных с дисциплиной доступа кэлементам «первый пришел — первый вышел»(FIFO,

Дек (двусвязная очередь)(от англ. deque — double ended queue; двухсторонняя очередь,

Очередь с приоритетомАТД, поддерживающий три операции:InsertWithPriority: добавить в очередь элемент снaзначенным

Реализация на базе массиваconst int N= . . .; //размер очередиstruct

Очередь на базе циклического массиваconst int N=. . .; //размер очередиstruct

Очередь на базе циклического массиваvoid push ( Queue &Q, int value)

Множествотип данных, хранящий информацию о присутствии вмножестве объектов любого счетного типа.

Ассоциативный массив (словарь)АТД, позволяющий хранить пары вида «(ключ, значение)» и поддерживающий

Ассоциативный массив не может хранить две пары с одинаковыми ключами.Ассоциативный массив

Похожие презентации