§ 4. Одномерные массивы в функциях. Сортировка массива

П р и м е р 1. Рассортировать одномерный целочисленный массив по возрастанию последней цифры числа. Если последняя цифра одинакова, то сортировать по возрастанию самого числа.

void MyInp(int x[],int size); // Ввод массива размерности size

void MyOut(int x[],int size); // Вывод массива размерности size

// Сортировка массива по возрастанию последней цифры числа void MySort(int x[],int size);

int DIGIT(int num) // Для одного числа получаем последнюю цифру

{ return abs(num % 10);

};

void RR(int &u, int &v) // Перестановка двух целых чисел

{ int t;

t=u; u=v; v=t;

};

// DIGIT и RR – это встраиваемые функции (см. 6.1).

int main()

{ const n=5; int A[n]; MyInp(A,n);

cout<<" Integer random array\n"; MyOut(A,n);

MySort(A,n);

cout<<" \n\Array after sorting\n"; MyOut(A,n);

getch(); return 0;

} ;

void MyInp(int x[],int size)

{ // или randomize();

for(int i=0; i<size; i++)

cin>>x[i]; // или x[i]=random(100)-50;

} ;

void MyOut(int x[],int size)

{ cout<<endl;

for(int i=0; i<size; i++)

cout<<x[i]<<" ";

} ;

Прежде чем писать последнюю функцию, рассмотрим следующий алгоритм сортировки одномерного массива. Последовательно сравниваем каждую пару двух соседних чисел и в зависимости от результата сравнения их переставляем или оставляем на месте. За один просмотр результата не достигнем, поэтому повторяем это. Алгоритм реализуется с помощью двух вложенных циклов.

В первом, плохом, варианте и внутренний, и внешний циклы можно повторить (size-1) раз, где size — размерность массива.

for ( int k=1; k<size; k++)

for(int j=0; j<size-1; j++)

if ( x[j]>x[j+1] )

RR(x[j], x[j+1]);

Улучшим внутренний цикл. Легко заметить, что после первого этапа наибольшее число массива будет в конце, то есть займёт своё место независимо от того, где оно было до сортировки. После второго шага второе наибольшее число займёт предпоследнее место, и так далее. Поэтому если вначале надо анализировать все пары чисел, то на втором шаге последнее число можем не “трогать”, так как оно уже на своём месте. Аналогично, на каждом последующем этапе количество сравниваемых пар можно на одну уменьшать. Тогда внутренний цикл будет таким:

for(int j=0; j<size-k; j++) …

Оптимизация внешнего цикла. Всегда ли надо (size1) просмотров массива? Для “хорошего” массива, который частично рассортирован, результат можем получить и раньше. Как c учётом этого организовать внешний цикл? Предлагается следующее. Просмотр и анализ массива будем продолжать, если на предыдущем этапе была хотя бы одна перестановка. Если окажется, что ни одну пару не переставляли, то это означает, что массив рассортировали и можно выйти из внешнего цикла. Это реализуется с помощью переменной flag. Если на какомто шаге была хотя бы одна перестановка, переменная flag изменит своё значение на единицу, и внешний цикл продолжаем. В противном случае, если не было ни одной перестановки, останется flag=0, и сортировка прекращается.

int flag=1, k; k=size;

while (flag)

{ k--; flag=0;

for(int j=0; j<k; j++)

if (x[j]>x[j+1]) { RR(x[j], x[j+1]);

flag=1;

}

}

Используемый при написании программы сортировки приём можно назвать методом последовательного (поэтапного) улучшения алгоритма (программы). Вначале составляем наиболее простой, не обязательно эффективный алгоритм. Его можем запрограммировать и отладить. При этом возможны, но не обязательны, некоторые упрощения постановки задачи. Отладив такой упрощённый вариант, улучшаем алгоритм и (или) программу и снимаем ограничения на условие задачи.

Если надо сортировать числовой массив по некоторому параметру числа, то в обычную сортировку необходимо внести следующие дополнения:

1. вначале строим массив параметров (массив D последних цифр);

2. сравниваем не сами числа, а эти параметры. И если параметры равны, только тогда сравниваем сами числа, если по условию требуется, как в нашем примере, “двойная” сортировка;

3. переставляем не только сами числа, но и их параметры, чтобы они соответствовали тем же числам, что и до сортировки.

void MySort(int x[],int size)

{ // Строим массив последних цифр

int D[20]; // 20 — наибольшая размерность

for(int i=0; i<size; i++)

D[i]=DIGIT(x[i]); /* В качестве фактического параметра функции можно использовать индексированную переменную, то есть элемент массива. В качестве формального параметра индексированную переменную записывать нельзя */

int flag=1, k; k=size;

while (flag)

{ k--; flag=0;

for(int j=0; j<k; j++)

// сравниваем параметры чисел, а если они равны, то и сами числа

if ( D[j]>D[j+1] || x[j]>x[j+1] && D[j]==D[j+1] )

{ RR(D[j], D[j+1]); // переставляем параметры

RR(x[j], x[j+1]); // переставляем исходные числа

flag=1;

}

} // the end of while

} ; // the end of function MySort

Независимо от того, является массив входным или выходным, он передаётся одинаково в качестве параметра функции по следующим правилам:

• в заголовке функции указываем тип элементов массива, его имя и пустые квадратные скобки. Чаще всего в качестве параметра указывается и его размерность (size в примере). Этим самым мы подчёркиваем, что работаем с массивом произвольной размерности;

• в тексте функции, как обычно, доступ к элементам массива осуществляется с помощью индексов;

• в вызывающей функции объявляем массив обычным образом;

• при вызове функции в качестве фактического параметра записываем только имя массива A (не A[I], не A[N], не A[], не A[5]) или &A[0] — адрес начала массива, т. е. номер первого байта элемента A[0].

При использовании массива в качестве параметра функции фактически передаётся не сам массив, а указатель на него, или адрес массива, то есть номер первого байта первой ячейки массива (с индексом 0). Другими словами, int x[] (или int *x) в заголовке функции означает, что ячейка x предназначена для хранения адреса. При вызове функции из объявления int A[N] следует, что A, или &A[0], — это адрес начала массива из N элементов. Как и для простых переменных, этот адрес (но не сам массив) копируется в ячейку x. В результате получается, что в A и в x хранятся адреса одной и той же области оперативной памяти. Или, другими словами, A[0] в main — это та же ячейка, что и x[0] в MySort, A[1] — это та же ячейка, что и x[1], и так далее. Поэтому если в функции массив x изменим, то этим самым мы изменим и массив A.

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

П р и м е р 2.

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

2) Составить функцию для вывода массива.

3) Составить логическую функцию, которая возвращает true или false в зависимости от того, рассортирован ли массив по возрастанию.

4) В main проверить эти функции.

void MyInp(int x[],int size);

void MyOut(int x[],int size);

bool Sorted(int x[],int size);

int main(int argc, char* argv[])

{ const n=5; int A[n]; MyInp(A,n);

cout<<" Integer array"; MyOut(A,n);

if (Sorted(A,n))

cout<<" \n рассортирован по возрастанию \n";

else cout<<" \n не рассортирован по возрастанию \n";

getch(); return 0;

} ;

void MyInp(int x[],int size)

{ for(int i=0; i<size; i++)

{ textcolor (15);

do // цикл для ввода одного числа с проверкой

{ cin>>x[i];

if (x[i]>0) break;

textcolor (12);

cprintf("Error. Repeat. ");

} while (1);

}

} ;

void MyOut(int x[], int size)

{ cout<<endl;

for(int i=0; i<size; i++) cout<<x[i]<<" ";

} ;

bool Sorted(int x[], int size)

{ for (int i=0; i<size-1; i++)

if (x[i]>x[i+1])

return false;

return true;

}

П р и м е р 3 (cтрока как массив символов).

Составить функцию, которая в строке находит количество цифр и количество введённого символа.

Для простой работы со строками достаточно объявить её как массив символов, не используя в явном виде указатели и возможности работы с ними (см. 2–й семестр). Объявление и инициализация строк были показаны в § 6 гл. 1. Для ввода строк вместо cin лучше использовать функцию gets, так как cin вводит строку до первого пробела.

void STRDIGIT (char t[],char simbol, int &K1, int &K2);

int main()

{ char str[50]; // объявляем массив наибольшей длины 50

gets(str); // ввод строки

char c1; int KDig, KC; cout<<"Input the symbol ";

c1=getchar(); // ввод одного символа

STRDIGIT(str,c1,KDig,KC);

cout<<"In the string ";

puts(str); // вывод строки, или printf ( “%s\n”, str)

cout<< KDig<< " digits and "<<KC << " of simbol "<<c1;

getch(); return 0;

}

void STRDIGIT (char t[], char simbol, int &K1, int &K2)

{ K1=0; K2=0;

for (int i=0; i<strlen(t); i++) // strlen возвращает длину строки

{ if (t[i]>='0' && t[i]<='9') K1++;

if (t[i]==simbol) K2++;

} }

// или

for (int i=0; t[i] !=’\0’; i++)

/* Цикл продолжается, пока не встретится символ конца строки, которым заканчивается любая строка. Это же можно записать короче: for (int i=0; t[i]; i++) */

{ if (isdigit(t[i])) K1++; // является ли символ цифрой

if ( ! (t[i]-simbol ) ) K2++; }

// или

for (int i=0; t[i];)

{ if ( isdigit(t[i])) K1++;

if (t[i++]==simbol) K2++;

}

Кроме функции getchar для ввода одного символа можно использовать функции getch или getche. От их выбора зависит, вопервых, надо ли при вводе символа нажимать не только на клавишу вводимого символа, но и на клавишу ввода (да, нет, нет) и, вовторых, будет ли отображаться введённый символ на экране (да, нет, да).

Кроме функции isdigit, есть другие функции, анализирующие один символ:

• islower — является ли аргумент символом нижнего регистра (маленькой буквой, например);

• isupper — является ли аргумент символом верхнего регистра (большой буквой, например);

• isalpha — является ли аргумент буквой алфавита (верхнего или нижнего регистра);

• isgraph — является ли аргумент печатным символом, отличным от пробела;

• isprint — является ли аргумент печатным символом, включая пробел. Эти и другие подобные функции, имена которых начинаются с is, возвращают true или false в зависимости от того, принадлежит ли символ соответствующей группе.