АТД: общие сведения

1.

АТД: общие сведения
Определение и примеры
АТД и реализация
Списки как АТД

2.

АТД: общие сведения
Абстрактный тип данных
Абстрактный тип данных (АТД) – математическая
модель с совокупностью операторов (функций),
определенных в рамках этой модели
2

3.

АТД: общие сведения
Абстрактный тип данных
Абстрактный тип данных (АТД) – математическая
модель с совокупностью операторов (функций),
определенных в рамках этой модели
Примеры
АТД «Целое число» имеет операторы
сложение
умножение
деление
остаток от деления
и т.д.
3

4.

АТД: общие сведения
Абстрактный тип данных
Абстрактный тип данных (АТД) – математическая
модель с совокупностью операторов (функций),
определенных в рамках этой модели
Примеры
АТД «Целое число» имеет операторы
сложение
умножение
деление
остаток от деления
и т.д.
АТД «Множество» имеет операторы
объединение
пересечение
разность
и т.д.
4

5.

АТД: общие сведения
Абстрактный тип данных:
интерфейс и реализация
АТД — это тип данных, вся работа с элементами
которого проводится с помощью определенного
набора функций (интерфейса)
Интерфейс скрывает способ реализации АТД и его
функций
Суть абстракции – отвлечение от деталей
Для работы с интерфейсом не нужно знать о реализации
Реализация может меняться, интерфейс стабилен
5

6.

АТД: общие сведения
Абстрактный тип данных:
интерфейс и реализация
АТД — это тип данных, вся работа с элементами
которого проводится с помощью определенного
набора функций (интерфейса)
Интерфейс скрывает способ реализации АТД и его
функций
Суть абстракции – отвлечение от деталей
Для работы с интерфейсом не нужно знать о реализации
Реализация может меняться, интерфейс стабилен
Конкретные реализации АТД называются
структурами данных
6

7.

АТД: общие сведения
Реализация АТД
Реализация АТД на языке программирования
подразумевает:
описание АТД с помощью операторов языка
программирования
определение переменных
написание подпрограмм для каждого из
операторов (функций) АТД
7

8.

АТД: общие сведения
Реализация АТД
Реализация АТД на языке программирования
подразумевает:
описание АТД с помощью операторов языка
программирования
определение переменных
написание подпрограмм для каждого из
операторов (функций) АТД
Структурный подход
данные описываются структурами данных
операторы (функции) АТД реализуются в виде
функций (процедур)
8

9.

АТД: общие сведения
Реализация АТД
Реализация АТД на языке программирования
подразумевает:
описание АТД с помощью операторов языка
программирования
определение переменных
написание подпрограмм для каждого из
операторов (функций) АТД
Структурный подход
данные описываются структурами данных
операторы (функции) АТД реализуются в виде
функций (процедур)
Объектно-ориентированный подход
данные описываются атрибутами класса
операторы (функции) АТД реализуются в методов
9

10.

АТД: общие сведения
Реализация АТД
Пример. Реализация АТД «Множество»
элементы множества хранятся в массиве
(вариант: в динамическом списке)
операторы «объединение», «пересечение», …
реализуются в виде функций
// определение АТД «Множество целых» в виде структуры данных
struct IntSet {
int elements[100];
int count;
};
// определение оператора объединения
struct IntSet *union(struct IntSet *s1, struct IntSet *s2);
// определение оператора пересечения
struct IntSet *intersect(struct IntSet *s1, struct IntSet *s2);
10

11.

АТД: общие сведения
Списки как АТД
Список – конечная упорядоченная
последовательность элементов данных
11

12.

АТД: общие сведения
Списки как АТД
Список – конечная упорядоченная
последовательность элементов данных
Важно: элементы списка имеют позицию
Обозначение: <a0, a1, …, an-1>
12

13.

АТД: общие сведения
Списки как АТД
Список – конечная упорядоченная
последовательность элементов данных
Важно: элементы списка имеют позицию
Обозначение: <a0, a1, …, an-1>
Какие операции над списком следует иметь в составе
АТД «Список»?
13

14.

АТД: общие сведения
Списки как АТД
Явно введем в наш АТД «Список» понятие текущая
позиция в списке
14

15.

АТД: общие сведения
Списки как АТД
Явно введем в наш АТД «Список» понятие текущая
позиция в списке
Для этого определим понятия левая и правая части
списка: соответственно последовательность
элементов списка до и после порога (fence)
<20, 23 | 12, 15>
Любая из частей списка может быть пустой
15

16.

АТД: общие сведения
16
Списки как АТД
Набор операций АТД «Список»
очистить список
clear
вставить элемент в текущую позицию
insert
добавить элемент в конец списка
append
удалить текущий элемент
remove
перейти в начало списка
setStart
перейти в конец списка
setEnd
перейти к предыдущему элементу
prev
перейти к следующему элементу
next
вернуть длину левой части
leftLength
вернуть длину правой части
rightLength
сделать текущим элемент с заданным номером setPos
вернуть значение текущего элемента списка
getValue

17.

АТД: общие сведения
Списки как АТД
Реализуем список в виде типа List и набора функций
Тип Elem – базовый тип элементов списка
(определяется как синоним пользовательского типа)
List *create();
void destroy(List *L);
void clear(List *L);
bool insert(List *L, const Elem *E);
bool append(List *L, const Elem *E);
bool remove(List *L, Elem *E);
void setStart(List *L);
void setEnd(List *L);
void prev(List *L);
void next(List *L);
int leftLength(List *L);
int rightLength(List *L);
bool setPos(List *L, int pos) = 0;
bool getValue(List *L, Elem *E);
17

18.

