Объявление двумерного динамического массива c. Динамический двумерный массив с указателем на указатель

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

с помощью функции malloc , calloc , realloc и free;
посредством оператора new и delete .

Функция malloc резервирует непрерывный блок ячеек памяти для хранения указанного объекта и возвращает указатель на первую ячейку этого блока. Обращение к функции имеет вид:

void *malloc(size);

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

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

void *calloc (nime, size);

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

Функция realloc изменяет размер выделенной ранее памяти. Обращаются к ней так:

char *realloc (void *p, size);

Здесь p - указатель на область памяти, размер которой нужно изменить на size . Если в результате работы функции меняется адрес области памяти, то новый адрес вернется в качестве результата. Если фактическое значение первого параметра NULL , то функция realloc работает также, как и функция malloc , то есть выделяет участок памяти размером size байт.

Для освобождения выделенной памяти используется функция free . Обращаются к ней так:

void free (void *p size);

Здесь p - указатель на участок памяти, ранее выделенный функциями malloc , calloc или realloc .

Операторы new и delete аналогичны функциям malloc и free . New выделяет память, а его единственный аргумент - это выражение, определяющее количество байтов, которые будут зарезервированы. Возвращает оператор указатель на начало выделенного блока памяти. Оператор delete освобождает память, его аргумент - адрес первой ячейки блока, который необходимо освободить.

Динамический массив - массив переменной длины, память под который выделяется в процессе выполнения программы. Выделение памяти осуществляется функциями calloc, malloc или оператором new . Адрес первого элемента выделенного участка памяти хранится в переменной, объявленной как указатель. Например, следующий оператор означает, что описан указатель mas и ему присвоен адрес начала непрерывной области динамической памяти, выделенной с помощью оператора new :

int *mas=new int;

Выделено столько памяти, сколько необходимо для хранения 10 величин типа int.

Фактически, в переменной mas хранится адрес нулевого элемента динамического массива. Следовательно, адрес следующего, первого элемента, в выделенном участке памяти - mas +1, а mas +i является адресом i-го элемента. Обращение к i-му элементу динамического массива можно выполнить, как обычно mas[i], или другим способом *(mas +i ) . Важно следить за тем, чтобы не выйти за границы выделенного участка памяти.

Когда динамический массив (в любой момент работы программы) перестает быть нужным, то память можно освободить с помощью функции free или оператора delete .

Предлагаю рассмотреть несколько задач, закрепляющих данный урок:

Задача 1

Найти сумму вещественных элементов динамического массива.

//Пример использования функции malloc и free #include "stdafx.h" #include using namespace std; int main() { setlocale(LC_ALL,"Rus"); int i, n; float *a; //указатель на float float s; cout<<"\n"; cin>>n; //ввод размерности массива //выделение памяти под массив из n вещественных элементов a=(float *)malloc(n*sizeof(float)); cout<<"Введите массив A \n"; //ввод элементов массива for (i=0; i>*(a+i); } //накапливание суммы элементов массива for (s=0, i=0; i

//Пример использования функции malloc и free

#include "stdafx.h"

#include

using namespace std ;

int main ()

int i , n ;

float * a ; //указатель на float

float s ;

cout << "\n" ; cin >> n ; //ввод размерности массива

//выделение памяти под массив из n вещественных элементов

a = (float * ) malloc (n * sizeof (float ) ) ;

cout << "Введите массив A \n" ;

//ввод элементов массива

for (i = 0 ; i < n ; i ++ )

cin >> * (a + i ) ;

//накапливание суммы элементов массива

for (s = 0 , i = 0 ; i < n ; i ++ )

s += * (a + i ) ;

//вывод значения суммы

cout << "S=" << s << "\n" ;

//освобождение памяти

free (a ) ;

system ("pause" ) ;

return 0 ;

Задача 2

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

//Пример использования операторов new и delete #include "stdafx.h" #include using namespace std; int main() { setlocale(LC_ALL,"Rus"); int i, n; //ввод количества элементов массива cout<<"n="; cin>>n; //выделение памяти int *a=new int[n]; cout<<"Введите элементы массива:\n"; //ввод массива for (i=0; i>a[i]; //вывод заданного массива for (i=0; i

//Пример использования операторов new и delete

#include "stdafx.h"

#include

using namespace std ;

int main ()

setlocale (LC_ALL , "Rus" ) ;

int i , n ;

//ввод количества элементов массива

cout << "n=" ; cin >> n ;

//выделение памяти

int * a = new int [ n ] ;

cout << "Введите элементы массива:\n" ;

//ввод массива

