Индексы в массивах

СИНТАКСИС: aname[индекс]

ПРИМЕР: b[i+1]

ОПИСАНИЕ: Индекс может быть любым выражением типа int. Каждый раз , когда в программе встречается индексированная переменная, сначала определяется значение индекса, и по этому значению определяется, к какому элементу массива происходит обращение.

ПРИМЕЧАНИЕ: Ответственность за проверку нахождения индекса в диапазоне, заданном при объявлении массива, возлагается на программиста. При неверном значении индекса происходит обращение к ячейке памяти, не относящейся к этому массиву. Обычно это приводит к побочным эффектам в программе, причину которых программисту сложно обнаружить.

Использование индексных циклов for для обработки массивов.

Часто возникает необходимость в последовательной обработке значений массива, начиная с нулевого элемента. Примером может быть ввод данных в массив либо печать его содержимого. В языке Си такая обработка легко выполнима с помощью индексных циклов for – счётных циклов, управляющая переменная которых изменяется от нуля дог значения, на единицу меньшего размерности массива. Использование счетчика цикла в качестве индекса массива обеспечивает доступ к каждому элементу массива.

ПРИМЕР: Следующий массив s будет использован для хранения квадратов чисел от 0 до 5 (т.е. s [0] равен 0, s [5] равен 16)

#define size 5

Цикл for

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

s[i] = i*i;

инициализирует этот массив следующим образом

s[0] s[1] s[2] s[3] s[4]

S=

Сортировка массива

Рассмотри очень простой, но не очень эффективный алгоритм, называемый пузырьковым методом сортировки. В пузырьковом методе сравниваются смежные элементы массива и меняются местами в случае, если их порядок не соответствует заданному. При этом меньшие элементы «всплывают», как пузырьки, к поверхности массива (к элементу 0), а большие значения «оседают на дно» массива. Ниже приводится требования к данным и алгоритм для пузырьковой сортировки.

ВХОДЫ ЗАДАЧИ

Сортируемый массив

Число элементов массива

ВЫХОДЫ ЗАДАЧИ

Отсортированный массив

АЛГОРИТМ для пузырьковой сортировки

1.Повторять

2. проверять каждую пару смежных элементов массива, меняя значения местами, если они не упорядочены,

пока массив не отсортирован.

Для наглядности проведем трассировку одного выполнения шага 2, то есть сделаем один проход один проход, через сортируемый массив. Просматривая слева направо содержимое массива, мы можем увидеть результат каждого сравнения. Пары сравниваемых элементов массива на рисунке выделены темным цветом. Первая пара значений (m[0] = 60 и m[1] = 42) не упорядочена, поэтому значения меняются местами. Во втором столбце сравнивается следующая пара(m[2] = 75, m[3] = 83). Последняя пара (m[3] = 83, m[4] = 27) не упорядочена, поэтому значения меняются местами, как показано в последнем столбце

Последний массив, показанный на рисунке ближе к отсортированному, чем первоначальный. Только одно значение не в правильном порядке – это m[3]. Но в таком алгоритме должно быть совершено еще три прохода, прежде чем это значении выплывет к началу массива. В каждом из трех проходов только одна пара будет неупорядоченной, поэтому производится по одной перестановке. Содержимое m после завершения каждого прохода показано на рисунке:

Конец Конец Конец Конец Конец

прохода 1 прохода 2 прохода3 прохода 4 прохода 5

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

Переменные программы

int sorted /*флаг, индицирующий, были ли сделаны какие-либо перестановки в текущем проходе*/

int i /*управляющая переменная цикла и индекс*/

int pass /*номер текущего прохода, начиная с 1*/

Деталировка шага 2:

2.1 Инициализировать sorted в 1(истина).

2.2 Повторять для каждой пары смежных элементов массива.

2.3 if значения пары не в порядке.

2.4 Поменять значения местами.

2.5 Установить sorted в 0(ложь).

Шаг 2 будет реализован с помощью цикла for. Управляющая переменная цикла i будет также служить индексом первого элемента каждой пары; следовательно, i+1 будет индексом второго элемента каждой пары. При каждом проходе, начальное значение i = 0. Конечное значение i должно быть меньше наибольшего допустимого значения индекса массива, так что i+1 также будет находиться в диапазоне.

Для массива из n элементов число сравниваемых пар элементов в одном проходе будет n-pass, где pass – это номер текущего прохода, начинающийся с 0 для первого прохода.

main ()

{

int n; /*число сортируемых элементов*/

int i,

pas, /*номер текущего прохода массива*/

temp, /*временная переменная для обмена пар*/

sorted; /*флаг, указывающий на факт сортировки массива */