Презентация Линейные списки онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Линейные списки абсолютно бесплатно. Урок-презентация на эту тему содержит всего 47 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Презентации » Устройства и комплектующие » Линейные списки
Оцените!
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:47 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:280.00 kB
- Просмотров:73
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№2 слайд
![Некоторые задачи требуют](/documents_6/6fdca69f446ed3af67d918dc1b0c5947/img1.jpg)
Содержание слайда: Некоторые задачи требуют введения структур, способных увеличивать или уменьшать свой размер в процессе работы программы.
Некоторые задачи требуют введения структур, способных увеличивать или уменьшать свой размер в процессе работы программы.
Основу таких структур составляют динамиче-ские переменные, которые хранятся в неко-торой области памяти.
Обращение к ним производится с помощью указателя.
Как правило, такие переменные организуются в виде списков, элементы которых являются структурами (struct).
№3 слайд
![Если для связи элементов в](/documents_6/6fdca69f446ed3af67d918dc1b0c5947/img2.jpg)
Содержание слайда: Если для связи элементов в структуре задан указатель (адресное поле) на следующий элемент, то такой список называют одно-направленным (односвязным).
Если добавить в структуру еще и указатель на предыдущий элемент, то получится двунаправленный список (двусвязный).
Если последний элемент связать указателем с первым, получится кольцевой список.
№4 слайд
![Для работы с](/documents_6/6fdca69f446ed3af67d918dc1b0c5947/img3.jpg)
Содержание слайда: Для работы с однонаправленными списками шаблон структуры (структурный тип) будет иметь следующий вид:
Для работы с однонаправленными списками шаблон структуры (структурный тип) будет иметь следующий вид:
struct TList1 {
Информационная часть (ИЧ)
TList1 *next; – Адресная часть
};
Информационная часть – описание полей (членов структуры), определяющих обрабаты-ваемую в списке информацию;
next – указатель на следующий элемент.
№6 слайд
![Для работы с двунаправленными](/documents_6/6fdca69f446ed3af67d918dc1b0c5947/img5.jpg)
Содержание слайда: Для работы с двунаправленными списками шаблон структуры будет иметь следующий вид:
Для работы с двунаправленными списками шаблон структуры будет иметь следующий вид:
struct TList2 {
Информационная часть (ИЧ)
TList2 *prev, *next;
};
prev – указатель на предыдущий элемент;
next – указатель на следующий элемент.
№8 слайд
![Над списками обычно](/documents_6/6fdca69f446ed3af67d918dc1b0c5947/img7.jpg)
Содержание слайда: Над списками обычно выполняются следующие операции:
Над списками обычно выполняются следующие операции:
– начальное формирование списка (создание первого элемента);
– добавление нового элемента в список;
– обработка (просмотр, поиск, удаление и т.п.);
– освобождение памяти, занятой всем списком.
№9 слайд
![Структура данных СТЕК](/documents_6/6fdca69f446ed3af67d918dc1b0c5947/img8.jpg)
Содержание слайда: Структура данных СТЕК
Структура данных СТЕК
Стек – упорядоченный набор данных, в ко-тором добавление и удаление элементов производится только с конца, который на-зывают вершиной стека, т.е. стек – список с одной точкой доступа к его элементам.
Стек это структура данных типа LIFO (Last In, First Out) – последним вошел, первым выйдет.
№11 слайд
![Число элементов стека не](/documents_6/6fdca69f446ed3af67d918dc1b0c5947/img10.jpg)
Содержание слайда: Число элементов стека не ограничивается. При добавлении элементов в стек память должна динамически выделяться и освобождаться при удалении. Таким образом, стек – динамическая структура данных, состоящая из переменного числа элементов одинакового типа.
Число элементов стека не ограничивается. При добавлении элементов в стек память должна динамически выделяться и освобождаться при удалении. Таким образом, стек – динамическая структура данных, состоящая из переменного числа элементов одинакового типа.
Операции, выполняемые над стеком, имеют спе-циальные названия:
push – добавление элемента (вталкивание);
pop – удаление (извлечение) элемента, верхний элемент стека удаляется (не может приме-няться к пустому стеку).
№12 слайд
![Кроме этих обязательных](/documents_6/6fdca69f446ed3af67d918dc1b0c5947/img11.jpg)
Содержание слайда: Кроме этих обязательных операций используется операция top (peek) для чтения информации в вершине стека без извлечения.
Кроме этих обязательных операций используется операция top (peek) для чтения информации в вершине стека без извлечения.
Рассмотрим основные алгоритмы работы со стеком, взяв для простоты в качестве информационной части целые числа (int info;), хотя информационная часть может состоять из любого количества объектов допустимого типа, за исключением файлов.
№14 слайд
![. Объявление указателей на](/documents_6/6fdca69f446ed3af67d918dc1b0c5947/img13.jpg)
Содержание слайда: 2. Объявление указателей на структуру (можно объявить в шаблоне глобально):
2. Объявление указателей на структуру (можно объявить в шаблоне глобально):
Stack *begin, – Вершина стека
*t; – Текущий указатель
3. Так как первоначально стек пуст:
begin = NULL;
4. Захват памяти под первый элемент:
t = new Stack;
в памяти формируется конкретный адрес (обозначим его А1) для первого элемента, т.е. адрес текущего элемента t равен А1.
№15 слайд
![. Ввод информации обозначим i](/documents_6/6fdca69f446ed3af67d918dc1b0c5947/img14.jpg)
Содержание слайда: 5. Ввод информации (обозначим i1);
5. Ввод информации (обозначим i1);
а) формирование информационной части:
t -> info = i1;
б) формирование адресной части: значение адреса вершины стека записываем в адресную часть текущего элемента (там был NULL)
t -> next = begin;
На этом этапе получили:
№19 слайд
![Функция формирования элемента](/documents_6/6fdca69f446ed3af67d918dc1b0c5947/img18.jpg)
Содержание слайда: Функция формирования элемента стека
Функция формирования элемента стека
Простейший вид функции (типа push), в которую передаются указатель на вершину (р) и введенная информация (in), а измененное значение вершины (t) возвращается в точку вызова оператором return:
Stack* InStack (Stack *p, int in) {
Stack *t = new Stack; // Захват памяти
t -> info = in; // Формируем ИЧ
t -> next = p; // Формируем АЧ
return t;
}
№20 слайд
![Участок программы с](/documents_6/6fdca69f446ed3af67d918dc1b0c5947/img19.jpg)
Содержание слайда: Участок программы с обращением к функции InStack для добавления n элементов (исполь-зуем случайные числа) в стек может иметь следующий вид:
Участок программы с обращением к функции InStack для добавления n элементов (исполь-зуем случайные числа) в стек может иметь следующий вид:
for (i = 1; i <= n; i++) {
in = random (20);
begin = InStack (begin, in);
}
№21 слайд
![Если в функцию InStack](/documents_6/6fdca69f446ed3af67d918dc1b0c5947/img20.jpg)
Содержание слайда: Если в функцию InStack указатель на вершину передавать по адресу, то она может иметь следующий вид:
Если в функцию InStack указатель на вершину передавать по адресу, то она может иметь следующий вид:
void InStack (Stack **p, int in) {
Stack *t = new Stack;
t -> info = in;
t -> next = *p;
*p = t;
}
Обращение к ней в данном случае будет: InStack (&begin, in);
№22 слайд
![Просмотр стека без извлечения](/documents_6/6fdca69f446ed3af67d918dc1b0c5947/img21.jpg)
Содержание слайда: Просмотр стека (без извлечения)
Просмотр стека (без извлечения)
1. Устанавливаем текущий указатель на вершину
t = begin;
2. Проверяем, если стек пуст (begin = NULL), то выводим сообщение и либо завершаем работу, либо переходим на формирование стека.
3. Если стек не пуст, выполняем цикл до тех пор, пока текущий указатель t не равен NULL, т.е. пока не обработаем последний элемент, адресная часть которого равна NULL.
№24 слайд
![Функция, реализующая этот](/documents_6/6fdca69f446ed3af67d918dc1b0c5947/img23.jpg)
Содержание слайда: Функция, реализующая этот алгоритм:
Функция, реализующая этот алгоритм:
void View (Stack *p) {
Stack *t = p;
if ( p == NULL ) { // Или if (!p)
cout << “ Стек пуст! ” << endl;
return;
}
while( t != NULL) {
cout << t->info << endl;
t = t -> next;
}
}
Обращение к этой функции: View (begin);
№25 слайд
![Алгоритм освобождения памяти](/documents_6/6fdca69f446ed3af67d918dc1b0c5947/img24.jpg)
Содержание слайда: Алгоритм освобождения памяти
Алгоритм освобождения памяти
1. Начинаем цикл, выполняющийся пока begin не станет равным NULL.
2. Устанавливаем текущий указатель на вершину:
t = begin;
3. Вершину переставляем на следующий элемент:
begin = begin -> next;
4. Освобождаем память, занятую бывшей верши-ной
delete t;
5. Конец цикла.
№27 слайд
![Вершина стека передается в](/documents_6/6fdca69f446ed3af67d918dc1b0c5947/img26.jpg)
Содержание слайда: Вершина стека передается в функцию по адресу с помощью указателя для того, чтобы его измененное значение было возвращено из функции в точку вызова.
Вершина стека передается в функцию по адресу с помощью указателя для того, чтобы его измененное значение было возвращено из функции в точку вызова.
Обращение к этой функции:
Del_All (&begin);
После ее выполнения указатель на вершину begin будет равен NULL.
№29 слайд
![Вершина стека передается в](/documents_6/6fdca69f446ed3af67d918dc1b0c5947/img28.jpg)
Содержание слайда: Вершина стека передается в функцию по адресу с помощью ссылки (копии адреса) для того, чтобы его измененное значение было возвращено из функции в точку вызова.
Вершина стека передается в функцию по адресу с помощью ссылки (копии адреса) для того, чтобы его измененное значение было возвращено из функции в точку вызова.
Обращение к этой функции:
Del_All (begin);
После ее выполнения указатель на вершину begin будет равен NULL.
№31 слайд
![В данном случае в функцию](/documents_6/6fdca69f446ed3af67d918dc1b0c5947/img30.jpg)
Содержание слайда: В данном случае в функцию передаем указатель на вершину стека, а его измененное значение, равное NULL, возвращаем из функции в точку вызова с помощью оператора return.
В данном случае в функцию передаем указатель на вершину стека, а его измененное значение, равное NULL, возвращаем из функции в точку вызова с помощью оператора return.
№32 слайд
![Алгоритм получения информации](/documents_6/6fdca69f446ed3af67d918dc1b0c5947/img31.jpg)
Содержание слайда: Алгоритм получения информации из вершины стека c извлечением
Алгоритм получения информации из вершины стека c извлечением
1. Устанавливаем текущий указатель t на вершину
t = begin;
2. Сохраняем значение ИЧ out (выводим на экран)
out = begin -> info;
3. Переставляем вершину на следующий элемент
begin = begin -> next;
4. Освобождаем память бывшей вершины t
delete t;
После этого в переменной out находится нужное нам значение, а стек стал короче на один элемент.
№33 слайд
![Функция типа pop , в которую](/documents_6/6fdca69f446ed3af67d918dc1b0c5947/img32.jpg)
Содержание слайда: Функция (типа pop), в которую передаются вершина (р) и адрес переменной out для интересующей нас информации, измененное значение вершины (p) возвращается в точку вызова оператором return:
Функция (типа pop), в которую передаются вершина (р) и адрес переменной out для интересующей нас информации, измененное значение вершины (p) возвращается в точку вызова оператором return:
Stack* OutStack (Stack *p, int *out) {
Stack *t = p;
*out = p -> info;
p = p -> next;
delete t;
return p;
}
№34 слайд
![Обращение к этой функции](/documents_6/6fdca69f446ed3af67d918dc1b0c5947/img33.jpg)
Содержание слайда: Обращение к этой функции:
Обращение к этой функции:
begin = OutStack ( begin, &out );
Необходимая нам информация out (в нашем примере тип int) известна в точке вызова, т.к. передается по адресу.
Если в функцию OutStack указатель на вершину передавать по адресу, а нужную информацию out возвращать из функции оператором return, то она может иметь следующий вид:
№39 слайд
![Указатель на вершину стека](/documents_6/6fdca69f446ed3af67d918dc1b0c5947/img38.jpg)
Содержание слайда: Указатель на вершину стека передаем в функцию, а его измененное значение, возвращаем из функции в точку вызова с помощью оператора return.
Указатель на вершину стека передаем в функцию, а его измененное значение, возвращаем из функции в точку вызова с помощью оператора return.
Функция удаления из стека элементов, кратных 5, с использованием динамического массива:
№41 слайд
![a new int n Создаем](/documents_6/6fdca69f446ed3af67d918dc1b0c5947/img40.jpg)
Содержание слайда: a = new int[n]; // Создаем динамический массив
a = new int[n]; // Создаем динамический массив
// Извлекаем все элементы из стека в массив
for ( i = 0; i < n; i++ )
b = OutStack ( b, a + i );
/* Удаляем из массива кратные 5, т.е. переписы-ваем в массив только те, что не кратны 5 */
for ( m = i = 0; i < n; i++ )
if ( a[i] % 5 != 0 )
a[m++] = a[i];
// m – количество оставшихся элементов
№42 слайд
![Создаем стек снова](/documents_6/6fdca69f446ed3af67d918dc1b0c5947/img41.jpg)
Содержание слайда: /* Создаем стек снова – переписываем в него элементы, оставшиеся в массиве: */
/* Создаем стек снова – переписываем в него элементы, оставшиеся в массиве: */
for ( i = 0; i < m; i++ )
b = InStack ( b, a[i] );
delete []a; // Освобождаем память
/* Возвращаем в точку вызова вершину вновь созданного стека */
return b;
}
Обращение к функции:
begin = Del_5_mas ( begin );
№43 слайд
![И в этом случае в функцию](/documents_6/6fdca69f446ed3af67d918dc1b0c5947/img42.jpg)
Содержание слайда: И в этом случае в функцию передаем указатель на вершину стека, а его измененное значение, возвращаем из функции в точку вызова оператором return.
И в этом случае в функцию передаем указатель на вершину стека, а его измененное значение, возвращаем из функции в точку вызова оператором return.
Функция создания нового стека из элементов уже созданного стека, не кратных 5:
№45 слайд
![Обращение к функции Обращение](/documents_6/6fdca69f446ed3af67d918dc1b0c5947/img44.jpg)
Содержание слайда: Обращение к функции:
Обращение к функции:
begin = New_Stack_5 ( begin );
Что в созданном стеке не совсем корректно в сравнении с исходным?
Линейный поиск нужной информации в стеке может быть выполнен на базе функции просмотра View.
Например, найдем в стеке количество элементов кратных 5 :
№47 слайд
![Часть кода с обращением к](/documents_6/6fdca69f446ed3af67d918dc1b0c5947/img46.jpg)
Содержание слайда: Часть кода с обращением к этой функции:
Часть кода с обращением к этой функции:
. . .
int kol;
. . .
kol = Poisk (begin);
if (kol == 0)
Сообщение, что таких НЕТ!
else
Вывод результата!
. . .
В функцию передаем вершину стека, а в точку вызова возвращаем количество найденных элементов…
Скачать все slide презентации Линейные списки одним архивом:
Похожие презентации
-
Линейные списки: стеки, очереди, деки. Лекция 3
-
Основы программирования. Линейные списки
-
Индивидуальная работа «Линейные списки»
-
Линейный алгоритмический процесс
-
Нелинейные алгоритмы. Язык программирования Паскаль. 8 класс
-
Операторы линейных программ
-
Решение задач с линейными массивами
-
Решение простейших задач линейного программирования графическим методом
-
Линейное программирование. Транспортная задача
-
Особенности применения задач линейного программирования при моделировании процессов функционирования сложных систем. Раздел 3