Программная инженерия Нижний Новгород 017 Лабораторный

1.3. Условия и ограничения 
В рамках выполнения данной лабораторной работы могут быть использованы следующие 
основные допущения: 

При планировании структуры текста в качестве самого нижнего уровня можно 
рассматривать уровень строк. 

В качестве тестовых текстов можно рассматривать текстовые файлы программы. 
2. Метод решения 
2.1. Структуры данных 
При выборе модели представления текста необходимо учитывать, какие операции будут 
выполняться. Можно рассмотреть несколько моделей представления текста: текст можно 
рассматривать 
как 
линейную 
последовательность 
символов, 
как 
линейную 
последовательность строк, как линейную последовательность страниц и т.д. 
Так, для следующего примера текста: 
pFirst=NULL 
ListLen=0 

---

 
69 
представление текста в виде последовательности символов имеет вид: 
а представление в виде последовательности слов может иметь следующий формат: 
Единство возможных моделей текста можно обеспечить, если при введении каждого более 
высокого уровня использовать все ранее введенные (ниже расположенные) структуры 
представления. Такой подход может быть реализован с использованием иерархических 
связных списков. Звенья такого списка содержат по два указателя: один используется для 
организации отношения следования по элементам текста одного и того же уровня, а другой – 
для указания отношения следования по иерархии уровней представления текста (от более 
высокого уровня к ниже расположенному). 
В силу необходимости выполнения операций редактирования текст является 
динамической структурой данных. В соотвествтии с определением, динамическая 
структура есть математическая структура, которой соответствует частично-упорядоченное 
(по включению) базовое множество М, элементы которого являются структурами данных. При 
этом отношения включения индуцируются операцииями преобразования структуры данных. 
Необходимым условием применения связного списка как структуры хранения текста 
является возможность нахождения такого унифицированного типа звеньев, который можно 
было бы использовать на любых уровнях представления текста, так как реализация своего типа 
звеньев для каждого уровня приведет к увеличению трудоемкости управления памятью и 
дублированию программ обработки. Возможное решение при выборе структуры звеньев 
может состоять в следующем: 

каждое звено структуры хранения содержит два поля указателей и поле для хранения 
данных; 

нижний уровень иерархической структуры звеньев ограничивается уровнем строк, а не 
символов. Это повышает эффективность использования памяти, так как в случае 
отдельного уровня для хранения символов, затраты на хранение служебной информации 
(указатели) в несколько раз превышают затраты на хранение самих данных.При 
использовании строк в качестве атомарных элементов поле для хранения данных является 
массивом символов заданного размера; 

количество уровней и количество звеньев на каждом уровне может быть произвольным;