Презентация Классификация структур данных. (Лекция 8) онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Классификация структур данных. (Лекция 8) абсолютно бесплатно. Урок-презентация на эту тему содержит всего 37 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Презентации » Устройства и комплектующие » Классификация структур данных. (Лекция 8)
Оцените!
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:37 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:2.87 MB
- Просмотров:88
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№2 слайд
![Классификация структур данных](/documents_6/a614800ecff0ef9b0f74eedae3e85244/img1.jpg)
Содержание слайда: Классификация структур данных
По сложности:
простые
интегрированные
По способу представления:
физическая
логическая
По наличию связей между элементами данных:
несвязные
связные
По изменчивости:
Статические
полустатические
динамические
По характеру упорядоченности элементов в структуре:
линейные
нелинейные
По виду памяти, используемой для сохранности данных:
для оперативной
для внешней памяти
№4 слайд
![Операции с линейным списком](/documents_6/a614800ecff0ef9b0f74eedae3e85244/img3.jpg)
Содержание слайда: Операции с линейным списком
1) Получить значение i-го элемента списка или изменить i-й элемент;
2) Напечатать элементы списка в порядке их расположения;
3) Найти в списке элемент с заданным значением;
4) Определить длину списка;
5) Вставить новый элемент непосредственно за i-м элементом или перед ним, вставить элемент в пустой список;
6) Удалить i-й элемент;
7) Соединить два линейных списка в один список;
8) Разбить список на два списка;
9) Создать копию списка;
10) Сделать список пустым.
№5 слайд
![Реализация списков](/documents_6/a614800ecff0ef9b0f74eedae3e85244/img4.jpg)
Содержание слайда: Реализация списков посредством массивов
Линейный список
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;
№9 слайд
![Создать связный список](/documents_6/a614800ecff0ef9b0f74eedae3e85244/img8.jpg)
Содержание слайда: Создать связный список положительных и отрицательных элементов
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 слайд
![Удалить элемент с заданным](/documents_6/a614800ecff0ef9b0f74eedae3e85244/img9.jpg)
Содержание слайда: Удалить элемент с заданным значением
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;
№14 слайд
![Стек Операции, производимые](/documents_6/a614800ecff0ef9b0f74eedae3e85244/img13.jpg)
Содержание слайда: Стек
Операции, производимые над стеками:
1) Занесение элемента в стек.
Push(S,x), где S - идентификатор стека, x - заносимый элемент.
2) Выборка элемента из стека.
Pop(S)
3) Определение пустоты стека.
Empty(S)
4) Прочтение элемента без его выборки из стека.
StackTop(S) эквивалентно x = Pop(Stack) Push(Stack, x).
№15 слайд
![Реализация стека на базе](/documents_6/a614800ecff0ef9b0f74eedae3e85244/img14.jpg)
Содержание слайда: Реализация стека на базе массива
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;
№18 слайд
![Const MaxQ Const MaxQ Type E](/documents_6/a614800ecff0ef9b0f74eedae3e85244/img17.jpg)
Содержание слайда: 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;
№20 слайд
![Const size Const size Type](/documents_6/a614800ecff0ef9b0f74eedae3e85244/img19.jpg)
Содержание слайда: 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 слайд
![Дек Дек - особый вид очереди](/documents_6/a614800ecff0ef9b0f74eedae3e85244/img20.jpg)
Содержание слайда: Дек
Дек - особый вид очереди (от англ. deq - double ended queue) - это такой последовательный список, в котором как включение, так и исключение элементов может осуществляться с любого из двух концов списка.
Операции над деком:
включение элемента справа;
включение элемента слева;
исключение элемента справа;
исключение элемента слева;
определение размера;
очистка.
№25 слайд
![обход в прямом порядке -от](/documents_6/a614800ecff0ef9b0f74eedae3e85244/img24.jpg)
Содержание слайда: обход в прямом порядке -от корня к левой ветви, затем к правой;
обход в прямом порядке -от корня к левой ветви, затем к правой;
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
№27 слайд
![Бинарное дерево это конечное](/documents_6/a614800ecff0ef9b0f74eedae3e85244/img26.jpg)
Содержание слайда: Бинарное дерево
– это конечное множество элементов, которое либо пусто, либо содержит один элемент, называемый корнем дерева, а остальные элементы множества делятся на два непересекающихся подмножества, каждое из которых само является бинарным деревом. Эти подмножества называются левым и правым поддеревьями исходного дерева.
№28 слайд
![Основные операции с деревьями](/documents_6/a614800ecff0ef9b0f74eedae3e85244/img27.jpg)
Содержание слайда: Основные операции с деревьями
1. Обход дерева.
Обработка корня.
Обработка левой ветви.
Обработка правой ветви.
2. Удаление поддерева.
Поиск родителя поддерева
Разрыв связи с удаляемым поддеревом
Декремент степени исхода
3. Вставка поддерева.
Определения родителя для нового поддерева
Установка связи с новым поддеревом
Инкремент степени исхода
№29 слайд
![Двоичное дерево поиска Оба](/documents_6/a614800ecff0ef9b0f74eedae3e85244/img28.jpg)
Содержание слайда: Двоичное дерево поиска
Оба поддерева — левое и правое, являются двоичными деревьями поиска.
У всех узлов левого поддерева произвольного узла X значения ключей данных меньше, значения ключа данных самого узла X.
У всех узлов правого поддерева того же узла X значения ключей данных не меньше, значения ключа данных узла X.
№34 слайд
![Куча это специализированная](/documents_6/a614800ecff0ef9b0f74eedae3e85244/img33.jpg)
Содержание слайда: Ку́ча
— это специализированная структура данных типа дерево , которая удовлетворяет свойству кучи
Значение в любой вершине не меньше, чем значения её потомков.
Глубина листьев (расстояние до корня) отличается не более чем на 1 слой.
Последний слой заполняется слева направо.
Структура данных для кучи — массив A, где A[1] — элемент в корне,
потомками элемента A[i] являются A[2i] и A[2i+1] (при нумерации элементов с первого).
Скачать все slide презентации Классификация структур данных. (Лекция 8) одним архивом:
Похожие презентации
-
Классификация структур данных. Лекция 2
-
Алгоритмы и структуры данных. Иерархические структуры данных. Лекция 3
-
Алгоритмы и структуры данных. Лекция 2
-
Структуры и объединения данных. (Лекция 13)
-
Массивы. Классификация данных по структуре
-
Основы алгоритмизации и программирования. Лекция 15. Динамические структуры данных
-
Алгоритмы и структуры данных. (Лекция 6. 4)
-
Структуры данных. Запись. (Лекция 7)
-
Алгоритмы и структуры данных. Лекция 7. Сбалансированные деревья. АВЛ-деревья
-
Структура программы в Паскале. Ввод и вывод данных. (Тема 2)