4624

Программирование данных статической структуры. Сортировка и поиск в одномерных массивах

Практическая работа

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

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

Русский

2012-11-23

1.37 MB

21 чел.

Введение

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

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

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

Целью занятия является изучение методов сортировки и поиска в одномерных массивах, а также привитие практических навыков в использовании записей при программировании практических задач.


1. СОРТИРОВКА И ПОИСК В ОДНОМЕРНЫХ МАССИВАХ

1.1. Сортировка массивов

Сортировкаэто процесс перестановки объектов какого-либо множества в определенном порядке. Как правило, цель сортировки – облегчить последующий поиск элементов в отсортированном множестве. В этом смысле элементы сортировки присутствуют во многих практических задачах. Упорядоченные объекты содержатся в телефонных справочниках, в оглавлениях книг, в библиотеках, в словарях и т.п.

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

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

Методы сортировки обычно разделяют на две категории:

  1.  сортировка массивов – «внутренняя сортировка», так как массивы располагаются в оперативной памяти ЭВМ, для которой характерен быстрый произвольный допуск к ячейкам памяти;
  2.  сортировка файлов – «внешняя сортировка», так как файлы хранятся в более медленной внешней памяти (магнитных или оптических дисках, магнитной ленте и т.п.).

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

.

Основные требования к методам сортировки массивов: 1) экономное использование памяти (из которого вытекает недопустимость применения дополнительных массивов) и 2) быстродействие.

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

  •  количество присваиваний;
  •  количество сравнений.

Все методы сортировки массивов можно разделить на две большие группы:

  •  прямые методы сортировки;
  •  улучшенные методы сортировки.

Прямые методы сортировки требуют выполнения порядка n2 операций сравнения, а улучшенные – порядка  сравнений.

Прямые методы сортировки по принципу, лежащему в основе метода, в свою очередь разделяются на три подгруппы:

1) сортировка вставкой (включением);

2) сортировка выбором (выделением);

3) сортировка обменом («пузырьковая» сортировка).

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

Задание № 1. Сортировка вставкой

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

2. Идея метода заключается в следующем. Исходный массив чисел А = (а1, а2, …, аn) разделяется на две части: отсортированную и неотсортированную. Элементы из неотсортированной части поочередно выбираются и вставляются в отсортированную часть так, чтобы не нарушить в ней упорядоченность элементов. В начале работы алгоритма в качестве отсортированной части массива принимают только один первый элемент а1, а в качестве неотсортированной части — все остальные элементы (а2, …, аn).

Таким образом, алгоритм будет состоять из (n – 1)-го прохода (n — размерность массива), каждый из которых будет включать четыре действия:

  •  взятие очередного i-го неотсортированного элемента и сохранение его в дополнительной переменной;
  •  поиск позиции j в отсортированной части массива, в которой присутствие взятого элемента не нарушит упорядоченности элементов;
  •  сдвиг элементов массива от (i – 1)-го до j-го вправо, чтобы освободить найденную позицию вставки;
  •  вставка взятого элемента в найденную j-ю позицию.

3. Схематично описанные действия одного прохода представлены на рис. 1.1, а алгоритм сортировки – на рис. 1.2.

4. Пример сортировки методом вставки показан на рис. 1.3.

5. Программа, реализующая рассмотренный алгоритм, будет иметь следующий вид:

program InsertionSort;

{$APPTYPE CONSOLE}

uses

 SysUtils;

const

 n=10;                 //Длина массива

type

 TVector=array[1..n] of Integer;

var

 Vector: TVector;      //Вектор, элементы которого сортируются

      B: Integer;      //Промежуточная переменная

  i,j,k: Integer;

