🗊Презентация Классификация структур данных. (Лекция 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
Описание слайда:
Лекция 8

Слайд 2


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

Слайд 3


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

Слайд 4


Операции с линейным списком 1) Получить значение i-го элемента списка или изменить i-й элемент; 2) Напечатать элементы списка в порядке их расположения; 3) Найти в списке элемент с заданным значением; 4) Определить длину списка; 5) Вставить новый элемент непосредственно за i-м элементом или перед ним, вставить элемент в пустой список; 6) Удалить i-й элемент; 7) Соединить два линейных списка в один список; 8) Разбить список на два списка; 9) Создать копию списка; 10) Сделать список пустым.
Описание слайда:
Операции с линейным списком 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;
Описание слайда:
Реализация списков посредством массивов Линейный список 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;
Описание слайда:
Операция вставки элемента 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 <= L.last) do begin is_present:= x = L.elems[p]; p:= p+1 end; end;
Описание слайда:
Поиск элемента 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 <= L.last) do begin is_present:= x = L.elems[p]; p:= p+1 end; end;

Слайд 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<0 then add_beg(t2, r); until r=0; writeln(' список положительных элементов:'); trav_info(t1); writeln(‘список отрицательных элементов:'); trav_info(t2); end.
Описание слайда:
Создать связный список положительных и отрицательных элементов 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<0 then add_beg(t2, r); until r=0; writeln(' список положительных элементов:'); trav_info(t1); writeln(‘список отрицательных элементов:'); trav_info(t2); end.

Слайд 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;
Описание слайда:
Удалить элемент с заданным значением 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).
Описание слайда:
Стек Операции, производимые над стеками:  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;
Описание слайда:
Реализация стека на базе массива 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 <q. head; end;  
Описание слайда:
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 <q. head; end;  

Слайд 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 <= q. tail then QSize:=q. tail -q.head else QSize:=q.tail+SIZE-q.head+1; end;
Описание слайда:
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 <= q. tail then QSize:=q. tail -q.head else QSize:=q.tail+SIZE-q.head+1; end;

Слайд 21


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

Слайд 22


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

Слайд 23


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

Слайд 24


Классификация структур данных. (Лекция 8), слайд №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
Описание слайда:
обход в прямом порядке -от корня к левой ветви, затем к правой; обход в прямом порядке -от корня к левой ветви, затем к правой; 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. Вставка поддерева. Определения родителя для нового поддерева Установка связи с новым поддеревом Инкремент степени исхода
Описание слайда:
Основные операции с деревьями 1. Обход дерева. Обработка корня. Обработка левой ветви. Обработка правой ветви. 2. Удаление поддерева. Поиск родителя поддерева Разрыв связи с удаляемым поддеревом Декремент степени исхода 3. Вставка поддерева. Определения родителя для нового поддерева Установка связи с новым поддеревом Инкремент степени исхода

Слайд 29


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

Слайд 30


Поиск узла с ключом 17
Описание слайда:
Поиск узла с ключом 17

Слайд 31


Добавление узла с ключом 42
Описание слайда:
Добавление узла с ключом 42

Слайд 32


Удаление узла 5
Описание слайда:
Удаление узла 5

Слайд 33


Удаление узла 5
Описание слайда:
Удаление узла 5

Слайд 34


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

Слайд 35


Основные операции с кучей Добавление элемента в кучу Добавить элемент х в конец массива h Восстановление кучи
Описание слайда:
Основные операции с кучей Добавление элемента в кучу Добавить элемент х в конец массива h Восстановление кучи

Слайд 36


Основные операции с кучей Удаление узла из кучи
Описание слайда:
Основные операции с кучей Удаление узла из кучи

Слайд 37


Основные операции с кучей Нормализация кучи
Описание слайда:
Основные операции с кучей Нормализация кучи

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию