Классификация структур данных. (Лекция 8) - презентация, доклад, проект скачать

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

Классификация структур данных. (Лекция 8), слайд №1

Классификация структур данных. (Лекция 8), слайд №2

Классификация структур данных. (Лекция 8), слайд №3

Классификация структур данных. (Лекция 8), слайд №4

Классификация структур данных. (Лекция 8), слайд №5

Классификация структур данных. (Лекция 8), слайд №6

Классификация структур данных. (Лекция 8), слайд №7

Классификация структур данных. (Лекция 8), слайд №8

Классификация структур данных. (Лекция 8), слайд №9

Классификация структур данных. (Лекция 8), слайд №10

Классификация структур данных. (Лекция 8), слайд №11

Классификация структур данных. (Лекция 8), слайд №12

Классификация структур данных. (Лекция 8), слайд №13

Классификация структур данных. (Лекция 8), слайд №14

Классификация структур данных. (Лекция 8), слайд №15

Классификация структур данных. (Лекция 8), слайд №16

Классификация структур данных. (Лекция 8), слайд №17

Классификация структур данных. (Лекция 8), слайд №18

Классификация структур данных. (Лекция 8), слайд №19

Классификация структур данных. (Лекция 8), слайд №20

Классификация структур данных. (Лекция 8), слайд №21

Классификация структур данных. (Лекция 8), слайд №22

Классификация структур данных. (Лекция 8), слайд №23

Классификация структур данных. (Лекция 8), слайд №24

Классификация структур данных. (Лекция 8), слайд №25

Классификация структур данных. (Лекция 8), слайд №26

Классификация структур данных. (Лекция 8), слайд №27

Классификация структур данных. (Лекция 8), слайд №28

Классификация структур данных. (Лекция 8), слайд №29

Классификация структур данных. (Лекция 8), слайд №30

Классификация структур данных. (Лекция 8), слайд №31

Классификация структур данных. (Лекция 8), слайд №32

Классификация структур данных. (Лекция 8), слайд №33

Классификация структур данных. (Лекция 8), слайд №34

Классификация структур данных. (Лекция 8), слайд №35

Классификация структур данных. (Лекция 8), слайд №36

Классификация структур данных. (Лекция 8), слайд №37

Содержание ▲

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

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

Слайд 1

Описание слайда:

Лекция 8

Слайд 2

Описание слайда:

Классификация структур данных По сложности: простые интегрированные По способу представления: физическая логическая По наличию связей между элементами данных: несвязные связные По изменчивости: Статические полустатические динамические По характеру упорядоченности элементов в структуре: линейные нелинейные По виду памяти, используемой для сохранности данных: для оперативной для внешней памяти

Слайд 3

Описание слайда:

Список В математике список (или кортеж) – это конечная последовательность элементов какого-нибудь множества Ψ. , где n – количество элементов (длина) списка, xi есть i-й элемент списка (xi ∈ Ψ). Линейный список Связный список

Слайд 4

Описание слайда:

Операции с линейным списком 1) Получить значение i-го элемента списка или изменить i-й элемент; 2) Напечатать элементы списка в порядке их расположения; 3) Найти в списке элемент с заданным значением; 4) Определить длину списка; 5) Вставить новый элемент непосредственно за i-м элементом или перед ним, вставить элемент в пустой список; 6) Удалить i-й элемент; 7) Соединить два линейных списка в один список; 8) Разбить список на два списка; 9) Создать копию списка; 10) Сделать список пустым.

Слайд 5

Описание слайда:

Реализация списков посредством массивов Линейный список const maxlen = … {для конкретной задачи целое} type elemtype = … {для задачи тип элементов}; list = record elems: array [1..maxlen] of elemtype; last: integer end; var L: list; procedure make_null(var L: list); begin L.last:=0 end;

Слайд 6

Описание слайда:

Операция вставки элемента x перед i-м элементом Операция вставки элемента x перед i-м элементом procedure insert(var L: list; x: elemtype; i:integer); var p: integer; begin for p:=L.last downto i do L.elems[p+1]:=L.elems[p]; L.elems[i]:=x; L.last:=L.last+1; end;

Слайд 7

Описание слайда:

Поиск элемента X function is_present(var L: list; x: elemtype):boolean; var p:integer; begin is_present:= false; p:=1; while not is_present and (p

Слайд 8

Описание слайда:

Связанный список Порядок элементов определяется последовательностью ссылок на элементы списка.

Слайд 9

Описание слайда:

Создать связный список положительных и отрицательных элементов const max_elem = 20; Type elem_type = integer; elem = record info: elem_type; next: byte end; list = record elems:array[1..max_elem] of elem; first:byte end; var t1,t2: list; r: elem_TYPE; begin t1.first := 0; t2.first2 := 0; repeat read (r); if r>0 then add_beg(t1, r); if r

Слайд 10

Описание слайда:

Удалить элемент с заданным значением procedure DEL(var t: list; x:elem_TYPE); var cur:byte; begin cur := t.first; while (cur 0) do begin if t.elems[cur].info=x then if cur=first then first:=t.elems [cur].next else t.elems [cur+1].next:=t.elems [cur].next; cur := t.elems [cur].next end; end;

Слайд 11

Описание слайда:

Двунаправленный список

Слайд 12

Описание слайда:

Циклический список

Слайд 13

Описание слайда:

Стек, очередь, дек

Слайд 14

Описание слайда:

Стек Операции, производимые над стеками: 1) Занесение элемента в стек. Push(S,x), где S - идентификатор стека, x - заносимый элемент. 2) Выборка элемента из стека. Pop(S) 3) Определение пустоты стека. Empty(S) 4) Прочтение элемента без его выборки из стека. StackTop(S) эквивалентно x = Pop(Stack) Push(Stack, x).

Слайд 15

Описание слайда:

Реализация стека на базе массива const stacksize = … {максимальное число элементов}; type elemtype = … {тип элементов стека}; stack = record elems: array [1..stacksize] of elemtype; top: integer {индекс вершины стека} end; var S: stack; procedure push (var S: stack;x:elemtype); Begin S.top:=S.top+1; S.elems[S.top]:=x end; procedure pop (var S: stack; var x:elemtype); begin x:=S.elems[S.top]; S.top:=S.top-1; end;

Слайд 16

Описание слайда:

Очередь

Слайд 17

Описание слайда:

Пример реализации очереди в виде одномерного массива

Слайд 18

Описание слайда:

Const MaxQ = 100; Const MaxQ = 100; Type E = char; Queue = record Elems:Array [1..MaxQ] of E; Head, tail: integer end; var Q: Queue; Procedure Insert(I: char; var Q: Queue); begin Inc(q.tail); Q.elems[tail]:=I; end; Function Empty(Q: Queue): Boolean; begin empty:= q.tail

Слайд 19

Описание слайда:

Организация кольцевой очереди

Слайд 20

Описание слайда:

Const size=100; Const size=100; Type Data= integer; Queue= record elems: array[1..SIZE] of data; tail, head : integer; end; Var q:queue; Procedure QInit; { инициализация } begin q. tail :=1; q.head:=1; end; Procedure Qclr; {очистка} begin q. tail :=q.head; end; Function QSize : integer; begin if q.head

Слайд 21

Описание слайда:

Дек Дек - особый вид очереди (от англ. deq - double ended queue) - это такой последовательный список, в котором как включение, так и исключение элементов может осуществляться с любого из двух концов списка. Операции над деком: включение элемента справа; включение элемента слева; исключение элемента справа; исключение элемента слева; определение размера; очистка.

Слайд 22

Описание слайда:

Слайд 23

Описание слайда:

Дерево — это совокупность элементов, называемых узлами и отношений, образующих иерархическую структуру узлов

Слайд 24

Описание слайда:

Слайд 25

Описание слайда:

обход в прямом порядке -от корня к левой ветви, затем к правой; обход в прямом порядке -от корня к левой ветви, затем к правой; 1 2 3 5 8 9 6 10 4 7 обход в обратном порядке -проходится левая ветвь, затем правая, затем корень 2 8 9 5 10 6 3 7 4 1 симметричный обход - дерево проходится, начиная с левой ветви вверх к корню, затем к правой ветви; 2 1 8 5 9 3 10 6 7 4

Слайд 26

Описание слайда:

Представление дерева

Слайд 27

Описание слайда:

Бинарное дерево – это конечное множество элементов, которое либо пусто, либо содержит один элемент, называемый корнем дерева, а остальные элементы множества делятся на два непересекающихся подмножества, каждое из которых само является бинарным деревом. Эти подмножества называются левым и правым поддеревьями исходного дерева.

Слайд 28

Описание слайда:

Основные операции с деревьями 1. Обход дерева. Обработка корня. Обработка левой ветви. Обработка правой ветви. 2. Удаление поддерева. Поиск родителя поддерева Разрыв связи с удаляемым поддеревом Декремент степени исхода 3. Вставка поддерева. Определения родителя для нового поддерева Установка связи с новым поддеревом Инкремент степени исхода

Слайд 29

Описание слайда:

Двоичное дерево поиска Оба поддерева — левое и правое, являются двоичными деревьями поиска. У всех узлов левого поддерева произвольного узла X значения ключей данных меньше, значения ключа данных самого узла X. У всех узлов правого поддерева того же узла X значения ключей данных не меньше, значения ключа данных узла X.

Слайд 30

Описание слайда:

Поиск узла с ключом 17

Слайд 31

Описание слайда:

Добавление узла с ключом 42

Слайд 32

Описание слайда:

Удаление узла 5

Слайд 33

Описание слайда:

Удаление узла 5

Слайд 34

Описание слайда:

Ку́ча — это специализированная структура данных типа дерево , которая удовлетворяет свойству кучи Значение в любой вершине не меньше, чем значения её потомков. Глубина листьев (расстояние до корня) отличается не более чем на 1 слой. Последний слой заполняется слева направо. Структура данных для кучи — массив A, где A[1] — элемент в корне, потомками элемента A[i] являются A[2i] и A[2i+1] (при нумерации элементов с первого).