AOP_Tom1 (1021736), страница 132
Текст из файла (страница 132)
В приведенной выше работе Айвергон и Джонсон назвали прямой порядок порядком поддеревьев. Графические способы представления связей между древовидными структурами н соответствующими линейными обозначениями были описаны в А. С. Оегг!пйег, Ргос. Наггаг|! Яушр. оп ГЛяйа! Сотрисегз алг) !Ле!г АррйсаНопэ (АрН1, 1961), 203-224, Представление деревьев в прямом порядке степенями с алгоритмами, связывающими это представление с десятичной записью Дьюи и другими свойствами деревьев, были представлены в работе 8.
Оогп, Ргос. Яушр. МайЛ. ТЛеогу ог" Аигошага (Вгоо!г!уп; Ро1у. 1пэь, 1962), 223-240. История древовидных структур как математических объектов вместе с библиографией по этой теме приведена в разделе 2.3.4.6. В то время, когда в 1966 году создавался этот раздел, большинство сведений об информационных структурах было получено благодаря изучению систем обработки списков, игравших очень важную роль в истории. Первой широко используемой системой был язык 1РЬ-г' (наследннк 1Р1 Н1, разработанный в 1959 году).
Он представлял собой интерпретирующую систему, в которой программист изучал машино- подобный язык для работы со списками. Примерно в то же время Г. Гелернтером (Н. Ое!егпгег) и его сотрудниками был разработан РЬРЬ (набор подпрограмм на языке РОНТ11АН для работы со списками, который также обязан своему появлению на свет 1РЬ, но в отличие от него вместо интерпретируемого языка использовал вьгювы подпрограмм). Третья система, ЫБР, была также создана в 1959 году Дж. МакКарти (Л.
МсСагГЬу)'. Ь1БР существенно отличался от своих предшественников; его программы были (и хлстаются) математическими функциональными выражениями, скомбинированными с "условными выражениями" (сопб!г!опа? ехргевгйопв) и конвертированными затем в представление списков. В 60-е годы возникло много систем обработки списков; с исторической точки зрения среди них наиболее известен набор подпрограмм ЯЫР для реализации списков с двойными связями на языке РОВТВАл?, созданный Й. Вейзенбаумом (Л.
1Че!вепЬашп). В статье Боброу (ВоЬгоя) и Рафаэля (КарЬае!), САСМ 7 (1964), 231-240, можно прочесть краткое введение в 1Р1 Ч, ЫБР и 8Ь1Р,. В ней же дается сравнение этих систем. Превосходное введение в Ы8Р было опубликовано Ф. М. Вудвордом (Р. М. ЧЧоос?иагг() и Д. П. Дженкинсом (?Л. Р. Леп?г!пв), Сошр. Л. 4 (1961), 47-53. Кроме того, можно ознакомиться с авторским описанием их собственных систем (эти статьи представляют значительную историческую ценность): "Ап !псгойпсбоп ло 1РЬ-Чь А.
Ньювелла (А. Ыелге!!) и Ф. М. Тонге (Р. М. Топбе), САСМ 3 (1960), 205 — 211; "А РОВТВА!С-сошр!!ед Ывг Ргосевгйпб Ьапйцайе" Г. Гелернтера (Н. Се1егплег), Д. Р. Хансена (Л. К. Напвеп) и К. ЛЬ Гербериха (С. Ь. СегЬепсЬ), ЛАСМ 7 (1960), 87-101; "Кеспгв!че ?ппсВопв о? вугпЪо1лс ехргеввюпв апс( 1Ье!г сошрп!абоп Ьу шас?йпе, 1" Джона Мак-Карти (ЛоЬп МсСаггЬу), САСМ 3 (1960), 184-195; "Зугпшелпс 1!вл Ргосеввогь Й. Вейзенбаума (Л, %е!вепЪашп), САСМ 6 (1963), 524-544. Статья Вейзенбаума включает полное описание всех использованных в БЫР алгоритмов.
Из всех перечисленных ранних систем только ЫЯР имел все необходимые составляющие для того, чтобы пережить десятилетия дальнейшего прогресса. МакКарти описал раннюю историю ЫБР в Н!всосу о? Ргоягашш!п8 Ьапяпайев (Асабеш!с Ргевв, 1981), 173-197. В 60-е годы появился ряд систем для рабашм со строками, в которых первостепенное значение приобрели операции со строками переменной длины, содержащими алфавитную информацию — поиск вхождения в строку определенной подстроки, ее замещение другой и т. п. Наиболее важными из них с исторической точки зрения были СОМ1Т [Ч. Н.
тийте, САСМ 6 (1963), 83 — 84] и 81лОВОЬ [В. Л. РагЬег, К. Е. Сг!влго!6, апг? 1. Р. Ро!опв?гу, ЛАСМ 11 (1964), 21-30]. Хотя системы работы со строками широко использовались и состоят, в первую очередь, из алгоритмов, подобных рассмотренным в этой главе, они сыграли сравнительно малую роль в истории развития технологий представления информационных структур. Детали внутренней ревлизапии были скрыты от пользователей этих систем. Обзор ранних систем работы со строками можно найти в Б. Е.
Маг?п!с?с, САСМ 10 (1967), 420-424. В системах обработки списков 1РЬ-Ч и РЬРЬ не использовались ни сборка мусора, ни технология счетчиков ссылок при работе с разделяемыми списками. Вместо этого каиСдый список "принадлежал" одному списку и "заимствовался" всеми другими списками, которые на него ссылались. Список удалялся, когда его владелец позволял это. Следовательно, програлглгист должен был сам гарантировать, что при удалении список никому не был одолжен. Технология счетчика ссылок для списков введена Д.
Э. Коллинзом (С. Е. Со!!!пв), САСМ 3 (1960), 655-657, и позже проанализирована в САСМ 9 (1966), 578 — 588. Сборка мусора впервые была описана в статье Мак-Карти в 1960 году [см. также примечания Вейзенбаума в САСМ 7 (1964), 38, и статью Коэна (Со1леп) и Триллинга (Тг!П!п8), В?Т 7 (1967), 22 -30]. Рост понимания важности рабаты со связями естественным образом привел к их включению в алгебраические языки программирования, созданные после 1965 года.
Новые языки позволяли программистам выбрать подходящую форму представления данных, не прибегая к ассемблеру и избегая накладных расходов универсальных структур списков. Некоторыми из фундаментальных шагов на этом пути были рабаты Х. 1ч'!гСЬ апс! Н. ччеЬег, САСМ 9 (1966), 13 — 23, 25, 89-99; Н. 1Ч. Ьасчэоп, СА СМ 10 (1967), 358 — 367; С. А. Н. Нааге, кутба! Матри!ас!оп Ьалдиадеэ алг! Тес)ш!г!иеэ, еб.
Ъу 11. О. ВаЬпж (Ашэсегдаш: ХогсЬ-Но!!апб, 1968), 262-284; О.-Л. ОаЬ! апб К. Ь!уйаэгб, САСМ 9 (1966), 671-678; А, чап 1Ч!!пйаагбеп, В. 3. Ма!11аих, Л. Е. Ь. Рес1с, апб С. Н. А. Коэсег, Хитег!эсЬе ЛХаСЬ. 14 (1969), 79-218; Оепп!э М. Н!СсЬ!е, Н!эсогу об Рго8гатт!п8 Ьапйиайеэ — П (АСМ Ргеээ, 1996), 671-698.
Алгоритмы динамического выделения памяти появились за несколько лет до их описания в печати. Очень интересное обсуждение было подготовлено В. Т. Комфортам (Ч'. Т. Сот!от!) в 1961 году и опубликовано в САСМ 7 (1964), 357-362. Метод граничного дескриптора, описанный в разделе 2.5, был разработан автором книги в 1962 гаду для использования в операционной системе компьютера Виггои8Ьэ В5000. Система двойников впервые использовалагь Г. Марковицем (Н. Маг1соийх) в системе программирования 81МЯСШРТ в 1963 году, а также была независимо разработана и опубликована К.
Ноултонам (К. Кпои!соп), САСМ 8 (1965), 623 — 625 (см, также САСМ 9 (1966), 616-625]. Дополнительную информацию о динамическом выделении памяти можно найти в статьях ПНе апд Лоде!с, Сотр. Х 5 (1962), 200-209; Ва!)еу, ВагпеСС, агсб Виг1еэоп, САСМ 7 [1964), 339-346; А. Т. Вегяг!ээ, САСМ 8 (1965), 512 — 513: О. Т. Воээ, САСМ 10 (1967), 481 — 492. Общее обсуждение информационных структур и их связи с программированием было подготовлено Мэри д'Империо (Магу 6'Ьпребо) — "Васа Бсгиссигеэ апг! сЬе!г Нергеэепсас!оп ш Ясогайе", Аппиа! Нес4еи !и Аисотабс Ргодгвтт!л8 5 (Ох(огай Регйатоп Ргеээ, 1969). Ее статья служит серьезным путеводителем па истории предмета, поскольку включает детальный анализ структур, использованных в двенадцати системах обработки списков и работы са строками. Дополнительные исторические детали можно найти в трудах двух симпозиумов, САСМ 3 (1960), 183-234, и САСМ 9 (1966), 567 — 643 (отдельные статьи из этих трудов упоминались ранее).
Великолепно аннотированная библиография ранних работ по манипуляции символами и математическими формулами, имеющая множество связей с материалом этой главы, была составлена Д. Э. Саммет (д. Е. Бапипес); см. Сотрис!п8 Несбеиэ 7 (Ли!у — АийиэС, 1966), В1 — В31. В настоящей главе очень подробна рассматривались некоторые типы информационных структур, и (чтобы за деревьями суметь рассмотреть лес), вероятно, будет разумно проанализировать, что нами изучено, и подвести краткий итог па теме "информационные структуры" с точки зрения более широкой перспективы. Начав с базовой идеи узла (поде) как элемента данных, можно найти множество примеров, иллюстрирующих удобные пути представления структурных отношений либо неявно (оснавываясь на относительном порядке, в котором узлы хранятся в памяти компьютера), либо явно (с помощью указывающих на другие узлы связей в узлах).
Объем структурной информации, которая должна быть представлена в таблицах компьютерных программ, зависит от операций, которые должны выполняться над узлами. Из методических соображений мы, в основном, сконцентрировали свое внимание на связях между информационными структурами и их компьютерным представлением, а не рассматривалц эти вопросы по отдельности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