Цель лекции : изучить объявления, выделения и освобождения памяти для одномерных динамических массивов, обращения к элементам, научиться решать задачи с использованием одномерных динамических массивов в языке C++.

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

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

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

Объявление одномерных динамических массивов

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

Синтаксис :

Тип * ИмяМассива;

Тип – тип элементов объявляемого динамического массива . Элементами динамического массива не могут быть функции и элементы типа void .

Например:

int *a; double *d;

В данных примерах a и d являются указателями на начало выделяемого участка памяти. Указатели принимают значение адреса выделяемой области памяти для значений типа int и типа double соответственно.

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

Выделение памяти под одномерный динамический массив

Для того чтобы выделить память под одномерный динамический массив в языке С++ существует 2 способа.

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

Синтаксис :

ИмяМассива = new Тип [ВыражениеТипаКонстанты];

ИмяМассива – идентификатор массива, то есть имя указателя для выделяемого блока памяти .

ВыражениеТипаКонстанты – задает количество элементов ( размерность) массива . Выражение константного типа вычисляется на этапе компиляции.

Например:

int *mas; mas = new int ; /*выделение динамической памяти размером 100*sizeof(int) байтов*/ double *m = new double [n]; /*выделение динамической памяти размером n*sizeof(double) байтов*/ long (*lm); lm = new long ; /*выделение динамической памяти размером 2*4*sizeof(long) байтов*/

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

2) при помощи библиотечной функции malloc (calloc) , которая служит для выделения динамической памяти.

Синтаксис :

ИмяМассива = (Тип *) malloc(N*sizeof(Тип));

ИмяМассива = (Тип *) calloc(N, sizeof(Тип));

ИмяМассива – идентификатор массива, то есть имя указателя для выделяемого блока памяти .

Тип – тип указателя на массив .

N – количество элементов массива.

Например:

float *a; a=(float *)malloc(10*sizeof(float)); // или a=(float *)calloc(10,sizeof(float)); /*выделение динамической памяти размером 10*sizeof(float) байтов*/

Так как функция malloc (calloc) возвращает нетипизированный указатель void * , то необходимо выполнять преобразование полученного

// объявление двумерного динамического массива на 10 элементов:

float **ptrarray = new float* ; // две строки в массиве

for (int count = 0; count < 2; count++)

ptrarray = new float ; // и пять столбцов

// где ptrarray – массив указателей на выделенный участок памяти под массив вещественных чисел типа float

Сначала объявляется указатель второго порядка float **ptrarray, который ссылается на массив указателей float* ,где размер массива равен двум. После чего в циклеforкаждой строке массива объявленного встроке 2 выделяется память под пять элементов. В результате получается двумерный динамический массив ptrarray.Рассмотрим пример высвобождения памяти отводимой под двумерный динамический массив.

// высвобождение памяти отводимой под двумерный динамический массив:

for (int count = 0; count < 2; count++)

delete ptrarray;

// где 2 – количество строк в массиве

