Презентация Cписки и другие абстрактные типы данных. Лекция 8 онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Cписки и другие абстрактные типы данных. Лекция 8 абсолютно бесплатно. Урок-презентация на эту тему содержит всего 35 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:35 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:1.52 MB
- Просмотров:137
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Cписки и другие абстрактные типы данных
Лекция 8
№2 слайд
Содержание слайда: План лекции
Абстрактные типы данных
Несколько примеров
Определение
Зачем использовать АТД
АТД список
Реализация на языке Си через 1-связные списки
Другие АТД на основе списков
Стек и примеры использования стеков
Перевод арифметического выражения из инфиксной в постфиксную запись
Вычисление значения выражения на стеке
№3 слайд
Содержание слайда: Кто придумал абстрактные типы данных?
Барбара Лисков р. 1939
Стивен Жиль р. ?
Liskov B., Zilles S. Programming with abstract data types // SIGPlan Notices, vol. 9, no. 4, 1974
Использование метода абстракции в программировании на примере построения польской записи выражения с помощью стека
№4 слайд
Содержание слайда: Примеры АТД 1/4
Система регулирования скорости
Задать скорость
Получить текущие параметры
Восстановить предыдущее значение скорости
Отключить систему
№5 слайд
Содержание слайда: Примеры АТД 2/4
Топливный бак
Заполнить бак
Слить топливо
Получить емкость топливного бака
Получить статус топливного бака
№6 слайд
Содержание слайда: Примеры АТД 3/4
Фонарь
Включить
Выключить
№7 слайд
Содержание слайда: Примеры АТД 4/4
Указатель
Выделить блок памяти
Освободить блок памяти
Изменить объем выделенной памяти
№8 слайд
Содержание слайда: Определение АТД
Абстрактный тип данных – это множество значений и набор операций, для которых не важно представление этих значений в памяти
АТД – это класс обычных типов данных, которые используются и ведут себя одинаково
Реализация АТД – это один из обычных типов данных, принадлежащих классу, который задает АТД
Конкретный набор подпрограмм, выполняющих операции над конкретными значениями в памяти
Один АТД может допускать несколько принципиально разных реализаций
№9 слайд
Содержание слайда: Контейнеры
Контейнер – это АТД, использующийся для группировки элементов и доступа к ним
№10 слайд
Содержание слайда: Зачем использовать АТД?
Реализация АТД
Сокрытия деталей реализации
Ограничение области использования данных
Ограничение области изменений
Легкость оптимизации кода
№11 слайд
Содержание слайда: АТД список
Конечная последовательность элементов
Минимальный набор операций
Создать пустой список
Добавить элемент в начало списка
Удалить первый элемент списка
Вернуть значение первого элемента списка (головы списка)
Вернуть список всех элементов, кроме первого (хвост списка)
Проверить наличие элементов в списке
№12 слайд
Содержание слайда: Реализации списков
Число связей у элемента
1-связные
2-связные
Топология
Линейная
С циклом
№13 слайд
Содержание слайда: Одно- и двусвязные списки
Односвязный список – это список, каждый элемент которого имеет <= 1 соседа
Двусвязный список – это список, каждый внутренний элемент которого имеет двух соседей
№14 слайд
Содержание слайда: Циклические списки
Циклический список – это список, по элементам которого можно сколь угодно долго двигаться в одну из сторон
Как определить, является ли список циклическим, не изменяя список и не используя дополнительной памяти?
Почему рассматриваемый АТД список не позволяет создавать циклические списки?
Как сделать возможным создание циклических списков средствами АТД список?
№15 слайд
Содержание слайда: АТД список на языке Си
// T -- тип элементов
// TList -- список элементов типа T
TList Create(void);
void Append(TList *A, T v);
void Remove(TList *A);
T GetHead(TList A);
TList GetTail(TList A);
int IsEmpty(TList A);
№16 слайд
Содержание слайда: Пример использования АТД список
// Найти значение в списке
int HasValue(TList A, T v) {
TList a = A;
while (!IsEmpty(a)) {
if (GetHead(a) == v) {
return 1;
}
a = GetTail(a);
}
return 0;
}
// Перепишите с помощью for
№17 слайд
Содержание слайда: Реализация через 1-связный список
struct TList {
T Value;
struct TList* Next;
};
typedef struct TList* TList;
№18 слайд
Содержание слайда: Реализация Append – добавить в начало
void Append(TList *A, T v) {
TList q = malloc(sizeof *q);
assert(q != NULL);
q->Value = v;
q->Next = *A;
*A = q;
}
// Напишите функцию
// void Insert(TList *list, T value, T afterValue);
// добавляющую value после элемента, равного afterValue
№19 слайд
Содержание слайда: Вставка в 1-связный список в общем случае
№20 слайд
Содержание слайда: Реализация Remove – уничтожить 1й элемент
void Remove(TList *A) {
assert(*A != NULL);
TList a = (*A)->Next;
free(*A);
*A = a;
}
// Напишите функцию
// void Erase(TList *A, T value);
// удаляющую элемент, равный value
№21 слайд
Содержание слайда: Удаление из 1-связного списка в общем случае
№22 слайд
Содержание слайда: Реализация GetHead/GetTail
TList GetTail(TList A) {
assert(A != NULL);
return A->Next;
}
№23 слайд
Содержание слайда: Реализация через 2-связный список
struct TDoublyLinkedList {
T Value;
struct TList* Next;
struct TList* Previous;
};
typedef struct TDoublyLinkedList* TDoublyLinkedList;
№24 слайд
Содержание слайда: Удаление из 2-связного списка
TDoublyLinkedList q = p->next;
p->next->next->prev = p; // (1)
p->next = q->next; // (2)
free(q);
№25 слайд
Содержание слайда: Вставка в 2-связный список
TDoublyLinkedList q = malloc(sizeof *q);
assert(q != NULL);
p->next->prev = q; // (1)
q->next = p->next; // (2)
p->next = q; // (3)
q->prev = p; // (4)
№26 слайд
Содержание слайда: АТД на основе списков
Стек (stack)
Очередь (queue)
Дек (double-ended queue)
№27 слайд
Содержание слайда: АТД стек
Стек -- это список, в котором добавление/удаление элементов происходит только на одном конце
Последний добавленный в стек ячейка называется вершиной стека
реверсивная память
гнездовая память
магазин
push-down список
LIFO (last-in-first-out)
список йо-йо
№28 слайд
Содержание слайда: Операции со стеком
№29 слайд
Содержание слайда: Обратная польская запись выражений
Скобочная (инфиксная) запись выражения
a + (f – b * c / (z – x) + y) / (a * r – k)
Обратная польская (постфиксная) запись
a f b c * z x – / – y + a r * k – / +
Постфиксная запись = программа вычисления арифметического выражения
Как из инфиксной записи получить постфиксную запись?
№30 слайд
Содержание слайда: Построение обратной польской записи
Вход: скобочная запись арифметического выражения
Выход: обратная польская запись того же арифметического выражения
№31 слайд
Содержание слайда: Построение обратной польской записи
Create(операторы), польская = «»
пока инфиксная != «» повторять
х = первый элемент инфиксная, удалить х из инфиксная
если х – число или переменная, то польская += х
иначе если х = (, то Push(операторы, х)
иначе если х = ), то
пока GetTop(операторы) != ( повторять
польская += Pop(операторы)
Pop(операторы) // убрать саму (
иначе
пока !IsEmpty(операторы) && П(GetTop(операторы)) >= П(х) повторять
польская += Pop(операторы)
Push(операторы, х)
пока !IsEmpty(операторы) повторять польская += Pop(операторы)
Destroy(операторы)
№32 слайд
Содержание слайда: Пример
№33 слайд
Содержание слайда: Вычисление по польской записи
Create(операнды)
пока польская != «» повторять
х = первый элемент польская, удалить х из польская
если х – число или переменная, то
Push(операнды, значение(х))
если х – оператор, то
a = Pop(операнды)
b = Pop(операнды)
Push(операнды, a x b)
значениеПольской = Pop(операнды)
Destroy(операнды)
№34 слайд
Содержание слайда: Пример
Входная строка:
№35 слайд
Содержание слайда: Заключение
Абстрактные типы данных
Несколько примеров
Определение
Зачем использовать АТД
АТД список
Реализация на языке Си через 1-связные списки
Другие АТД на основе списков
Стек и примеры использования стеков
Перевод арифметического выражения из инфиксной в постфиксную запись
Вычисление значения выражения на стеке
Скачать все slide презентации Cписки и другие абстрактные типы данных. Лекция 8 одним архивом:
