Первый таймер на этом веб-сайте, поэтому здесь идет.
Я новичок на С++, и сейчас я работаю над книгой "Структуры данных, использующие С++ 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
В обоих случаях ваше внутреннее измерение может быть динамически задано (т.е. взято из переменной), но разница во внешнем измерении.
Этот вопрос в основном эквивалентен следующему:
Является 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 и зависит только от std::cin и std::cout . Barebones, но достаточно хорошо, чтобы показать, как работать с простыми многомерными массивами.
Собирая информацию для написания этой статьи, вспомнилось мне моё первое знакомство с указателями – грусть-печаль была… Поэтому после прочтения нескольких разделов по этой теме из разных книг о программировании на C++, было решено пойти иным путем и изложить тему Указатели C++ в той последовательности, в которой я считаю нужным. Сразу дам вам короткое определение и будем рассматривать указатели в работе – на примерах. В следующей статье () будут изложены нюансы, применение указателей со строками в стиле Си (символьными массивами) и основное, что следует запомнить.
Указатель в С++ – переменная, которая в себе хранит адрес данных (значения) в памяти, а не сами данные.
Рассмотрев следующие примеры, вы поймете главное – зачем нам нужны в программировании указатели, как их объявлять и применять.
Допустим, в программе нам необходимо создать целочисленный массив, точный размер которого нам не известен до начала работы программы. То есть мы не знаем какое количество чисел понадобится пользователю внести в этот массив. Конечно, мы можем подстраховаться и объявить массив на несколько тысяч элементов (к примеру на 5 000). Этого (по нашему субъективному мнению) должно хватить пользователю для работы. Да – действительно – этого может быть достаточно. Но не будем забывать, что этот массив займет в оперативной памяти много места (5 000 * 4 (тип int) = 20 000 байт). Мы то подстраховались, а пользователь будет заполнять только 10 элементов нашего массива. Получается, что реально 40 байт в работе, а 19 960 байт напрасно занимают память.
неразумное использование оперативной памяти
#include
#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 #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 #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
// объявление двумерного динамического массива на 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 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; } [список переменных]; Объявление полей структуры возможно только без инициализации. Если несколько полей следующих друг за другом в описании структуры имеют один и тот же тип, то для их описания можно использовать синтаксис объявления нескольких переменных одного и того же типа. Файлы.
Файл – это именованная область данных на каком-либо носителе информации. Типы файлов (относительно языка «СИ»): Дополнительные операции: Режимы открытия файлов с СИ
Перенаправление потоков Функция возвращает: Закрытие файла Функция возвращает: Проверка на достижение конца файла Функция возвращает: Открытие текстовых файлов Чтение из текстового файла Форматированное чтение Функция возвращает: Функция возвращает: Функция возвращает: Запись в текстовый файл в СИ
Форматированный вывод Запись в бинарный файл Навигация по файлу Чтение текущего смещения в файле: SEEK_SET (0) – от начала файла. Получение признака ошибки: Буферизация Функция очистки буфера: Создает буфер размером BUFSIZ. Используется до ввода или вывода в поток. Временные файлы Функция создания временного файла: Удаление и переименование Функция удаления файла: Лекция №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 #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() удаляет элемент из начала очереди и возвращает его значение. В таблице показано действие последовательности таких операций. Следует иметь в виду, что операция извлечения удаляет элемент из очереди и уничтожает его, если он не хранится где-нибудь в другом месте. Поэтому после извлечения всех элементов очередь будет пуста. В программировании очереди применяются при решении многих задач. Один из наиболее популярных видов таких задач - симуляция. Очереди также применяются в планировщиках задач операционных систем и при буферизации ввода/вывода. /* Мини-планировщик событий */ #include #include #include #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; Похожая информация. Цель лекции
: изучить объявления, выделения и освобождения памяти для одномерных динамических массивов, обращения к элементам, научиться решать задачи с использованием одномерных динамических массивов в языке 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 *
, то необходимо выполнять преобразование полученного Обычно, объем памяти, необходимый для той или иной переменной, задается еще до процесса компиляции посредством объявления этой переменной. Если же возникает необходимость в создание переменной, размер которой неизвестен заранее, то используют динамическую память. Резервирование
и освобождение
памяти в программах на C++ может происходить в любой момент времени. Осуществляются операции распределения
памяти двумя способами: Функция 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
. Предлагаю рассмотреть несколько задач, закрепляющих данный урок: Найти сумму вещественных элементов динамического массива. //Пример использования функции malloc и free
#include "stdafx.h"
#include //Пример использования функции 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
;
Изменить динамический массив целых чисел таким образом, чтобы его положительные элементы стали отрицательными и наоборот. Для решения задачи мы будем умножать каждый элемент на -1. //Пример использования операторов new и delete
#include "stdafx.h"
#include //Пример использования операторов 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"
;
//ввод массива
}
- выделить блок оперативной памяти под массив указателей;
- выделить блоки оперативной памяти под одномерные массивы, представляющие собой строки искомой матрицы;
- записать адреса строк в массив указателей.
#include
#include
void main()
{
}
текстовые;
бинарные.
Основные операции производимые над файлами:
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_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);
FILE * tmpfile(void);
Создает временный файл в режиме wb+. После закрытия файла, последний автоматически удаляется.
Функция генерации имени временного файла:
char * tmpnam(char *buffer);
int remove(const char *filename);
Функция переименования файла:
int rename(const char *fname, const char *nname);
Функции возвращают:
0 – в случае успеха,
!0 – в противном случае.
Действие
Содержимое очереди
qstore(A)
A
qstore(B)
А В
qstore(C)
A B C
qretrieve() возвращает А
В С
qstore(D)
B C D
qretrieve() возвращает В
C D
qretrieve() возвращает С
D
Объявление одномерных динамических массивов
Выделение памяти под одномерный динамический массив
Задача 1
Задача 2