К. Хамахер, З. Вранешич, С. Заки - Организация ЭВМ - 5-е издание (2003) (1114649), страница 27
Текст из файла (страница 27)
Благодаря этому программа получается более эффективной, Если система команд компьютера позволяет перемещать данные из одного места памяти в другое, минуя регистры, тогда код обмена во внутреннем цикле, состоящий из четырех команд (рис. 2.34 б), можно сократить до трех команд: МочеВуте (КО,К2),(КО,К1) МочеВусе КЗ,(КО,К2) МочеВуте (КО,К1),КЗ Такую возможность поддерживает, в частности, процессор 68000 (см. главу 3). Программа, приведенная на рис. 2.34, б, работает корректно лишь в том случае, если в списке содержатся хотя бы два элемента, поскольку проверка условия завершения цикла выполняется в конце цикла. Таким образом осуществляется как минимум один проход по циклу, независимо от значения ж 2.11.3. Связные списки Во многих прикладных программах, не предназначенных для выполнения инженерных расчетов, упорядоченный список элементов данных должен быть представлен в памяти таким образом, чтобы в него легко было добавлять новые элементы или удалять из любого места ненужные, сохраняя определенный порядок.
Такая структура более универсальна, чем стек или очередь (см. раздел 2.8), которые позволяют удалять и добавлять данные только в начало и конец списка. Рассмотрим пример. Список оценок, полученных студентами в результате трехкратного тестирования, на примере которого в разделе 2.5 рассматривался индексный режим адресации, содержит в первом слове каждой записи код студента (рис. 2.14). Предположим, мы хотим поддерживать этот список (он хранится в непрерывном блоке памяти) отсортированным по кодам студентов, а записи о студентах при этом могут добавляться и удаляться. Это позволит выводить на экран и печатать список в упорядоченном виде.
Если после создания списка студент по какой-то причине будет исключен из группы, в списке останется пустая запись. В случае добавления в список новых оценок или печати такового эту пустую запись придется каждый раз пропускать. В еще более сложной ситуации мы окажемся, если после создания списка в группу будет включен новый студент. Чтобы список остался упорядоченным, нам придется сдвинуть в нем все записи начиная с номера, следующего за номером добавляемой записи. Точно так же при выходе студента из группы можно сдвинуть все записи, следующие за его удаленной записью, чтобы в списке не оставалось пробела.
Обеих этих сложных операций позволяет избежать структура данных, называемая связным списков. Как и в обычном списке, каждая запись в связном занимает четыре слова, но последовательные записи необязательно должны занимать последовательные блоки памяти. Для того чтобы связать записи в упорядоченный список, в каждую из них включают поле указателя длиной в одно слово, содержащее адрес следующей записи списка. Схематическое представление такой структуры данных показано на рис. 2.35, а.
Первую запись связного списка иногда называют его «головой», а последнюю — «хвостом». 2.11. Примеры программ 115 Для того чтобы в список добавить новую запись, между записями 1 и ( + 1, нужно скопировать поле указателя из записи 1 в новую запись, а адрес новой записи поместить в поле указателя записи й Эта операция схематически показана на рис. 2.35, 6. Для удаления записи 1 значение из ее поля указателя копируется в поле указателя записи ( — 1.
Поле эзателя Последний элемент списка Первый элемент списка Рис. 2.36. Связный список: структура связного списка; (в); добавление новой записи между записями 1 и 2 (б) На рис. 2.36 приведен пример записей с результатами тестов, связанных между собой по принципу связного списка и отсортированных по кодам студентов. Длина каждой записи теперь составляет пять слов. В первом слове, определенном в качестве ключевого поля, содержится код студента, во втором — поле указателя, а остальные три слова хранят результаты тестов. Если слово имеет длину 32 разряда, для списка выделяется область памяти длиной 2000 байт начиная с адреса 1000.
В таком случае каждая запись занимает 20 байт и выделенной области хватает для хранения 100 записей. Студенту, который включается в группу, назначается один из блоков памяти длиной 5 слов. Записям удобно назначать адреса 1000, 1020, 1040, ..., 2980, но так делать необязательно. Кроме того, никакой связи между кодами студентов и порядком их включения в группу не существует.
Таким образом, блоки записей, упорядоченные по кодам студентов, будут совершенно непредсказуемым образом разбросаны по выделенной для списка области памяти и иметь произвольные адреса из диапазона от 1000 до 2980. Запись с наименьшим кодом находится в начале списка, а с наибольшим— в конце. Прн работе со списком адрес его начала удобно хранить в регистре процессора, называемом указаглвлим навала списка. В нашем примере это адрес 2320.
116 Глава 2. Машинные команды и программы Адрес 1040 в поле указателя первой записи определяет местоположение второй записи. В поле указателя второй записи хранится адрес третьей записи — 1200. Поле указателя последней записи содержит значение О, обозначающее конец спи- ска. Если список пуст, 0 содержит поле указателя его начала. Ключевое поле Поле (код студента) указателя Поля данных (Результаты тестов) Адрес в памяти 2320 запись 1 слово 1 слово 3 слова Голова Вторая запись Третья запись Предпоследняя запись Последняя запись Хвост Рис.
2.3а. Записи с результатами тестов, хранящиеся в виде связного списка Вставка новой записи А теперь мы более подробно рассмотрим процесс добавления новой записи в список, показанный на рис. 2.36. Предположим, что новая запись имеет код 28241, а следующий доступный блок памяти располагается по адресу 2960. Мы сканируем список записей начиная с головной, пока не достигнем записи, код хоторой будет больше кода добавляемой записи. Это запись с кодом 28370, расположенная по адресу 1200. Теперь введем в поле указателя новой записи значение 1200, а адрес новой записи, 2960, запишем в поле указателя предыдущей записи, расположенной по адресу 1040, заменив тем самым исходное значение 1200.
Теперь новая 2. 11. П римеры программ 1 1 7 запись помещена на третье место списка, между второй и третьей записями исходного списка. Выполняющая эту операцию подпрограмма приведена на рис. 2.37. Она состоит иэ трех частей, обрабатывающих три возможные ситуации, а именно; текущий список пуст, новая запись становится первой записью непустого списка и новая запись добавляется в любое другое место списка после первой записи. Последняя ситуация включает и тот случай, когда новая запись становится последней записью списка. №О,КНЕА)) НЕА1) КХЕЖКЕС,КНЕА1) 1ХЯЕКТ10Х Сопзраге ВгапсЬ>0 Новая запись становится единственным элементом Моче Кеспгп Нс пусто ! с — в НЕА1) списка (КНЕАВ),(КХЕЪ"КЕС) ЯЕАКСН КНЕА1),4(КХЕЪ'КЕС) 1 Новая запись ~ становится КХЕтч'КЕС,КНЕА1) 1 первой в списке Сопзрвте ВтапсЬ>0 Вставка новой записи записи с — в- ЗЕАКСН Моче Моче Кегпгп Моче Моче КНЕА1),КС()ККЕХТ 4(КС() ККЕХТ),КХЕХТ №О,КХЕХТ ТА? 1.
(КХЕХТ),(КХЕЪ'КЕС) 1ХЯЕКТ КХЕХТ,КС()ККЕХТ МООР КХЕХТ,4(КХЕЪ'КЕС) КХЕ'ьч'КЕС,4(КС()ККЕХТ) 1.00Р Сопзрате ВгапсЬ-0 Согпраге ВгапсЬ<0 Новая запись становится последней Моче ВгапсЬ Моче Моче Кеспгп ис новой записи ну списка 1ХЯЕКТ ТА1 1. Рмс. 2.37. Подпрограмма для добавления новой записи в связный список Посмотрим, как подпрограмма обрабатывает три укаэанные ситуации. В ней используется целый ряд регистров процессора, которым мы, для того чтобы облегчить понимание программы, присвоили другие имена, более информативные по сравнению с традиционными КО, К1, К2 и т.
д. Указатель начала списка мы назвали КНЕА(), а регистр, содержащий адрес новой заг|иси, — КХЕ%'КЕС. Еще два регистра, КС13ККЕХТ и КХЕХТ, во время сканирования списка содержат адреса текущей и следующей записей. Поле указателя в новой записи первоначально установлено в О. Если она становится последней записью списка, значение этого поля не меняется. Первая пара команд сравнения и перехода проверяет, не пуст ли список. Если список пуст (КНЕАП содержит О), новая запись становится единственным элементом списка и ее адрес просто записывается в КНЕА1), после чего выполняется команда возврата. В противном случае вторая пара команд сравнения и перехода проверяет, станет ли новая запись первой в списке, Если станет, две следующие команды пересылки изменяют содержимое ее поля указателя и регистра КНЕА?), после чего выполняется команда возврата.
Если новая запись не станет первой в списке, последняя часть подпрограммы определяет то место списка, куда она должна быть вставлена. Запись вставляется в нужное место с применением двух последних команд пересылки или добавляется в конец списка последней командой пересылки.
Для того чтобы упростить зту подпрограмму, мы не стали приводить команды сохранения и восстановления регистров. Удаление записи Удаление существующей записи из связного списка — операция более простая. Нам нужно просканировать список и найти в нем запись с заданным кодом, а по- том просто изменить значение указателя в предшествующей записи. Подпро- грамма, выполняющая эту операцию, приведена на рис. 2.38. (КНЕА?З),К1?)Х() М ВЕАКСН 4(КНЕА?)),КНЕА?) ?)ЕЬЕТ10Х Сотраге ВгапсЬ>0 Моче Кегпгп Моче Моче Не первая запись яеьвсн 1.00Р Со герате ВгапсЬ-0 Моче ВгапсЬ Моче Моче Кегпгп ?) Е1.ЕТЕ Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
