Лекции (1171139), страница 17
Текст из файла (страница 17)
Выходсостоит в том, чтобы захватывать пространство под массив в динамической памяти ужепосле ввода числа n. Вот полный текст программы:#include <stdio.h>#include <stdlib.h>#include <math.h>int main() {int n; // Требуемое количество простых чиселint k; // Текущее количество найденных простых чиселint *a; // Указатель на массив найденных простыхint p; // Очередное проверяемое числоint r; // Целая часть квадратного корня из pint i; // Индекс простого делителяbool prime; // Признак простотыprintf("Введите число простых: ");scanf("%d", &n);if (n <= 0)// Некорректное значение =>return 1; // завершаем работу с кодом ошибки// Захватываем память под массив простых чиселa = (int *) malloc(n * sizeof(int));a[0] = 2; k = 1;// Добавляем двойку в массивprintf("%d ", a[0]); // и печатаем ееp = 3;while (k < n) {// Проверяем число p на простотуr = (int)(// Целая часть корняsqrt((double) p) + 0.001);i = 0;prime = true;while (i < k && a[i] <= r) {if (p % a[i] == 0) { // p делится на a[i]60prime = false;break;// => p не простое,// выходим из цикла}++i; // К следующему простому делителю}if (prime) { // Если нашли простое число,a[k] = p; // то добавляем его в массив++k;// Увеличиваем число простыхprintf("%d ", p); // Печатаем простое числоif (k % 5 == 0) { // Переход на новую строкуprintf("\n"); // после каждых пяти чисел}}p += 2; // К следующему нечетному числу}if (k % 5 != 0) {printf("\n"); // Перевести строку}// Освобождаем динамическую памятьfree(a);return 0;}Пример работы данной программы:Введите число простых: 502 3 5 7 1113 17 19 23 2931 37 41 43 4753 59 61 67 7173 79 83 89 97101 103 107 109 113127 131 137 139 149151 157 163 167 173179 181 191 193 197199 211 223 227 229Операторы new и delete языка C++.В языке C++ для захвата и освобождения динамической памяти используютсяоператоры new и delete.
Они являются частью языка C++, в отличие от функций malloc иfree, входящих в библиотеку стандартных функций Си.Пусть T - некоторый тип языка Си или C++, p - указатель на объект типа T. Тогда длязахвата памяти размером в один элемент типа T используется оператор new:T *p;p = new T;Например, для захвата восьми байтов под вещественное число типа double используетсяфрагментdouble *p;p = new double;При использовании new, в отличие от malloc, не нужно приводить указатель от типа void*к нужному типу: оператор new возвращает указатель на тип, записанный после слова new.Оператор new удобен еще и тем, что можно присвоить начальное значение объекту,созданному в динамической памяти (т.е.
выполнить инициализацию объекта). Для этогоначальное значение записывается в круглых скобках после имени типа, следующего засловом new. Например, в приведенной ниже строке захватывается память подвещественное число, которому присваивается начальное значение 1.5:double *p = new double(1.5);Этот фрагмент эквивалентен фрагментуdouble *p = new double;61*p = 1.5;С помощью оператора new можно захватывать память под массив элементов заданноготипа. Для этого в квадратных скобках указывается длина захватываемого массива, котораяможет представляться любым целочисленным выражением. Например, в следующемфрагменте в динамической памяти захватывается область для хранения вещественнойматрицы размера m*n:double *a;int m = 100, n = 101;a = new double[m * n];Такую форму оператора new иногда называют векторной.Оператор delete освобождает память, захваченную ранее с помощью оператора new,например,double *p = new double(1.5); // Захват и инициализация. .
.delete p; // Освобождение памятиЕсли память под массив была захвачена с помощью векторной формы оператора new, тодля ее освобождения следует использовать векторную форму оператора delete, в которойпосле слова delete записываются пустые квадратные скобки:double *a = new double[100]; // Захватываем массив. .
.delete[] a; // Освобождаем массивЗАДАНИЕМодифицировать программу нахождения простых чисел, приведенную выше, сиспользованием операторов new и delete.Структуры данныхСтруктурыСтруктура — это конструкция, которая позволяет объединить несколькопеременных с разными типами и именами в один составной объект. Она позволяетстроить новые типы данных языкаОписание структуры выглядит следующим образом:struct имя_структуры {описание полей структуры};имя_структуры — это любое имя, соответствующее синтаксису языка;описания полей структуры — любая последовательность описаний переменных, именаи типы этих переменных могут быть произвольными. Эти переменные называются полямиструктуры.Заканчивается описание структуры закрывающей фигурной скобкой. За закрывающейфигурной скобкой в описании структуры обязательно следует точка с запятой, в отличиеот конструкции составного оператора, не следует забывать об этом.Рассмотрим пример: опишем вектор в трехмерном пространстве, который задается тремявещественными координатами x, y, z:struct R3Vector {double x;double y;double z;};Таким образом, вводится новый тип "struct R3Vector"; объект этого типа содержит внутрисебя три вещественных поля с именами x, y, z.
После того как структура определена,можно описывать переменные такого типа, при этом в качестве имени типа следуетиспользовать выражение struct R3Vector. Например, в следующей строке описываются двавещественных вектора в трехмерном пространстве с именами u, v:struct R3Vector u, v;62С объектами типа структура можно работать как с единым целым, например, копироватьэти объекты целиком:struct R3Vector u, v;. . .u = v; // Копируем вектор как единое целоеВ этом примере вектор v копируется в вектор u; копирование структур сводится кпереписыванию области памяти. Сравнивать структуры нельзя:struct R3Vector u, v;.
. .if (u == v) { // Ошибка! Сравнивать структуры нельзя. . .}Имеется также возможность работать с полями структуры. Для этого используетсяоперация точка ".": пусть s — объект типа структура, f — имя поля структуры. Тогдавыражениеs.fявляется полем f структуры s, с ним можно работать как с обычной переменной.Например, в следующем фрагменте в вектор w записывается векторное произведениевекторов u и v трехмерного пространства: w = u × v.struct R3Vector u, v, w;.
. .// Вычисляем векторное произведение w = u * vw.x = u.y * v.z - u.z * v.y;w.y = (-u.x) * v.z + u.z * v.x;w.z = u.x * v.y - u.y * v.x;В приведенных примерах все поля структуры R3Vector имеют один и тот же тип double,однако это совершенно не обязательно. Полями структуры могут быть другие структуры,никаких ограничений нет. Пример: плоскость в трехмерном пространстве задается точкойи вектором нормали, ей соответствует структура R3Plane. Точке трехмерногопространства соответствует структура R3Point, которая определяется аналогично вектору.Полное описание всех трех структур:struct R3Vector { // Вектор трехмерного пространстваdouble x;double y;double z;};struct R3Point { // Точка трехмерного пространстваdouble x;double y;double z;};struct R3Plane { // Плоскость в трехмерном пр-веstruct R3Point origin; // точка в плоскостиstruct R3Vector normal; // нормаль к плоскости};Пусть plane — это объект типа плоскость.
Для того, чтобы получить координату x точкиплоскости, надо два раза применить операцию "точка" доступа к полю структуры:plane.origin.xСтруктуры и указателиУказатели на структуры используются довольно часто. Указатель на структуру Sописывается обычным образом, в качестве имени типа фигурирует struct S*. Например, вследующем фрагменте переменная p описана как указатель на структуру S:struct S { . .
. }; // Определение структуры Sstruct S *p; // Описание указателя на структуру S63Описание структуры может содержать указатель на структуру того же типа в качествеодного из полей. Язык Си допускает использование указателей на структуры, определениекоторых еще не завершено. Например, рассмотрим структуру TreeNode (вершина дерева),которая используется при определении бинарного дерева. Она содержит указатели народительский узел и на левого и правого сыновей, которые также имеют тип structTreeNode:struct TreeNode {struct TreeNodestruct TreeNodestruct TreeNodeint value;};// Вершина дерева*parent; // Указатель на отца,*left;//на левого сына,*right; //на правого сына// Значение в вершинеParentStructvalueRightLeftРис.
3.1 Схема структуры TreeNodeЗдесь при описании полей parent, left, right используется тип указатель на структуруTreeNode, определение которой еще не завершено, что допустимо в языке С++.Для доступа к полям структуры через указатель на структуру служит операциястрелочка, которая обозначается двумя символами −> (минус и знак больше), их нужнорассматривать как одну неразрывную лексему (т.е. единый знак, единое слово). Пусть S —имя структуры, f — некоторое поле структуры S, p — указатель на структуру S. Тогдавыражение p−>f обозначает поле f структуры S (само поле, а не указатель не него!). Этовыражение можно записать, используя операцию звездочка (доступ к объекту черезуказатель), p−>f ~ (*p).f но, конечно, первый способ гораздо нагляднее. (Во второмслучае круглые скобки вокруг выражения *p обязательны, поскольку приоритет операцииточка выше, чем операции звездочка.)Пример: рекурсивный обход дерева:Рис.
3.2 Схема дереваВ качестве примера использования указателей на структуры приведем фрагментпрограммы, вычисляющий количество вершин бинарного дерева. Бинарным деревом64называется связный граф без циклов, у которого одна вершина отмечена как корневая, авсе вершины упорядочены иерархически по длине пути от корня к вершине. У каждойвершины должно быть не больше двух сыновей, причем задан их порядок (левый иправый сыновья).Вершина дерева описывается структурой TreeNode, которая рассматривалась выше.Если у вершины один из сыновей отсутствует, то соответствующий указатель содержитнулевой адрес.Для подсчета числа вершин дерева используем функцию numNodes с прототипомint numNodes(const struct TreeNode *root);Ей передается константный указатель на корневую вершину дерева или поддерева.Функция возвращает суммарное число вершин дерева или поддерева.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
