Операнд_1 ? операнд_2 : операнд_3 7 страница

1. указателям типа void*;

2. если тип указателей справа и слева от операции присваивания один и тот же.

Таким образом, неявное преобразование выполняется только к типу void*. Зна­чение 0 неявно преобразуется к указателю на любой тип. Присваивание указате­лей на объекты указателям на функции (и наоборот) недопустимо. Запрещено и присваивать значения указателям-константам, впрочем, как и константам любо­го типа (присваивать значения указателям на константу и переменным, на кото­рые ссылается указатель-константа, допускается).

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

Инкремент перемещает указатель к следующему элементу массива, декремент - к предыдущему. Фактически значение указателя изменяется на величину sizeof (тип). Если указатель на определенный тип увеличивается или уменьшает­ся на константу, его значение изменяется на величину этой константы, умножен­ную на размер объекта данного типа, например:

short * р = new short [S3;

р++; // значение р увеличивается на 2

long * q = new long [5];

q++; // значение q увеличивается на 4

Разность двух указателей - это разность их значений, деленная на размер типа в байтах (в применении к массивам разность указателей, например, на третий и шестой элементы равна 3). Суммирование двух указателей не допускается.

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

*р++ = 10;

Операции разадресации и инкремента имеют одинаковый приоритет и выполня­ются справа налево, но, поскольку инкремент постфиксный, он выполняется по­сле выполнения операции присваивания. Таким образом, сначала по адресу, за­писанному в указателе р, будет записано значение 10, а затем указатель будет увеличен на количество байт, соответствующее его типу. То же самое можно за­писать подробнее:

*р = 10; р++;

Выражение (*р)++, напротив, инкрементирует значение, на которое ссылается указатель.

Унарная операция получения адреса & применима к величинам, имеющим имя и размещенным в оперативной памяти. Таким образом, нельзя получить адрес ска­лярного выражения, неименованной константы или регистровой переменной. Примеры операции приводились выше.

Динамические массивы. Если до начала работы программы неизвестно, сколько в массиве элементов, в про­грамме следует использовать динамические массивы. Память под них выделяется с помощью операции new или функции mallос в динамической области памяти во время выполнения программы. Адрес начала массива хранится в переменной-указателе.

Обращение к элементу динамического массива осуществляется так же, как и к эле­менту обычного -­­­ например а[3]. Можно обратиться к элементу массива и другим способом - *(а+3). В этом случае мы явно задаем те же действия, что выполня­ются при обращении к элементу массива обычным образом. Рассмотрим их подробнее. В переменной-указателе а хранится адрес начала массива. Для получения адреса третьего элемента к этому адресу прибавляется смещение 3. Операция сло­жения с константой для указателей учитывает размер адресуемых элементов, то есть на самом деле индекс умножается на длину элемента массива: а + 3*sizeof(int). Затем с помощью операции * (разадресации) выполняется выборка значения из указанной области памяти.

Если динамический массив в какой-то момент работы программы перестает быть нужным и мы собираемся впоследствии использовать эту память повторно, необ­ходимо освободить ее с помощью операции delete[], например:

delete[] a;

Размерность массива при этом не указывается.

Таким образом, время жизни динамического массива, как и любой динамической переменной, - с момента выделения памяти до момента ее освобождения. Область действия зависит от места описания указателя, через который производится рабо­та с массивом. Область действия и время жизни указателей подчиняются общим правилам, рассмотренным на первом семинаре. Как вы помните, локальная пере­менная при выходе из блока, в котором она описана, «теряется». Если эта перемен­ная является указателем и в ней хранится адрес выделенной динамической памя­ти, при выходе из блока эта память перестает быть доступной, однако не помечается как свободная, поэтому не может быть использована в дальнейшем. Это называет­ся утечкой памяти и является распространенной ошибкой:

{ // пример утечки памяти

int n;

cin >> n;

int* pmas = new int[n];

…

}

// После выхода из блока указатель pmas недоступен

Пример 5.1. Написать программу, которая для вещественного массива из n элементов определяет сумму его элементов, расположенных правее последнего отрицательного элемента.

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

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

Листинг 5.1

#include "conio.h"

#include "math.h"

#include "windows.h"

#include “stdafx.h”

#include <iostream>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

int n;

setlocale(LC_ALL, "Russian");

cout<<"\nВведите количество элементов: ";

int i, ineg;

float sum, *a = new float[n]; // 1

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

for(i = 0; i < n; i++) cin >> a[i];

for(i = 0; i < n; i++) cout << a[i] << ‘ ‘; // 2

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

if(a[i] < 0) ineg = i; // 3

for(sum = 0., i = ineg + 1; i < n; i++)

sum += a[i]; // 4

cout<<"\nСумма: "<< sum;

delete[] a;

return 0;

}

Поскольку количество элементов заранее не задано, память под массив выделяет­ся в операторе 1 на этапе выполнения программы с помощью операции new. Выде­ляется столько памяти, сколько необходимо для хранения n элементов веществен­ного типа, и адрес начала этого участка заносится в указатель а.

Номер последнего отрицательного элемента массива формируется в переменной ineg. При просмотре массива с помощью оператора 3 в эту переменную последова­тельно записываются номера всех отрицательных элементов массива, таким обра­зом, после выхода из цикла в ней остается номер самого последнего.

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

Теперь перейдем к критическому анализу нашей первой попытки решения задачи. Для массивов, содержащих отрицательные элементы, эта программа работает верно, но при их отсутствии, как правило, завершается аварийно. Это связано с тем, что если в массиве нет ни одного отрицательного эле­мента, переменной ineg значение не присваивается. Поэтому в операторе for (опе­ратор 4) будет использовано значение ineg, инициализированное произвольным образом. Поэтому в программу необходимо внести проверку, есть ли в массиве хотя бы один отрица­тельный элемент. Для этого переменной ineg присваивается начальное значение, не входящее в множество допустимых индексов массива (например, -1). После цикла поиска номера отрицательного элемента выполняется проверка, сохрани­лось ли начальное значение ineg неизменным. Если это так, это означает, что усло­вие a[i]<0 в операторе 3 не выполнилось ни разу, и отрицательных элементов в массиве нет:

Листинг 5.2

#include "stdafx.h"

#include "conio.h"

#include "math.h"

#include "windows.h"

#include <iostream>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(LC_ALL, "Russian");

int n;

cout<<"\nВведите количество элементов: ";

cin >> n;

int i, ineg = -1;

float sum, *a = new float[n]; // 1

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

for(i = 0; i < n; i++) cin >> a[i];

for(i = 0; i < n; i++) cout << a[i] << ‘ ‘; // 2

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

if(a[i] < 0) ineg = i; // 3

if(ineg!= -1)

{

for(sum = 0., i = ineg + 1; i < n; i++)

sum += a[i]; // 4

cout<<"\nСумма: "<< sum;

}

delete[] a;

getch();

return 0;

}

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

Листинг 5.3

#include "stdafx.h"

#include "conio.h"

#include "math.h"

#include "windows.h"

#include <iostream>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

int n;

setlocale(LC_ALL, "Russian");

cout<<"\nВведите количество элементов: ";

cin >> n;

int i, ineg = -1;

float sum, *a = new float[n]; // 1

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

for(i = 0; i < n; i++) cin >> a[i];

bool flag_neg = false;

float sum = 0.f;

for(i = n - 1; i >= 0; i--)

{

if(a[i] < 0)

{

flag_neg = true;

break;

}

sum += a[i];

}

if(flag_neg)

cout<<"\nСумма: "<< sum;

else

cout<<"\nОтрицательных элементов нет ";

getch();

return 0;

}

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

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

Пример 5.2. Написать программу, которая упорядочивает вещественный массив методом бы­строй сортировки.

Идея алгоритма состоит в следующем. Применим к массиву так называемую про­цедуру разделения относительно среднего элемента. Вообще-то, в качестве «сред­него» можно выбрать любой элемент массива, но для наглядности мы будем выбирать по возможности, средний по своему номеру элемент.

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

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

Для хранения границ еще не упорядоченных частей массива более всего подходит структура данных, называемая стеком. Стек является одной из наиболее часто употребляемых структур данных и функционирует по принципу: «первым пришел, последним ушел».

В приведенной ниже программе стек реализуется в виде двух массивов stackr и stackl и одной переменной sp, используемой как «указатель» на вершину стека (она хранит номер последнего заполненного элемента массива). Для этого ал­горитма количество элементов в стеке не может превышать n, поэтому размер мас­сивов задан равным именно этой величине. При занесении в стек переменная sp увеличивается на единицу, а при выборке - уменьшается.

Ниже приведена программа, реализующая этот алгоритм:

Листинг 5.4

#include “stdafx.h”

#include <iostream>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

const int n = 20;

float *arr = new float[n], middle, temp;

int *stackl = new int[n], *stackr = new int[n];

int sp = 0, i, j, left, right;

setlocale(LC_ALL, "Russian");

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

for(i = 0; i < n; i++) cin >> a[i];

// Сортировка

sp = 1; stackl[1] = 0; stackr[1] = n - 1; // 1

while(sp > 0)

{ // 2

// Выборка из стека последнего запроса

left = stackl[sp]; // 3

right = stackr[sp]; // 4

sp--; // 5

while(left < right)

{ // 6

// Разделение {arr[left]..arr[right]}

i = left; j = right; // 7

middle = arr[(left + right)/2]; // 8

while(i < j)

{ // 9

while(arr[i] < middle) i++; // 10

while(middle < arr[j]) j--; // 11

if(i <= j)

{

temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

i++; j--;

}

}

if(i < right)

{ // 12

//Запись в стек запроса из правой части

sp++;

stackl[sp] = i;

stackr[sp] = right;

}

right = j; // 13

// Теперь left и right ограничивают левую часть

}

}

// Вывод результата

for(i = 0; i < n; i++) cout << arr[i] << “ “;

cout << endl;

// Удаление динамических массивов

delete[] arr;

delete[] stackl;

delete[] stackr;

getch();

return 0;

}

На каждом шаге сортируется один фрагмент массива. Левая граница фрагмента хранится в переменной left, правая - в переменной right. Сначала фрагмент уста­навливается размером с массив целиком (строка 1). В операторе 8 выбирается «сред­ний» элемент фрагмента.

Для продвижения по массиву слева направо в цикле 10 используется переменная i, справа налево - переменная j (в цикле 11). Их начальные значения устанавлива­ются в операторе 7. После того, как оба счетчика «сойдутся» где-то в средней части массива, происходит выход из цикла 9 на оператор 12, в котором заносятся в стек границы правой части фрагмента. В операторе 13 устанавливаются новые грани­цы левой части для сортировки на следующем шаге.

Если сортируемый фрагмент уже настолько мал, что сортировать его не требуется, происходит выход из цикла 6, после чего выполняется выборка из стека границ еще не отсортированного фрагмента (операторы 3,4). Если стек пуст, происходит выход из главного цикла 2. Массив отсортирован.

Ссылки. Ссылка представляет собой синоним имени, указанного при инициализации ссылки. Ссылку можно рассматривать как указатель, который всегда разымено­вывается. Формат объявления ссылки:

тип & имя;

где тип - это тип величины, на которую указывает ссылка, & - оператор ссылки, означающий, что следующее за ним имя является именем переменной ссылочного типа, например:

int kol;

int& pal = kol; //ссылка pal-альтернативное имя для kol

const char& CR = "\n"; // ссылка на константу

Запомните следующие правила.

- переменная-ссылка должна явно инициализироваться при ее описании, кро­ме случаев, когда она является параметром функции, описана как extern или ссылается на поле данных класса.

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

- тип ссылки должен совпадать с типом величины, на которую она ссылается.

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

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

Ссылка, в отличие от указателя, не занимает дополнительного пространства в па­мяти и является просто другим именем величины. Операция над ссылкой приво­дит к изменению величины, на которую она ссылается.

Пример 5.3. Составить программу нахождения тех элементов массива С (из n элементов), индексы которых являются степенями двойки (1, 2, 4, 8…). UML-диаграмма этого алгоритма приведена на рисунке 5.1.

Рисунок 5.1 - UML-диаграмма деятельности для примера 5.3

Листинг 5.5

#include "stdafx.h"

#include <iostream>

#include "conio.h"

#include "math.h"

#include "windows.h"

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

setlocale(LC_ALL, "Russian");

const int N = 1000;

int n, i, j, left, right, sp = 0, m = 1;

float *C = new float[N], middle, temp;

int *stackl = new int[N], *stackr = new int[N];

cout<<"\n\nЗадание:\n";

cout<<"\nСоставить программу с использованием динамических массивов\n";

cout<<"\nдля решения задачи на переупорядочивание элементов массива.\n";

cout<<"\nВ качестве алгоритма сортировки использовать метод быстрой сортировки массива.\n";

cout<<"\n\nЗадача: составить программу нахождения тех элементов массива С,\n";

cout<<"\nиндексы которых являются степенями двойки (1, 2, 4,...).\n";

cout<<"\n\nРабота программы:\n"

A:

cout<<"\nВведите количество элементов: ";

cin >> n;

if(n <= 0 || n > N)

{

cout<<"Неверный размер массива"<< "\n";

goto A;

}

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

for(i = 0; i < n; i++) cin >> C[i];

sp = 1;

stackl[1] = 0;

stackr[1] = n - 1;

while(sp > 0)

{

left = stackl[sp];

right = stackr[sp];

sp--;

while(left < right)

{

i = left;

j = right;

middle = C[(left + right)/2];

while(i < j)

{

while(C[i] < middle) i++;

while(middle < C[j]) j--;

if(i <= j)

{

temp = C[i];

C[i] = C[j];

C[j] = temp;

i++;

j--;

}

}

if(i < right)

{

sp++;

stackl[sp] = i;

stackr[sp] = right;

}

right = j;

}

}

cout<<"\nМассив после сортировки:\n\n";

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

{

cout << C[i] << "\n";

}

cout<<"\nМассив из элементов, индексы которых являются степенями двойки:\n\n"<<"\n";

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

{

while (m < n)

{

cout << C[m] << "\n";

m = m * 2;

}

}

delete[] C;

delete[] stackl;

delete[] stackr;

getch();

return 0;

}

Пример 5.4. В массиве {aj}, j = 1, 2, …10 есть положительные и отрицательные элементы. Вычислить произведение отрицательных элементов. UML-диаграмма этого алгоритма приведена на рисунке 5.2.

Рисунок 5.2 - UML-диаграмма деятельности для примера 5.4

Листинг 5.6

// Лабораторная работа №_5_1

#include "stdafx.h"

#include <iostream>

#include "conio.h"

#include "windows.h"

#include <tchar.h>

#include <math.h>

#include <time.h>

#include <iomanip>

using namespace std;

const int n = 1000;

int _tmain(int argc, _TCHAR* argv[])

