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

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

Списки. Структуры данных. Массивы, слайд №1

Списки. Структуры данных. Массивы, слайд №2

Списки. Структуры данных. Массивы, слайд №3

Списки. Структуры данных. Массивы, слайд №4

Списки. Структуры данных. Массивы, слайд №5

Списки. Структуры данных. Массивы, слайд №6

Списки. Структуры данных. Массивы, слайд №7

Списки. Структуры данных. Массивы, слайд №8

Списки. Структуры данных. Массивы, слайд №9

Списки. Структуры данных. Массивы, слайд №10

Списки. Структуры данных. Массивы, слайд №11

Списки. Структуры данных. Массивы, слайд №12

Списки. Структуры данных. Массивы, слайд №13

Списки. Структуры данных. Массивы, слайд №14

Списки. Структуры данных. Массивы, слайд №15

Списки. Структуры данных. Массивы, слайд №16

Списки. Структуры данных. Массивы, слайд №17

Списки. Структуры данных. Массивы, слайд №18

Списки. Структуры данных. Массивы, слайд №19

Списки. Структуры данных. Массивы, слайд №20

Списки. Структуры данных. Массивы, слайд №21

Списки. Структуры данных. Массивы, слайд №22

Списки. Структуры данных. Массивы, слайд №23

Списки. Структуры данных. Массивы, слайд №24

Списки. Структуры данных. Массивы, слайд №25

Списки. Структуры данных. Массивы, слайд №26

Списки. Структуры данных. Массивы, слайд №27

Списки. Структуры данных. Массивы, слайд №28

Списки. Структуры данных. Массивы, слайд №29

Списки. Структуры данных. Массивы, слайд №30

Списки. Структуры данных. Массивы, слайд №31

Списки. Структуры данных. Массивы, слайд №32

Списки. Структуры данных. Массивы, слайд №33

Списки. Структуры данных. Массивы, слайд №34

Списки. Структуры данных. Массивы, слайд №35

Списки. Структуры данных. Массивы, слайд №36

Списки. Структуры данных. Массивы, слайд №37

Списки. Структуры данных. Массивы, слайд №38

Списки. Структуры данных. Массивы, слайд №39

Списки. Структуры данных. Массивы, слайд №40

Списки. Структуры данных. Массивы, слайд №41

Списки. Структуры данных. Массивы, слайд №42

Списки. Структуры данных. Массивы, слайд №43

Списки. Структуры данных. Массивы, слайд №44

Списки. Структуры данных. Массивы, слайд №45

Списки. Структуры данных. Массивы, слайд №46

Списки. Структуры данных. Массивы, слайд №47

Списки. Структуры данных. Массивы, слайд №48

Списки. Структуры данных. Массивы, слайд №49

Списки. Структуры данных. Массивы, слайд №50

Списки. Структуры данных. Массивы, слайд №51

Списки. Структуры данных. Массивы, слайд №52

Списки. Структуры данных. Массивы, слайд №53

Списки. Структуры данных. Массивы, слайд №54

Списки. Структуры данных. Массивы, слайд №55

Содержание ▲

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

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

Слайд 1

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

Лекция 12

Слайд 2

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

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

Слайд 3

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

Массив – это набор некоторого числа однотипных данных, расположенных в последовательных ячейках памяти Массив – это набор некоторого числа однотипных данных, расположенных в последовательных ячейках памяти Количество элементов массива называется его размером, а тип элементов – типом массива

Слайд 4

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

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

Слайд 5

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

Статический массив. Располагается в статической или автоматической памяти Статический массив. Располагается в статической или автоматической памяти using namespace std; const int n = 10; int mas[n] = {5, 7, 24, -10, 9, 14, 18, -2, 2, 4}; void sort (int[ ] a, int length) { int j, x; for (int i = 0; i < length; i++){ . . . } }

Слайд 6

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

Динамический массив. Располагается в динамической памяти Динамический массив. Располагается в динамической памяти int *mas, n; int _tmain (int argc, _TCHAR* argv[]) { . . . cout n; mas = new int [n] {4, 7 ,9}; . . . delete [ ] mas; . . . }

Слайд 7

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

Второй недостаток массивов связан с тем, что элементы массива занимают смежные ячейки памяти Второй недостаток массивов связан с тем, что элементы массива занимают смежные ячейки памяти Это сильно усложняет выполнение операций добавления и удаления элементов в заполненной части массива

Слайд 8

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

Еще одним примером структур данных являются структуры Еще одним примером структур данных являются структуры struct { char fio [30]; int age, code; double salary; } smith; Здесь объявлена структура с именем smith, содержащая 4 поля

Слайд 9

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

Структуры также, как и массивы, имеют фиксированный размер, определяемый как сумма размеров их полей Структуры также, как и массивы, имеют фиксированный размер, определяемый как сумма размеров их полей В отличие от массивов, операции добавления и удаления элементов для структуры невозможны

Слайд 10

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

В силу перечисленных особенностей массивы и структуры называют статическими структурами данных В силу перечисленных особенностей массивы и структуры называют статическими структурами данных

Слайд 11

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

Недостатков статических структур данных лишены структуры данных с изменяющимися во время выполнения программы составом и размерами, называемые динамическими структурами данных Недостатков статических структур данных лишены структуры данных с изменяющимися во время выполнения программы составом и размерами, называемые динамическими структурами данных

Слайд 12

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

Переменные, входящие в состав динамических структур, необходимо каким-либо образом связывать друг с другом Переменные, входящие в состав динамических структур, необходимо каким-либо образом связывать друг с другом Поэтому каждый элемент динамической структуры должен содержать один или несколько адресов связанных с ним элементов, т.е. указателей на эти элементы

Слайд 13

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

Самый простой способ соединить отдельные элементы между собой заключается в том, чтобы снабдить каждый из них только одним указателем на другой элемент Самый простой способ соединить отдельные элементы между собой заключается в том, чтобы снабдить каждый из них только одним указателем на другой элемент В результате получается динамическая структура, называемая линейным (однонаправленным) списком

Слайд 14

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

Между элементами линейного списка существует отношение предыдущий-последующий Между элементами линейного списка существует отношение предыдущий-последующий

Слайд 15

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

