Массив как статическая структура данных

Массив– это упорядоченная последовательность данных одного и того же типа, имеющая общее имя; доступ к элементам массива организуется при помощи индексов, которые могут быть любого порядкового типа. Индексы можно представлять себе как порядковые номера элементов в последовательности.

Массив как статическая структура обладает следующими свойствами:

· она имеет описание, и обращение к ней возможно по имени;

· память под нее выделяется на этапе компиляции;

· объем памяти фиксирован и не меняется в процессе выполнения программы.

Массивы могут быть одномерными, двумерными и многомерными.

Одномерный массив – это массив, для получения доступа к элементам которого достаточно одной индексной переменной. Математическим представлением одномерного массива является вектор.

Линейный поиск в массивах данных.

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

Способы сортировки в массивах данных.

Сортировкой информационной структуры (массива, списка, файла) называется преобразование исходной структуры путем перестановки ее элементов для достижения упорядоченности по заданному признаку порядка.

Признаки порядка.

Одномерный массив А (n) называется упорядоченным

по возрастанию, если для любого i = 2, 3, …, n a_i > a_i-1

по неубыванию, если для любого i = 2, 3, …, n a_i ≥ a_i-1

по убыванию, если для любого i = 2, 3, …, n a_i < a_i-1

по невозрастанию, если для любого i = 2, 3, …, n a_i ≤ a_i-1

Пузырьковая сортировка (попарные перестановки).

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

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

Сортировка выбором.

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

a_i^’ = min(max){a_j , j=i, i+1, …, n}, i=1, …, n-1

где n – размерность массива

Сортировка простыми вставками.

Чтобы упорядочить массив A(n) сортировкой простыми вставками используется следующий подход: для i = 2, 3, …, n каждый элемент a_i переставляется в нужное место среди упорядоченных ранее элементов a₁, a₂, …, a_i-1, раздвигая их за счет удаления a_i.

Некоторые рекомендации при работе с массивом.

1. При объявлении массивов размерность задается константами, поэтому следует объявлять наиболее разумные размерности, а затем вводить переменные размерности и циклы организовывать уже с их использованием.

2. При обработке массивов рекомендуется использовать вывод на экран всего введенного массива в наглядной форме для визуального контроля правильности ввода и демонстрации соответствия результатов введенным данным.

3. Следует максимально ограничивать выделение дополнительных (рабочих) массивов той же размерности, что и обрабатываемые, а также искать эффективные по трудоемкости алгоритмы.

4. В задачах на анализ или поиск в заданном массиве не следует искажать массив в своих целях.

5. Если требуется найти фрагмент массива, обладающий каким-либо свойством (цепочку элементов), то следует в качестве результата показать не только сам фрагмент, но и его местоположение (индексы первого и последнего элементов фрагмента) в массиве.

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

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

Тестирование программ

Под тестированиемпонимается процесс проверки правильности работы  программы в целях выявления ошибок, при этом выявляются как ошибки в алгоритме, так и в составлении самой программы.

Целью тестирования является выявление как можно большего числа ошибок.

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

Отладка программ

Если тестирование – это процесс, направленный на выявление ошибок, то целью отладкиявляются локализация и устранение выявленных в процессе тестирования ошибок в алгоритме и реализующей его программе (выявление синтаксических ошибок выполняется транслятором).

Процесс отладки включает:

· действия, направленные на выявление ошибок (тестирование);

· диагностику и локализацию ошибок (определение характера и местонахождения ошибок);

· внесение исправлений в программу с целью устранения ошибок.

Нисходящая отладка программ (сверху вниз).

Нисходящая отладка начинается с отладки взаимосвязи подзадач самого высокого уровня (отладки интерфейсов подзадач).

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

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

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

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

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

2. Что такое «формальные параметры»? Назвать их разновидности.

3. Что такое «фактические параметры»?

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

5. Какое местоположение могут занимать подпрограммы в тексте и вне текста программы?

6. Что такое «массив»? Какими свойствами обладает массив как статическая структура?

7. Назвать некоторые рекомендации при работе с массивами.

8. Что означает линейный поиск в массиве данных?

9. Что такое «сортировка в массиве данных»? Назвать некоторые способы сортировки.

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

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

12. Что такое «тестирование программы»? Что называется тестом?

13. Что называется отладкой программы?

14. Что такое «нисходящая отладка»? Что представляет собой заглушка?

III. Последовательность выполнения общего задания.

Постановка задачи

Координатами x, y заданы n точек плоскости. Найти:

1) процент точек, удаление которых от начала координат больше заданной величины r и у которых обе координаты отрицательны;

2) среднее удаление всех точек от начала координат.