Сортировка посредством выбора

РАБОТА С МАССИВАМИ В ФУНКЦИЯХ

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

к лабораторным работам по курсу «Программирование»

Уфа 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. Схема движения индексов при сортировке вставкой.

Сортировка посредством выбора

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

Например:

B=<20,10,8,-5,7>, B'=< >

B=<20,10,8,7>, B'=<-5>

B=<20,10,8>, B'=<-5,7>

B=<20,10>, B'=<-5,7,8>

B=<20>, B'=<-5,7,8,10>

B=< >, B'=<-5,7,8,10,20> .

Функция selekt упорядочивает массив s сортировкой посредством выбора.

/* сортировка методом выбора */

double *select( double *s, int n){

int i,j;

double c;

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

for (j=i+1;j<n;j++)

  if (s[i]>s[j]){

        c=s[i];

        s[i]=s[j];

        s[j]=c;

  }

return(s);

}

Здесь, как и в предыдущем примере оба списка В и В' размещаются в разных частях массива s (см. рис.2).

Рис.2. Схема движения индексов при сортировке выбором.

Поиск в линейных списках

Последовательный поиск

Задача поиска. Пусть заданы линейные списки: список элементов В=<К1,К2,К3,...,Кn> и список ключей V=<V1,V2,...,Vm> (в простейшем случае это целые числа).Требуется для каждого значения Vi из V найти множество всех совпадающих с ним элементов из В. Чаще всего встречается ситуация когда V содержит один элемент, а в В имеется не более одного такого элемента.

Эффективность некоторого алгоритма поиска А оценивается максимальным Max{А} и средним Avg{А} количествами сравнений, необходимых для нахождения элемента V в В. Если Pi - относительная частота использования элемента Кi в В , а Si - количество сравнений, необходимое для его поиска, то

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

Очевидно, что Max последовательного поиска равен N. Если частота использования каждого элемента списка одинакова, т.е. P=1/N, то Avg последовательного поиска равно N/2. При различной частоте использования элементов Avg можно улучшить, если поместить часто встречаемые элементы в начало списка.

Пусть во входном потоке задано 100 целых чисел К1,К2,... К100 и ключ V. Составим программу для последовательного хранения элементов Кi и поиска среди них элемента, равного V, причем такого элемента может и не быть в списке. Без использования стоппера программа может быть реализована следующим образом:

/* последовательный поиск без стоппера */

#include <iostream.h>

main() {

int k[100],v,i;

cout>>”Введите элементы массива”;

for (i=0;i<100;i++) cin>>k[i];

cout<<”Введите значение для поиска”;

  cin>>v;

i=0;

while(k[i]!=v && i<100) i++;

if (k[i]==v) cout<<v<<i;

else cout<<"не найден"<<v;

}

С использованием стоппера программу можно записать в виде:

/* последовательный поиск со стоппером */

#include <iostream.h>

main() {

int k[100],v,i;

cout>>”Введите элементы массива”;

for (i=0;i<100;i++) cin>>k[i];

cout<<”Введите значение для поиска”;

cin>>v;

k[100]=v;                       /* стоппер */  

  i=0;

while(k[i]!=v) i++;

if (i<100) cout<<v<<i;

else cout<<"не найден"<<v;

}

Бинарный поиск

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

Нахождение элемента бинарным поиском осуществляется очень быстро. Max бинарного поиска равен log₂(N), и при одинаковой частоте использования каждого элемента Avg бинарного поиска равен log₂(N). Недостаток бинарного поиска заключается в необходимости последовательного хранения списка, что усложняет операции добавления и исключения элементов.

Пусть, например, во входном потоке задано 101 число, К1,К2,...,К100, V - элементы списка и ключ. Известно, что список упорядочен по возрастанию, и элемент V в списке имеется. Составим программу для ввода данных и осуществления бинарного поиска ключа V в списке К1,К2,...,К100.

/* Бинарный поиск */

#include <iostream.h>

main() {

int k[100], v, i, j ,m;

cout>>”Введите элементы массива”;

for (i=0;i<100;i++) cin>>k[i];

cout<<”Введите значение для поиска”;

cin>>v;

i=0; j=100; m=50;

while (k[m]!=v) {

if (k[m]<v) i+=m;

else j=m-i;

m=(i+j)/2;

}

cout<<v<<m;

}

Содержание работы

2. 1.     Определить массив, элементы которого будут упорядочиваться. Тип массива выбрать по таблице №1.

Разработать функцию сортировки массива методом, выбранным по таблице 2 в соответствии с вариантом. Любым способом заполнить элементы массива значениями. Выполнить сортировку массива с помощью заданного алгоритма и проконтролировать ее результат. Сделать выводы.

Сохранить файл с тестом программы для последующих работ.

Таблица 1

Таблица 2

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

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

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

randomize - инициализирует генератор случайных чисел;

random (int num); - генератор случайных чисел.

Например, для заполнения матрицы случайными числами от -20 до 20 можно создать следующую функцию:

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] = -20+random(41);

}

2.4 Сохранить все результаты в файлы и оформить отчет.

Требования к отчету

Отчет по работе должен содержать:

· название, цель, задачи работы;

· номер и условие своего варианта;

· текст (листинг) программ;

· полученные численные результаты;

· ответы на контрольные вопросы по указанию преподавателя.

Контрольные вопросы

1. При передачи массивов в функции используется передача по...?

2. Что такое «сортировка»? Сколько существует групп алгоритмов сортировки?

3. Сколько существует алгоритмов сортировки?

4. По каким признакам характеризуются алгоритмы сортировки?

5. Что нужно учитывать при выборе алгоритма сортировки?

6. Какой алгоритм сортировки считается самым простым?

7. Какой алгоритм сортировки считается самым эффективным?

8. Что означает понятие «скорость сортировки»?

9. В чем заключается метод пузырьковой сортировки?

10. В чем заключается метод сортировки посредством выбора?

11. В чем заключается метод сортировки вставками?

12. В чем заключается метод сортировки слиянием?

13. В чем заключается метод быстрой сортировки?

14. Что такое поиск?

15. Что называется ключом поиска?

16. Какие известны методы поиска?

17. Какой алгоритм поиска является наиболее эффективным?

18. Какое требование предъявляется к структуре данных, в которой выполняется бинарный поиск?

21. В чем заключается метод линейного поиска?

22. В чем заключается метод бинарного поиска?

Приложение А