Для элемента линейного списка можно определить следующий тип данных: Для элемента линейного списка можно определить следующий тип данных: struct element { int info; // информационное поле element* next; // указатель на следующий }; // элемент Для информационного поля может быть выбран любой другой тип данных, в том числе, массив или структура

Слайд 16

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

Слайд 17

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

Основными операциями при работе со списками являются: Основными операциями при работе со списками являются: инициализация списка проверка списка на пустоту добавление элемента в список удаление элемента из списка поиск в списке

Слайд 18

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

Эта операция сводится к созданию пустого списка Эта операция сводится к созданию пустого списка p = NULL;

Слайд 19

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

Проверка на пустоту заключается в вычислении значения выражения Проверка на пустоту заключается в вычислении значения выражения p == NULL, которое имеет значение TRUE в случае, если список пуст, и FALSE в противном случае

Слайд 20

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

Операция сводится к созданию нового элемента с помощью указателя на голову списка Операция сводится к созданию нового элемента с помощью указателя на голову списка p= new elem; p->next = NULL; x = rand() % 100; p->info = x;

Слайд 21

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

Предполагается, что предварительно в списке тем или иным способом выделен некоторый элемент Предполагается, что предварительно в списке тем или иным способом выделен некоторый элемент Далее, возможны две ситуации: новый элемент нужно вставить перед выделенным; новый элемент нужно вставить после выделенного Рассмотрим каждую из ним в отдельности

Слайд 22

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

Для этого необходимо выполнить следующие действия: Для этого необходимо выполнить следующие действия: определить рабочую переменную-указатель создать новый элемент с помощью рабочего указателя связать новый элемент со следующим за выделенным связать выделенный элемент с новым

Слайд 23

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

Слайд 24

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

q= new elem; // создать новый элемент q= new elem; // создать новый элемент q->next = r->next; // связать его со следующим за // выделенным r->next = q; // связать выделенный элемент с // новым x = rand() % 100; q->info = x; q = NULL;

Слайд 25

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

В этом случае задача сводится к предыдущей, а именно, нужно: В этом случае задача сводится к предыдущей, а именно, нужно: добавить новый элемент после выделенного, произвести обмен значениями между выделенным и новым элементами

Слайд 26

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

Слайд 27

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

Операции добавления элементов в список могут различаться способом ввода данных Операции добавления элементов в список могут различаться способом ввода данных Данные могут задаваться путем консольного ввода, путем считывания из файла, путем использования генератора случайных чисел

Слайд 28

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

Операции добавления в список позволяют создавать списки как с прямым, так и с обратным по отношению к порядку ввода следованием элементов Операции добавления в список позволяют создавать списки как с прямым, так и с обратным по отношению к порядку ввода следованием элементов Алгоритм создания списка: инициировать список повторить нужное число раз операцию добавления элемента в список

Слайд 29

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

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

Слайд 30

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

Слайд 31

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

Слайд 32

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

q = p; //поиск заданного значения x q = p; //поиск заданного значения x while (q->next != NULL && q->info!=x) q = q->next; if (q->info==x) cout

Слайд 33

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

Особенность этой операции заключается в том, что удалить можно только элемент, следующий за выделенным Особенность этой операции заключается в том, что удалить можно только элемент, следующий за выделенным Алгоритм удаления состоит просто в изменении значения поля указателя выделенного элемента: q = r->next; r->next = q->next; delete *q;

Слайд 34

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

Слайд 35

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

Особым случаем является удаление первого элемента списка, которое сводится изменению значения указателя на голову списка: Особым случаем является удаление первого элемента списка, которое сводится изменению значения указателя на голову списка: p = r->next; delete *r; Разумеется, удаление элемента возможно только при условии, что список не пуст

Слайд 36

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

Слайд 37

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

Операция заключается в последовательном переборе всех элементов списка от первого до последнего Операция заключается в последовательном переборе всех элементов списка от первого до последнего Просмотр списка может сопровождаться выводом значений информационных полей, поиском максимального значения и т.д. Операция реализуется простым циклом for

Слайд 38

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

Рассмотрим пример реализации линейного списка в виде динамической структуры Рассмотрим пример реализации линейного списка в виде динамической структуры Тестирование приложения

Слайд 39

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

Двунаправленные списки отличаются от однонаправленных тем, что между их элементами существуют отношения предыдущий-последующий и последующий-предыдущий Двунаправленные списки отличаются от однонаправленных тем, что между их элементами существуют отношения предыдущий-последующий и последующий-предыдущий

Слайд 40

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

Небольшое усложнение структуры элемента списка позволяет получить возможность просмотра его в двух направлениях: от начала к концу и от конца к началу Небольшое усложнение структуры элемента списка позволяет получить возможность просмотра его в двух направлениях: от начала к концу и от конца к началу struct element { int info; // информационное поле element* prev; // указатель на предыдущий element* next; // указатель на следующий };

Слайд 41

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

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

Слайд 42

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

Добавить перед Добавить перед q= new elem; q->next = r; q->prev = r->prev; x = rand() % 100; q->info = x; r->prev = q; r->prev->next = q; q = NULL;

Слайд 43

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

Добавить первый Добавить первый q= new elem; q->next = p; q->prev = NULL; x = rand() % 100; q->info = x; p->prev = q; p = q; q = NULL;

Слайд 44

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

Удалить перед текущим Удалить перед текущим q=r->prev; r->prev = q->prev; q->prev->next =r; delete *q;

Слайд 45

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

В двунаправленном списке можно удалить и текущий элемент: В двунаправленном списке можно удалить и текущий элемент: r->prev->next = r->next; r->next->prev =r->prev; delete *r;

Слайд 46

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

Кольцевой однонаправленный список получается из линейного «замыканием» последнего элемента на первый Кольцевой однонаправленный список получается из линейного «замыканием» последнего элемента на первый Соответственно, операция добавления в конец такого списка должна завершаться следующим присваиванием: q->next = p;

Слайд 47

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

Для двунаправленного кольцевого списка требуется установить две ссылки: Для двунаправленного кольцевого списка требуется установить две ссылки: первого элемента на последний, последнего элемента на первый Ссылка первого элемента *p на созданный в конце списка элемент *q имеет вид p->prev = q; а последнего на первый q->next = p;

Слайд 48

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

Вышеописанная реализация списка в виде связной динамической структуры имеет ряд очевидных достоинств Вышеописанная реализация списка в виде связной динамической структуры имеет ряд очевидных достоинств К числу этих достоинств относятся: возможность создавать, удалять и регулировать размер списков во время выполнения программы; относительная простота выполнения операций добавления элементов в список и их удаления из списка

Слайд 49

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

Однако список может быть реализован и с помощью массива Однако список может быть реализован и с помощью массива Для этого необходимо создать массив с типом элемента вида: struct element { int info; // информационное поле int next; // указатель на следующий элемент };

Слайд 50

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

В этом случае поле ссылки имеет значение индекса следующего элемента В этом случае поле ссылки имеет значение индекса следующего элемента Для обозначения «свободных» элементов массива можно использовать особые значения поля ссылки, например, равные -2 Операции добавления новых элементов требуют в этих случаях предварительного поиска в массиве свободных мест

Слайд 51

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

При этом остается ограничение на длину списка, что позволяет реализовать списки с длиной, не превышающей объявленную длину массива При этом остается ограничение на длину списка, что позволяет реализовать списки с длиной, не превышающей объявленную длину массива Соответственно, появляется еще одна дополнительная операция – проверка на переполнение списка Пример реализации списка в виде массива Тестирование приложения

Слайд 52

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

Понятие списка вводится в информатике как структура данных, представляющая соответствующий абстрактный тип данных Понятие списка вводится в информатике как структура данных, представляющая соответствующий абстрактный тип данных Абстра́ктным типом да́нных (АТД) называется тип данных, который определяется путем перечисления набора возможных операций над его данными

Слайд 53

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

В число этих операций входят операции создания и удаления элементов АТД В число этих операций входят операции создания и удаления элементов АТД Вся внутренняя структура такого типа спрятана от разработчика программного обеспечения и в этом и заключается суть абстракции

Слайд 54

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

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