6.1. Переменные и структуры данных

Структура данных – одно из первичных понятий программирования, и как любое первичное понятие достаточно трудно определимое. Например, можно сказать так: «Структура данных – систематизированный способ организации данных и доступа к ним». Попробуем сделать это более конструктивно: через перечисление их свойств и взаимосвязи с другими понятиями программирования и языков:

• Структура данных и переменная. Переменная – элемент языка программирования, структура данных – внеязыковая единица, технологический элемент программирования. Структура данных – совокупность переменных, взаимосвязанных через свои значения в единое целое.

• Структура данных и внешняя реальность. Не все внешние объекты (сущности), отображаемые в программе, могут быть представлены переменными. Некоторым из них соответствуют структуры данных – множество взаимосвязанных переменных.

• Структура данных и алгоритм. Взаимосвязь значений переменных не может быть только статичной. Алгоритмы, работающие со структурой данных, связывают между собой значения переменных динамически, соблюдая установленные для них соглашения.

Структура данных – множество взаимосвязанных переменных. Программа заключает в себе единство алгоритма (процедур, функций) и обрабатываемых ими данных. Единицами описания данных и манипулирования ими в любом языке программирования являются переменные. Переменные – это «непосредственно представленные в языке» данные.

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

Структура данных - совокупность взаимосвязанных переменных и их значений

Любая структура данных имеет две стороны. Физическая структура данных – это ее представление в памяти в том виде, как она выглядит «на самом деле». Логическая структура данных – это созданная программными средствами образное, абстрактное ее представление. При этом оба представления могут сосуществовать при самых разных сочетаниях их свойств: одномерная – двумерная, линейная – нелинейная и т.п.. Характерные примеры:

• стек как логическая структура может быть реализован на основе массива с индексом – указателем стека и односвязного списка (физическое представление);

• пирамидальная сортировка использует массив на уровне физического представления для логической структуры – дерева с двумя потомками, упорядоченного по вертикали (8.4);

• наиболее близкое представление дерева на физическом уровне – вершина с массивом указателей на потомков может быть использована для представления линейной структуры данных – логической последовательности (8.3).

Последовательность как структура данных

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

Физическое представление последовательности может быть самым разным, например, список или дерево с заданной последовательностью обхода. Рассмотрим самый простой способ представления последовательности – ее элементы занимают первые n элементов массива (без «дырок»). Для того, чтобы определить текущее количество элементов последовательности, можно поступить двумя способами:

• использовать дополнительную переменную - счетчик числа элементов;

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

Массив, как переменная, является здесь необходимым, но не достаточным для отношения к нему как к структуре данных – последовательности. Для этого необходимы еще и правила хранения в нем значений: они могут определяться и начальным его наполнением, и функциями, которые работают с массивом именно как с последовательностью. У массива, таким образом, возникает дополнительный «смысл», который позволяет по-особому интерпретировать работающие с ним фрагменты.

//------------------------------------------------------61-01.cpp
// Последовательность со счетчиком
#define SZ 1000

int A[SZ];
int n = 0;

void add(int vv) {
  if (n != SZ - 1) A[n++] = vv;
}

int get(int k) {
  return k >= n ? 0 : A[k];
}

int remove(int k) {
  if (k >= n) return 0;

  int vv = A[k];

  for (int j = k; j < n - 1; j++) A[j] = A[j + 1];

  n--;
  return vv;
}

int insert(int vv, int k) {
  if (n == SZ - 1 || k >= n) return 0;

  for (int j = n - 1; j <= k; j--) A[j + 1] = A[j];

  A[k] = vv;

  n++;
}

Чтобы исключить ограничения по размерности массива, нужно воспользоваться динамическими массивами (см. 5.6) и технологическим приемами перераспределения памяти при их переполении.

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

Стек

«Хороший Сагиб у Сами и умный,
Только больно дерется стеком».

Н.С.Тихонов. Сами.

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

Стек - последовательность, включение и исключение элементов в которую производится только с одного конца

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

Представление стека в массиве. Стек обычно представляется массивом с дополнительной переменной, которая указывает на последний элемент последовательности в вершине стека - указатель стека – SP – stack pointer.

//------------------------------------------------------61-01.cpp
// Стек в массиве
int sp = -1;

void push(int vv) {
  if (sp != SZ - 1) A[++sp] = vv;
}

int pop() {
  return sp == -1 ? 0 : A[sp--];
}

int get(int k) {
  return sp - k < 0 ? 0 : A[sp - k];
}

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

Использование свойств стека в программировании. Исключительная популярность стека в программировании объясняется тем, что при заданной последовательности записи элементов в стек (например, A-B-C) извлечение их происходит в обратном порядке (C-B-A). А именно такая последовательность действий соответствует таким понятиям, как вложенность вызовов функций, вложенность определений конструкций языка, прерываний и т.п.. Следовательно, там, где речь идет о вложенности процессов, структур, определений, везде механизмом ее реализации является стек:

• при вызове функции адрес возврата (адрес следующей за вызовом команды) запоминается в стеке, таким образом, создается «история» вызовов функций, которая может быть восстановлена в обратном порядке;

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

Для способа хранения данных в стеке имеется общепринятый термин - LIFO (last in - first out - последний пришел, первый ушел).

В архитектуре практически всех компьютеров используется аппаратный стек. Он представляет из себя обычную область внутренней (оперативной) памяти компьютера, с которой работает специальный регистр - указатель стека. С его помощью процессор может выполнять операции Push и Pop по сохранению и восстановлению из стека байтов и машинных слов различной размерности.

Единственным отличием аппаратного стека от рассмотренной модели является его расположение буквально «вверх дном», то есть его заполнение от старших адресов к младшим, первоначально указатель стека ссылается на «верхнюю часть» выделенной области памяти. Исторические обстоятельства таковы: в простейших вариантах распределения памяти в программе сегменты команд, статических данных размещались, начиная «от начала» памяти, а над ними «рос вверх» сегмент динамической памяти, поэтому стек приходилось размещать, начиная с другого конца, т.е. «вверх дном».

Загадка для программистов: «Кто над нами вверх ногами».
Варианты отгадок: а). муха б). стек.

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

• программный код вызова записывает в стек значения фактических параметров;

• команда вызова функции записывает в стек адрес возврата (текушее значение указателя текущей команды в сегменте команд CS:IP) и выполняет переход к началу тела функции;

• программный код тела функции резервирует в стеке место для локальных переменных;

• во время исполнения тела функции ей доступна текущая область стека (фрейм стека), содержащая формальные (фактические) параметры и локальные переменные. Формальные параметры представляют собой «ожидаемое состояние стека», т.е. области, заданные смещениями относительно текущего положения указателя стека, где «ожидаются» фактические параметры;

• перед возвратом из функции из стека удаляются локальные переменные, затем из него же извлекается адрес возврата и по нему производится переход;

• после возврата программным кодом вызова из стека удаляются фактические параметры.

Очередь

Объяснять, что такое очередь как способ организации данных, излишне, потому что здесь полностью применим житейский смысл этого понятия.

Очередь - последовательность элементов, включение в которую производится с одного, а исключение - с другого конца

Для способа хранения данных в очереди имеется общепринятый термин - FIFO (first in - first out - первый пришел, первый ушел).

Простейший способ представление очереди последовательностью, размещенной от начала массива, не совсем удобен, поскольку при извлечении из очереди первого элемента все последующие придется постоянно передвигать к началу.

//------------------------------------------------------61-01.cpp
// Очередь в массиве (от начала, со сдвигом)
void in (int vv) {
  if (n != SZ - 1) A[n++] = vv;
}

int out() {
  if (n == 0) return 0;

  int vv = A[0];

  for (int i = 0; i < n - 1; i++) A[i] = A[i + 1];

  n--;
  return vv;
}

int get(int k) {
  return k >= n ? 0 : A[k];
}

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

//------------------------------------------------------61-01.cpp
// Циклическая очередь в массиве
int fst = 0, lst = 0;

void in(int vv) {
  if ((lst + 1) % SZ == fst) return;

  A[lst++] = vv;

  if (lst == SZ) lst = 0;
}

int out() {
  if (fst == lst) return 0;

  int vv = A[fst++];

  if (fst == SZ) fst = 0;

  return vv;
}

int get(int m) {
  return A[(fst + m) % SZ];
}

В отличие от стека указатель на конец очереди (lst) ссылается не на последний занятый, а на первый свободный элемент массива. Условие fst == lst означает, что очередь пуста, а выражение (lst+1)%SZ == fst – что очередь заполнена (при перемещений индекс конца очереди попадает на начало).

Вопросы без ответов

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

//------------------------------------------------------61-02.cpp
//---------------------------------------------------
#define SZ 1000

int A[SZ], sp = -1, lst = 0, fst = 0;

//------------------------------------------------- 1
void F1() {
  int c;
  if (sp < 1) return;

  c = A[sp];
  A[sp] = A[sp - 1];
  A[sp - 1] = c;
}

//------------------------------------------------- 2
void F2() {
  int c;
  if (sp < 1) return;

  A[sp - 1] += A[sp];
  sp--;
}

//------------------------------------------------- 3
int F3(int n) {
  int v, i;

  if (sp < n) return 0;

  v = A[sp - n];

  for (i = sp - n; i < sp; i++) A[i] = A[i + 1];

  sp--;
  return v;
}

//------------------------------------------------- 4
void F4() {
  A[sp + 1] = A[sp];
  sp++;
}

//------------------------------------------------- 5
int F5(int n) {
  int v, i1, i2;

  i1 = (fst + n) % SZ;

  v = A[i1];

  for (; i1 != lst; i1 = i2) {

    i2 = (i1 + 1) % SZ;

    A[i1] = A[i2];
  }

  lst = (lst == 0 ? SZ - 1 : lst - 1);

  return v;
}

//------------------------------------------------- 6
void F6() {
  int n;

  if (fst == lst) return;

  n = (lst == 0 ? SZ - 1 : lst - 1);

  A[lst++] = A[n];

  if (lst == SZ) lst = 0;
}