begin

 Randomize;            //Инициализация датчика случайных чисел

 Writeln('Formirovanie elementov massiva:');

 for i:=1 to n do

  begin

   Vector[i]:=random(100); {Элементы вектора формируются как случайные целые числа в диапазоне от 0 от 100}

   writeln('Vector[',i:2,']=',Vector[i]:2);

  end;

 Readln;

 for i:=2 to n do

  begin

   B:=Vector[i]; //Взятие очередного неотсортированного элемента

   // Цикл поиска позиции вставки неотсортированного элемента

   j:=1;

   while (B>Vector[j]) do

    j:=j+1; //После окончания цикла j фиксирует позицию вставки

    //Цикл сдвига элементов для освобождения позиции вставки

    for k:=i-1 downto j do

     Vector[k+1]:=Vector[k];

     Vector[j]:=B;    //Вставка элемента на найденную позицию

  end;

 Writeln('Otsortirovanniy massiv:');

 for i:=1 to n do

  Writeln('Vector[',i:2,']=',Vector[i]:2);

 Readln;

end.

6. Результаты работы программы представлены на рис. 1.4.

7. Внесите в программу следующие изменения:

  •  размер массива составляет n = 100;
  •  массив Vector состоит из вещественных (real), а не целых (integer) чисел;
  •  случайные числа, образующие массив Vector, должны находиться в диапазоне от -100 до +100, поэтому для формирования элементов массива  Vector используется следующий оператор:

Vector[i]:=2*X*Random-X;

(где Х объявляется как константа, равная 100);

  •  сортировка должна осуществляться в порядке убывания элементов.

8. Отладьте программу и сохраните проект в папке \Мои документы\ПЗ-03\Задание1 под именем InsertionSort.

Задание № 2. Сортировка обменом (метод «пузырька»)

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

2. Идея метода заключается в следующем. Слева направо поочередно сравниваются два соседних элемента ai и ai+1 исходного массива чисел А = (а1, …, аn), и если их взаиморасположение не соответствует заданному условию упорядоченности, то они меняются местами. Далее берутся два следующих соседних элемента и т.д. до конца массива. После одного такого прохода на последней n-ой позиции массива будет стоять максимальный элемент («всплыл» первый «пузырек»). Поскольку максимальный элемент уже стоит на своей последней позиции, то второй проход обменов выполняется до n-1-го элемента. И так далее. Для полной сортировки требуется n-1 проход.

3. Алгоритм сортировки методом обмена приведен на рис. 1.5. Следует обратить внимание на то, как осуществляется перестановка соседних элементов в массиве через дополнительную переменную В:

B:=Vector[i];

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

Vector[i+1]:=B;

Если ее не ввести, то выполнение оператора Vector[i]:=Vector[i+1]; приведет к тому, что старое значение элемента Vector[i] исчезнет, так как будет заменено на значение Vector[i+1].

4. Пример, иллюстрирующий работу алгоритма сортировки массива обменом, приведен на рис. 1.6.

5. Программа, реализующая метод обмена («пузырька»), будет иметь следующий вид:

program BubbleSort;

{$APPTYPE CONSOLE}

uses

 SysUtils;

const

  n=10;     // Длина исходного массива

  X=100;

type

  TVector=array[1..n] of Real;

Var

  Vector: TVector;    // Вектор, элементы которого сортируются

       B: Real;       // Промежуточная переменная

     i,k: Integer;

begin

 Randomize;            // Инициализация датчика случайных чисел

 Writeln('Formirovanie elementov massiva:');

 for i:=1 to n do

  begin

    Vector[i]:=2*X*random-X; {Элементы вектора формируются как случайные числа в диапазоне от -100 до +100}

    writeln('Vector[',i:2,']=',Vector[i]:6:2);

  end;

 Readln;

 for k:=n downto 2 do {"Всплывание" очередного максимального элемента на k-ю позицию}

   for i:=1 to k-1 do

     if Vector[i]>Vector[i+1] then

       begin

         B:=Vector[i];     // Обмен местами соседних элементов

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

         Vector[i+1]:=B

       end;

 Writeln('Otsortirovanniy massiv:');

 for i:= 1 to n do

   Writeln('Vector[',i:2,']=',Vector[i]:6:2);

 Readln;