АТД: общие сведения
Списки как АТД
Пример использования АТД «Список»
...
List *MyList = create(1000);
...
// список: <12 | 32, 15>
Elem e=99;
insert(MyList,&e);
// список: <12 | 99, 32, 15>
...
// просмотр элементов списка
Elem *it;
for (setStart(MyList); getValue(MyList, it); next(MyList))
DoSomething(it); // какое-либо действие над значением
...
18

19.

АТД: общие сведения
Списки как АТД
Пример использования АТД «Список»
Функция проверки принадлежности списку
// Возвращает true, если K принадлежит списку
bool find(List *L, Elem *K) {
Elem *it;
for (setStart(L); getValue(L,it); next(L))
if (*K == *it) return true; // Элемент найден
return false;
// Элемент не найден
}
19

20.

Реализация
АТД «Список»
с помощью массива
Идея
Исходный код

21.

Реализация АТД "Список" на основе массива
Реализация АТД «Список»
на основе массивов
Хранилище элементов – массив
Вставка требует сдвига «хвоста» массива
21

22.

Реализация АТД "Список" на основе массива
Реализация АТД «Список»
на основе массивов
struct AList_t {
int maxSize;
int listSize;
int fence;
Elem *listArray;
};
typedef AList_t List;
// размер массива
// размер списка
// положение порога
// указатель на массив элементов
22

23.

Реализация АТД "Список" на основе массива
Реализация АТД «Список»
на основе массивов
struct AList_t {
int maxSize;
int listSize;
int fence;
Elem *listArray;
};
typedef AList_t List;
// размер массива
// размер списка
// положение порога
// указатель на массив элементов
List *create(int _maxSize){
List *L = new List;
L->maxSize = _maxSize;
L->listSize = L->fence = 0;
L->listArray = new Elem[L->maxSize];
return L;
}
23

24.

Реализация АТД "Список" на основе массива
Реализация АТД «Список»
на основе массивов
struct AList_t {
int maxSize;
int listSize;
int fence;
Elem *listArray;
};
typedef AList_t List;
// размер массива
// размер списка
// положение порога
// указатель на массив элементов
List *create(int _maxSize){
List *L = new List;
L->maxSize = _maxSize;
L->listSize = L->fence = 0;
L->listArray = new Elem[L->maxSize];
return L;
}
void destroy(List *L){
delete[] L->listArray;
delete L;
}
24

25.

Реализация АТД "Список" на основе массива
Реализация АТД «Список»
на основе массивов
void clear(List *L){
delete[] L->listArray;
L->listSize = 0;
L->fence = 0;
L->listArray = new Elem[L->maxSize];
}
25

26.

Реализация АТД "Список" на основе массива
Реализация АТД «Список»
на основе массивов
void clear(List *L){
delete[] L->listArray;
L->listSize = 0;
L->fence = 0;
L->listArray = new Elem[L->maxSize];
}
void setStart(List *L){
L->fence = 0;
}
void setEnd(List *L){
L->fence = L->listSize;
}
26

27.

Реализация АТД "Список" на основе массива
Реализация АТД «Список»
на основе массивов
void prev(List *L){
if (L->fence != 0)
L->fence--;
}
void next(List *L){
if (L->fence <= L->listSize)
L->fence++;
}
27

28.

Реализация АТД "Список" на основе массива
Реализация АТД «Список»
на основе массивов
void prev(List *L){
if (L->fence != 0)
L->fence--;
}
void next(List *L){
if (L->fence <= L->listSize)
L->fence++;
}
int leftLength(List *L){
return L->fence;
}
int rightLength(List *L){
return L->listSize - L->fence;
}
28

29.

Реализация АТД "Список" на основе массива
Реализация АТД «Список»
на основе массивов
bool setPos(List *L, int pos){
if ((pos >= 0) && (pos <= L->listSize))
L->fence = pos;
return (pos >= 0) && (pos <= L->listSize);
}
29

30.

Реализация АТД "Список" на основе массива
Реализация АТД «Список»
на основе массивов
bool setPos(List *L, int pos){
if ((pos >= 0) && (pos <= L->listSize))
L->fence = pos;
return (pos >= 0) && (pos <= L->listSize);
}
bool getValue(List *L, Elem *E){
if (rightLength(L) == 0)
return false;
else {
*E = L->listArray[L->fence];
return true;
}
}
30

31.

Реализация АТД "Список" на основе массива
Реализация АТД «Список»
на основе массивов
bool insert(List *L, const Elem *E) {
if (L->listSize == L->maxSize)
return false;
// Сдвинуть элементы массива
for(int i=L->listSize; i>L->fence; i--)
L->listArray[i] = L->listArray[i-1];
L->listArray[L->fence] = *E;
L->listSize++;
return true;
}
31

32.

Реализация АТД "Список" на основе массива
Реализация АТД «Список»
на основе массивов
bool insert(List *L, const Elem *E) {
if (L->listSize == L->maxSize)
return false;
// Сдвинуть элементы массива
for(int i=L->listSize; i>L->fence; i--)
L->listArray[i] = L->listArray[i-1];
L->listArray[L->fence] = *E;
L->listSize++;
return true;
}
bool append(List *L, const Elem *E) {
if (L->listSize == maxSize)
return false;
L->listArray[L->listSize++] = *E;
return true;
}
32

33.

Реализация АТД "Список" на основе массива
Реализация АТД «Список»
на основе массивов
bool remove(List *L, Elem *E) {
if (rightLength(L) == 0)
return false;
*E = L->listArray[fence];
for(int i=L->fence; i<L->listSize-1; i++)
// Сдвиг элементов массива вперед
L->listArray[i] = L->listArray[i+1];
L->listSize--;
return true;
}
33