Д. Кнут - Искусство программирования том 1 (1119450), страница 83
Текст из файла (страница 83)
Перед каждым шагом моделирования для этого следует установить НЕНЧ[А] еЧ[А3 для 1 < А < п, затем записать все изменения величин Ч[А3 в ЧЕНЧ[А] и наконец установить Ч[А] +- ЧЕНЧ[А], 1 < А < и Но этот "очень прямолинейный" метод не очень подходит по следующим причинам (1) часто и очень велико, а количество изменяемых переменных очень мало, (2) часто переменные упорядочены не в виде таблицы Ч[13,, Ч[и], а разбросаны в памяти самым произвольным образом, (3) этот метод не может обработать случай (что обычно является ошибкой), когда одна переменная принимает два значения на одном и том же шаге моделирования Предполагая, что количество изменяемых на одном шаге переменных очень малб, придумайте эффективный алгоритм, который моделирует нужные действия, используя две вспомогательные таблицы ЧЕНЧ[А] и 11НК[А], 1 < А < и. Если возможно, алгоритм должен обнаружить ошибку в случае, если одна переменная принимает два значения на одном и том же шаге, ь 12.
(ЕЕ] Почему в описанной в этом разделе программе моделирования лучше использовать дважды связанные списки вместо однократно связанных или последовательных списков? 2.2.6. Массивы и ортогонвльные списки Одним нз простейших обобщений линейного списка является двумерный (или, в более общем случае, многомерный) массив данных. Например, рассмотрим следующую матрицу размера т х и: А[1 Ц А[1 23 . А[1,п] А[2,Ц А[2,23 ... А[2„п3 А[пэ,13 А[гп,2] ...
А[т,п] В этом двумерном массиве каждый узел А [у,)с] принадлежит двум линейным спискам; списку "строки у' А[3,1],А[3,2],...„А[у,п] и списку "столбца Аи А[1,к], А [2,)с],..., А[т,к]. Такие ортогональные списки строк и столбцов н образуют двумерную структуру матрицы. Аналогичные замечания относятся и к многомерным массивам данных.
Последовательное распределение. Когда массив хранится по последоваглельно расположенным адресам, память обычно распределяется так, чтобы (2) 10С(АУ,К]) = ао+а~.)+атК, где ао, а~ и аз — константы. Рассмотрим более общий случай: предположим, что имеется четырехмерный массив элементов длиной в одно слово ЦП,З,К,Ц, где 0 < 1 < 2, 0 < Л < 4, 0 < К < 10, 0 < 1. < 2. Память следовало бы распределить таким образом, чтобы ЕОС(ЦП 3 К,Е]) = ао+а~1+ атд+азК+а41.. (3) Это значит, что изменение 1, Л, К или Ь сразу же приведет к вычислению изменения адреса элемента ЦП,З,К,Е].
Наиболее естественный (н наиболее распространенный) способ распределения памяти заключается в упорядочении элементов согласно лексикографическому порядку их индексов (упр. 1.2.1 — 15(с1)), который иногда называют "упорядочение по строкам": Ц[0,0,0,0], Ц[0,0,0,1], Ц[0,0,0,2], Ц[0,0,1,0], Ц[0,0,1,1], ..., Ц[0,0,10,2], Ц[0,1,0,0], ..., Ц[0,4,10,2], ЦП,О,О,О], ..., Ц[2,4,10,2]. Нетрудно видеть, что этот порядок удовлетворяет требованиям (3) и может быть выражен так: ЕОС(ЦП,З,К,Е]) = 1ЛС(0[0,0,0,0]) + 1651+ 333+ ЗК+ 1. (4) Вообще, А-мерный массив с элементами А Пю1з,...,1А] длиной с слов при 0 < 1~ < 4, 0 < Хг < Нз, ..., 0 < 1ь < Нь может храниться в памяти в виде ЕОС(АП~,1з, ...,1ь]) =ЕОС(А[0,0,...,0])+с(Из+1)... (Нь+1)1~+ +с(На+1)1ь ~+с1ь = 1.0С (А [0,0,..., 0] ) + ~ а.1.
(5) 1<~ <ь где П(Н+ ) (6) ~ <в«ь Для доказательства этой формулы заметим, что а,— это объем памяти, необходимой для хранения части массива А П,, ...,1„, 3„+,,..., Ль], где 1„..., 1, — константы, а Л„чч,...,Ль изменяются для всех 0 < Л„<.~ < Н„ч.ы..., 0 < Зь < аы Следовательно, по определению лексикографического порядка адрес АПы..., 1ь] будет измениться точно на эту величину при изменении 1„на единицу. Формулы (5) и (6) соответствуют значению числа 1~ 1з...
1ь в системе счисления со смешанным основанием (ппхео-гаа(х пшпЬег зуятеш). Например, для массива ТТМЕ[Н,О,Н,М,З] с 0 < Ю < 4, 0 < О < 7, 0 < Н < 24, 0 < М < 60 и 0 < 3 < 60 адрес элемента Т1МЕ[Н,О,Н,М,З] будет равен адресу Т1МЕ[0,0,0,0„0] плюс величина "Н недель+ 0 дней + Н часов+ М минут+ 3 секунд" в секундах.
Конечно, массив с 2 419 200 элементами может понадобиться только для очень экзотического приложения. Традиционный метод хранения массивов обычно подходит только для массива с полностью прямоугольной структурой, в которой все элементы А[1г,1г,...,1ь] имеют индексы в независимых диапазонах 1г < 1г < иг, 1г < 1г < иг, 1г < 1ь < иы В упр.
2 показано, как можно адаптировать формулы (5) и (6), когда нижние границы ((г, 1г,..., 1ь) не равны (0,0,...,0). Однако но многих случаях массив не является прямоугольным. Чаще всего он представляет собой треугольнуя матрицу, в которой хранятся только элементы А [г',А], например, для 0 < А < г < п: А [0,0] А [1, 0] А [1, П (7) А[п,О] А[п,Ц ... А[п,п] Как правило, известно, что все остальные элементы матрицы равны нулю или А[у,А] = А[А,)], так что достаточно хранить в памяти всего лишь около половины всех элементов матрицы. Для хранения нижней треугольной матрицы (7) в -'(п+ 1) (и+ 2) последовательных позициях памяти следует отказаться от линейного распределения памяти (2) и использовать распределение в виде (8) 10С(А[Э,К]) = по+ Л(Л) + Л(К) (10) А[),А] = С[),А], В[),Ц = С[А,) + П .
Таким образом, получим А[0,0] В[0,0] В[1,0] ... В[п,О] АП,О] А[1,П В[1, П ... В[п, П С [О, 0] С [О, П С [О, 2] ... С [О, и+ П С[1,0] СП, П С[1,2] ... С[1,п+П С[п,О] С[п, П С[п,2] ...С[п,п+П А[п,О] А[и, П А[п,2] ...В[п,п] Так, две треугольные матрицы могут быть компактно упакованы в (п + 1)(п + 2) ячейках памяти с линейной адресацией типа (2). где [~ и гг — функции одной переменной. (Константа ао может быть включена в функцию Л или ~г.) Если способ адресации имеет вид (8), доступ к произвольному элементу А [г, И можно достаточно легко осуществить с помощью двух (очень коротких) вспомогательных таблиц со значениями [г и гг. К тому же эти функции потребуется вычислить только один раз.
Причем лексикографический порядок индексов массива (7) удовлетворяет условию (8), а для элементов длиной в одно слово получим простую формулу 10С(А[Э,К]) = 10С(А[0,0]) + + К. 1(1 + П 2 (9) Однако существует более эффективный способ хранения треугольных матриц одного и того же размера. Предположим, что нужно сохранить две матрицы А [ г, А] и В [у,к], где 0 < А < г < п.
Тогда их можно свести к одной матрице С [1, А], где 0 < ] < п, О < А < п + 1,используя условие Обобщение треугольных матриц для больших измерений называется тетраэдральным массивом [геггайес[га1 агтау). Рассмотрение этой интересной темы продолжается в упр, б-8.
Типичные приемы программирования при работе с последовательно адресуемыми массивами описаны в упр. 1.3.2 — 10 и в двух ответах к данному упражнению. Особенно интересными в этих программах являются фундаментальные методы эффективного обхода строк и столбцов, а также использование последовательных стеков. Женщина, 21 год, карие глаза, темные волосы Мужчина, 24 года, карие глаза, темные волосы Женщина, 22 года, зеленые глаза, светлые волосы Мужчина, 28 лег, светло-карие глаза, светлые волосы Женщина, 22 года, голубые глаза, рыжие волосы Женщина, 21 год, голубые глаза, светлые волосы РВИОМ [6] РЮБОМ [8] РМВМОМ [4] РММЗОМ [8] Рва Мам [2] РМММОМ [1] Рис.
13. Каждый узел находится н четырех различных списках. В качестве примера использования связанного распределения памяти для прямоугольных списков рассмотрим раэреэгсенные магприцы (зрагзе та1ггсез) (т, е, матрицы большого размера, в которых большинство элементов равно нулю). Назиачеиие задачи — организовать работу с такими структурами, как с обычной матрицей, Связанное распределение. Связанное распределение памяти прекрасно подходит и для представления многомерных массивов данных.' Вообще, узлы могут содержать й полей связи, по одному для каждого списка, которому принадлежит этот узел.
Связанное распределение памяти обычно используется в случаях, когда массивы данных не строго прямоугольиы. В качестве примера рассмотрим список, в котором каждый узел представляет описание некоторого человека, с четырьмя полями связи для обозначения: пола БЕХ, возраста АСЕ, цвета глаз ЕУЕЗ и цвета волос НА18. Например с помощью полей ЕЛЕЯ связываются узлы с одним цветом глаз и т.
д. (рис. 13). Тогда нетрудно представить эффективиый алгоритм вставки в этот список узлов с описаниями новых людей. Операция удаления в такой структуре будет выполняться гораздо медленнее, ио ее эффективность можно повысить, используя дважды связанные списки. В таком случае можно представить алгоритмы с разной степенью эффективности для выполнения, например, таких запросов: "Найти всех голубоглазых блондинок в возрасте от 21 до 23 лете (см. упр. 9 и 10). Подобного рода задачи, в которых узлы одного списка могут принадлежать нескольким другим спискам, встречаются довольно часто. Действительно, описанная в предыдущем разделе модель работы лифта содержит узлы, которые находятся сразу в двух списках: [)0Е0Е и ЫА1Т. но достичь прн этом большой зкономии времени и пространства в памяти за счет исключения из нее равйых нулю элементов.
Один способ организации произвольного доступа к элементам этой матрицы заключается в использовании методов хранения и извлечения данных, которые описаны в главе 6, т. е. поиск элемента А[у,А3 выполняется на основе ключа "(у, А)". Существует, однако, еще один способ работы с разреженными матрицами, который часто более предпочтителен, поскольку он точнее соответствует структуре матрицы. Именно этот метод будет рассмотрен ниже. Рассматриваемое здесь представление состоит из циклически связанных списков, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
