ээээээ ээээээээээээээээ
.pdfВ результате выполнения этой операции некоторой переменной i должно быть присвоено значение первого элемента стека и изменено значение указателя на начало списка.
Procedure ReadStack(Var u-.EXST; Var i-.Integer); Var x: EXST;
Begin
i:u^.Data; x:=u; u:=u^.Next; Dlspose(x);
End;
Недостатком описанной процедуры является предположение о том, что стек не пуст. Для его исправления следует разработать логическую функцию проверки пустоты обрабатываемого стека. function Free(u:EXST):Boolean;
Очереди
Очередь — это упорядоченный набор элементов, в котором извлечение элементов происходит с одного его конца, а добавление новых элементов — с другого.
Очередь является динамической структурой — с течением времени изменяется и ее длина, и набор составляющих ее элементов. Поэтому удобно представить ее в виде списка.
Описание очереди на языке программирования:
Type ЕХО=^О; O=Record Data: Integer; Next: EXO; End;
Над очередью определены две операции: занесение элемента в очередь и извлечение элемента из очереди.
В очереди, в силу ее определения, доступны две позиции: ее конец, куда заносятся новые элементы, и ее начало, откуда извлекаются элементы. Поэтому для работы с очередью необходимо описать две переменные:
Var xl, х2: EXO;
где xl — соответствует началу очереди и будет использоваться для вывода элемента из очереди, х2 — соответствует концу очереди и будет использоваться для добавления новых элементов в очередь.
Поскольку очередь представлена списком, занесение элемента в очередь соответствует занесению элемента в конец списка.
Procedure WriteO (Var xl,x2: EXO; с: Integer); Varи: EXO;
Begin
New(u); u^.data:=c; u^.nexf:=^NIL;
If xl=NIL Then xl:=u {если очередь пуста}
Else x2^.next:=u; {заносим элемент в конец списка} х2:=u;
End;
Основная программа, создающая очередь, может быть такой:
Begin
xl:=NIL; x2:=NIL;
Write Ln('Введите элементы очереди. Конец ввода — О');
Read(Digit);
While Digit<>O Do Begin WriteO(xl,x2,Digit); Read(Digit); End
End.
Процедура извлечения элемента из очереди аналогична удалению элемента из начала списка.
Поскольку извлечение элемента из пустой очереди осуществить нельзя, опишем логическую функцию, проверяющую, есть ли элементы в очереди.
Procedure Reado(Var xl,x2:EXO; Var c:Integer); Var u:ЕХО; Function Nul (xl: ЕХО): Boolean; Begin Nul:=(xl=Nil); End;
Begin
If Nul(xl) Then Writeln(‘0чepeдь пуста') Else
Begin c:=xl^.Data; u:=xl; xl:=xl^.Next; Dispose(u); End;
End;
Деревья
Введение основных понятий
Граф — это непустое множество точек (вершин) и множество отрезков (ребер), концы которых принадлежат заданному множеству точек.
Если на каждом ребре задать направление, то граф будет ориентированный.
Если, двигаясь по ребрам графа в заданном направлении, можно попасть из заданной вершины 1 в заданную вершину 2, то говорят, что эти вершины соединены путем. Замкнутый путь, состоящий из различных ребер, называется циклом.Граф называется связным, если любые две его вершины соединены путём. Связный граф без циклов называется деревом. На рис. 54 изображено дерево, в узлах которого располагаются символы.
Примечание. С каждой вершиной дерева связывается конечное число отдельных деревьев, называемых поддеревьями.
Для дальнейшей работы с деревьями необходимо определить ряд понятий.
•Вершина у, находящаяся непосредственно ниже вершины х, называется непосредственным потомком х, а вершина х называется предком у.
•Если вершина не имеет потомков, то она называется терминальной вершиной или листом, если имеет, то называется внутренней вершиной.
•Количество непосредственных потомков внутренней вершины называется ее степенью.
•Степенью дерева называется максимальная степень всех вершин. Например:
•вершины F, D, Е являются непосредственными потомками вершины В;
•вершины F, D, Е являются листьями;
•вершины С, G, Н — внутренние;
•степень вершины В — 3, а вершины Н — 1;
•степень дерева равна 3.
Двоичное дерево — это дерево, в котором из каждой вершины исходит не более двух ребер.
6.2. Представление деревьев
Дерево — это сложная динамическая структура данных, применяющаяся для эффективного хранения информации.
Очевидно, что для описания требуются ссылки. Опишем, как переменные с фиксированной структурой — сами вершины, тогда степень дерева будет определять число ссылочных компонент, указывающих на вершины поддеревьев. В бинарном дереве их два - левое и правое.
Type TreeLink =^Tree;
Tree=Record
Data: <mun данных>;
Left, Right: TreeLink;
End;
Корень дерева опишем в разделе описания переменных:
Var kd: TreeLink;
6.3. Основные операции над деревом
К основным операциям над деревьями относятся:
•занесение элемента в дерево;
•обход дерева;
•удаление элемента из дерева. Рассмотрим вставку и обход дерева на примере следующей задачи.
6.5. Удаление из дерева
Непосредственное удаление элемента из упорядоченного дерева реализуется достаточно просто, если эта вершина является конечной (рис. 55) или из нее выходит только одно ребро (рис. 56). Для этого нужно изменить соответствующую ссылку у предшествующей вершины.
Если же из удаляемой вершины выходит две ветви, то нужно найти подходящую вершину дерева, которую можно было бы вставить на место удаляемой вершины (рис. 57).Из вышесказанного следует, что процедура удаления элемента из дерева должна различать три случая:
•удаляемая вершина имеет два поддерева (В этом случае удаляемый элемент нужно заменить либо на самый правый элемент его левого поддерева, либо на самый левый элемент его правого поддерева. При этом они должны иметь не больше одного потомка);
•удаляемая вершина имеет не более одного поддерева (0 или 1);
•удаляемой вершины в дереве нет. Ниже приведена рекурсивная процедура deltree, решающая поставленную задачу. Она отыскивает элемент с заданным ключом и удаляет его.
В процедуре deltree описана вспомогательная процедура dl, которая работает только в первом из трех перечисленных случаев.Вспомогательная процедура dl "движется" по правой ветви левого поддерева исключаемого элемента q^ и заменяет значение
ключа в q^ на соответствующее значение из самого правого элемента r^ левого поддерева.
1. Базис, алфавит, основание.
Система счисления - способ записи (изображения) чисел.
Символы, при помощи которых записывается число, называются цифрами.
Системы счисления, в которых количественный эквивалент каждой цифры зависит от ее положения (позиции) в коде(записи) числа, называются позиционными.
Основанием позиционной системы счисления называется количество знаков или символов, используемых для изображения числа в данной системе счисления.
Базисом позиционной системы счисления называется последовательность чисел, каждое из которых задает количественное значение или "вес" каждого разряда.
Например: Базисы некоторых позиционных систем счисления.
Десятичная система: 100, 101, 102, 103, 104, ..., 10n, ...
Двоичная система: 20, 21, 22, 23, 24, ..., 2n, ...
Восьмеричная система: 80, 81, 82, 83, 84, ..., 8n, ...
Совокупность различных цифр, используемых в позиционной системе счисления для записи чисел, называется алфавитом системы счисления. Количество цифр в алфавите равно основанию системы счисления.
Уравновешенные системы счисления
---===---
Двоичная СС с большим успехом используется в компьютерной технике
до сих пор. Однако выявились и существенные недостатки использования
двоичной СС, влияющие на скорость работы процессора и надежность передачи
информации.
Одним из этих недостатков является так называемая проблема представления
отрицательных чисел. Попытка преодолеть этот и другие недостатки двоичной
системы счисления стимулировала использование в компьютерах других систем
счисления и развитие собственно теории систем счисления.
Выбирая систему кодирования информации в компьютере, разработчики в
первую очередь думают о быстродействии процессора, т.е. о скорости обработки
закодированной информации.
///
Что привычно и хорошо для человека, выполняющего вычисления на бумаге,
не всегда хорошо для компьютера. Для того чтобы сложить два целых числа
с разными знаками, и человек, и компьютер, вообще говоря, должны выполнить
следующие действия:
1)взять модули слагаемых;
2)сравнить эти модули;
3)запомнить знак большего по модулю слагаемого;
4)получившийся результат з
5)из большего модуля вычесть меньший модуль;
6)записать со знаком из п. 3.
Многовато будет для простой и часто используемой операции!
\\\
В десятичной системе счисления для представления отрицательных чисел
человек использует знак числа. То, есть для записи отрицательных чисел
имеющихся 10 знаков недостаточно. Используется еще один знак - '-'.
То есть для записи отрицательных десятичных чисел потребоваломь 11 знаков!
Аналогично, для записи отрицательных двоичных чисел требуется 3 знака,
но в нашем распоряжении их два - 0 и 1. Для решения проблемы вначале века
использовалось прямое кодирование: в старший бит регистра числа явно
вписывался знак '0' для положительных и знак '1' для отрицательных чисел.
При определении значения числа этот бит игнорировался. Вроде бы все
нормально, но процессор не может работать с отдельными битами регистра.
Для определения знака числа, число загружалось в процессор, применение
маски (числа 10 или 1000) оставляло в регистре только бит знака, весь
регистр проверялся (ноль или нет). Для выделения значения числа снова
использовалась маска (7F или 7FFF), после чего определялось число -
не слишком ли много действий процессора для выполнения простых операций?
///
для 1 байта 5 = 00000101 -5 = 10000101
\\\
Чтобы сократить число действий процессора, придумали обратный код:
для чисел договорились старший бит не использовать, а для получения
отрицательного числа выполнять команду инвертирования - менять в записи
0 на 1, а 1 на 0. Это одна команда для процессора. Но проверка бита
знака все равно остется.
///
для 1 байта 5 = 00000101 -5 = 11111010
\\\
Кроме всего прочего применение прямого или обратного кодирования
добавляет новую проблему: число 0 оказываеися можно хранить двумя
разными способами (как?). Появились значения +0 и -0.
Представьте, решаем квадратное уравнение, и начинаем проверять,
равен ли он 0. Поребуется сравнивать как с число 0, так и с числом -0,
- двойная работа!
Использующийся в настоящее время во всех компьютерах способ хранения