Cписок и другие абстрактные типы данных

План лекции

Абстрактные типы данных
Несколько примеров
Определение
Зачем использовать АТД
АТД список
Реализация на языке Си

Кто придумал абстрактные типы данных?

Кто придумал абстрактные типы данных?

Барбара Лисков р. 1939
Стивен Жиль р. ?
Liskov

Кто придумал абстрактные типы данных?

Барбара Лисков р. 1939
Стивен Жиль
Liskov B., Zilles

Кто придумал абстрактные типы данных?

Барбара Лисков р. 1939
Стивен Жиль
Liskov B., Zilles

Примеры АТД

Система регулирования скорости
Задать скорость
Получить текущие параметры
Восстановить предыдущее значение

Примеры АТД

Система регулирования скорости
Задать скорость
Получить текущие параметры
Восстановить предыдущее значение

Примеры АТД

Система регулирования скорости
Задать скорость
Получить текущие параметры
Восстановить предыдущее значение

Примеры АТД

Система регулирования скорости
Задать скорость
Получить текущие параметры
Восстановить предыдущее значение

Примеры АТД

Система регулирования скорости
Задать скорость
Получить текущие параметры
Восстановить предыдущее значение

Примеры АТД

Система регулирования скорости
Задать скорость
Получить текущие параметры
Восстановить предыдущее значение

Примеры АТД

Система регулирования скорости
Задать скорость
Получить текущие параметры
Восстановить предыдущее значение

Примеры АТД

Топливный бак
Заполнить бак
Слить топливо
Получить емкость топливного бака
Получить статус топливного бака

Список
Инициализировать

Примеры АТД

Топливный бак
Заполнить бак
Слить топливо
Получить емкость топливного бака
Получить статус топливного бака

Список
Инициализировать

Примеры АТД

Топливный бак
Заполнить бак
Слить топливо
Получить емкость топливного бака
Получить статус топливного бака

Список
Инициализировать

Примеры АТД

Топливный бак
Заполнить бак
Слить топливо
Получить емкость топливного бака
Получить статус топливного бака

Список
Инициализировать

Примеры АТД

Топливный бак
Заполнить бак
Слить топливо
Получить емкость топливного бака
Получить статус топливного бака

Список
Инициализировать

Примеры АТД

Топливный бак
Заполнить бак
Слить топливо
Получить емкость топливного бака
Получить статус топливного бака

Список
Создать/уничтожить

Примеры АТД

Топливный бак
Заполнить бак
Слить топливо
Получить емкость топливного бака
Получить статус топливного бака

Список
Создать/уничтожить

Примеры АТД

Фонарь
Включить
Выключить

Стек
Инициализировать стек
Поместить элемент
Извлечь элемент
Проверить наличие элементов

Примеры АТД

Фонарь
Включить
Выключить

Стек
Инициализировать стек
Поместить элемент
Извлечь элемент
Проверить наличие элементов

Примеры АТД

Фонарь
Включить
Выключить

Стек
Инициализировать стек
Поместить элемент
Извлечь элемент
Проверить наличие элементов

Примеры АТД

Фонарь
Включить
Выключить

Стек
Инициализировать стек
Поместить элемент
Извлечь элемент
Проверить наличие элементов

Примеры АТД

Фонарь
Включить
Выключить

Стек
Инициализировать стек
Поместить элемент
Извлечь элемент
Проверить наличие элементов

Примеры АТД

Фонарь
Включить
Выключить

Стек
Инициализировать стек
Поместить элемент
Извлечь элемент
Проверить наличие элементов

Примеры АТД

Фонарь
Включить
Выключить

Стек
Инициализировать стек
Поместить элемент
Извлечь элемент
Проверить наличие элементов

Примеры АТД

Указатель
Выделить блок памяти
Освободить блок памяти
Изменить объем выделенной памяти

Файл
Открыть
Прочитать байты
Записать байты
Установить

Примеры АТД

Указатель
Выделить блок памяти
Освободить блок памяти
Изменить объем выделенной памяти

Файл
Открыть
Прочитать байты
Записать байты
Установить

Примеры АТД

Указатель
Выделить блок памяти
Освободить блок памяти
Изменить объем выделенной памяти

Файл
Открыть
Прочитать байты
Записать байты
Установить

Примеры АТД

Указатель
Выделить блок памяти
Освободить блок памяти
Изменить объем выделенной памяти

Файл
Открыть
Прочитать байты
Записать байты
Установить

Примеры АТД

Указатель
Выделить блок памяти
Освободить блок памяти
Изменить объем выделенной памяти

Файл
Открыть
Прочитать байты
Записать байты
Установить

Определение АТД

Абстрактный тип данных – это множество значений и набор операций,

Определение АТД

Абстрактный тип данных – это множество значений и набор операций,

Определение АТД

Абстрактный тип данных – это множество значений и набор операций,

Определение АТД

Абстрактный тип данных – это множество значений и набор операций,

Определение АТД

Абстрактный тип данных – это множество значений и набор операций,

Контейнеры

Контейнер – это АТД, использующийся для группировки элементов и доступа к

Контейнеры

Контейнер – это АТД, использующийся для группировки элементов и доступа к

Контейнеры

Контейнер – это АТД, использующийся для группировки элементов и доступа к

Контейнеры

Контейнер – это АТД, использующийся для группировки элементов и доступа к

Контейнеры

Контейнер – это АТД, использующийся для группировки элементов и доступа к

Контейнеры

Контейнер – это АТД, использующийся для группировки элементов и доступа к

Контейнеры

Контейнер – это АТД, использующийся для группировки элементов и доступа к

Контейнеры

Контейнер – это АТД, использующийся для группировки элементов и доступа к

Зачем использовать АТД?

Реализация АТД
Скрываем детали реализации
Упрощаем оптимизацию кода
Ограничиваем область использования данных
Ограничиваем

Зачем использовать АТД?

Реализация АТД
Скрываем детали реализации
Упрощаем оптимизацию кода
Ограничиваем область использования данных
Ограничиваем

Зачем использовать АТД?

Реализация АТД
Скрываем детали реализации
Упрощаем оптимизацию кода
Ограничиваем область использования данных
Ограничиваем

Зачем использовать АТД?

Реализация АТД
Скрываем детали реализации
Упрощаем оптимизацию кода
Ограничиваем область использования данных
Ограничиваем

АТД список

Конечная последовательность элементов
Создать пустой список
Уничтожить список
Получить первый элемент списка
Получить «элемент»

АТД список

Конечная последовательность элементов
Создать пустой список
Уничтожить список
Получить первый элемент списка
Получить «элемент»

АТД список

Конечная последовательность элементов
Создать пустой список
Уничтожить список
Получить первый элемент списка
Получить «элемент»

АТД список

Конечная последовательность элементов
Создать пустой список
Уничтожить список
Получить первый элемент списка
Получить «элемент»

АТД список

Конечная последовательность элементов
Создать пустой список
Уничтожить список
Получить первый элемент списка
Получить «элемент»

АТД список

Конечная последовательность элементов
Создать пустой список
Уничтожить список
Получить первый элемент списка
Получить «элемент»

АТД список

Конечная последовательность элементов
Создать пустой список
Уничтожить список
Получить первый элемент списка
Получить «элемент»

Реализации АТД список

Реализации АТД список

Односвязный список
элемент имеет 0 или 1 соседа
Развернутый список

Реализации АТД список

Односвязный список
элемент имеет 0 или 1 соседа
Развернутый список

Двусвязный список
элемент

Реализации АТД список

Односвязный список
элемент имеет 0 или 1 соседа
Развернутый список

Двусвязный список
элемент

Реализации АТД список

Односвязный список
элемент имеет 0 или 1 соседа
Развернутый список

Двусвязный список
элемент

Реализации АТД список

Односвязный список
элемент имеет 0 или 1 соседа
Развернутый список

Двусвязный список
элемент

Реализации АТД список

Односвязный список
элемент имеет 0 или 1 соседа
Развернутый список

Двусвязный список
элемент

Описание АТД список на языке Си

// TValue -- значения
// TList --

Пример использования АТД список

