Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 13

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 13)

Это возможно, если мы ограничим длину строки, например, 80 символами. Итак, мы определим таг с1: аггауГ! .. 80) о1 сйаг Следующие четыре подпрограммы используют с этим массивом индексную переменную 1. Фактически же эта переменная используется локально и может в каждой пропедуре описываться как локальная. Кроме того, теперь нужна еще ввести глобальную переменную 1.

для обозначения длины текущей строки. тте!11пе; т:= 0; йо:= 1по + 1; нййе еой(х),йо Ъей)и 1:= !'+1; геай(х, с1(1)) еий; .1:= 1; геат)й(х) Ри!1йе: 1:= 0; 'иййе 1 < Х йе Ъей!и1:= !+1яп! (у, !(!)) еий; иЮей(у) (1.61) Леан)1пе; 1:= 0; ттЫе — ~ео1п(гара!) йо Ьейю 1:= 1+1; гоаб(с1(!)) еий; Х:= 1; геат(1п )тг1!е1!пе. '1;= 0; ит1!е (1по); ттМе ! < Х йо Ьей)и т;= т+1; вп!е(с1Я еий; вгйей Условие поеЫ н программе !пзег! теперь легко можно выразить как 1. Ф 0 На этом разработка программы редактирования файлов за.

вершаетси. Улражиелил Т1 УПРАЖНЕНИЯ 1Л. Пусть кардинальные числа стандартных типов йч!ейег, геа! и сдаг обо знзчеиы через сс, се и сс. Каковы кардинальные числа следующих типов данных, определенных в этой главе в качестве примеров: лол, Воо!еал, дейэ, буква, цифра, офицер, гош, а!(а. байк сотр!ех, регзол, гоогдслаге, гдагзей гарезга!из? 1.2. Как бы вы представили переменные типов, перечисленных в упр. 1.1! '(а) в памяти вычислительной машины, которой вы пользуетесь? 0) на Фортране? с) на предпочитаечом вами языке программирования? 1.3. Какова последовательность комакд (на вашей ЭВМ) для: (а) операций размещения в пзмяти компонент упакованных записей н массивов н обращения к ним? (Ц операций яад множествами, включан проверку принадлежности? 1.4. Мегино лн во время выполнения программм контролировать правильность использования записей с чариантамн? А во время траисляцииэ 1.$.

По каким причинам некоторые совокупности данных определяют как последовательные файлы, а не как массивы? 1.6. Предположим, что вам нужно представить последовательные файлы, определенные в равд, 1.11, на ЭВМ с очень большой оперативкой памятью. Вам разрешается ввести ограничение, что длина файла ни. когда не превышает определенную величину (,. Следовательно, вы моясете представить файлы с помощью массивов. Опипсите возможную реализацию, включая выбранное представление данных и процедуры для элементарных файловых операций уе1, ри1, гезе! и гешгйе, которые определены с помощью аксиом в равд. !.1!.

1.7. Выполните упр. !.6 для сегментнрованных файлов. 1.Ь. Имеется железнодорожное расписание, содержащее список ежеднев. ных рейсов поездов яа нескольких линиях железной дороги. Найдите такое представление этих данных с помощью массивов. записей или файлов, которое было бы удобно для поиска времеяи прибытия иотправлсяия поезда в нужном направлении для определенной станции. 1.9. Дан текст Т в виде файла я небольшой список слов в виде двух мас. синов А я В.

Предположии, что слова — это небольшие массивы символов, зсссксиьсальнзя длина которых фиксирована. Наппшате программу, ноторая преобразует текст Т в теист Э, заменяя каскдый раз слово Ас соответствующим словом Вс. 1.10. Какие изменения (переопределенче констант и т. п.) необходимы, чтобы переделать программы !.й и 1,4 для имеющейся у вас вычислительной машины? 1.11, Напишите программу, подобную программе 1.4, С заголовком ргосебнге шг!!егеа!(час!: !ех1; к: геа1; а, ом сл!еуег) Требуется преобразовать значение к в последовательность, состоящую по крайней мере нз л символов (их надо добавить в файл (), предстзвлясошнх х в десятичном виде с фиксированной запятой с т цифрами после запятой.

Если необходимо, числу !ожет предшествовать соответствующее количество пробелов и/сслсс знак. !Л2. Перепишите текстовый редактор яз раза. !.! !.4 в виде завершенной программы. /, Фундамгнга*ьныс структура данных 1.13. Сравните три следующие версии бинарного поиска с (1.!7).

Каине из этих трех программ правильны? Какие более эффеитивиы? Мы пред. полагаем, что имеютсн следующие переменные и ионотанта й/ ) 0: чпг /,//с ! гп/еуег; а; пггпу(1 .. /тг) от Т; х: Т Программа /ы / с= 1;/:= /(/; рш1/' с= (/+/) а(ч2; ЕаЯ с хйеп/:= /се)яе/ г= и Ип(И(аЩ=х) т/ (/к /) Программа В: / з= 1; /: =- /у; гереа1/с:=- (/+/') д!т 2; !/х ~ аЯ(реп/:= /с — 1; 1/а(й) ~ х (йеп г':=- /с-! 1 ип(И / >,/ Программа С: г:= 1! /:= /тГ'* иереей а:- (/+/) д!ч 2; (хх < аЩ(йеп/:= /сеЬе/:= /с+1 пи!11 / ." / Указание, Все программы должны зананчиваться при а(й) = х, если' талая компонента существует, илн лри а(й) Ф х, если нет компоненты со значением х.

1.1Е. Пехоторая хомпания проводит опрос, чтобы выяснить спрос на свою продукцию. Вс продунция — это лластиини и магнитофонные ленты с песнями; самые популярные лесин будут переданы по радио. Олрашииаемое население делится на четыре категории согласно полу н возрасту (схажем, моложе 20 и старше 20). Каждый опрашиваемый дочжсн назвать пять любимых песен. Песням ставятся в соответствие числа от ! до /т' (например, пусть Ж = 30).

Результаты опроса представлены в файле род талого типа 1уре Ь/г — 1., /ч"; хг.т =- (пга/г, /сага/г); гптрапге = гесогй люле, ~и/глгп!с; а//а; а: гсх; «уе: /ч/грег; с/!«/сг; атгау (1 .. 5) о(/!/г елб ! чат ро//: 61е о$ гггропге Итак, каждый элемелт файла представляет опрашиваемого и солержит его имя, фаиилию, пол, возраст и пять любимых ласса в порядка Литература предпочтения. Этот файл является вкодным для программы, которая должна получить следующие результаты: 1.

Список песен в порядке их популярности. Каждый элемент этого списка содержит номер песни и число упоминаний при опросе. Песни, которые ни разу ие упоминались, исключаются из списка. 2. Четыре отдельных списка с именами и фамилиями всех отвечаю. щих, которые назвали на первом месте одну нз трех песен, наиболее популярных в их категории. Всем пяти спискам должны предшествовать соответствующие заголовки, ЛИТЕРАТУРА !.1. ВАНЬ О. 3„013КБТйА Е. Угг., НОАйЕ С.

А. й., 31гис[пгед Ргайгавпппй — Хеаг Уог!г; Асадев!с Ргезз, 1972. [Имеется перевод: Дал О., Дейкстра Э., Хоор К., Структурное программирование. — Мл Мир, 1975.1 1.2. НОАйЕ С. А. й. Хо1ез ап Оа1а 31гпсгиг!пй. — 31гпсгигеб Ргойгавв!пй, ОаЫ, О![йз1га, Ноаге, 83 — 174. [Имеется перевод: Хоор К. Заметки о структурной организации данных. — В кни Дал О., Дейкстра Э., Хоор К. Структурное программирование. — Ми Мир, 1975, с. 98 †!97.1 1.3. 3ЕХБЕХ К., ТЧ[йТН Х. РАБСАЬ, 17зег Манна! ап4 йерог1. — Ьес1пге Хо1ез 1п Соврвег Бс1епсе.

— Вес!!в Брг[ппег.Чег!ая, 18, !974. [Имеется перевод; Неясен К., Вирт Н. ПАСКАЛЬ; Руководство для пользователи и описиние языка. — Мл Финансы и статистика, 1982.[ 1.4. 911йТН Х. Ргайгав Оете[орвеп1 Ьу 31еряйзе йейпевеп1.— Соти. АСМ, 14, Хо 4, 1971, 221 — 227. 1.5 %1йТН Х. Тйе Ргойгавв1пй Ьапйнайе РАБСА1..

— Леси Тл[агпгиггги. Хо. 1, 1971, 35 — 53, 1.6. ТЧ[йТН Х. Оп 1йе Совравйоп о1 Юе!1-31гис[агед 1згойгавз. — Сотрийлу Яи иеуз, 8, Хо. 4, 1974, 247 — 259. СОРТИРОВКА эл. Введенмв Основная цель этой главы — показать на множестве примеров, как используются структуры данных, описанные в предыдущей главе, и продемонстрировать влияние выбранной структуры данных на алгоритмы, выполняющие некоторое задание. Кроме того, сортировка служит хорошим примером того, что одна и та же цель может достигаться с помошью различных алгоритмов, причем каждый нз них имеет свои определенные преимушества и недостатки, которые нужно оценить с точки зрения конкретной снзуации. Под сортировкой обычно понимают процесс перестановки объектов данного множества в определенном порядке.

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

Даже маленьких детей приучают приводить вещи «в порядок», и они сталкиваются с некоторым видом сортировки задолго до того, как узнают что-либо об арифметике. Следовательно, методы сортировки очень важны, особенно при обработке данных. Казалось бы, что легче рассортировать, чем набор данных? Однако с сортировкой связаны многие фундаментальные приемы построения алгоритмов, которые и будут нас интересовать в первую очередь. Почти все такие приемы встречаются в связи с алгоритмами сортировки.

Характеристики

Список файлов учебной работы