Реферат на тему:


Воспользуйтесь поиском к примеру Реферат        Грубый поиск Точный поиск






Загрузка...

Реферат на тему:

Массивы

1. Одномерные массивы

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

Приведем пример, где возникают такие данные. В примере 5.1 (п.5.5) сначала читалось число точка, в которой надо было вычислить значение полинома. Затем читались его коэффициенты. Но более естественно сначала прочитать поленом, а затем одну или более точек для вычислений. В этом случае весь поленом придется запомнить. И если его степень может достигать 101, то нужно 102 переменные. Означать их и описывать их обработку не лучший способ убить время. Лучше обозначить массив переменную, составленную из 102 переменных, которые идентифицируются именем массива и номерами от 0 до 101. Можно и от 1 до 102 это дело вкуса.

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

все они (компоненты или элементы массива) имеют тот же тип;

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

множество индексов (индексова множество) конечна и зафиксирована в определении массива и в процессе выполнения программы не меняется;

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

Количество элементов индексовои множества называется длиной массива.

Посмотрим на массив с точки зрения математики. Пусть компоненты массива имеют тип T, а индексы тип I. значением переменной-массива является послидовнисть значений типа T, занумерованных значениями типа I, то есть функция типа I® T. Множество всех таких функций образует носитель для типа, который в языке Паскаль обозначается выражением вида

array [I] of T.

Например, массив, в котором надо хранить коэффициенты полинома, мог бы иметь тип array [0..101] of real. В таком массиве 102 компоненты вещественного типа с номерами от 0 до 101. Или массив, в котором надо хранить количества символов, прочитанных где мог бы иметь тип array [char] of integer. В нем 256 целых переменных, а их номерами есть символы.

Типом компонентов может быть произвольный тип, кроме файлов (раздел 13). Типом индексов I любой перечисляемый тип. Правда, система Турбо Паскаль не позволяет указывать типы integer и word, а тем более тип longint, как типы индексов. Там слишком много элементов. Но это не страшно, поскольку система позволяет создавать массивы даже с еще большим количеством элементов (см. Раздел 16.5).

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

В определении массивов в качестве переменных нет никаких особенностей. Например, мы можем написать как

type ART = array [0..101] of real; var A: ART;

так и

var A: array [0..101] of real;

В обоих случаях переменная A состоит из 102 действительных переменных. Они идентифицируются выражениями A [0] A [1], ..., A [101]. Или выражениями вида A [индексовий-выражение], где индексовий-выражение имеет значение от 0 до 101.

С точки зрения математики, для массивов данная операция индексирования []. По массивом типа I® T и номером компонента в нем она порождает переменную типа T. Пусть имя обозначено как массив типа array [I] of T, E выражение типа I. Тогда выражение имя [E] задает элемент этого массива, то есть переменную типа T, номер которой в массиве является значением выражения E.

Выражения с операцией [] допустимые в операторах везде, где используется переменная соответствующего типа, за исключением того, что элемент массива не можетбыть параметром цикла. Например, если действует определение типа ART и переменной A, то можно писать что-то вроде

A [1]: = 1; A [2] = A [1] 2;

for k = 3 to 101 do readln (A [k]);

writeln (A [1] + A [2] + A [3] + A [4]).

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

var a, b: array [char] of integer; ch: char;

можно вместо цикла

for ch = chr (0) to chr (255) do b [ch] = a [ch];

написать лаконично

b = a;

Остановимся на подстановке аргумента-массива на место параметра подпрограммы. Если параметр массив является параметром значением, то в начале выполнения вызова подпрограммы в локальной памяти этого вызова создается копия аргумента. Если в массиве много элементов, то возможна ситуация, когда автоматической памяти для такого аргумента не хватит. Однако за выполнение подпрограммы массив или остается без изменений, либо изменяется, причем именно изменен массив и нужен для дальнейшей обработки по программе. В первом случае его можно подставлять по ссылке, а не по значению; во втором надо. Случаи, когда параметры-массивы необходимо означать как параметры-значения, встречаются довольно редко. Конечно, использование параметров-переменных типа массив требует повышенной аккуратности.

2. Строки

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

Переменная-строка является массивом символов вместе с дополнительным компонентом. В определении типа задается длина n последовательности символьных компонентов, индексированных целыми 1, ..., n. дополнительный компонентуказывает длину последовательности символов, представленной в массиве. Эта длина значения-строки может изменяться в процессе выполнения программы от 0 до длины массива n.

В языке Турбо Паскаль тип строк задается выражением вида

string [n]

где n целая стала из диапазона 1..255 (возможно, именуемая). Например, string [80]. Переменная такого типа является массивом символов с индексами от 0 до n. Значение-строку подается переменными с индексами от 1 до n, переменная с индексом 0 подает длину строки. Точнее, если ее значение c, то m = ord (c) рассматривается как длина значения-строки. В процессе выполнения программы она может меняться от 0 до n.

Элементы массива с индексами от m + 1 до n недоступны; их значения можно рассматривать как "мусор". Попытка присвоить то этим элементам или взять их значения приведет к аварийному завершению программы.

Поскольку неотъемлемая длина значения-строки подается в одном байте, она не может превышать 255. Отсюда "имеем, то что имеем", то есть ограничение 255 на длины строк. Имя типа string эквивалентно выражению string [255].

простыми выражениями типа строка является имя переменной-строки, строчная стала (литерал), или выражение типа char. Над строками данная бинарная операция катенации (или дописки) ее признаком является '+'. Результат получается дописыванием правого операнда к левому: значением выражения '123' + '45' является '12345'. Целая длина строки возвращается с вызова функции length с аргументом-строкой: length ( '123') = 3.

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

Выражение типа "строка" можно присвоить переменной-строке. Его символы присваиваются элементам переменной, начиная с первого. Если длина значения больше максимально возможной длины n переменной, то присваиваются только n первых символов. При этом длина значения (или n) неявно присваивается добавляеттково компонента переменной-строки (как символ нулевом элемента массива). Например, пусть переменная s обозначена как string [3]. После присваивания

s = '12345'

четыре ее компоненты с индексами 0, 1, 2, 3 иметь значение chr (3), '1', '2', '3', а после

s = '12'

chr (2), '1', '2', а последний компонент будет недоступным, и его значение будет "мусором". При последнем значение переменной s выполнения оператора

s = s + '9'

предоставит ей значение '129', а оператора

s = '9' + s

значение '912'. В обоих случаях s [0] = chr (3). После присваивания s = '' переменная s подает пустая строка: s [0] = chr (0), а остальные элементы недоступны.

Изменить длину значения можно явно, изменив нулевой символ. Если после s = '' выполнить s [0] = 2, то значение компонентов с индексами 1 и 2 со "мусора" превратятся в значение-строку. Присваивания другим элементам строки не изменяет длины его значение.

В типах строк обозначен операции сравнения =, & lt; & gt ;, & lt ;, .... По определению, строки равны, если имеют ту же длину, и в ее пределах соответствующие символы одинаковы. В противном случае они не равны. Составление строк зависит от системы программирования.

В языке Турбо Паскаль, если length (s1) & lt; length (s2), то строка s1 меньше строки s2, то есть s1 & lt; s2 истина. При равных длин строки сравниваются в лексикографическом порядке, то есть s1 & lt; s2 тогда, когда существует такое i, что 1Ј иЈ length (s1), при котором s1 [i] & lt; s2 [i], а все соответствующие элементы с меньшими номерами равны между собой. Как видим, упорядочения строк в Турбо Паскаль отличается от лексикографического.

В системе программирования Турбо Паскаль отмечены также много полезных подпрограмм обработки строк. Рассмотрим лишь четыре из них.

Функция с заголовком

function copy (s: string; ind, cnt: byte): string

задает возвращения подстроки строки s, начинающаяся с s [ind] и имеет длину cnt. Например, copy ( 'abcd', 2, 2) = 'bc ".

Функция с заголовком

function pos (subs, s: string): byte

задает возврат номера того элемента в строке s, начиная с которого subs входит в s как подстрока (если не входит, то возвращается 0). Например, pos ( 'bc', 'abcd') = 2, pos ( 'aa', 'abcd') = 0.

Процедура с заголовком

procedure val (s: string, var v; var ErrCode: integer)

задает преобразование изображения числа в строке s в числовой тип и присваивания его переменной v. Если преобразование действительно возможно, то значением ErrCode будет 0. В противном случае ее значением будет позиция с символом в строке, начиная с которого преобразования невозможно. Тип аргумента, соответствующего параметру v, должен иметь тип, соответствующий содержанию строки s. Так же содержание строки должен задавать число, представите в типе этого аргумента. Например, s = '1.3' или s = '1E2 "второй аргумент должен быть вещественного типа, а не целого. Аналогично по его типа integer в строки не должно быть значений, представляющих числа, большие 32767 или меньше -32768.

Процедура с заголовком

procedure delete (var s: string; start, len: integer)

задает уничтожения len символов, начиная с позиции start в строке s. Например, s = 'abcdef' после вызова delete (s, 3, 3) строка s иметь значение 'abf ". По start = 0 или len = 0 или start & gt; length (s) строка не меняется. По start + len & gt; length (s) с s изымается подстроку до конца строки.

3. Нестандартное представление чисел

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

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

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

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

1) Значение цифры десятичного числа подается элементом массива типа integer. Память используется очень неэкономно (разряд занимает 2 или 4 байта), но арифметические операции реализуются через поразрядные операции над значениями цифр, уже обозначенные в Паскале для типа integer.

2) Цифра числа (а не ее значение число) непосредственно является значением типа char и подается одним байтом. Покомпонентный операции над значениями цифр надо воспроизвести в виде операций над символами. Для изображения чисел удобно воспользоваться строчным типом.

3) Значение цифры числа в P-ной системе подается одним байтом как число от 0 до P-1, где PЈ 256. По P = 256 каждый бит отражает значение двоичной цифры 0 или 1; такое представление экономное тратит память, но требует определенных усилий для реализации операций.

4) Значение P-ковой цифры, где PЈ 16 подается четырьмя битами (полубайт) так, что две соседние цифры занимают байт.

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

4. Матрицы и многомерные массивы

Рассмотрим прямоугольную таблицу с mґ n однотипиних элементов как последовательность из m строк, в каждой из которых n элементов. Последовательности определенной длины подаются в языках программирования массивами. Следовательно, возникает понятие "массив, элементами которого являются массивы", или двумерный массив. Если элементы прямоугольной таблицы сами являются последовательностями или таблицы образуют последовательность определенной длины, то возникает понятие трехмерного массива и тому подобное.

Определение многомерных массивов и изображения их элементов в языке Паскаль опишем с помощью простого примера. Позиция в игре "крестики-нолики на поле 3ґ 3" подается квадратной таблицей из символов 'x', '0' или '' (пробел). Пронумеруем клетки поля, как в шахматах буквами "a", "b", "c" по горизонтали и числами 1, 2, 3 по вертикали. Тогда строки таблицы можно представить массивами типа

type Row = array [ 'a' .. 'c'] of char;

Таблицу можно рассмотреть как последовательность трех строк и подать массив типа

type Table = array [1 .. 3] of Row;

Партия, то есть последовательность позиций, имеет длину не более 9, и может подаваться массивом таблиц:

type Game = array [1 .. 9] of Table;

Массивы типа Table имеют два измерения: номер строки и номер символа в нем; массивы типа Game три: номера таблицы, строки и символа. Измерение 1..9 в типе Game называется внешним, измерение 'a' .. 'c' Нумератор символы в строках, внутренним.

Тип Game можно задать эквивалентным выражением, а не

Загрузка...

Страницы: 1 2