end.

6. Результаты работы программы представлены на рис. 1.7.

7. Внесите в программу следующие изменения:

  •  размер массива составляет n = 100;
  •  массив Vector состоит из целых (integer), а не вещественных (real) чисел;
  •  случайные числа, образующие массив Vector, должны находиться в диапазоне от 0 до 500;
  •  сортировка должна осуществляться в порядке убывания элементов.

8. Отладьте программу и сохраните проект в папке \Мои документы\ПЗ-03\Задание1 под именем BubbleSort.

9. Если сравнить рассмотренные прямые методы между собой, то в среднем метод вставки в несколько раз быстрее (в зависимости от длины массива), чем метод обмена («пузырька»).

1.2. Поиск элементов в одномерных массивах

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

Поиск – это нахождение каких-либо конкретных данных в большом объеме ранее собранных данных.

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

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

Указанные условия поиска считаются элементарными.

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

Любой поиск может быть реализован как простой перебор записей (медленный поиск) и как бинарный (быстрый) поиск.

Задание № 3. Линейный поиск

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

2. Идея метода линейного поиска заключается в следующем. В исходном массиве чисел А = (а1, а2, …, аn) последовательно просматриваются все элементы массива до тех пор, пока не встретится искомый элемент или пока не будет достигнут конец массива. В последнем случае искомого элемента, который называют ключом, в массиве нет.

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

В самом неблагоприятном случае, когда искомый элемент является последним в массиве, требуется провести n сравнений.

3. Схема алгоритма линейного поиска первого вхождения значения В в массив А приведена на рис. 1.8. Результатом работы алгоритма является индекс (Ind) того элемента ai, значение которого равно В (ai = В). Если искомый элемент в массиве отсутствует, то выдается значение Ind = -1.

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

program LinePoisk;

{$APPTYPE CONSOLE}

uses

 SysUtils;

const

 n=10;                 // Длина массива

type

TVector=array[1..n] of Integer;

var

    A: TVector;      // Вектор, в котором ищется значение

    B: Integer;      // Искомое значение

i,Ind: Integer;

begin

 Randomize;            // Инициализация датчика случайных чисел

 Writeln('Formirovanie elementov massiva:');

 for i:=1 to n do

  begin

   A[i]:=random(100); {Элементы вектора формируются как случайные целые числа в диапазоне от 0 от 100}

   writeln('A[',i:2,']=',A[i]:2);

  end;

 Writeln('Vvedite iskomoe znachenie B');

 Readln(B);           // Ввод искомого значения В

 i:=1;

 while ((i<=n) and (A[i]<>B)) do

   i:=i+1;

 if A[i]=B then Ind:=i   // Поиск элемента

           else Ind:=-1;

 Writeln('Index iskomogo elementa Ind =',Ind:3);

 Readln;

end.

5. Результаты работы программы представлены на рис. 1.9.

6. Проверьте работу программы при значении В, отсутствующем в массиве.

7. Внесите в программу следующие изменения:

  •  размер массива составляет n = 20;
  •  элементы массива А вводятся с клавиатуры.

8. Отладьте программу и сохраните проект в папке \Мои документы\ПЗ-03\Задание3 под именем LinePoisk.

Задание № 4. Двоичный поиск

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

2. Алгоритм двоичного поиска допустимо использовать для нахождения заданного элемента только в упорядоченных массивах. Рассмотрим его на примере массива, упорядоченного по неубыванию (А[i]<=А[i+1]).

Принцип двоичного поиска: исходный массив отсортированных чисел А = (а1, а2, …, аn) делится пополам и для сравнения выбирается средний элемент. Если он совпадает с искомым, то поиск заканчивается. Если же средний элемент меньше искомого, то все элементы левее его также будут меньше искомого. Следовательно, их можно исключить из зоны дальнейшего поиска, оставив только правую часть массива. Аналогично, если средний элемент больше искомого, то отбрасывается правая часть, а остается левая.

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

И так далее, пока или элемент будет найден, или длина зоны поиска станет равной нулю. В последнем случае искомый элемент найден не будет.

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

3. Алгоритм двоичного поиска приведен на рис. 1.10.

Вначале исходный диапазон представляет собой весь массив. На каждом шаге рассматривается средний элемент диапазона, индекс которого получается как (L+R) div 2 (деление нацело), где L - индекс левой границы диапазона (на первом шаге равен 1), R - индекс правой границы (на первом шаге равен реальной размерности массива n). Поиск заканчивается, когда значение среднего элемента диапазона равно искомому, т.е. найден нужный элемент, или когда индекс левой границы становится больше индекса правой, это будет означать, что данного элемента в массиве нет.

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

5. Один из возможных вариантов программы, реализующей метод двоичного поиска, имеет следующий вид:

program BinSearch;

{$APPTYPE CONSOLE}

uses

 SysUtils;

const

n=10;       // Длина массива

type

TVector=array[1..n] of Integer;

var

  A: TVector;  // Исходный отсортированный массив целых чисел

  B: Integer;  // Искомый элемент

 L,R: Integer;  //Текущие границы зоны поиска: L-левая, R-правая

  i: Integer;

begin

  Writeln('Vvedite elementy massiva v poriadke vozrastania:');

  for i:=1 to n do

   begin

    Write('A[',i,']=');

    Read(A[i]);

   end;

  Write('Vvedite iskomiy element B=');

  Readln(B);

  L:=1;

  R:=n;   {Вначале левая граница поиска совпадает с первым элементом, а правая граница - с последним элементом}

  // Пока не пересекутся границы поиск продолжается

  while (L<=R) do 

   begin

    i:=(L+R) div 2;   // Определение индекса среднего элемента

    if A[i]=B then

        Break     // Выход из цикла поиска, т.к. элемент найден

     else

        if A[i]<B then L:=i+1    // Изменение границ

                  else R:=i-1;

   end;

  if A[i]=B then

     Writeln('Iskomiy element nayden na pozicii ',i:3)

  else

     Writeln('Iskomiy element ne nayden');

  Readln

end.

6. Результаты работы программы приведены на рис. 1.12.

7. Проверьте работу программы при различных значениях В, в том числе и отсутствующих в массиве.

8. Внесите в программу следующие изменения:

  •  размер массива составляет n = 20;
  •  элементы массива А формируются датчиком случайных чисел в диапазоне от 0 до 100;
  •  включите в программу операторы, сортирующие элементы массива в порядке возрастания.

8. Отладьте программу и сохраните проект в папке \Мои документы\ПЗ-03\Задание4 под именем BinSearch.

2. РАБОТА С СОСТАВНЫМИ ДАННЫМИ НЕОДНОРОДНОЙ СТРУКТУРЫ

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

Записи состоят из одного или нескольких полей, для каждого из которых при объявлении указывается имя (идентификатор) и тип.

Записи делятся на обычные и вариантные.

Обычная фиксированная запись состоит из одного или нескольких полей, для каждого из которых при объявлении указывается имя (идентификатор) и тип в разделе Type:

Type

 Имя_записи = record

   Поле_1: Тип_1;

   ...

   Поле_n: Тип_n;

 end;

Var

 Идентификатор_1, ...: Имя_записи;

где

Имя — имя типа запись;

Поле_i и Тип_i (i = 1, ..., n) — имя и соответствующий тип i-го поля записи.

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

Group_KB51[1].Name       :='Sergey';

Group_KB51[1].Marks.Prog :=5;

Для упрощения работы с записями имеется специальный оператор присоединения with, позволяющий использовать в тексте программы имена полей без указания имени переменной-записи:

with Имя_записи do

 begin

   Инструкции программы

 end;

В Инструкциях программы можно использовать только имена полей.

Вариантные записи включают две части:

  1.  обычная фиксированная запись;
  2.  вариантная, состоящая из поля признака и одной или нескольких вариантных компонент. Вариантные компоненты включаются в конкретный элемент типа «запись» по альтернативному принципу, в зависимости от значения поля признака.

Записи могут объединяться в массивы.

Задание № 5. Составление списка сотрудников и поиск в нем нужных записей

1. Составить список сотрудников фирмы, содержащей 6 человек. Список должен содержать следующие сведения для каждого сотрудника:

  •  фамилия, имя, отчество;
  •  должность;
  •  дата рождения;
  •  год поступления в фирму;
  •  оклад;
  •  адрес проживания (улица, номер дома и квартиры);
  •  домашний телефон.

2. Информацию о каждом сотруднике оформить в виде записи. Записи объединить в массив.

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

4. Исходные данные:

Якименко Петр Иванович

Генеральный директор

Родился 23.1.1960

В фирме с 1991 года

Зарплата 1500 грн.

Адрес: ул. Репина, 12-45

Телефон: 123-45-67

Синилов Сергей Анатольевич

Главный бухгалтер

Родился 14.5.1964

В фирме с 1991 года

Зарплата 1200 грн.

Адрес: пр-т Мира, 67-19
Телефон: 341-78-33

Трофименко Анна Ивановна

Кассир

Родилась 28.2.1969

В фирме с 1994 года

Зарплата 1000 грн.

Адрес: ул. Левченко, 84-37

Телефон: 456-34-21

Сажин Никита Андреевич

Старший программист

Родился 3.9.1973

В фирме с 1997 года

Зарплата 1300 грн.

Адрес: ул. Вагонная, 94-36

Телефон: 533-67-84

Созин Алексей Петрович

Программист

Родился 13.12.1984

В фирме с 2001 года

Зарплата 1100 грн.

Адрес: ул. Римская, 68-83

Телефон: 666-77-88

Малыш Василий Владимирович

Программист

Родился 18.6.1988

В фирме с 2003 года

Зарплата 800 грн.

Адрес: ул. Охотников, 8-3

Телефон: 222-33-11

5. Текст программы:

program Spisok;

{$APPTYPE CONSOLE}

uses

 SysUtils;

const m=6;

type man=record  //Определение типа запись

       fio: record familia, name, otch: string[20]; end; //ФИО

     dolgn: string[20];                        //Должность

      date: record day, mes, god: integer; end; //Дата рождения

     godpos: integer;                            //Год поступления

  zarplata: integer;                            //Зарплата

    adress: record ul: string[15]; dom, kv: integer; end; //Адрес

 telephone: string[9]                          //Телефон

        end;

var 

  sotr: array [1..m] of man;     //Определение массива записей

     n: integer;

  symb: string[1];

procedure vvod;                   //Процедура ввода полей записей

begin

 for n:=1 to m do

 begin

   writeln('Vvesti dannye na sotrudnika nomer:',n);

   writeln('Familia -');

   readln(sotr[n].fio.familia);

   writeln('Imia -');

   readln(sotr[n].fio.name);

   writeln('Otchestvo -');

   readln(sotr[n].fio.otch);

   writeln('Dolgnost -');

   readln(sotr[n].dolgn);

   writeln('Data rogdenia');

   writeln('  Den -');

   readln(sotr[n].date.day);

   writeln('  Mesiac -');

   readln(sotr[n].date.mes);

   writeln('  God -');

   readln(sotr[n].date.god);

   writeln('God postuplenia v firmu - ');

   readln(sotr[n].godpos);

   writeln('Zarobotnaia plata -');

   readln(sotr[n].zarplata);

   writeln('Adress progivania -');

   writeln('  Ulica -');

   readln(sotr[n].adress.ul);

   writeln('  Nomer doma -');

   readln(sotr[n].adress.dom);

   writeln('  Nomer kvartity - ');

   readln(sotr[n].adress.kv);

   writeln('Nomer telephone');

   readln(sotr[n].telephone);

 end;

end;

procedure list(n:integer);  //Процедура печати

begin

 writeln('-----------------------------------------------------------------');

 writeln(sotr[n].fio.familia,' ',sotr[n].fio.name,' ',sotr[n].fio.otch);

 writeln('Data rogdenia ',sotr[n].date.day,'/',sotr[n].date.mes,'/', sotr[n].date.god);

 writeln;

end;

begin

 vvod;                   //Вызов процедуры ввода исходных данных

 writeln('Raspechatat spisok sotrudnikov,');

 writeln('familii kotorix nachinautsia s bukvy S');

  writeln('i daty ix rogdenia');

 writeln;

 for n:=1 to m do 

 begin

   symb:=copy(sotr[n].fio.familia,1,1);

   if symb='S' then list(n);   //Вызов процедуры печати списка

 end;

 readln

end.

6. Результаты выполнения программы (рис. 2.1):

7. Измените программу таким образом, чтобы распечатать анкетные данные сотрудников, имеющих срок службы больше 10 лет.

8. Отладьте программу и сохраните проект в папке \Мои документы\ПЗ-05\Задание5 под именем Spisok.

Рис. 2.1. Результат работы программы

ВЫВОДЫ

  1.  Сортировка – это процесс перестановки объектов какого-либо множества в определенном порядке.
  2.  Методы сортировки разделяют на две категории: сортировка массивов, выполняемая в оперативной памяти ЭВМ, и сортировка файлов, выполняемая на внешних носителях данных.
  3.  Методы сортировки массивов подразделяются на прямые методы (требуют выполнения порядка n2 операций сравнения) и улучшенные методы (требуют выполнения порядка  операций сравнения.
  4.  Алгоритм двоичного поиска допустимо использовать для нахождения заданного элемента только в упорядоченных массивах. Его суть заключается в последовательном сравнении значения искомого элемента со средним значением среднего элемента диапазона массива.
  5.  К составным статическим данным неоднородной структуры относятся записи, объединяющие в единое целое любое число структур данных других типов. Записи состоят из одного или нескольких полей, для каждого из которых при объявлении указывается имя (идентификатор) и тип. Обращение к полям записей выполняется с помощью квалифицируемых (уточненных) идентификаторов, в которых указывается вся цепочка имен от идентификатора переменной типа запись до идентификатора требуемого поля. Имена полей квалифицируемого идентификатора разделяются точками.

Контрольные вопросы

  1.  Что собой представляет сортировка массивов? Как классифицируются методы сортировки?
  2.  В чем заключается идея метода сортировки вставкой?
  3.  Что нужно изменить в алгоритме сортировки методом вставки, чтобы перейти от сортировки по возрастанию элементов, к сортировке по убыванию элементов?
  4.  В чем заключается идея метода сортировки обменом?
  5.  Как при сортировке обменом не потерять элементы исходного массива?
  6.  Как осуществляется линейный поиск?
  7.  В чем состоит идея двоичного поиска?
  8.  Какие преимущества имеет двоичный поиск перед линейным?
  9.  Что собой представляют записи? Как они описываются в программе?
  10.  Как осуществляется обращение к полям записи?
  11.  Как записи объединяются в массивы?


Рис. 1.1.
 Схема действий для одного прохода алгоритма сортировки методом вставки

Рис. 1.2. Схема алгоритма сортировки методом вставки

Рис. 1.3. Пример реализации сортировки методом вставки. Слева в кружке указан номер прохода

Рис. 1.4. Результат работы программы, реализующей алгоритм сортировки массива методом вставки

Рис. 1.5. Схема алгоритма сортировки методом обмена

Рис. 1.6. Пример реализации сортировки методом обмена

Рис. 1.7. Результат работы программы, реализующей алгоритм сортировки массива методом обмена

Рис. 1.8. Схема алгоритма линейного поиска

ис. 1.9. Результат работы программы, реализующей алгоритм линейного поиска

Рис. 1.10. Схема алгоритма двоичного поиска

Рис. 1.11. Пример реализации двоичного поиска

Рис. 1.12. Результат работы программы, реализующей алгоритм двоичного поиска

  1.  

 

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

53626. Е. Благинина «Посидим в тишине» и Э. Мошковская «Я маму мою обидел» 36.5 KB
  Кто нибудь знает это стихотворение наизусть Откройте учебники на странице 119. Почему так названо стихотворение как вы думаете Прочитайте стихотворение про себя. Чему учит стихотворение К маме нужно относиться с любовью и заботой. Кто ответит на вопросы Вы познакомились со стихотворением Елены Благининой Посидим в тишине.
53627. Пётр Павлович Ершов «Конек - Горбунок» 72.5 KB
  Слайд 1 Итак самое знаменитое произведение Ершова была сказка Конёк –Горбунок Почему сказка Говорят животные на ките люди живут нет жарптицы месяц как живой человек конёк летает нельзя искупаться в кипятке и остаться живым. Слайд 2. Слайд 3. А кто прочитал всю сказку Сколько частей 3 Слайд 4 Сегодня на уроке мы попытаемся увидеть: как своим поэтическим языком описал героев Ершов и поняли ли его художники иллюстрировавшие сказку Конёк Горбунок.
53628. Формирование бюджета капиталовложений 25 KB
  При планировании инвестиционной деятельности компании обычно имеют дело не с отдельными проектами, а с портфелем возможных проектов. При этом затраты на реализацию этих проектов превышают доступные предприятию инвестиционные ресурсы.
53629. Сравнение трёхзначных чисел 54 KB
  Для чего нам нужны эти навыки устного счёта 60 и 12 на сколько одно число больше другого во сколько раз одно число больше другого. сколько сумме этих чисел не хватает до 100. 65 и 9 На сколько одно число больше другого найдите сумму этих чисел сколько сумме этих чисел не хватает до 50. Сколько сказок на каждом диске 16 х 3 = 48 60 – 48 = 12 12 : 2 = 6 2.
53631. Нижняя прямая подача мяча (обучение). Закрепление перемещений волейболиста, приема волейбольного мяча сверху двумя руками посредством эстафеты 73.5 KB
  1 мин 1 мин 30 с Соблюдать интервал; обратить внимание на внешний вид учащихся Следить за дистанцией Следить за правильностью выполнения задания спина прямая взгляд направлен вперед. Во время бега следить за правильностью постановки ноги. Следить за высотой подъема бедра. Следить за четкостью выполнения команд за соблюдение интервала.
53632. Весёлые старты 125 KB
  Упражнения в ходьбе: на носках руки вверх; на пятках руки за голову; на внешней стороне стопы руки на поясе; ходьба; б Бег. Ходьба руки за голову. Руки прямые пальцы вместе. стойка ноги врозь руки на пояс.
53633. Прыжки в длину с разбега. Метание в горизонтальную цель 60.5 KB
  а ходьба в приседе руки на коленях. б ходьба на пятках руки в стороны. в ходьба на носках руки на поясе. г ходьба на внешней стороне стопы руки за голову.
53634. Совершенствование технических действий в баскетболе 55 KB
  Задачи урока: образовательные: совершенствовать технику ловлипередачи мяча совершенствовать умения в бросках мяча совершенствовать технику ведения мяча; развивающие: развивать двигательные качества – ловкость быстроту реакции координацию движений; воспитательные: воспитывать у обучающихся чувства коллективизма взаимовыручки дружбы. Тип учебного занятия: урок закрепления Формы работы: фронтальная групповая Инвентарь и оборудование: баскетбольные мячи конусы Место проведения: спортивный зал. ОРУ с баскетбольными мячами на месте:...