Элементарные структуры данных

#include <iostream.h>
int lg(int);
int main() {
  for (int N = 1000; N <= 1000000000; N *= 10)
    cout << lg(N) << " " << N << endl;
}
int lg(int N) {
  for (int i = 0; N > 0; i++, N /= 2) ;
  return i;
}
        

#include <iostream.h>
#include <stdlib.h>
#include <math.h>
typedef int Number;
Number randNum() {
  return rand();
}
int main(int argc, char *argv[]) {
  int N = atoi(argv[1]);
  float ml = 0.0, m2 = 0.0;
  for (int i = 0; i < N; i++) {
    Number x = randNum();
    ml += ((float) x)/N;
    m2 += ((float) x*x)/N;
  }
  cout << "    Среднее: " << ml << endl;
  cout << "Ср.-кв.откл.: " << sqrt(m2-m1*m1) << endl;
}
        

#include "Number.h"
        

Третий вариант рекомендован и широко распространен в программировании на C, C++ и других языках. Он предусматривает разбиение программы на три файла:

Интерфейс, где определяется структура данных и объявляются функции, используемые для управления этой структурой

Реализация функций, объявленных в интерфейсе

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

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

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

Для программы 3.2 интерфейс должен включать следующие объявления:

typedef int Number;
Number randNum();
        

Первая строка указывает тип обрабатываемых данных, а вторая - операции, связанные с этим типом. Этот код можно поместить в файл с именем, например, Number.h, где на него будут независимо ссылаться и клиенты, и реализации.

Реализация интерфейса Number.h представляет собой функцию randNum, которая может содержать следующий код:

#include <stdlib.h>
#include "Number.h"
Number randNum()
  { return rand(); }
        

Первая строка содержит ссылку на предоставленный системой интерфейс, в котором описана функция rand(). Вторая строка - ссылка на реализуемый нами интерфейс (она включена для проверки того, что реализуемая и объявленная функции имеют одинаковый тип). Две последних строки содержат код функции. Этот код можно хранить, например, в файле int.c. Реальный код функции rand содержится в стандартной библиотеке времени выполнения C++.

Клиентская программа, соответствующая примеру 3.2, будет начинаться с директив include для интерфейсов, где объявлены используемые функции:

#include <iostream.h>
#include <math.h>
#include "Number.h"
        

После этих трех строк может следовать описание функции main из программы 3.2. Этот код может храниться, например, в файле с именем avg.c.

Результатом совместной компиляции программ avg.c и int.c будут те же функциональные возможности, что и реализуемые программой 3.2. Но рассматриваемая реализация более гибкая, поскольку связанный с типом данных код инкапсулирован и может использоваться другими клиентскими программами, а также потому, что программа avg.c без изменений может использоваться с другими типами данных. По-прежнему предполагается, что любой тип, используемый под именем Number, преобразуется в тип float. C++ позволяет описывать это преобразование, а также описывать желаемые встроенные операторы (наподобие += и <<) как часть нового типа данных. Использование одних и тех же имен функций или операторов для различных типах данных называется перегрузкой (overloading).

Помимо рассмотренного варианта "клиент-интерфейс-реализация" существует много других способов поддержки различных типов данных. Эта концепция не зависит от определенного языка программирования, либо метода реализации. Однако имена файлов не являются частью языка, и, возможно, придется изменить рекомендованный выше простой метод для функционирования в конкретной среде C++ (в системах существуют различные соглашения или правила, относящиеся к содержимому файлов заголовков, а некоторые системы требуют определенных расширений, таких как .C или .cxx для файлов программ). Одна из наиболее важных особенностей C++ - понятие классов, которые предоставляют удобный метод описания и реализации типов данных. В этой главе за основу взято простое решение, но впоследствии практически повсеместно будут использоваться классы. посвящена применению классов для создания базовых типов данных, важных для разработки алгоритмов. Кроме того, там будет подробно рассмотрено взаимоотношение между классами C++ и парадигмой "клиент-интерфейс-реализация".

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

Часто приходится создавать структуры данных, которые позволяют обрабатывать наборы данных. Структуры данных могут быть большими, либо интенсивно используемыми. Поэтому необходимо выделить наиболее важные операции, которые будут выполняться над данными, и иметь методы эффективной реализации этих операций. Выполнение этих задач - первые шаги в процессе последовательного создания абстракций более высокого уровня из абстракций низших уровней. Этот процесс представляет собой удобный способ разработки все более мощных программ. Простейшим механизмом группировки данных в C++ являются массивы (array), которые рассматриваются в разделе 3.2, и структуры (structure), о которых пойдет речь ниже.

Структуры представляют собой сгруппированные типы, используемые для описания наборов данных. Этот подход позволяет управлять всем набором как единым целым, сохраняя при этом возможность ссылаться на отдельные компоненты по их именам. Структуры в языке C++ можно использовать для описания нового типа данных, а также для определения операций с этими данными. Другими словами, со сгруппированными данными можно обращаться примерно так же, как со встроенными типами вроде int и float. Как будет показано ниже, можно присваивать имена переменным и передавать эти переменные в качестве аргументов функций, а также выполнять множество других операций.

Например, при обработке геометрических данных используется абстрактное понятие точки на плоскости. Следовательно, можно написать

struct point { float x; float y; } ;
        

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

Выражение

struct point a, b;

объявляет две переменные этого типа. Можно ссылаться по имени на отдельные члены структуры. Например, операторы

a.x = 1.0; a.y = 1.0; b.x = 4.0; b.y = 5.0;
        

устанавливают значения переменных таким образом, что a представляет точку (1,1), а b - точку (4,5). Кроме того, структуры можно передавать функциям в качестве аргументов. Например, код

float distance(point a, point b)
  { float dx = a.x - b.x, dy = a.y - b.y;
    return sqrt(dx*dx + dy*dy);
  }
        

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

Программа 3.3 представляет собой интерфейс, который содержит описание типа данных для точек на плоскости: в нем используется структура для представления точек и содержится операция вычисления расстояния между двумя точками. Функция, реализующая данную операцию, приведена в программе 3.4. Подобная схема "интерфейс-реализация" используется для описания типов данных при любой возможности, поскольку в ней описание инкапсулировано в интерфейсе, а реализация выражена в прямой и понятной форме. Тип данных используется в клиентской программе за счет включения интерфейса и компиляции реализации совместно с клиентом (либо с помощью средств раздельной компиляции). Программа реализации 3.4 включает интерфейс (программу 3.3), чтобы обеспечить соответствие описания функции потребностям клиента. Смысл в том, чтобы клиентские программы могли работать с точками без необходимости принимать какие-либо допущения об их представлении. В будет показано, как осуществить следующий этап разделения клиента и реализации.

Программа 3.3. Интерфейс типа данных point

Этот интерфейс описывает тип данных, состоящий из набора значений "пары чисел с плавающей точкой" и операции "вычисление расстояния между двумя точками".

struct point { float x; float y; };
float distance(point, point);
        

Программа 3.4. Реализация структуры данных point

Здесь содержится определение функции distance, объявленной в программе 3.3. Используется библиотечная функция вычисления квадратного корня.

#include <math.h>
#include "Point.h"
float distance(point a, point b)
  { float dx = a.x - b.x, dy = a.y - b.y;
    return sqrt(dx*dx + dy*dy);
  }
        

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

Структуры позволяют группировать данные. Кроме того, в языке C++ можно связывать данные с операциями, которые должны с ними выполняться, с помощью механизма классов (class). Подробности определения классов с множеством примеров приводятся в . Классы позволяют даже использовать программу, такую как 3.2, для обработки элементов типа point после описания соответствующих арифметических операций и преобразований типов для точек. Эта возможность использования ранее определенных операций высокого уровня абстракции даже для вновь созданных типов данных является одной из важных и выдающихся особенностей программирования на C++. Она основана на способности непосредственного определения собственных типов данных средствами языка. При этом классы позволяют не только описывать компоновку данных в структуре, но и точно задавать операции над данными (а также структуры данных и алгоритмы, которые их поддерживают). Классы формируют основу рассматриваемых в книге реализаций. Однако прежде чем приступить к детальному изучению описания и использования классов (), необходимо рассмотреть ряд низкоуровневых механизмов для управления данными и их объединения.

Помимо предоставления основных типов int, float и char, а также возможности встраивать их в составные типы с помощью описателя struct, C++ допускает косвенные манипуляции с данными. Указатель (pointer) - это ссылка на объект в памяти (обычно реализуемая в виде машинного адреса). Чтобы объявить переменную a как указатель на целое значение, используется выражение int *a. На само целое можно ссылаться значение с помощью записи *a. Возможно объявление указателей на любой тип данных. Унарная операция предоставляет машинный адрес объекта и удобна для инициализации указателей. Например, выражение *a означает то же, что и a.

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

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

polar(float x, float y, float *r, float *theta)
  { *r = sqrt(x*x + y*y); *theta = atan2(y, x); }
        

Аргументы передаются этой функции по значению - если функция и присвоит новое значение переменной аргумента, эта операция является локальной и скрыта от вызывающей функции. Поэтому функция не может изменять указатели на числа с плавающей точкой r и theta, но способна изменять значения самих чисел с помощью косвенного обращения. Например, если вызывающая функция содержит объявление float a, b, то вызов функции

polar(1.0, 1.0, a, b)
        

приведет к тому, что для a установится значение 1.414 214 ($$$\sqrt{2}$$$ ), а для b - значение 0.785398 (п/4). Оператор позволяет передавать адреса a и b в функцию, которая работает с этими аргументами как с указателями.

В языке C++ можно достичь того же результата посредством ссылочных параметров:

polar(float x, float y, floats r, floats theta)
  { r = sqrt(x*x + y*y); theta = atan2(y, x); }
        

Запись floats означает "ссылка на float". Ссылки можно рассматривать как встроенные указатели, при каждом использовании которых выполняется автоматический переход. Например, в этой функции ссылка на theta означает ссылку на любую переменную float, используемую во втором аргументе вызывающей функции. Если вызывающая функция содержит объявление float a, b, как в примере из предыдущего абзаца, то в результате вызова функции polar(1.0, 1.0, a, b) переменной a будет присвоено значение 1.414214, а переменной b - значение 0.785398.

