Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 6
Текст из файла (страница 6)
Ьв. ХГассивы 1.5. ОГРАНИЧЕННЫЕ ТИПЫ Часто бывает, что переменная принимает значения некоторого типа только в определенном интервале. Это можно выразить, определив переменную ограниченного типа, который описывается так: 1уре Т = пик ...так (1.9) где т1п и тах — границы интервала. Примеры: 1уре год=-1900 .. 1999 Туре буква = 'А' ..
'2' 1уре цифра='0' ..'9' Туре офицер = лейтенант ..еенерал Пусть даны переменные: чагу: год час 1.: буква тогда присваивания у:= 1973 и 1.:= 'В" разрешены, а у;= ;= 1291 и Т.:= '9' не разрешены. Транслятор может проверять законность таких присваиваний только в том случае, если присваиваемое значение суть константа или переменная того же типа.
Допустимость присваиваний вида у:=1 и Ь:=с где 1 — типа 1агеуег, а с — типа сйаг, можно проверить только во время выполнения программы. Системы, выполняющие такие проверки, оказались на практике чрезвычайно полезными для разработки программ. Использование ими избыточной информации для выявления возможных ошибок также является одной из основных причин применения языков высокого уровня. ° л. мдссивы Массив — это, по-видимому, наиболее широко известная структура данных, так как во многих языках, включая Ллгол-бО и Фортран, это единственная структура, которая существует в явном виде.
Массив — зто регулярная структура: все его компоненты — одного типа, называемого базовым тином. Массив — также структура с так называемым случайным доступом, все его компоненты могут выбираться произвольно и являются одинаково доступнымн. Для обозначения отдельной компоненты к имени всего массива !. Фундаментальные структуры данных (уре Т = аггау! Ц о1 Т, (1.1О) Примеры: туре Лоту = актау(1 .. 5) ок геа1 туре Сакс) = актау(1, . 80) о1 слет туре афа = актау(1 ..10) оа сйаг Конкретное значение переменной наг х: Поте если каждая компонента удовлетворяет равенству х;= 2-', может иметь вид, как показано на рнс, 1.2. Хх хх Хв Рис. К2, Массив типа гоак Составное значение х тина Т со значениями компонент гь ..., с может задаваться с помощью конструктора*> массива и оператора присваивания; х:=Т(е„..., с„) (1,11) Операция, обратная конструктору,— селектор.
Он позволяет выбрать нз массива отдельную компоненту. Если в качестве переменной х рассматривать массив, то селектор массива обозначается с помощью имени массива, дополненного соответствующим индексом компоненты ~': Гып ~ (!.12» Прн работе с массивами, особенно большими, обычно выборочно изменяют отдельные компоненты, а не строят заново ') В явмкв Паскаль такие конструкторы отсутствуют. — Прим. ред. добавляется так называемый индекс, позволяющий выбрать компоненту. Индекс должен иметь значение типа, определенного как тин индексов массива. Описание регулярного типа Т задает, таким образом, не только базовый тип То, но н тип индексов П 56. Массивы все составное значение.
При этом переменная-массив рас, сматривается как массив составляющих переменных и допускается присваивание значения отдельным компонентам, !!ри иер: х Д:= — 0.125 Хотя при выборочном присваивании меняется только значение отдельной компоненты, с точки зрения построения концепции следует считать, что изменилось все составное значение.
То, что индексы массива, т. е. «имена» его компонент, должны быть определенного (скалярного) типа, имеет весьма важные следствия. Индексы могут вычисляться, вместо индексной константы можно использовать индексное вьсражвиив. Значение этого выражения вычисляется, и результат определяет выбираемую компоненту. Такая общность дает ис только одно из важнейших я мощных средств программирования, но и приводит к одной из самых частых ошпбок, так как полученное значение выражения может не попасть в ннзервал, заданный в качестве диапазона для индексов данно~о массива.Мы будем считать, что в случае такого ошибочного обращения к несуществующей компоненте массива адекватная вычислительная система выдает предупреждение.
Обычно тип индексов должен быть скалярным, т, е, неструктурированным, типом, иа котором определено отношение порядка. Если базовый тип массива также упорядоченный, то иа таком регулярном типе имеется естественное отношение порядка. Для двух массивов упорядочение определяется с помощью сравнения компонент с наименьшими индексами, Формально это можно описать следующим образом; Если имеются два массива х н у, то отношение х - р выполняется в том и только том случае, если существует индекс й такой, что хЮ < уй и х!с)=уй для всякого 1< й. (1ЗВ) Например, (2, 3, 5, 7, 9) < (2, 3, 5, 7, 1 1) '1ЛВЕ(.' < '1.1ВЕ(.' Однако обычно считается, что массивы никак не упора.
дочены. Кардинальное число составного типа равно произведению кардинальных чисел типов его компонент. Поскольку все компоненты регулярного типа А принадлежат к одному н тому !. Фундамент«ление структура даниил же базовому типу В, мы получим сагб!па!!!у(А) =(сагб!па!!(у(В))" где и сагс(!па1!!у((), а ( — тип индексов массива. В следующем небольшом фрагменте программы показано использование селектора для массива. Цель этой программы — найти наименьший индекс ( компоненты со значением х. Поиск выполняется с помощью последовательного просмотра массива а, описанного как (1.14) чаг а: аггау[1..йс) о1 Т; (л(> О) 1:=О; гереа1 (: = — (+ 1 пп(1! (а [() = х) ~( (( = У); И аК ~ х 1Ьеп «в а нгт такого элемента» (1.15) В другом варианте этой програмлты применяется распространенный прием т(тиктивного элемента, или барьера, расположенного в конце массива.
Использование барьера позволяет упростить условие окончания цикла: вага: а!гну[!..Лс+1) о1 Т; (;=О; а [й(+ 1):=х; гереа1 (:=с+ 1 ип!1! а [с) =х; И () Л( !!теп «в а нгт такого элемента» Поэтому оно называется инвариантом цикла, Разумеется, поиск можно значительно ускорить, если компоненты уже упорядочены (рассортированы). В этом случае чаще всего применяется метод повторного деления пополам интервала, в котором ищется нужный элемент. Такой прием называется методом деления пополам или бинарным поиском, он показан в программе (1.17).
При каждом повторении просматриваемый интервал между индексами ( и (' делится пополам. Поэтому максимальное число требующихся сравнений равно [!опт(й()) 1:= 1; (':=- № гереаГ к:=- ((+() д1т 2; (1.17) Их > а[(с) !!тев (:== (с+1 е!зе !':= (с-1 ив!И (а[!с]=х) Ч ((Ы(') Присваиванне а[У+1):= х является примером выборочного изменения, т.
е. изменения отдельной компоненты составной переменной. В обеих версиях (1.15) и (1.16) основным условием, выполняющимся вне зависимости от того, сколько раз выполняется оператор (: = ( + 1, является а[() Ф х для (=1 ... ! — 1 Пб. массивы (Соответствующим ннвариантным условием выхода из цикла является а[Й[<х для 6=1 ...! — 1 а[Ь[= х для 6=1+ 1 ... )У Следовательно, если программа заканчивается при п[й] Ф х, то не существует а[6[ =х для 1<6: 1т'.) Компоненты массива могут в свою очередь быть составными. Переменная-массив, компоненты которой являются массивами, называется матриией. Например, М:аггау[! ..
10[о! Яош — это массив, состоящий из десяти компонент (строк), каждая из которых состоит нз пяти компонент вещественного типа. Этот массив называется матрицей !ОХ 5 с вещественными компонентами. Селекторы могут соответствующим образом следовать один за другим, так что МИИ обозначает 1'-ю компоненту строки М [1[, являющейся 1-й компонентой М.
Обычно эзо записывается короче, как М [~', 1[ н точно так же описание М: аггау [! .. 10[ о[аггау[1 .. Ь[о$геа1 можно записать проще, как М:аггау[1 .. 10, ! .. 5[оугва1 Если нужно выполнить некоторое действие со всеми компонентами массива или с расположенными подряд компонентами какой-то части массива, то для этого удобно использовать оператор цикла, как показано в следующем примере. Пусть дробь 1 представляется с помощью массива д, так, что т. е.
в десятичном виде с й — 1 цифрами. Теперь пусть 1 нужно разделить на 2. Для этого обычную операцию деления производят со всеми А — 1 цифрами А, начиная с 1= 1. При этом деление цифры на 2 выполняется с учетом возможного переноса из предыдущей позиции, и на следующий шаг Д Фундаментальные структуры данныи передается возможный остаток (см. 1.18) г: 10ьг+а(1); й11):= гй)ч 2; г;=- г — 2ь41) (1.18) Этот процесс используется в программе 1.1 для получения таблицы отрицательных степеней 2.
Оператор цикла удобно использовать также и для деления пополам при вычислении 2-', 2-9, ..., 2-"; таким образом получается вложенность двух операторов цикла. ртойтапь ражег (аигрги); (десятичное л1уедстивление отрииательных степеней двойни) еовчен = 10; 1уре сйф1 === О,. 9; тат ю',1с,г: ттеуег; ат1 аттау11 .. и) 01сйуй; Ьей1ы тот й:=- 1 1о л йо Ьерп иг11г('.'); г:=- 0; 1от1:== 1 10)с — 1 оо Ьей!и г:=- 10 ч+т16)' т)[1);= 7 й)т 2; г ." == г — 2ьт)(1); ит11е(сйг(а11)+ага)('0"))) еий; мЩ:= 5; ут11е!п('Ъ') евй евй . Программа 1.1, Вычисление степеней двойки.
Результат для гь = 10 имеет вид .6 .26 .1 25 .ОВ25 .09125 .016625 .0079125 .00390625 .0019б9126 .0009755525 $.7. Эдписи Самый общий метод получения составных типов — зто объединение компонент, принадлежащих к произвольным, возможно, тоже составным типам, в один составной тип. При. 1.7. Записи з! меры из математики — это комплексные числа, состоящие нз двух вещественных чисел, и координаты точек, состоящие из двух или более вещественных чисел в зависимости от размерности пространства, заданного системой координат. Пример из обработки данных — зто описание людей с помощью нескольких существенных характеристик, таких, как имя и фамилия, дата рождения, пол и семейное положение, В математике такой составной тнп называется декартов»он произведение»с типов компонент.
Это связано с тем, что множество значений такого составного типа состоит нз всех возможных комбинаций значений, взятык по одному нз каждого типа компонент. Следовательно, число таких наборов из и чисел равно произведению количеств элементов всех составляющих множеств, так что кардинальное число состав.
ного типа равно произведению кардинальных чисел всех типов компонент. В обработке данных комбинированные типы, такие, как описания людей или объектов, часто встречаются в файлах или «банках данных» и представляют собой записи существенных характеристик человека нли обьекта. Поэтому слово «запись» (гесогд) стало широко принятым для обозначения подобной совокупности данных, и мы будем использовать этот термин вместо термина «декартово произведение». В общем виде составной тип Т определяется следуюсцим образом: (1.19) Сагг(!па!!!у (Т) = саг«Впа! !1 у (Т~)....
» сагс(!па!!!у (Т„) Прссжерьс: !уре Свтр!вх = гесвгй ге: геа1! ии: геа! евй туре Расе = гессмв с!ау; 1 .. 31, тоисй; 1..12; уваг: 1,.2000 евй А Фундаментальные структуры данных туре Регзоп = кесаев пате: а(Та; ,гтгз!пате: а(!а ,' й!г!йе!а!е: Юа!е; зех: (та!е,~ета!е) ! таге!а!из: (з!пц!е, таге!е»1, ттйуоиед»!!тогсеИ) евй Значение типа Т можно строить с помощью конструктора записи е> и, следовательно, присваивать его переменной этого типа: Х:= Т(Х1» Хт» ° ° ° » Хн) (1.20) где х; — значение типа компоненты Ть Пусть даны переменные-записи: зи Сотр1ех г(: 1)а!е Р: Регзоп им могут присваиваться отдельные значения, например, следующим образом (см. рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
