для чего необходимо описание массива
Ключевые слова:
• массив
• описание массива
• заполнение массива
• вывод массива
• обработка массива
• последовательный поиск
• сортировка
До сих пор мы работали с простыми типами данных. Для решения многих практических задач из простых типов образуют составные типы данных, так называемые структуры данных. Примером такой структуры является одномерный массив.


Решение разнообразных задач, связанных с обработкой массивов, базируется на использовании таких типовых алгоритмов, как:
• суммирование значений элементов массива;
• поиск элемента с заданными свойствами;
• сортировка массива.
2.2.1. Описание массива
Перед использованием в программе массив должен быть описан, т. е. должно быть указано имя массива, количество элементов массива и их тип. Это необходимо для того, чтобы выделить участок памяти нужного размера для хранения массива. Общий вид описания одномерного массива:
Пример
Здесь описан массив а из 10 целочисленных значений. При выполнении этого оператора в памяти компьютера будет выделено место для хранения десяти целочисленных переменных.
Массив, элементы которого имеют заданные начальные значения, может быть описан в разделе описания констант:
В этом случае не просто выделяются последовательные ячейки памяти — в них сразу же заносятся соответствующие значения.
2.2.2. Заполнение массива
Заполнять массив можно, либо вводя значение каждого элемента с клавиатуры, либо присваивая элементам некоторые значения в программе. При этом может использоваться цикл с параметром.
Например, для ввода с клавиатуры значений элементов описанного выше массива а используется следующий цикл с параметром:
Задавать значения элементов массива можно с помощью оператора присваивания. Например:
В следующем фрагменте программы организовано заполнение целочисленного массива а, состоящего из 10 элементов, случайными числами, значения которых изменяются в диапазоне от 0 до 99:
2.2.3. Вывод массива
Во многих случаях бывает полезно вывести значения элементов массива на экран. Так, если значения массива генерировались случайным образом, то необходимо знать, каков исходный массив. Также нужно знать, каким стал массив после обработки.
Значения элементов массива можно вывести в строку, разделив их пробелом:
Более наглядным является следующий вариант вывода элементов массива с пояснениями в столбик:
На основании рассмотренных примеров запишем программу, в которой осуществляется: заполнение целочисленного массива а, состоящего из 10 элементов, случайными числами, значения которых изменяются в диапазоне от 0 до 99; вывод массива а на экран.
2.2.4. Вычисление суммы элементов массива
Пример. В некотором населённом пункте я домов. Известно, сколько людей проживает в каждом из домов. Составим алгоритм подсчёта количества жителей населённого пункта.
Суммирование элементов массива осуществляется по тому же принципу, что и суммирование значений простых переменных: за счёт поочерёдного добавления слагаемых:
1) определяется ячейка памяти (переменная s), в которой будет последовательно накапливаться результат суммирования;
2) переменной s присваивается начальное значение 0 — число, не влияющее на результат сложения;
3) для каждого элемента массива из переменной s считывается её текущее значение и складывается со значением элемента массива; полученный результат присваивается переменной s.
Описанный процесс наглядно можно изобразить так:
Запишем соответствующую программу на языке Паскаль.
Сравните программы n_2 и n_3. Выделите в них общие блоки. Обратите внимание на различия.
Каким образом в программе n_3 уточнена информация, представленная в примере о домах населённого пункта?
2.2.5. Последовательный поиск в массиве
В программировании поиск — одна из наиболее часто встречающихся задач невычислительного характера.
Можно выделить следующие типовые задачи поиска:
1) найти наибольший (наименьший) элемент массива;
2) найти элемент массива, значение которого равно заданному значению.
Для решения таких задач в программе необходимо организовать последовательный просмотр элементов массива и сравнение значения очередного просматриваемого элемента с неким образцом.
Рассмотрим подробно решение задач первого типа: нахождение наибольшего (наименьшего) элемента.
Представим себе одномерный массив в виде стопки карточек, на каждой из которых написано число. Тогда идея поиска наибольшего элемента массива может быть представлена следующим образом:
1) возьмём верхнюю карточку (первый элемент массива), запомним имеющееся на карточке число (запишем его мелом на доске) как наибольшее из просмотренных; уберём карточку в сторону;
2) возьмём следующую карточку; сравним числа, записанные на карточке и на доске; если число на карточке больше, то сотрём число, записанное на доске, и запишем там то же число, что и на карточке; если же новое число не больше, то на доске оставим имеющуюся запись; уберём карточку в сторону;
3) повторим действия, описанные в п. 2, для всех оставшихся карточек в стопке.
В итоге на доске будет записано самое большое значение элемента просмотренного массива.
В программировании при обосновании корректности циклических алгоритмов используется понятие инварианта цикла.

Условие «записанное на доске число — самое большое из всех просмотренных до сих пор» является инвариантом цикла для рассмотренного алгоритма.
Так как доступ к значению элемента массива осуществляется по его индексу, при организации поиска наибольшего элемента в одномерном массиве можно искать его индекс. Обозначим искомый индекс imax. Тогда описанный выше алгоритм в сформированном нами массиве а на языке Паскаль можно записать так:
Если в массиве несколько элементов, значения которых равны максимальному значению, то данная программа найдёт первый из них (первое вхождение). Подумайте, что следует изменить в программе, чтобы в ней находился последний из максимальных элементов. Как следует преобразовать программу, чтобы с её помощью можно было найти минимальный элемент массива?
Результатом решения задачи второго типа (нахождение элемента массива, значение которого равно заданному значению) может быть:
• k — индекс элемента массива такой, что a[k] = х, где х — заданное число;
• сообщение о том, что искомого элемента в массиве не обнаружено.
Программа поиска в сформированном нами массиве а значения, равного х, может выглядеть так:
В этой программе последовательно просматриваются все элементы массива. Если в массиве несколько элементов, значения которых равны заданному числу, то программа найдёт последний из них.
Во многих случаях требуется найти первый из элементов, имеющих соответствующее значение, и дальнейший просмотр массива прекратить. Для этой цели можно использовать следующий фрагмент программы:
Здесь выполнение алгоритма будет прервано в одном из двух случаев: 1) в массиве найден первый из элементов, равный заданному; 2) все элементы массива просмотрены.
Запишите полный текст программы и выполните её на компьютере.
Зачастую требуется определить количество элементов, удовлетворяющих некоторому условию. В этом случае вводится переменная, значение которой увеличивается на единицу каждый раз, когда найден нужный элемент.
Определите, количество каких элементов подсчитывается с помощью следующего фрагмента программы.
Если требуется определить сумму значений элементов, удовлетворяющих некоторому условию, то вводят переменную, к значению которой прибавляют значение найденного элемента массива.
Определите, какому условию удовлетворяют элементы массива, значения которых суммируются с помощью следующего фрагмента программы.
Запишите полные тексты двух последних программ и выполните их на компьютере.
2.2.6. Сортировка массива

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

Вы уже встречались с сортировкой при работе с базами данных. Сейчас мы рассмотрим один из возможных вариантов 1 реализации механизма этой операции — сортировку выбором.
1 С другими способами сортировки вы познакомитесь на уроках информатики в 10-11 классах.
Сортировка выбором (например, по невозрастанию) осуществляется следующим образом:
1) в массиве выбирается максимальный элемент;
2) максимальный и первый элементы меняются местами; первый элемент считается отсортированным;
3) в неотсортированной части массива снова выбирается максимальный элемент; он меняется местами с первым неотсортированным элементом массива;
4) действия, описанные в п. 3, повторяются с неотсортированными элементами массива до тех пор, пока не останется один неотсортированный элемент (его значение будет минимальным).
Рассмотрим процесс сортировки выбором на примере массива а = <0, 1, 9, 2, 4, 3, б, 5>.
Приведём фрагмент программы, реализующий описанный алгоритм:
Здесь мы использовали один цикл внутри другого. Такая конструкция называется вложенным циклом.
Запишите полный текст программы и выполните её на компьютере для рассмотренного в примере массива а.
2.2.7. Другие структуры данных
Многие современные приложения (диалоговые, сетевые, инструментальные системы, операционные системы и др.) работают с данными, объём которых заранее не может быть ограничен определённой величиной. Предположим, разрабатывается большой программный комплекс, при работе которого в оперативной памяти будет храниться большое количество различных данных, представленных в форме массивов. Область памяти, отводимая для каждого массива, непрерывна; границы области во время выполнения программы строго фиксированы. Так как объём данных заранее неизвестен, программистам придётся указывать максимально возможные размеры используемых массивов. В результате этого для хранения всех возможных данных может оказаться недостаточно доступной памяти. При этом на практике крайне редко будут встречаться ситуации, когда каждый массив будет полностью заполнен — во многих из них часть зарезервированной памяти будет оставаться свободной. Жёсткие границы не позволяют перераспределять пустое пространство одних массивов в пользу других. Как результат — неэффективное использование оперативной памяти. Выходом в этой ситуации является замена при проектировании программы некоторых массивов на списки, которые занимают именно столько памяти, сколько действительно нужно в данный момент, и не создают никаких запасов.
Список представляет собой множество элементов, которые могут быть разбросаны операционной системой по оперативной памяти как угодно. Связь элементов списка осуществляется за счёт того, что каждый элемент списка содержит кроме данных адрес элемента, следующего за ним в списке.

В линейном списке для каждого элемента, кроме первого, есть предыдущий элемент; для каждого элемента, кроме последнего, есть следующий элемент. Таким образом, все элементы списка упорядочены (рис. 2.3).
Рис. 2.3. Линейный список
В линейном списке можно обойти все элементы, только двигаясь последовательно от текущего элемента к следующему, начиная с первого. Прямой доступ к i-му элементу невозможен; список — структура с последовательным доступом. В отличие от списка массив является структурой с произвольным доступом.
САМОЕ ГЛАВНОЕ
Массив — это совокупность фиксированного количества однотипных элементов, которым присвоено общее имя. Доступ к отдельному элементу массива осуществляется по его номеру (индексу).
Перед использованием в программе массив должен быть описан. Общий вид описания одномерного массива:
Заполнять массив можно, либо вводя значение каждого элемента с клавиатуры, либо присваивая элементам некоторые значения в программе. При заполнении массива и его выводе на экран используется цикл с параметром.
При решении разнообразных задач, связанных с обработкой массивов, используются такие типовые алгоритмы, как: суммирование элементов массива; поиск элемента с заданными свойствами; сортировка массива.
Вопросы и задания
1. Ознакомьтесь с материалами презентации к параграфу, содержащейся в электронном приложении к учебнику. Какими слайдами вы могли бы дополнить презентацию?
2. Может ли массив одновременно содержать целые и вещественные значения?
3. Для чего необходимо описание массива?
4. Что вы можете сказать о массиве, сформированном следующим образом?
а) for i:=l to 10 do a[i]:=random(101)-50;
б) for i:=l to 20 do a[i]:=i;
в) for i:=l to 5 do a[i]:=2*i-l;
5. Выполните на компьютере программу решения задачи, рассмотренной в примере пункта 2.2.4. Считайте количество жильцов дома случайным числом из диапазона от 50 до 200 человек, а число домов n = 30.
6. Рядом с вами находятся две корзины. Первая наполнена яблоками разных размеров, вторая — пустая.
Шаг 1. Вы берёте любое яблоко из первой корзины и кладёте его на стол перед собой.
Шаг 2. Вы достаёте следующее яблоко из первой корзины и выполняете сравнение:
— если яблоко в руках больше, чем яблоко на столе, то вы опускаете яблоко, которое у вас в руках, во вторую корзину;
— если яблоко в руках меньше яблока на столе, вы кладёте яблоко на стол, а яблоко, которое лежало на столе, перекладываете во вторую корзину.
Вы повторяете шаг 2 до тех пор, пока первая корзина не опустеет.
Какое яблоко окажется на столе в самом конце? Попытайтесь сформулировать, что является инвариантом цикла в приведённом алгоритме. Сформулируйте условие задачи с использованием терминологии, рассмотренной в этом параграфе.
7. Напишите программу, которая вычисляет среднюю за неделю температуру воздуха. Исходные данные вводятся с клавиатуры.
8. Дан массив из десяти целых чисел. Напишите программу подсчёта количества элементов этого массива, имеющих максимальное значение.
9. В классе 20 учеников писали диктант по русскому языку. Напишите программу, подсчитывающую количество двоек, троек, четвёрок и пятёрок, полученных за диктант.
10. Объявлен набор в школьную баскетбольную команду. Известен рост каждого из п учеников, желающих попасть в эту команду. Составьте алгоритм подсчёта количества претендентов, имеющих шанс попасть в команду, если рост игрока команды должен быть не менее 170 см. Запишите на языке Паскаль программу. Считайте рост претендента в команду случайным числом из диапазона от 150 до 200 см, а число претендентов n = 50.
11. В целочисленных массивах а и b содержатся длины катетов десяти прямоугольных треугольников (а[i] — длина первого катета, b[i] — длина второго катета i-ro треугольника). Напишите программу, которая по имеющимся данным определит треугольник с наибольшей площадью и выведет его номер, длины катетов и площадь. Предусмотрите случай, когда таких треугольников несколько.
12. Занесите информацию о десяти европейских странах в массивы n (название страны), k (численность населения), s (площадь страны). Напишите программу, выводящую названия стран в порядке возрастания плотности их населения.
13. Найдите информацию о таких частных случаях списка, как стек и очередь. Подготовьте короткое сообщение.
Электронное приложение к уроку
![]() | ![]() | ![]() |
| Файлы | Материалы урока | Ресурсы ЭОР |
Cкачать материалы урока
Дадим формальное определение:
массив — структурированный тип данных, состоящий из некоторого числа элементов одного типа.
Для того чтобы разобраться в возможностях и особенностях обработки массивов в программах на ассемблере, нужно ответить на следующие вопросы:
· Как описать массивв программе?
· Как инициализировать массив, то есть как задать начальные значения его элементов?
· Как организовать доступк элементам массива?
· Как организовать массивыс размерностью более одной?
· Как организовать выполнениетиповых операций с массивами?
Описание и инициализация массива в программе
Специальных средств описания массивов в программах ассемблера, конечно, нет. При необходимости использовать массив в программе его нужно моделировать одним из следующих способов:
1. Перечислением элементов массива в поле операндов одной из директив описания данных. При перечислении элементы разделяются запятыми. К примеру:
;массив из 5 элементов.Размер каждого элемента 4 байта:
2. Используя оператор повторения dup. К примеру:
;массив из 5 нулевых элементов.
;Размер каждого элемента 2 байта:
Такой способ определения используется для резервирования памяти с целью размещения и инициализации элементов массива.
3. Используя директивы labelиrept. Пара этих директив может облегчить описание больших массивов в памяти и повысить наглядность такого описания. Директиваreptотносится к макросредствам языка ассемблера и вызывает повторение указанное число раз строк, заключенных между директивой и строкой endm. К примеру, определим массив байт в области памяти, обозначенной идентификаторомmas_b. В данном случае директиваlabelопределяет символическое имяmas_b, аналогично тому, как это делают директивы резервирования и инициализации памяти. Достоинство директивыlabelв том, что она не резервирует память, а лишь определяет характеристики объекта. В данном случае объект — это ячейка памяти. Используя несколько директивlabel, записанных одна за другой, можно присвоить одной и той же области памяти разные имена и разный тип, что и сделано в следующем фрагменте:
В результате в памяти будет создана последовательность из четырех слов f1f0. Эту последовательность можно трактовать как массив байт или слов в зависимости от того, какое имя области мы будем использовать в программе —mas_bилиmas_w.
4. Использование цикла для инициализации значениями области памяти, которую можно будет впоследствии трактовать как массив.
5. Посмотрим на примере листинга 2, каким образом это делается.
Листинг 2 Инициализация массива в цикле
mes db 0ah,0dh,’Массив- ‘,’$’
mas db 10 dup (?) ;исходный массив
xor ax,ax ;обнуление ax
mov cx,10 ;значение счетчика цикла в cx
mov si,0 ;индекс начального элемента в cx
go: ;цикл инициализации
mov mas[si],bh ;запись в массив i
inc si ;продвижение к следующему элементу массива
loop go ;повторить цикл
;вывод на экран получившегося массива
mov ah,02h ;функция вывода значения из al на экран
add dl,30h ;преобразование числа в символ
mov ax,4c00h ;стандартный выход
end main ;конец программы
Доступ к элементам массива
При работе с массивами необходимо четко представлять себе, что все элементы массива располагаются в памяти компьютера последовательно.
Само по себе такое расположение ничего не говорит о назначении и порядке использования этих элементов. И только лишь программист с помощью составленного им алгоритма обработки определяет, как нужно трактовать эту последовательность байт, составляющих массив. Так, одну и ту же область памяти можно трактовать как одномерный массив, и одновременно те же самые данные могут трактоваться как двухмерный массив. Все зависит только от алгоритма обработки этих данных в конкретной программе. Сами по себе данные не несут никакой информации о своем “смысловом”, или логическом, типе. Помните об этом принципиальном моменте.
Эти же соображения можно распространить и на индексы элементов массива. Ассемблер не подозревает об их существовании и ему абсолютно все равно, каковы их численные смысловые значения.
Для того чтобы локализовать определенный элемент массива, к его имени нужно добавить индекс. Так как мы моделируем массив, то должны позаботиться и о моделировании индекса. В языке ассемблера индексы массивов — это обычные адреса, но с ними работают особым образом. Другими словами, когда при программировании на ассемблере мы говорим об индексе, то скорее подразумеваем под этим не номер элемента в массиве, а некоторый адрес.
Давайте еще раз обратимся к описанию массива. К примеру, в программе статически определена последовательность данных:
Пусть эта последовательность чисел трактуется как одномерный массив. Размерность каждого элемента определяется директивой dw, то есть она равна2байта. Чтобы получить доступ к третьему элементу, нужно к адресу массива прибавить6. Нумерация элементов массива в ассемблере начинается с нуля.
То есть в нашем случае речь, фактически, идет о 4-м элементе массива — 3, но об этом знает только программист; микропроцессору в данном случае все равно — ему нужен только адрес.
В общем случае для получения адреса элемента в массиве необходимо начальный (базовый) адрес массива сложить с произведением индекса (номер элемента минус единица) этого элемента на размер элемента массива:
база + (индекс*размер элемента)
Архитектура микропроцессора предоставляет достаточно удобные программно-аппаратные средства для работы с массивами. К ним относятся базовые и индексные регистры, позволяющие реализовать несколько режимов адресации данных. Используя данные режимы адресации, можно организовать эффективную работу с массивами в памяти. Вспомним эти режимы:
· индексная адресация со смещением — режим адресации, при котором эффективный адрес формируется из двух компонентов:
o постоянного (базового)— указанием прямого адреса массива в виде имени идентификатора, обозначающего начало массива;
o переменного (индексного)— указанием имени индексного регистра.
;поместить 3-й элемент массива mas в регистр ax:
· базовая индексная адресация со смещением — режим адресации, при котором эффективный адрес формируется максимум из трех компонентов:
o постоянного(необязательный компонент), в качестве которой может выступать прямой адрес массива в виде имени идентификатора, обозначающего начало массива, или непосредственное значение;
o переменного (базового)— указанием имени базового регистра;
o переменного (индексного)— указанием имени индексного регистра.
Этот вид адресации удобно использовать при обработке двухмерных массивов. Пример использования этой адресации мы рассмотрим далее при изучении особенностей работы с двухмерными массивами.
Напомним, что в качестве базового регистра может использоваться любой из восьми регистров общего назначения. В качестве индексного регистра также можно использовать любой регистр общего назначения, за исключением esp/sp.
Микропроцессор позволяет масштабировать индекс. Это означает, что если указать после имени индексного регистра знак умножения “*” с последующей цифрой 2, 4 или 8, то содержимое индексного регистра будет умножаться на 2, 4 или 8, то есть масштабироваться.
Применение масштабирования облегчает работу с массивами, которые имеют размер элементов, равный 2, 4 или 8 байт, так как микропроцессор сам производит коррекцию индекса для получения адреса очередного элемента массива. Нам нужно лишь загрузить в индексный регистр значение требуемого индекса (считая от 0). Кстати сказать, возможность масштабирования появилась в микропроцессорах Intel, начиная с модели i486. По этой причине в рассматриваемом здесь примере программы стоит директива .486. Ее назначение, как и ранее использовавшейся директивы.386, в том, чтобы указать ассемблеру при формировании машинных команд на необходимость учета и использования дополнительных возможностей системы команд новых моделей микропроцессоров.
В качестве примера использования масштабирования рассмотрим листинг 3, в котором просматривается массив, состоящий из слов, и производится сравнение этих элементов с нулем. Выводится соответствующее сообщение.
Листинг 3. Просмотр массива слов с использованием
.data ;начало сегмента данных
mes1 db ‘не равен 0!$’,0ah,0dh
mes2 db ‘равен 0!$’,0ah,0dh
mas dw 2,7,0,0,1,9,3,6,0,8 ;исходный массив
.486 ;это обязательно
mov ds,ax ;связка ds с сегментом данных
xor ax,ax ;обнуление ax
mov cx,10 ;значение счетчика цикла в cx
mov esi,0 ;индекс в esi
mov dx,mas[esi*2] ;первый элемент массива в dx
cmp dx,0 ;сравнение dx c 0
je equal ;переход, если равно
not_equal: ;не равно
mov ah,09h ;вывод сообщения на экран
mov ah,02h ;вывод номера элемента массива на экран
inc esi ;на следующий элемент
dec cx ;условие для выхода из цикла
jcxz exit ;cx=0? Если да — на выход
jmp compare ;нет — повторить цикл
mov ah,09h ;вывод сообщения mes3 на экран
mov ah,09h ;вывод сообщения mes2 на экран
inc esi ;на следующий элемент
dec cx ;все элементы обработаны?
mov ax,4c00h ;стандартный выход
end main ;конец программы
Еще несколько слов о соглашениях:
· Если для описания адреса используется только один регистр, то речь идет о базовой адресациии этот регистр рассматривается какбазовый:
;переслать байт из области данных, адрес
которой находится в регистре ebx:
· Если для задания адреса в команде используется прямая адресация(в виде идентификатора) в сочетании с одним регистром, то речь идет обиндексной адресации. Регистр считаетсяиндексным, и поэтому можно использовать масштабирование для получения адреса нужного элемента массива:
;сложить содержимое eax с двойным словом в памяти
;по адресу mas + (ebx)*4
· Если для описания адреса используются два регистра, то речь идет о базово-индексной адресации. Левый регистр рассматривается как базовый, а правый — как индексный. В общем случае это не принципиально, но если мы используем масштабирование с одним из регистров, то он всегда являетсяиндексным. Но лучше придерживаться определенных соглашений.
· Помните, что применение регистров ebp/bpиesp/spпо умолчанию подразумевает, что сегментная составляющая адреса находится в регистреss.
Заметим, что базово-индексную адресацию не возбраняется сочетать с прямой адресацией или указанием непосредственного значения. Адрес тогда будет формироваться как сумма всех компонентов.
;адрес операнда равен [mas+(ebx)+(ecx)*2]
;адрес операнда равен [(ebx)+8+(ecx)*4]
Но имейте в виду, что масштабирование эффективно лишь тогда, когда размерность элементов массива равна 2, 4 или 8 байт. Если же размерность элементов другая, то организовывать обращение к элементам массива нужно обычным способом, как описано ранее.
Рассмотрим пример работы с массивом из пяти трехбайтовых элементов (листинг 4). Младший байт в каждом из этих элементов представляет собой некий счетчик, а старшие два байта — что-то еще, для нас не имеющее никакого значения. Необходимо последовательно обработать элементы данного массива, увеличив значения счетчиков на единицу.
Листинг 4. Обработка массива элементов с нечетной длиной
MODEL small ;модель памяти
STACK 256 ;размер стека
.data ;начало сегмента данных
N=5 ;количество элементов массива
mas db 5 dup (3 dup (0))
main: ;точка входа в программу
xor ax,ax ;обнуление ax
mov dl,mas[si] ;первый байт поля в dl
inc dl ;увеличение dl на 1 (по условию)
mov mas[si],dl ;заслать обратно в массив
add si,3 ;сдвиг на следующий элемент массива

























