Презентация Динамические структуры данных. Односвязные и двусвязные списки онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Динамические структуры данных. Односвязные и двусвязные списки абсолютно бесплатно. Урок-презентация на эту тему содержит всего 53 слайда. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:53 слайда
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:969.50 kB
- Просмотров:80
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Динамические структуры данных
Лекция 5
№2 слайд
Содержание слайда: Динамические структуры
Односвязные (однонаправленные) списки
Двусвязные (двунаправленные) списки
№3 слайд
Содержание слайда:
№4 слайд
Содержание слайда:
№5 слайд
Содержание слайда:
№6 слайд
Содержание слайда:
№7 слайд
Содержание слайда:
№8 слайд
Содержание слайда:
№9 слайд
Содержание слайда:
№10 слайд
Содержание слайда:
№11 слайд
Содержание слайда:
№12 слайд
Содержание слайда:
№13 слайд
Содержание слайда:
№14 слайд
Содержание слайда:
№15 слайд
Содержание слайда:
№16 слайд
Содержание слайда:
№17 слайд
Содержание слайда:
№18 слайд
Содержание слайда:
№19 слайд
Содержание слайда:
№20 слайд
Содержание слайда: Что надо уметь делать со списком?
№21 слайд
Содержание слайда:
№22 слайд
Содержание слайда: Создать новый узел.
Добавить узел:
в начало списка;
в конец списка;
после заданного узла;
до заданного узла.
Искать нужный узел в списке.
Удалить узел.
№23 слайд
Содержание слайда: СТЕК
Стек – это линейный список, в котором все включения и исключения (и обычно всякий доступ) делаются в одном конце списка (в голове списка).
Стеки используются в работе алгоритмов, имеющих рекурсивный характер. Конец стека называется вершиной стека. Принцип работы стека - “последний пришел - первый вышел”. Внизу находится наименее доступный элемент. Часто говорят, что элемент опускается в стек.
№24 слайд
Содержание слайда:
№25 слайд
Содержание слайда: Пример. Ввести с клавиатуры 10 чисел, записав их в стек. Вывести содержимое стека и очистить память.
№26 слайд
Содержание слайда:
№27 слайд
Содержание слайда:
№28 слайд
Содержание слайда:
№29 слайд
Содержание слайда: Очередь – это линейный список, в один конец которого добавляются элементы, а с другого конца исключаются, элементы удаляются из начала списка, а добавляются в конце списка – как обыкновенная очередь в магазине. Принцип работы очереди: «первый пришел - первый вышел».
№30 слайд
Содержание слайда: Пример. Ввести с клавиатуры 10 чисел, записав их в очередь. Вывести содержимое очереди и очистить память.
Для решения этой задачи достаточно в предыдущем примере изменить процедуру добавления элемента.
№31 слайд
Содержание слайда:
№32 слайд
Содержание слайда:
№33 слайд
Содержание слайда:
№34 слайд
Содержание слайда: Двусвязные списки
При добавлении нового узла NewNode в начало списка надо
1) установить ссылку next узла NewNode на голову существующего списка и его ссылку prev в NULL;
№35 слайд
Содержание слайда: Двусвязные списки
2) установить ссылку prev бывшего первого узла (если он существовал) на NewNode;
№36 слайд
Содержание слайда: Двусвязные списки
3) установить голову списка на новый узел;
4) если в списке не было ни одного элемента, хвост списка также устанавливается на новый элемент.
№37 слайд
Содержание слайда: Двусвязные списки
№38 слайд
Содержание слайда: Добавление узла после заданного
Дан адрес NewNode нового узла и адрес p одного из существующих узлов в списке.
Требуется вставить в список новый узел после p.
Если узел p является последним, то операция сводится к добавлению в конец списка.
№39 слайд
Содержание слайда: Добавление узла после заданного
Если узел p – не последний, то операция
вставки выполняется в два этапа:
1) установить ссылки нового узла на следующий за данным (next) и предшествующий ему (prev);
2) установить ссылки соседних узлов так, чтобы включить NewNode в список.
№40 слайд
Содержание слайда: Добавление узла после заданного
(добавление после выполняется аналогично)
№41 слайд
Содержание слайда: Поиск узла в списке
Проход по двусвязному списку может выполняться в двух направлениях – от головы к хвосту (как для односвязного) или от хвоста к голове.
№42 слайд
Содержание слайда: Проход по списку в от головы списка
Алгоритм:
установить вспомогательный указатель q на голову списка;
если указатель q равен NULL (дошли до конца списка), то стоп;
выполнить действие над узлом с адресом q ;
перейти к следующему узлу, q->next
Перейти к п.2
№43 слайд
Содержание слайда: ...
PNode q = Head; // начали с головы
while ( q != NULL )
{ // пока не дошли до конца
... // делаем что-то хорошее с q
q = q->next; // переходим к следующему узлу
}
...
№44 слайд
Содержание слайда: Проход по списку от хвоста к голове списка
Алгоритм:
установить вспомогательный указатель q на хвост списка;
если указатель q равен NULL (дошли до начала списка), то стоп;
выполнить действие над узлом с адресом q ;
перейти к следующему узлу, q->prev
№45 слайд
Содержание слайда: PNode q = Tail; // начали с хвоста
while ( q != NULL )
{ // пока не дошли до начала
... // делаем что-то хорошее с q
q = q->prev; // переходим к следующему узлу
}
...
№46 слайд
Содержание слайда: Удаление узла
№47 слайд
Содержание слайда:
№48 слайд
Содержание слайда: Циклические списки
Иногда список (односвязный или двусвязный) замыкают в кольцо.
Указатель next последнего элемента указывает на первый элемент.
Для двусвязных списков указатель prev первого элемента указывает на последний. В таких списках понятие «хвоста» списка не имеет смысла, для работы с ним надо использовать указатель на «голову», причем «головой» можно считать любой элемент.
№49 слайд
Содержание слайда: Дано число N и N целых чисел. Создать циклический односвязный линейный список, в который поместить все эти элементы в порядке поступления (тип – очередь). Вернуть указатель на первый элемент списка. Затем распечатать этот список.
№50 слайд
Содержание слайда:
№51 слайд
Содержание слайда:
№52 слайд
Содержание слайда: Вывести значение N-го элемента кольцевого списка. Считать, что счет начинается с первого элемента и продолжается по кругу, если элементов в списке меньше N.
№53 слайд
Содержание слайда: Вставить значение х после N-го по счету элемента циклического списка.
Скачать все slide презентации Динамические структуры данных. Односвязные и двусвязные списки одним архивом:
