Передача двумерных массивов в функцию
Министерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное
учреждение высшего профессионального образования
Уфимский государственный авиационный технический университет
Кафедра экономической информатики
ИЗУЧЕНИЕ ИНТЕГРИРОВАННОЙ СРЕДЫ BORLAND C++.
РАБОТА С МАССИВАМИ В ФУНКЦИЯХ
МЕТОДИЧЕСКИЕ УКАЗАНИЯ
к лабораторным работам по курсу «Программирование»
Уфа 2012
Составитель: Е.И. Филосова
ББК
УДК 519.682
Методические указания к лабораторным работам по курсу «Программирование» для студентов специальности 080500 «БИЗНЕС ИНФОРМАТИКА» / Уфимский государственный авиационный технический университет; Составитель Е.И. Филосова, Уфа, 2012 - 15с.
В методических указаниях представлена лабораторная работа по изучению раздела «Изучение интегрированной среды Borland C++. Работа с массивами в функциях» дисциплины «Программирование». Представлены примеры, контрольные вопросы и задания для самостоятельной работы. Методические указания могут быть так же использованы в курсовом и дипломном проектировании.
Ил. 1, табл. 0
Рецензенты: доц.
доц.
© Уфимский государственный авиационный технический университет, 2012
Содержание
Цель работы...................................................................................................................... 4
1. Общие положения........................................................................................................ 4
|
|
1.1 Передача массивов в функцию................................................................................. 4
1.2 Передача двумерных массивов в функцию............................................................. 5
1.3 Методы сортировки данных.................................................................................... 6
1.3.1 Пузырьковая сортировка................................................................................... 6
1.3.2. Сортировка вставкой......................................................................................... 7
1.3.3. Сортировка посредством выбора..................................................................... 8
1.4 Поиск в линейных списках....................................................................................... 9
1.4.1. Последовательный поиск.................................................................................. 9
1.4.2. Бинарный поиск............................................................................................... 10
2 Содержание работы.................................................................................................... 10
3 Требования к отчету................................................................................................... 12
4 Контрольные вопросы............................................................................................... 12
Приложение А Задания для самостоятельного выполнения на функции............. 14
Цель работы
Изучить работу с массивами в функциях в языке С++:
· передача одномерных массивов в функцию;
· передача многомерных массивов в функцию;
|
|
· поиск и сортировка при работе с массивами.
Общие положения
Передача массивов в функцию
При передаче массива в функцию всегда происходит передача его адреса. Т.о. в C++ все массивы передаются по адресу.
Пример 1.Даны два массива из n целых чисел каждый. Определить, в каком из них больше положительных элементов.
Очевидно, что для решения этой задачи потребуется подсчитать количество положительных элементов в двух массивах, то есть выполнить для обоих массивов одни и те же действия. Следовательно, эти действия надо поместить в функцию. Интерфейс функции: входные данные — массив и количество его элементов, результат — количество положительных элементов в массиве. Таким образом, заголовок функции должен иметь вид:
int n_posit(const int *a, const int n);
Имя массива представляет собой указатель на его нулевой элемент, поэтому в функцию массивы передаются через указатели. Количество элементов в массиве должно передаваться отдельным параметром, потому что, в отличие от строк символов, использующих признак конца строки, для массивов общего вида никакого признака конца массива не существует.
#include <iostream.h>
#include <conio.h>
int n_posit(const int *a, const int n): // прототип функции
|
|
int main(){
int i, n;
cout << "Введите количество элементов: ";
cin >> n;
int *a = new int[n];
int *b = new int[n];
cout<< "Введите элементы первого массива: ";
for (i = 0; i < n; i++) cin >> a[i];
cout << "Введите элементы второго массива: ";
for (i = 0; i < n; i++) cin >> b[i];
if (n_posit(a, n) > n_posit(b, n))
cout << " В первом положительных больше \n”;
else if(n_posit(a, n) < n_posit(b. n))
cout << " Во втором положительных больше \n ";
else cout << " Одинаковое количество \n ";
getch();
}
//функция, подсчитывающая количество положительных элементов в массиве
int n_posit(const int *a, const int n) {
int count = 0;
for (int i = 0; i < n; i++)
if (a[i] > 0) count++:
return count;
}
В этой программе место под массивы выделяется в динамической области памяти, поскольку в задании не указано конкретное количество элементов. Однако функцию n_posit можно без изменений применять и для «обычных» массивов, потому что для каждого из них имя тоже является указателем на нулевой элемент, только константным. Например, опишем массив из 10 элементов и инициализируем первые шесть из них (оставшимся будут присвоены нулевые значения):
int х[10] = {2, 3, -1, -10, 4, -2};
cout << n_posit(x, 10); // будет выведено значение 3
|
|
Передача двумерных массивов в функцию
Пример 8. Написать программу, определяющую, в какой строке целочисленной матрицы n×m находится самая длинная серия одинаковых элементов.
Под серией имеются в виду элементы, расположенные подряд. В виде функции здесь удобно оформить решение основной задачи, оставив главной программе только ввод исходных данных и вывод результатов. Для удобства отладки ввод массива в программе выполняется случайным образом. Память под массив выделяется в цикле для того, чтобы можно было задавать обе размерности массива в виде переменных.
#include <iostream.h>
#include <conio.h>
int ser_equals(int **a, const int n, const int m);
int RandomMas(int **a, const int n, const int m);
int main() {
int m, n, i , j;
cout << "Vvedite kolichestvo strok: ";
cin >> n;
cout << "Vvedite kolichestvo stolbchov: ";
cin >> m;
int **a = new int *[n]; // выделение памяти
for (i =0; i < n; i++) a[i] = new int [m];
RandomMas(a, n, m); // вызов функции RandomMas для заполнения массива
for (int i = 0; i < n; i++) { // вывод массива на экран
for (int j = 0; j < m; j++)
cout << a[i][j]<<" ";
cout <<"\n";
}
int line = ser_equals(a, n, m); // вызов функции ser_equals для поиска самой длинной
// серии одинаковых элементов
if (line >= 0)
cout << "Samaia dlinnaia seria v stroke " << line+1;
else
cout << "Serii odinakovix elementov net ";
getch();
}
// функция заполнения массива случайным образом
int RandomMas(int **a, const int n, const int m) {
randomize;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
a[i][j] = random(4);
}
// функция поиска самой длинной серии одинаковых элементов
int ser_equals(int **a, const int n, const int m) {
int i, j, count, line = -1, maxcount = 0;
for (i = 0; i < n; i++) {
count =0;
for (j = 0; j < m - 1; j++) {
if (a[i][j] == a[i][j + 1] )
count++;
else {
if (count > maxcount) {
maxcount = count; line = i;
}
count = 0; }
}
if (count > maxcount) {
maxcount = count;
line = i;
}
}
return line;
}
Алгоритм работы функции ser_equals прост: в каждой строке выполняется сравнение соседних элементов. Если они равны, мы находимся внутри серии, при этом увеличиваем ее текущую длину. Она накапливается в переменной count, которая обнуляется перед обработкой каждой строки. Если же элементы не равны, это означает либо окончание серии, либо просто одиночный элемент. В этом случае надо посмотреть, не является ли данная серия самой длинной из рассмотренных и, если да, то запомнить ее длину и номер строки, в которой она встретилась. Для подготовки к анализу следующих серий в этой же строке надо обнулить счетчик count. Аналогичная проверка после цикла просмотра строки выполняется для серии, которая расположена в конце строки, поскольку в этом случае ветвь else выполняться не будет.
Если в массиве нет ни одной серии одинаковых элементов, функция вернет значение, равное -1.
Методы сортировки данных
Пузырьковая сортировка
Задача сортировки заключается в следующем: задан список целых чисел (простейший случай) В=< K1, K2,..., Kn >. Требуется переставить элементы списка В так, чтобы получить упорядоченный список B'=< K'1, K'2,...,K'n >, в котором для любого 1<=i<=n элемент K'(i) <= K'(i+1).
При обменной сортировке упорядоченный список В' получается из В систематическим обменом пары рядом стоящих элементов, не отвечающих требуемому порядку, пока такие пары существуют.
Наиболее простой метод систематического обмена соседних элементов с неправильным порядком при просмотре всего списка слева на право определяет пузырьковую сортировку: максимальные элементы как бы всплывают в конце списка.
Пример:
B=<20,-5,10,8,7>, исходный список;
B1=<-5,10,8,7,20>, первый просмотр;
B2=<-5,8,7,10,20>, второй просмотр;
B3=<-5,7,8,10,20>, третий просмотр.
В последующих примерах будем считать, что сортируется одномерный массив в порядке возрастания элементов.
Нижеприведенная функция bubble сортирует входной массив методом пузырьковой сортировки.
/* сортировка пузырьковым методом */
float * bubble(float * a, int n)
{
char is=1;
int i;
float c;
while(is) {
is=0;
for (i=1; i<n; i++)
if ( a[i]<a[i-1] ) {
c=a[i];
a[i]=a[i-1];
a[i-1]=c;
is=1;
}
}
return(a);
}
Сортировка вставкой
Упорядоченный массив B' получается из В следующим образом: сначала он состоит из единственного элемента К1; далее для i=2,...,N выполняется вставка узла Кi в B' так, что B' остается упорядоченным списком длины i.
Например, для начального списка B=< 20,-5,10,8,7 > имеем:
B=< 20,-5,10,8,7> B'=< >
B=< -5,10,8,7 > B'=< 20 >
B=< 10,8,7 > B'=< -5,20 >
B=< 8,7 > B'=< -5,10,20 >
B=< 7 > B'=< -5,8,10,20 >
B=< > B'=< -5,7,8,10,20 >
Функция insert реализует сортировку вставкой.
/* сортировка методом вставки */
float *insert(float *s, int n) {
int i,j,k;
float aux;
for (i=0; i<n; i++){
aux=s[i];
for (k=0; k<=i && s[k]<aux; k++);
for (j=i-1; j>=k; j--) s[j+1]=s[j];
s[k]=aux;
}
return(a);
}
Здесь оба списка В и В' размещаются в массиве s, причем список В занимает часть s c индексами от i до n, а B' - часть s c индексами от m до i-1 (см. рис.1).
Рис.1. Схема движения индексов при сортировке вставкой.
Дата добавления: 2018-05-13; просмотров: 350; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!