Списковые структуры.
Списковые структуры строят из специальных элементов, включающих помимо информационной части еще и один или несколько указателей - адресов элементов или вложенных структур, связанных с данным элементом. Размещая подобные элементы в динамической памяти можно организовывать различные внутренние структуры (рис. 5,15).
|
Однако при использовании списковых структур следует помнить, что:
• для хранения указателей необходима дополнительная память;
• поиск информации в Линейных списках осуществляется последовательно, а потому требует больше времени;
• построение списков и выполнение операций над элементами данных,
хранящимися в списках, требует более высокой квалификации программистов, более трудоемко, а соответствующие подпрограммы содержат больше ошибок и, следовательно, требуют более тщательного тестирования.
Обычно векторное представление используют для хранения статических множеств, таблиц (одномерных и многомерных), например, матриц, строк, записей, а также графов, представленных матрицей смежности, матрицей инцидентности или аналитически [55]. Списковое представление удобно для хранения динамических (изменяемых) структур и структур со сложными связями.
В наиболее ответственных случаях при выборе внутреннего представления целесообразно определять вычислительную сложность [24, 55] выполнения наиболее часто встречающихся операций со структурой данных или ее элементами для различных вариантов. А также оценивать их емкостную сложность.
Например,предложены 10 вариантов внутреннего представления неориентированного графа. Для выбора структуры необходимы исследования - расчет временной сложности указанных операций на уровне машинных команд в тактах микропроцессора для каждого представления и емкостной сложности этих представлений. Анализ результатов показывает, что, если число вершин n<=100, то с точки зрения уменьшения времени выполнения наиболее эффективное представление - массив списков. Если же существенно экономное использование оперативной памяти, то наиболее эффективное представление - массив динамических векторов.