AOP_Tom1 (1021736), страница 131
Текст из файла (страница 131)
(Подробнее о 1РЫ1 речь идет в 1ЯЕ Ттапэасйопз 1Т-2 (ЯертетпЬег, 1956), 61-70; Ртос. Яезсетл 1о!и! Сотр. СолЕ 9 (1957), 218 — 240. Материалы по 1РЬ-Н1 впервые появились в виде конспекта лекций в Университете штата Мичиган летом 1957 года.] Работа Ньювелла, Шоу и Саймона привлекла многих исследователей к использованию связанной памяти, которую в то время часто называли по первым буквам фамилий авторов гч88-памятью, но, в основном, для решения задач, связанных с моделированием человеческого мышления.
Постепенно эти технологии стали базовыми инструментами программирования. Первая статья, описывающая эффективность связанной памяти для выполнения "приземленных" задач, была опубликована Д. В. Каррам П1 (Л. ЪЧ. Сатг П1) в САСМ 2,2 (РеЪгпату, 1959), 4 — 6. В ней Карр указал, что связанными списками легко манипулировать на обычных языках программирования без привлечения изощренных подпрограмм или интерпретирующих систем. (См. также С. А. В!ваню, "1п8ех!п8 апд сопсго1-этосом гесЬп!с!пеэ", 1ВМ Х Неэ. апд Е)ею 3 (1959), 288 — 301.] Сначала для связанных таблиц использовались узлы из одного слова, но около 1959 года постепенно различные коллективы убедились в преимуществах узлов из нескольких последовательных слов и "многосвязных" списков.
Первой статьей, посвященной сугубо этой идее, была статья О Т. Нозэ, САСМ 4 (1961), 147-150. В то время для того, что в настоящей главе мы называем узлом, автором указанной статьи использовался термин "плекс" (р!ех), хотя позднее он употреблял зто слово в другом смысле — для описания класса узлов в комбинации с алгоритмами их прохождения. Обозначения для ссылки на поле в узле, в основном, бывают двух видов: имя поля либо предшествует обозначению указателя, либо следует за ним.
Таким образом, то, что в данной главе записывается как "1МРО(Р)", некоторые авторы записывают как "Р.1МРО". Во время создания этой главы обе записи, пожалуй, встречались одинаково часто. Запись, принятая в настоящей книге, имеет то достоинство, что она непосредственно транслируется на языки РОНТ)1А)Ч, СОВОЬ и подобные, если определить массивы 1МРО и 11МК и использовать в качестве индекса Р. Кроме того, представляется естественным использовать обозначения математической функции для описания атрибутов узла.
Заметьте, что "1МРО(Р)" произносится как "1МРО от Р", как принято в математике — Е(х) вербально передается как "1 от х". Альтернативное обозначение "Р.1МРО" менее естественно, поскольку имеет тенденцию к подчеркиванию Р, хотя и может быть прочитано как "Р-е 1МРО". Причина, по которой 1МРО(Р) кажется более предпочтительным способом записи, по-видимому, заключается в том, что Р— переменная, а 1МРО имеет конкрет- ный смысл при использовании записи. По аналогии можно рассматривать вектор А = (А[1], А[2],..., А[100]) как узел, имеющий 100 полей с именалзи 1,2,..., 100.
Теперь на второе поле в в(ашик обозначениях можно сослаться как к2(Р)", где Р указывает на вектор А; но если ссылаться на )-й элемент вектора, то более естественно записать нА[Я", помещая перегиенную "1" второй. Точно так представляется более подходящей запись 1ИРО(Р) с переменной кРв на втором месте*. Возможно, первыми, кто увидели в концепциях стека (" последним вошел— первым вышел";!аяг-(п-Йгяг-оп() и очереди ("первым вошел — первым вышел"; Йгяя1п-Йгяг-оп() важные объекты изучения, были бухгалтеры, заинтересованные в упрощении процесса начисления подоходных налогов.
Обсуждение методов Ь1ГО и Г1РО при составлении прайс-листов можно найти в любом учебнике среднего уровня для бухгалтеров [см., например, С. Г. апс( %. Л. ЙОЫаггег, Сояг Ассоппйпй (!ваези Ъог)с: ЖЙеу, 1957), СЬар(ег 7]. В середине 40-х годов А. М. Тьюринг (А. М. Тпйпб) разработал механизм стека, названный реверсивной памятью, для связывания подпрограмм, локальных переменных и параметров, Тьюринг использовал для принятых ныне понятий "добавление в стек" и "снятие со стека" (рпяЬ/рор) понятия "закапыватьв (Ьпгу) и "откапывать" (с()я!пяег/ппЬпгу) (см. ссылки в разделе 1.4.5).
Несомненно, простые применения стеков, расположенных в последовательных адресах памяти, в программировании с первых дней были обычным делом, поскольку стек представляет собой интуитивно понятную и естественную концепцию. Программирование стеков в связанном виде появилось впервые в 1РЬ, как упоминалось выше; имя "стек" происходит из терминологии 1РЬ (хотя в 1РЬ имелся более официальный термин чрпяййогчп 1мгн) и независимо введено Э.
В, дейкстрой (Е. %. 1)1))сигуа) [)тшпег. Ма(Ь. 2 (1960)., 312 — 318]. Термин "деки (с(ес)пе) был введен Э. Ю. Швеппе (Е. гЬ ЯсЬзчерре) в 1966 году. Происхождение цпкличсских списков и списков с двойными связями не ясно. Вероятно, эти идеи многим показались естественными. Важным фактором в популяризации этих технологий было существование основанных на них систем общего назначения для обработки списков [см. Кпо(гег) Ь(яг Бягпсяпгея, САСМ 6 (1962), 161 — 165, и Бупнпесбс Ь(яг Ргосеяяог, САСМ 6 (1963), 524 — 544, Н. Вейзенбаума (Л. Же)яепЪашп)]. Айвен Сэтерленд (1чап Йп(Ьег!апс)) ввел в использование независимые двусвязные списки в ббльших узлах в своей системе ЙЬессЬрас) (РЬ.
1). 1Ьея(я, Маяя. 1пяц о( ТесЬпо1обу, 1963). С первых "компьютерных" дней многие квалифицированные программисты независимо разработали различные методы адресации и прохождения многомерных массивов информации. Таким образом была рождена еще одна часть неопубликованного компьютерного фольклора. Обзор этой темы можно найти в работе Н.
Нейегшап, САСМ 5 (1962), 205 — 207 [см, также Л. С. Созчег, Сошр. Х 4 (1962), 280-286]. Структуры деревьев, явно представленные в памяти компьютера, изначально использовались для приложений, работающих с алгебраическими формулами. Ма- В Аргументапия автора безупречна, но... "меняется все в наж век перемен" и место ГОНТНАН и СОНОЬ заняли языки С++, Рааса! и зача (а также тлена! Вавы и многие другие), в которых полна смысла именно запись Р.1ИРΠ— "поле 1ИРО структуры Р" (или "записи" и т.
п.— название варьируется в зависимости от языка программирования). Что же касается аналогии с массивом, то в том же С или С++ на клементы массива в[1 можно ссылаться и как на вП), и как на 1(а) .— 11рилс персе. шинный язык для ряда ранних компьютеров использовал трехадресный код для представления вычислений арифметических выражений; последний эквивалентен 19РО, ЬЬ1вК и КЬ1НК бинарногоэ!редставления дерева.
В 1952 году Г. Д. Кахриманиан (Н. О. КаЛПп|ашап) разработал алгоритмы для дифференцирования алгебраических формул, представленн|ях в расширенном трехадресном коде [см. Яутрозпип оп АпмипаНс Рго8гатт!пд (ЖаэЫпйгоп, В.Сз О%се о1 Нага! НезеагсЛ, Мау, 1954), 6-14]. С тех пор древовидные структуры различных видов независимо изучались многими исследователями в связи с их применением во многих компьютерных приложениях.
Однако в публикациях основные технологии для работы с деревьями (не го списками) появлялись лишь в составе описаний отдельных алгоритмов. Первый общий обзор был сделан в связи с изучением структур данных в работе К. Е. 1чегэоп апд Ь. Н. 3оЛпзоп [1ВМ Согр. геаеагсЛ герог|а НС-390, НС-603, 1961]; см. также 1чегзоп, А Ргодгатт!п8 Ьап8иаде (Нем Ъогйп| Ж!!еу, 1962), Сбарсег 3, и С. Яа!!оп, САСМ 5 (1962), 103-114. Концепция проши|пмх (!ЛгеаЫе|!) деревьев принадлежит А.
Д. Перлису (А. 3. Рег!!э) и хЬ Торнтону (С. Т!|ого!оп) [САСМ 3 (1960), 195-204]. В их статье вводится также важная идея прохода деревьев в различных порядках и приводятся многочисленные примеры алгоритмов алгебраических манипуляций. К сожалению, эта важная статья готовилась наскоро и содержит много опечаток.
Прошитые списки Перлнса и Торнтона в нашей терминологии представляют собой правопрошитые деревья. Бинарные деревья, прошитые в обоих направлениях, были независимо открыты А. В. Кольтом (А. Ч'. Но!1), А Ма|Летайса! апг) Арр!!е|) 7пгезг!яасюп ог Тгее Яггисгигез (ТЛез!а, П. о( Реппву!чап!а, 1963). Прямой и непрямой порядки узлов деревьев в работе Е. Ра|ч!а)г, Со!!оди!пт оп гЛе Ропп|)агюп о7 Ма|Летайсз, Т!Лапу, 1962 (Вп|!арезм А)гаг!еппа! К!а|!о, 1965), 227 — 238, назывались "нормальный прямой порядок" и "дуальный прямой порядок".
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
