Тема 5

Структурные переменные: одномерные массивы. Задание типа одномерного массива: тип индекса, тип компонента, алгоритмы и программы обработки одномерных массивов: поиск элементов массива по заданным критериям, определение максимального и минимального элементов массива и их индексов, вставка, удаление, сдвиг элементов массива. Решение задач сортировки, бинарный поиск, преобразование массивов, формирование массивов по заданным критериям, вычислительные задачи над элементами массивов.

Структурные переменные.

Переменные или константы структурного типа состоят из других компонентов…

Выделяют следующие структурные типы

Массивы (матрицы)

Строки

Записи

Множества

Каждое значение этих типов представляет собой структуру из множества образовавших её компонентов. Для описания её структуры используется иерархическое дерево.

Полная переменная

компоненты





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

А – структурная переменная

1 2 3 4 n (количество компонент)

Помимо типа компонент необходимо задавать их порядок и число. Компонента определяется по её номеру. Память под компоненты выделяется в соответствии в последовательных участках. Под каждую компоненту в соответствии с типом. Нет памяти – нет переменной.

Массивы бывают статические и динамические. Для статических массивов память выделяется одни раз, в соответствии с его типом после объявления переменной в var. Под динамические массивы память выделяется во время выполнения программы путём вызова процедуры setlength. В случае динамические массивов память можно освобождать.

Type

Задание типа массива необходимо указать тип индекса, который задаёт номер и количество. Тип индекса – тип диапазон.

<объявление типа массива>::=<имя типа (идентификатор)>=array[<тип индекса>]_of_<тип компоненты>.

<тип индекса>::=<диапазон>::=const1...const2

Массив – упорядоченный набор компонент n –типа, который характеризуется числом, нумерацией, именем компонент. После объявления типа, в разделе var объявляют полные переменные типа массив. (В Delphi имя типа начинается с ).

Const nmax=100;

Type

Tmas_r=array[0..nmax] of real;

Tmas_i=array[0..nmax] of integer;

Tmas_c=array[0..nmax] of char;

Tmas1=array[‘a’..’z’] of integer;

Var a,b,x,z: Tmas_r;

Ind1,ind2:Tmas_i;

I,j,l,m,n:integer

// объявление статических массивов. В соответствии с типом под переменные выделяется память.



Динамический массив.

Объявление динамического массива

Tmasd=array of real;

Задание массива. Массив можно ввести, смоделировать, задать датчиком случайных чисел. Прежде чем вводить массив мы задать реальное количество n. Обращение к отдельному элементу осуществляется по индексу. <Имя полной переменной>[<индекс>]

A[i] a[0] a[2*i] a[2*i+1]

//раздел операторов

Begin

Readln(n) //n=5;

For i:=0 to n-1 do

Read(a[i]);

Readln;

Writeln(‘массив’);

For i:=0 to n-1 do

Write(a[i]:15:5,’ ‘);

Writeln;

Моделированные массивы.

Задачи

  1. Вычисление суммы произведений по условию и без

  2. Поиск вхождения элемента в массив

  3. Поиск максимального и минимального с условием и без ( формирование из одного массива нескольких)

  4. Слияние массивов в один

  5. Сортировка массива по условию и без

Фрагмент программы для вычисления среднего значения элементов массива, лежащих в (xn,xk).

Введём перемену S:=0

Алгоритм

В цикле по I просматриваем массив, проверяем, что текущий a[i] принадлежит заданному диапазону. В этом случае увеличиваем значение суммы и счётчик количества

S:=0 k:=0

For i:=0 to n-1 do

If (a[i]> xn) and a[i]< xk then

Begin S:=s+a[i];

K:=k=1;

End;

If K<>0 then S:=S/k;

Перепишем элементы в другой массив b. В этом случае k- индекс элемента второго массива. А на выходе k- количество элементов нового массива.

S:=0;

K:=0;

For i:=0 to n-1 do

If (a[i]> xn) and a[i]< xk then

B[k]:=a[i];

K:=k+1;

End.

Вывод нового массива

If k<>0 then

For i:=0 to k do

