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

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

#include <jnath.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 *lin]c ; static link **grid;

static int G, cnt = 0; static float d; void gridinsert(float x, float y) { int X = x*G+l; int Y = y*G+l; point p; p.x = x; p.у = у; 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++; gridtX][Y] = t;

int main(int argc, char *argv[]) { int i, N = atoi(argv[l]); 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 (randFloatO , randFloatO ) ; cout cnt pairs within d endl;

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

Упражнения

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

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

3.64 Написать программу заполнения двумерного массива значений 0-1 путем установки значения 1 для элемента а[1]Ц], если наибольшее общее кратное i и j равно единице, и установки значения О во всех остальных случаях.

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

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

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

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

t> 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 количества вершин с со свойством наличия ребра от а до с и от с до Ь.

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

Абстрактные типы данных

Разработка абстрактных моделей для данных и способов обработки этих данных является важнейшим компонентом в процессе решения задач с помош.ью компьютера. Примеры этого мы видим на низком уровне в повседневном программировании (когда, например, как обсуждалось в главе 3, мы используем массивы и связные списки) и на высоком уровне при решении прикладных задач (как было продемонстрировано в главе 1, во время использования бора union-fmd при решении задачи связности. В настояш.ей главе рассматриваются абстрактные типы данных (abstract data type, в дальнейшем АТД), позво-ляюш.ие создавать программы с использованием высокоуровневых абстракций. За счет применения абстрактных типов данных появляется возможность отделять абстрактные (концептуальные) преобразования, которые программы выполняют над данными, от любого конкретного представления структуры данных и любой конкретной реализации алгоритма.

Все вычислительные системы базируются на уровнях абстракции: на основе определенных физических свойств кремния и других материалов берется абстрактная модель бита, который может принимать двоичные значения 0-1; затем на основе динамических свойств значений определенного набора битов берется абстрактная модель машины; далее, на основе принципа работы машины под управлением программы на машинном языке берется абстрактная модель языка программирования; и, наконец, берется абстрактное понятие алгоритма, реализуемое в виде программы на языке С++. Абстрактные типы данных обеспечивают возможность продолжать этот процесс дальше и разрабатывать абстрактные конструкции для