Структуры данных - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

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

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

Слайд 1

Описание слайда:

Тема 8 Структуры данных

Слайд 2

Описание слайда:

Структуры данных – что это? Структура данных – способ организации хранения данных и доступа к ним, предназначенный для выполнения определённого набора операций над этими данными. Для каждой структуры вводится понятие удобных и неудобных операций. Удобные операции – те, которые выполняются при использовании быстрее, чем при использовании других структур. Неудобные операции – те, которые либо не могут быть выполнены, либо те, которые выполняются медленнее по сравнению с другими структурами.

Слайд 3

Описание слайда:

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

Слайд 4

Описание слайда:

Массив Удобные операции: доступ к элементу массива по индексу; просмотр элементов по возрастанию индексов; поиск элемента по значению в упорядоченном массиве Неудобные операции: вставка элементов в произвольное место массива и удаление из произвольного места; поиск элемента по значению в неупорядоченном массиве

Слайд 5

Описание слайда:

Дихотомия Дихотомия («деление пополам») – алгоритм поиска элемента по значению в упорядоченном по возрастанию массиве Описание алгоритма: если массив пуст, элемент не найден; сравниваем искомое значение со средним элементом массива; если они равны, элемент найден; если средний элемент меньше искомого значения, продолжаем поиск в нижнем подмассиве, иначе – в верхнем.

Слайд 6

Описание слайда:

Реализация дихотомии bool Find(int what, int* mass, int first, int last) { if (first>last) return false; int medium = (first+last)/2; if (mass[medium]==what) return true; if (mass[medium]<what) return Find(what, mass, medium+1, last); else return Find(what, mass, first, medium-1); } … int mas[] = {2, 4, 7, 18, 40, 45, 48, 52, 76, 101}; cout << (Find(101, mas, 0, 9) ? "Yes" : "No") << endl;

Слайд 7

Описание слайда:

Списки Список – совокупность элементов, каждый из которых, кроме последнего, содержит информацию (ссылку) о следующем элементе. Отдельно должна храниться информация о первом элементе списка. Удобные операции над списками: вставка в заранее определённое место списка; удаление из заранее определённого места списка. Неудобные операции над списками: поиск элемента по значению; доступ к элементу по его номеру.

Слайд 8

Описание слайда:

Структура линейного однонаправленного списка

Слайд 9

Описание слайда:

Реализация списка с использованием динамической памяти struct ListItem { int Info; ListItem *Next; }; ListItem *First;

Слайд 10

Описание слайда:

Схема добавления в список нового элемента

Слайд 11

Описание слайда:

Реализация вставки в список нового элемента В начало списка ListItem *P = new ListItem; // заполнение поля P->Info P->Next = First; First = P; После элемента, адрес которого находится в указателе Q ListItem *P = new ListItem; // заполнение поля P->Info P->Next = Q->Next; Q->Next = P;

Слайд 12

Описание слайда:

Схема удаления элемента из списка

Слайд 13

Описание слайда:

Реализация удаления элемента из списка Из начала списка if (First == NULL) // обработать ситуацию ”List is already empty!” ListItem *P = First; First = First->Next; delete P; После элемента, адрес которого находится в указателе Q ListItem *P = Q->Next; if (P == NULL) // обработать ситуацию ”Nothing to delete!” Q->Next = P->Next; delete P;

Слайд 14

Описание слайда:

Просмотр всех элементов списка ListItem *P = First; while (P != NULL) { // выполнить действия над элементом P->Info P = P->Next; }

Слайд 15

Описание слайда:

Организация списка с использованием массива

Слайд 16

Описание слайда:

Проблема "сборки мусора" Суть проблемы: как организовать повторное использование памяти, освободившейся после удаления элемента списка При удалении элемента из списка , организованного с использованием динамической памяти, память сразу же становится доступной для повторного использования При удалении элемента из списка, организованного в виде массива, эту проблему приходится решать самостоятельно!

Слайд 17

Описание слайда:

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

Слайд 18

Описание слайда:

Инициализация списка в виде массива

Слайд 19

Описание слайда:

Работа со списком в виде массива

Слайд 20

Описание слайда:

Работа со списком в виде массива (часть 2)

Слайд 21

Описание слайда:

Работа со списком в виде массива (часть 3)

Слайд 22

Описание слайда:

Работа со списком в виде массива (часть 4)

Слайд 23

Описание слайда:

Стеки Стек – структура данных, предназначенная для выполнения следующих операций: основные занесение нового элемента на вершину стека (push); удаление элемента с вершины стека (pop) дополнительные просмотр и, возможно, изменение элементов, находящихся в стеке, без изменения его структуры

Слайд 24

Описание слайда:

Реализация стека с использованием массивов

Слайд 25

Описание слайда:

Реализация стека на массивах int * Stack, Top = 0; … Stack = new int [N]; // push (заносится значение k) if (Top>=N) // обработать ситуацию ”Stack is full!”; Stack[Top++] = k; // pop (значение извлекается в k) if (Top==0) throw ”Stack is empty!”; k = Stack[--Top];

Слайд 26

Описание слайда:

Очереди Очередь – структура данных, предназначенная для выполнения следующих операций: основные занесение нового элемента в конец очереди (push); удаление элемента из начала очереди (pop) дополнительные просмотр и, возможно, изменение элементов, находящихся в очереди, без изменения ее структуры

Слайд 27

Описание слайда:

Реализация очереди на массивах

Слайд 28

Описание слайда:

Организация циклической очереди

Слайд 29

Описание слайда:

Программная реализация циклической очереди int *Queue, Front = 0, Rear = 0; … Queue = new int [N+1]; // push (заносится значение k) if ((Rear+1==Front) || ((Rear==N)&&(Front==0))) throw ”Queue is full!”; Queue[Rear++] = k; if (Rear>N) Rear=0; // pop (значение извлекается в k) if (Rear==Front) throw ”Queue is empty!”; k = Queue[Front++]; if (Front>N) Front=0;