Д. Кнут - Искусство программирования том 1 (1119450), страница 63
Текст из файла (страница 63)
В компьютере 1) т'АЕАС [А1ап Ь. Ье)пег,,)АСМ 1 (1954), 57-81[ была реализована идея непосредственной передачи информации между устройствами ввода- вывода и памятью во время работы программы, а затем прерывания программы по ее завершении. Из существования подобных систем следует, что для них были разработаны алгоритмы буферизации, но подробности не были опубликованы.
В первой опубликованной работе о методах буферизации в том смысле, в котором мы их описали, представлен крайне сложный подход к этой проблеме [см. О. Мос1с, С. Л. 8вв)Еь, "Ргойгапипес) 1прпс-Опсрпь Вп)1ег)пй", Ргос. АСМ чаа Сопб (1958), рарег 19, и )АСМ 6 (1959), 145-151[. (Должен предупредить читателя о том, что в обеих статьях широко используется местный жаргон, для понимания которого придется потратить некоторое время, но вам помогут в этом другие статьи из журнала ,)АСМ 6.) Система прерывания, которая позволяла осуществлять буферизацию ввода и вывода, была независимо разработана Э.
В. Дейкстрой (Е. %. 1)1)йвьга) в 1957 и 1958 годах для компьютера Х вЂ” 1, созданного Б. Ж. Лупстрой (В. д. Ьоорвгга) и К. С. Шолтеном (С. 8. 8сЬо!геп) [см. Сошр. 7. 2 (1959), 39 — 43]. В докторской диссертации дейкстры. ьСопппппгсагюп тв1гЬ ап Ап1ошабс Сошрптегв е (1958), обсуждаются методы буферизации, которые в данном случае были рассчитаны на очень длинные кольца буферов, в то время как в программах рассматривался, в основном, В/В на перфоленты и терминал.
В каждом буфере содержался либо один символ, либо одно число. Впоследствии Дейкстра развил эти идеи и пришел к важному общему понятию семафоров, которые лежат в основе управления параллельными процессами любого вида, а не только вводом-выводом [см. Ргойтатттб Ьапбиабев, ег). Ьу Р. Оепцув (Асабеппс Ргевв, 1968), 43 — 112; В1Т 8 (1968), 174-186; Асса 1п1огшабса 1 (1971), 115-138[. В статье 1)аьбб Е.
Регйпвоп, в1прпг-Опсрпг Вп)тегшй апг) РОККА'.ч)", .)АСМ 7 (1960), 1 — 9, рассматриваются буферные кольца и приводится подробное описание простой буферизации для многих устройств одновременно. Как пРедставляетСя, примЕРНО З 000 команд †э разумный верхний предел сложности задач. — ГЕРМАН ГОЛДС ГАЙН (НЕГгМАй ЕО~ 05Т!йЕ) и ДЖОН ФОН НЕЙМАН (ЗОНй 'чОй йЕОМАйй) (1946) кСвяаь с помопсью автоматического компьютера". — Прим. персе. ГЛАВА 2 ИНФОРМАЦИОННЫЕ СТРУКТУРЫ Нет, не увижу, это ясно, Поэмы, дерева прекрасней. — ДЖОЙС КИЛМЕР (ЗО!СЕ КШМЕй) (1913) (ПеревоД Л. Макаровой) Ах, я с таблицы памяти моей Все суетные записи сотру, — Гамлет (акт й сцена Б, строка 9в) (перевод м. лозинского) 2.1. ВВЕДЕНИЕ ПРОГРАммы оБычно оперируют информацией, которая содержится в таблицах.
В большинстве случаев эти таблицы представляют собой не просто бесформенную массу численных значений, а элементы данных с важными сгпрукшурными взаимосвязями. В простейшем виде таблица может выглядеть так, как простой линейный список элементов, а сведения о ее структурных свойствах можно получить, ответив на следующие вопросы. Какой элемент располагается в списке первым? Какой последним? Какие элементы предшествуют данному элементу, а какие следуют за ним? Сколько элементов содержится в списке? Ответив на такие вопросы, даже в этом простом случае можно получить богатую информацию о структуре данных (см.
раздел 2.2). В более сложных случаях таблица может иметь структуру двумерного массива (т. е. матрицы или решетки, состоящей из строк и столбцов) или даже и-мерного массива для п больше 2, древовидную структуру (сгее зсгцсгпге), которая представляет иерархические или разветвляющиеся связи, либо такую сложную многосвязную структуру (пш11111п)гег) зсгцсгпге) с большим количеством соединений, которая устроена, как человеческий мозг, Для правильного использования компьютера необходимо хорошо знать структурные взаимосвязи между данными, основные методы представления структур внутри компьютера, а также методы работы с ними.
В данной главе приводятся наиболее важные сведения об информационных структурах: статические и динамические свойства структур разных типов, средства выделения памяти для хранения и представления структурированных данных, эффективные алгоритмы для создания, изменения, удаления информации о структуре данных, а также для доступа к ней. В ходе изучения материала на нескольких важных примерах будет проиллюстрировано применение этих методов для решения широкого круга задач. В примерах будут рассмотрены топологическая сортировка, арифметика многочленов, моделирование дискретных систем, работа с разреженными матрицами, манипулирование алгебраическими формулами, а также создание компиляторов-д операционных систем.
Основное внимание здесь будет уделено представлению структуры внутри компьютера; ее преобразование между внешними и внутренними представлениями будет подробно рассмотрено в главах 9 и 10. Большая часть представленного здесь материала часто называется обработкой списков, особенно с тех пор как было создано достаточно систем программирования, например ЫЕР, предназначенных специально для работы со структурами общего типа под названием Списки. (Далее в этой главе слово "Список" с прописной начальной буквой будет использоваться для обозначения отдельного типа структуры, которая более подобно рассматривается в разделе 2.3.6.) Хотя в большинстве случаев системы обработки Списков очень полезны, они часто накладывают на работу программиста не всегда оправданные ограничения.
В собственных программах обычно эффективнее непосредственно использовать предлагаемые в этой главе методы, подгоняя для конкретного приложения формат данных и алгоритмы их обработки. Многие разработчики программного обеспечения все еще считают, что методы обработки Списков очень сложны (и потому вынул;цены использовать интерпретаторы сторонних разработчиков или уже готовые наборы процедур) и что обработка Списков может выполняться лишь некоторым строго определенным способом.
Как будет показано ниже, ничего сверхъестественного, загадочного илн трудного в работе со сложными структурами нет. Приведенные здесь методы являются частью арсенала каждого программиста, и их можно использовать при создании программ на языке ассемблера или на таких алгебраических языках, как РОНТВЛМ, С и Ъата. Методы работы с информационнымн структурами будут проиллюстрированы здесь на примере компьютера М1Х. Читателю, которого не интересует подробная структура программ для компьютера М1Х, следует изучить хотя бы способы, с помощью которых информация о структуре представляется в памяти компьютера М1Х.
Здесь важно определиться с терминами и обозначениями, которые будут довольно часто использоваться. Информация в таблице состоит из набора узлов (пи(еэ); некоторые авторы называют их записями (гесогг1в), объектами (епббеэ) или цепочками (Ьеабэ) . Иногда вместо термина "узел" будут использоваться термины "предмет" и "элемент". Каждый узел состоит из одного или нескольких последовательных слов в памяти компьютера, которые могут быть разделены на именованные части — поля.
В простейшем случае узел представляет собой только одно слово и содержит только одно поле, охватывающее это слово целиком. В качестве другого и более интересного примера рассмотрим элементы таблицы, которая предназначена для представления игральных карт. Предположим, что узлы в ней состоят из двух слов, которые делятся на пять полей — ТАС, 3911, ЕАМК, МЕХТ и Т1ТЬЕ: (Так выглядит формат содержимого двух слов в компьютере М1Х.
Следует напомнить, что слово в компьютере М1Х состоит нз пяти байтов и знака (см, раздел 1.3.1),) В этом примере предполагается, что каждое слово имеет знак "+" (плюс). Адрес (аИгеэз) узла, который также называется связью (Ипк), указателем (рохпФег) или ссылкой (ге1егепсе) на этвт узел, является адресом его первого слова. Адрес часто указывается относительно некоторой базовой ячейки памяти, но в этой главе для простоты предполагается, что адрес является абсолютным.
Любое поле внутри узла может содержать числа, буквы, ссылки или нечто другое, заданное программистом. В приведенном выше примере колода карт для раскладывания пасьянса может быть представлена следующим образом: ТАО = 1 означает, что карта обращена лицевой стороной вниз, ТАО = 0 †лицев стороной вверх; 801Т = 1, 2, 3 или 4 означает масть карты, т. е. трефы, бубны, черви или пики соответственно; ЕАИК = 1, 2,..., 13 означает ранг карты, т. е. туз, двойка,..., король; ИЕХТ является связью с картой, расположенной под данной картой в этой же колоде; Т1ТЕЕ представляет предназначенное для печати имя карты из пяти символов. Типичная колода карт может выглядеть так, как показано ниже. Карты Представление в компьютере 100: + 1 1 10 Л 101: + „ 1 0 о С 388: + 0 4 3 100 (2) 387: + и о 3 о 8 242: + 0 2 2 388 243: + и и 2 и 0 Адреса карт в компьютерном представлении показаны здесь в виде чисел 100, 386 и 242, хотя в данном примере они могли бы быть любыми, поскольку каждая карта связана со следующей картой, расположенной под ней.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
