Cтраница 4
Узлы определяются ссылками на узлы, поэтому связные списки иногда называют самоссылочыми ( self-referent) структурами. Более того, хотя узел обычно ссылается на другой узел, возможна ссылка на самого себя, поэтому связные списки могут представлять собой циклические ( cyclic) структуры. Последствия этих двух фактов станут ясны при рассмотрении конкретных представлений и применений связных списков. [46]
Разработка абстрактных моделей для данных и способов обработки этих данных является важнейшим компонентом в процессе решения задач с помощью компьютера. Примеры этого мы видим на низком уровне в повседневном программировании ( когда, например, как обсуждалось в главе 3, мы используем массивы и связные списки) и на высоком уровне при решении прикладных задач ( как было продемонстрировано в главе 1, во время использования бора union-find при решении задачи связности. В настоящей главе рассматриваются абстрактные типы данных ( abstract data type, в дальнейшем АТД), позволяющие создавать программы с использованием высокоуровневых абстракций. За счет применения абстрактных типов данных появляется возможность отделять абстрактные ( концептуальные) преобразования, которые программы выполняют над данными, от любого конкретного представления структуры данных и любой конкретной реализации алгоритма. [47]
Можно объявить размер массива таким, чтобы он мог вместить большее число элементов, чем ожидается. Но это может привести к избыточному расходу памяти. Связные списки могут обеспечивать более рациональное использование памяти. Связные списки позволяют программе настраиваться во время счета. [48]
Мы изучили такие структуры данных фиксированного размера, как одномерные индексированные массивы, двумерные индексированные массивы и структуры struct. В этой главе вводятся динамические структуры данных, которые нарастают и сокращаются в процессе выполнения программы. Связные списки являются наборами элементов данных, выстроенными в линейку; операции вставки элементов данных и их удаления могут осуществляться в любом месте связного списка. Стеки играют существенную роль в компиляторах и операционных системах; операции вставки и удаления проводятся в конце стека, то есть в его вершине. Бинарные деревья способствуют высокоскоростному поиску и быстрой сортировке данных, эффективному удалению дубликатов элементов данных, отображению системы каталогов файлов а также компиляции выражений на машинный язык. У этих структур данных имеется много других любопытных приложений. [49]
Можно объявить размер массива таким, чтобы он мог вместить большее число элементов, чем ожидается. Но это может привести к избыточному расходу памяти. Связные списки могут обеспечивать более рациональное использование памяти. Связные списки позволяют программе настраиваться во время счета. [50]
Вставка и удаление любого элемента связного списка) Наш шаблон класса связных списков выполняет операции вставки и удаления элементов только в начале и конце списка. Эти возможности удобны в том случае, если мы используем скрытое наследование и композицию для разработки шаблонов класса стеков и класса очередей с помощью незначительных добавлений к повторно используемому шаблону класса связных списков. Действительно, связные списки являются наиболее общими структурами, которые мы используем в программах. [51]
Указатели в Фортране используются как временные универсальные псевдонимы, с помощью которых можно ссылаться на различные реальные объекты определенного типа. Связь указателя с действительным объектом может быть установлена и разорвана в ходе выполнения программы. С помощью указателей можно создавать связные списки, назначать имена сечениям массивов и векторным индексам. [52]