4752

Использование массивов при обработке больших объемов информации

Лекция

Информатика, кибернетика и программирование

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

Русский

2012-11-25

979.28 KB

13 чел.

Массивы

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

В линейной таблице каждому ее элементу соответствует порядковый номер. Для элемента прямоугольной таблицы должны быть указаны два номера: номер по вертикали (номер строки) и номер по горизонтали (номер столбца).

В высшей математике табличные величины называют соответственно векторами и матрицами.

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

Имя массива образуется по общему правилу образования имен, т. е. представляет собой идентификатор, например A, Bl, C8 и т. д. Однако оно не должно совпадать с именем ни одной простой переменной, используемой в той же программе.

Работа с массивом сводится к действиям над его элементами. Для того чтобы указать, какой элемент в данный момент используется, достаточно задать его порядковый номер, который приписывается к имени соответствующего массива. Таким образом, элементы массива обозначаются переменной с индексами. Запись переменной с индексами состоит из имени массива и следующего за ним в квадратных скобках списка индексов, например А[1], A[I], B1[K], C8[I, J], С8[2, 1]

Индексы определяют положение элемента в массиве. Число индексов определяет размерность массива, т.е. форму его компоновки: одномерный, двумерный и т. д. Одномерный массив соответствует линейной таблице. Его элемент обозначается переменной с одним индексом: A[l], A[I] —соответственно первый и i-й элементы одномерного массива А;

Двумерный массив описывает в программе прямоугольную таблицу. Его элементы обозначаются переменной с двумя индексами: C8[I, J], С8[2, 1], где первый индекс обозначает номер строки, а второй — номер столбца.

Таким образом, для обращения к конкретному элементу массива необходимо указать имя массива и значения индексов.

Для записи элементов массива в память компьютера нужно выделить для их хранения необходимое количество (массив) ячеек памяти, которое определяется размером массива. Размеры массива задаются границами изменения индексов по каждому измерению (минимальное и максимальное значение индекса).

По умолчанию применяется так называемая нумерация с нулевой базой, т.е. элементы массива нумеруются, начиная с 0.

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

Описание статического массива определяет имя, размер массива и тип данных, которые в нем хранятся. Формат описания в разделе переменных:

Var 

<имя_массива>: array <[тип_индекса]> of <тип_данных>;

 

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

Например

Var
A : array [1..10] of real;

Описывается одномерный массив вещественных чисел A, который максимально может состоять из 10 элементов. Нижняя граница индекса равна 1, верхняя – 10.

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

Динамические массивы отличаются от обычных статических тем, что для них не объявляется заранее длина – число элементов. Объявление такого массива содержит только имя и тип элементов.

Var  <имя_массива>: array of <тип_данных>.

При объявлении динамического массива место под него не отводится. Прежде чем использовать такой массив, надо задать в программе его размер процедурой SetLength. Параметры данной процедуры - количество элементов по каждой размерности. Например, SetLength(10,20) - для двумерного массива.

Линейный (одномерный) массив – это просто список элементов данных.

Примеры описания одномерных массивов:

var B : array [0..5] of real
 
R : array [1..34] of char;
 
N : array [’A’..’Z’] of integer;
 
M : array of integer; {динамический массив}

Для доступа к элементу массива следует указать имя массива с последующим числом (индексом), заключенном в квадратные скобки.

Элементы массива можно использовать в любом выражении точно также как и значение константы или переменной.

Напримерa[0]=11.2; a[1]=10.2; a[3]=22.1; a[4]=1.1;
Y = a[0] * 2 – a[1];
 

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

Пример.

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

 

Компоненты приложения

Окно формы приложения

Edit

Label

CheckBox

Button

GroupBox 

Краткая характеристика компоненты GroupBox

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

Свойства панели GroupBox

Caption 

Задает надпись для рамки, выделяющей группу объединенных компонентов.

Если компоненты, размещаемые на панели, оказываются под панелью и не отображаются, то следует выделить панель и выбрать в контекстном меню команду ControlSend to Back (Порядок → На задний план).

Программный код приложения

Обратите внимание, что размер массива N и сам массив M описаны в разделе объявления типов, констант, переменных, функций и процедур, доступном для всех модулей приложения, т.к. эти переменные  будут использоваться в разных событийных процедурах: в процедуре заполнения массива случайными числами TForm1.Button1Click и процедуре обработки массива  TForm1.Button2Click.

Все подзадачи решаются за один просмотр элементов массива.

Например, поиск минимального элемента в массиве. Вначале устанавливается текущий минимум по нулевому элементу массива min:=M[0]. Затем начинается просмотр элементов массива: выбирается очередной элемент M[i] и сравнивается с min. Если элемент M[i] меньше текущего min, то выполняется переприсваивание min:=M[i].

implementation

{$R *.dfm}

const

  Nmax=100;

var

 N:integer;

 M:array [0..Nmax] of integer; // Описание массива целых чисел

procedure TForm1.BitBtn1Click(Sender: TObject);

var

 i:integer;

begin

 Randomize;

 N:=StrToInt(Form1.LabeledEdit1.Text);  // Число элементов массива

 Form1.Edit5.Text:=''; //  Очищение окна вывода массива

 For i:=0 to N-1 do

   begin                                //Заполнение массива случайными

     M[i]:=Round(Sin(Random(10))*10);   //целыми числами [-10;+10]

     Form1.Edit5.Text:=Form1.Edit5.Text+ //Вывод элементов массива

     '  '+IntToStr(M[i]);

   end;

end;

procedure TForm1.BitBtn2Click(Sender: TObject);

var

 i:integer;

 Sum,Min,CountP,Sum1,Kol:integer;

begin

 if Form1.CheckBox3.Checked then Min:=M[0];

 Form1.Edit1.Text:='';

 Form1.Edit2.Text:='';

 Form1.Edit3.Text:='';

 Form1.Edit4.Text:='';

 Sum:=0;

 Kol:=0;

 Sum1:=0;

 CountP:=0;

 For i:=0 to N-1 do

   begin

     if Form1.CheckBox1.Checked then

     Sum:=Sum+M[i];                  // Сумма всех элементов

     if Form1.CheckBox2.Checked then

     if M[i]>0 then CountP:=CountP+1; //Количество положительных эл-тов

     if Form1.CheckBox3.Checked then

     if Min>M[i] then Min:=M[i];     // Минимальный элемент

     if Form1.CheckBox4.Checked then

       if (M[i] mod 5 =0 ) and (M[i]<>0) then

         begin                       

           inc(Kol);                 //Количество и

           Sum1:=Sum1+M[i];          //сумма элеметов кратных 5

         end;

   end;                  // Вывод результатов расчета

 if  Form1.CheckBox1.Checked then Form1.Edit1.Text:=IntToStr(Sum);

 if  Form1.CheckBox2.Checked then Form1.Edit2.Text:=IntToStr(CountP);

 if  Form1.CheckBox3.Checked then Form1.Edit3.Text:=IntToStr(Min);

 if  Form1.CheckBox4.Checked then Form1.Edit4.Text:=FloatToStr(Sum1/Kol);

end;

end.

Линейная сортировка массива

Существует множество алгоритмов для сортировки массивов. Ниже рассмотрены два из них: сортировка выбором и методом пузырька.

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

Суть этого метода очень проста и может быть описана так:

1.        В последовательности из n элементов выбирается наименьший (наибольший) элемент;

2.        Меняется местом с первым;

3.        Далее процесс повторяется с оставшимися n-1 элементами, затем с оставшимися n-2 элементами и т.д., до тех пор пока не останется один самый большой (маленький) элемент.

Для реализации этого алгоритма необходимо использовать два вложенных цикла с параметром For. Внешний цикл (по i) предназначен для последовательного фиксирования элементов массива, внутренний (по j) - осуществляет поиск минимального (максимального) и его позиции в неотсортированной части массива. После выхода из внутреннего цикла следует перестановка элементов. Последний элемент во внешнем цикле не рассматривается: он сам встанет на свое место.

Окно формы приложения

Программный код процедуры сортировки выбором

Сортировка методом пузырька

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

Фрагмент программного кода сортировки методом пузырька

Уплотнение массива

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

Пример. Удалить из сформированного массива числа, кратные трем.

Фрагмент программного кода уплотнения массива

Обратите внимание: на место удаленного i-го элемента переписывается i+1-ый элемент, на место i+1-го элемента переписывается i+2-ой элемент и т.д.

Вставка элемента в массив

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

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

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

Фрагмент программного кода

Изменение положения элементов на некотором отрезке

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

Пример.В одномерном массиве, состоящем из n элементов, изменить порядок следования значений элементов на обратный от позиции n1 до позиции n2 (n1<n2<n). 

Фрагмент программного кода

В приведенном фрагменте программы цикл выполняется лишь до половины диапазона (от n1 до (n1+n2) div 2)  иначе в массиве ничего не изменится.

Кольцевой сдвиг элементов массива

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

Пример. В одномерном массиве, состоящем из n элементов произвести кольцевой сдвиг элементов на k позиций. Значение k задается, оно может быть как положительным, так и отрицательным, но целым и лежать в диапазоне:  (n-1) < k < n-1

 Фрагмент программного кода

Ошибки при использовании массивов

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

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

Например:

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

В программы, в которых возможны ошибки времени выполнения вследствие неправильного ввода исходных данных, следует добавлять инструкции проверки вводимых данных. Например так,

 


 

А также другие работы, которые могут Вас заинтересовать

10059. Характеристика экспертных процедур 42.5 KB
  Характеристика экспертных процедур Эвристические методы или методы экспертных оценок методы использующие результаты опыта и интуицию. Особенностью эвристических методов и моделей является отсутствие строгих математических доказательств оптимальности получаемы...
10060. Общая схема экспертизы 40.5 KB
  Общая схема экспертизы Общая схема экспертных вопросов включает следующие основные этапы: подбор экспертов и формирование экспертных групп, формирование опросов и составление анкет, работу с экспертами, формирование правил определения суммарных оценок н
10061. Риски в окружающем нас мире 30 KB
  Риски в окружающем нас мире. Риски и связанная с ними неопределенность постоянно окружают нас в реальной действительности. Поэтому мы интуитивно понимаем смысл этих понятий без дополнительных объяснений со стороны знающих людей толкового словаря или учебников. Доста...
10062. Риск и неопределенность 24.5 KB
  Риск и неопределенность. Деятельность субъекта хозяйствования постоянно сопряжена с неопределенностью ситуаций которые обусловливают принятие возможных альтернативных решений и действий в условиях риска. Возникают также ситуации связанные с риском когда любой ал...
10063. Покрытие убытка на основе поддержки государственных и/или муниципальных органов 25 KB
  Покрытие убытка на основе поддержки государственных и/или муниципальных органов Метод покрытия убытка на основе поддержки государственных и/или муниципальных органов Budget support означает снижение участия самой фирмы в возмещении ущерба за счет полной или частичной пер
10064. Объективное и субъективное понимание риска 26.5 KB
  Объективное и субъективное понимание риска. Исходя из вышесказанного можно выделить два взаимосвязанных компонента категории риска: объективный и субъективный. Риск с объективной позиции отражает ту или иную неопределенность в среде активности субъекта. Как субъект
10065. Основные методы снижения экономического риска и их характеристика 59 KB
  Основные методы снижения экономического риска и их характеристика В системе управления риском важная роль принадлежит правильному выбору мер предупреждения и минимизации риска которые в значительной степени определяют ее эффективность. Следует отметить что в миро...
10066. Сущность хозяйственного риска, предмет, объекты и субъекты хозяйственного риска 27 KB
  Сущность хозяйственного риска предмет объекты и субъекты хозяйственного риска. Таким образом хозяйственный риск это решение или действие в условиях неопределенности связанное с производством продукции товаров услуг их реализацией товарноденежными и финансовы...
10067. Элементы хозяйственного риска, формы их проявления 27.5 KB
  Элементы хозяйственного риска формы их проявления. Осознание степени риска происходит благодаря выделению в рискованной ситуации основных элементов характеристика взаимосвязи и взаимодействия которых составляет сущность и содержание хозяйственного риска а именн...