Редактирование текстов

Редактирование текстов
Гергель В.П., профессор ,
директор института ИТММ
Тема 2.2:
Методы программирования - 2
Учебный курс:

Содержание
Глава 2. Динамические структуры и представление на ЭВМ сложных математических моделей
2.2. Редактирование текстов
Выбор модели представления текста
Выбор структуры хранения текста
Реализация
схема наследования,
навигация,
доступ,
модификация структуры,
алгоритмы обхода,
итератор,
копирование
Повторное использование памяти (сборка мусора)
Вопросы для обсуждения
из 38
Редактирование текстов
ИТММ ННГУ, 2002-2020

из 38
ИТММ ННГУ, 2002-2020
1. Выбор модели представления текста …
Пример:
pFirst = NULL;
ListLen = 0;
1. Текст – линейная последовательность символов
2. Текст – линейная последовательность слов
(слово - линейная последовательность символов)
3. Текст – линейная последовательность строк, строки состоят из слов, слова – из символов и т.д.
Редактирование текстов

из 38
ИТММ ННГУ, 2002-2020
Математическая модель текста – иерархическая структура представления (дерево)
1. Выбор модели представления текста
Редактирование текстов

из 38
ИТММ ННГУ, 2002-2020
2. Выбор структуры хранения текста …
1. Уровень символов – список символов
2. Уровень слов – список слов
В первом поле звеньев вместо значения-слов можно поместить указатель на соответствующий список символов
3. Уровень строк – список строк
Редактирование текстов

из 38
ИТММ ННГУ, 2002-2020
На всех уровнях представления (кроме символов) значение задается указателем на соответствующую структуру ниже расположенного уровня
Определение 2.1. Разработанная структура хранения называется связным (иерархическим) списком
Абстрактная структура типа дерева представима в виде связного списка
В списке существуют делимые и неделимые (атомарные, терминальные) элементы (А-не, ТОМ-часть)
Визуальное представление текста содержит только атомарные элементы, структура хранения должна включать все элементы
2. Выбор структуры хранения текста …
Редактирование текстов

из 38
ИТММ ННГУ, 2002-2020
Разные типы звеньев – трудности при управлении памятью, дублирование программ обработки
Единый тип звена
typedef Tlink *PTLink;
class TLink{
PTLink pNext;
int Atom; // =1 – звено-атом
union {
PTLink pDown;
char Symb;
};
2. Выбор структуры хранения текста …
Редактирование текстов

из 38
ИТММ ННГУ, 2002-2020
Размер введенного унифицированного звена – 10 байт (=16 при учете округления при динамическом выделении памяти) ⇒ для представления символов такой вид звена является неэкономичным
Возможное решение проблемы – повышение уровня атомарности
Целесообразный уровень – уровень строк
2. Выбор структуры хранения текста …
Редактирование текстов

из 38
ИТММ ННГУ, 2002-2020
Структура звена
#define TextLineLength 20
typedef char TStr[TextLineLength];
class TTextLink : public TDatValue {
protected:
TStr Str;
TTextLink *pNext, *pDown;
};
2. Выбор структуры хранения текста …
Редактирование текстов

из 38
ИТММ ННГУ, 2002-2020
Указатель pNext есть ссылка на следующий элемент того же уровня
Указатель pDown есть ссылка на структуру хранения ниже расположенного уровня
Представление строки (атомарного элемента)
Признак атомарности элемента pDown==NULL
2. Выбор структуры хранения текста …
Редактирование текстов

из 38
ИТММ ННГУ, 2002-2020
Представление структурного элемента
Для ссылки на ниже расположенный уровень используется указатель pDown
Поле Str можно использовать для именования структурных элементов текста (название всего текста, его разделов, подразделов и т.д.)
2. Выбор структуры хранения текста …
Редактирование текстов

из 38
ИТММ ННГУ, 2002-2020
Пример структуры хранения
2. Выбор структуры хранения текста …
Редактирование текстов

из 38
ИТММ ННГУ, 2002-2020
2. Выбор структуры хранения текста
Базовые операции обработки звена Порождение звена (конструктор)
TTextLink ( TStr s=NULL, PTTextLink pn=NULL,
PTTextLink pd=NULL );
Переход к следующей звену
PTTextLink GetNext() { return pNext; }
Переход на подуровень
PTTextLink GetDown() { return pDown; }
Редактирование текстов

из 38
ИТММ ННГУ, 2002-2020
3. Реализация – схема наследования …
Класс, реализующий структуру хранения текста в виде связного списка
Редактирование текстов

из 38
ИТММ ННГУ, 2002-2020
PTTextLink pFirst; // корень дерева
PTTextLink pCurrent; // текущая строка
stack
Path; // стек траектории
// навигация
int GoFirstLink(void); // к первой строке
int GoDownLink (void); // к след. строке по Down
int GoNextLink (void); // к след. строке по Next
int GoPrevLink (void); // к пред. позиции
Указатель текущей строки pCurrent не включается в стек траектории движения по тексту
3. Реализация – навигация по структуре …
Редактирование текстов

из 38
ИТММ ННГУ, 2002-2020
3. Реализация – навигация по структуре
В стеке Path размечаются указатели на все звенья, лежащие на пути от начала текста до текущего звена
Редактирование текстов

из 38
ИТММ ННГУ, 2002-2020
3. Реализация – доступ к текущей строке
// доступ
string GetLine (void); // чтение текста текущего звена
void SetLine(string s); // замена текста текущего звена
Редактирование текстов

из 38
ИТММ ННГУ, 2002-2020
3. Реализация – модификация структуры …
// вставка и удаление строки в подуровне
void InsDownLine(string s);
void DelDownLine(void);
// вставка и удаление раздела в подуровне
void InsDownSection(string s);
void DelDownSection(void);
// вставка и удаление строки на том же уровне
void InsNextLine(string s);
void DelNextLine(void);
// вставка и удаление раздела на том же уровне
void InsNextSection(string s);
void DelNextSection(void);
Редактирование текстов

из 38
ИТММ ННГУ, 2002-2020
3. Реализация – модификация структуры …
Вставка строки и раздела в подуровне
Редактирование текстов

из 38
ИТММ ННГУ, 2002-2020
3. Реализация – модификация структуры
Удаление строки и раздела в подуровне
Операция удаление строки не выполняется, если исключаемый элемент не является атомарным
Редактирование текстов

из 38
ИТММ ННГУ, 2002-2020
3. Реализация – алгоритмы обхода …
Печать текста: схема обхода – текст текущей строки, текст подуровня, текст следующего раздела текста того же уровня (top-down-next)
while (1) {
if ( pLink != NULL ) {
cout << pLink->Str; // обработка звена
St.push(pLink); // запись в стек
pLink = pLink->pDown;// переход на подуровень
}
else if ( St.empty() ) break;
else {
pLink = St.top(); St.pop();// выборка из стека
pLink = pLink->pNext; // переход по тому же
} // уровню
}
Редактирование текстов

Ввод текста из файла: уровень текста в файле можно выделить строками специального вида (например, скобками '{' и '}')
Глава 2
{
2.1. Полиномы
{
1. Определение
2. Структура
}
2.2. Тексты
{
1. Определение
2. Структура
}
}
Общая схема алгоритма
Повторить
ввод строки
ЕСЛИ '}' ТО Завершить
ЕСЛИ '{' ТО Выполнить
рекурсивно Ввод_текста
Добавить строку на том же
уровне
из 38
ИТММ ННГУ, 2002-2020
3. Реализация – алгоритмы обхода
Редактирование текстов

из 38
ИТММ ННГУ, 2002-2020
3. Реализация – итератор …
Схема обхода TDN, нерекурсивный вариант
Корневые звенья необработанных разделов текста запоминаются в стеке
Текущая строка в стеке не хранится (кроме корневого звена всего текста)
Редактирование текстов

из 38
ИТММ ННГУ, 2002-2020
3. Реализация – итератор …
Инициализация (Reset) – установка на корневое звено текста
pCurrent = pFirst;
if ( pCurrent != NULL ) {
St.push(pCurrent);
if ( pCurrent->pNext != NULL )
St.push(pCurrent->pNext);
if ( pCurrent->pDown != NULL )
St.push(pCurrent->pDown);
}
Редактирование текстов

из 38
ИТММ ННГУ, 2002-2020
3. Реализация – итератор
Переход к следующему звену текста (GoNext)
Получить звено из стека
ЕСЛИ звено не является корнем всего текста
ТО поместить следующие звенья (по указателям pNext и pDown) в стек
pCurrent = St.top(); St.pop();
if (pCurrent != pFirst ) {
if ( pCurrent->pNext != NULL )
St.push(pCurrent->pNext);
if ( pCurrent->pDown != NULL )
St.push(pCurrent->pDown);
}
Редактирование текстов
Пример: программа

из 38
ИТММ ННГУ, 2002-2020
3. Реализация – копирование текста …
Общая замечания
Для копирования текста необходимо предварительно скопировать разделы текста, на которые указывают указатели pDown и pNext ⇒ алгоритмы обхода NDT или DNT
Для навигации по тексту-копии также необходим стек; использование стеков исходного текста и текста-копии должны быть согласованы
Редактирование текстов

из 38
ИТММ ННГУ, 2002-2020
3. Реализация – копирование текста …
Общая схема алгоритма Для навигации по исходному тексту и тексту-копии используется один – объединенный - стек
Каждое звено текста копируется за два прохода:
1 проход – при подъеме из подуровня (pDown)
создание копии звена,
заполнение поля pDown (подуровень уже скопирован)
запись в поле Str значения Copy (для распознания звена при попадании на него при втором проходе),
запись в поле pNext указателя на звено-оригинал (для возможности последующего копирования текста исходной строки),
запись указателя на звено-копию в стек
2 проход – при извлечении звена из стека
заполнение полей Str и pNext,
указатель на звено-копию запоминается в переменной cpl
Редактирование текстов

из 38
ИТММ ННГУ, 2002-2020
3. Реализация – копирование текста
Редактирование текстов
Пример: программа
Исходный текст
Текст - копия

из 38
ИТММ ННГУ, 2002-2020
3. Реализация – повторное использование памяти (сборка мусора) …
Общая замечания
При удалении разделов текста для освобождения звеньев следует учитывать следующие моменты:
обход всех звеньев удаляемого текста может потребовать длительного времени,
при множественности ссылок на разделы текста (для устранения дублирования одинаковых частей) удаляемый текст нельзя исключить – этот текст может быть задействован в других фрагментах текста
Память, занимаемая удаляемым текстом, не освобождается, а удаление текста фиксируется установкой указателей в состояние NULL (например, pFirst=NULL)
Редактирование текстов

из 38
ИТММ ННГУ, 2002-2020
3. Реализация – повторное использование памяти (сборка мусора) …
Подобный способ выполнения операций удаления текста может привести к ситуации, когда в памяти, используемой для хранения текста, могут присутствовать звенья, на которые нет ссылок в тексте и которые не возвращены в систему управления памятью для повторного использования. Элементы памяти такого вида носят наименование "мусора"
Наличие "мусора" в системе может быть допустимым, если имеющейся свободой памяти достаточно для работы программ. В случае нехватки памяти необходимо выполнить "сборку мусора" (garbage collection)
Редактирование текстов

из 38
ИТММ ННГУ, 2002-2020
3. Реализация – повторное использование памяти (сборка мусора) …
Общая схема подхода…
При освобождение звена в операторе delete звено включается в список свободных звеньев
// освобождение звена
void operator delete (void *pM) {
PTTextLink pLink = (PTTextLink)pM;
pLink->pNext = MemHeader.pFree;
MemHeader.pFree = pLink;
}
Редактирование текстов

из 38
ИТММ ННГУ, 2002-2020
3. Реализация – повторное использование памяти (сборка мусора)
Как при сканировании памяти различать звенья "мусора" и звенья текста ?
Возможный подход – маркировка текстовых звеньев и звеньев списка свободных звеньев
Редактирование текстов
Пример: программа

Характер использования текста определяет способ его представления
Для хранения иерархически-представленного текста могут быть использованы связные списки
Связные списки является общей структурой хранения структур типа дерева
Использование итераторов позволяет обеспечить единый и простой способ обработки различных структур данных
При разработке структур хранения сложных данных может потребоваться создание дополнительных средств управления памятью
Возможный подход управления памятью – накопление и сборка мусора
из 38
Заключение
ИТММ ННГУ, 2002-2020
Редактирование текстов

из 38
Вопросы для обсуждения
ИТММ ННГУ, 2002-2020
Дополнительные модели представления текста
Набор операций при работе со связными списками
Рекурсивные и итеративные алгоритмы обработки данных
Статические данные и статические методы классов
Перегрузка операторов new и delete
Способы недопущения мусора при множественности ссылок на структурные элементы структуры хранения
Редактирование текстов

Расширение набора операций обработки текста (изменение структуры текста, копирование)
Разработка визуальных средств работы с иерархическим текстом
из 38
Темы заданий для самостоятельной работы
ИТММ ННГУ, 2002-2020
Редактирование текстов

Структуры хранения геометрических объектов на ЭВМ
из 38
Следующая тема
ИТММ ННГУ, 2002-2020
Редактирование текстов