- •7. Одномерные массивы 114
- •8. Обработка двумерных массивов (матриц) 162
- •9. Обработка строк 183
- •10. Тип данных, определенный пользователем. Структуры 214
- •11. Использование подпрограмм 228
- •Приложение 52 310 Список литературы 313 Введение
- •1. Этапы создания Windows-приложения
- •2. Среда Visual Basic 2005
- •2.1. Структура среды Visual Basic 2005
- •2.2. Создание нового проекта
- •2.3. Сохранение проекта
- •2.4. Выполнение приложения
- •2.5. Основные команды среды Visual Basic 2005
- •2.6. Методы тестирования
- •2.7. Отладка приложений в среде vb
- •3. Разработка интерфейса в среде vb. Основные элементы управления
- •3.1. Метка
- •3.2. Текстовое поле
- •3.3. Кнопка
- •3.4. Окно списка
- •3.5. Выравнивание положения элементов управления
- •4. Программа линейной структуры
- •4.1. Понятие переменной
- •4.2. Типы данных
- •4.3. Объявление переменных
- •4.4. Оператор присваивания
- •Оператор присваивания работает справа налево.
- •4.5. Константы
- •4.6. Арифметические операции
- •4.7. Математические функции
- •4.8. Арифметическое выражение
- •4.9. Окно ввода (InputBox)
- •4.10. Окно вывода сообщения (MsgBox)
- •4.11. Пример. Вычисление площади треугольника
- •4.12. Пример. Нахождение цифр числа
- •5. Организация ветвлений
- •5.1. Логические константы и переменные
- •5.2. Операции сравнения
- •5.3. Логические операции
- •5.4. Логическое выражение
- •5.5. Условный оператор
- •5.6. Функция iIf
- •5.7. Оператор множественного ветвления ElseIf
- •5.8. Оператор выбора Select Case
- •5.9. Оператор безусловного перехода GoTo
- •5.10. Пример. Решение линейного уравнения
- •5.11. Пример. Программа-калькулятор
- •6. Программирование повторений
- •6.1. Цикл со счетчиком
- •6.1.1. Табуляция функции
- •6.1.2. Вычисление факториала
- •6.1.3. Обработка совокупности чисел с известным числом элементов
- •6.2. Цикл с условием
- •6.2.1. Ввод с проверкой
- •6.2.2. Обработка совокупности чисел с неизвестным числом элементов
- •6.2.3. Вычисление суммы ряда по общей формуле
- •Вычисление суммы ряда с использованием рекуррентного соотношения
- •6.2.5. Вычисление произведения ряда
- •Решение нелинейных уравнений методом простой итерации
- •7. Одномерные массивы
- •Массивы всегда обрабатываются в цикле.
- •7.1. Ввод массива
- •Вывод массива в окно списка и в текстовое поле
- •7.3. Вычисление суммы и произведения элементов массива
- •7.4. Определение количества элементов массива, удовлетворяющих некоторому условию
- •7.5. Вычисление среднего арифметического и среднего геометрического элементов массива, удовлетворяющих некоторому условию
- •7.6. Нахождение максимального элемента массива
- •7.7. Нахождение минимального элемента массива, удовлетворяющего некоторому условию
- •7.8. Поиск первого элемента массива, удовлетворяющего некоторому условию
- •7.9. Поиск последнего элемента массива, удовлетворяющего некоторому условию
- •7.10. Замена одного элемента массива
- •7.11. Замена всех элементов массива, удовлетворяющих некоторому условию
- •7.12. Перестановка местами двух элементов массива
- •7.13. Формирование нового массива из некоторых элементов исходного массива
- •7.14. Проверка совпадения всех элементов массива
- •7.15. Проверка упорядоченности всех элементов массива
- •7.16. Сортировка массива методом пузырька
- •7.17. Линейная сортировка массива (методом поиска минимума)
- •Никогда нельзя использовать одновременно оба способа перестановки элементов массива.
- •8. Обработка двумерных массивов (матриц)
- •8.1. Ввод прямоугольной матрицы
- •8.2. Вывод прямоугольной матрицы в окно списка и в текстовое поле
- •8.3. Поиск максимального элемента матрицы
- •8.4. Обработка матрицы по строкам
- •8.5. Обработка матрицы по столбцам
- •8.6. Обработка квадратных матриц
- •Для обработки элементов, стоящих на любой диагонали, достаточно одного цикла. Для обработки элементов, принадлежащих к одному из треугольников, необходимо использовать вложенные циклы.
- •9. Обработка строк
- •9.1. Основные функции обработки строк
- •9.2. Посимвольная обработка строки
- •9.3. Формирование массива слов строки
- •9.4. Формирование строки из массива слов
- •9.5. Слова-палиндромы
- •9.6. Выделение чисел из строки
- •9.7. Сравнение строк
- •9.8. Обработка многострочного текста
- •10. Тип данных, определенный пользователем. Структуры
- •10.1. Описание структуры. Область видимости. Понятие метода
- •10.2. Оператор With
- •10.3. Ввод массива структур
- •10.4. Вывод массива структур
- •10.5. Поиск в массиве структур
- •10.6. Формирование нового массива из некоторых элементов исходного массива
- •10.7. Сортировка массива структур
- •11. Использование подпрограмм
- •11.1. Определение процедуры и функции. Описание процедуры и функции
- •11.2. Передача параметров по ссылке и по значению
- •11.3. Формальные параметры и фактические переменные
- •11.4. Локальные и глобальные переменные
- •11.5. Static-переменные
- •Приложение 1
- •Приложение 2
- •Приложение 3
- •Приложение 4
- •Приложение 5
- •Приложение 6
- •Приложение 7
- •Приложение 8
- •Приложение 9
- •Приложение 10
- •Приложение 11
- •Приложение 12
- •Приложение 13
- •Приложение 14
- •Приложение 15
- •Приложение 16
- •Приложение 17
- •Приложение 18
- •Приложение 19
- •Приложение 20
- •Приложение 21
- •Приложение 22
- •Приложение 23
- •Приложение 24
- •Приложение 25
- •Приложение 26
- •Приложение 27
- •Приложение 28
- •Приложение 29
- •Приложение 30
- •Приложение 31
- •Приложение 32
- •Приложение 33
- •Приложение 34
- •Приложение 35
- •Приложение 36
- •Приложение 37
- •Приложение 38
- •Приложение 39
- •Приложение 40
- •Приложение 41
- •Приложение 42
- •Приложение 43
- •Приложение 44
- •Приложение 45
- •Приложение 46
- •Приложение 47
- •Приложение 48
- •Приложение 49
- •Приложение 50
- •Приложение 51
- •Приложение 52
- •Список литературы
7.17. Линейная сортировка массива (методом поиска минимума)
Сортировка массива методом поиска минимума является одним из частных случаев линейной сортировки. Она может использоваться как для сортировки по возрастанию, так и по убыванию.
При сортировке по возрастанию метод предлагает найти минимальный элемент в массиве и поставить его на нулевое место. А элемент с нулевого места переместить на место минимального элемента. После этого нулевой элемент массива гарантировано стоит на своем месте. Поэтому в дальнейшей сортировке он не участвует. На следующем шаге массив просматривается уже с первого элемента. В этой части находится свой минимум, которой меняется местами с первым элементом. Теперь уже два элемента массива стоят на своих местах. На следующем шаге массив обрабатывается со второго элемента. Процесс продолжается до тех пор, пока в необработанной части массива не останутся два элемента. Среди них тоже находится минимальный. Он ставится на предпоследнее место массива. А последний необработанный элемент автоматически попадает на последнее место в массиве. Теперь все элементы стоят на своих местах и процесс сортировки можно прекратить. В таблице 10 приведен пример сортировки массива по возрастанию методом поиска минимума.
Таблица 10
Массив |
Действие |
5 4 1 3 2 |
Обработку массива начинаем с нулевого элемента. Его значение равно 5. Находим минимальный элемент в массиве. Его значение равно 1, и он стоит на второй позиции. Меняем местами элементы с номерами 0 и 2. |
1 4 5 3 2 |
Минимальный элемент гарантировано стоит на правильном месте, поэтому в дальнейшей сортировке он не участвует. Обработку массива начинаем с элемента под номером 1. Его значение равно 4. В оставшейся части массива ищем минимальный элемент. Его значение равно 2, и он стоит на четвертой позиции. Меняем местами элементы с номерами 1 и 4. |
1 2 5 3 4 |
Теперь уже два элемента стоят на правильных местах. В дальнейшей сортировке они не участвуют. Обработку массива начинаем с элемента под номером 2. Его значение равно 5. В оставшейся части массива ищем минимальный элемент. Его значение равно 3, и он стоит на третьей позиции. Меняем местами элементы с номерами 2 и 3. |
1 2 3 5 4 |
Уже три элемента стоят на правильных местах. В дальнейшей сортировке они не участвуют. В необработанной части массива осталось два элемента. Эта перестановка будет последней. Обработку массива начинаем с элемента под номером 3. Его значение равно 5. В оставшейся части массива ищем минимальный элемент. Его значение равно 4, и он стоит на четвертой позиции. Меняем местами элементы с номерами 3 и 4. |
1 2 3 4 5 |
В результате последней перестановки оба необработанных элемента оказались на правильных местах. Процесс сортировки закончен. |
Сортировка методом поиска минимума является одним из частных случаев линейной сортировки. Остальные варианты приведены в таблице 11.
Таблица 11
Направление сортировки |
Метод сортировки | |
Метод поиска минимума |
Метод поиска максимума | |
По возрастанию |
В необработанной части массива ищется минимальный элемент, который потом меняется местами с первым элементом в необработанной части. Необработанная часть уменьшается слева на один элемент. |
В необработанной части массива ищется максимальный элемент, который потом меняется местами с последним элементом в необработанной части. Необработанная часть уменьшается справа на один элемент. |
По убыванию |
В необработанной части массива ищется минимальный элемент, который потом меняется местами с последним элементом в необработанной части. Необработанная часть уменьшается справа на один элемент. |
В необработанной части массива ищется максимальный элемент, который потом меняется местами с первым элементом в необработанной части. Необработанная часть уменьшается слева на один элемент. |
Помимо этих вариантов существует еще один частный случай линейной сортировки. Это минимаксная сортировка (иногда встречается другое ее название – максиминная). Согласно данному методу в необработанной части массива одновременно ищется максимальный и минимальный элементы, которые затем расставляются по своим местам в зависимости от направления сортировки. При этом необработанная часть массива сокращается одновременно с двух сторон.
Рассмотрим особенности программной реализации алгоритма сортировки целочисленного массива по возрастанию методом поиска минимума.
Для решения задачи нам потребуется несколько дополнительных переменных. Переменная startпредназначена для хранения номера элемента, с которого начинается необработанная часть массива.
Dim start As Integer
На каждом шаге основного цикла мы будем искать минимальный элемент в необработанной части массива. При этом нам потребуются переменные для хранения значения минимального элемента (min) и его номера (imin). Переменнаяminвсегда будет иметь такой же тип, что и элементы массива. Переменнаяiminвсегда будет иметь целочисленный тип данных.
Dim imin, min As Integer
Организуем основной цикл. На первом шаге алгоритма линейной сортировки начало необработанной части массива совпадает с началом самого массива, то есть с нулевым элементом. После каждого шага цикла начало необработанной части будет смещаться на один элемент к концу массива. На последнем аге цикла в необработанной части массива остается всего два элемента. Очевидно, что при этом начало необработанной части массива будет совпадать с предпоследним элементом массива, то есть с элементом, имеющим номер (n-1)
For start = 0 To n – 1
На каждом шаге цикла мы будем искать минимальный элемент в необработанной части массива. Поиск удобно начинать с первого элемента необработанной части. Его номер всегда совпадает со значением, записанным в переменной start. Запоминаем стартовый элемент необработанной части как минимум.
min = a(start)
В специальную переменную записываем соответствующий номер элемента.
imin = start
Организуем цикл для поиска минимального элемента в необработанной части массива. Цикл начнется с элемента, следующего за стартовым, и будет идти до конца необработанной части. В нашей задаче конец необработанной части совпадает с концом массива.
For i = start + 1 To n
Анализируем очередной элемент массива.
If a(i) < min Then
Если этот элемент меньше ранее найденного минимума, то значение минимума надо обновить, записав в него значение проверяемого элемента массива.
min = a(i)
В другую переменную записываем номер найденного минимального элемента. Этот номер мы будем использовать при перестановке элементов массива.
imin = i
End If
Next
После завершения цикла поиска минимума, мы должны поменять местами найденное минимальное значение и стартовый элемент необработанной части массива. Это можно сделать двумя различными способами. Первый способ – традиционный, рассмотренный в разделе 7.12. Он предлагает использовать дополнительную переменную, в которую временно записывается значение одного из переставляемых элементов. Программный код при этом выглядит следующим образом.
Dim z As Integer
z = a(start)
a(start) = a(imin)
a(imin) = z
Второй способ применяется только при решении задачи линейной сортировки и не может быть распространен на другие случаи. На место минимального элемента из необработанной части записывается значение стартового элемента необработанной части.
a(imin) = a(start)
Затем на место стартового элемента записывается значение минимального элемента, которое хранится в переменой min.
a(start) = min