Презентация Динамические структуры данных и их организация с помощью указателей онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Динамические структуры данных и их организация с помощью указателей абсолютно бесплатно. Урок-презентация на эту тему содержит всего 72 слайда. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Презентации » Устройства и комплектующие » Динамические структуры данных и их организация с помощью указателей
Оцените!
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:72 слайда
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:239.19 kB
- Просмотров:72
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№2 слайд
![Линейные списки](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img1.jpg)
Содержание слайда: Линейные списки (однонаправленные цепочки)
Списком называется структура данных, каждый элемент которой посредством указателя связывается со следующим элементом.
Каждый элемент связанного списка
хранит какую-либо информацию,
указывает на следующий за ним элемент.
Так как элемент списка хранит разнотипные части (хранимая информация и указатель), то его естественно представить записью, в которой в одном поле располагается объект, а в другом – указатель на следующую запись такого же типа. Такая запись называется звеном, а структура из таких записей называется списком или цепочкой.
№4 слайд
![Для иллюстрации работы с](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img3.jpg)
Содержание слайда: Для иллюстрации работы с линейными списками рассмотрим задачу:
Для иллюстрации работы с линейными списками рассмотрим задачу:
Разработайте программу работы с односвязным списком. Программа должна содержать следующие процедуры, вызываемые из меню:
Добавление нового элемента в начало списка.
Добавление нового элемента в конец списка.
Удаление первого элемента.
Вывод списка на экран.
№5 слайд
![Описание списка Пример](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img4.jpg)
Содержание слайда: Описание списка
Пример описания списка
type ukaz=^spisok;
spisok=record
inf:integer;
next:ukaz;
end;
В Паскале существует основное правило: перед использованием какого-либо объекта он должен быть описан. Исключение сделано лишь для указателей, которые могут ссылаться на еще не объявленный тип.
var
ug:ukaz;
a:integer;
№6 слайд
![Разработаем программу методом](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img5.jpg)
Содержание слайда: Разработаем программу методом пошаговой детализации.
Разработаем программу методом пошаговой детализации.
Чтобы список существовал, надо определить указатель на его начало.
Создадим список:
begin
new(ug);
ug^.next:=nil;
Выведем названия пунктов меню соответствующих операциям работы со списками:
writeln('1. Dobavit element v nachalo');
writeln('2. Dobavit element v konets');
writeln('3. udalit 1 element');
writeln('4. exit');
№7 слайд
![Организуем бесконечный цикл,](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img6.jpg)
Содержание слайда: Организуем бесконечный цикл, и в зависимости от выбранного пользователем пункта меню будем вызывать соответствующие процедуры.
Организуем бесконечный цикл, и в зависимости от выбранного пользователем пункта меню будем вызывать соответствующие процедуры.
while true do
begin
writeln('viberite hunkt menu');
readln(a);
case a of
1: begin
writeln('Vvedite element'); readln(a);
dobavlenieVgol(ug,a); vivod(ug);
end;
2: begin
writeln('Vvedite element'); readln(a);
dobavlenieVxvost(ug,a); vivod(ug);
end;
№9 слайд
![А Добавим элемент в голову](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img8.jpg)
Содержание слайда: А) Добавим элемент в голову списка. Для этого необходимо выполнить последовательность действий:
А) Добавим элемент в голову списка. Для этого необходимо выполнить последовательность действий:
получить память для нового элемента;
поместить туда информацию;
присоединить элемент к голове списка.
procedure dobavlenieVgol(var ug:ukaz; z:integer);
var x:ukaz;
begin
new(x); {Выделяем память для нового элемента }
x^.inf:=z; {Помещаем информацию в поле inf типа integer}
x^.next:=ug^.next; {В поле next типа указатель помещаем тот адрес на который раньше ссылалась голова списка – адрес первого элемента}
ug^.next:=x; {Указатель головы списка переводим на новый элемент}
end;
№10 слайд
![Б Добавление элемента в конец](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img9.jpg)
Содержание слайда: Б)Добавление элемента в конец списка. Для этого необходимо выполнить последовательность действий:
Б)Добавление элемента в конец списка. Для этого необходимо выполнить последовательность действий:
Найти последний элемент списка.
Выделить память для нового элемента.
Поместить туда информацию.
Присоединить элемент к хвосту списка.
procedure dobavlenieVxvost(ug:ukaz; z:integer);
var x,y:ukaz;
Begin
x:=ug; {Копируем указатель на голову в переменную x}
while x^.next<>nil do x:=x^.next; {Пока просматриваемый элемент полем next не указывает на «пусто» (пока не достигнут конец списка) переходим к следующему элементу}
№11 слайд
![new y Выделяем память для](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img10.jpg)
Содержание слайда: new(y); {Выделяем память для нового элемента}
new(y); {Выделяем память для нового элемента}
y^.inf:=z; {Помещаем информацию в поле inf }
y^.next:=nil; {Следующего за новым элементом не будет, т.к. добавляем в хвост}
x^.next:=y; {Указатель последнего элемента списка переводим на новый элемент}
end;
№12 слайд
![Вывод списка на экран](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img11.jpg)
Содержание слайда: Вывод списка на экран
procedure vivod( ug:ukaz);
var x:ukaz;
begin
x:=ug^.next; {Копируем указатель на голову в переменную x}
write('spisok ');
if ug^.next=nil then {Если голова списка указывает на «пусто»}
writeln('pust')
else {Если голова списка не указывает на «пусто»}
№13 слайд
![while x lt gt nil do](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img12.jpg)
Содержание слайда: while x<>nil do {Выполняем цикл до тех пор, пока x не указывает на «пусто» (пока не дошли до конца списка)}
while x<>nil do {Выполняем цикл до тех пор, пока x не указывает на «пусто» (пока не дошли до конца списка)}
begin
write(x^.inf, ' '); {Выводим информацию из поля inf на экран}
x:=x^.next; {Переходим к следующему элементу}
end;
end;
№14 слайд
![Удаление первого элемента из](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img13.jpg)
Содержание слайда: Удаление первого элемента из списка
Во вспомогательном указателе запомним указатель на первый элемент.
Поле next указателя на голову переключим на второй (следующий за первым) элемент списка.
Освободим область динамической памяти, на которую указывает вспомогательный указатель.
procedure udalenie1(var ug:ukaz);
var x:ukaz;
begin
if ug^.next=nil then
begin
writeln('Spisok pust');
end
№15 слайд
![else else begin x ug .next Во](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img14.jpg)
Содержание слайда: else
else
begin
x:=ug^.next; {Во вспомогательном указателе запомним адрес первого элемента}
ug^.next:=x^.next; {Поле next указателя на голову переключим на второй (следующий за первым) элемент списка}
dispose(x); {Освободим область динамической памяти, на которую указывает вспомогательный указатель}
end;
end;
№16 слайд
![Продемонстрируем применение](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img15.jpg)
Содержание слайда: Продемонстрируем применение вышеприведенных процедур в итоговой программе:
Продемонстрируем применение вышеприведенных процедур в итоговой программе:
type ukaz=^spisok;
spisok=record
inf:integer;
next:ukaz;
end;
var
ug:ukaz;
a:integer;
procedure udalenie1(var ug:ukaz);
var x:ukaz;
begin
if ug^.next=nil then
№21 слайд
![writeln . Dobavit element v](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img20.jpg)
Содержание слайда: writeln('1. Dobavit element v nachalo');
writeln('1. Dobavit element v nachalo');
writeln('2. Dobavit element v konets');
writeln('3. udalit 1 element');
writeln('4. exit');
while true do
begin
writeln('viberite hunkt menu');
readln(a);
case a of
1: begin
writeln('Vvedite element'); readln(a);
dobavlenieVgol(ug,a); vivod(ug);
end;
№23 слайд
![Двунаправленный список](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img22.jpg)
Содержание слайда: Двунаправленный список
Использование однонаправленных списков при решении ряда задач может вызвать определенные трудности.
По однонаправленному списку можно двигаться только в одном направлении, от головы списка к последнему звену. Между тем нередко возникает необходимость произвести какую-либо операцию с элементом, предшествующим элементу с заданным свойством. Однако после нахождения элемента с данным свойством в однонаправленном списке у нас нет возможности получить удобный и быстрый способ доступа к предыдущему элементу.
Для устранения этого неудобства добавим в каждое звено списка еще одно поле, значением которого будет ссылка на предыдущее звено.
№24 слайд
![Type ukazat S S record Inf](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img23.jpg)
Содержание слайда: Type ukazat= ^S;
S= record
Inf: integer;
Next: ukazat;
Pred: ukazat;
End;
Type ukazat= ^S;
S= record
Inf: integer;
Next: ukazat;
Pred: ukazat;
End;
Динамическая структура, состоящая из звеньев такого типа, называется двунаправленным списком, который схематично можно изобразить так:
№25 слайд
![Наличие в каждом звене](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img24.jpg)
Содержание слайда: Наличие в каждом звене двунаправленного списка ссылки как на следующее, так и на предыдущее звено позволяет от каждого звена двигаться по списку в любом направлении. По аналогии с однонаправленным списком здесь есть заглавное звено. В поле Pred этого звена фигурирует пустая ссылка nil, свидетельствующая, что у заглавного звена нет предыдущего (так же, как у последнего нет следующего).
Наличие в каждом звене двунаправленного списка ссылки как на следующее, так и на предыдущее звено позволяет от каждого звена двигаться по списку в любом направлении. По аналогии с однонаправленным списком здесь есть заглавное звено. В поле Pred этого звена фигурирует пустая ссылка nil, свидетельствующая, что у заглавного звена нет предыдущего (так же, как у последнего нет следующего).
№27 слайд
![Как видно, здесь список](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img26.jpg)
Содержание слайда: Как видно, здесь список замыкается в своеобразное «кольцо»: двигаясь по ссылкам, можно от последнего звена переходить к заглавному звену, а при движении в обратном направлении – от заглавного звена переходить к последнему. Списки подобного рода называют кольцевыми списками.
Как видно, здесь список замыкается в своеобразное «кольцо»: двигаясь по ссылкам, можно от последнего звена переходить к заглавному звену, а при движении в обратном направлении – от заглавного звена переходить к последнему. Списки подобного рода называют кольцевыми списками.
Кольцевые списки бывают однонаправленными и двунаправленными.
№28 слайд
![Стек и очередь Стек вид](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img27.jpg)
Содержание слайда: Стек и очередь
Стек –вид списка, обращение к которому идет только через указатель на первый элемент. Если в стек нужно добавить элемент, то он добавляется впереди первого элемента, при этом указатель на начало стека переключается на новый элемент. Алгоритм работы со стеком характеризуется правилом: «последним пришел – первым вышел».
Очередь – это вид списка, имеющего два указателя на первый и последний элемент цепочки. Новые элементы записываются вслед за последним, а выборка элементов идет с первого. Этот алгоритм типа «первым пришел – первым вышел».
Возможно организовать списки с произвольным доступом к элементам. В этом случае необходим дополнительный указатель на текущий элемент.
№29 слайд
![Деревья Дерево это](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img28.jpg)
Содержание слайда: Деревья
Дерево – это совокупность элементов, называемых узлами (один из которых определен как корень), и отношений, образующих иерархическую структуру узлов.
Формально дерево определяется как конечное множество T одного или более узлов со следующими свойствами:
Существует один выделенный узел, а именно – корень данного дерева;
Остальные узлы (за исключением корня) распределены среди m непересекающихся множеств T1 , T2 , …. Tm , и каждое из этих множеств, в свою очередь, является деревом; деревья T1 , T2 , ... Tm называются поддеревьями данного корня.
№30 слайд
![Т.е. каждый узел дерева](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img29.jpg)
Содержание слайда: Т.е. каждый узел дерева является корнем некоторого поддерева данного дерева.
Т.е. каждый узел дерева является корнем некоторого поддерева данного дерева.
Количество поддеревьев узла называется степенью этого узла.
Узел с нулевой степенью называется концевым узлом или листом.
Каждый узел имеет уровень, который определяется следующим образом: уровень корня дерева равен нулю, а уровень любого другого узла на единицу выше, чем уровень корня ближайшего поддерева, содержащего данный узел.
№31 слайд
![Узел A является корнем,](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img30.jpg)
Содержание слайда: Узел A является корнем, который имеет два поддерева {B} и {C, D, E, F, G}. Корнем дерева {C, D, E, F, G} является узел C . Уровень узла C равен 1 по отношению ко всему дереву. Он имеет три поддерева {D}, {E} и {F, G}, поэтому степень узла C равна 3. Концевыми узлами (листьями) являются узлы B , D , E , G .
Узел A является корнем, который имеет два поддерева {B} и {C, D, E, F, G}. Корнем дерева {C, D, E, F, G} является узел C . Уровень узла C равен 1 по отношению ко всему дереву. Он имеет три поддерева {D}, {E} и {F, G}, поэтому степень узла C равна 3. Концевыми узлами (листьями) являются узлы B , D , E , G .
Предок узла, имеющий уровень на единицу меньше уровня самого узла, называется родителем. Потомки узла, уровень которых на единицу больше относительно самого узла, называются сыновьями или детьми.
№32 слайд
![Обходы дерева Существует](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img31.jpg)
Содержание слайда: Обходы дерева
Существует несколько способов обхода всех узлов дерева. Три наиболее часто используемых способа обхода называются прямой, обратный и симметричный обходы. Все три способа можно рекурсивно определить следующим образом:
Если дерево T является нулевым деревом, то в список обхода записывается пустая строка;
Если дерево T состоит из одного узла, то в список обхода записывается этот узел;
Пусть дерево T имеет корень n и поддеревья T1, T2, ... Tm,
№33 слайд
![Прямой обход. Сначала](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img32.jpg)
Содержание слайда: Прямой обход. Сначала посещается корень n , затем в прямом порядке узлы поддерева T1, далее все узлы поддерева T2 и т.д. Последними посещаются в прямом порядке узлы поддерева Tm .
Прямой обход. Сначала посещается корень n , затем в прямом порядке узлы поддерева T1, далее все узлы поддерева T2 и т.д. Последними посещаются в прямом порядке узлы поддерева Tm .
Обратный обход. Сначала посещаются в обратном порядке все узлы поддерева T1, затем в обратном порядке узлы поддеревьев T2 … Tm, последним посещается корень n .
Симметричный обход. Сначала в симметричном порядке посещаются все узлы поддерева T1 , затем корень n , после чего в симметричном порядке все узлы поддеревьев T2 … Tm .
№34 слайд
![Порядок узлов данного дерева](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img33.jpg)
Содержание слайда: Порядок узлов данного дерева в случае прямого обхода будет следующим: 1 2 3 5 8 9 6 10 4 7.
Порядок узлов данного дерева в случае прямого обхода будет следующим: 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.
№35 слайд
![Двоичные деревья Двоичное или](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img34.jpg)
Содержание слайда: Двоичные деревья
Двоичное или бинарное дерево – это наиболее важный тип деревьев. Каждый узел бинарного дерева имеет не более двух поддеревьев, причем в случае только одного поддерева следует различать левое или правое.
Бинарное дерево – это конечное множество узлов, которое является либо пустым, либо состоит из корня и двух непересекающихся бинарных деревьев, которые называются левым и правым поддеревьями данного корня.
Бинарное дерево можно представить в виде динамической структуры данных, состоящей из узлов, каждый из которых содержит кроме данных не более двух ссылок на правое и левое бинарное дерево. На каждый узел имеется одна ссылка. Начальный узел называется корнем.
№36 слайд
![По аналогии с элементами](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img35.jpg)
Содержание слайда: По аналогии с элементами списков, узлы дерева удобно представить в виде записей, хранящих информацию и два указателя:
По аналогии с элементами списков, узлы дерева удобно представить в виде записей, хранящих информацию и два указателя:
Пример
type ptree=^tree;
tree=record
inf:integer;
left,right:ptree;
end;
№37 слайд
![Дерево поиска Способ](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img36.jpg)
Содержание слайда: Дерево поиска
Способ построения дерева, при котором для каждого узла все ключи (значения узлов) его левого поддерева меньше ключа этого узла, а все ключи его правого поддерева больше, называется деревом поиска или двоичным упорядоченным деревом.
С помощью дерева поиска можно организовать эффективный способ поиска, который значительно эффективнее поиска по списку.
Поиск в дереве поиска выполняется по следующему рекурсивному алгоритму:
Если дерево не пусто, то нужно сравнить искомый ключ с ключом в корне дерева:
- если ключи совпадают, поиск завершен;
- если ключ в корне больше искомого, выполнить поиск в левом поддереве;
- если ключ в корне меньше искомого, выполнить поиск в правом поддереве.
Если дерево пусто, то искомый элемент не найден.
№38 слайд
![Дерево поиска может быть](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img37.jpg)
Содержание слайда: Дерево поиска может быть использовано для построения упорядоченной последовательности ключей узлов. Например, если мы используем симметричный порядок обхода такого дерева, то получим упорядоченную по возрастанию последовательность.
Дерево поиска может быть использовано для построения упорядоченной последовательности ключей узлов. Например, если мы используем симметричный порядок обхода такого дерева, то получим упорядоченную по возрастанию последовательность.
Можно организовать «зеркально симметричный» обход, начиная с правого поддерева, тогда получим упорядоченную по убыванию последовательность.
Таким образом, деревья поиска можно применять для сортировки значений.
№39 слайд
![Разработайте программу работы](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img38.jpg)
Содержание слайда: Разработайте программу работы с бинарным деревом. Программа должна содержать следующие процедуры, вызываемые из меню:
Разработайте программу работы с бинарным деревом. Программа должна содержать следующие процедуры, вызываемые из меню:
построение пустого дерева;
добавление нового элемента;
просмотр дерева в симметричном порядке: левая ветвь, узел, правая ветвь;
поиск элемента;
удаление элемента.
№41 слайд
![Добавление элемента Для того](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img40.jpg)
Содержание слайда: Добавление элемента
Для того чтобы вставить узел, необходимо найти его место. Для этого мы сравниваем вставляемое значение с корнем, если оно больше, чем значение корня, уходим в правое поддерево, а иначе – в левое. Тем же образом продвигаемся дальше, пока не дойдем до конечного узла (листа). Сравниваем вставляемое значение со значением листа. Если оно меньше, то добавляем листу левого сына, а иначе – правого сына.
procedure (var kor:ptree; z:integer);
begin
if kor=nil then {Если дерево пустое, то добавляемый элемент станет корнем}
begin
new(p); {Выделяем память для нового элемента}
№42 слайд
![p .inf z Записываем в поле](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img41.jpg)
Содержание слайда: p^.inf:=z; {Записываем в поле inf информацию}
p^.inf:=z; {Записываем в поле inf информацию}
p^.left:=nil;{Левые и правые сыновья нового элемента nil}
p^.right:=nil; {т.к. в дерево можно добавлять только лист}
kor:=p
end
else {Если дерево не пустое}
begin
if z<kor^.inf then
begin { Если вставляемое значение меньше значения корня}
if kor^.left=nil then {и у корня нет левого сына, то добавим новое значение левым сыном корня}
№44 слайд
![end end else if kor .right](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img43.jpg)
Содержание слайда: end
end
else if kor^.right=nil then {если вставляемое значение не меньше корня, то, если у корня нет правого сына, то добавляем новое значение в качестве правого сына корня}
begin
new(p);
p^.inf:=z;
p^.left:=nil;
p^.right:=nil;
kor^.right:=p
end
else dobavl(kor^.right, z); {если у корня есть правый сын, то вызываем процедуру добавления (рекурсия) для правого сына (т.е. теперь правый сын рассматривается как корень)}
end; {Заканчиваем случай, когда дерево не пустое}
end;
№45 слайд
![Обход дерева и вывод на экран](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img44.jpg)
Содержание слайда: Обход дерева и вывод на экран (левая ветвь, корень, правая ветвь)
procedure vivod(kor:ptree);
begin
if kor^.left<>nil then vivod(kor^.left); {Если у узла kor есть левый сын, то вызываем процедуру вывод для левого сына вершины kor}
writeln(kor^.inf); {Выводим информацию узла kor}
if kor^.right<>nil then vivod(kor^.right); {Если у узла kor есть правый сын, то вызываем процедуру вывод для правого сына вершины kor}
end;
№46 слайд
![Поиск узла с заданным](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img45.jpg)
Содержание слайда: Поиск узла с заданным значением
Функция poisk не только возвращает значение true, если в дереве есть искомый элемент со значением z, и false, если такого элемента нет, но и находит указатели на этот элемент (p) и на его предка (parent), они передаются в качестве параметров-переменных.
function poisk(kor:ptree; z:integer; var p,parent:ptree):boolean;
begin
P:=kor; {Начинаем поиск с корня}
parent:=nil;
while p<>nil do {Пока мы не «выйдем за границы дерева»}
begin
if z=p^.inf then {Если узел p имеет искомое значение z}
begin {Элемент найден, выходим из процедуры}
poisk:=true; exit;
end;
№47 слайд
![parent p текущее значение](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img46.jpg)
Содержание слайда: parent:=p; {текущее значение указателя p сохраняем в переменной parent как предка}
parent:=p; {текущее значение указателя p сохраняем в переменной parent как предка}
if z<p^.inf then p:=p^.left {Если искомое значение z меньше информации в текущем узле p, то рассмотреть в качестве p его левого сына (спуститься влево)}
else p:=p^.right; {Если искомое значение z больше информации в текущем узле p, то рассмотреть в качестве p его правого сына (спуститься вправо)}
end; {Конец цикла, пока не «выйдем за границы дерева»}
poisk:=false; {Если мы не нашли элемента с искомым значением z, то его в дереве нет}
end;
№50 слайд
![Сложнее всего случай, когда у](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img49.jpg)
Содержание слайда: Сложнее всего случай, когда у удаляемого узла есть оба потомка.
Сложнее всего случай, когда у удаляемого узла есть оба потомка.
Есть простой особый случай: если у правого потомка удаляемого узла нет левого потомка, удаляемый узел заменяется на своего правого потомка, а левый потомок удаляемого узла подключается вместо отсутствующего левого потомка к замещающему узлу.
№51 слайд
![В общем же случае на место](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img50.jpg)
Содержание слайда: В общем же случае на место удаляемого узла ставится самый левый узел его правого поддерева (или наоборот – самый правый узел его левого поддерева). Это не нарушает свойств дерева поиска.
В общем же случае на место удаляемого узла ставится самый левый узел его правого поддерева (или наоборот – самый правый узел его левого поддерева). Это не нарушает свойств дерева поиска.
№52 слайд
![procedure del var kor ptree z](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img51.jpg)
Содержание слайда: procedure del(var kor:ptree; z:integer); {Удаляет узел со значением z из дерева с корнем kor}
procedure del(var kor:ptree; z:integer); {Удаляет узел со значением z из дерева с корнем kor}
var
p:ptree; {указатель, в котором будет храниться адрес удаляемого элемента}
parent:ptree; {указатель, в котором будет храниться адрес предка удаляемого элемента (чтобы знать к кому подключать замещающий элемент)}
y:ptree; {указатель, в котором будет храниться адрес замещающего элемента}
Для процедуры удаления нам понадобится вспомогательная функция findZamena, которая возвращает указатель на узел, замещающий удаляемый, кроме этого в ней осуществляются все необходимые действия по переподключению узлов, чтобы дерево сохранило свойства дерева поиска. В нее передается указатель на удаляемый узел p.
№53 слайд
![function findZamena p ptree](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img52.jpg)
Содержание слайда: function findZamena(p:ptree):ptree;
function findZamena(p:ptree):ptree;
var
y:ptree; {Указатель на узел, замещающий удаляемый}
predy:ptree; {Указатель на предка узла, замещающего удаляемый}
begin
if p^.left=nil then y:=p^.right {Если у удаляемого узла нет левого потомка, то замещающим станет правый потомок удаляемого узла}
else if p^.right=nil then y:=p^.left {Если у удаляемого узла есть левый потомок, но нет правого потомка, то замещающим станет левый потомок удаляемого узла}
else {Если у удаляемого узла есть оба потомка}
begin
y:=p^.right; {Указатель на узел, замещающий удаляемый, переводим на правого сына удаляемого узла
( переходим в правое поддерево)}
№54 слайд
![if y .left nil then y .left p](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img53.jpg)
Содержание слайда: if y^.left=nil then y^.left:=p^.left {Если у правого сына удаляемого узла (на него указывает y) нет левого сына, то наш поиск окончен (удаляемый узел заменяется на своего правого потомка, а именно на него указывает y), необходимо только левого потомка удаляемого узла p подключить к замещающему узлу y вместо отсутствующего левого потомка}
if y^.left=nil then y^.left:=p^.left {Если у правого сына удаляемого узла (на него указывает y) нет левого сына, то наш поиск окончен (удаляемый узел заменяется на своего правого потомка, а именно на него указывает y), необходимо только левого потомка удаляемого узла p подключить к замещающему узлу y вместо отсутствующего левого потомка}
else {Если у правого сына удаляемого узла есть левый сын}
begin
repeat
predy:=y; {Текущее значение указателя y сохраняем в качестве указателя на предка y}
y:=y^.left; {А указатель у переводим на его левого сына (идем по самой левой ветке, чтобы найти самый левый узел его правого поддерева)}
until y^.left<>nil; {Действия повторяем до тех пор, пока не дойдем до узла у которого нет левого сына, он и должен заменить удаляемый узел}
№55 слайд
![y .left p .left Подключаем к](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img54.jpg)
Содержание слайда: y^.left:=p^.left; {Подключаем к узлу y, замещающему удаляемый узел p, левого потомка удаляемого узла (своего левого у него нет)}
y^.left:=p^.left; {Подключаем к узлу y, замещающему удаляемый узел p, левого потомка удаляемого узла (своего левого у него нет)}
predy^.left:=y^.right; {Правого сына замещающего узла y подключаем в качестве левого сына к предку y (на то место, где раньше был y)}
y^.right:=p^.right; {Правого сына удаляемого узла p подключаем в качестве правого сына к замещающему узлу y }
end;
end;
findZamena:=y; {Имени функции присваиваем результат}
end; {Конец процедуры findZamena}
№56 слайд
![begin начало самой процедуры](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img55.jpg)
Содержание слайда: begin {начало самой процедуры удаления del }
begin {начало самой процедуры удаления del }
{При вызове процедуры poisk, которая возвращает значение булевского типа, в переменной p возвращается указатель на удаляемый элемент, а в переменной parent указатель на его предка}
if not poisk(kor, z, p, parent) then {Если в дереве с корнем kor не найден удаляемый элемент z}
begin
writeln('net elementa'); {Выводим соответствующее сообщение}
exit; {И выходим из процедуры}
end;
y:=findZamena(p); {у присваиваем указатель на элемент, замещающий удаляемый элемент p, и производим все необходимые переподключения узлов, чтобы наше дерево сохранило свойства дерева поиска}
№57 слайд
![if p kor then kor y Если](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img56.jpg)
Содержание слайда: if p=kor then kor:=y {Если удаляемый элемент является корнем дерева, надо указателю на корень присвоить указатель на замещающий элемент y}
if p=kor then kor:=y {Если удаляемый элемент является корнем дерева, надо указателю на корень присвоить указатель на замещающий элемент y}
else {иначе – присоединить этот указатель к соответствующему поддереву предка parent удаляемого узла}
if z<parent^.inf then parent^.left:=y {Если удаляемое значение z меньше значения узла parent, то удаляемый узел был левым сыном parent и мы подключаем замещающий узел y в качестве левого сына}
else parent^.right:=y; {В противном случае удаляемый узел был правым сыном parent и мы подключаем замещающий узел y в качестве правого сына}
dispose(p); {Освобождаем память, занимаемую указателем p}
end; {Конец процедуры del}
№58 слайд
![Вся программа Вся программа](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img57.jpg)
Содержание слайда: Вся программа:
Вся программа:
Разработайте программу работы с бинарным деревом. Программа должна содержать следующие процедуры, вызываемые из меню:
построение пустого дерева;
добавление нового элемента;
просмотр дерева в следующем порядке: левая ветвь, узел, правая ветвь;
поиск элемента;
удаление элемента.
№64 слайд
![procedure Vivod kor ptree](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img63.jpg)
Содержание слайда: procedure Vivod(kor:ptree);
procedure Vivod(kor:ptree);
begin
if kor^.left<>nil then
Vivod(kor^.left);
Writeln(kor^.inf);
if kor^.right<>nil then
Vivod(kor^.right);
end;
function Poisk(kor:ptree; z:integer; var p,parent:ptree):boolean;
begin
P:=kor;
while p<>nil do
begin
№66 слайд
![procedure del var kor ptree z](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img65.jpg)
Содержание слайда: procedure del(var kor:ptree; z:integer);
procedure del(var kor:ptree; z:integer);
var
p:ptree; {udaljaemij el}
parent:ptree; {predok p}
y:ptree; {zamenit p}
function findZamena(p:ptree):ptree;
var
y:ptree; {zamena p}
predy:ptree; {predok y}
begin
if p^.left=nil then y:=p^.right
else
if p^.right=nil then y:=p^.left
else
№72 слайд
![Домашнее задание . Составить](/documents_6/fc52b72c4ea2891e5cc3c9c10d29df10/img71.jpg)
Содержание слайда: Домашнее задание
1. Составить опорный конспект лекции по теме «Динамические структуры данных и их организация с помощью указателей. Стеки, Очереди, односвязные и двухсвязные линейные списки и кольца. Бинарные деревья» на основе презентации.
2. Программирование на языке Pascal. Рапаков Г. Г., Ржеуцкая С. Ю. СПб.: БХВ-Петербург, 2004, стр. 339-366.
Скачать все slide презентации Динамические структуры данных и их организация с помощью указателей одним архивом:
Похожие презентации
-
Динамические структуры данных (язык Паскаль)
-
Динамические данные разветвленной структуры
-
Динамические структуры данных: очереди и стеки
-
Динамические структуры данных: списки
-
Динамические структуры данных. Односвязные и двусвязные списки
-
Основы алгоритмизации и программирования. Лекция 15. Динамические структуры данных
-
Динамические структуры данных. Стек, очередь, дек, деревья
-
Динамические структуры данных. Деревья
-
Динамические структуры данных. Стеки и очереди
-
Динамические структуры данных. Графы