Автор работы: Пользователь скрыл имя, 26 Октября 2011 в 20:44, лекция
Массив — это структура данных, которую можно рассматривать как набор переменных одинакового типа, имеющих общее имя. Массивы бывают одномерные и многомерные. Доступ к элементам массива осуществляется по индексу.
Массив в программах должен быть объявлен. Это делается следующим образом:
<имя>: array [<н_индекс>..<в_индекс>] of <тип>;
Массив —
это структура данных, которую можно рассматривать
как набор переменных одинакового типа,
имеющих общее имя. Массивы бывают одномерные
и многомерные. Доступ к элементам массива
осуществляется по индексу.
Массив в программах должен быть объявлен. Это делается следующим образом:
<имя>: array [<н_индекс>..<в_индекс>] of <тип>;
Здесь <имя> — имя переменной-массива, array — зарезервированное слово языка Паскаль, обозначающее, что переменная является массивом, <н_индекс> и <в_индекс> — соответственно нижний и верхний индексы, которыми являются целые константы, определяющие диапазон изменения индексов элементов одномерного массива (то есть размер массива), <тип> — тип элементов массива.
Под выводом массива понимается вывод всех значений элементов массива.
Под вводом массива понимается получение от пользователя во время работы программы значений элементов массива.
Массив можно задать, используя константы и счетчик случайных чисел, а также вычислять элементы массива по заданным формулам или просто вводить их последовательно.
Для ввода
больших массивов удобно использовать
специальную функцию-генератор
Существуют типовые алгоритмы обработки одномерных массивов. Приведем типовые фрагменты программ на языке Паскаль.
Поэлементный ввод:
for i:=1 to n do
readln(mas[i]);
Вывод массива в строку:
for i:=1 to n do
write(mas[i]);
Вывод массива в столбец:
for i:=1 to n do
writeln(mas[i]);
Поиск минимального элемента массива:
min:=1;
for i:=2 to n do
if mas[i]<mas[min] then min:=i;
write('Минимальный элемент массива = ',mas[min]);
Перестановка элементов на четных и нечетных местах:
for i:=1 to n div 2 do
begin
p:=mas[2*i-1];
mas[2*i-1]:=mas[2*i];
mas[2*i]:=p
end;
Объединение двух одномерных массивов с поочередной выборкой:
for i:=1 to n do
begin
mas[2*i-1]:=a[i];
mas[2*i]:=b[i]
end;
Перестановку элементов массива, состоящего из значений 0, 1 и 2, так чтобы расположить сначала все нули, затем все единицы и, наконец, все двойки, можно выполнить без применения дополнительного массива. Можно просто подсчитать количество значений 0, 1, 2 и заполнить массив заново требуемым образом:
var a: array [1..50] of integer;
i,nul,ed,dva,n: integer;
BEGIN
n:=10;
randomize;
for i:=1 to n do
begin
a[i]:=random(3);
write(a[i]:4)
end;
writeln;
nul:=0; ed:=0; dva:=0;
for i:=1 to n do
case a[i] of
0: inc(nul);
1: inc(ed);
2: inc(dva);
end;
for i:=1 to nul do a[i]:=0;
for i:=nul+1 to ed+nul+1 do a[i]:=1;
for i:=ed+nul+1 to n do a[i]:=2;
for i:=1 to n do
write(a[i]:4);
END.
Смена всех элементов Xi и Yi (i = 1, …, n) в однотипных массивах X и Y размерностью n без использования промежуточных величин:
for i:=1 to n do
begin
x[i]:=x[i]+y[i];
y[i]:=x[i]-y[i];
x[i]:=x[i]-y[i]
end;
Практически каждый программист в своей работе сталкивается с необходимостью сортировать данные, иначе говоря, упорядочивать их определенным образом. Существует целый класс алгоритмов сортировки.
Рассмотрим несколько методов сортировки одномерных массивов.
Пусть дан массив из пяти целых чисел. Отсортировать его по возрастанию методом прямого выбора (перебором).
Алгоритм сортировки этим методом будет выглядеть следующим образом.
Теперь без труда можно написать программу на нужном языке.
Отсортируем тот же массив из пяти целых чисел методом прямого обмена (его называют еще «пузырьковым» методом, или методом перестановки соседних элементов).
Организовать такую перестановку можно следующим образом.
Ниже
показан соответствующий
var a: array [1..5] of integer;
i,j,n,c: integer;
BEGIN
n:=5;
randomize;
for i:=1 to n do
begin
a[i]:=random(15)-3;
write(a[i]:4)
end;
writeln;
for i:=1 to n-1 do
for j:=1 to n-1 do
if a[j]>a[j+1] then
begin
c:=a[j];
a[j]:=a[j+1];
a[j+1]:=c
end;
for i:=1 to n do
write(a[i]:4)
END.
Еще один метод сортировки массива был предложен Д. Л. Шеллом в 1959 году. Основная идея алгоритма заключается в том, чтобы вначале устранить массовый беспорядок в массиве, сравнивая далеко отстоящие друг от друга элементы, и постепенно уменьшить этот интервал до единицы. Это означает, что на последних шагах сортировка сводится просто к перестановкам соседних элементов (если, конечно, такие перестановки необходимы). Фрагмент программы, выполняющий сортировку массива из пяти элементов методом Шелла, выглядит следующим образом:
const n=5;
var a: array[1..n] of integer;
c,k,i,j: integer;
BEGIN
randomize;
for i:=1 to n do
begin
a[i]:=random(15)-3;
write(a[i]:4)
end;
k:=n div 2; {вычисление шага}
while k>0 do begin
for j:=n-k downto 1 do begin
i:=j;
while i<=n-k do begin
if a[i]>a[i+k] then begin
c:=a[i];
a[i]:=a[i+k];
a[i+k]:=c
end;
i:=i+k;
end
end;
k:=k div 2
end;
writeln;
for i:=1 to n do
write(a[i]:4);
END.
Пример 1. Составить программу, которая осуществляет перестановку одномерного массива без использования дополнительного массива.
Листинг 1.
const n=20;
var a: array [1..n] of integer;
i,c: integer;
BEGIN
randomize;
for i:=1 to n do
begin
a[i]:=random(30)-4;
write(a[i]:4)
end;
for i:=1 to n div 2 do
begin
c:=a[i];
a[i]:=a[n-i+1];
a[n-i+1]:=c
end;
writeln;
for i:=1 to n do
write(a[i]:4);
writeln
END.
Пример 2. Найти сумму всех элементов массива A, больших заданного числа.
Листинг 2.
var a: array [1..100] of integer;
i,ch,n,s: integer;
BEGIN
randomize;
write('Введите размер массива -> ');
readln(n);
for i:=1 to n do
begin
a[i]:=random(20)-5;
write(a[i]:4)
end;
writeln;
write('Введите число -> ');
readln(ch);
s:=0;
for i:=1 to n do
if a[i]>ch then s:=s+a[i];
writeln('Сумма элементов, больших числа ',ch,' равна ',s)
END.
Пример 3. Заполнить массив, применив для его заполнения следующее значение: .
Листинг 3.
const n=10;
var a: array [1..n] of real;
i: integer;
x: real;
BEGIN
write('Введите значение х -> ');
readln(x);
for i:=1 to n do
begin
a[i]:=x*sqr(i)/(i+x);