Методы программирования. Громов Ю.Ю - 6 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

6
А1. Установить NEXT (NEWCARD) ← TOP. (Устанавливается соответст-
вующая связь в узле новой карты.)
А2. Установить TOP ← NEWCARD. (Тем самым обеспечивается, что
TOP по-прежнему указывает на верхнюю карту в колоде.)
А3. Установить TAG (TOP) ← 0. (Отмечается, что карта повёрнута лице-
вой стороной вверх.) ■
Другим примером является алгоритм, подсчитывающий количество
карт в колоде в данный момент:
В1. Установить N ← 0, X ← TOP. (N – целая переменная, X – переменная
связи.)
В2. Если X = Λ, то остановиться. (N равно числу карт в колоде.)
В3. Установить N ← N + 1, X ← NEXT (X) и вернуться к шагу В2. ■
Линейный список – это множество, состоящее из n ≥ 0 узлов
x [1], x [2], …, x [n], структурные свойства которого ограничиваются
только линейным относительным положением узлов: x [1] – первый узел;
при 1 < k < n узлу x [k] предшествует узел x [k – 1], а следует за ним узел
x [k + 1]; x [n] – последний узел.
Возможные операции с линейными списками:
1) получение доступа к k-му узлу списка, чтобы проанализировать
и/или изменить содержимое его полей;
2) включение нового узла в список непосредственно перед k-м узлом;
3) исключение k-го узла списка;
4) объединение двух (или более) списков в один;
5) разбиение списка на два (или более) списков;
6) копирование списка;
7) определение количества узлов в списке;
8) сортировка узлов списка по некоторым полям;
9) поиск в списке узла с заданным значением в некотором поле.
Случаи при k = 1 и k = n в операциях 1), 2), 3) особые, поскольку в
линейном списке доступ к первому и последнему узлу получить проще.
Очень часто на практике встречаются линейные списки, в которых
включение, исключение и доступ к значениям производятся в первом или
последнем узлах. Среди таких списков различают:
• стек – список, в котором все включения, все исключения и вся-
кий доступ выполняются в одном конце этого списка;
• очередь – список, в котором все включения производятся на од-
ном конце этого списка, а все исключения и всякий доступ – на другом
его конце;
• дек – список, в котором включения, исключения и всякий доступ
делаются на обоих концах этого списка.

Страницы