Лабораторная работа по дисциплине "Технология программирования"

Содержание1. Ознакомиться с теоретическими сведениями по абстрактным структурам данных и методами их обработки.
2. Для указанной задачи и типа данных (см. таблицу 2) предложить способ реализации и определить требуемый объем памяти.
3. Провести анализ заданных методов поиска, упорядочения и корректировки. Оценить время выполнения соответствующих операций.
4. Предложить альтернативный вариант решения задачи, в котором должно быть минимум одно улучшение.
ВведениеЦель работы
Цель работы - исследование структур данных, методов их обработки и оценки.
Улучшения могут касаться как структуры данных, так и основных операций. Обосновать новые решения, используя количественные и качественные критерии. Количественными критериями являются: объем памяти, среднее количество сравнений и количество тактов. Качественные критерии определяют возможность использования того или иного метода применительно к разработанной структуре. К ним можно отнести: применимость операции только к упорядоченным данным; необходимость знать количество элементов; наличие признака разбивки на гнезда; необходимость в прямом доступе к элементам; знание граничных значений; невозможность создать структуру в соответствии с арифметической прогрессией и др.
Задача 1. Дано N элементов, где каждый элемент является предложением на естественном языке.
Физическая структура данных
Односвязный линейный список (Однонаправленный связный список).

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

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