Таблица элементов

редактировать

A Таблица элементов - это структура данных, обычно используемая для представления последовательности элементов текстовый документ. Создается начальная ссылка (или "диапазон") на весь исходный файл, а последующие вставки и удаления создаются как комбинации одной, двух или трех ссылок на разделы исходного документа или диапазонов, связанных с более ранними. вставки.

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

Это структура данных была изобретена Дж. Стротером Муром.

Содержание

  • 1 Описание
  • 2 Операции
    • 2.1 Индекс
      • 2.1.1 Пример
    • 2.2 Вставить
    • 2.3 Удалить
  • 3 Сложность времени
  • 4 Использование
  • 5 См. Также
  • 6 Ссылки

Описание

Для этого описания мы используем buffer как неизменяемый блок для хранения содержимого.

Таблица частей состоит из трех столбцов:

  • Какой буфер
  • Начальный индекс в буфере
  • Длина в буфере

Помимо таблицы, два буферы используются для обработки редактирования:

  • «Исходный буфер»: буфер исходного текстового документа. Этот буфер доступен только для чтения.
  • «Добавить буфер»: буфер во временный файл. Этот буфер предназначен только для добавления.

Операции

Индекс

Определение: Индекс (i): вернуть символ в позиции i

Получить i-й символ, считывается соответствующая запись в таблице штук.

Пример

Для следующих буферов и таблицы частей:

BufferContent
Исходный файлipsum sit amet
Добавить файлLorem deletedtext dolor
Таблица элементов
КакойНачальный индексДлина
Добавить06
Исходный06
Добавить185
Исходный69

Для доступа к i-му символу ищется соответствующая запись в таблице штук.

Например, чтобы получить значение Index (15), извлекается 3-я запись таблицы частей. Это связано с тем, что третья запись описывает символы от 12 до 17 (первая запись описывает символы от 0 до 5, следующая - от 6 до 11). Запись в таблице элементов инструктирует программу искать символы в буфере «добавить файл», начиная с индекса 18 в этом буфере. Относительный индекс в этой записи равен 3 (15 - 12), что делает значение Index (15)символом «o».

Для буферов и таблицы частей, приведенных выше, показан следующий текст:

Lorem ipsum dolor sit amet

Буфер подразумевает такую ​​последовательность действий:

начало: ipsum sit amet (таблица единиц теперь Исходная [0,9]) вставка: Lorem ipsum sit amet (таблица единиц теперь Добавлена ​​[0,6], Исходная [0,9]) вставка «удаленного текста» где-то «удаленный текст» удаляется (но остается в буфере добавления) вставка: Lorem ipsum dolor sit amet (таблица элементов заканчивается на конечном состоянии)

Вставить

Вставка символов в текст состоит из:

  • добавления символов в буфер «добавить файл» и
  • обновления записи в таблице частей (разбиения записи на две или три)

Удалить

Удаление включает только изменение соответствующей записи в таблице элементов.

Сложность по времени

Хотя таблица элементов сама по себе является структурой данных, в ней не указывается, как ее следует реализовать. Временная сложность операций зависит от того, как таблица реализуется. Одна из возможных реализаций таблицы элементов - это развернутое дерево, поскольку оно обеспечивает быстрый доступ к элементам, к которым недавно осуществлялся доступ.

Использование

Некоторые используют часть в ОЗУ внутреннюю таблицу, включая Bravo, Abiword и Visual Studio Code.

Функция "быстрого сохранения" в некоторых версиях Microsoft Word использует таблицу элементов для включения формат файла на диске.

Для представления текстовых файлов на диске в Oberon System используется метод цепочки элементов, который позволяет частям одного документа указывать на сохраненный текст в другом документе, похожем на включение.

См. также

  • Веревка (информатика)
  • буфер промежутка, структура данных, обычно используемая в текстовых редакторах, которая позволяет выполнять эффективные операции вставки и удаления, сгруппированные рядом там же

Ссылки

.

Последняя правка сделана 2021-06-02 05:11:26
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте