Динамические структуры данных. Односвязные и двусвязные списки

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

Динамические структуры данных. Односвязные и двусвязные списки, слайд №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

Содержание ▲

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

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

Слайд 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.