Writeln (b[i]);

Проверка вхождения элемента в массив

  1. Элемент входит один раз

  2. Ни разу

  3. Много раз

Найти k

K:=0

For i:=0 to n-1 do

If a[i]=obr then

K:=k=1;

Abs(a[i]-obr)<0.1E-10;

Если K>0, то надо найти первое и последнее вхождение. Нахождение первого вхождения.

K:=1;

Read(obr);

For i:=0 to n-1 do

If abs(a[i-obr])<0.1E-10 then

Begin K:=I;

Break;

End;

If k<>1 then Writeln(k);

Сформируем массив в котором будут индексы элементов исходного массива совпадающие с заданным. Индекс второго массива изменяем до переменной k.

K:=1;

For i:=0 to n-1 do

If abs(a[i]-obr)<0.1E-10 then

Begin

K:=k+1;

ind[k]:=I;

end;

Максимальный элемент массива и его индекс

Max:real;

Imax:integer;

Max:=a[imax]

// добавить в раздел объявлений

До входа в цикл max и его индекс принимаем равными первому элементу.

В цикле просматриваем от i:=0 до i-1.

Сравниваем текущий a[i] с max если да, то меняем max и его индекс.

imax:=1;

max:=a[imax];

For i:=0 to n-1 do

If a[i]>max then

Begin

Imax:=1;

Max:=a[imax];

End;





Тема №5

Структурированные переменные это переменные, состоящие из множества других компонентов (структурированных или простых).

Массивом называется упорядоченный набор компонентов одного типа. Помимо типа необходимо задать их порядок и число. Компонента выбирается по её номеру. Память под компоненты выделяется в последовательных участках в соответствии с типом.

Массивы бывают:

  1. Статические (память выделяется 1 раз в соответствии с её типом после объявления переменной в разделе VAR);

  2. Динамические (Память выделяется во время выполнения программы процедурой SETLENGTH(…));



В описании статического массива необходимо указать тип индекса, который задаёт количество. Его тип-диапазон.



Type

<имя типа(идентификатор)>=ARRAY[<тип индекса>]_of_<тип компоненты>;



Var

<имя переменной>:<имя типа>;



Пример:

Const

nmax=100;



Type

Tmas_r=array[0..nmax] of real;

Tmas_i=array[0..nmax] of integer;

Tmas_c=array[0..nmax] of char;

Tmas1=array[‘a’..’z’] of integerl;



Var

a,b,x,z: Tmas_r; ind1,ind2:Tmas_i; … … …



Обращение к массиву осуществляется по номеру:

<имя>[<индекс>]





[0; nmax]



Ввод массива:

Writeln(‘введите размер массива’);

Readln(n);

For i:=0 to n-1 do

Readln(M[i]);



Вывод массива:

For i:=0 to n-1 do

Write(M[i]:5:3);







Поиск минимального элемента и его индекса:

Mmin:=M[0]; // присваиваем минимальному значению значение 0-го элемента массива

For i:=0 to n-1 do

If M[i]

Begin

Mmin:=M[i];

j:=i{индекс минимального эл-та};

End;



Поиск максимального элемента и его индекса:

Mmax:=M[0]; // присваиваем максимальному значению значение 0-го элемента массива

For i:=0 to n-1 do

If M[i]>Mmax then

Begin

Mmin:=M[i];

j:=i{индекс максимального эл-та};

End;



Нахождение произведения элементов массива (если среди элементов нет нулевого):

Pr:=1;{присваиваем произведению 1};

For i:=0 to n-1 do

Pr:=Pr*M[i]; {выражение текущего значения переменной через предыдущее}



Нахождение суммы элементов массива:

Sum:=0;

For i:=0 to n-1 do

Sum:=Sum+M[i]; {выражение текущего значения переменной через предыдущее}



Вставка p-го элемента в массива:

Writeln(‘введите значение элемента’);

Readln(X);

For i:=n downto p+1 do

M[i]:=M[i-1];

M[p]:=X;



Удаление p-го элемента в массива:

Writeln(‘введите значение элемента’);

Readln(X);

For i:=p to n-2 do

M[i]:=M[i+1];



Вставка и удаление элемента – частные случаи сдвига элементов массива.



Метод бинарного поиска

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

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

Метод (алгоритм) бинарного поиска реализуется следующим образом:

1. Сначала образец сравнивается со средним (по номеру) элементом массива (рис. 5.10, а).

  • Если образец равен среднему элементу, то задача решена.

  • Если образец больше среднего элемента, то это значит, что искомый элемент расположен ниже среднего элемента (между элементами с номерами sred+1 и niz), и за новое значение verb принимается sred+i, а значение niz не меняется (рис. 5.10, б).

  • Если образец меньше среднего элемента, то это значит, что искомый элемент расположен выше среднего элемента (между элементами с номерами verh и sred-1), и за новое значение niz принимается sred-1, а значение verh не меняется (рис. 5.10, в).

a

б

в

Рис. 5.10. Выбор среднего элемента массива при бинарном поиске

Рис. 5.11. Алгоритм бинарного поиска в упорядоченном по возрастанию массиве

2. После того как определена часть массива, в которой может находиться искомый элемент, по формуле (niz-verh) /2+verh вычисляется новое значение sred и поиск продолжается.

Алгоритм бинарного поиска, блок-схема которого представлена на рис. 5.11, заканчивает свою работу, если искомый элемент найден или если перед выполнением очередного цикла поиска обнаруживается, что значение verh больше, чем niz.

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

Предположим, что у нас N элементов в массиве и индекс каждого элемента лежит в промежутке от 1 до N.

Первый шаг сортировки методом пузырька

  1. Сравниваем первый и второй элементы массива. Если первый элемент больше, чем второй, то меняем их местами.

  2. Сравниваем второй и третий элементы массива. Если второй элемент больше, чем третий, то меняем их местами.

  3. ...

  4. Cравниваем предпоследний (N-1) и последний (N) элементы массива. Если предпоследний элемент больше, чем последний, то меняем их местами.

В результате самым последним элементом в массиве у нас окажется самый большой элемент.

Повторяем вышеуказанные действия для части массива, начиная с 1 позиции до N-1 (шаг 2).

Второй шаг сортировки методом пузырька

  1. Сравниваем первый и второй элементы массива. Если первый элемент больше, чем второй, то меняем их местами.

  2. Сравниваем второй и третий элементы массива. Если второй элемент больше, чем третий, то меняем их местами.

  3. ...

  4. Cравниваем элемент N-2 и элемент N-1 массива. Если (N-2)-й элемент больше, чем элемент N-1, то меняем их местами.

В результате предпоследний элемент в массиве у нас тоже будет на своем, "отсортированном" месте.

Последующие шаги сортировки методом пузырька

Повторяем вышеуказанные действия для части массива, начиная с 1 позиции до N-2 (шаг 3), а потом для диапазона 1..N-3 и так далее до диапазона 1..2.

После завершения последнего шага наш массив будет отсортирован по возрастанию.

Пример:

Исходный 9 3 5 4 2

  1. шаг 3 5 4 2 9

  2. шаг 3 4 2 5 9

  3. шаг 3 2 4 5 9

  4. шаг 2 3 4 5 9



For j:=1 to n-1 do

For i:=1 to n-j do

If a[i]>a[i+1] then

Begin

buf:=a[i];

a[i]:=a[i+1];

a[i+1]:=buf;

End;

Сортировка методом прямого выбора.

На первом шаге отыскивается максимальный элемент во всём массиве и меняется местами с последним. На втором отыскивается максимальный элемент на интервале от 0 до n-2 и меняется с элементом М[n-2] и так далее…

Repeat

Mmax:=M[0];

for i:=0 to N do

If M[i]>Mmax then

Begin

Mmax:=M[i];

j:=i;

End;

M[j]:=M[N];

M[N]:=Mmax;

dec(N); {равносильно N:=N-1}

Until N=2;








Случайные файлы

Файл
81108.rtf
pirogov.doc
33890.rtf
30955-1.rtf
154310.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.