|
|
Удаление элемента из списка. ⇐ ПредыдущаяСтр 4 из 4 При удалении элемента из списка необходимо различать три случая:1. Удаление элемента из начала списка. 2. Удаление элемента из середины списка. 3. Удаление из конца списка. Удаление элемента из начала списка. List:= Head; { запомним адрес первого элемента списка }Head:= Head^.List; { теперь Head указывает на второй элемент списка }Dispose(List); { освободим память, занятую переменной List^ } Удаление элемента из середины списка. Для этого нужно знать адреса удаляемого элемента и элемента, находящегося в списке перед ним.List:= Head;While (List<>nil) and (List^.Data<>Digit) do begin x:= List; List:= List^.Next; end;x^.Next:= List^.Next;Dispose(List); Удаление из конца списка.Оно производится, когда указатель х показывает на предпоследний элемент списка, а List – на последний.List:= Head; x:= Head;While List^.Next<>nil do begin x:= List; List:= List^.Next; end;x^.Next:= nil;Dispose(List);Контрольные вопросы 1. Что такое указатели? Какие значения они могут принимать? Какие операции возможны над указателями? 2. Что представляют собой динамические структуры данных? Для чего они используются? Чем отличаются от данных статического типа? 3. Какие стандартные процедуры существуют в языке Pascal для работы с указателями? 4. Зачем различать типы указателей? 5. Какие операции требуется выполнить для вставки и удаления элемента списка? 6. Сколько элементов может содержать список? 7. Можно ли для построения списка обойтись одной переменной? Варианты заданий 1. Сформировать список строк и а) сохранить его в текстовом файле; б) сохранить его в обратном порядке в текстовом файле. Использовать рекурсию. 2. Сформировать список строк из текстового файла. 3. Написать функцию, которая вычисляет среднее арифметическое элементов непустого списка. 4. Написать процедуру присоединения списка L2 к списку L1. 5. Написать функцию, которая создает список L2, являющийся копией списка L1, начинающегося с данного узла. 6. Написать функцию, которая подсчитывает количество вхождений ключа в списке. 7. Написать функцию, которая удаляет из списка все вхождения ключа. 8. Многочлен – Equal(p, q), проверяющую на равенство многочлены p и q; – Summa(p, q, r), которая строит многочлен r = p + q. 9. Вычислить значение многочлена 10. Сформировать список целых чисел и упорядочить их по неубыванию. 11. Сформировать список целых чисел и удалить из него все четные. 12. Сформировать список вещественных чисел и вычислить сумму. 13. Написать рекурсивную и нерекурсивную процедуры проверки наличия в списке заданного числа. 14. Написать функцию, которая проверяет, упорядочены ли элементы списка по алфавиту. 15. Написать функцию, подсчитывающую количество слов в списке, которые начинаются с той же буквы, что и следующее слово. 16. Определить симметричность произвольного текста любой длины. Текст должен оканчиваться точкой. Задачу решить с помощью двух списков. 17. Вычислить значение выражения 18. Написать функцию, которая использует исходный список L и создает два новых списка L1 и L2. L1 содержит нечетные узлы, а L2 – четные. 19. Написать функцию, которая использует исходный список L и создает два новых списка L1 и L2. L1 содержит нечетные числа, а L2 – четные. 20. Сформировать два списка, отсортировать их объединить в один, не нарушая порядка.
Лабораторная работа №7 Стек Цель работы: Закрепить технику работы с динамическими структурами данных на примере стека. Рассмотреть основные операции со стеком и познакомится с типичными примерами применения стека. Общие сведения Стек – упорядоченный набор элементов, в котором добавление новых элементов и удаление существующих производится с одного конца, называемого вершиной стека. В любой момент времени доступен лишь один элемент стека – верхний. Извлекать элементы из стека можно только в порядке, обратном их добавления в стек (первым пришел, последним ушел). Значением указателя, представляющего стек, является ссылка на вершину стека, каждый элемент стека содержит поле ссылки на следующий элемент. Таким образом, описать стек, содержащий, например, целые числа, можно следующим образом: Type PStack = ^TStack; TStack = Record Data: Integer; Next: PStack; end;Var Stack: PStack;Если стек пуст, то значение переменной Stack равно nil. Примеры Занесение в стек. Занесение в стек производится аналогично вставке нового элемента в начало списка: Var x: PStack;…………… New(x); x^.Data:= …….; x^.Next:= Stack; Stack:= x;……………Извлечение элемента из стека. В результате выполнения этой операции некоторой переменной N должно быть присвоено значение первого элемента стека и изменено значение указателя на начало стека: Var N: Integer; x: PStack;…………………. N:= Stack^.Data; x:= Stack; Stack:= Stack^.Next; Dispose(x);………………….Контрольные вопросы 1. В чем сходство и отличие динамических структур данных типа список и стек? 2. Можно ли добраться до середины или конца («дна») стека, минуя его начало («вершину»)? 3. Приведите примеры из жизни, где встречается «принцип стека». 4. Оформите в виде процедуры Push занесение в стек значения. 5. Оформите в виде процедуры Pop извлечение значения из стека. Варианты заданий 1. Подсчитать количество элементов в стеке. 2. Сформировать стек, содержащий строки и сохранить его в текстовом файле. 3. Восстановить стек, содержащий строки, из текстового файла. 4. Написать функцию, которая вычисляет среднее арифметическое элементов стека. 5. Написать процедуру присоединения стека S2 к стеку S1. 6. Определить симметричность произвольного текста любой длины. Текст должен оканчиваться точкой. Задачу решить с помощью двух стеков. 7. Слить два стека, содержащих возрастающую последовательность целых положительных чисел, в третий стек так, чтобы его элементы располагались также в порядке возрастания. 8. В данном тексте проверить соответствие открытия и закрытия скобок. 9. Напечатать содержимое текстового файла, выписывая символы каждой его строки в обратном порядке. 10. Проверить, является ли строка палиндромом.
Лабораторная работа №8 Двоичные деревья Цель работы: Изучить способы эффективного хранения и обработки информации на примере бинарных деревьев. Общие сведения Бинарное дерево - это иерархическая динамическая структура данных, состоящая из узлов и соединяющих их дуг. В каждый узел, кроме одного, ведет ровно одна дуга. Этот единственный узел называется корнем дерева. С каждой вершиной дерева связывается конечное число отдельных деревьев, называемых поддеревьями. На рисунке изображено дерево, в узлах которого располагаются символы:
Вершина Y, находящаяся непосредственно ниже вершины X, называется непосредственным потомком X, а вершина X называется предком Y. Если вершина не имеет потомков, то она называется листом, если имеет, то называется внутренней вершиной. Например, вершины D, E являются непосредственными потомками вершины B; вершины H, I, J являются листьями. Очевидно, что для описания дерева требуются ссылки. Опишем бинарное дерево как структуру типа Record, содержащую как минимум два поля – указатели на левое и правое поддеревья, и поле данных, например типа Integer: Type PTree = ^TTree; TTree = Record Data: Integer; Left, Right: PTree; end;Корень дерева описывается ссылочной переменной:Var Tree: PTree;Основные операции над деревом К основным операциям над деревьями относятся: • занесение элемента в дерево; • обход дерева; • удаление элемента из дерева. Примеры Вставка элемента в дерево. Создать и вывести на экран дерево, элементы которого вводятся с клавиатуры и имеют целый тип. Причем для каждой вершины дерева во всех левых вершинах должны находиться числа меньшие, а в правой большие, чем числа, хранящиеся в этой вершине. Такое дерево называется деревом поиска. Опишем процедуру вставки в дерево новой вершины. При вставке в дерево вершина вставляется либо как поддерево уже существующей вершины или как единственная вершина дерева. Поэтому и левая, и правая связи новой вершины должны быть равны nil. Когда дерево пусто, значение передаваемой в виде параметра ссылки равно nil. В этом случае нужно изменить ее так, чтобы она указывала на новую вершину, которая была вставлена как корневая. При вставке второго элемента переданный из основной программы параметр ANode уже не будет равен nil, и надо принимать решение о том, в какое поддерево необходимо вставить новую вершину. Procedure InsTree(var ANode: PTree; n: lnteger);Begin if ANode = nil then Begin new(ANode); With ANode^ do Begin Left:= nil; Right:= nil; Data:= n; end; end else if n< ANode^.Data then InsTree(ANode^.Left, n) else InsTree(ANode^.Right, n);End;Вывод элементов дерева. Опишем процедуру вывода значений элементов двоичного дерева на экран. Для этого необходимо выполнить полный обход дерева. При обходе дерева его отдельные вершины посещаются в определенном порядке. Вывод двоичного дерева можно производить рекурсивно, выполняя для каждой вершины три действия: • вывод числа, хранящегося в узле; • обход левого поддерева; • обход правого поддерева. Порядок выполнения этих действий определяет способ обхода дерева. Способы обхода: • прямой обход (сверху вниз); • симметричный обход (слева направо); • обратный обход (снизу вверх). Процедура симметричного вывода дерева имеет следующий вид: Procedure PrintTree(ANode: PTree);Begin if ANode <> nil then Begin PrintTree(ANode^.Left); WriteLn(ANode^.Data); PrintTree(ANode^.Right) End;End;Основная программа осуществляет ввод чисел с клавиатуры. Используются: переменная Tree типа PTree – значение указателя на корень дерева; переменная Digit типа Integer для хранения очередного введенного числа.Var Tree: PTree; Digit: Integer;BEGIN {основная программа} Writeln(‘Окончание ввода – 0’); Tree:= nil; Read(Digit); While Digit<>0 Do Begin InsTree(Tree,Digit); Write(‘Введите очередное число: ‘); ReadLn(Digit); End; PrintTree(Tree);END. Удаление из дерева. Непосредственное удаление элемента из упорядоченного дерева реализуется достаточно просто, если эта вершина является конечной:
или из нее выходит только одно ребро:
Для этого нужно изменить соответствующую ссылку у предшествующей вершины. Если же из удаляемой вершины выходит две ветви, то нужно найти подходящую вершину дерева, которую можно было бы вставить на место удаляемой вершины. В этом случае удаляемый элемент нужно заменить либо на самый правый элемент его левого поддерева, либо на самый левый элемент его правого поддерева. Такие элементы не могут иметь более одного потомка. Пусть задана следующая структура: Type PTree = ^TTree; TTree = Record Data: Integer; Left, Right: PTree; end;Var Tree: PTree;Необходимо удалить из дерева Tree узел со значением поля Data=x.В процедуре DeleteNode различаются три случая:1. Узла со значение, равным х, нет.2. Узел со значением х имеет не более одного потомка.3. Узел со значением х имеет двух потомков.Procedure DeleteNode(x: Integer; var ANode: PTree);Var q: PTree;Procedure Del(var R: PTree);Begin if R^.Right <> nil then Del(R.^Right) else begin q^.Data:= R^.Data; q:= R; R:= R^.Left; Dispose(q); end;End; { Del }Вegin { DeleteTree } if ANode = nil then Writeln(‘Элемента с ключом ’,x,’ в дереве нет’) else if x < ANode^.Data then DeleteNode(x,ANode^.Left) else if x > ANode^.Data then DeleteNode(x,ANode^.Right) else begin q:= ANode; if q^.Right = nil then Begin ANode:= q^.Left; Dispose(q); end else if q^.Left = nil then begin ANode:= q^.Right; Dispose(q); end else Del(q^.Left); end;End;Вспомогательная процедура Del вызывается только в третьем случае. Она «спускается» вдоль самой правой ветви левого поддерева удаляемого узла q^ и затем заменяет данные (поле Data) в q^ соответствующими значениями самого правого узла R^ этого левого поддерева, после чего от R^ можно освободиться. На рисунке задано начальное дерево (а), из которого последовательно удаляются узлы со значениями 13, 15, 5, 10. Полученные деревья показаны на рис. b – e. Контрольные вопросы 1. Что такое рекурсивный алгоритм? 2. Из каких частей строится определение рекурсивного алгоритма? 3. Что является обязательным в любом рекурсивном алгоритме? 4. Можно ли рекурсию заменить итерацией? Можно ли итерацию заменить рекурсией? 5. Каков принцип построения динамической структуры «дерево»? 6. Перечислите сходства и отличия динамических структур типа «линейный список», «стек», «дерево». 7. Перечислите структуры, которые можно представить в виде дерева, которые встречаются в повседневной жизни. 8. Закончите фразу: «Список – это дерево, в котором …». Задачи   Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...  Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...  ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...  Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|
задан своими коэффициентами, которые хранятся в форме списка. Написать функции:
. Значения 
вводятся с клавиатуры и динамически размещаются в памяти.
