Листинг 5.3

#include " stdafx.h"

#include " conio.h"

#include " math.h"

#include " windows.h"

#include < iostream>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])

{

int n;

setlocale(LC_ALL, " Russian");

cout< < " \nВведите количество элементов: ";

cin > > n;

int i, ineg = -1;

float sum, *a = new float[n]; // 1

cout< < " \nВведите элементы массива: \n\n";

for(i = 0; i < n; i++) cin > > a[i];

bool flag_neg = false;

float sum = 0.f;

for(i = n - 1; i > = 0; i--)

{

if(a[i] < 0)

{

flag_neg = true;

break;

}

sum += a[i];

}

if(flag_neg)

cout< < " \nСумма: " < < sum;

else

cout< < " \nОтрицательных элементов нет ";

getch();

return 0;

}

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

Для исчерпывающего тестирования этой программы необходимо ввести по край­ней мере три варианта исходных данных - когда массив содержит один, несколь­ко или ни одного отрицательного элемента.

Пример 5.2. Написать программу, которая упорядочивает вещественный массив методом бы­строй сортировки.

Идея алгоритма состоит в следующем. Применим к массиву так называемую про­цедуру разделения относительно среднего элемента. Вообще-то, в качестве «сред­него» можно выбрать любой элемент массива, но для наглядности мы будем выбирать по возможности, средний по своему номеру элемент.

Процедура разделения делит массив на две части. В левую помещаются элементы, меньшие, чем элемент, выбранный в качестве среднего, а в правой - большие. Это достигается путем просмотра массива попеременно с обоих концов, при этом каж­дый элемент сравнивается с выбранным средним, и элементы, находящиеся в «не­подходящей» части, меняются местами. После завершения процедуры разделения средний элемент оказывается на своем окончательном месте. Далее процедуру разделения необходимо повторить отдельно для левой и правой части: в каждой части выбирается среднее, относительно которого она делится на две, и так далее.

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

Для хранения границ еще не упорядоченных частей массива более всего подходит структура данных, называемая стеком. Стек является одной из наиболее часто употребляемых структур данных и функционирует по принципу: «первым пришел, последним ушел».

В приведенной ниже программе стек реализуется в виде двух массивов stackr и stackl и одной переменной sp, используемой как «указатель» на вершину стека (она хранит номер последнего заполненного элемента массива). Для этого ал­горитма количество элементов в стеке не может превышать n, поэтому размер мас­сивов задан равным именно этой величине. При занесении в стек переменная sp увеличивается на единицу, а при выборке - уменьшается.

Ниже приведена программа, реализующая этот алгоритм: