Cтраница 4
Мы изучили такие структуры данных фиксированного размера, как одномерные индексированные массивы, двумерные индексированные массивы и структуры struct. В этой главе вводятся динамические структуры данных, которые нарастают и сокращаются в процессе выполнения программы. Связные списки являются наборами элементов данных, выстроенными в линейку; операции вставки элементов данных и их удаления могут осуществляться в любом месте связного списка. Стеки играют существенную роль в компиляторах и операционных системах; операции вставки и удаления проводятся в конце стека, то есть в его вершине. Бинарные деревья способствуют высокоскоростному поиску и быстрой сортировке данных, эффективному удалению дубликатов элементов данных, отображению системы каталогов файлов а также компиляции выражений на машинный язык. У этих структур данных имеется много других любопытных приложений. [46]
В настоящей главе обсуждается много алгоритмов поиска имени г в таблице. Из всех операций, производимых над таблицей, отыскание одного элемента является наиболее общей. Действительно, существуют таблицы, на которых после их построения никогда не производится других операций. Тут разумно не пожалеть усилий и построить эти таблицы так, чтобы минимизировать время поиска. Это положение иллюстрируют оптимальные бинарные деревья поиска ( разд. [47]