До сих пор речь в основном шла об описании отдельных информационных элементов, обрабатываемых программами. Во многих случаях необходимо работать с потенциально крупными наборами данных, и сейчас мы обратимся к основным методам достижения этой цели. Обычно термин структура данных относится к механизму организации информации для обеспечения удобных и эффективных средств управления и доступа к ней. Многие важные структуры данных основаны либо на одном из двух элементарных решений, рассматриваемых ниже, либо на обоих сразу. Массив (array) служит средством организации объектов четко упорядоченным образом, что более удобно для доступа, чем для управления. Список (list) позволяет организовать объекты в виде логической последовательности, что более удобно для управления, чем для доступа.

Упражнения

3.1. Найдите наибольшее и наименьшее числа, которые можно представить типами int, long int, short int, float и double в своей среде программирования.

3.2. Протестируйте генератор случайных чисел в своей системе. Для этого сгенерируйте N случайных целых чисел в диапазоне от 0 до r - 1 с помощью выражения rand() % r и вычислите среднее значение и среднеквадратичное отклонение для r = 10, 100 и 1000 и N = 103, 104, 105 и 106 .

3.3. Протестируйте генератор случайных чисел в своей системе. Для этого сгенерируйте N случайных чисел типа double в диапазоне от 0 до 1, преобразуя их в целые числа диапазона от 0 до r - 1 путем умножения на r и усечения результата. Затем вычислите среднее значение и среднеквадратичное отклонение для r = 10, 100 и 1000 и N = 103, 104, 105 и 106 .

3.4. Выполните упражнения 3.2 и 3.3 для r = 2, 4 и 16.

3.5. Реализуйте функции, позволяющие применять программу 3.2 для случайных разрядов (чисел, которые могут принимать значения только 0 и 1).

3.6. Определите структуру для представления игральных карт.

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

3.8. Добавьте к типу данных point (программы 3.3 и 3.4) функцию, которая определяет, лежат ли три точки на одной прямой, с допуском 10^-4. Считайте, что все точки находятся в единичном квадрате.

3.9. Определите тип данных для треугольников, находящихся в единичном квадрате, включая функцию вычисления площади треугольника. Затем напишите клиентскую программу, которая генерирует случайные тройки пар чисел с плавающей точкой от 0 до 1 и вычисляет среднюю площадь сгенерированных треугольников.

Массивы

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

Массив является фиксированным набором однотипных данных, которые хранятся в виде непрерывной последовательности. Доступ к данным осуществляется по индексам. Для ссылки на i-й элемент массива используется выражение a[i]. Перед выборкой элемента массива a[i] программист должен занести туда какое-то значение. Кроме того, в языке C++ программист должен сам следить, чтобы индексы были неотрицательны и меньше размера массива. Пренебрежение этими правилами является распространенной ошибкой программирования.

Фундаментальность массивов, как структур данных, заключается в их прямом соответствии системам памяти почти на всех компьютерах. Для извлечения содержимого слова из памяти машинный язык требует указания адреса. Таким образом, всю память компьютера можно рассматривать как массив, где адреса памяти соответствуют индексам. Большинство процессоров машинного языка транслируют программы, использующие массивы, в эффективные программы на машинном языке, в которых осуществляется прямой доступ к памяти. Можно с уверенностью сказать, что доступ к массиву с помощью выражения a[i] требует лишь нескольких машинных команд.

Простой пример использования массива демонстрируется в программе 3.5, которая распечатывает все простые числа, меньшие 10000. Используемый метод восходит к третьему столетию до н.э. и называется решетом Эратосфена (см. рис 3.1).

Программа 3.5. Решето Эратосфена

Цель программы заключается в присвоении элементам a[i] значения 1, если i простое число, и значения 0 в противном случае. Сначала значение 1 присваивается всем элементам массива. Затем присваивается значение 0 элементам, индексы которых не являются простыми числами (кратны известным простым числам). Если после этого некоторый элемент a[i] сохраняет значение 1, его индекс является простым числом.

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

#include <iostream.h>
static const int N = 1000;
int main()
  { int i, a[N];
    for (i = 2; i < N; i++) a[i] = 1;
    for (i = 2; i < N; i++)
      if (a[i])
        for (int j = i; j*i < N; j++) a[i*j] = 0;
    for (i = 2; i < N; i++)
      if (a[i]) cout << " " << i;
    cout << endl;
  }
        

(рис 3.1) Решето Эратосфена

Для вычисления простых чисел, меньших 32, сначала во все элементы массива заносится значение 1 (второй столбец). Это указывает, что пока не обнаружено ни одно число, которое не является простым (элементы a[0] и a[1] не используются и не показаны). Затем заносится значение 0 в те элементы массива, индексы которых кратны 2, 3 и 5, поскольку они не являются простыми числами. Индексы элементов массива, в которых сохранилось значение 1, являются простыми числами (крайний правый столбец).

Это типичный алгоритм, где используется возможность быстрого доступа к любому элементу массива по его индексу. Реализация содержит четыре цикла, из которых три выполняют последовательный доступ к массиву от первого до последнего элемента. Четвертый цикл выполняет скачки по массиву, через i элементов за один раз. В некоторых случаях последовательная обработка абсолютно необходима, а в других используется просто поскольку она не хуже других методов. Например, первый цикл программы 3.5 можно заменить на

for (i = N-1; i > 1, i--) a[i] = 1;
        

что никак не отразится на вычислениях. Подобным же образом можно изменить направление внутреннего цикла, либо изменить последний цикл, чтобы печатать простые числа в порядке убывания. Однако нельзя изменить порядок выполнения внешнего цикла основных вычислений, поскольку перед проверкой элемента a[i] на простоту уже должны быть обработаны все целые числа, меньшие i.

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

N + N/2 + N/3 + N/5 + N/7 + N/11 + ...

что меньше, чем

N + N/2 + N/3 + N/4 + ... = NHN ~ Nln N.

Одно из отличительных свойств C++ состоит в том, что имя массива генерирует указатель на первый элемент массива (с индексом 0). Более того, возможны простые арифметические операции с указателями: если p является указателем на объект определенного типа, можно записать код, предполагающий последовательное расположение объектов данного типа. При этом для ссылки на первый объект используется запись *p, на второй - *(p+1), на третий - *(p+2) и т.д. Другими словами, записи *(a+i) и a[i] в языке C++ эквивалентны.

Это обеспечивает альтернативный механизм доступа к объектам массивов, который иногда оказывается удобнее индексации. Он чаще всего используется для массивов символов (строк). Мы вернемся к этому вопросу в разделе 3.6.

Подобно структурам, указатели на массивы важны тем, что позволяют эффективно управлять массивами как высокоуровневыми объектами. В частности, указатель на массив можно передать как аргумент функции - это позволяет функции обращаться к объектам массива без необходимости создания копии всего массива. Такая возможность необходима при написании программ, работающих с очень большими массивами. Например, она используется в функциях поиска, рассмотренных в разделе 2.6 . Другие примеры будут приведены в разделе 3.7.

В программе 3.5 предполагается, что размер массива должен быть известен заранее. Чтобы выполнить программу для другого значения N, следует изменить константу N и повторно скомпилировать программу. В программе 3.6 показан другой способ: пользователь может ввести значение N, и программа выведет простые числа, меньшие этой величины. Здесь применены два основных механизма C++, и в обоих массивы передаются в функции в качестве аргументов. Первый механизм обеспечивает передачу аргументов командной строки главным программам в массиве argv с размером argc. Массив argv является составным и включает объекты, которые сами представляют собой массивы (строки). Мы отложим его рассмотрение до раздела 3.7, а пока примем на веру, что переменная N принимает значение, вводимое пользователем при выполнении программы.

Программа 3.6. Динамическое выделение памяти массиву

Для изменения верхнего предела простых чисел, вычисляемых в программе 3.5, необходима повторная компиляция программы. Однако предельное значение можно принимать из командной строки и использовать его для выделения памяти массиву во время выполнения с помощью операции C++ new[]. Например, если скомпилировать программу и ввести в командной строке 1000000, будут получены все целые числа, меньшие миллиона (если компьютер достаточно мощный для таких вычислений). Для отладки программы (с небольшими затратами времени и памяти) достаточно значения 10 0. В дальнейшем мы будем часто использовать этот подход, хотя для краткости не будем выполнять проверку на нехватку памяти.

int main(int argc, char *argv[])
  { int i, N = atoi(argv[1]);
    int *a = new int[N];
    if (a == 0)
      { cout << "не хватает памяти" << endl; return 0; }
        

Второй базовый механизм - операция new[], которая во время выполнения выделяет под массив нужный объем памяти и возвращает указатель на массив. В некоторых языках программирования динамическое выделение памяти массивам затруднено либо вообще невозможно. А в некоторых других языках этот процесс выполняется автоматически. Динамическое выделение памяти - важный инструмент в программах, работающих с несколькими массивами, особенно если некоторые из них должны иметь большой размер. Если бы в данном случае не было механизма выделения памяти, нам пришлось бы объявить массив с размером, не меньшим любого допустимого входного параметра. В сложной программе, где может использоваться много массивов, сделать так для каждого из них невозможно. В этой книге мы будем обычно использовать код, подобный коду программы 3.6, по причине его гибкости. Однако в некоторых приложениях, где размер массива известен, вполне применимы простые решения, как в программе 3.5. Массивы не только родственны низкоуровневым средствам доступа к данным памяти в большинстве компьютеров. Они широко распространены еще и потому, что прямо соответствуют естественным методам организации данных в приложениях. Например, массивы прямо соответствуют векторам (математический термин для упорядоченных списков объектов).

Стандартная библиотека C++ содержит класс Vector - абстрактный объект, который допускает индексацию подобно массиву (с необязательной автоматической проверкой соответствия диапазону), но в нем предусмотрена возможность увеличения и уменьшения размера. Это позволяет воспользоваться преимуществами массивов, но возлагать задачи проверки допустимости индексов и управления памятью на систему. Поскольку в этой книге много внимания уделяется быстродействию, мы будем избегать неявных затрат и поэтому чаще использовать массивы, указывая, что в коде могут быть применены и векторы (см. упражнение 3.14).

Программа 3.7 - пример программы моделирования, использующей массивы. В ней моделируется последовательность испытаний Бернулли (Bernoulli trials) - известная абстрактная концепция теории вероятностей. Если подбросить монету N раз, вероятность выпадения k решек составляет

$$$${N\choose k}\dfrac{1}{2^{N}} \approx \dfrac{e^{-(k-N/2)^{2}/N}}{\sqrt{\pi N/2}}$$$$

Программа 3.7. Имитация подбрасываний монеты

Если подбросить монету N раз, ожидается выпадение N/2 решек, но в принципе это число может быть любым в диапазоне от 0 до N. Данная программа выполняет эксперимент Mраз, принимая аргументы Mи N из командной строки. Она использует массив f для отслеживания частоты выпадений "i решек" для $$$0\leq i\leqN$$$, а затем выводит гистограмму результатов эксперимента. Каждые 10 выпадений обозначаются одной звездочкой.

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

#include <iostream.h>
#include <stdlib.h>
int heads()
  { return rand() < RAND MAX/2; }
int main(int argc, char *argv[])
  { int i, j, cnt;
    int N = atoi(argv[1]), M = atoi(argv[2]);
    int *f = new int[N+1];
    for (j = 0; j <= N; j + +) f[j] = 0;
    for (i = 0; i < M; i++, f[cnt]++)
      for (cnt = 0, j = 0; j <= N; j++)
        if (heads()) cnt++;
    for (j = 0; j <= N; j++)
      { if (f[j] == 0) cout << ".";
        for (i = 0; i < f[j]; i += 10) cout << "*";
        cout << endl;
      }
  }
        

(рис 3.2) Имитация подбрасываний монеты

Эта таблица демонстрирует результат выполнения программы 3.7 при = 32 и M = 1000. Имитируется 1000 экспериментов подбрасывания монеты по 32 раза. Количество выпадений решки аппроксимируется нормальной функцией распределения, график которой показан поверх данных.

Здесь используется нормальная аппроксимация - известная кривая в форме колокола. На . А пока нам интересны вычисления, в которых используются числа как индексы массива для определения частоты выпадений. Способность поддерживать этот вид операций - одно из основных достоинств массивов.

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

Массивы можно применять для организации объектов различных типов, а не только целых чисел. В языке C++ можно объявлять массивы любых встроенных либо определяемых пользователем типов (другими словами, составных объектов, объявленных как структуры). В программе 3.8 показано использование массива структур для точек на плоскости - с помощью описания структуры из раздела 3.1. Кроме того, демонстрируется типичное использование массивов: организованное хранение данных для обеспечения быстрого доступа к ним в процессе вычислений.

Между прочим, программа 3.8 также интересна в качестве примера квадратичного алгоритма: в ней выполняется проверка всех пар набора из N элементов данных, в результате чего затрачивается время, пропорциональное N². В этой книге для подобных алгоритмов мы всегда пытаемся найти более эффективную альтернативу, поскольку с увеличением N данное решение становится неподъемным. Для данного случая в разделе 3.7 будет показано использование составных структур данных, что дает линейное время вычисления.

Программа 3.8. Вычисление ближайшей точки

Эта программа демонстрирует использование массива структур и представляет типичный случай, когда элементы сохраняются в массиве для последующей обработки в процессе некоторых вычислений. Подсчитывается количество пар из N сгенерированных случайным образом точек на плоскости, соединяемых прямой, длина которой меньше d. При этом используется тип данных для точек, описанный в разделе 3.1. Время выполнения составляет O(N2) , поэтому программа не может применяться для больших значений N. Программа 3.20 обеспечивает более быстрое решение.

#include <math.h>
#include <iostream.h>
#include <stdlib.h>
#include "Point.h"
float randFloat()
  { return 1.0*rand()/RAND MAX; }
int main(int argc, char *argv[])
  { float d = atof(argv[2]);
    int i, cnt = 0, N = atoi(argv[1]);
    point *a = new point[N];
    for (i = 0; i < N; i++)
      { a[i].x = randFloat(); a[i].y = randFloat(); }
    for (i = 0; i < N; i++)
      for (int j = i+1; j < N; j + +)
        if (distance(a[i], a[j]) < d) cnt++;
    cout << cnt << " пар в радиусе " << d << endl;
  }
        

Подобным образом можно создавать составные типы произвольной сложности: не только массивы структур, но и массивы массивов, либо структуры, содержащие массивы. Эти возможности будут подробно рассматриваться в разделе 3.7. Однако сначала ознакомимся со связными списками, которые служат главной альтернативой массивам при организации коллекций объектов.

Упражнения

3.10. Предположим, переменная a объявлена как int a[99]. Определите содержимое массива после выполнения следующих двух операторов:

for (i = 0; i < 99; i++) a[i] = 98-i;

for (i = 0; i < 99; i++) a[i] = a[a[i]];

3.11. Измените реализацию решета Эратосфена (программа 3.5) для использования массива (1) символов и (2) разрядов. Определите влияние этих изменений на расход памяти и времени, используемых программой.

3.12. С помощью решета Эратосфена определите количество простых чисел, меньших N, для N = 103, 104, 105 и 106 .

3.13. С помощью решета Эратосфена постройте график зависимости от N количества простых чисел, меньших N, для значений N от 1 до 1000.

3.14. Стандартная библиотека C++ в качестве альтернативы массивам содержит тип данных Vector. Узнайте, как использовать этот тип данных в своей системе, и определите его влияние на время выполнения, если заменить в программе 3.5 массив типом Vector.

3.15. Эмпирически определите эффект удаления проверки a[i] из внутреннего цикла программы 3.5 для N = 103, 104, 105 и 106 и объясните его.

3.16. Напишите программу подсчета количества различных целых чисел, меньших 1000, которые встречаются во входном потоке.

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

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

3.19. Измените программу 3.7 для имитации случая, когда решка выпадает с вероятностью p. Выполните 1000 испытаний с 32 подбрасываниями при .

3.20. Измените программу 3.7 для имитации случая, когда решка выпадает с вероятностью $$$\lambda/N$$$ . Выполните 1000 испытаний с 32 подбрасываниями для получения выходных данных, которые можно сравнить с рис 3.2. Получается классическое распределение Пуассона.

3.21. Измените программу 3.8 для вывода координат пары ближайших точек.

3.22. Измените программу 3.8 для выполнения тех же вычислений в в d-мерном пространстве.

Связные списки

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

Определение 3.2. Связный список - это набор элементов, содержащихся в узлах (node), каждый из которых также содержит ссылку (link) на некоторый узел.

В определении узлов упоминаются ссылки на узлы, поэтому связные списки иногда называют самоссылочыми (self-referent) структурами. Более того, хотя ссылка узла обычно указывает на другой узел, возможны и ссылки на себя, поэтому связные списки могут представлять собой циклические (cyclic) структуры. Последствия этих двух фактов станут ясны при рассмотрении конкретных представлений и применений связных списков.

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

Это пустая (null) ссылка, не указывающая на какой-либо узел.

Ссылка указывает на фиктивный узел (dummy node), который не содержит элементов.

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

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

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

Связные списки являются примитивными конструкциями в некоторых языках программирования, но не в C++. Однако базовые строительные блоки, о которых шла речь в разделе 3.1, хорошо приспособлены для реализации связных списков. Указатели используются для ссылок, а структуры для узлов:

struct node { Item item; node *next; } ;
typedef node *link;
        

Эта пара выражений - ни что иное, как код C++ для определения 3.2. Узлы состоят из элементов (здесь типа будут представлены более сложные случаи, которые обеспечивают большую гибкость и более эффективную реализацию определенных операций, но этот простой пример достаточен для понимания основ обработки списков. Подобные соглашения для связных структур будут использоваться на протяжении всей книги.

Для эффективного использования связных списков ключевое значение имеет выделение памяти. Выше описана единственная структура (struct node), но она может существовать во множестве экземпляров - по одному для каждого узла, который придется использовать. Как только понадобится новый узел, для него нужно выделить память. При объявлении переменной типа node для нее резервируется память во время компиляции. Однако часто приходится организовывать вычисления, связанные с резервированием памяти во время выполнения - с помощью вызовов системных операций управления памятью. Например, в строке кода

link x = new node;
        

содержится операция new, которая резервирует для узла достаточный объем памяти и возвращает указатель на него в переменной x. В разделе 3.5 будет кратко показано, как система резервирует память, поскольку это хороший пример применения связных списков!

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

struct node
  { Item item; node *next;
    node (Item x; node *t)
      { item = x; next = t; };
  };
  typedef node *link;
        

то оператор

link t = new node(x, t);
        

не только резервирует достаточный для узла объем памяти и возвращает указатель на него в переменной t, но и присваивает полю item узла значение x, а указателю поля - значение t. Конструкторы помогают избегать ошибок, связанных с не инициализированными данными.

Теперь, когда узел списка создан, возникает вопрос: как обращаться к находящейся в нем информации - элементу и ссылке? Мы уже ознакомились с базовыми операциями, необходимыми для выполнения этой задачи: достаточно разыменовать указатель, а затем использовать имена членов структуры. Элемент узла, на который указывает ссылка x (типа Item), имеет вид (*x).item, а ссылка (типа link) - (*x).link. Эти операции так часто используются, что в языке C++ для них предусмотрены эквивалентные сокращения: x->item и x->link. Кроме того, нам так часто будет нужна фраза "узел, на который указывает ссылка x", что мы будем говорить просто "узел x" - ссылка именует узел.

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

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

Пустые ссылки, фиктивные узлы и пустые списки будут рассмотрены в разделе 3.4. Как показано на рисунках, и для вставки, и для удаления необходимо лишь два оператора C++. Для удаления узла, следующего за узлом x, используются операторы

t = x->next; x->next = t->next;
        

или проще:

x->next = x->next->next;
        

Для вставки в список узла t в позицию, следующую за узлом x, используется операторы

t->next = x->next; x->next = t;
        

(рис 3.3) Удаление из связного списка

Для удаления из связного списка узла, следующего за заданным узлом x, в t заносится указатель на удаляемый узел, а затем ссылка в x заменяется на t->next. Указатель t может использоваться для обращения к удаленному узлу. Хотя ссылка этого узла по-прежнему указывает куда-то внутрь списка, обычно такая ссылка не используется после удаления узла из списка - за исключением, возможно, сообщения системе с помощью операции delete о том, что задействованная память больше не нужна.

(рис 3.4) Вставка в связный список

Для вставки узла t в позицию связного списка, следующую за заданным узлом x (вверху), в t->next заносится значение x->next (в середине), затем в x->next заносится значение t (внизу).

Именно в силу простоты вставки и удаления и существуют связные списки. Соответствующие операции для массивов неестественны и неудобны, поскольку требуют перемещения всего содержимого массива, которое следует после затрагиваемого элемента.

Однако связные списки плохо приспособлены для поиска k-го элемента (по индексу) - операции, которая чрезвычайно эффективна в массивах. В массиве для поиска k-го элемента достаточно записать просто a[k], а в списке для этого необходимо перейти по k ссылкам. Другая операция, неестественная для списков, в которых узлы содержат лишь единственную ссылку - поиск элемента, предшествующего данному.

После удаления узла из связного списка операцией x->next = x->next->next к нему уже невозможно обратиться. Для небольших программ, вроде рассмотренных выше примеров, это не имеет существенного значения, но обычно хорошей практикой программирования считается применение операции delete (противоположной операции new) для любого узла, который уже не нужен. В частности, последовательность операторов

t = x->next; x->next = t->next; delete t;

        

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

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

Программа 3.9. Пример циклического списка (задача Иосифа)

Для представления людей, расставленных в круг, создается циклический связный список, где каждый элемент (человек) содержит ссылку на соседний элемент против часовой стрелки. Целое число i представляет i-го человека в круге. После создания циклического списка из одного узла вставляются узлы от 2 до N, и в результате образуется окружность с узлами от 1 до N. При этом переменная x указывает на узел N. Затем пропускаем M - 1 узлов, начиная с 1-го, и изменяем значение ссылки (M- 1)-го узла так, чтобы пропустить M-ый узел. Продолжаем эту операцию, пока не останется один узел.

#include <iostream.h>
#include <stdlib.h>
struct node
  { int item; node* next;
    node(int x, node* t)
      { item = x; next = t; }
  };
  typedef node *link;
  int main(int argc, char *argv[])
    { int i, N = atoi(argv[1]), M = atoi(argv[2]);
      link t = new node(1, 0); t->next = t;
      link x = t;
      for (i = 2; i <= N; i++)
        x = (x->next = new node(i, t));
      while (x != x->next)
        { for (i = 1; i < M; i++) x = x->next;
          x->next = x->next->next;
        }
      cout << x->item << endl;
    }
        

В качестве примера рассмотрим следующую программу решения задачи Иосифа Флавия - любопытного аналога решета Эратосфена.

Предположим, N человек решили выбрать главаря. Для этого они встали в круг и стали удалять каждого M-го человека, смыкая круг после каждого удаления. Задача состоит в определении, кто останется последним (чтобы потенциальный лидер с математическими способностями смог заранее выбрать нужную позицию в круге).

(рис 3.5) Пример задачи Иосифа

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

Номер выбираемого главаря является функцией от для N = 9 и M = 5, люди удаляются в порядке 5 1 7 4 3 6 9 2, а 8-ой номер становится избранным главарем. Программа 3.9 считывает значения N и M, а затем распечатывает эту последовательность.

Для прямой имитации процесса выбора в программе 3.9 используется циклический связный список. Сначала создается список элементов от 1 до . Затем в списке отсчитывается . Этот процесс продолжается до тех пор, пока не останется только один узел (который будет указывать на себя).

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

В языке C++ указатели служат прямой и удобной реализацией абстрактной концепции связных списков, но важность абстракции не зависит от конкретной реализации. Например, на рис 3.6 показана реализация связного списка для задачи Иосифа с помощью массивов целых чисел. То есть связный список можно реализовать с помощью индексов массива вместо указателей. Связные списки применялись задолго до появления конструкций указателей в языках высокого уровня, таких как C++. И даже в современных системах иногда оказываются удобными реализации на основе массивов.

(рис 3.6) Представление связного списка с помощью массивов

Здесь показана реализация связного списка для задачи Иосифа (см. рис 3.5) с помощью индексов массива вместо указателей. Индекс элемента, следующего в списке за элементом с индексом 0, находится в next[0] и т.д. Сначала (три верхних строки) элемент для участника i имеет индекс i-1; циклический список формируется занесением значений i+1 в next[i] для i от 0 до 8, а в next[8] заносится значение 0. Для имитации процесса выбора Иосифа изменяются ссылки (элементы массива next), но элементы участников не перемещаются. Каждая пара строк показывает результат перемещения по списку четырехкратным выполнением x = next[x] с последующим удалением пятого элемента (отображаемого в крайнем левом столбце) путем занесения в элемент next[x] значения next[next[x]].

Упражнения

3.23. Напишите функцию, которая возвращает количество узлов циклического списка по заданному указателю на один из узлов списка.

3.24. Напишите фрагмент кода, который определяет количество узлов в циклическом списке между узлами, указанными двумя данными указателями x и t.

3.25. Напишите фрагмент кода, который по указателям x и t двух раздельных связных списков вставляет список, указываемый t, в список, указываемый x - в позицию после узла x.

3.26. Напишите фрагмент кода, который для данных указателей x и t на узлы циклического списка перемещает узел, следующий после t, в позицию после узла x.

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

3.28. Определите время выполнения программы 3.9 в виде функции от Mи N.

3.29. Используйте программу 3.9, чтобы определить значения функции Иосифа для M = 2, 3, 5, 10 и N = 103, 104, 105 и 106 .

3.30. Используйте программу 3.9, чтобы построить график зависимости функции Иосифа от N для M = 10 и N от 2 до 1000.

3.31. Воспроизведите таблицу на рис 3.6 для случая, когда элемент i первоначально находится в массиве в позиции N-i.

3.32. Разработайте версию программы 3.9, в которой для реализации связного списка используется массив индексов (см. рис 3.6).

Простые операции со списками

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

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

Искусство разработки корректного и эффективного кода для приложений обработки списков приходит с практикой и терпением. В этом разделе представлены примеры и упражнения, призванные помочь освоить создание кода обработки списков. На протяжении книги будет использоваться множество других примеров, поскольку связные структуры лежат в основе многих эффективных алгоритмов.

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

Определение 3.3. Связный список представляет собой либо пустую ссылку, либо ссылку на узел, который содержит элемент и ссылку на связный список.

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

Одна из наиболее распространенных операций со списками - обход (traverse). Это последовательный перебор элементов списка и выполнение некоторых операций с каждым из них. Например, если x является указателем на первый узел списка, последний узел содержит пустой указатель, а visit - процедура, которая принимает элемент в качестве аргумента, то обход списка можно реализовать следующим образом:

for (link t = x; t != 0; t = t->next) visit(t->item);
        

Этот цикл (либо его эквивалентная форма while) постоянно встречается в программах обработки списков, подобно циклу for (int i = 0; i < N; i++) в программах обработки массивов. Программа 3.10 является реализацией простой задачи обработки списка - изменение порядка следования узлов на обратный. Она принимает связный список в качестве аргумента и возвращает связный список, состоящий из тех же узлов, но расположенных в обратном порядке.

Программа 3.10. Обращение списка

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

link reverse(link x)
  { link t, y = x, r = 0;
    while (y != 0)
      { t = y->next; y->next = r; r = y; y = t; }
    return r;
  }
        

(рис 3.7) Обращение списка

Для обращения порядка следования элементов списка используются указатель r на уже обработанную часть списка и указатель y на еще не просмотренную часть списка. На данной диаграмме показано изменение указателей каждого узла списка. Указатель узла, следующего за y, сохраняется в переменной t, ссылка y изменяется так, чтобы указывать на r, после чего r перемещается в позицию y, а y - в позицию t.

На рис 3.7 показано изменение, выполняемое функцией в своем главном цикле для каждого узла. Такие диаграммы упрощают проверку каждого оператора программы на правильность изменения ссылок. Программисты обычно используют подобные диаграммы для наглядного представления операций обработки списков.

Программа 3.11 служит реализацией другой задачи обработки списков: переупорядочение узлов по возрастанию их элементов. Она генерирует , ожидаемое время выполнения программы пропорционально , поскольку в главах 6-10 будет рассмотрено множество методов сортировки. А сейчас нам просто нужен пример приложения, выполняющего обработку списков.

Списки в программе 3.11 демонстрируют еще одно часто используемое соглашение: в начале каждого списка содержится фиктивный узел, называемый ведущим (head node). Поле элемента ведущего узла игнорируется, а его ссылка всегда содержит указатель на узел с первым элементом списка. В программе используется два списка: один для накопления случайных чисел, добавляемых в первом цикле, а другой для накопления сортированного результата во втором цикле. На рис 3.8 показаны изменения, вносимые программой 3.11 в течение одной итерации главного цикла. Из входного списка извлекается очередной узел, находится его позиция в выходном списке, и узел вставляется в эту позицию.

Программа 3.11. Сортировка методом вставки в список

Этот код генерирует N случайных целых чисел в диапазоне от 0 до 999, строит связный список, в котором на каждый узел приходится по одному числу (первый цикл for), затем переупорядочивает узлы, чтобы при обходе списка числа следовали по возрастанию (второй цикл for). Для выполнения сортировки используется два списка - входной (несортированный) и выходной (сортированный). В каждой итерации цикла из входного списка удаляется узел и вставляется в нужную позицию выходного списка. Код упрощен благодаря использованию в каждом списке ведущих узлов, содержащих ссылки на первые узлы. В объявлениях ведущих узлов применен конструктор, поэтому их данные инициализируются при создании.

node heada(0, 0); link a = heada, t = a;
for (int i = 0; i < N; i++)
  t = (t->next = new node(rand() % 1000, 0));
node headb(0, 0); link u, x, b = headb;
for (t = a->next; t != 0; t = u)
  { u = t->next;
    for (x = b; x->next != 0; x = x->next)
      if (x->next->item > t->item) break;
    t->next = x->next; x->next = t;
  }
        

(рис 3.8) Сортировка связного списка

На этой диаграмме показан один шаг преобразования неупорядоченного связного списка (заданного указателем a) в упорядоченный связный список (заданный указателем b) с использованием сортировки вставками. Сначала берется первый узел неупорядоченного списка, и указатель на него сохраняется в t (вверху). Затем выполняется поиск в b первого узла x, для которого справедливо условие x->next->item > t->item (или x->next = NULL), и t вставляется в список после x (в середине). Эти операции уменьшают на один узел размер списка a и увеличивают на один узел размер списка b, сохраняя список b упорядоченным (внизу). После завершения цикла список a окажется пустым, а список b будет содержать все узлы в упорядоченном виде.

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

Дублировать цикл for, который обнаруживает наименьший элемент, и создавать список из одного узла таким же образом, как в программе 3.9.

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

Использовать фиктивный ведущий узел, ссылка которого указывает на первый узел списка, как в данном примере.

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

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

Несколько вариантов соглашений о связных списках приведено в таблица 3.1; остальные рассматриваются в упражнениях. Во всех вариантах таблица 3.1 для ссылки на список используется указатель head, и программа управляет ссылками узлов, используя данный код для различных операций. Выделение памяти под узлы и ее освобождение, а также заполнение узлов информацией одинаковы для всех соглашений. Для повышения надежности функций, реализующих те же операции, необходим дополнительный код проверки на ошибки. Таблица же приведена для демонстрации сходства и различия вариантов.

Другая важная ситуация, в которой иногда удобно использовать ведущий узел, возникает, когда необходимо передать указатели на списки в качестве аргументов функций, которые могут изменять список таким же образом, как и в случае массивов. Использование ведущего узла позволяет функции принимать или возвращать пустой список. При отсутствии ведущего узла функция нуждается в механизме сообщения вызывающей функции, что список оставлен пустым. Одно из решений для C++ состоит в передаче параметра-указателя на список по ссылке. Второй механизм - примененный в программе 3.10 - прием функциями обработки списков указателей на входные списки в качестве аргументов и возврат указателей на выходные списки. При этом ведущие узлы не нужны. Кроме того, этот механизм очень удобен для рекурсивной обработки списков, которая часто используется в этой книге (см. раздел 5.1 ).

В программе 3.12 объявлен набор функций в виде "черного ящика", которые реализуют базовый список операций. Это позволит нам не повторять фрагменты кода в тексте программ и не зависеть от деталей реализации. Программа 3.13 реализует выбор Иосифа (см. программу 3.9), но уже в виде клиентской программы, использующей этот интерфейс. Идентификация важных операций, используемых в вычислениях, и их описание в интерфейсе обеспечивают гибкость, которая позволяет рассматривать различные конкретные реализации важных операций и проверять их эффективность.

В таблица 3.1 приведены реализации базовых операций обработки списков, основанные на пяти часто используемых соглашениях. Такой код используется в простых приложениях обработки списков, непосредственно в коде программы.

Соглашения о первом и последнем узлах в связных списках

Циклический список, всегда непустой
первая вставка:	head->next = head;
вставка t после х:	t->next = x->next; x->next = t;
удаление после х:	x->next = x->next->next;
цикл обхода:	t = head;
	do { ... t = t->next; } while (t != head);
проверка на наличие лишь одного элемента:	if (head->next == head)
Указатель на начало, пустой указатель в конце
инициализация:	head = 0;
вставка t после х:	if (x == 0) {head = t; head->next = 0; }
	{ t->next = x->next; x->next = t; }
удаление после х:	t = x->next; x->next = t->next;
цикл обхода:	for (t = head; t != 0; t = t->next)
проверка на пустоту:	if (head == 0)
Фиктивный ведущий узел, пустой указатель в конце
инициализация:	head = new node; head->next = 0;
вставка t после х:	t->next = x->next; x->next = t;
удаление после х:	t = x->next; x->next = t->next;
цикл обхода:	for (t = head->next; t != 0; t = t->next)
проверка на пустоту:	if (head->next == 0)
Фиктивные ведущий и завершающий узлы
инициализация:	head = new node;
	z = new node;
	head->next = z; z->next = z;
вставка t после х:	t->next = x->next; x->next = t;
удаление после х:	x->next = x->next->next;
цикл обхода:	for (t = head->next; t != z; t = t->next)
проверка на пустоту:	if (head->next == z)

Программа 3.12. Интерфейс обработки списков

В этом коде, который можно сохранить в интерфейсном файле list.h, описаны типы узлов и ссылок, а также выполняемые над ними операции. Для выделения памяти под узлы списка и ее освобождения объявляются собственные функции. Функция , несколько отличный интерфейс, основанный на классах C++, может обеспечить независимость клиентских программ от подробностей реализации.

typedef int Item;
struct node { Item item; node *next; };
typedef node *link;
typedef link Node;
void construct(int);
Node newNode(int);
void deleteNode(Node);
void insert(Node, Node);
Node remove(Node);
Node next(Node);
Item item(Node);

        

Программа 3.13. Организация списка для задачи Иосифа

Эта программа решения задачи Иосифа служит примером клиентской программы, использующей примитивы обработки списков, которые объявлены в программе 3.12 и реализованы в программе 3.14.

#include <iostream.h>
#include <stdlib.h>
#include "list.h"
int main(int argc, char *argv[])
  { int i, N = atoi(argv[1]), M = atoi(argv[2]);
    Node t, x;
    construct(N);
    for (i = 2, x = newNode(1); i <= N; i++)
      { t = newNode(i); insert(x, t); x = t; }
    while (x != next(x))
      { for (i = 1; i < M; i++) x = next(x);
        deleteNode(remove(x));
      }
    cout << item(x) << endl;
    return 0;
  }
        

В разделе 3.5 рассматривается реализация операций из программы 3.12 (см. программу 3.14), но можно опробовать и другие решения, не изменяя программу 3.13 (см. упражнение 3.51). Эта тема еще будет неоднократно затронута в данной книге. В языке C++ имеется несколько механизмов, специально предназначенных для упрощения разработки инкапсулированных реализаций; речь об этом пойдет в .

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

С помощью дополнительных ссылок можно реализовать возможность обратного перемещения по связному списку. Например, применение двухсвязного списка (double linked list) позволяет выполнять операцию "найти элемент, предшествующий данному". В таком списке каждый узел содержит две ссылки: одна (prev) указывает на предыдущий элемент, а другая (next) - на следующий. При наличии фиктивных узлов либо цикличного двухсвязного списка выражения x, и 3.10 показаны основные действия со ссылками, необходимые для реализации операций удалить (remove), вставить после (insert after) и вставить перед (insert before) в двухсвязных списках. Обратите внимание, что для операции удаления не требуется дополнительной информации о предшествующем (либо следующем) узле в списке, как для односвязных списков - эта информация содержится в самом узле.

(рис 3.9) Удаление в двухсвязном списке

Как видно из диаграммы, для удаления узла в двухсвязном списке достаточно знать указатель на этот узел. Для заданного t в t->next->prev заносится значение t->prev (в середине), а в t->prev->next - значение t->next (внизу).

(рис 3.10) Вставка в двухсвязном списке

Для вставки узла в двухсвязный список необходимо установить четыре указателя. Новый узел можно вставить после данного узла (как показано на диаграмме), либо перед ним. Для вставки узла t после узла x в t->next заносится значение x->next, а в x->next->prev - значение t (в середине). Затем в x->next заносится значение t, а в t->prev - значение x (внизу).

На самом деле главная особенность двухсвязных списков состоит в возможности удаления узла, когда ссылка на него является единственной информацией об узле. Часто бывает, что ссылка передается при вызове функции в качестве аргумента, а также что узел имеет другие ссылки и сам является частью другой структуры данных. Эта дополнительная возможность требует в два раза больше памяти для ссылок в каждом узле, и в два раза больше манипуляций со ссылками на каждую базовую операцию. Поэтому двухсвязные списки обычно не используются, если этого не требуют условия. Рассмотрение подробных реализаций отложим до обзора нескольких особых случаев, где в этом возникнет необходимость - например, в разделе 9.5 .

Связные списки используются в материале книги, во-первых, для основных АТД-реализаций (абстрактные типы данных; см. ), а во-вторых, в качестве компонентов более сложных структур данных. Для многих программистов связные списки являются первым знакомством с абстрактными структурами данных, которыми разработчик может непосредственно управлять. Как мы неоднократно убедимся, они образуют важное средство разработки высокоуровневых абстрактных структур данных, необходимых для решения множества задач.

Упражнения

3.33. Напишите функцию, которая перемещает наибольший элемент данного списка в конец списка.

3.34. Напишите функцию, которая перемещает наименьший элемент данного списка в начало списка.

3.35. Напишите функцию, которая переупорядочивает связный список так, чтобы узлы в четных позициях следовали после узлов в нечетных позициях, сохраняя относительный порядок четных и нечетных узлов.

3.36. Реализуйте фрагмент кода для связного списка, меняющий местами узлы, которые следуют после узлов, указываемых ссылками t и u.

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

3.38. Напишите функцию, принимающую два аргумента - ссылку на список и функцию, принимающую список в качестве аргумента - и удаляет все элементы данного списка, для которых функция возвращает ненулевое значение.

3.39. Выполните упражнение 3.38, но создайте копии узлов, которые прошли проверку и возвратите ссылку на список, содержащий эти узлы, в порядке их следования в исходном списке.

3.40. Реализуйте версию программы 3.10, в которой используется ведущий узел.

3.41. Реализуйте версию программы 3.11, в которой не используются ведущие узлы.

3.42. Реализуйте версию программы 3.9, в которой используется ведущий узел.

3.43. Реализуйте функцию, которая меняет местами два заданных узла в двухсвязном списке.

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

3.45. Добавьте в таблица 3.1 строку для циклического списка, имеющего фиктивный узел, который служит и первым, и последним узлом.

Выделение памяти под списки

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

Здесь очень важно представлять, как может быть реализована операция new. Например, при удалении узла из списка наша задача - оформить ссылки таким образом, чтобы узел более не был привязан к списку. Но что делает система с памятью, которую этот узел занимал? Как система утилизирует пространство, чтобы всегда иметь возможность выделять его под новый узел операцией new? За этими вопросами стоят механизмы, которые служат еще одним примером эффективности элементарной обработки списков.

Операция delete противоположна операции new. Когда блок выделенной памяти уже не нужен, мы с помощью операции delete сообщаем системе, что этот блок доступен для дальнейшего использования. Динамическое распределение памяти (dynamic memory allocation) - это процесс управления памятью и действий в ответ на вызовы new и delete из клиентских программ.

При выполнении операции new непосредственно в приложениях, таких как программы 3.9 или 3.11, как правило, запрашиваются блоки памяти одинакового размера. Поэтому метод отслеживания памяти, доступной для распределения, напрашивается сам: достаточно использовать связный список! Все узлы, которые не входят ни в один используемый список, можно совместно содержать в единственном связном списке. Этот список называется свободным (free list). Когда необходимо выделить память под узел, он извлекается - то есть удаляется - из свободного списка. При удалении узла из какого-либо списка он вставляется в свободный список.

Программа 3.14 является реализацией интерфейса, описанного в программе 3.12, включая функции распределения памяти. При совместной компиляции с программой 3.13 она дает такой же результат, что и прямая реализация, с которой мы начали в программе 3.9. Сопровождение свободного списка для узлов фиксированного размера - тривиальная задача при наличии базовых операций вставки и удаления узлов из списка.

Программа 3.14. Реализация интерфейса обработки списков

Эта программа реализует функции, объявленные в программе 3.12, а также демонстрирует стандартное распределение памяти под узлы фиксированного размера. Создается свободный список, который инициализируется максимальным количеством узлов, используемых программой. Все узлы взаимосвязаны. Когда клиентская программа выделяет память для узла, он удаляется из свободного списка. Когда клиентская программа освобождает узел, он добавляется к свободному списку.

По соглашению клиентские программы обращаются к узлам списков только путем объявления переменных типа Node и использования их в качестве аргументов функций, описанных в интерфейсе. Узлы, возвращаемые клиентским программам, имеют ссылки на самих себя. Эти соглашения служат средством защиты от ссылок неопределенными указателями и в какой-то мере гарантируют, что клиент использует интерфейс должным образом. В языке C++ эти соглашения реализуются путем использования классов совместно с конструкторами (см. ).

#include <stdlib.h>
#include "list.h"
link freelist;
void construct(int N)
  {
    freelist = new node[N+1];
    for (int i = 0; i < N; i++)
      freelist[i].next = freelist[i+1];
    freelist[N].next = 0;
  }
  link newNode(int i)
    { link x = remove(freelist);
      x->item = i; x->next = x;
      return x;
    }
    void deleteNode(link x)
      { insert(freelist, x); }
    void insert(link x, link t)
      { t->next = x->next; x->next = t; }
    link remove(link x)
      { link t = x->next; x->next = t->next; return t; }
    link next(link x)
    Item item(link x)
      { return x->item; }
        

На рис 3.11 показано разрастание свободного списка по мере удаления узлов в программе 3.13. Для простоты подразумевается реализация связного списка (без ведущего узла), основанная на индексах массива.

Реализация механизма распределения памяти общего назначения в среде C++ намного сложнее, чем подразумевают рассмотренные простые примеры, а реализация операции new в стандартной библиотеке явно не настолько проста, как показано в программе 3.14. Одно из основных различий состоит в том, что функции new приходится обрабатывать запросы на выделение памяти для узлов различного размера - от крохотных до огромных. Для этой цели разработано несколько хитроумных алгоритмов. Другой подход, используемый в некоторых современных системах, состоит в освобождении пользователя от необходимости явно удалять узлы за счет алгоритмов сборки мусора (garbage collection). Эти алгоритмы автоматически удаляют все узлы, на которые не указывает ни одна ссылка. В этой связи также разработано несколько нетривиальных алгоритмов управления памятью. Мы не будем рассматривать их подробно, поскольку их характеристики быстродействия зависят от свойств определенных компьютеров.

(рис 3.11) Представление связного списка и свободного списка в виде массивов

На этой версии рис 3.6 приведен результат ведения свободного списка с узлами, удаленными из циклического списка. Слева указан индекс первого узла свободного списка. После завершения процесса свободный список представляет собой связный список, содержащий все удаленные элементы. Переходы по ссылкам, начиная с 1, дают следующий ряд элементов: 2 9 6 3 4 7 1 5 - т.е. в порядке, обратном тому, в котором элементы удалялись.

Программы, использующие конкретные сведения о приложении, часто эффективнее программ общего назначения, решающих те же задачи. Распределение памяти - не исключение из этого правила. Алгоритм обработки запросов на выделение блоков памяти различного размера не может "знать", что всегда будут запрашиваться блоки фиксированного размера, и поэтому не может использовать этот факт.

Парадоксально, но вторая причина отказа от функций библиотек общего назначения заключается в том, что это делает программу более переносимой - так можно защититься от непредвиденных изменений быстродействия при смене библиотеки либо переноса в другую систему. Многие программисты считают, что использование простого механизма распределения памяти, вроде продемонстрированного в программе 3.14 - удачный способ разработки эффективных и переносимых программ, использующих связные списки. Этот подход возможен в ряде алгоритмов, которые будут рассмотрены в данной книге, если в них применяются подобные запросы к системе управления памятью. В остальной части книги для распределения памяти будут применяться стандартные функции C++ new и delete.

Упражнения

3.46. Напишите программу, которая удаляет все узлы связного списка (с помощью операции delete с указателем).

3.47. Напишите программу, которая удаляет узлы связного списка, находящиеся в позициях с номерами, кратными 5 (пятый, десятый, пятнадцатый и т.д.).

3.48. Напишите программу, которая удаляет узлы в четных позициях связного списка (второй, четвертый, шестой и т.д.).

3.49. Реализуйте интерфейс программы 3.12 с помощью непосредственных вызовов new и delete в функциях newNode и deleteNode соответственно.

3.50. Эмпирически сравните время выполнения функций распределения памяти из программы 3.14 с операторами new и delete (см. упражнение 3.49) для программы 3.13 при M = 2 и N = 103, 104, 105 и 106 .

3.51. Реализуйте интерфейс программы 3.12, используя вместо указателей индексы массива (без ведущего узла) таким образом, чтобы результат работы описывался рисунком 3.11.

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

3.53. При соблюдении условий упражнения 3.52 напишите фрагмент кода, который для заданного указателя узла подсчитывает количество различных узлов, которые будут достигнуты при переходах по ссылкам от данного узла. Модификация любых узлов не допускается. Используйте не более некоторого постоянного объема дополнительной памяти.

3.54. При соблюдении условий упражнения 3.53 напишите функцию, которая определяет, достигнут ли одного и того же цикла переходы из двух заданных ссылок.

Строки

В языке C термин "строка" (string) обозначает массив символов переменной длины, определяемый начальной позицией и символом завершения строки. Язык C++ наследует эту структуру данных из C. Кроме того, строки в качестве высокоуровневой абстракции включены в стандартную библиотеку. В этом разделе мы рассмотрим несколько примеров строк в стиле C. Ценность строк в качестве низкоуровневых структур данных обусловлена двумя главными причинами. Во-первых, во многих вычислительных приложениях выполняется обработка текстовых данных, которые могут представляться непосредственно строками. Во-вторых, многие вычислительные системы предоставляют прямой и эффективный доступ к байтам памяти, которые в точности соответствуют символам строк. Таким образом, в подавляющем большинстве случаев абстракция строк связывает потребности приложения с возможностями компьютера.

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

Язык C++ наследует из C эффективную реализацию на основе массивов, которая рассматривается в этом разделе, а также предоставляет более обобщенную реализацию из стандартной библиотеки. В будут рассмотрены и другие реализации.

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

Для строки необходимо зарезервировать память либо во время компиляции, объявив массив символов фиксированной длины, либо во время выполнения, с помощью вызова new[]. После выделения памяти массиву его можно заполнять символами с начала и до символа завершения строки. Без символа завершения строка представляет собой обыкновенный массив символов. Символ завершения строки позволяет применять более высокий уровень абстракции, когда только часть массива (от начала до символа завершения) считается содержащей значимую информацию. Символ завершения имеет значение 0, или '\0'.

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

Одной из наиболее важных является операция сравнения (compare). Она определяет, которая из двух строк должна быть первой в словаре. Для простоты изложения предполагается идеальный словарь (поскольку реальные правила для строк, содержащих знаки пунктуации, буквы нижнего и верхнего регистра, цифры и пр., довольно сложны), и строки сравниваются посимвольно от начала и до конца. Такой порядок называется лексикографическим. Кроме того, функция сравнения используется для определения равенства строк: по соглашению функция сравнения возвращает отрицательное число, если первая строка находится в словаре перед второй строкой, ноль, если строки равны, и положительное число, если первая строка находится в словаре после второй. Важно понимать, что проверка на равенство двух строк - это не определение, равны ли два указателя строк: если два указателя строк равны, то равны и соответствующие строки (это просто одна и та же строка), но различные указатели строк могут указывать на равные строки (идентичные последовательности символов). Хранение информации в строках с последующей обработкой либо доступом к ней путем сравнения строк, применяется во множестве приложений. Поэтому операция сравнения имеет особое значение. Характерный пример содержится в разделе 3.7, а также во многих других местах книги.

Программа 3.15 является реализацией простой задачи обработки строк. Она выводит те позиции внутри длинной строки текста, где содержится короткая строка-образец. Для этой задачи разработано несколько сложных алгоритмов, а данный простой алгоритм демонстрирует несколько соглашений, используемых при обработке строк в C++.

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

Элементарные операции со строками

Версии с индексированным массивом
Вычисление длины строки (strlen(a))	for (i = 0; a[i] != 0; i++) ; return i ;
Копирование (strcpy(a, b))	for (i = 0; (a[i] = b[i]) != 0; i++) ;
Сравнение (strcmp(a, b))	for (i = 0; a[i] == b[i]; i++)
	if (a[i] == 0) return 0;
	return a[i] - b[i];
Сравнение (первых символов) (strncmp(a, b, n))	for (i = 0; i < n a[i] != 0; i++)
	if (a[i] != b[i]) return a[i] - b[i];
	return 0;
Присоединение (strcat(a, b))	strcpy(a+strlen(a), b)
Эквивалентные версии с указателями
Вычисление длины строки (strlen(a))	b = a; while (*b++) ; return b-a-1;
Копирование (strcpy(a, b))	while (*a++ = *b++) ;
Сравнение (strcmp(a, b))	while (*a++ = *b++)
	if (*(a-1) == 0) return 0;
	return *(a-1) - *(b-1);

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

for (i = 0; i < strlen(a); i++)
  if (strncmp(a[i], p, strlen(p)) == 0)
    cout << i << " ";
        

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

Программа 3.15. Поиск строки

Эта программа обнаруживает все вхождения введенного из командной строки слова в строке текста (предположительно намного большей длины). Строка текста объявляется в виде массива символов фиксированной длины (можно с помощью операции new[], как в программе 3.6). Чтение строки выполняется из стандартного ввода с помощью функции cin.get() . Память для слова (аргумента командной строки) выделяется системой перед вызовом программы, а указатель строки содержится в элементе argv[1]. Для каждой начальной позиции i в строке a выполняется попытка сравнения подстроки, которая начинается с этой позиции, со словом p. Равенство проверяется символ за символом. При достижении конца слова p выводится начальная позиция i вхождения этого слова в текст.

#include <iostream.h>
#include <string.h>
static const int N = 10000;
int main(int argc, char *argv[])
  { int i; char t;
    char a[N], *p = argv[1];
    for (i = 0; i < N-1; a[i] = t, i++)
      if (!cin.get(t)) break;
    a[i] = 0;
    for (i = 0; a[i] != 0; i++)
      { int j;
        for (j = 0; p[j] != 0; j++)
          if (a[i+j] ! = p[j]) break;
        if (p[j] == 0) cout << i << " ";
      }
    cout << endl;
  }
        

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

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

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

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

while (*a++ = *b++) ;
        

вместо

for (i = 0; a[i] != 0; i++) a[i] = b[i];
        

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

Распределение памяти для строк сложнее, чем для связных списков, поскольку строки имеют различный размер. Вообще-то максимально обобщенный механизм резервирования памяти для строк - это просто системные функции new[] и delete[]. Как было сказано в разделе 3.6, для решения этой задачи разработаны различные алгоритмы. Их характеристики производительности зависят от системы и компьютера. Часто распределение памяти при работе со строками является не такой сложной проблемой, как это может показаться, поскольку используются указатели на строки, а не сами символы. И обычно мы не предполагаем, что все строки занимают конкретно выделенные блоки памяти. Как правило, мы считаем, что каждая строка занимает область памяти с неопределенным адресом, но достаточно большую, чтобы вмещать строку и ее символ завершения. При выполнении операций создания либо удлинения строк следует очень внимательно отнестись к выделению памяти. В качестве примера мы рассмотрим в разделе 3.7 программу, которая читает строки и обрабатывает их.

Упражнения

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

3.56. Напишите программу, которая определяет, является ли данная строка палиндромом (одинаково читается в прямом и обратном направлениях), если игнорировать пробелы. Например, программа должна давать положительный ответ для строки "if i had a hifi".

3.57. Предположим, что память для строк выделяется индивидуально. Напишите версии функций strcpy и strcat, которые выделяют память и возвращают указатель на новую строку-результат.

3.58. Напишите программу, которая принимает строку в качестве аргумента и читает ряд слов (последовательностей символов, разделенных пробелами) из стандартного ввода, выводя те из них, которые входят как подстроки в строку аргумента.

3.59. Напишите программу, которая заменяет в данной строке подстроки, состоящие из нескольких пробелов, одним пробелом.

3.60. Реализуйте версию программы 3.15, в которой будут использоваться указатели.

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

Составные структуры данных

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

Подобно тому, как одномерные массивы соответствуют векторам, двумерные массивы, с двумя индексами, соответствуют матрицам и широко используются в математических расчетах. Например, следующий код можно применить для перемножения матриц a и b с помещением результата в третью матрицу c.

for (i = 0; i < N; i++)
  for (j = 0; j < N; j++)
    c[i][j] = 0.0;
for (i = 0; i < N; i++)
  for (j = 0; j < N; j++)
    for (k = 0; k < N; k++)
      c[i][j] += a[i][k]*b[k][j];
        

Математические расчеты часто естественно выражаются с помощью многомерных массивов.

Помимо математических применений привычный способ структурирования информации состоит в использовании таблиц чисел, организованных в виде строк и столбцов. В таблице оценок можно выделить по одной строке для каждого студента и по одному столбцу для каждого предмета. Такую таблицу можно представить в виде двумерного массива с одним индексом для строк и еще одним - для столбцов. Если студентов 100, а предметов 10, можно объявить массив как grades[100][10], а затем ссылаться на оценку ;-го студента по j-му предмету следующим образом: grade[i][j]. Для вычисления средней оценки по предмету необходимо сложить элементы соответствующего столбца и разделить сумму на количество строк. Чтобы вычислить среднюю оценку определенного студента, нужно сложить элементы строки и разделить сумму на количество столбцов и т.п. Двумерные массивы широко используются в подобных приложениях. В программе часто удобно использовать и более двух измерений. Например, в таблице оценок можно использовать третий индекс для хранения всех оценок за все годы.

Двумерные массивы - это просто удобная запись, поскольку числа хранятся в памяти компьютера, которая, по сути, является одномерным массивом. Во многих языках программирования двумерные массивы хранятся построчно в одномерных массивах. Так, в массиве a[M][N] первые N позиций будут заняты первой строкой (элементы от a[0][0] до a[0][N-1]), следующие N позиций - второй строкой (элементы от a[1][0] до a[1][N-1]) и т.д. При организации хранения в порядке старшинства строк последняя строка кода перемножения матриц из предыдущего абзаца в точности эквивалентна выражению:

c[N*i+j] = a[N*i+k]*b[N*k+j]
        

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

В программе 3.6 был представлен метод динамического выделения памяти массивам, который позволяет использовать программы для задач различных размеров без повторной компиляции. Хотелось бы иметь подобный метод и для многомерных массивов. Как выделять память многомерным массивам, размер которых неизвестен на этапе компиляции? Другими словами, необходима возможность обращаться в программе к элементу массива наподобие a[i][j], но не объявлять массив в виде (например) int a[M][N], поскольку значения Mи N неизвестны. При организации хранения элементов по строкам оператор вида

int* a = malloc(M*N*sizeof(int));
        

выделяет память под массив целых чисел размером MxN, но это решение приемлемо не для всех случаев. Например, если массив передается в функцию, во время компиляции можно не задавать только его первое измерение. В программе 3.16 приведено более эффективное решение для двумерных массивов, основанное на определении "массивов массивов".

Программа 3.17 демонстрирует использование аналогичной составной структуры - массива строк. Поскольку наше абстрактное понятие строки относится к массиву символов, то, на первый взгляд, массивы строк следовало бы представлять в виде массивов массивов. Однако конкретным представлением строки служит указатель на начало массива символов, поэтому массив строк может быть и массивом указателей. Как показано на в частности. Этот пример содержит типичную ситуацию обработки строк: сначала символы считываются в большой одномерный массив, потом расставляются указатели на отдельные строки (ограниченные символами завершения), а затем осуществляется работа с указателями.

Программа 3.16. Выделение памяти под двумерный массив

Эта функция динамически выделяет память двумерному массиву как массиву массивов. Память сначала выделяется для массива указателей, а затем для каждой строки. С помощью этой функции оператор

int **a = malloc2d(M, N);
выделяет память массиву целых чисел размером M х N.
int **malloc2d(int r, int c)
  { int **t = new int*[r];
    for (int i = 0; i < r; i++)
      t[i] = new int[c]; return t;
  }
        

Программа 3.17. Сортировка массива строк

Эта программа иллюстрирует важную функцию обработки строк: расположение набора строк в упорядоченном виде. Строки считываются в буфер достаточного размера, чтобы вместить их все. Для каждой строки в массиве хранится указатель. Затем указатели переупорядочиваются так, чтобы указатель на самую младшую строку находился в первой позиции массива, указатель на следующую в алфавитном порядке строку - во второй позиции и т.д.

Библиотечная функция qsort, которая в действительности выполняет сортировку, принимает четыре аргумента: указатель на начало массива, количество объектов, размер каждого объекта и функцию сравнения. Независимость от типа сортируемых объектов достигается за счет слепого переупорядочения блоков данных, которые представляют объекты (в данном случае, указатели на строки), а также за счет использования функции сравнения, принимающей в качестве аргумента указатели на void. Программа выполняет обратное приведение этих блоков к типу указателей на указатели на символы для функции strcmp. Чтобы обратиться к первому символу строки для операции сравнения, выполняется разыменование трех указателей: один для получения индекса (который является указателем) элемента массива, один для получения указателя строки (с помощью индекса) и еще один для получения символа (с помощью указателя).

Мы будем использовать другой метод достижения независимости от типа для функций сортировки и поиска (см. и ).

#include <iostream.h>
#include <stdlib.h>
#include <string.h>
int compare(const void *i, const void *j)
  { return strcmp(*(char **)i, *(char **)j); }
int main()
  { const int Nmax = 1000;
    const int Mmax = 10000;
    char* a[Nmax]; int N;
    char buf[Mmax]; int M = 0;
    for (N = 0; N < Nmax; N++)
      {
        a[N] = buf[M];
        if (!(cin >> a[N])) break;
        M += strlen(a[N])+1;
      }
    qsort(a, N, sizeof(char*), compare);
    for (int i = 0; i < N; i++)
      cout << a[i] << endl;
  }
        

Нам уже встречалось другое применение массивов строк: массив argv, используемый для передачи строковых аргументов функции main в программах на C++. Система сохраняет в строковом буфере символы командной строки, введенные пользователем, и передает в процедуру main указатель на массив указателей строк в этом буфере. Для определения чисел, соответствующих некоторым аргументам, используются функции преобразования. Остальные аргументы используются непосредственно как строки.

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

(рис 3.12) Сортировка строк

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

(рис 3.13) Мультисписок

С помощью двух полей ссылок узлы можно связывать в два независимых списка: в один список по одному полю, и в другой - по другому. Здесь правое поле связывает узлы в одном порядке (например, в порядке их создания), а левое поле - в другом порядке (в нашем случае это порядок по возрастанию, возможно, в результате сортировки вставками, использующей только левое поле ссылки). Переходя по правым ссылкам от узла a, мы обойдем узлы в порядке их создания. Переходя по левым ссылкам от узла b, мы обойдем узлы в порядке возрастания.

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

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

Чтобы увидеть дополнительные примеры составных структур данных и четко понять различия между индексированными и связными структурами данных, рассмотрим структуры данных для представления графов. Граф (graph) - это фундаментальный комбинаторный объект, который определяется набором объектов (называемых вершинами) и набором связей между вершинами (называемых ребрами). Мы уже встречались с понятием графов в задаче связности из .

Предположим, что граф с количеством вершин V и количеством ребер E описывается набором из E пар целых чисел в диапазоне от , пара i-j обозначает связь между вершинами i и j и имеет то же значение, что и пара j-i. Графы, содержащие такие ребра, называются неориентированными (undirected). Другие типы графов рассматриваются в части 7.

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

(рис 3.14) Представление графа в виде матрицы смежности

Граф представляет собой набор вершин и соединяющих их ребер. Для простоты вершинам присвоены индексы (неотрицательные целые числа по порядку, начиная с нуля). Матрица смежности - это двумерный массив, содержащий бит 1 в строке i и столбце j в том и только том случае, когда между вершинами i и j существует ребро. Этот массив симметричен относительно диагонали. По соглашению все диагональные элементы содержат биты 1 (каждая вершина соединена сама с собой). Например, шестая строка (и шестой столбец) указывает, что вершина 6 соединена с вершинами 0, 4 и 6.

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

Другой простой метод представления графа предусматривает использование массива связанных списков, называемых списками смежности (adjacency lists). Каждой вершине соответствует связный список с узлами для всех вершин, связанных с данной. Для неориентированных графов должно выполняться следующее: если существует узел для вершины показан пример представления неориентированного графа с помощью списков смежности. В программе 3.19 приведен метод создания такого представления для вводимой последовательности ребер.

Программа 3.18. Представление графа в виде матрицы смежности

Эта программа выполняет чтение набора ребер, описывающих неориентированный граф, и создает для него представление в виде матрицы смежности. При этом элементам a[i][j] и a[j][i] присваивается значение 1, если существует ребро из i в j (или из j в j). Иначе эти элементы содержат значение 0. В программе предполагается, что количество вершин V - константа времени компиляции. Иначе пришлось бы динамически выделять память под массив, представляющий матрицу смежности (см. упражнение 3.71).

#include <iostream.h>
int main()
  { int i, j, adj[V][V];
    for (i = 0; i < V; i++)
      for (j = 0; j < V; j++) adj[i][j] = 0;
    for (i = 0; i < V; i++) adj[i][i] = 1;
    while (cin >> i >> j)
      { adj[i][j] = 1; adj[j][i] = 1; }
  }
        

(рис 3.15) Представление графа в виде списков смежности

В этом представлении графа, изображенного на рис 3.14, используется массив списков. Объем необходимой для данных памяти пропорционален сумме количеств вершин и ребер. Для поиска индексов вершин, связанных с данной вершиной i, анализируется i-я позиция массива, содержащая указатель на связный список, который содержит по одному узлу для каждой связанной с i вершины.

Программа 3.19. Представление графа в виде списков смежности

Эта программа считывает набор ребер, которые описывают граф, и создает его представление в виде списков смежности. Список смежности представляет собой массив списков, по одному для каждой вершины, где j-й список содержит связный список узлов, соединенных с j-ой вершиной.

#include <iostream.h>
struct node
  { int v; node* next;
    node(int x, node* t)
      { v = x; next = t; }
  };
  typedef node *link;
  int main()
    { int i, j; link adj[V];
      for (i = 0; i < V; i++) adj[i] = 0;
      while (cin >> i >> j)
        {
          adj[j] = new node(i, adj[j]);
          adj[i] = new node(j, adj[i]);
        }
    }
        

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

Таким образом, представления графа различными методами являются различными компромиссами между расходами памяти и времени. Для матрицы смежности необходим объем памяти, пропорциональный V²; для списков смежности объем памяти пропорционален . Оба типа представлений можно элементарно распространить на другие типы графов (см., например, упражнение 3.70). Они служат основой большинства алгоритмов обработки графов, которые будут рассмотрены в части 7.

В завершение главы рассмотрим пример, демонстрирующий использование составных структур данных для эффективного решения простой геометрической задачи, о которой шла речь в разделе 3.2. Для данного значения d необходимо узнать количество пар из множества N точек внутри единичного квадрата, которые можно соединить отрезком прямой с длиной, меньшей d. В программе 3.20 используется двумерный массив связных списков, что снижает время выполнения по сравнению с программой 3.8 примерно на коэффициент 1/d2 для достаточно больших значений N. Для этого единичный квадрат разбивается на сетку меньших квадратов одинакового размера. Затем для каждого квадрата создается связный список всех точек, попадающих в квадрат. Двумерный массив обеспечивает непосредственный доступ к набору точек, ближайших к данной точке. Связные списки обладают гибкостью, позволяющей хранить все точки без необходимости знать заранее, сколько точек попадает в каждую ячейку сетки.

Объем используемой программой 3.20 памяти пропорционален 1/d2 + N , но время выполнения составляет O(d2 N2) , что существенно лучше грубой реализации из программы 3.8 при небольших значениях d. Например, для N = 106 и она дает почти линейный алгоритм определения возможности соединения отрезками длиной d набора из N случайных точек на плоскости. Это фундаментальная задача из области проектирования сетей и цепей.

Программа 3.20. Двумерный массив списков

Эта программа демонстрирует эффективность правильного выбора структуры данных на примере геометрических вычислений из программы 3.8. Единичный квадрат разбивается на сетку. Создается двумерный массив связных списков, причем каждой ячейке (квадрату) сетки соответствует один список. Размер ячеек достаточно мал, чтобы все точки в пределах расстояния d от каждой данной точки попали в одну ячейку с ней либо в смежные ячейки. Функция malloc2d подобна одноименной функции из программы 3.16, но она создана для объектов типа link, а не int.

#include <math.h>
#include <iostream.h>
#include <stdlib.h>
#include "Point.h"
struct node
  { point p; node *next;
    node(point pt, node* t) { p = pt; next = t; } }; typedef node *link;
    static link **grid;
    static int G, cnt = 0; static float d;
    void gridinsert(float x, float y)
      { int X = x*G+1; int Y = y*G+1;
        point p; p.x = x; p.y = y;
        link s, t = new node(p, grid[X][Y]);
        for (int i = X-1; i <= X+1; i++)
          for (int j = Y-1; j <= Y+1; j++)
for (s = grid[i][j]; s != 0; s = s->next)
  if (distance(s->p, t->p) < d) cnt+ + ;
        grid[X][Y] = t;
      }
      int main(int argc, char *argv[])
        { int i, N = atoi(argv[1]);
          d = atof(argv[2]); G = 1/d;
          grid = malloc2d(G+2, G+2);
          for (i = 0; i < G+2; i++)
for (int j = 0; j < G+2; j++)
  grid[i][j] = 0;
          for (i = 0; i < N; i++)
gridinsert(randFloat(), randFloat());
          cout << cnt << " пар в радиусе " << d << endl;
        }
        

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

Упражнения

3.62. Напишите версию программы 3.16, обрабатывающую трехмерные массивы.

3.63. Измените программу 3.17 для индивидуальной обработки вводимых строк (память выделяется каждой строке после считывания ее из ввода). Можно предположить, что длина любой строки не превышает 100 символов.

3.64. Напишите программу заполнения двумерного массива значениями 0 или 1: элемент a[i][j] должен содержать значение 1, если наибольший общий делитель

i и j равен единице, и значение 0 в остальных случаях.

3.65. Воспользуйтесь программами 3.20 и 1.4 для разработки эффективной программы, которая определяет, можно ли соединить набор из N точек отрезками длиной меньше d.

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

3.67. Реализуйте перемножение матриц, представленных мультисписками.

3.68. Запишите матрицу смежности, построенную программой 3.18, для введенных пар значений: 0-2, 1-4, 2-5, 3-6, 0-4, 6-0 и 1-3.

3.69. Запишите список смежности, построенный программой 3.19, для введенных пар значений: 0-2, 1-4, 2-5, 3-6, 0-4, 6-0 и 1-3.

3.70. Ориентированный (directed) граф - это граф, у которого связи между вершинами имеют направление: ребра следуют из одной вершины в другую. Выполните упражнения 3.68 и 3.69 для случая, когда вводимые пары представляют ориентированный граф, а обозначение i-j указывает, что ребро направлено из i в j. Кроме того, нарисуйте этот граф, используя стрелки для указания ориентации ребер.

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

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

3.73. Напишите функцию, которая использует матрицу смежности графа для подсчета по заданным вершинам а и b количества таких вершин с, что существуют ребра из а в с и из с в b.

3.74. Выполните упражнение 3.73 с использованием списков смежности.