Лабораторная работа № 2
Тема: Поняття масиву. Робота зі статичними масивами.
Цель: Использовать особенности реализации массива и возможности работы с указателями.
Литература:
П. Франка С++: Учебный курс.– СПб: Питер Ком, 1999.
И. М. Двоеглазов Язык программирования С++. Справочное руководство. – Киев, 1993.
Теоретические сведения.
Указатель это особый тип, который в принципе представляет из себя адрес в памяти того элемента, на который он указывает. Указатели могут хранить сегмент и смещение, а могут хранить только смещение, но эти различия нас на данном этапе не волнуют.
Смысл использования указателей состоит в том, что отводя место только для запоминания адреса в памяти вы получаете идентификатор ( переменную типа указатель), который может ссылаться на любой элемент в памяти указанного типа, причем в разный момент указатель может указывать на разные элементы, т.е. не надо перемещать в памяти с места на место кучи байтов, достаточно просто изменить указатель.
При объявлении указателя необходимо указать тип элемента, на который будет указывать указатель
Указатель может указывать на любые объекты: переменные, массивы, классы, структуры, и даже на функции. Про объявлении, признаком указателя является символ "*", причем при компиляции объявлений символ "*" имеет меньший приоритет, чем "()" - признак функции, и "[]" - признак массива.
Примеры:
int *r; - указатель на целое число
int* r; - тоже самое
long *g[10]; -массив из 10 указателей на длинное целое
long (*t)[10]; - указатель на массив из десяти длинных целых
Для инициализации указателей используется операция присваивания "=". Указатель можно присваивать значение другого указателя, а можно явно задать присваивание указателю адреса переменной, того типа, на который он указывает. Для этого используют операцию взятия адреса "&":
int r=10;
int *t=&r; - здесь мы явно инициализировали указатель так, чтобы он указывал на переменную. Для того, чтобы можно было использовать то, на что ссылается указатель через его имя используют оператор разадресации - "*", т.е в при объявлении "*" - служит признаком указателя, а при реализации "*" - служит знаком использования данных по адресу, если стоит перед указателем.
Пример:
#include
void main()
{
int a=1, b=2, p;
int *c=&b, *d=c;
p=*d; c=&a; *d=*c;
cout<< a<<' '<< b<<' '<< p<<' '<<*c<<' '<< d<<' '<< "\n";
}
С указателями возможны арифметические операции сложения и разности, например с указателями применимы операции ++ и --, однако при этом к адресу будет добавлены или вычтен не один байт, а столько байт, сколько занимает тип, на который указывает данный указатель, т.е. произойдет смещение на следующий элемент данного типа в памяти, при этом указатель может указывать на место в памяти, которое используется другой переменной и которая может иметь другой тип, но компилятор это не волнует, если вы обращаетесь к этому участку памяти через указатель, то содержимое будет интерпретироваться в соответствии с типом указателя.
Как уже сказано, указатель хранит адрес на блок памяти. Для удобства ввели пустой указатель - NULL. Значение NULL означает, что указатель ни на что не указывает , что позволяет не изменить содержимое памяти в случае ошибки или исключительных ситуациях, а также идентифицировать указатель как не инициализированный или временно не используемый, т.к. в условных операторах ( if, switch, операции сравнения) NULL несет такую же смысловую нагрузку что и 0, т.е. "ложь".
Массивы
Мы уже прекрасно знаем что такое одномерный массив. Теперь рассмотрим двумерный массив. Если одномерный массив можно представить как прямую, где каждому целому числу соответствует какой-то элемент массива, то двумерный массив логически представляет из себя таблицу, т.е. одному числу по одному измерению соответствует целая строка из элементов, и для конкретизации элемента необходимо воспользоваться вторым числом ( задать столбец). По другому двумерный массив можно представить как одномерный массив, элементами которого являются тоже массивы (в принципе так оно и есть - многомерный массив это как бы одномерный массив элементами которого являются массивы, элементами которых тоже могут является массивы).
Объявляются массивы следующим образом :
int mas [10] [30] - здесь объявлен двумерный массив 10 на 30 элементов типа int. Элементы опять же нумеруются с нуля ( т.е. массив имеет индексы [0...9] [0...29]), размерность массива характеризует количество пар квадратных скобок ( в нашем случае их две), ну и имя ( идентификатор) нашего массива: mas.
Обращение к элементу массива производится аналогично случаю с одномерным массивом- путем указания в квадратных скобках индексов требуемого элемента:
mas[1][3]=8;
mas[3][12]=10;
mas[6][3]= mas[3][12]*10;
Пришло время рассмотреть некоторые технические особенности массивов. Начнем с того как массивы располагаются в памяти компьютера. Понятно что ни о каком табличном, трехмерном и (так далее) представлении массивов в памяти не может быть и речи. Память представляет из себя как бы ленту - одну длинную строку, а это значит что любой массив с любым количеством измерений хранится в виде одной строки. Это вполне естественно для одномерного массива: просто в памяти начиная с какого-то адреса размещаются элементы массива. То как в памяти размещаются многомерные массивы становится понятным , если определять многомерный массив как массив из массивов, т.е. в случае двумерного массива вместо нулевого элемента соответствующего одномерного массива записывается одномерный массив соответствующий этому элементу ,т.е. в случае двумерного mas[n][k] c массива сперва в памяти размещается элемент [0][0], затем [0][1],[0][2], ...... ,[0][k-1], [1][0],[1][1],[1][2], ...... ,[1][k-1], ...... ,[n-1][0],[n-1][1],[n-1][2], ...... ,[n-1][k-1]. Как можно заметить индексация начинается с младшего индекса. Трехмерный массив получается из нашего двумерного , элементами которого будут является одномерные массивы, и т.д. для четырех, пяти ,..., х-мерного массива.
У массивов в С++ есть есть особенность - имя массива является указателем на первый элемент массива:
char s[10];
*s='1'; // присвоить первому элементу массива значение '1'
при объявлении многомерного массива, обращение к массиву через его имя , но с меньшим количеством индексов понимается как указатель на массив:
int mas [4][3][1];
тогда mas - указатель на первый элемент массива ( также можно понимать как указатель на весь массив), mas[2][1] - указатель на одномерный массив (явно указывает на первый элемент этого массива), mas[2] - указатель на двумерный массив.
В принципе работа с массивом реализована через указатели, а благодаря индексам осуществляется сдвиг в памяти от того адреса где начинается массив ( именно этот адрес и несет в себе имя массива) на определенное количество байт.
Однако long n=sizeof(mas); вернет размер не указателя, а размер всего массива.
Пришло время снова заняться указателями. Мы изучили массивы, увидели на примере массивов как широко применяются указатели. Сейчас мы значительно расширим сферу применения указателей.
Дело в том, что используемые в программе переменные размещаются в стеке <....> , размер которого ограничен для каждого компилируемого файла, и величина его не превышает 64 килобайта. Память компьютера гораздо больше 64 кб. и значит компьютер способен обрабатывать данные размером много более 64 кб. Для того , что бы иметь доступ к большей памяти используют указатели. Процесс использования памяти вне стека (динамической памяти) состоит в том что бы , сначала, выделить место требуемого размера в памяти , при этом указателю присваивается адрес первого байта выделенной области ( теперь указатель указывает на эту область), а после того как эти данные становятся ненужными необходимо освободить эту память (если этого не сделать то выделенный кусок памяти будет недоступен для любой программы до перезагрузки компьютера - память как бы пропадет).
При работе с динамическими данными есть особенность - выделив память и присвоив соответствующий адрес указателю, при изменении указателя вы можете потерять доступ к памяти (если конечно вы предусмотрительно не присвоили значение первого указателя какому ни будь другому). Собственно потеря доступа будет выражаться только в том что вы не будите знать где начинается нужный вам блок (потеряли указатель), а так вы можете обратится к любому адресу памяти через указатель, присвоив ему соответствующее значение.
Динамическое выделение памяти может понадобится для обработки данных большого размера : изображения, звук, базы данных (если вы их будите писать в ручную), математических, физических, экономических, других задач с большим количеством исходных данных или данных возникающих в процессе вычисления, и многое другое.
Итак самый простой способ выделить динамически память - воспользоваться операцией new. Способ применения: var = new type ;
где var это указатель на элементы тапа type.
Для освобождения памяти, выделенной с помощью new используют операцию delete var; где var указатель указывающий на блок в памяти который необходимо освободить.
Тип следующий сразу за new отвечает за размер памяти выделяемой динамически, поэтому , например создать динамический массив можно следующим образом:
int *mat_ptr = new int[3][10][12];
Другой способ выделения памяти - использование функций malloc и free. Функци malloc выделяет память, но в отличии от new возвращает указатель на void (*void), т.е. необходимо явно приведение типов, и второе отличие - это необходимость в качестве аргумента указывать размер выделяемой области в байтах ( использовать функцию sizeof()) , что дает возможность выделять память под массив длина которого определяется вашей программой (зависит от какой-то переменной), а не заготавливать заранее огромный массив, большая часть которого в большинстве случаев не нужна. Обычный способ применения:
ptr=(*type)malloc(sizeof(type)*n);
где type - тип указателя, а n количество элементов для которых необходимо выделить память (как видите аргументом функции является только размер запрашиваемой области)
Освободить выделенную с помощью malloc() память можно с помощью функции free(ptr), где ptr это указатель на выделенный блок. При одном таком выделении памяти, если вы выделяете память сразу для нескольких элементов, будет выделен непрерывный фрагмент, и поэтому к этим элементам можно обращаться как к элементам массива:
int a=2,d=45,n=23;
mu=(int*) malloc(sizeof(float)*(n+1));
mu[2]=a;
d+=mu[2];
Ход работы.
Задача 1. Реализовать сортировку массива по возрастанию методом обмена.
Задача 2. Реализовать сортировку массива по убыванию методом выбора.
Задача 3. Дан двумерный массив A[1..m, 1..n], все строки которого упорядочены по возрастанию. Составить программу, которая строит одномерный массив В, содержащий все элементы массива А, упорядоченные по неубыванию.
Задача 4. Реализовать сортировку массива по возрастанию методом вставок.