Простейшие структуры данных

Для того чтобы ясно представить как "работает" алгоритм, опишем простейший автомат, который предназначен для выполнения операций, предписанных этим алгоритмом.

В состав такого автомата входят:

· память, состоящая из отдельных ячеек;

· считывающая/записывающая головка;

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

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

В простейшем случае константой является любое арифметическое число. Например, 12, 0.78, 0, –45.33 и т. д. Константами могут быть такие строки символов, структуры данных и др.

Под простой переменной, или просто переменной будем понимать некоторую ячейку памяти, т.е. отдельное место для хранения одной константы. В отдельной ячейке за время работы алгоритма может побывать множество различных констант (отсюда название – переменная). Такими ячейками (электронными, магнитными, оптическими) снабжен реальный компьютер.

Переменные имеют буквенно-символьное обозначение. Например, 1, n, a, a1, b, H2 – переменные. Одновременно обозначение переменной является индексом ячейки, в которую будут записываться константы. Любая из таких констант называется значением переменной. Например, Z является переменной и адресом ячейки Z одновременно. С алгоритмической точки зрения понятия “переменная” и “адрес ячейки” памяти являются идентичными.

Запись вида Y: = 5.5 следует понимать так: записать константу 5.5 в ячейку с адресом Y (если до этой операции в ячейку была записана константа, то она будет затерта, а на ее место будет помещена константа 5.5). Произносить эту запись следует так: “переменной Y присвоить значение 5.5”.

Запись вида L: = M следует понимать так: прочитать константу, расположенную по адресу M и скопировать эту константу в ячейку с адресом L (при этом константа из ячейки M не удаляется, а остается такой, какой она была до чтения). Произносить эту запись нужно так: "переменной L присвоить значение переменной M (или просто: L присвоить M)".

Другой разновидностью переменных являются так называемые индексированные переменные или массивы. Массив – это некоторая совокупность ячеек, объединенная одним обозначением (массивом может быть одна ячейка). Всякий массив обязательно имеет размерность. Массивы бывают одномерными, двумерными, трехмерными и т.д.

Одномерный массив – это последовательность ячеек, расположенных в одну линию. Ниже приведен пример такого массива.

Массив имеет имя q. Для того чтобы можно было отличить одну ячейку массива от другой ячейки этого же массива, их нумеруют. Нумерация ячеек обычно начинается с 1. Номер ячейки массива называется его индексом, а константа в ячейке – элементом массива. Теперь становится возможной работа с отдельной ячейкой такого массива. Например, команда q₇: = 8.2 означает, что в 7-ю ячейку массива q надлежит записать константу 8.2. Команда r₄₁:= q₂ + q₅ означает, что нужно сложить константы, записанные во 2-ю и 5-ю ячейки массива q, и результат записать в 41-ю ячейку одномерного массива r. Эту же операцию можно описать другими словами: 41-му элементу массива r присвоить значение суммы 2-го и 5-го элементов массива q.

Двумерный массив по расположению ячеек напоминает математическую матрицу:

Элемент такого массива характеризуется двумя индексами: первый показывает строку, в которой расположена ячейка, второй – ее столбец. Например, команда d_{2, 5} = 43 означает, что в ячейку, размещенную на пересечении 2-й строки и 5-го столбца двумерного массива d, нужно записать константу 43.

Аналогично устроена структура массивов трех- и большей размерности.