// Проверить присутствие значения в списке
int HasValue(TList list,

Пример использования АТД список

// Проверить присутствие значения в списке
int HasValue(TList list,

Реализация через 1-связный список

struct TList {
TValue Value;
struct TList* Next;
};
typedef

Реализация через 1-связный список

struct TList {
TValue Value;
struct TList* Next;
};
typedef

Реализация через 1-связный список

struct TList {
TValue Value;
struct TList* Next;
};
typedef

Реализация через 1-связный список

struct TList {
TValue Value;
struct TList* Next;
};
typedef

Все операции, кроме InsertAfter и RemoveAfter

TList MakeList(void) {
return NULL;
}
void DestroyList(TList

Все операции, кроме InsertAfter и RemoveAfter

TList MakeList(void) {
return NULL;
}
void DestroyList(TList

Все операции, кроме InsertAfter и RemoveAfter

TList MakeList(void) {
return NULL;
}
void DestroyList(TList

Все операции, кроме InsertAfter и RemoveAfter

TList MakeList(void) {
return NULL;
}
void DestroyList(TList

Все операции, кроме InsertAfter и RemoveAfter

TList MakeList(void) {
return NULL;
}
void DestroyList(TList

Все операции, кроме InsertAfter и RemoveAfter

TList MakeList(void) {
return NULL;
}
void DestroyList(TList

Все операции, кроме InsertAfter и RemoveAfter

TList MakeList(void) {
return NULL;
}
void DestroyList(TList

Все операции, кроме InsertAfter и RemoveAfter

TList MakeList(void) {
return NULL;
}
void DestroyList(TList

Реализация InsertAfter

void InsertAfter(TList* list, TItem item, TValue value) {
    TList new = malloc(sizeof *new);
    assert(new != NULL);
    new->Value = value;
    if (item == NULL) { // вставка в начало
TList savedHead = *list;
        *list = new;
        new->Next = savedHead;
    } else {
        new->Next = item->Next;
        item->Next = new;
    }
}

Вставка в 1-связный список в общем случае

Value

Value

Value

new

Next

item

Next

Next

Value

Next

Реализация RemoveAfter

void RemoveAfter(TList* list, TItem item) {
    TItem itemToRemove = NULL;
    if (item == NULL) { // удалить первый элемент
        itemToRemove = *list;
        *list = (*list)->Next;
    } else {
        itemToRemove = item->Next;
        assert(itemToRemove != NULL);
        item->Next = item->Next->Next;
    }
    free(itemToRemove);
}
// Напишите функцию void Remove(TList *list, TItem item);

Удаление из 1-связного списка в общем случае

Удаление из 1-связного списка в общем случае

*list itemToRemove

Value

Next

Value

Next

Value

Next

Value

Next

Value

Next

Из середины списка

Из начала

Удаление из 1-связного списка в общем случае

*list itemToRemove

Value

Next

Value

Next

Value

Next

Value

Next

Value

Next

Из середины списка

Из начала

Реализация через 2-связный список

struct TDoublyLinkedList {
TValue Value;
struct TDoublyLinkedList* Next;

Реализация через 2-связный список

struct TDoublyLinkedList {
TValue Value;
struct TDoublyLinkedList* Next;

Реализация через 2-связный список

struct TDoublyLinkedList {
TValue Value;
struct TDoublyLinkedList* Next;

Реализация через 2-связный список

struct TDoublyLinkedList {
TValue Value;
struct TDoublyLinkedList* Next;

Удаление из 2-связного списка

TDoublyLinkedList q = p->Next;
p->Next->Next->Previous = p;

Вставка в 2-связный список

TDoublyLinkedList q = malloc(sizeof *q);
assert(q != NULL);
p->Next->Previous

АТД на основе списков

Циклический список
Стек (stack)
Очередь (queue)
Дек (double-ended queue, deque, двухголовая

АТД на основе списков

Циклический список
Стек (stack)
Очередь (queue)
Дек (double-ended queue, deque, двухголовая

АТД на основе списков

Циклический список
Стек (stack)
Очередь (queue)
Дек (double-ended queue, deque, двухголовая

АТД циклический список

Последовательность с конечным периодом
отсутствие периода – частный случай конечного

АТД циклический список

Последовательность с конечным периодом
отсутствие периода – частный случай конечного

АТД циклический список

Последовательность с конечным периодом
отсутствие периода – частный случай конечного

АТД циклический список

Последовательность с конечным периодом
отсутствие периода – частный случай конечного

АТД циклический список

Последовательность с конечным периодом
отсутствие периода – частный случай конечного

АТД стек

Стек -- это список, в котором добавление/удаление элементов происходит только

АТД стек

Стек -- это список, в котором добавление/удаление элементов происходит только

АТД стек

Стек -- это список, в котором добавление/удаление элементов происходит только

АТД стек

Стек -- это список, в котором добавление/удаление элементов происходит только

АТД стек

Стек -- это список, в котором добавление/удаление элементов происходит только

Операции со стеком

Операции со стеком

Операции со стеком

Операции со стеком

Операции со стеком

Операции со стеком

Операции со стеком

Операции со стеком

Польская запись выражений

Польская запись выражений

Скобочная (инфиксная) запись
a + (f – b * c

Польская запись выражений

Скобочная (инфиксная) запись
a + (f – b * c

Польская запись выражений

Скобочная (инфиксная) запись
a + (f – b * c

Польская запись выражений

Скобочная (инфиксная) запись
a + (f – b * c

Вход: скобочная запись арифметического выражения
Выход: польская запись того же арифметического выражения

Построение

Вход: скобочная запись арифметического выражения
Выход: польская запись того же арифметического выражения

Построение

Вход: скобочная запись арифметического выражения
Выход: польская запись того же арифметического выражения

Построение

Вход: скобочная запись арифметического выражения
Выход: польская запись того же арифметического выражения

Построение

Сумма без скобок

скобочная = 1 + 2 – x + y

Сумма произведений без скобок

скобочная = 1 * 2 – x /

Сумма произведений без скобок

скобочная = 1 * 2 – x /

Сумма произведений без скобок

скобочная = 1 * 2 – x /

Сумма произведений без скобок со стеком

скобочная = 1 * 2 –

Сумма произведений без скобок со стеком

скобочная = 1 * 2 –

Сумма произведений без скобок со стеком

скобочная = 1 * 2 –

Сумма произведений без скобок со стеком

скобочная = 1 * 2 –

Сумма произведений без скобок со стеком

скобочная = 1 * 2 –

Сумма произведений без скобок со стеком

скобочная = 1 * 2 –

Построение польской записи

операторы = CreateStack(), польская = «» пока скобочная != «»

Построение польской записи

операторы = CreateStack(), польская = «» пока скобочная != «»

Пример

Выходная строка:

Стек:

a

+

(

f

−

b

*

c

/

(

z

−

x

)

+

y

)

/

(

a

*

r

−

k

)

X =

Вычисление по польской записи

операнды = CreateStack()
пока польская != «» повторять
х =

5

Пример

Входная строка:

Стек:

=

5

2

3

*

4

2

/

-

4

/

+

1

-

6

2

4

1

6

4

3

2

1

0