andrey

Путь к Файлу: /Документы для форматирования / Кошелев / Динамические структуры данных / Классификация структур данных.ppt

Ознакомиться или скачать весь учебный материал данного пользователя
Скачиваний:   361
Пользователь:   andrey
Добавлен:   05.01.2015
Размер:   282.5 КБ
СКАЧАТЬ

Наверх страницы

Содержимое презентации:

Слайд 1

Классификация структур данных Лекция 5

Слайд 2

Классификация Данные статической структуры Данные динамической структуры Данные

Слайд 3

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

Слайд 4

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

Слайд 5

Данные динамической структуры Файлы Несвязанные динамические структуры Список очередь Стек односвязные многосвязные Линейной структуры Кольцевой структуры деревья Графы Разветвленной структуры Связанные динамические структуры Данные динамической структуры

Слайд 6

Линейный список

Слайд 7

Определение • Линейный список – это данные динамической структуры, которые представляют собой совокупность линейно связанных однородных элементов и для которых разрешены следующие действия: 

Слайд 8

Определение • Добавление элемента в начало (голову) списка; • Добавление элемента в конец (хвост) списка; • Вставка элемента между двумя любыми другими элементами списка; • Удаление любого как крайнего, так и среднего элемента списка.

Слайд 9

Описание списка p 1 значения полей key на рисунке проставлены условно nil n n-1 p 1 значения полей key на рисунке проставлены условно nil n n-1 p 1 значения полей key на рисунке проставлены условно nil n n-1

Слайд 10

Описание списка Type ukaz=^list_item; list_item=record key:integer; next:ukaz; end; Var P:ukaz; Описание типа указателя Описание информационного поля элемента Описание ссылочного поля элемента Объявление указателя на элемент списка

Слайд 11

Описание списка Typedef struct List_item { int key; struct List_item *next; } List_item *P; Описание информационного поля элемента Описание ссылочного поля элемента Объявление указателя на элемент списка

Слайд 12

Примеры Typedef struct Dyn_rec { char S; float K; Dyn_rec *L; } Dyn_rec=^List List=record S:char; K:real; L:Dyn_rec; }

Слайд 13

Инициализация списка … Begin … New(p); p^.next:=nil; … End. nil P Выделение памяти под элемент Заполнение ссылочного поля

Слайд 14

Инициализация списка … { … P=New(List_item); P->next=NULL; … } NULL P Выделение памяти под элемент Заполнение ссылочного поля

Слайд 15

Добавление в начало: общий алгоритм • Создать новый элемент • Установить нулевую ссылку на него • Установить связь старого элемента с вновь созданным • Переместить указатель на новый элемент

Слайд 16

Добавление элемента в начало (Pascal) Var P,Q:ukaz; Begin New(P); p^.next:=nil; New(Q); Q^.next:=nil; P^.next=Q; P:=Q; End. P Q nil nil Создание первого элемента Добавление к нему нового

Слайд 17

Добавление элемента в начало C List_item *P,*Q; { P=New(List_item); P->next=NULL; Q=New(List_item); Q=NULL; P->next=Q; P=Q; } P Q nil nil Создание первого элемента Добавление к нему нового

Слайд 18

Добавление в конец: общий алгоритм • Создание нового элемента • Установка связи с последним элементом • Перемещение указателя на новый элемент

Слайд 19

Добавление элемента в конец (Pascal) Var P,Q:ukaz; begin end. New(P); p^.next:=nil; nil P New(Q); Q Q^.next:=P; P:=Q; P

Слайд 20

Добавление элемента в конец (C) Var Dyn_rec *P,*Q; begin end. P=New(Dyn_rec); P->next=NULL; NULL P Q=New(Dyn_rec); Q Q->next=P; P=Q; P

Слайд 21

Добавление несколько элементов (формирование): общий алгоритм • Создание первого элемента • Добавление нового элемента в цикле, до тех пор, пока в информационное поле не будет введен спецсимвол – окончание цепочки

Слайд 22

Добавление нескольких Var P,Q:ukaz; элементов Begin New(P); P^.next:=nil; Readln(P^.data); While P^.data < > ‘*’ do begin New(Q); Readln(Q^.data); Q^.next:=P^.next; P^. next=Q; End; End.

Слайд 23

Добавление нескольких Dyn_rec *P,*Q; элементов { P= New(Dyn_rec); P->next=NULL; scanf(P->key); While (P->key!= ‘*’) { Q=New(Dyn_rec); Q->next=NULL; scanf(Q->key); P->next=Q; P=Q; } }.

Слайд 24

