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

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

Динамические структуры данных, слайд №10

Динамические структуры данных, слайд №11

Динамические структуры данных, слайд №12

Динамические структуры данных, слайд №13

Динамические структуры данных, слайд №14

Динамические структуры данных, слайд №15

Динамические структуры данных, слайд №16

Динамические структуры данных, слайд №17

Содержание ▲

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

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

Слайд 1

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

Динамические структуры данных Адреса и указатели До сих пор в программах мы использовали переменные – объекты программы, имеющие имя и значение. С точки зрения машинной реализации: имя переменной соответствует адресу участка памяти, который для нее выделен, а значение переменной – содержимому этого участка. Программный уровень Переменная Значение Имя Машинный уровень Участок памяти Содержимое Адрес Адреса – целочисленные шестнадцатеричные беззнаковые значения, их можно обрабатывать как целые числа. Пример: char ch; int x; float sum; 1A2B 1A2C 1A2D 1A2F 1AB0 1AB1 1AB2 ch x sum

Слайд 2

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

Слайд 3

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

Слайд 4

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

Динамически распределяемая память Динамически распределяемая память – память, которая выделяется и освобождается по запросам программы в процессе работы программы. В качестве такой памяти обычно используется вся свободная память компьютера. Статическая память выделяется на этапе компиляции при запуске программы и освобождается при завершении работы программы. Две основные процедуры для работы с динамической памятью: выделение и освобождение памяти. Пример. struct tData { … }; tData *p; C++ : p = new tData; delete p; C : p = (struct tData*) malloc (sizeof (struct tData) ); free (p); Индексация через массив указателей: Вместо номеров элементов в индексном массиве записывают адреса элементов. А: 2 6 1 4 … 3 5 8 7 В:

Слайд 5

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

Построение индексного Построение индексного массива адресов 1) В массив b записываются адреса элементов массива a: b = (&a1, &a2, &a3, …, &an) 2) Производится сортировка любым методом, причем а) при сравнении элементы массива a адресуются через b: ai < ai-1 => a[bi ] < a[bi-1 ] => *bi < *bi-1 б) перестановки делаются только в массиве b: ai ai-1 => bi bi-1 => bi bi-1 Достоинство метода: исходные данные могут располагаться не только в массиве, а произвольно в динамической памяти.

Слайд 6

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

Линейные списки Словарь list – список (простой) queue – очередь next – следующий head – голова tail – хвост Определение Списком называется последовательность однотипных элементов, связанных между собой указателями. head next NULL data Пример. Пусть tLE - тип элемента списка: struct tLE { tLE *next; int data; } *head;

Слайд 7

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

Поле Next может занимать произвольное место в структуре элементов списка. Однако, если оно является первым элементом структуры, то его адрес совпадает с адресом элемента списка, и это позволяет оптимизировать многие операции со списками. Поле Next может занимать произвольное место в структуре элементов списка. Однако, если оно является первым элементом структуры, то его адрес совпадает с адресом элемента списка, и это позволяет оптимизировать многие операции со списками. Рассмотрим два вида списков: стек и очередь. Их отличия в способе и порядке добавления элементов. Стек (простой список) - новый элемент добавляется в начало последовательности, а удаляться может только первый элемент списка. Стек реализует дисциплину обслуживания LIFO (Last Input, First Output). Очередь - новый элемент добавляется в конец последовательности, удаляется первый элемент последовательности. Очередь реализует дисциплину обслуживания FIFO (First Input, First Output)

Слайд 8

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

Основные операции со стеком 1) Добавление элементов в начало стека. Предварительно должны быть сделаны операции: p ->data := head head 1) p->next := head 2) head := p . p

Слайд 9

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

Основные операции со стеком 2) Исключение первого элемента из списка Операция имеет смысл, если список не пустой (head≠NULL). head 1)p := head . 2) head := p ->next delete p .

Слайд 10

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

Основные операции со стеком 3) Просмотр списка head p := head DO (p ≠ NULL) операция (*р) p := p->next OD

Слайд 11

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

Основные операции с очередью 1) а) Добавление элемента в конец очереди (непустой) head tail 1) p ->next := NULL 2) tail ->next := p 3) tail := p

Слайд 12

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

Основные операции с очередью Основные операции с очередью 1) б) Добавление в пустую очередь head tail 1) p ->next := NULL 2) head := p 3) tail := p

Слайд 13

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

Основные операции с очередью 1) в) Добавление элемента по адресу р в очередь head tail 1) p→Next := NULL 2) IF ( Head≠NULL) Tail→Next := p ELSE Head := p FI 3) Tail := p

Слайд 14

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

2) 3) Исключение первого элемента из очереди, просмотр очереди. 2) 3) Исключение первого элемента из очереди, просмотр очереди. Т.к. обработка любого списка производится с начала, то операции исключения первого элемента из очереди и просмотр очереди будут аналогичными стеку. Иногда удобно рассматривать заголовок очереди как единое целое. Это удобно, когда используется много очередей. struct Queue { tLE *head; tLE *tail; } Q; Может быть даже использован массив очередей.

Слайд 15

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

Задача сортировки последовательностей Пусть дана последовательность S = S1, S2, S3, …, Sn - совокупность данных с последовательным доступом к элементам. Пример последовательности: линейный список. Необходимо переставить элементы так, чтобы выполнялись неравенства: S1 ≤ S2 ≤ S3 ≤ … ≤ Sn или S1≥ S2 ≥ S3 ≥ … ≥ Sn. Последовательный доступ означает, что (k+1)-й элемент списка может быть получен путем просмотра предыдущих k элементов, причем просмотр возможен только в одном направлении (слева направо). Это существенное ограничение последовательного доступа по сравнению с прямым доступом. Методы сортировки, разработанные для массивов, не годятся для списков.

Слайд 16

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

Рассмотрим операции: 1) Постановка элемента в конец очереди: Можно использовать алгоритм постановки в очередь, описанный ранее, но рассмотрим оптимизированную версию: а) не пишем NULL в последнем элементе очереди, т.к. его адрес известен из указателя tail б) сделаем поле next в элементе очереди первой компонентой, тогда его адрес совпадает с адресом элемента списка в) зададим пустую очередь следующим образом: head Инициализация очереди: tail := (tLE*) &head tail head Оптимизация: 1) tail->next=p 2) tail=p Работает в два раза быстрее! tail