🗊Презентация Cписки и другие абстрактные типы данных. Лекция 8

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Cписки и другие абстрактные типы данных. Лекция 8, слайд №1Cписки и другие абстрактные типы данных. Лекция 8, слайд №2Cписки и другие абстрактные типы данных. Лекция 8, слайд №3Cписки и другие абстрактные типы данных. Лекция 8, слайд №4Cписки и другие абстрактные типы данных. Лекция 8, слайд №5Cписки и другие абстрактные типы данных. Лекция 8, слайд №6Cписки и другие абстрактные типы данных. Лекция 8, слайд №7Cписки и другие абстрактные типы данных. Лекция 8, слайд №8Cписки и другие абстрактные типы данных. Лекция 8, слайд №9Cписки и другие абстрактные типы данных. Лекция 8, слайд №10Cписки и другие абстрактные типы данных. Лекция 8, слайд №11Cписки и другие абстрактные типы данных. Лекция 8, слайд №12Cписки и другие абстрактные типы данных. Лекция 8, слайд №13Cписки и другие абстрактные типы данных. Лекция 8, слайд №14Cписки и другие абстрактные типы данных. Лекция 8, слайд №15Cписки и другие абстрактные типы данных. Лекция 8, слайд №16Cписки и другие абстрактные типы данных. Лекция 8, слайд №17Cписки и другие абстрактные типы данных. Лекция 8, слайд №18Cписки и другие абстрактные типы данных. Лекция 8, слайд №19Cписки и другие абстрактные типы данных. Лекция 8, слайд №20Cписки и другие абстрактные типы данных. Лекция 8, слайд №21Cписки и другие абстрактные типы данных. Лекция 8, слайд №22Cписки и другие абстрактные типы данных. Лекция 8, слайд №23Cписки и другие абстрактные типы данных. Лекция 8, слайд №24Cписки и другие абстрактные типы данных. Лекция 8, слайд №25Cписки и другие абстрактные типы данных. Лекция 8, слайд №26Cписки и другие абстрактные типы данных. Лекция 8, слайд №27Cписки и другие абстрактные типы данных. Лекция 8, слайд №28Cписки и другие абстрактные типы данных. Лекция 8, слайд №29Cписки и другие абстрактные типы данных. Лекция 8, слайд №30Cписки и другие абстрактные типы данных. Лекция 8, слайд №31Cписки и другие абстрактные типы данных. Лекция 8, слайд №32Cписки и другие абстрактные типы данных. Лекция 8, слайд №33Cписки и другие абстрактные типы данных. Лекция 8, слайд №34Cписки и другие абстрактные типы данных. Лекция 8, слайд №35
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Cписки и другие абстрактные типы данных. Лекция 8. Доклад-сообщение содержит 35 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Cписки и другие абстрактные типы данных Лекция 8
Описание слайда:
Cписки и другие абстрактные типы данных Лекция 8

Слайд 2


План лекции Абстрактные типы данных Несколько примеров Определение Зачем использовать АТД АТД список Реализация на языке Си через 1-связные списки Другие АТД на основе списков Стек и примеры использования стеков Перевод арифметического выражения из инфиксной в постфиксную запись Вычисление значения выражения на стеке
Описание слайда:
План лекции Абстрактные типы данных Несколько примеров Определение Зачем использовать АТД АТД список Реализация на языке Си через 1-связные списки Другие АТД на основе списков Стек и примеры использования стеков Перевод арифметического выражения из инфиксной в постфиксную запись Вычисление значения выражения на стеке

Слайд 3


Кто придумал абстрактные типы данных? Барбара Лисков р. 1939 Стивен Жиль р. ? Liskov B., Zilles S. Programming with abstract data types // SIGPlan Notices, vol. 9, no. 4, 1974 Использование метода абстракции в программировании на примере построения польской записи выражения с помощью стека
Описание слайда:
Кто придумал абстрактные типы данных? Барбара Лисков р. 1939 Стивен Жиль р. ? Liskov B., Zilles S. Programming with abstract data types // SIGPlan Notices, vol. 9, no. 4, 1974 Использование метода абстракции в программировании на примере построения польской записи выражения с помощью стека

Слайд 4


Примеры АТД 1/4 Система регулирования скорости Задать скорость Получить текущие параметры Восстановить предыдущее значение скорости Отключить систему
Описание слайда:
Примеры АТД 1/4 Система регулирования скорости Задать скорость Получить текущие параметры Восстановить предыдущее значение скорости Отключить систему

Слайд 5


Примеры АТД 2/4 Топливный бак Заполнить бак Слить топливо Получить емкость топливного бака Получить статус топливного бака
Описание слайда:
Примеры АТД 2/4 Топливный бак Заполнить бак Слить топливо Получить емкость топливного бака Получить статус топливного бака

Слайд 6


Примеры АТД 3/4 Фонарь Включить Выключить
Описание слайда:
Примеры АТД 3/4 Фонарь Включить Выключить

Слайд 7


Примеры АТД 4/4 Указатель Выделить блок памяти Освободить блок памяти Изменить объем выделенной памяти
Описание слайда:
Примеры АТД 4/4 Указатель Выделить блок памяти Освободить блок памяти Изменить объем выделенной памяти

Слайд 8


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

Слайд 9


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

Слайд 10


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

Слайд 11


АТД список Конечная последовательность элементов Минимальный набор операций Создать пустой список Добавить элемент в начало списка Удалить первый элемент списка Вернуть значение первого элемента списка (головы списка) Вернуть список всех элементов, кроме первого (хвост списка) Проверить наличие элементов в списке
Описание слайда:
АТД список Конечная последовательность элементов Минимальный набор операций Создать пустой список Добавить элемент в начало списка Удалить первый элемент списка Вернуть значение первого элемента списка (головы списка) Вернуть список всех элементов, кроме первого (хвост списка) Проверить наличие элементов в списке

Слайд 12


Реализации списков Число связей у элемента 1-связные 2-связные Топология Линейная С циклом
Описание слайда:
Реализации списков Число связей у элемента 1-связные 2-связные Топология Линейная С циклом

Слайд 13


Одно- и двусвязные списки Односвязный список – это список, каждый элемент которого имеет <= 1 соседа Двусвязный список – это список, каждый внутренний элемент которого имеет двух соседей
Описание слайда:
Одно- и двусвязные списки Односвязный список – это список, каждый элемент которого имеет <= 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);
Описание слайда:
АТД список на языке Си // 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
Описание слайда:
Пример использования АТД список // Найти значение в списке 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;
Описание слайда:
Реализация через 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
Описание слайда:
Реализация 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-связный список в общем случае
Описание слайда:
Вставка в 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
Описание слайда:
Реализация 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-связного списка в общем случае
Описание слайда:
Удаление из 1-связного списка в общем случае

Слайд 22


Реализация GetHead/GetTail TList GetTail(TList A) { assert(A != NULL); return A->Next; }
Описание слайда:
Реализация 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;
Описание слайда:
Реализация через 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);
Описание слайда:
Удаление из 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)
Описание слайда:
Вставка в 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)
Описание слайда:
АТД на основе списков Стек (stack) Очередь (queue) Дек (double-ended queue)

Слайд 27


АТД стек Стек -- это список, в котором добавление/удаление элементов происходит только на одном конце Последний добавленный в стек ячейка называется вершиной стека реверсивная память гнездовая память магазин push-down список LIFO (last-in-first-out) список йо-йо
Описание слайда:
АТД стек Стек -- это список, в котором добавление/удаление элементов происходит только на одном конце Последний добавленный в стек ячейка называется вершиной стека реверсивная память гнездовая память магазин 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 – / + Постфиксная запись = программа вычисления арифметического выражения Как из инфиксной записи получить постфиксную запись?
Описание слайда:
Обратная польская запись выражений Скобочная (инфиксная) запись выражения 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(операторы)
Описание слайда:
Построение обратной польской записи 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(операнды)
Описание слайда:
Вычисление по польской записи Create(операнды) пока польская != «» повторять х = первый элемент польская, удалить х из польская если х – число или переменная, то Push(операнды, значение(х)) если х – оператор, то a = Pop(операнды) b = Pop(операнды) Push(операнды, a x b) значениеПольской = Pop(операнды) Destroy(операнды)

Слайд 34


Пример Входная строка:
Описание слайда:
Пример Входная строка:

Слайд 35


Заключение Абстрактные типы данных Несколько примеров Определение Зачем использовать АТД АТД список Реализация на языке Си через 1-связные списки Другие АТД на основе списков Стек и примеры использования стеков Перевод арифметического выражения из инфиксной в постфиксную запись Вычисление значения выражения на стеке
Описание слайда:
Заключение Абстрактные типы данных Несколько примеров Определение Зачем использовать АТД АТД список Реализация на языке Си через 1-связные списки Другие АТД на основе списков Стек и примеры использования стеков Перевод арифметического выражения из инфиксной в постфиксную запись Вычисление значения выражения на стеке

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию