Простые операции над списками

В предыдущем разделе при перечислении преимуществ связанных списков в п. (а) и (Ь) молчаливо предполагалось, что свободные ячейки доступны для хранения данных всегда, когда это необходимо, и что в первую очередь для этой цели повторно используются ячейки исключенных элементов. Чтобы реализовать такой подход, строится другой список, называемый списком доступного пространства, который представляет собой связанный список всех свободных ячеек. Каждый раз, когда в список включается новый элемент, он размещается в ячейке, указанной в качестве начала списка доступного пространства, и эта первая ячейка удаляется из списка доступного пространства.

При этом корректируется строка таблицы индексов, связанная со списком доступного пространства, и теперь ее указатель будет равен указателю, содержавшемуся в ячейке, только что удаленной из вершины списка доступного пространства, т. е. будет содержать адрес следующей доступной свободной ячейки.

Когда элемент исключается, его ячейка удаляется из «полезного» списка и становится первой ячейкой списка доступного пространства, при этом также корректируется таблица индексов. Чтобы при каждом добавлении или исключении элемента сохранять порядок внутри списка, необходимо корректировать указатели логических соседей этого элемента. Логическое место нового элемента определяется в соответствии с его ключом порядка, для чего последовательно просматривается список, в то время как физическое место' нового элемента — эта первая ячейка списка доступного пространства.

Если необходимо, включить в список L элемент D, то этот список последовательно просматривается, начиная с ячейки 20, адрес которой указан в соответствующей строке таблицы индексов. Путем сравнения ключа порядка этого элемента с другими ключами порядка определяется, что новый элемент логически должен быть размещен между элементами С и Е. Из таблицы индексов выбирается адрес первой свободной ячейки, 12, и записывается в поле указателя элемента С. Значение указателя в ячейке 12, равнее 24, заносится в поле указателя строки таблицы индексов, соответствующей списку доступного пространства. Новая информация (D) записывается в ячейку 12, а значение указателя, хранившееся в начале операции в ячейке 30 (элемента С) и временно запасенное, теперь размещается в поле указателя-ячейки 12. При исключении элемента D из списка будут выполняться обратные действия.

Для обработки списков созданы специальные языки, как, например, ЛИСП, операторы которых обеспечивают автоматическое выполнение рассмотренных действий [23]. Однако в большинстве языков высокого уровня, за исключением ПЛ/1, программист должен явно писать команды коррекции указателей.

Часто возникают некоторые практические трудности, когда в списке используются только прямые указатели, т. е, указатели, содержащие либо адрес логически следующего элемента, либо признак конца списка. При такой организации, если просмотр элементов списка начинается не с первой ячейки, то доступной оказывается только часть списка. Другая трудность связана с необходимостью исключения из списка элемента, например D, который был найден не в результате последовательного просмотра списка или который является также и членом других списков. Ясно, что в этом случае необходимо скорректировать все указатели, ссылающиеся на D, но может оказаться так, что неизвестно, где эти указатели находятся. Если имеется только одна цепочка данных и D не является последним элементом этой цепочки, то такую трудность преодолеть легко. Для этого достаточно переслать в ячейку D содержимое логически следующей за ней ячейки, а затем удалить эту освободившуюся ячейку из- связанного списка (и включить ее в список доступного пространства), как это показано на рис. 9.29.

Тем не менее для упрощения операций исключения, а также по некоторым, другим причинам, иногда более удобно увеличить количество указателей в последовательной структуре. На рис. 9.30 изображены две наиболее часто используемые структуры.

В структуре кольца указатель последнего элемента содержит ссылку на первый элемент, а не признак конца списка. Эта структура также называется круговым списком.

В двойном связанном списке каждая ячейка содержит два указателя. Прямой указатель содержит адрес логически следующей ячейки, а обратный указатель — адрес логически предыдущей ячейки.


Организация данных и структуры данных Метод обменной сортировки с выбором Метод турнирной сортировки Методом квадратичной сортировки Метод вставки Методы Замещения Слияние рассортированных подфайлов Осциллирующей сортировки Многофазная сортировка Сравнение методов внешней сортировки Генераторы программ сортировки слияния Информация и ее представление в вычислительных машинах Ассоциативная структура Последовательная структура Связанный список Простые операции над списками Иерархические структуры Древовидная структура Линейное представление древовидной структуры Преобразование арифметических выражений в списковые структуры Сетевая структура Системы управления базами данных Инвертированные файлы Пример инвертированного файла Поиск по нескольким ключам Элементы системы управления базой данных Работа системы управления базой данных Роль администратора базы данных Определения Организация в записи Компоненты записи Блоки Форматы блоков и записей Организация и методы доступа Последовательная организация Метод доступа с очередями Библиотечная организация Оглавление тома Метки оглавления тома Метки тома магнитной ленты Прямая организация Прямая адресация Методы рандомизации Сравнение методов рандомизации Индексно-последовательная организация Область основных данных Области переполнения Области индексов Произвольный поиск Режимы обработки Добавление новых записей Статистика Общее про методы сортировки Сортировка в основной памяти Метод сортировки посредством выбора	Простые операции над списками В предыдущем разделе при перечислении преимуществ связанных списков в п. (а) и (Ь) молчаливо предполагалось, что свободные ячейки доступны для хранения данных всегда, когда это необходимо, и что в первую очередь для этой цели повторно используются ячейки исключенных элементов. Чтобы реализовать такой подход, строится другой список, называемый списком доступного пространства, который представляет собой связанный список всех свободных ячеек. Каждый раз, когда в список включается новый элемент, он размещается в ячейке, указанной в качестве начала списка доступного пространства, и эта первая ячейка удаляется из списка доступного пространства. При этом корректируется строка таблицы индексов, связанная со списком доступного пространства, и теперь ее указатель будет равен указателю, содержавшемуся в ячейке, только что удаленной из вершины списка доступного пространства, т. е. будет содержать адрес следующей доступной свободной ячейки. Когда элемент исключается, его ячейка удаляется из «полезного» списка и становится первой ячейкой списка доступного пространства, при этом также корректируется таблица индексов. Чтобы при каждом добавлении или исключении элемента сохранять порядок внутри списка, необходимо корректировать указатели логических соседей этого элемента. Логическое место нового элемента определяется в соответствии с его ключом порядка, для чего последовательно просматривается список, в то время как физическое место' нового элемента — эта первая ячейка списка доступного пространства. Если необходимо, включить в список L элемент D, то этот список последовательно просматривается, начиная с ячейки 20, адрес которой указан в соответствующей строке таблицы индексов. Путем сравнения ключа порядка этого элемента с другими ключами порядка определяется, что новый элемент логически должен быть размещен между элементами С и Е. Из таблицы индексов выбирается адрес первой свободной ячейки, 12, и записывается в поле указателя элемента С. Значение указателя в ячейке 12, равнее 24, заносится в поле указателя строки таблицы индексов, соответствующей списку доступного пространства. Новая информация (D) записывается в ячейку 12, а значение указателя, хранившееся в начале операции в ячейке 30 (элемента С) и временно запасенное, теперь размещается в поле указателя-ячейки 12. При исключении элемента D из списка будут выполняться обратные действия. Для обработки списков созданы специальные языки, как, например, ЛИСП, операторы которых обеспечивают автоматическое выполнение рассмотренных действий [23]. Однако в большинстве языков высокого уровня, за исключением ПЛ/1, программист должен явно писать команды коррекции указателей. Часто возникают некоторые практические трудности, когда в списке используются только прямые указатели, т. е, указатели, содержащие либо адрес логически следующего элемента, либо признак конца списка. При такой организации, если просмотр элементов списка начинается не с первой ячейки, то доступной оказывается только часть списка. Другая трудность связана с необходимостью исключения из списка элемента, например D, который был найден не в результате последовательного просмотра списка или который является также и членом других списков. Ясно, что в этом случае необходимо скорректировать все указатели, ссылающиеся на D, но может оказаться так, что неизвестно, где эти указатели находятся. Если имеется только одна цепочка данных и D не является последним элементом этой цепочки, то такую трудность преодолеть легко. Для этого достаточно переслать в ячейку D содержимое логически следующей за ней ячейки, а затем удалить эту освободившуюся ячейку из- связанного списка (и включить ее в список доступного пространства), как это показано на рис. 9.29. Тем не менее для упрощения операций исключения, а также по некоторым, другим причинам, иногда более удобно увеличить количество указателей в последовательной структуре. На рис. 9.30 изображены две наиболее часто используемые структуры. В структуре кольца указатель последнего элемента содержит ссылку на первый элемент, а не признак конца списка. Эта структура также называется круговым списком. В двойном связанном списке каждая ячейка содержит два указателя. Прямой указатель содержит адрес логически следующей ячейки, а обратный указатель — адрес логически предыдущей ячейки.