Презентация Классификация структур данных. (Лекция 8) онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Классификация структур данных. (Лекция 8) абсолютно бесплатно. Урок-презентация на эту тему содержит всего 37 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:37 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:2.87 MB
- Просмотров:88
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Лекция 8
№2 слайд
Содержание слайда: Классификация структур данных
По сложности:
простые
интегрированные
По способу представления:
физическая
логическая
По наличию связей между элементами данных:
несвязные
связные
По изменчивости:
Статические
полустатические
динамические
По характеру упорядоченности элементов в структуре:
линейные
нелинейные
По виду памяти, используемой для сохранности данных:
для оперативной
для внешней памяти
№3 слайд
Содержание слайда: Список
В математике список (или кортеж) – это конечная последовательность элементов какого-нибудь множества Ψ.
<x1,x2,…,xn>, где 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 <= 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.
№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 <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;
№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] (при нумерации элементов с первого).
№35 слайд
Содержание слайда: Основные операции с кучей
Добавление элемента в кучу
Добавить элемент х в конец массива h
Восстановление кучи
№36 слайд
Содержание слайда: Основные операции с кучей
Удаление узла из кучи
№37 слайд
Содержание слайда: Основные операции с кучей
Нормализация кучи
Скачать все slide презентации Классификация структур данных. (Лекция 8) одним архивом:
