Структурированные типы. Регулярный тип(массив). Одномерные массивы. Инициализация одномерных массивов. Вывод компонентов.

Для хранения и обработки сложных видов информациинеобходимы нетревиальные структуры данных.

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

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

<имя_типа>=ARRAY [<сп.инд.типов> ] OF<тuп>

Здесь <имя muna> – правильный идентификатор; ARRAY, OF – зарезервированные слова (массив, из); <сп.инд.типов> – список из одного или нескольких индексных типов, разделенных запятыми; квадратные скобки, обрамляющие список, требование синтаксиса; <тип> - любой тип Турбо Паскаля. В качестве индексных типов в Турбо Паскале можно использовать любые порядковые типы, кроме LONGINT и типов-диапазонов с базовым типом LONGINT.

Var Massiv: array[1..100] of Real;

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

A[5] S[k+1].

В качестве индекса может быть использовано выражение. Тип индексов может быть только интервальным или перечисляемым. Действительный и целый типы недопустимы. Индексы интервального типа, для которого базовым является целый тип, могут принимать отрицательные, нулевое и положительные значения.

В операторной части программы один массив может быть присвоен другому, если их типы идентичны, например:R1:=Z.

Для ввода или вывода массива в список ввода или вывода помещается переменная с индексом, а операторы ввода или вывода выполняются в цикле.

Инициализация массивов (присвоение начальных значений всем компонентам массивов).

С использованием типизированных констант, например:

type Dim10= Array[1..10] of Real;
const raM10: Dim10 = ( 0, 2.1, 4, 5.65, 6.1, 6.7, 7.2, 8, 8.7, 9.3);

Вопрос №22

Алгоритмы внутренней сортировки. Сортировка выбором.

Под сортировкой понимают, процесс перестановки объектов множества в определенном порядке. Целью алгоритма сортировки является переорганизация записей в файле так, чтобы они располагались в нем в каком-либо строго определенном порядке (обычно в алфавитном или числовом).Если сортируемый файл целиком помещается в память (или целиком помещается в массив, то для него мы используем внутренние методы сортировки. Сортировка данных с ленты или диска называется внешней сортировкой.

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

Этот метод - один из простейших, и от работает очень хорошо для небольших файлов. Его "внутренний цикл" состоит из сравнения a[i]<a[min] (плюс код необходимый для увеличения j и проверки на то, что он не превысил N), что вряд ли можно еще упростить. Ниже мы обсудим то, сколько скорее всего раз эти инструкции будут выполняться.

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

Вопрос №23

Алгоритмы внутренней сортировки. Сортировка вставкой.

Под сортировкой понимают, процесс перестановки объектов множества в определенном порядке. Целью алгоритма сортировки является переорганизация записей в файле так, чтобы они располагались в нем в каком-либо строго определенном порядке (обычно в алфавитном или числовом).

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

Вопрос №24

Алгоритмы внутренней сортировки. Сортировка обменом.

Под сортировкой понимают, процесс перестановки объектов множества в определенном порядке. Целью алгоритма сортировки является переорганизация записей в файле так, чтобы они располагались в нем в каком-либо строго определенном порядке (обычно в алфавитном или числовом).

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

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

Вопрос №24

Регулярный тип(массив). Двумерные массивы. Инициализация двумерные массивов. Вывод компонентов двумерного массива.

Для хранения и обработки сложных видов информациинеобходимы нетревиальные структуры данных.

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

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

<имя_типа>=ARRAY [<сп.инд.типов> ] OF<тuп>

Здесь <имя muna> – правильный идентификатор; ARRAY, OF – зарезервированные слова (массив, из); <сп.инд.типов> – список из одного или нескольких индексных типов, разделенных запятыми; квадратные скобки, обрамляющие список, требование синтаксиса; <тип> - любой тип Турбо Паскаля. В качестве индексных типов в Турбо Паскале можно использовать любые порядковые типы, кроме LONGINT и типов-диапазонов с базовым типом LONGINT.

Matrix: array[1..N,1..M] of Real

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

B[3,5]

В качестве индекса может быть использовано выражение. Тип индексов может быть только интервальным или перечисляемым. Действительный и целый типы недопустимы. Индексы интервального типа, для которого базовым является целый тип, могут принимать отрицательные, нулевое и положительные значения.

В операторной части программы один массив может быть присвоен другому, если их типы идентичны, например:R1:=Z.

Для ввода или вывода массива в список ввода или вывода помещается переменная с индексом, а операторы ввода или вывода выполняются в цикле.

При работе с двумерным массивом первый индекс определяет номер строки, второй – номер столбца. Двумерные массивы хранятся в памяти ЭВМ по строкам.

Инициализация массивов (присвоение начальных значений всем компонентам массивов).

С использованием типизированных констант, например:

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

type Dim3x2= Array[1..3,1..2] of Integer;
const
  iaM3x2: Dim3x2= ( (1, 2)
                    (3, 4)
                    (5, 6));

Вопрос №26

Строковый тип данных. Описание и операции над данными этого типа.

Особое место в языке Паскаль занимают массивы символов. Стандартный Паскаль допускает два способа хранения символьных массивов в памяти ЭВМ: распакованный и упакованный. Распакованные массивы символов хранятся в памяти ЭВМ по одному символу в машинном слове, упакованные – по одному символу в байте. При описании упакованного массива символов используют служебное слово PACKED, например:

var MAS: Packed Array[1..20] of Char;

Описание распакованного массива символов имеет вид:

var M: Array[1..20] of char;

Для преобразования символьного массива из распакованной формы в упакованную и наоборот, из упакованной в распакованную, в язык Паскаль введены две стандартные функции Pack, UnPack.

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

Строковые переменные – это одномерные упакованные массивы символов, для описания которых в Турбо Паскале введен тип String.

Например, если строка содержит до 30 символов, ее тип будет определен как

type s = String[30];

Длина строки не может содержать более чем 255 символов.

В Турбо Паскале определено понятие строки переменной длины, в этом случае ее описание задается как

type s = String;

Тип String без указания длины совместим со всеми типами строк.

Особенностью строковых переменных является то, что к ним можно обращаться как к скалярным переменным, так и к массивам. Во втором случае применяется конструкция "переменная с индексом", что обеспечивает доступ к отдельным символам строки. При этом нижняя граница индекса равна 1. Отдельный символ строки совместим с типом Char.

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

Для строк определены операции присваивания, слияния (конкатенации) и сравнения.

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

Строки могут быть элементами списка ввода – вывода, при этом записывается имя строки без индекса.

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

Для работы со строками в Турбо Паскаль включены процедуры и функции, которые обеспечивают редактирование и преобразование строк.

Вопрос №27

Подпрограммы языка ТР. Их назначение.

Алгоритм решения задачи проектируется путем декомпозиции всей задачи в отдельные подзадачи. Обычно подзадачи реализуются в виде подпрограмм.

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

Процедура и функция – это именованная последовательность описаний и операторов. При использовании процедур или функций Паскаль-программа должна содержать текст процедуры или функции и обращение к процедуре или функции. Тексты процедур и функций помещаются в раздел описаний процедур и функций.

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

Нестандартные процедуры и функции.

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

Турбо Паскаль имеет различные средства для деления программы на части. На верхнем уровне деления (больших задач) — это модули, на нижнем уровне (элементарных подзадач) — это подпрограммы, которые в Турбо Паскале могут быть двух видов: процедуры и функции.

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

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

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

FUNCTION F(q1:Т1, q2:Т2, ...):Т;
<Раздел     описания    локальных    меток,    констант,    типов    и переменных>
<Раздел описания внутренних процедур и функций> 
Begin 
S1;... SN; 
F:= <Обязательный оператор, который присваивает имени функции значение результата>
End;

где F — имя функции, q_i — имена формальных параметров, T_i — типы формальных параметров, Т — тип результата, 5, — операторы тела функции.

Обращение к функции осуществляется в правой части оператора присваивания, при этом в выражении записываются имя функции и фактические параметры в виде:

X:=F(b₁, b₂, …),

где F – имя функции, b_i – фактические параметры. После выполнения функции вычисленное значение присваивается имени функции и передается в выражение.

Вопрос №30

Процедуры языка ТP. Их описание и применение

Алгоритм решения задачи проектируется путем декомпозиции всей задачи в отдельные подзадачи. Обычно подзадачи реализуются в виде подпрограмм.

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

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

Опсание:

procedure NumString(N: integer; var S: string);
var
   V: integer;
begin
   V := Abs(N);
   S := ' ';
   repeat
      S := Chr(N mod 10 + Ord('0')) + S;
      N := N div 10;
   until N = 0;
   if N < 0 then S := '-' + S;
 end;

Вопрос №30