Основы программирования (947332), страница 40
Текст из файла (страница 40)
Разработать программу, которая строит список, сортированный по возрастанию элементов, из целых чисел, вводимых с клавиатуры.Количество чисел не известно, но отлично от нуля. Конец ввода ~ по комбинации CTRL-Z (конец файла на устройстве ввода).Список сортирован, соответственно, добавляя элемент, необходимо сохранить закон сортировки: элемент должен вставляться перед первым элементом, который больше, чем добавляемый. В зависимости от конкретныхданных он может вставляться в начало, середину и конец списка.new(first);{запрашиваем память под первый элемент}ReadLn(first \nuin); {заносим число в информационное поле}first\p:=nil;while not EOF dobeginnew(q);{создаем элемент}ReadLn(q\num); {заносим значение}if q\num<first\num then {если элемент меньше первогоэлемента списка, то}2327.
Программирование с использованием динамической памятиbegin{вставляем перед первым}q\p:=first;firsU-q;endelse(иначе вставляем в середину или конец}beginn:-first;{указатель на текущий элемент}f:-first;{указатель на предыдущий элемент}flag:^false;{"элемент не вставлен"}{цикл поиска места вставки}while (n\ponil)and (not flag) dobeginn:=n\p; {переходим к следующему элементу}if q^,num<n\num then {место найдено}begin{вставляем в середину}q\p:^f\p;f''>p:^q;y7ag;=/rwe; {"элемент вставлен"}endelsef:-n;{сохраняем адрес текущего элемента}end;if not flag then {если элемент не вставлен, то}begin{вставляем после последнего}q\p:-nil;f\p:^q;end;end;end;Просмотр и обработка элементов списка.
Просмотр и обработка элементов списка выполняется последовательно с использованием дополнительного указателя:f:-=first;while fonil dobegin<обработка элемента по адресу f>end;...В качестве примера рассмотрим вывод на экран элементов списка:233Часть I. Основы алгоритмизации и процедурное программированиеf:=first;while fonil dobeginWriteLn(f\num, * *);end; ...Поиск элемента в списке. Поиск элементов в списке также выполняется последовательно, но при этом, как это и положено в поисковом цикле,обычно организуют выход из цикла, если нужный элемент найден, и осуществляют проверку после цикла, был ли найден элемент:fi^flrst;flag:--false;while (fonil) and (not flag) dobeginiff \num=k then flag:^notflagelsef:^f\p;end;if flag then <элемент найден >else <элемент не найден>; ...Удаление элемента из списка.
При выполнении операции удалениятакже возможно четыре случая:• удаление единственного элемента;• удаление первого (не единственного) элемента списка;• удаление элемента, следующего за данным;• удаление последнего элемента.Удаление единственного элемента. После удаления единственного элемента список становится пустым, следовательно при выполнении этой операции необходимо не только освободить память, выделенную для размещения элемента, но и занести nil в указатель списка first (рис. 7.14):first^234firstЩ''first[1]Dispose(first);first:^nil; ...*Удаление первого (не единстDisposefflrst); first: ^пН; венного) элемента списка. Удалеабв"^® первого элемента состоит из сохранения адреса следующего элеРис.
7.14. Удалениемента в рабочей переменной f, осединственного элемента списка:вобождения памяти элемента и зал-исходное состояние; б-освобождениеписи В указатель списка сохраненпамяти; в - занесение константы nil вного адреса следующего элементауказатель списка(рис. 7.15):7. Программирование с использованием динамической памятиfirstЛЕйrJL^^f:^firsi\p;firstiiiMД- ,1г—firstTT0lDispose(first):eпТТ0first: =/•гРис. 7.15. Удаление первого (не единственного)элемента списка:а - исходное состояние; б - сохранение адреса следующего элемента вспециальном указателе; в - освобождение памяти; г - запись в указатель списка адреса следующего элементаf:='first\p;(сохраняем адрес следующего элемента}Dispose(first); {освобождаем память}first:"=/; ...(заносим в указатель списка адрес следующегоэлемента}Удаление единственного элемента и первого элемента в программе можно объединить:q—first;first :=first\p;Dispose(q);...Удаление элемента, следующего за данным (не последнего).
Удалениеэлемента, следующего за данным, требует запоминания адреса удаляемогоэлемента, изменения адресной части данного элемента и освобождения памяти (рис. 7.16).n:=f^,p;f^,p:=n\p;(сохраняем адрес удаляемого элемента}(заносим в адресное поле предыдущего элемента адрес следующего элемента}Dispose(n); ... (освобождаем память}235Часть L Основы алгоритмизации и процедурное программированиеfirstIизчшэчхшfirstfnсиэчзпзч ЕГЭЧХШУдаление последнего элемента.
Удаление последнего элемента отличается только тем, что вполе «адрес следующего» заданного элемента записывается константа nil:n:=f^p;f\p:=nil;Dispose(п); ...n-.^f'^.p;Удаление последнего элемента можно свести к удалениюэлемента, следующего за данfirstfnным, так как адресная часть удаляемого элемента равна nil.9"ТЯ;?Г8Т0]Комбинируя приемы удаления,мы также можем организоf\p:=n\p;вать любую дисциплину удаления.Пример 7.5.
Разработатьfirstfпрограмму, которая удаляет изсписка все элементы меньше за7TT]Д"8Т01 данного значения к.Удаляемые значения могутDispose(n);располагаться в списке на любомместе, следовательно, возможнывсе четыре варианта удаленияРис. 7.16. Удаление элемента, следуюэлемента, которые сводятся кщего за данным (не последнего):двум случаям:а - исходное состояние; б - сохранение адреса• удаление единственногоудаляемого элемента; в - исключение удаляемогоэлемента и удаление записей изэлемента из списка; г - освобождение памятиначала списка-удаление из начала списка;• удаление средних и последнего элементов - удаление не из началасписка. Для разделения этих двух случаев введем специальный признак«удаление из начала», который в начале установим равным true, а затем, кактолько в списке будет оставлен хотя бы один элемент - изменим на false.пизчn.-'^Jirst;nft:=true;{признак «удаление из начала списка»}repeatifn^.num<kthenbegin2367.
Программирование с использованием динамической памятиifnft then {если «удаление из начала списка»}begin {удаление из начала списка}q:^firsi;first:=first^.p;Dispose(q);n:-first; {переходим к следующему элементу}endelse{иначе}begin{удаление из середины и конца}q:^n;п:-п\р; {переходим к следующему элементу}В18ро8е(ф;f\p:^n;endendelse {оставляем элемент в списке}beginf:-n;{устанавливаем адрес предыдущего элемента}п:-п\р;{переходим к следующему элементу}nft:='not nft {«удаление не из начала списка»}end;until n-nil;...{до завершения списка}Задания для самопроверкиЗадание 1. Разработайте профамму, которая вводит с клавиатуры последовательность чисел до символа «#», а затем удаляет из нее все числа, превышающиесреднее арифметическое чисел введенной последовательности.
Оставшиеся значения выведите в обратном порядке.Задание 2. Разработайте программу, которая вводит с клавиатуры последовательность чисел до символа «#», а затем определяет следующие суммы:XI + х^; Х2 + Xj,.,; хз + Хп.2; ... х^ + х,.Указание, Используйте двусвязный список.Задание 3. Разработайте профамму, которая определяет «водящего» в детскойифе. Водящий определяется с помощью «считалки» следующим образом. Все ифающие встают в круг и начинают «считаться». Каждый раз тот, на ком закончиласьсчиталка, выбывает из круга.
Водит оставшийся. Исходное количество ифающих п.Количество слов считалки т .Указание, Используйте кольцевой список.237Часть L Основы алгоритмизации и процедурное программирование7.5. Бинарные деревьяВ математике бинарным (двоичным) деревом называют конечное множество вершин, которое либо пусто, либо состоит из корня и не более чем двухнепересекающихся бинарных деревьев, называемых левым и правым поддеревьями данного корня.Таким образом, каждая вершина бинарного дерева может включать одноили два поддерева или не включать поддеревьев вовсе.
Первое поддеревообычно называют левым, а второе - правым. Соответственно ветвь, исходящую из вершины и ведущую в корень левого поддерева, называют левой, аветвь, ведущую в корень правого поддерева - правой. Вершины, из которыхне выходит ни одной ветви, называют листьями (рис. 7.17).В программах для реализации бинарных деревьев используют п-связныесписки. С вершинами бинарного дерева обычно связывают записи, хранящиенекоторую информацию.Построение дерева выполняется следующим образом. Если дерево пусто, то первая же вершина становится корнем дерева.
Добавление остальныхвершин регламентируется в зависимости от условия задачи: в соответствии сзаданной дисциплиной построения дерева отыскивается подходящая вершина, к которой й подсоединяется новая вершина.Достаточно часто используют регулярные бинарные деревья с разнымизаконами построения.
Примером могут служить сортированные бинарныедеревья, построение которых осуществляется по правилу: ключевое поле левого поддерева всегда долэюно содерэюать значение меньше, чем в корне, аключевое поле правого поддерева - значение больше или равное значению вкорне.Рассмотрим основные операции с сортированными бинарными деревьями.Корень дереваЛевая ветвьКорень левогоподдереваПравая ветвьКорень правогоподдереваРис. 7.17.
Пример бинарного дерева2387. Программирование с использованием динамической памятиИсходные установки. В начале программы необходимо описать элемент и его тип:Туре topjptr-^top;{тип «указатель на вершину»}top=recorcivalue:integer; {число}left,{указатель на левое поддерево}right:top_ptr; {указатель на правое поддерево}end;В статической памяти описываем указатель корня дерева и несколькоуказателей, используемых при выполнении операций со списком:Var root,{указатель структуры - адрес корня дерева}pass, next, q:topjptr; {вспомогательные указатели}Исходное состояние - «пустое дерево»:root:=nil;Построение дерева.
Дерево строится в соответствии с главным правилом. Например, пусть дана последовательность целых чисел {5, 2, 8, 7, 2, 9,1, 5}. Первое число 5 будет записано в корень дерева (рис. 7.18, а). Второечисло 2 меньше значения в корне дерева, следовательно, оно будет записанов левое поддерево (рис. 7.18, б).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