Что изменится? Var P,Q:ukaz; Begin New(P); P^.next:=nil; Readln(P^.data); repeat New(Q); Readln(Q^.data); Q^.next:=P^.next; P^. next=Q; until P^.data = ‘*’ ; End. Будет ли создаваться элемент со *? Что нужно сделать, чтобы не создавался?

Слайд 25

Просмотр элементов Begin New(P); P^.age:=20; P^.next:=nil For I:=1 to 3 do begin New(Q); Q^.age:=20+I;Q^.next:=P^.next; P^. next=Q; end; While P^.next<>nil do Begin writeln(P^.age); P:=P^.next; end; end. Каков результат выполнения программы?

Слайд 26

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

Слайд 27

Удаление элемента (Pascal) Var P,Q:ukaz; Begin Q:=P^.next; P^.next:=Q^.next; Despose(Q); End. Q nil P Сохранение ссылки на удаляемый элемент Установка связи с элементом за удаляемым Освобождение памяти

Слайд 28

Удаление элемента (С) Dyn_rec *P,*Q; { Q=P.next; P.next:=Q.next; delete(Q); } Q nil P Сохранение ссылки на удаляемый элемент Установка связи с элементом за удаляемым Освобождение памяти

Слайд 29

Удаление крайнего элемента • Сохранение ссылки на предполагаемый крайний элемент • Удаление элемента

Слайд 30

Удаление крайнего элемента Домашнее задание: • Составить фрагменты программы удаления крайнего элемента с начала и конца списка • Выяснить чем отличаются данные операции

Слайд 31

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

Слайд 32

Вставка элемента(Pascal) P nil Var P,Q:ukaz; Begin New(Q); Q:=P^.next; P^.next:=Q; End. Q

Слайд 33

Вставка элемента(C) Dyn_rec *P,*Q; { Q=New(Dyn_rec); Q=P.next; P.next=Q; } P nil Q

Слайд 34

Резюме • Линейно-связанный список - …

Слайд 35

Резюме • Описание элементов списка: Type ukaz=^list_item; list_item=record key:integer; next:ukaz; end; Var P:ukaz; ? ? ? ? Typedef struct List_item { int key; struct List_item *next; } List_item *P;

Слайд 36

Резюме: что это значит? • NEW(Pbeg); •Dispose(Pbeg); •Pbeg:=nil; •P:=Q; •P^.next:=Q^.next; • Pbeg=new(); •delete(Pbeg); •Pbeg=NULL; •P=Q; •P->next=Q->next; Pascal C

Слайд 37

Очередь

Слайд 38

Определение • Очередь – это данные динамической структуры, которые представляют собой совокупность линейно связанных однородных элементов и для которых разрешены следующие действия:

Слайд 39

Определение • Добавление элемента в конец (хвост) очереди; • Удаление элемента из начала очереди.

Слайд 40

Определение • Очередь – «список типа FIFO» (first-in-first-out, первый пришел- первый ушел)

Слайд 41

Стек

Слайд 42

Определение • Стек – это данные динамической структуры, которые представляют собой совокупность линейно связанных однородных элементов и для которых разрешены следующие действия:

Слайд 43

Определение • Добавление элемента в конец (хвост) стека; • Удаление элемента из хвоста стека.

Слайд 44

Определение • Очередь – «список типа LIFO» (last-in-first-out, последний пришел- первый ушел)

Слайд 45

Линейно-связанные структуры • Имеют одну ссылку на следующий элемент и не связаны с предыдущими; • В зависимости от типа структуры дозволен определенный список операций.


Внимание! Не забудьте ознакомиться с остальными документами данного пользователя!

Соседние файлы в текущем каталоге:

На сайте уже 21970 файлов общим размером 9.9 ГБ.

Наш сайт представляет собой Сервис, где студенты самых различных специальностей могут делиться своей учебой. Для удобства организован онлайн просмотр содержимого самых разных форматов файлов с возможностью их скачивания. У нас можно найти курсовые и лабораторные работы, дипломные работы и диссертации, лекции и шпаргалки, учебники, чертежи, инструкции, пособия и методички - можно найти любые учебные материалы. Наш полезный сервис предназначен прежде всего для помощи студентам в учёбе, ведь разобраться с любым предметом всегда быстрее когда можно посмотреть примеры, ознакомится более углубленно по той или иной теме. Все материалы на сайте представлены для ознакомления и загружены самими пользователями. Учитесь с нами, учитесь на пятерки и становитесь самыми грамотными специалистами своей профессии.

Не нашли нужный документ? Воспользуйтесь поиском по содержимому всех файлов сайта:



Каждый день, проснувшись по утру, заходи на obmendoc.ru

Товарищ, не ленись - делись файлами и новому учись!

Яндекс.Метрика