Презентация Списки. Структуры данных. Массивы онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Списки. Структуры данных. Массивы абсолютно бесплатно. Урок-презентация на эту тему содержит всего 55 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:55 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:2.75 MB
- Просмотров:99
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№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 << "Задайте размер массива" << endl;
cin >> 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 слайд
Содержание слайда: q= new elem; // создать новый элемент
q= new elem; // создать новый элемент
q->next = r->next; // связать его со следующим за // выделенным
r->next = q; // связать выделенный элемент с // новым
x = rand() % 100;
q->info = r->info; // обмен значениями
r->info = x;
№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 << «Значение найдено»;
else
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 слайд
Содержание слайда: Конкретные реализации АТД называются структурами данных
Конкретные реализации АТД называются структурами данных
Абстрактный тип данных список может быть реализован при помощи массива или линейного списка
Однако каждая реализация определяет один и тот же набор функций, который должен работать одинаково (по результату, а не по скорости) для всех реализаций
№55 слайд
Содержание слайда: Текст приложения
Текст приложения
Тестирование приложения
Скачать все slide презентации Списки. Структуры данных. Массивы одним архивом:
