Практикум ргппу 2017 3 Аннотация
 Скачать 3.14 Mb.
|
|
Тема 6. Алгоритмы работы со структурированными типами данных Наряду с простыми типами, рассмотренными в предыдущих темах, существуют структурированные типы данных, которые могут представлять совокупность значений. Переменные этих типов имеют структуры, которые определяются Виртом как совокупность связанных данных и множество правит, определяющих их организацию и способ доступа к элементам данных. Выбором той или иной структуры данных определяется и алгоритм обработки данных, от которого зависит эффективность их обработки. В языке C++ определены следующие стандартные структурированные типы данных: массив; строка; структура; В данной лабораторной работе будут рассмотрены алгоритмы работы с массивами. Лабораторная работа 6 Стандартные алгоритмы работы с одномерными массивами Теория Массив представляет собой совокупность пронумерованных однотипных значений, имеющих общее имя. Элементы массива обозначаются переменными с индексами. Индексы записывают в квадратных скобках после имени массива. На- пример: t[0], t[5], t[i], h[1][9], h[i][j] и т.п. Массив, хранящий линейную таблицу, называется одномерным. Тип элементов массива называется его базовым типом. Объявление массива: Имя_типа Имя_массива[Объявленный_размер] ; Объявление массива в таком виде задает элементы в количестве Объявленный размер пронумерованные от Имя_массива[0] до Имя_массива[Объявленный_размер - 1]. Значение каждого из них имеет тип Имя_типа. Индексы массивов всегда начинаются с нуля и заканчиваются целым числом, которое на единицу меньше размера массива. Например: int score [6]; Описание массива определяет, во-первых, размещение массива в памяти, во- вторых, правила его дальнейшего употребления в программе. Последовательные элементы массива располагаются в последовательных ячейках памяти (score[0], score[1] и т. д.), причем значения индекса не должны выходить из диапазона 0...5. В 111 качестве индекса может употребляться любое выражение соответствующего типа. Например, score[n+3]. Одной из наиболее часто встречающихся ошибок, допускаемых при написании программ с применением массивов, является попытка обращения к несуществующим элементам используемого массива. Рассмотрим следующее объявление массива: int а[6]; Любое выражение, выступающее в роли индекса массива а, должно давать одно из целых чисел от 0 до 5. Например, если в программе содержатся элементы a[i], то переменная i должна принимать значение, равное одному из шести целых чисел 0, 1, 2, 3, 4 или 5. Если же значение этой переменной будет иным, то это приведет к ошибке. Когда выражение, играющее роль индекса, принимает значение, отличное от допускаемого объявлением массива, говорят, что индекс выходит за пределы массива. К сожалению, в большинстве компиляторов сообщение о выходе за пределы массива не выдается; результатом использования неверного индекса массива будет некорректное поведение программы, возможно, приводящее к ее ава- рийному останову (который может произойти без всякого предупреждающего сообщения). Инициализация массивов Массив тоже можно инициализировать как обычную переменную. При этом значения элементов заключаются в фигурные скобки и отделяются друг от друга запятыми. Например, следующая инструкция инициализирует все три элемента массива children: int children[3]={2, 12, 1}; Приведенное выше объявление эквивалентно следующему коду: int children[3]; children[0]=2; children[1]=12; children[2]=1; Если в фигурных скобках приведено меньше значений, чем имеется элементов массива, то оставшиеся элементы инициализируются нулевым значением базового типа массива. Если массив инициализируется при объявлении, то его размер можно опустить — он автоматически будет равен количеству инициализирующих значений. Например, объявление int b[]={5, 12, 11}; 112 эквивалентно объявлению int b[3]={5, 12, 11}; При описании массива надо точно указать границы его индексов. Изменение размеров массива происходит через изменение в тексте программы и повторную компиляцию. Один из способов сделать программу более гибкой — использовать в ней именованные константы в качестве размеров каждого массива. сonst int N=10; int a[N]; Теперь для изменения размеров массива a и всех операторов программы, связанных с этими размерами, достаточно отредактировать только одну строку в программе — описание константы N. Другой вариант использовать в программе массива с изменяющимся количеством элементов – это зарезервировать место для элементов массива с «запасом». А во время работы программы вводить количество используемых элементов массива. Обработка массивов в программах производится покомпонентно т.е. в цикле. Приведем блок-схему и программу ввода значений в массив: n i=0,n-1,1 a[i] # include # include using namespace std; void main() { int a[20]; int n; cout<< "n=" ; cin>>n; for ( int i=0;i "a[" < ; cin>>a[i]; } } В программе приведен пример ввода элементов массива с комментариями. Результат работы программы: Пример программы ввода массива в строчку: # include # include #include using namespace std; void main() 113 { setlocale(0, "" ); int a[20]; int n; cout<< "введите количество элементов массива" ; cin>>n; cout<< "Введите элементы массива" < int i=0;i } Результат работы программы: Использование массива в качестве аргумента функции В списке формальных параметров функции может быть массив, так что при" ее вызове аргументом, который подставляется вместо этого формального параметра, является весь массив. Однако в этом случае параметр не передается в функцию ни по значению, ни по ссылке. Это новый вид формального параметра, который называется параметр-массив. Рассмотрим пример функции для ввода элементов массива. Это void-функция, которая выполняет последовательность действий: ввод элементов массива в цикле. В данной функции, задан один параметр-массив а, который при вызове этой функции будет заменен массивом-аргументом. В эту функцию передается по значению еще один обычный параметр — n; предполагается, что этот параметр является целым числом, равным размеру массива. Функция заполняет свой параметр-массив (т.е. элементы массива) вводимыми с клавиатуры значениями. Прототип функции: void vvod(int a[], int n); // Предусловие: объявлен массив а с размером n. // Пользователь вводит n целых чисел. // Постусловие: массив а заполнен введенными с клавиатуры // целыми числами в количестве n. Определение функции: void vvod(int a[], int size) {cout<<"Введите "< } Формальный параметр int a [ ] является параметром-массивом. Об этом в C++ свидетельствуют квадратные скобки без каких-либо индексных выражений. Параметр-массив — это не совсем то же самое, что параметр, передаваемый по ссылке, но во многих ситуациях эти два вида параметров ведут себя очень схоже. Разберем подробно приведенный пример, чтобы понять, как же работает аргумент- 114 массив в данном случае. (Аргумент-массив — это, конечно же, массив, который подставляется вместо параметра-массива, такого как а [ ].) В вызове функции vvod должны быть указаны два аргумента: первый является массивом целых чисел, а второй — объявленным размером этого массива. Например, допустим следующий вызов функции: int score[5], num = 5; vvod(score, num); Такой вызов функции vvod заполнит массив score пятью целыми числами, вве- денными с клавиатуры. Обратите внимание, что формальный параметр а [ ] (который используется в прототипе функции и в заголовке ее объявления) содержит квадратные скобки без индексного выражения. (В эти квадратные скобки можно вставить какое-нибудь число, но компилятор его проигнорирует.) Аргумент же, указываемый при вызове функции (в нашем примере это score), не содержит никаких квадратных скобок и индексных выражений. При вызове функции, в качестве аргумента которой используется массив, любое действие, выполняемое с параметром-массивом, выполняется с аргументом- массивом, значения которого могут изменяться функцией. Если формальный параметр изменяется в теле функции (например, с помощью cin-инструкции), то аргумент-массив будет изменен. При использовании массива в качестве аргумента функции передается только адрес первого элемента массива. Базовый тип аргумента-массива должен совпадать с типом формального параметра, поэтому функция уже имеет информацию о базовом типе аргумента. Однако через аргумент-массив в функцию не передаются сведения о размере массива. При выполнении кода функции компьютер знает, с какой ячейки памяти начинается массив и сколько памяти занимает каждый элемент массива, но не знает, сколько элементов содержится в массиве (если не указать ему этого дополнительно). Вот почему важно всегда задавать дополнительный аргумент типа int, в котором содержится информация о размере массива. (В этом и состоит различие между параметром-массивом и параметром, передаваемым по ссылке. Параметр-массив можно представить себе в виде неполноценной разновидности передаваемого по ссылке параметра, когда функция располагает всеми сведениями о массиве, за исключением его размера.) Применение модификатора const При вызове с аргументом-массивом функция может изменять значения, которые хранятся в этом массиве. Обычно это не вызывает проблем. Однако при написании сложного определения функции можно непреднамеренно изменить одну или несколько величин, которые хранятся в массиве, даже если этот массив не должен меняться. Можно указать компилятору, что вы не собираетесь изменять аргумент-массив, и тогда он будет проверять, не выполняется ли в коде изменение значений массива, и сообщать об этом. Для этого перед параметром-массивом нужно вставить модификатор const. Параметр-массив с модификатором const называется константным параметром-массивом (constant array parameter). Например, приведенная ниже функция выводит хранящиеся в массиве значения, но не изменяет их. 115 Прототип функции: void vivod(const int a[], int n) // Предусловие: объявлен массив а с размером n // Всем элементам массива а присвоены значения. // Постусловие: значения массива а выведены на экран. Определение функции: void vivod(const int a[], int n) { cout<<"В массиве содержатся следующие значения:\n"; for (int i=0; i Модификатор const можно применять к параметру любого типа, но обычно он применяется к параметрам-массивам. В дальнейшем ввод и вывод элементов массива будет выполняться в void- функциях. Примеры Пример 1. Вычислить произведение элементов массива. Исходные данные: n элементов вещественного массива a, n – целый тип. Результат: Произведение элементов массива p – целый тип. Тестовый пример:при n=5, элементы массива a=: 1 3 5 3 4, p=180. Пример 2. Найти среднее арифметическое значение элементов массива, не превышающих числа a Ввод n vvod(n,a) p=1 I=0,n-1,1 p=p*p[i] Вывод p Ввод n, a vvod(n,b) s=0 k=0 i=0,n-1,1 b[i]<=a s=s+b[i] k=k+1 sr=s/k Вывод sr да нет 116 Исходные данные: N элементов вещественного массива b. Вещественное число a. Результат: Среднее арифметическое значение sr. Промежуточные значения: i - Индекс элементов массива s - Сумма элементов массива, не превышающих число a. k - Количество элементов массива, не превышающих число a. Тестовый пример: при n=7, a=2, элементы массива b=1 -3 5 4 -4 6 2, sr=-1 Пример 3. Определить, сколько элементов целочисленного массива стоит до первого элемента, значение которого меньше своего индекса. Исходные данные: Целочисленный массив z из n элементов. Результат: i-1 - Количество элементов, стоящих до первого элемента, меньшего своего индекса. Тестовый пример: при n=7, элементы массива z=1 6 15 4 0 6 -1, i-1=4. Пример 4. Найти минимальный элемент и его индекс среди элементов массива с номерами от k до l. Исходные данные: Целочисленный массив d из n элементов k – начало поиска. l – конец поиска. Результаты: im - Номер минимального элемента в заданном наборе элементов. Для минимального элемента дополнительная переменная не нужна, потому что значение минимального элемента – это d[im]. Тестовый пример: при n=7, k=1, l=4 элементы массива d=1 -3 5 4 -4 -6 2, im=4, d[im]=-4. Пример 5. Ввод n,k,l vvod(n, d) im=k i=k,l,1 d[i] Начальное значение индекса минимального элемента Если новый элемент меньше текущего минимального Индекс минимального эдемента изменяется да нет Ввод n vvod(n,z) i=0,n-1,1 z[i] < i Вывод i-1 да нет 117 Определить номер и значение минимального элемента среди положительных элементов массива вещественных чисел Исходн ые данные: Веществ енный массив a из n элементо в. Результ ат: im – Номер минимал ьного элемента Промеж уточные значени я: k – определяет наличие положительного элемента в массиве. k равно нулю пока не встретится положительный элемент. Тестовый пример: при n=10 и элементах: -3, -5, 7, -2, 5, 2, -7, 5,3, 6 im=5, a[5]=2 Пример 6. В целочисленном массиве найти номера двух первых равных элементов. Исходные данные: Целочисленный массив d из n элементов. Результат: k l – Номера первых равных элементов. В данном примере поиск равных элементов лучше вести в процедуре, в этом случае при нахождении равных элементов можно досрочно выйти их процедуры, а значит сразу из двух циклов. Тестовый пример: при n=7, элементы 4, 6, 3, 6, 3, 7, 1, k=1, l=3. Ввод n vvod(n,a) k=0 i=0,n-1,1 a[i]>0 k=0 a[i] k=0 Вывод im, a[im] эл-тов >0 нет Признак первого эл-та >0. да нет да нет да нет да нет Если это первый эл-т >0. индекс первого эл-та >0 Изменение признака первого эл-та >0 A A Ввод n vvod(n,d) k=-1 равных эл-тов нет Вывод k, l да нет да нет ravn(n,d,k,l) k=-1 l=0 i=0,n-2,1 j=i+1,n-1,1 d[i]=d[j] k=i l=j Если равные элементы найдены, досрочный выход из процедуры exit ravn(n,d,k,l) 118 Пример 7. Заменить элементы, имеющие четное значение нулем. Исходные данные: Целочисленный массив a из n элементов. Результат: Целочисленный массив a из n элементов. Тестовый пример: при n=7 введенный массив: 4, 6, 7, 9, 3, 2, 1; преобразованный массив: 0, 0, 7, 9, 3, 0, 1. Пример 8. Переставить местами значения элементов двух массивов, имеющих четные индексы. Исходные данные: Вещественные массивы c и d из n элементов. Результат: Вещественные массивы c и d из n элементов. Тестовый пример: при n=5 введенные массивы: c: 1, 2, 3, 4, 5 d: -1, -2, -3, -4, -5. преобразованные массивы: c: 1, -2, 3, -4, 5 d: -1, 2, -3, 4, -5. Пример 9. Удалить элемент с номером k. Дано: Вещественный массив f из n элементов, k – номер удаляемого элемента. Ввод n vvod(n,a) i=0,n-1,1 a[i] % 2=0 a[i]=0 vivod(n,a) да нет Ввод n vvod(n,c) vvod(n,d) i=0,n-1,1 i % 2=0 switch(c[i],d[i]) vivod(n,c) vivod(n,d) да нет switch(a,b) temp=a a=b b=temp Ввод n,k vvod(n,f) k!=n i=k+1,n-1,1 f[i-1]=f[i] n=n-1 vivod(n,f) да нет 119 Результат: Вещественный массив f из n -1 элементов. При удалении элементы массива сдвигаются влево. Тестовый пример: при n=7 и k=4 ввод: 5, 6, 4, 8, 1, 9, 2 вывод: 5, 6, 4, 1, 9, 2; n=6. Пример 10. Вставить в массив после заданного элемента нуль. Дано: Целочисленный массив x из n элементов, p – номер элемента. Результат: Целочисленный массив x из n+1 элементов. При вставке элементы маccива сдвигаются вправо. Чтобы не потерять элементы, сдвиг выполняется с конца Тестовый пример: n=5, p=3, ввод: 7, 3, 4, 8, 1; вывод: 7, 3, 4, 0, 8, 1. Пример 11. Создать программу, обеспечивающую работу следующих пунктов меню. 1. Ввод массива целых чисел из 20 элементов. 2. Генерация 20 .элементов массива от -100 до 100. 3. Замена в массиве отрицательных элементов нулем. 4. Вывод элементов массива. 5. Конец работы. Исходные данные: Массив a из 20 целых чисел. Ввод n,p vvod(n,x) i=n-1,p,-1 x[i+1]=x[i] x[p]=0 vivod(n,x) n=n+1 120 Печать меню Ввод k k vivod(a,n) replace(a,n) generac(a,n) Такого пункта нет vvod(a,n) true 1 2 3 4 5 иначе break Ввод n k=5 да нет Текст программы: # include # include #include # include # include using namespace std; void vvod( int a[], int n); void generac( int a[], int n); void replace( int a[], int n); void vivod( int a[], int n); void main() {srand(( unsigned )time(NULL)); setlocale(0, "" ); int a[20]; int n,k; cout<< "введите количество элементов массива" ; cin>>n; do {cout<< "1. Ввод массива a" < < < < < ; cin>>k; switch (k) 121 { case 1: vvod(a,n); break ; case 2: generac(a,n); break ; case 3: replace(a,n); break ; case 4: vivod(a,n); break ; case 5: cout<< "Конец работы" < : cout<< "Такого пункта нет" < (k==5) break ; } while ( true ); _getch(); } void vvod( int a[], int n) { cout<< "Введите элементы массива" < int i=0;i } void generac( int a[], int n) { for ( int i=0;i int a[], int n) { for ( int i=0;i } void vivod( int a[], int n) {cout<< "Массив a" < int i=0;i ; cout< |