Задание 7. Сортировка массива
Сортировку следует понимать как процесс перегруппировки заданного множества объектов в некотором определенном порядке. Основное требование к методам сортировки – экономное использование времени процессора и памяти. Существующие методы сортировки обычно разбивают на три класса в зависимости от лежащего в их основе приема: сортировка выбором, сортировка обменом, сортировка вставками.
Пример.Реализовать пузырьковую сортировку случайным образом генерируемого массива.Пузырьковая сортировка: массив просматривается от начала до конца. Сравниваются i-тое и (i+1)-ое числа. Если i-тое число больше (сортировка по возрастанию), то они меняются местами. Массив просматривается до тех пор, пока от начала до конца массива не сделано ни одной перестановки соседних чисел.
#include <iostream.h>
#include <stdlib.h>
#include <time.h>
void main ()
{
int a[100],n,b;
bool f;
cout<<"Enter n<100 ";
cin >>n;
cout<<"\nArray:\n";
randomize();
for (int i=0;i<n;i++) //Генерируем массив случайных чисел в
//диапазоне [0..50] и выводим на экран
{
a[i]= random(51);
cout <<a[i]<<" ";
}
cout<<"\nSotr:\n";
do
{
f=false;
for(int i=0;i<n-1;i++)// Просматриваем весь массив
if (a[i]>a[i+1])
{
b=a[i];
a[i]=a[i+1];
a[i+1]=b;
f=true; //Был обмен
}
}
while (f); // Проверяем, был ли хоть один обмен
for (int i=0;i<n;i++) // Выводим на экран отсортированный
//массив
cout<<a[i]<<" ";
}
Отсортировать случайным образом генерируемый массив, используя следующие алгоритмы.
1. Усовершенствованная пузырьковая сортировка. Используется принцип пузырьковой сортировки, но массив просматривается не от начала до конца, а от начала до последнего перемещенного элемента (после которого все элементы уже упорядочены). Вначале этим «последним» элементом выбирается последний элемент массива.
2. Простой выбор.Выбрать наибольший элемент массива и поменять его местами с последним (n-ным) элементом массива. Затем из n-1 первых элементов опять выбрать наибольший и опять поменять его местами с (n-1)-м. И так далее, пока весь массив не будет упорядочен.
3. Простые вставки. Так обычно сортируют карты: из веера карт берут одну, стоящую не по старшинству и помещают между двумя уже упорядоченными картами. Массив просматривают с начала до конца. Рассматривается i-тый элемент массива и вставляется на нужную позицию в ряду первых (i-1) уже упорядоченных элементов. (Первоначально “упорядочен” только первый элемент массива). Если i-тый элемент перемещается в j-тую позицию, то все элементы с j-того по (i-1)-ый элемент должны быть сдвинуты на одну позицию вправо.
4. Метод подсчета. Если для какого-то элемента массива известно, что если он больше, чем i других элементов этого массива, то он должен стоять на (i+1)-ом месте после упорядочивания. Для каждого i-го элемента массивасчитают, сколько чисел меньше его, и результат заносят в массив индексов с[i]. Это делается следующим образом. Сравнивают попарно все элементы массива: i-тый и j-тый. (Одна пара чисел может сравниваться только один раз.) Если i-тый больше, то с[i] увеличивают на единицу, иначе c[j] увеличивают на единицу. После формирования массива индексов с, формируют результирующий массив.
5. Метод распределяющего подсчета. Используется, если в массиве много одинаковых элементов. Создается массив индексов d[i]. Размерность массива – число различных между собой элементов исходного массива. Затем в элемент массива d[i] заносят количество элементов массива, равных i, и в результирующий массив записывают по d[i] элементов i-того типа. Например, исходный массив 0010101031; d[0]=5, d[1]=4, d[2]=0, d[3]=1. Результирующий массив 0000011113.
Функции
Функция - это именованная часть программы, к которой можно обращаться из других частей программы столько раз, сколько потребуется. Программа на языке С++ - это совокупность функций, каждая из которых должна быть описана до ее использования. Определение функции имеет следующий формат:
тип_функции имя_функции (спецификация_формальных_параметров)
тело_функции
Здесь тип_функции – тип возвращаемого функцией значения, в том числе void, если функция не возвращает никакого значения. Тип функции может быть любым кроме массива и функции. Имя_функции – идентификатор. Спецификация_формальных_параметров может отсутствовать (но скобки обязательны) или представлять собой список спецификаций для каждого параметра, имеющий вид:
тип имя_параметра
или
тип имя_параметра= умалчиваемое значение.
Тело_функции - это блок или составной оператор, заключенный в скобки {}. Очень важным оператором тела функции является оператор возврата в точку вызова
returnвыражение;
или
return;.
Выражение в операторе return определяет возвращаемое функцией значение, именно то значение, которое будет результатом обращения к функции. Если функция имеет тип void, то этот оператор можно опустить.
Обращение к функции (вызов функции ) – это выражение вида
имя_функции (список_фактических_параметров)
При обращении к функции формальные параметры заменяются фактическими, причем соблюдается строгое соответствие параметров по типам. Именно поэтому необходимо определить или хотя бы объявить функцию до ее вызова. Объявление функции (прототип) совпадает с заголовком определения функции после которого ставится ;. В списке формальных параметров в этом случае могут отсутствовать имена параметров.
Приведем несколько примеров.
Пример 1. Составить функции для нахождения максимума двух целых чисел, куба целого числа. Найти куб максимального из двух чисел и вывести на экран, используя данные функции.
# include <iostream.h>
int max (int n, int m ) // определение функции нахождения максимума
{return n<m?m:n;}
int cube(int); //прототип функции вычисления куба целого числа
void main (void)
{
int i,j,m;
cin >>i>>j;
m=cube(max(i,j));// вложенные вызовы функций – m – куб
// максимального из двух чисел
cout<<“\nmax=”<<m);
}
int cube(int x)// Определение функции вычисления
//куба целого числа
{return x*x*x;}
Пример 2. Определить функцию, подсчитывающую количество нулей в троичной записи натурального числа. Найти все пары натуральных чисел в диапазоне [n1,n2], разность между которыми равна 4 и в троичной записи которых равное число нулей. Например, такой парой является пара 6(203) и 10(1013) (в троичной записи по одному нулю).
# include <iostream.h>
int oct (int a)// определение функции
{int sum=0;
while (a>0)
{
if (a%3==0) sum++;
a/=3;
}
return sum;
}
void main()
{
int n1,n2;
cout <<"Enter n1,n2 ";
cin>>n1>>n2;
for (int i=n1;i<=n2-4;i++)// Проверяем все пары чисел,
//разность между которыми равна 4
if (oct(i)==oct(i+4) && oct(i)>0)// условие, содержащие
//три вызова функции oct
cout <<i<<" "<<i+4<<"\n";
}
Особое место в ряду функций занимают так называемые рекурсивные функции, причем разделают прямую и косвенную рекурсию. Функция называется косвенно рекурсивной в том случае, если она содержит обращение к другой функции, содержащий вызов данной функции. Если же в теле функции имеется вызов самой этой функции, то речь идет о прямой рекурсии, а такую функцию называет рекурсивной. Рекурсивные алгоритмы эффективны в тех задачах, где рекурсия используется в определении данных. Если у задачи есть очевидное итерационное решение, то рекурсии следует избегать. Поэтому серьезное изучение рекурсивных методов нужно проводить, вводя динамические структуры данных. Сейчас же рассмотрим только принципиальные возможности С++ для организации рекурсивных алгоритмов.
Пример 3. Напишите рекурсивную функцию, вычисляющую xn (n-целое, неотрицательное).
# include <iostream.h>
float step(float x, int n)
{ float k;
if (n==0) return 1;
k=x*step(x,n-1); //рекурсивный вызов
return k;
}
void main()
{
float x;
int n;
cout<<"Enter x,n ";
cin>>x>>n;
cout <<"\nStepen("<<x<<","<<n<<")= "<<step(x,n);
}
Для n=0 функция возвращает значение 1. В противном случае вызывается та же функция с уменьшенным на 1 значением параметра степени. Таким образом, организуется последовательность вычислений xn=x*xn-1, xn-1=x*xn-2…, x2=x*x1, x1=x*x0, x0=1. Обратите внимание, что последовательность рекурсивных обращений к функции прерывается только при вызове функции step(x,0). Таким образом, важным моментом при составлении любой рекурсивной функции является организация выхода их рекурсии. Каждая задача, решаемая рекурсивным образом, при некоторых наборах данных должна иметь элементарное нерекурсивное решение, например, в нашем примере x0=1.
Больше значение в современном программировании играет не только умение создавать собственные функции, но и грамотное использование уже созданных библиотечных функций. Использование любой стандартной библиотечной функции предполагает ее тщательное предварительное изучение с помощью справочника по языку программирования или справочной системы интегрированной среды программирования. В качестве примера рассмотрим некоторые из библиотечных функций языка С для работы со стоками и файлами.
Функции для работы со строками описаны в заголовочном файле string.h. ([7] стр. 501, [8] стр. 167.) Как было отмечено в главе 5 строка в языке С задается как массив символов и строковые функции работают именно с символьными массивами, завершающимися символом ‘\0’, причем вся ответственность за переполнение массивов ложится на плечи программиста. Так как имя массива является указателем-константой на его первый элемент, то параметрами строковых функций чаще всего являются именно указатели-константы на объект типа char (const char *). Рассмотрим описание некоторых функций библиотеки string.h
1.
# include <string.h>
unsigned int strlen(char * str)
Функция strlen() возращает длину строки str. Завершающий нулевой символ не учитывается.
Пример использования функции:
char s[255]; cin.getline(s,255);
cout<< “Длина строки равна ”<<strlen(s);
2.
#include <string.h>
int strcmp(const char *str1, const char* str2);
Функция strcmp() сравнивает в лексикографическом порядке две строки и возвращает целое значение, зависящее от результата сравнения следующим образом: значение меньше нуля, если str1<str2; ноль, если str1=str2; больше нуля, если str1>str2. Приведем пример использования этой функции – фрагмент программы, проверяющий упорядочены ли два слова по алфавиту:
char s1[20], s2[20];
cin>>s1>>s2;
int k=strcmp(s1,s2);
if (k<0) cout<< “Слова упорядочены по алфавиту”;
else if (k==0) cout<< “Слова одинаковы”;
else cout<< “Слова не упорядочены по алфавиту”;
#include <string.h>
char * strcpy (char *str1, const char* str2);
Функция strcpy() копирует содержимое строки str2 в строку str1 и возвращает значение указателя str1. Если заданные символьные массивы перекрываются, поведение функции не определено. Приведем пример использования этой функции – ввести в клавиатуры слово и скопировать его в новую строку.
char str1[20],str2[20];
cin>>str1;
strcpy(str2,str1);
cout<<str1<<" "<<str2;
Функции для работы с файлами описаны в заголовочном файле stdio.h. ([8] стр. 131). В языке не предусмотрены никакие предопределенные структуры фалов: все файлы рассматриваются как последовательности, потоки байтов. Для файла определен маркер (указатель чтения/записи), который определят текущую позицию, к которой осуществляется доступ. В программе возможно открывать потоки ввода-вывода и связывать их либо с файлами на диске либо с физическими устройствами (например, принтером), записывать в них или считывать из них информацию. Доступ к потоку осуществляется с помощью типа FILE, определенного в файле stdio.h следующим образом:
FILE * идентификатор;
Описанный указатель можно связывать с конкретным файлом в момент открытия данного файл. Это осуществляется с помощью функции
FILE * fopen(const char *fname, const char * mode);
Функцияfopen()открывает файл, имя которого задает параметр fname и возвращает поток, связанный с этим файлом. Строка fname должна представлять собой имя файла, которое разрешено определенными в данной операционной системе правилами. Если указанный файл не удается открыть, функция возвращает нулевой указатель. Типы операций, которые разрешено выполнять с файлом, определяются параметром mode. Существует таблица значений параметра mode. Наиболее часто используемые значения:
“r” – открывает текстовый файл для чтения;
“w” – создает текстовый файл для записи;
“a” – открывает текстовый файл для записи в конец файла;
“r+” – открывает текстовый фал для чтения и записи;
“w+” – создает текстовый файл для чтения и записи;
“a+” – открывает текстовый файл для чтения и записи в конец файла.
Приведем фрагмент программы, иллюстрирующий корректный способ открытия файла.
FILE *fp=fopen("1.txt","r");
if (fp==NULL) {cout<<"Не удается открыть файл "; exit(1);}
else {….}
В данном примере происходит попытка открыть файл с именем “1.txt” в текущем каталоге для чтения. Если такого файла не существует, на экран выдается соответствующее сообщение и с помощью функции exit(), описанной в заголовочном файле stdlib.h, происходит завершение программы. При открытии файла для записи с параметром “w” также рекомендуется делать проверку, так как диск может быть защищен от записи или заполнен.
По окончании работы с файлом он должен быть закрыт с помощью функции
int fclose (FILE * stream);
После обращения к функции fclose() указатель stream больше не связан с конкретным файлом. При успешном выполнении функции возвращается ноль, в противном случае возвращается значение EOF. Попытка закрыть уже закрытый файл расценивается как ошибка.
Опишем назначений основных функций ввода и ввода данных.
Функцияint fgetc(FILE * stream); считывает из входного потока streаm следующий символ, соответствующий текущей позиции, при достижении конца файла возвращает значение EOF.
Функцияchar * fgets (char *str, int num, FILE * stream); считывает из входного потока stream не более num-1 и помещает их в массив, адресуемый указателем str. Символы читаются пока не будет прочитан символ новой строки или конец файла либо пока не будет достигнут заданный предел. По завершении чтения символов сразу за последним прочитанным символом размещается нулевой символ. Символ новой строки сохраняется и остается частью строки. При успешном выполнении функции возвращается значение str, при неуспешном – нулевой указатель.
Функцияint fscanf (FILE * stream, const char * format, …); читает информацию из потока stream. Управляющая строка, задаваемая параметром format состоит из символов трех категорий: спецификаторы формата, пробельные символы и символы, отличные от пробельных. Спецификаторы формата – им предшествует знак процента – сообщают, какого типа данные будут прочитаны. Например спецификатор %d прочитает целое значение, а спецификатор %с прочитает символ. Пробельные символы заставляют функцию пропустить один или несколько пробельных символов во входном потоке. Не пробельный символ заставляет функцию прочитать и отбросить соответствующий символ из входного потока. Символ *, стоящий после знака % и перед кодом формата прочитает данные заданного типа, но запретит их присваивание. В качестве неопределенных параметров функции могут использовать параметры зависимости от управляющей строки. Например, функция fcsanf (fp, “%d%d”, &a, &b) прочитает очередные два целых числа из файлового потока fp в переменные a, b, а функция fcsanf (fp, “%d%*d”, &a) считает два целый числа, но в переменной а сохранит только первое из них. Функция возвращает количество аргументов, которым действительно присвоены значения.
Функция int fputc(int ch, FILE * stream); записывает символ ch в заданный поток stream в текущую позицию файла, а затем передвигает индикатор позиции файла. Возвращает значение записанного символа, а в случае ошибки значение EOF.
Функция int fputs(const char *str, FILE* stream); записывает в заданный поток stream содержимое строки, адресуемой указателем str. При этом завершающий нулевой символ не записывается. При успешном выполнении возвращается неотрицательное значение, при неудачном – значение EOF.
Функция int fprintf (FILE * stream, const char *format, …); - записывает в файловый поток stream значения параметров из заданного списка параметров в соответствии со строкой форматирования format. Например, функция fprintf(fp, “%d”, a) запишет значение целой переменной a в файловый поток fp. Функция возвращает количество реально выведенных символов, а при возникновении ошибки- отрицательное значение.
Для проверки, достигнут ли конец файла используют функцию
int feof(FILE *stream);
Если индикатор позиции файла, связанного с потоком stream, расположен в конце файла возвращается ненулевое значение, в противном случае - нуль.
Для изменения индикатора позиции файла используют функцию
int fseek ( FILE* stream, long offset, int origin);
Функция устанавливает индикатор позиции файла, связанного с потоком stream, в соответствии со значением смещения offset (количество байтов) и исходного положения origin. Параметр origin может принимать одно их следующих значений: 0 - начало файла, 1 – текущая позиция, 2 – конец файла. При успешном выполнении функция возвращает нулевое значение, при возникновении сбоя – ненулевое. Функция очищает признак конца файла. Вообще говоря функцию fseek() следует использовать только при работе с двоичными файлами. При использовании же с текстовыми файлами параметр origin должен иметь значение 0, а параметр offset – значение, полученное в результате вызова функции
long ftell (FILE* stream);
которая возвращает текущее значение индикатора позиции файла.
Приведем фрагмент программы, считывающей из файлового потока fp каждый третий символ
char a;
while ((a=fgetc(fp))!=EOF && fseek(fp,2,1)==0)
cout<<a<<" ";
Если необходимо считать каждое третье число из файла (предполагается, что числа разделены пробелами) программа примет следующий вид:
int a;
while (fscanf(fp, "%d%*d%*d ", &a)!=EOF && fseek(fp,ftell(fp),0)==0)
cout<<a<<" ";
Каждому студенту рекомендуется выполнить хотя бы одно из упражнений 1-12 заданий 1-4.
Дата добавления: 2015-10-09; просмотров: 1096;