#include
#include
#include
void main()
{

int *a; // указатель на массив

system("chcp 1251");

scanf("%d", &n);

scanf("%d", &m);

// Выделение памяти

a = (int*) malloc(n*m*sizeof(int));

// Ввод элементов массива

for(i=0; i

for(j=0; j

printf("a[%d][%d] = ", i, j);

scanf("%d", (a+i*m+j));

// Вывод элементов массива

for(i=0; i

for(j=0; j

printf("%5d ", *(a+i*m+j)); // 5 знакомест под элемент массива

getchar(); getchar();
}

Результат выполнения

Введите количество строк: 3

Введите количество столбцов: 4

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

Функция malloc() – возвращает указатель на первый байт области памяти размером size, которая была выделена из динамически распределяемой области памяти. Если в динамической области памяти не хватает памяти, то возвращается нулевой указатель.

#include
#include
#include
void main()
{

int **a; // указатель на указатель на строку

system("chcp 1251");

printf("Введите количество строк: ");

scanf("%d", &n);

printf("Введите количество столбцов: ");

scanf("%d", &m);

// Выделение памяти под указатели на строки

a = (int**)malloc(n*sizeof(int*));

// Ввод элементов массива

for(i=0; i

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

a[i] = (int*)malloc(m*sizeof(int));

for(j=0; j

printf("a[%d][%d] = ", i, j);

scanf("%d", &a[i][j]);

// Вывод элементов массива

for(i=0; i

for(j=0; j

printf("%5d ", a[i][j]); // 5 знакомест под элемент массива

free(a[i]); // освобождение памяти под строку

getchar(); getchar();
}

Результат выполнения программы аналогичен предыдущему случаю.

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

Указатели.

Указатель – это переменная, значением которой является адрес, по которому располагаются данные. Адрес – это номер ячейки памяти, в которой или с которой располагаются данные.

По типу данных в СИ указатели делятся на:

Типизированный указатель – указатель, содержащий адрес данных определенного типа (системного или пользовательского).

Не типизированный указатель – указатель, содержащий адрес данных неопределенного типа (просто адрес).

Объявление указателя;

Установка указателя;

обращение к значению, расположенному по указателю. Объявление (описание) указателя в языке СИ имеет следующий вид:

Тип *имя [=значение];

Указатель в СИ при объявлении можно инициализировать, указав через знак присвоения соответствующее значение. Данное значение должно быть адресом, записанном в одном из следующих виде:

Нулевое значение (идентификатор NULL);

Другой указатель;

Адрес переменной (через операцию взятия адреса);

Выражение, представляющее собой арифметику указателей;

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

#include

int var; // обычная целочисленная переменная

int *ptrVar; // целочисленный указатель (ptrVar должен быть типа int, так как он будет ссылаться на переменную типа int)

ptrVar = &var; // присвоили указателю адрес ячейки в памяти, где лежит значение переменной var

scanf("%d", &var); // в переменную var положили значение, введенное с клавиатуры

printf("%d\n", *ptrVar); // вывод значения через указатель

Результат выполнения: 6 6

Лекция №3.

Функции.

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

Описание функции на языке СИ осуществляется в любом месте программы вне описания других функций и состоит из трех элементов:

1. прототип функции;

2. заголовок функции;

3. тело функции.

Прототип функции – необязательная часть описания функции, предназначенная для объявления некоторой функции, интерфейс которой соответствует данному прототипу.Объявление прототипа имеет следующий вид:

Тип имя(список типов формальных параметров);

Параметры функции – значения, передаваемые в функцию при ее вызове.

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

Тип имя(список формальных параметров)

Примеры заголовков функций:

Int func(int i, double x, double y)

Void func(int ind, char *string)

Double func(void)

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

Реализация функции на СИ для вычисления факториала числа.

Double factorial(unsigned);

Double factorial(unsigned num)

Double fact = 1.0;

For(unsigned i=1;i<=num;i++)

Fact *= (double)i;

Return fact;

Структуры.

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

Объявление в СИ структуры имеет вид:

Struct [имя типа]

Поле_1;

Поле_2;

Поле_N;

} [список переменных];

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

Файлы.

Файл – это именованная область данных на каком-либо носителе информации. Типы файлов (относительно языка «СИ»):
текстовые;
бинарные.
Основные операции производимые над файлами:
1.Открытие файлов.
2.Чтение и запись данных.
3.Закрытие файлов.

Дополнительные операции:
1.Навигация по файлу.
2.Обработка ошибок работы с файлами.
3.Удаление и переименование файлов.
4.Описание переменной

Режимы открытия файлов с СИ

Перенаправление потоков
FILE * freopen(const char *filename, const char *mode, FILE *stream);

Функция возвращает:
Указатель на файл – все нормально,
NULL – ошибка переопределения.

Закрытие файла
int fclose(FILE *stream);

Функция возвращает:
0 – файл успешно закрыт.
1 – произошла ошибка закрытия файла.

Проверка на достижение конца файла
int feof(FILE *stream);
stream - указатель на открытый файл.

Функция возвращает:
0 – если конец файла еще не достигнут.
!0 – достигнут конец файла.

Открытие текстовых файлов
Во втором параметре дополнительно указывается символ t (необязательно):
rt, wt, at, rt+, wt+, at+

Чтение из текстового файла

Форматированное чтение
int fscanf(FILE *stream, const char * format, ...);

Функция возвращает:
>0 – число успешно прочитанных переменных,
0 – ни одна из переменных не была успешно прочитана,
EOF – ошибка или достигнут конец файла.
Чтение строки

Функция возвращает:
buffer – все нормально,
Чтение строки
char * fgets(char * buffer, int maxlen, FILE *stream);

Функция возвращает:
buffer – все нормально,
NULL – ошибка или достигнут конец файла.
Чтение символа
int fgetc(FILE *stream);
Функция возвращает:
код символа – если все нормально,
EOF – если ошибка или достигнут конец файла.
Помещение символа обратно в поток
int ungetc(int c, FILE *stream);
Функция возвращает:
код символа – если все успешно,
EOF – произошла ошибка.

Запись в текстовый файл в СИ

Форматированный вывод
int fprintf(FILE *stream, const char *format, ...);
Функция возвращает:
число записанных символов – если все нормально,
отрицательное значение – если ошибка.
Запись строки
int fputs(const char *string, FILE *stream);
Функция возвращает:
число записанных символов – все нормально,
EOF – произошла ошибка.
Запись символа
int fputc(int c, FILE *stream);
Функция возвращает:
код записанного символа – все нормально,
EOF – произошла ошибка.
Открытие бинарных файлов
Во втором параметре дополнительно указывается символ b (обязательно):rb, wb, ab, rb+, wb+, ab+
Чтение из бинарных файлов
size_t fread(void *buffer, size_t size, size_t num,FILE *stream);
Функция возвращает количество прочитанных блоков. Если оно меньше num, то произошла ошибка или достигнут
конец файла.

Запись в бинарный файл
size_t fwrite(const void *buffer, size_t size, size_t num, FILE *stream);
Функция возвращает количество записанных блоков. Если оно меньше num, то произошла ошибка.

Навигация по файлу

Чтение текущего смещения в файле:
long int ftell(FILE *stream);
Изменение текущего смещения в файле:
int fseek(FILE *stream, long int offset, int origin);

SEEK_SET (0) – от начала файла.
SEEK_CUR (1) – от текущей позиции.
SEEK_END (2) – от конца файла.
Функция возвращает:
0 – все нормально,
!0 – произошла ошибка.
Перемещение к началу файла:
void rewind(FILE *stream);
Чтение текущей позиции в файле:
int fgetpos(FILE *stream, fpos_t *pos);
Установка текущей позиции в файле:
int fsetpos(FILE *stream, const fpos_t *pos);
Функции возвращают:
0 – все успешно,
!0 – произошла ошибка.
Структура fpos_t:
typedef struct fpos_t {
long off;
mbstate_t wstate;
} fpos_t;

Получение признака ошибки:
int ferror(FILE *stream);
Функция возвращает ненулевое значение, если возникла ошибка.
Функция сброса ошибки:
void clearerr(FILE *stream);
Функция вывода сообщения об ошибке:
void perror(const char *string);

Буферизация

Функция очистки буфера:
int fflush(FILE *stream);
Функция возвращает:
0 – все нормально.
EOF – произошла ошибка.
Функция управления буфером:
void setbuf(FILE *stream, char * buffer);

Создает буфер размером BUFSIZ. Используется до ввода или вывода в поток.

Временные файлы

Функция создания временного файла:
FILE * tmpfile(void);
Создает временный файл в режиме wb+. После закрытия файла, последний автоматически удаляется.
Функция генерации имени временного файла:
char * tmpnam(char *buffer);

Удаление и переименование

Функция удаления файла:
int remove(const char *filename);
Функция переименования файла:
int rename(const char *fname, const char *nname);
Функции возвращают:
0 – в случае успеха,
!0 – в противном случае.

Лекция №4.

Стек.

Стек (stack) является как бы противоположностью очереди, поскольку он работает по принципу "последним пришел - первым вышел" (last-in, first-out, LIFO). Чтобы наглядно представить себе стек, вспомните стопку тарелок. Первая тарелка, стоящая на столе, будет использована последней, а последняя тарелка, положенная наверх - первой. Стеки часто применяются в системном программном обеспечении, включая компиляторы и интерпретаторы.

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

int tos=0; /* вершина стека */

/* Затолкать элемент в стек. */

void push(int i)

if(tos >= MAX) {

printf("Стак полон\n");

/* Получить верхний элемент стека. */

if(tos < 0) {

printf("Стек пуст\n");

return stack;

Переменная tos ("top of stack" - "вершина стека") содержит индекс вершины стека. При реализации данных функций необходимо учитывать случаи, когда стек заполнен или пуст. В нашем случае признаком пустого стека является равенство tos нулю, а признаком переполнения стека - такое увеличение tos, что его значение указывает куда-нибудь за пределы последней ячейки массива.

Пример работы со стеком.

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

/* Простой калькулятор с четырмя действиями. */

#include

int *p; /* указатель на область свободной памяти */

int *tos; /* указатель на вершину стека */

int *bos; /* указатель на дно стека */

void push(int i);

p = (int *) malloc(MAX*sizeof(int)); /* получить память для стека */

printf("Ошибка при выделении памяти\n");

bos = p + MAX-1;

printf("Калькулятор с четырьмя действиями\n");

printf("Нажмите "q" для выхода\n");

printf("%d\n", a+b);

printf("%d\n", b-a);

printf("%d\n", b*a);

printf("Деление на 0.\n");

printf("%d\n", b/a);

case ".": /* показать содержимое вершины стека */

printf("Текущее значение на вершине стека: %d\n", a);

} while(*s != "q");

/* Занесение элемента в стек. */

void push(int i)

if(p > bos) {

printf("Стек полон\n");

/* Получение верхнего элемента из стека. */

if(p < tos) {

printf("Стек пуст\n");

Очередь.

Очередь - это линейный список информации, работа с которой происходит по принципу "первым пришел - первым вышел" (first-in, first-out); этот принцип (и очередь как структура данных) иногда еще называется FIFO. Это значит, что первый помещенный в очередь элемент будет получен из нее первым, второй помещенный элемент будет извлечен вторым и т.д. Это единственный способ работы с очередью; произвольный доступ к отдельным элементам не разрешается.

Чтобы представить себе работу очереди, давайте введем две функции: qstore() и qretrieve() (от "store"- "сохранять", "retrieve" - "получать"). Функция qstore() помещает элемент в конец очереди, а функция qretrieve() удаляет элемент из начала очереди и возвращает его значение. В таблице показано действие последовательности таких операций.


Действие	Содержимое очереди
qstore(A)	A
qstore(B)	А В
qstore(C)	A B C
qretrieve() возвращает А	В С
qstore(D)	B C D
qretrieve() возвращает В	C D
qretrieve() возвращает С	D

Следует иметь в виду, что операция извлечения удаляет элемент из очереди и уничтожает его, если он не хранится где-нибудь в другом месте. Поэтому после извлечения всех элементов очередь будет пуста.

В программировании очереди применяются при решении многих задач. Один из наиболее популярных видов таких задач - симуляция. Очереди также применяются в планировщиках задач операционных систем и при буферизации ввода/вывода.

/* Мини-планировщик событий */

#include

char *p, *qretrieve(void);

void enter(void), qstore(char *q), review(void), delete_ap(void);

for(t=0; t < MAX; ++t) p[t] = NULL; /* иницилизировать массив

пустыми указателями */

printf("Ввести (E), Список (L), Удалить (R), Выход (Q): ");

*s = toupper(*s);

/* Вставка в очередь новой встречи. */

void enter(void)

printf("Введите встречу %d: ", spos+1);

if(*s==0) break; /* запись не была произведена */

p = (char *) malloc(strlen(s)+1);

printf("Не хватает памяти.\n");

if(*s) qstore(p);

/* Просмотр содержимого очереди. */

void review(void)

for(t=rpos; t < spos; ++t)

printf("%d. %s\n", t+1, p[t]);

/* Удаление встречи из очереди. */

void delete_ap(void)

if((p=qretrieve())==NULL) return;

printf("%s\n", p);

/* Вставка встречи. */

void qstore(char *q)

printf("List Full\n");

/* Извлечение встречи. */

char *qretrieve(void)

if(rpos==spos) {

printf("Встречь больше нет.\n");

return p;

Список.

односвязный циклический список это рекурсивное объявление структур, точнее указателя на нее в самой структуре типа:

int data;//поле данных

s *next;//следующий элемент

} *first,*curr;//первый и текущий элемент

Инициализация:

first->next=curr;

чтобы получить первый элемент используй first->data

чтобы добавить новый элемент: curr->next=new s;

curr=curr->next;//переходишь к последнему

и чтобы получить например 50 элемент через цикл перебирай список:

curr=first;//переход к первому

for(int i=0;i<50;i++)

if(curr->next!=NULL)

curr=curr->next;

Похожая информация.

Первый таймер на этом веб-сайте, поэтому здесь идет.

Я новичок на С++, и сейчас я работаю над книгой "Структуры данных, использующие С++ 2nd ed, D.S. Malik".

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

Int *board;

И затем использовать for-loop для создания "столбцов" при использовании массива указателей как "строк".

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

Int **board; board = new int* ;

Мой вопрос таков: какой метод лучше? Метод ** мне легче визуализировать, но первый метод можно использовать почти так же. Оба способа можно использовать для создания динамических 2-мерных массивов.

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

Int row, col; cout << "Enter row size:"; cin >> row; cout << "\ncol:"; cin >> col; int *p_board; for (int i=0; i < row; i++) p_board[i] = new int; for (int i=0; i < row; i++) { for (int j=0; j < col; j++) { p_board[i][j] = j; cout << p_board[i][j] << " "; } cout << endl; } cout << endl << endl; int **p_p_board; p_p_board = new int* ; for (int i=0; i < row; i++) p_p_board[i] = new int; for (int i=0; i < row; i++) { for (int j=0; j < col; j++) { p_p_board[i][j] = j; cout << p_p_board[i][j] << " "; } cout << endl; }

4 ответов

Первый метод нельзя использовать для создания динамических 2D-массивов, потому что:

Int *board;

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

For (int i = 0; i < 4; ++i) { board[i] = new int; }

то, что вы заканчиваете, представляет собой 2D-массив с статическим числом строк (в данном случае 4) и динамическим числом столбцов (в данном случае 10). Таким образом, динамика не полностью , так как при распределении массива в стеке вы должны указывать постоянный размер , т.е. Известный в время . Динамический массив называется динамическим , потому что его размер не обязательно должен быть известен в время компиляции , но скорее может быть определен некоторой переменной в во время выполнения .

Еще раз, когда вы выполните:

Int *board;

Const int x = 4; // <--- `const` qualifier is absolutely needed in this case! int *board[x];

вы предоставляете константу, известную в время компиляции (в данном случае 4 или x), чтобы компилятор теперь мог предварительно выделить эту память для вашего массива, и когда ваша программа будет загружена в память, у нее уже будет этот объем памяти для массива board , поэтому он называется static , т.е. потому что размер жестко закодирован и не могут динамически меняться (во время выполнения).

С другой стороны, когда вы делаете:

Int **board; board = new int*;

Int x = 10; // <--- Notice that it does not have to be `const` anymore! int **board; board = new int*[x];

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

В результате, чтобы действительно создать динамический 2D-массив, вам нужно пойти со вторым методом:

Int **board; board = new int*; // dynamic array (size 10) of pointers to int for (int i = 0; i < 10; ++i) { board[i] = new int; // each i-th pointer is now pointing to dynamic array (size 10) of actual int values }

Мы только что создали квадратный 2D-массив размером 10 на 10. Чтобы пройти его и заполнить его фактическими значениями, например 1, мы могли бы использовать вложенные циклы:

For (int i = 0; i < 10; ++i) { // for each row for (int j = 0; j < 10; ++j) { // for each column board[i][j] = 1; } }

То, что вы описываете для второго метода, дает только 1D-массив:

Int *board = new int;

Это просто выделяет массив с 10 элементами. Возможно, вы имели в виду что-то вроде этого:

Int **board = new int*; for (int i = 0; i < 4; i++) { board[i] = new int; }

В этом случае мы выделяем 4 int* , а затем каждый из них укажем на динамически выделенный массив из 10 int s.

Итак, теперь мы сравниваем это с int* board; . Основное различие заключается в том, что при использовании такого массива количество "строк" должно быть известно во время компиляции. Это потому, что массивы должны иметь фиксированные размеры времени компиляции. У вас может также возникнуть проблема, если вы хотите, возможно, вернуть этот массив из int* s, поскольку массив будет уничтожен в конце его области.

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

For (int i = 0; i < 4; i++) { delete board[i]; } delete board;

Я должен рекомендовать вместо этого использовать стандартный контейнер. Вы можете использовать std::array 4> или, возможно, std::vector> , который вы инициализируете соответствующим размером.

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

Этот вопрос в основном эквивалентен следующему:

Является int* x = new int; "лучше", чем int x ?

Ответ: "нет, если вам не нужно выбирать этот размер массива динамически".

Этот код хорошо работает с очень небольшим количеством требований к внешним библиотекам и показывает базовое использование int **array .

Этот ответ показывает, что массив each имеет динамический размер, а также как назначить линейный массив динамически размера в массив ветвей динамического размера.

Эта программа принимает аргументы из STDIN в следующем формате:

2 2 3 1 5 4 5 1 2 8 9 3 0 1 1 3

Код для программы ниже...

#include int main() { int **array_of_arrays; int num_arrays, num_queries; num_arrays = num_queries = 0; std::cin >> num_arrays >> num_queries; //std::cout << num_arrays << " " << num_queries; //Process the Arrays array_of_arrays = new int*; int size_current_array = 0; for (int i = 0; i < num_arrays; i++) { std::cin >> size_current_array; int *tmp_array = new int; for (int j = 0; j < size_current_array; j++) { int tmp = 0; std::cin >> tmp; tmp_array[j] = tmp; } array_of_arrays[i] = tmp_array; } //Process the Queries int x, y; x = y = 0; for (int q = 0; q < num_queries; q++) { std::cin >> x >> y; //std::cout << "Current x & y: " << x << ", " << y << "\n"; std::cout << array_of_arrays[x][y] << "\n"; } return 0; }

Это очень простая реализация int main и зависит только от std::cin и std::cout . Barebones, но достаточно хорошо, чтобы показать, как работать с простыми многомерными массивами.

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

Указатель в С++ – переменная, которая в себе хранит адрес данных (значения) в памяти, а не сами данные.

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

Допустим, в программе нам необходимо создать целочисленный массив, точный размер которого нам не известен до начала работы программы. То есть мы не знаем какое количество чисел понадобится пользователю внести в этот массив. Конечно, мы можем подстраховаться и объявить массив на несколько тысяч элементов (к примеру на 5 000). Этого (по нашему субъективному мнению) должно хватить пользователю для работы. Да – действительно – этого может быть достаточно. Но не будем забывать, что этот массив займет в оперативной памяти много места (5 000 * 4 (тип int) = 20 000 байт). Мы то подстраховались, а пользователь будет заполнять только 10 элементов нашего массива. Получается, что реально 40 байт в работе, а 19 960 байт напрасно занимают память.

неразумное использование оперативной памяти

#include using namespace std; int main() { setlocale(LC_ALL, "rus"); const int SizeOfArray = 5000; int arrWithDigits = {}; cout << "Массив занял в памяти " << sizeof(arrWithDigits) << " байт" << endl; int amount = 0; cout << "Сколько чисел вы введёте в массив? "; cin >> amount; cout << "Реально необходимо " << amount * sizeof(int) << " байт" << endl; for (int i = 0; i < amount; i++) { cout << i + 1 << "-е число: "; cin >> arrWithDigits[i]; } cout << endl; for (int i = 0; i < amount; i++) { cout << arrWithDigits[i] << " "; } cout << endl; return 0; }

#include

using namespace std ;

int main ()

const int SizeOfArray = 5000 ;

int arrWithDigits [ SizeOfArray ] = { } ;

cout << "Массив занял в памяти " << sizeof (arrWithDigits ) << " байт" << endl ;

int amount = 0 ;

cout << "Сколько чисел вы введёте в массив? " ;

cin >> amount ;

cout << "Реально необходимо " << amount * sizeof (int ) << " байт" << endl ;

for (int i = 0 ; i < amount ; i ++ )

cout << i + 1 << "-е число: " ;

cin >> arrWithDigits [ i ] ;

cout << endl ;

for (int i = 0 ; i < amount ; i ++ )

cout << arrWithDigits [ i ] << " " ;

cout << endl ;

return 0 ;

В стандартную библиотечную функцию sizeof() передаем объявленный массив arrWithDigits строка 10. Она вернёт на место вызова размер в байтах, который занимает этот массив в памяти. На вопрос “Сколько чисел вы введете в массив?” ответим – 10. В строке 15, выражение amount * sizeof(int) станет равнозначным 10 * 4, так как функция sizeof(int) вернет 4 (размер в байтах типа int). Далее введем числа с клавиатуры и программа покажет их на экран. Получается, что остальные 4990 элементов будут хранить нули. Так что нет смысла их показывать.

Главная информация на экране: массив занял 20 000 байт, а реально для него необходимо 40 байт. Как выйти из этой ситуации? Возможно, кому-то захочется переписать программу так, чтобы пользователь с клавиатуры вводил размер массива и уже после ввода значения объявить массив с необходимым количеством элементов. Но это невозможно реализовать без указателей. Как вы помните – размер массива должен быть константой . То есть целочисленная константа должна быть инициализирована до объявления массива и мы не можем запросить её ввод с клавиатуры. Поэкспериментируйте – проверьте.

Тут нам подсвечивает красным оператор >> так как изменять константное значение нельзя.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Тут нас предупреждают о том, что размером массива НЕ может быть значение обычной переменной. Необходимо константное значение!

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

В следующем коде мы будем использовать указатель и новые для вас операторы new (выделяет память) и delete (освобождает память).

разумное использование оперативной памяти, применяя указатели

#include #include using namespace std; int main() { setlocale(LC_ALL, "rus"); int sizeOfArray = 0; // размер массива (введет пользователь) cout << "Чтобы создать массив чисел, введите его размер: "; cin >> sizeOfArray; // ВНИМАНИЕ! int* arrWithDigits - объявление указателя // на участок памяти, которую выделит new int* arrWithDigits = new int ; for (int i = 0; i < sizeOfArray; i++) { arrWithDigits[i] = i + 1; cout << arrWithDigits[i] << " "; } cout << endl; delete arrWithDigits; // освобождение памяти return 0; }

#include

using namespace std ;

int main ()

setlocale (LC_ALL , "rus" ) ;

int sizeOfArray = 0 ; // размер массива (введет пользователь)

cout << "Чтобы создать массив чисел, введите его размер: " ;

cin >> sizeOfArray ;

// ВНИМАНИЕ! int* arrWithDigits - объявление указателя

// на участок памяти, которую выделит new

int * arrWithDigits = new int [ sizeOfArray ] ;

for (int i = 0 ; i < sizeOfArray ; i ++ )

arrWithDigits [ i ] = i + 1 ;

cout << arrWithDigits [ i ] << " " ;

cout << endl ;

delete arrWithDigits ; // освобождение памяти

return 0 ;

Пользователь вводит значение с клавиатуры – строка 12. Ниже определён указатель: int * arrWithDigits Эта запись означает, что arrWithDigits – это указатель. Он создан для хранения адреса ячейки, в которой будет находиться целое число. В нашем случае arrWithDigits будет указывать на ячейку массива с индексом 0. Знак * – тот же что применяется при умножении. По контексту компилятор “поймет”, что это объявление указателя, а не умножение. Далее следует знак = и оператор new , который выделяет участок памяти. Мы помним, что у нас память должна быть выделена под массив, а не под одно число. Запись new int [ sizeOfArray ] можно расшифровать так: new (выдели память) int (для хранения целых чисел) (в количестве sizeOfArray ).

Таким образом в строке 16 был определён динамический массив . Это значит, что память под него выделится (или не выделится) во время работы программы, а не во время компиляции, как это происходит с обычными массивами. То есть выделение памяти зависит от развития программы и решений, которые принимаются непосредственно в её работе. В нашем случае – зависит от того, что введёт пользователь в переменную sizeOfArray

В строке 25 применяется оператор delete . Он освобождает выделенную оператором new память. Так как new выделил память под размещение массива, то и при её освобождении надо дать понять компилятору, что необходимо освободить память массива, а не только его нулевой ячейки, на которую указывает arrWithDigits . Поэтому между delete и именем указателя ставятся квадратные скобки – delete arrWithDigits ; Следует запомнить, что каждый раз, когда выделяется память с помощью new , необходимо эту память освободить используя delete . Конечно, по завершении программы память, занимаемая ей, будет автоматически освобождена. Но пусть для вас станет хорошей привычкой использование операторов new и delete в паре. Ведь в программе могут располагаться 5-6 массивов например. И если вы будете освобождать память, каждый раз, когда она уже не потребуется в дальнейшем в запущенной программе – память будет расходоваться более разумно.

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

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

попытка изменить переменные, переданные в функцию

#include #include using namespace std; void changeData(int varForCh1, int varForCh2); int main() { setlocale(LC_ALL, "rus"); int variableForChange_1 = 0; int variableForChange_2 = 0; cout << "variableForChange_1 = " << variableForChange_1 << endl; cout << "variableForChange_2 = " << variableForChange_2 << endl; cout << endl; changeData(variableForChange_1, variableForChange_2); cout << endl; cout << "variableForChange_1 = " << variableForChange_1 << endl; cout << "variableForChange_2 = " << variableForChange_2 << endl; return 0; } void changeData(int varForCh1, int varForCh2) { cout << "Введите новое значение первой переменной: "; cin >> varForCh1; cout << "Введите новое значение второй переменной: "; cin >> varForCh2; }

#include

using namespace std ;

void changeData (int varForCh1 , int varForCh2 ) ;

int main ()

setlocale (LC_ALL , "rus" ) ;

int variableForChange_1 = 0 ;

int variableForChange_2 = 0 ;

cout << "variableForChange_1 = " << variableForChange_1 << endl ;

cout << "variableForChange_2 = " << variableForChange_2 << endl ;

cout << endl ;

changeData (variableForChange_1 , variableForChange_2 ) ;

cout << endl ;

cout << "variableForChange_1 = " << variableForChange_1 << endl ;

cout << "variableForChange_2 = " << variableForChange_2 << endl ;

return 0 ;

void changeData (int varForCh1 , int varForCh2 )

cout << "Введите новое значение первой переменной: " ;

cin >> varForCh1 ;

cout << "Введите новое значение второй переменной: " ;

cin >> varForCh2 ;

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

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

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

изменение значений переменных, используя указатели

#include #include using namespace std; void changeData(int* varForCh1, int* varForCh2); int main() { setlocale(LC_ALL, "rus"); int variableForChange_1 = 0; int variableForChange_2 = 0; cout << "variableForChange_1 = " << variableForChange_1 << endl; cout << "variableForChange_2 = " << variableForChange_2 << endl; cout << endl; changeData(&variableForChange_1, &variableForChange_2); cout << endl; cout << "variableForChange_1 = " << variableForChange_1 << endl; cout << "variableForChange_2 = " << variableForChange_2 << endl; return 0; } void changeData(int* varForCh1, int* varForCh2) { cout << "Введите новое значение первой переменной: "; cin >> *varForCh1; cout << "Введите новое значение второй переменной: "; cin >> *varForCh2; }