Задачи, решаемые на ЭВМ, являются математическими моделями процессов или явлений реальной жизни. В математической модели находят отражение наиболее существенные связи между реальными объектами. Модели реальных объектов вместе с присущими им связями образуют структуры данных, процесс обработки которых и описывается с помощью алгоритмов.
Разные классы решаемых на ЭВМ задач характеризуются и разными структурами данных, что находит отражение и в соответствующих языках программирования. Языки, ориентированные на решение различных классов задач, используют и различные способы представления и обработки структур данных. Однако при решении задачи на ЭВМ подобно тому, как структуры разнообразных алгоритмов отображаются на структуру машинного языка, так и разнообразные структуры данных отображаются на структуру машинной памяти.
Память ЭВМ имеет дискретную структуру и состоит из элементов, называемых ячейками. Каждая ячейка может содержать одно значение, называемое машинным словом. Ячейки нумеруются следующими подряд натуральными числами. Таким образом, память ЭВМ представляет собой линейную последовательность ячеек.
1. Простые переменные.Простые переменные описывают структуры, состоящие из одного элемента, поэтому простая переменная характеризуется одним значением. При отображении на память ЭВМ имени простой переменной ставится в соответствие номер ячейки памяти, в которой хранится значение этой переменной (часто значение простой переменной занимает более одной ячейки).
2. Массивы.Переменные с индексами служат для описания структур, состоящих из множества элементов одного типа, упорядоченных в соответствии со значениями индексов. Такие структуры в языках программирования называют массивами, причем в зависимости от числа индексов различают массивы одномерные (один индекс), двумерные (два индекса) и т.д.
В языках программирования индексы принято записывать в скобках после имени переменной, а не в качестве подстрочных индексов, как это принято в математической записи.
Переменная с одним индексом описывает одномерный массив. Элементы одномерного массива образуют последовательность, причем номер элемента последовательности определяется индексом.
Значения элементов одномерного массива хранят в памяти также в виде последовательности, т.е. структура одномерного массива однозначно отображается на структуру памяти ЭВМ, при этом индекс элемента означает номер ячейки памяти, в которой хранится значение этого элемента относительно номера той ячейки памяти, в которой хранится значение первого элемента этого массива. Например, если значение первого элемента массива хранится в ячейке с номером 101, то значение пятого элемента хранится в ячейке с номером 105, а значение двадцатого элемента – в ячейке с номером 120.
Так как структура одномерного массива однозначно соответствует структуре памяти ЭВМ, то отображение других структур данных на память ЭВМ соответствует отображению этих структур на одномерный массив.
Переменные с двумя и более индексами служат для описания многомерных массивов. Двумерный массив состоит из элементов, образующих прямоугольную таблицу. В этом случае первый индекс обозначает номер строки, а второй – номер столбца таблицы, на пересечении которых и расположен данный элемент.
При отображении двумерного массива на одномерный элементы двумерного массива располагаются в виде последовательности (строка за строкой или столбец за столбцом). Предположим, что принят первый способ (отображение по строкам), тогда номер k элемента двумерного массива x[i, j] в последовательности может быть вычислен по формуле k=(i-1)n + j, где n – число элементов в строке двумерного массива.
По аналогичному принципу отображаются на одномерный массив и массивы большей размерности.
Массив как структура данных характерен тем, что с помощью индексов обеспечивается прямой доступ к любому элементу массива или записи в массив сводятся к вычислению значений индексов.
3. Стеки.Стек – тип структуры данных, организованной по принципу "последним пришел – первым ушел" (LIFO – Last In First Out). В стеке в отличие от очереди доступен только один элемент, называемый вершиной стека. При записи в стек очередной элемент заносится в его вершину, а остальные элементы продвигаются вниз без изменения порядка. При выборке из стека выбирается элемент из его вершины, а все остальные элементы без изменения порядка сдвигаются вверх, так что в вершину попадает элемент, поступивший в стек последним.
По принципу стека организована, например, стопка книг на столе. Новую книгу кладем поверх стопки. Эту же книгу мы возьмем из стопки первой, после этого на верху окажется книга, положенная туда последней. По такому же принципу организована пистолетная или автоматная обойма (магазин) – патрон, заправленный в обойму последним, попадет из обоймы в ствол первым. По этой причине стек называют также магазинной памятью.
Для отображения стека используется одномерный массив a[1], a[2], ... a[n], причем длина n этого массива выбирается с таким запасом, чтобы длина стека (число ее элементов) не превышала n.
При отображении стека на одномерный массив первый элемент очереди записывают в первый элемент массива, вновь поступающие элементы записывают в следующие свободные элементы массива.
Для указания вершины стека можно использовать индекс i. При записи в стек указатель вершины будет сдвигаться в сторону конца массива, при чтении из стека указатель вершины будет перемещаться в сторону начала массива. Значение i = 0 перед чтением из стека служит признаком того, что стек пуст, а значение i = n перед записью в стек – признаком того, что переполнен.
Отображение стека на массив из пяти элементов можно представить так:
Вершина
Алгоритм записи в стек и чтения из стека могут быть представлены в таком виде:
