Глава 3. Технология создания программ

127

Для реализации линейного списка требуется вспомогательный массив целых чисел и еще одна переменная, например:

10 25 20 6 21 8 1 30 - массив данных 1234567-1- вспомогательный массив

0 - индекс первого элемента в списке

1-й элемент вспомогательного массива содержит для каждого i-ro элемента массива данных индекс следующего за ним элемента. Отрицательное число используется как признак конца списка. Тот же массив после сортировки:

10 25 20 6 21 8 1 30 - массив данных 2745103-1- вспомогательный массив 6 - индекс первого элемента в списке

Для создания бинарного дерева можно использовать два вспомогательных массива (индексы вершин его правого и левого поддерева). Отрицательное число используется как признак пустой ссылки. Например, дерево, приведенное на рис. 3.3, можно представить следующим образом:

10 25 20 6 21 8 1 30 - массив данных 3 2-16-1-1 -1 -1 - левая ссылка

1 7 4 5 -1 -1 -1 -1 - правая ссылка

Память под такие структуры можно выделить либо на этапе компиляции, если размер можно задать константой, либо во время выполнения программы, например:

struct Node{

Data d; // тип данных Data должен быть определен ранее i nt i;

}:

Node spisokl[1000]; // на этапе компиляции

Node *pspisok2 = new Node[m]; // на этапе выполнения

ВНИМАНИЕ

При работе с подобными структурами необходимо контролировать возможный выход индексов за границу массива.

Приведенный выше способ реализации позволяет использовать преимущества динамических структур (например, сортировать структуры из громоздких элементов данных без их физического перемещения в памяти), и при этом не расходовать время на выделение и освобождение памяти для каждого элемента данных.

Упражнения к части I

Циклические вычислительные процессы Вариант 1

Вычислить и вывести на экран в виде таблицы значения функции F на интервале от Хнач. до Хкон. с шагом dX.

ах² + Ъ при х < О и Ъ ф О х -а

х -с х

I с

при х > О и b = О

в остальных случаях

где а, Ь, с — действительные числа.

Функция F должна принимать действительное значение, если выражение

(Ац ИЛИ Вц) И (Ац ИЛИ Сц)

не равно нулю, и целое значение в противном случае. Через Ац, Вц и Сц обозначены целые части значений а, Ь, с, операции И и ИЛИ — поразрядные. Значения а, Ь, с, Хнач., Хкон., dX ввести с клавиатуры.

Вариант 2

J-- b ах

х -а

Вычислить и вывести на экран в виде таблицы значения функции F на интервале от Хнач. до Хкон. с шагом dX.

F =

х 10*

с-

при х + 5 <0и с=0 при х + 5 >0и с * 0 в остальных случаях

где а, Ь, с — действительные числа.

Функция F должна принимать действительное значение, если выражение

(Ац И Вц) ИЛИ (Вц И Сц)

не равно нулю, и целое значение в противном случае. Через Ац, Вц и Сц обозначены целые части значений а, Ь, с, операции И и ИЛИ — поразрядные. Значения а, Ь_у с, Хнач., Хкон., dX ввести с клавиатуры.

Упражнения к части I

129

Вариант 3

Вычислить и вывести на экран в виде таблицы значения функции F на интервале от Хнач. до Хкон. с шагом dX.

ах² +Ьх + с при а <0и с * О F =

и,	при а > 0 и с - 0
X -С
а(х + с)	в остальных случаях

где а, Ь, с — действительные числа.

Функция F должна принимать действительное значение, если выражение

Ац И (Вц ИЛИ Сц)

не равно нулю, и целое значение в противном случае. Через Ац, Вц и Сц обозначены целые части значений а, Ь, с, операции И и ИЛИ — поразрядные. Значения а, Ь, с, Хнач., Хкон., dX ввести с клавиатуры.

Вариант 4

Вычислить и вывести на экран в виде таблицы значения функции F на интервале от Хнач. до Хкон. с шагом dX.

- ах-х -а

F =

-с Ъх

с при с <0и х * О при с > О и х = О

в остальных случаях

1С- а

где а, Ь_у с — действительные числа.

Функция F должна принимать действительное значение, если выражение Ац ИЛИ Вц ИЛИ Сц

не равно нулю, и целое значение в противном случае. Через Ац, Вц и Сц обозначены целые части значений а, Ь, с, операция ИЛИ — поразрядная. Значения а, Ъ, с, Хнач., Хкон., dX ввести с клавиатуры.

Вариант 5

Вычислить и вывести на экран в виде таблицы значения функции F на интервале от Хнач. до Хкон. с шагом dX.

а-

10 + 6

х -а

F =

х -с Зх + -

при х < 0 и Ъ * 0 при х > 0 и Ъ = 0 в остальных случаях

где а, Ь, с — действительные числа.

130