{

int n;

int RANGE_MIN = 0;

int RANGE_MAX = 20;

setlocale(LC_ALL, "Russian");

cout<< "Лабораторная работа №_5_1" << '\n';

cout<< '\n';

cout<< " В массиве {aj}, j = 1, 2,...10 есть положительные и отрицательные элементы. ";

cout<< '\n';

cout<< " Вычислить произведение отрицательных элементов ";

cout<< '\n'<< '\n'<< '\n';

cout<< "\nВведите резмерность массива ";

cin >> n;

int i = 0, s = 0, klav;

double *arr = new double[n];

double piece = 1;

cout<< '\n';

cout<< " Как будет проидведенно заполнение? ";

cout<< '\n';

cout<<" 1 - случайным образом ";

cout<< '\n';

cout<< " 2 - в ручную ";

cout<< '\n';

cout<<"Для продолжения нажмите клавишу выбора ";

cin >> klav;

cout << '\n';

if (klav == 1)

{

srand((unsigned int)time(NULL));

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

{

int rand100 = (((double) rand() / (double) RAND_MAX) * RANGE_MAX + RANGE_MIN);

arr[i]=rand100-10;

}

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

{

cout << arr[i] << " ";

}

}

if (klav==2)

{

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

{

cout<< "Введите " << i+1;

cout<< " элемент ";

cin >> arr[i];

}

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

{

cout << arr[i] << " ";

}

}

if (klav!= 1 && klav!=2)

{

cout<< "Неправильный выбор";

cout<< " Для выходна нажмите любую клавишу...";

goto stop;

}

cout << '\n';

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

{

if (arr[i] < 0)

{

piece = piece*arr[i];

s++;

}

}

if (s==0)

{

cout<< '\n '<<"В массиве отсутствуют отрицательные элементы";

}

else

{

cout<< '\n' <<" Произведение отрицательных элементов = " << piece;

}

delete []arr;

stop: getch ();

return 0;

}

Аппаратура и материалы. Для выполнения лабораторной работы необходим персональный компьютер со следующими характеристиками: процессор Intel Pentium-совместимый с тактовой частотой 800 МГц и выше, оперативная память - не менее 64 Мбайт, свободное дисковое пространство - не менее 500 Мбайт, устройство для чтения компакт-дисков, монитор типа Super VGA (число цветов от 256) с диагональю не менее 15². Программное обеспечение - операционная система Windows2000/XP и выше, среда разработки приложений Microsoft Visual Studio.

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

Методика и порядок выполнения работы. Перед выполнением лабораторной работы каждый студент получает индивидуальное задание в соответствии с индивидуальным заданием лабораторной работы №4. Защита лабораторной работы происходит только после его выполнения (индивидуального задания). При защите лабораторной работы студент отвечает на контрольные вопросы, приведенные в конце, и поясняет выполненное индивидуальное задание. Ход защиты лабораторной работы контролируется преподавателем.Порядок выполнения работы:

1. Проработать примеры, приведенные в лабораторной работе.

2. Составить программу с использованием динамических массивов для решения задачи. Номер варианта определяется по формуле , где - номер студента по списку преподавателя.

Индивидуальное задание №1. Вариант:

1. Сформировать массив, содержащий 7 элементов, задав элементы с клавиатуры. Определить количество элементов, кратных 3 и индексы последнего такого элемента.

2. В заданном массиве подсчитать число нулевых элементов и вывести а экран их индексы.

3. Сформировать с помощью датчика случайных чисел массив, элементы которого находятся в промежутке от -60 до 60. Подсчитать в нем количество положительных элементов.

4. В заданном одномерном массиве все отрицательные элементы заменить нулями и подсчитать их количество.

5. В массивах U[7], D[7], V[7] содержатся значения утренней, дневной и вечерней температуры соответственно за каждый день недели. Подсчитать среднее значение дневной температуры за каждый день.

6. В массивах А[n], G[n], F[n] содержатся оценки учащихся по алгебре, геометрии и физике соответственно. Определить, по какому предмету лучше успеваемость.

7. Сформировать с помощью датчика случайных чисел массив A[n], элементы которого находятся в промежутке от -60 до 60. Создать массив B[n], каждый элемент которого вычисляется по формуле:

8. В заданном одномерном массиве найти максимальный элемент и поменять его местами с последним элементом массива.

9. Задан массив из N случайных чисел, принадлежащих промежутку [-50, 100]. Найти сумму тех элементов массива, которые больше 15, но меньше 45, а также вычислить количество этих элементов.

10. В массивах U[7], D[7], V[7] содержатся значения утренней, дневной и вечерней температуры соответственно за каждый день недели. Сформировать массив S[7], в котором будут содержаться значения среднедневной температуры. Определить среднее значение температуры за неделю.

Дата добавления: 2015-10-26